xref: /dragonfly/usr.bin/undo/undo.c (revision d2cd83ff) 
1 /*
2  * Copyright (c) 2008 The DragonFly Project.  All rights reserved.
3  *
4  * This code is derived from software contributed to The DragonFly Project
5  * by Matthew Dillon <dillon@backplane.com>
6  *
7  * Redistribution and use in source and binary forms, with or without
8  * modification, are permitted provided that the following conditions
9  * are met:
10  *
11  * 1. Redistributions of source code must retain the above copyright
12  *    notice, this list of conditions and the following disclaimer.
13  * 2. Redistributions in binary form must reproduce the above copyright
14  *    notice, this list of conditions and the following disclaimer in
15  *    the documentation and/or other materials provided with the
16  *    distribution.
17  * 3. Neither the name of The DragonFly Project nor the names of its
18  *    contributors may be used to endorse or promote products derived
19  *    from this software without specific, prior written permission.
20  *
21  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
24  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE
25  * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
26  * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING,
27  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
28  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
29  * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
30  * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
31  * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
32  * SUCH DAMAGE.
33  *
34  * $DragonFly: src/usr.bin/undo/undo.c,v 1.6 2008/07/17 21:34:47 thomas Exp $
35  */
36 /*
37  * UNDO - retrieve an older version of a file.
38  */
39 
40 #include <sys/types.h>
41 #include <sys/stat.h>
42 #include <sys/wait.h>
43 #include <sys/tree.h>
44 #include <stdio.h>
45 #include <stdlib.h>
46 #include <stdarg.h>
47 #include <string.h>
48 #include <unistd.h>
49 #include <fcntl.h>
50 #include <errno.h>
51 #include <vfs/hammer/hammer_disk.h>
52 #include <vfs/hammer/hammer_ioctl.h>
53 
54 /*
55  * Sorted list of transaction ids
56  */
57 struct undo_hist_entry;
58 RB_HEAD(undo_hist_entry_rb_tree, undo_hist_entry);
59 RB_PROTOTYPE2(undo_hist_entry_rb_tree, undo_hist_entry, rbnode,
60 	undo_hist_entry_compare, hammer_tid_t);
61 
62 struct undo_hist_entry {
63 	RB_ENTRY(undo_hist_entry) rbnode;
64 	struct hammer_ioc_hist_entry tse;
65 	ino_t inum;
66 };
67 
68 enum undo_type { TYPE_FILE, TYPE_DIFF, TYPE_RDIFF, TYPE_HISTORY };
69 enum undo_cmd { CMD_DUMP, CMD_ITERATEALL };
70 
71 #define UNDO_FLAG_MULT		0x0001
72 #define UNDO_FLAG_INOCHG	0x0002
73 
74 static int undo_hist_entry_compare(struct undo_hist_entry *he1,
75 		    struct undo_hist_entry *he2);
76 static void doiterate(const char *filename, const char *outFileName,
77 		   const char *outFilePostfix, int flags,
78 		   struct hammer_ioc_hist_entry ts1,
79 		   enum undo_cmd cmd, enum undo_type type);
80 static void dogenerate(const char *filename, const char *outFileName,
81 		   const char *outFilePostfix,
82 		   int flags, int idx, enum undo_type type,
83 		   struct hammer_ioc_hist_entry ts1,
84 		   struct hammer_ioc_hist_entry ts2);
85 static void collect_history(int fd, int *error,
86 		   struct undo_hist_entry_rb_tree *tse_tree);
87 static void collect_dir_history(const char *filename, int *error,
88 		   struct undo_hist_entry_rb_tree *dir_tree);
89 static void clean_tree(struct undo_hist_entry_rb_tree *tree);
90 static hammer_tid_t parse_delta_time(const char *timeStr);
91 static void runcmd(int fd, const char *cmd, ...);
92 static char *timestamp(hammer_ioc_hist_entry_t hen);
93 static void usage(void);
94 
95 static int VerboseOpt;
96 
97 RB_GENERATE2(undo_hist_entry_rb_tree, undo_hist_entry, rbnode,
98 	undo_hist_entry_compare, hammer_tid_t, tse.tid);
99 
100 
101 int
102 main(int ac, char **av)
103 {
104 	const char *outFileName = NULL;
105 	const char *outFilePostfix = NULL;
106 	enum undo_cmd cmd;
107 	enum undo_type type;
108 	struct hammer_ioc_hist_entry ts1;
109 	struct hammer_ioc_hist_entry ts2;
110 	int c;
111 	int flags;
112 
113 	bzero(&ts1, sizeof(ts1));
114 	bzero(&ts2, sizeof(ts2));
115 
116 	cmd = CMD_DUMP;
117 	type = TYPE_FILE;
118 
119 	while ((c = getopt(ac, av, "adDiuvo:t:")) != -1) {
120 		switch(c) {
121 		case 'd':
122 			if (type != TYPE_FILE)
123 				usage();
124 			type = TYPE_DIFF;
125 			break;
126 		case 'D':
127 			if (type != TYPE_FILE)
128 				usage();
129 			type = TYPE_RDIFF;
130 			break;
131 		case 'i':
132 			if (type != TYPE_FILE)
133 				usage();
134 			type = TYPE_HISTORY;
135 			cmd = CMD_ITERATEALL;
136 			break;
137 		case 'a':
138 			cmd = CMD_ITERATEALL;
139 			break;
140 		case 'u':
141 			outFilePostfix = ".undo";
142 			break;
143 		case 'v':
144 			++VerboseOpt;
145 			break;
146 		case 'o':
147 			outFileName = optarg;
148 			break;
149 		case 't':
150 			if (ts1.tid && ts2.tid)
151 				usage();
152 			else if (ts1.tid == 0)
153 				ts1.tid = parse_delta_time(optarg);
154 			else
155 				ts2.tid = parse_delta_time(optarg);
156 			break;
157 		default:
158 			usage();
159 			/* NOT REACHED */
160 			break;
161 		}
162 	}
163 
164 	/*
165 	 * Option validation
166 	 */
167 	if (outFileName && outFilePostfix) {
168 		fprintf(stderr, "The -o option may not be combined with -u\n");
169 		usage();
170 	}
171 
172 	ac -= optind;
173 	av += optind;
174 	flags = 0;
175 	if (ac > 1)
176 		flags |= UNDO_FLAG_MULT;
177 
178 	if (ac == 0)
179 		usage();
180 
181 	/*
182 	 * Validate the output template, if specified.
183 	 */
184 	if (outFileName && (flags & UNDO_FLAG_MULT)) {
185 		const char *ptr = outFileName;
186 		int didStr = 0;
187 
188 		while ((ptr = strchr(ptr, '%')) != NULL) {
189 			if (ptr[1] == 's') {
190 				if (didStr) {
191 					fprintf(stderr, "Malformed output "
192 							"template\n");
193 					usage();
194 				}
195 				didStr = 1;
196 				++ptr;
197 			} else if (ptr[1] != '%') {
198 				fprintf(stderr, "Malformed output template\n");
199 				usage();
200 			} else {
201 				ptr += 2;
202 			}
203 		}
204 	}
205 
206 	while (ac) {
207 		doiterate(*av, outFileName, outFilePostfix,
208 			  flags, ts1, cmd, type);
209 		++av;
210 		--ac;
211 	}
212 	return(0);
213 }
214 
215 /*
216  * Iterate through a file's history.  If cmd == CMD_DUMP we take the
217  * next-to-last transaction id.  Otherwise if cmd == CMD_ITERATEALL
218  * we scan all transaction ids.
219  *
220  * Also iterate through the directory's history to locate other inodes that
221  * used the particular file name.
222  */
223 static
224 void
225 doiterate(const char *filename, const char *outFileName,
226 	  const char *outFilePostfix, int flags,
227 	  struct hammer_ioc_hist_entry ts1,
228 	  enum undo_cmd cmd, enum undo_type type)
229 {
230 	struct undo_hist_entry_rb_tree dir_tree;
231 	struct undo_hist_entry_rb_tree tse_tree;
232 	struct undo_hist_entry *tse1;
233 	struct undo_hist_entry *tse2;
234 	struct hammer_ioc_hist_entry ts2, tid_max;
235 	char *path = NULL;
236 	int i;
237 	int fd;
238 	int error;
239 
240 	RB_INIT(&dir_tree);
241 	RB_INIT(&tse_tree);
242 
243 	tid_max.tid = HAMMER_MAX_TID;
244 	tid_max.time32 = 0;
245 
246 	/*
247 	 * Use the directory history to locate all possible versions of
248 	 * the file.
249 	 */
250 	collect_dir_history(filename, &error, &dir_tree);
251 	RB_FOREACH(tse1, undo_hist_entry_rb_tree, &dir_tree) {
252 		asprintf(&path, "%s@@0x%016llx", filename, tse1->tse.tid);
253 		if ((fd = open(path, O_RDONLY)) > 0) {
254 			collect_history(fd, &error, &tse_tree);
255 			close(fd);
256 		}
257 	}
258 	if (cmd == CMD_DUMP) {
259 		/*
260 		 * Single entry, most recent prior to current
261 		 */
262 		if (ts1.tid == 0 && RB_EMPTY(&tse_tree)) {
263 			if ((fd = open(filename, O_RDONLY)) > 0) {
264 				collect_history(fd, &error, &tse_tree);
265 				close(fd);
266 			}
267 		}
268 		if (ts1.tid == 0) {
269 			tse2 = RB_MAX(undo_hist_entry_rb_tree, &tse_tree);
270 			if (tse2) {
271 				ts2 = tse2->tse;
272 				tse1 = RB_PREV(undo_hist_entry_rb_tree,
273 					       &tse_tree, tse2);
274 				if (tse1)
275 					ts1 = tse1->tse;
276 			}
277 		}
278 		if (ts1.tid == 0) {
279 			printf("%s: No UNDO history found\n", filename);
280 		} else {
281 			dogenerate(filename,
282 				   outFileName, outFilePostfix,
283 				   0, 0, type,
284 				   ts1, ts2);
285 		}
286 	} else if (RB_ROOT(&tse_tree)) {
287 		/*
288 		 * Iterate entire history
289 		 */
290 		printf("%s: ITERATE ENTIRE HISTORY\n", filename);
291 
292 		tse1 = NULL;
293 		i = 0;
294 		RB_FOREACH(tse2, undo_hist_entry_rb_tree, &tse_tree) {
295 			if (tse1) {
296 				dogenerate(filename,
297 					   outFileName, outFilePostfix,
298 					   flags, i, type,
299 					   tse1->tse, tse2->tse);
300 			}
301 			if (tse1 && tse2->inum != tse1->inum)
302 				flags |= UNDO_FLAG_INOCHG;
303 			else
304 				flags &= ~UNDO_FLAG_INOCHG;
305 			tse1 = tse2;
306 			++i;
307 		}
308 		/*
309 		 * There is no delta to print for the last pair,
310 		 * because they are identical.
311 		 */
312 		if (type != TYPE_DIFF && type != TYPE_RDIFF) {
313 			dogenerate(filename,
314 				   outFileName, outFilePostfix,
315 				   flags, i, type,
316 				   tse1->tse, tid_max);
317 		}
318 	} else {
319 		printf("%s: ITERATE ENTIRE HISTORY: %s\n",
320 		       filename, strerror(error));
321 	}
322 	if (path)
323 		free(path);
324 	clean_tree(&dir_tree);
325 	clean_tree(&tse_tree);
326 }
327 
328 /*
329  * Generate output for a file as-of ts1 (ts1 may be 0!), if diffing then
330  * through ts2.
331  */
332 static
333 void
334 dogenerate(const char *filename, const char *outFileName,
335 	   const char *outFilePostfix,
336 	   int flags, int idx, enum undo_type type,
337 	   struct hammer_ioc_hist_entry ts1,
338 	   struct hammer_ioc_hist_entry ts2)
339 {
340 	struct stat st;
341 	const char *elm;
342 	char *ipath1 = NULL;
343 	char *ipath2 = NULL;
344 	FILE *fi;
345 	FILE *fp;
346 	char *buf;
347 	char *path;
348 	time_t t;
349 	struct tm *tp;
350 	char datestr[64];
351 	int n;
352 
353 	buf = malloc(8192);
354 
355 	/*
356 	 * Open the input file.  If ts1 is 0 try to locate the most recent
357 	 * version of the file prior to the current version.
358 	 */
359 	if (ts1.tid == 0)
360 		asprintf(&ipath1, "%s", filename);
361 	else
362 		asprintf(&ipath1, "%s@@0x%016llx", filename, ts1.tid);
363 
364 	if (ts2.tid == 0)
365 		asprintf(&ipath2, "%s", filename);
366 	else
367 		asprintf(&ipath2, "%s@@0x%016llx", filename, ts2.tid);
368 
369 	if (lstat(ipath1, &st) < 0 && lstat(ipath2, &st) < 0) {
370 		if (idx == 0 || VerboseOpt) {
371 			fprintf(stderr, "Unable to access either %s or %s\n",
372 				ipath1, ipath2);
373 		}
374 		free(ipath1);
375 		free(ipath2);
376 		goto done;
377 	}
378 
379 	/*
380 	 * elm is the last component of the input file name
381 	 */
382 	if ((elm = strrchr(filename, '/')) != NULL)
383 		++elm;
384 	else
385 		elm = filename;
386 
387 	/*
388 	 * Where do we stuff our output?
389 	 */
390 	if (outFileName) {
391 		if (flags & UNDO_FLAG_MULT) {
392 			asprintf(&path, outFileName, elm);
393 			fp = fopen(path, "w");
394 			if (fp == NULL) {
395 				perror(path);
396 				exit(1);
397 			}
398 			free(path);
399 		} else {
400 			fp = fopen(outFileName, "w");
401 			if (fp == NULL) {
402 				perror(outFileName);
403 				exit(1);
404 			}
405 		}
406 	} else if (outFilePostfix) {
407 		if (idx >= 0) {
408 			asprintf(&path, "%s%s.%04d", filename,
409 				 outFilePostfix, idx);
410 		} else {
411 			asprintf(&path, "%s%s", filename, outFilePostfix);
412 		}
413 		fp = fopen(path, "w");
414 		if (fp == NULL) {
415 			perror(path);
416 			exit(1);
417 		}
418 		free(path);
419 	} else {
420 		if ((flags & UNDO_FLAG_MULT) && type == TYPE_FILE) {
421 			if (idx >= 0) {
422 				printf("\n>>> %s %04d 0x%016llx %s\n\n",
423 				       filename, idx, ts1.tid, timestamp(&ts1));
424 			} else {
425 				printf("\n>>> %s ---- 0x%016llx %s\n\n",
426 				       filename, ts1.tid, timestamp(&ts1));
427 			}
428 		} else if (idx >= 0 && type == TYPE_FILE) {
429 			printf("\n>>> %s %04d 0x%016llx %s\n\n",
430 			       filename, idx, ts1.tid, timestamp(&ts1));
431 		}
432 		fp = stdout;
433 	}
434 
435 	switch(type) {
436 	case TYPE_FILE:
437 		if ((fi = fopen(ipath1, "r")) != NULL) {
438 			while ((n = fread(buf, 1, 8192, fi)) > 0)
439 				fwrite(buf, 1, n, fp);
440 			fclose(fi);
441 		}
442 		break;
443 	case TYPE_DIFF:
444 		printf("diff -N -r -u %s %s (to %s)\n",
445 		       ipath1, ipath2, timestamp(&ts2));
446 		fflush(stdout);
447 		runcmd(fileno(fp), "/usr/bin/diff", "diff", "-N", "-r", "-u", ipath1, ipath2, NULL);
448 		break;
449 	case TYPE_RDIFF:
450 		printf("diff -N -r -u %s %s\n", ipath2, ipath1);
451 		fflush(stdout);
452 		runcmd(fileno(fp), "/usr/bin/diff", "diff", "-N", "-r", "-u", ipath2, ipath1, NULL);
453 		break;
454 	case TYPE_HISTORY:
455 		t = (time_t)ts1.time32;
456 		tp = localtime(&t);
457 		strftime(datestr, sizeof(datestr), "%d-%b-%Y %H:%M:%S", tp);
458 		printf("\t0x%016llx %s", ts1.tid, datestr);
459 		if (flags & UNDO_FLAG_INOCHG)
460 			printf(" inode-change");
461 		if (lstat(ipath1, &st) < 0)
462 			printf(" file-deleted");
463 		printf("\n");
464 		break;
465 	}
466 
467 	if (fp != stdout)
468 		fclose(fp);
469 done:
470 	free(buf);
471 }
472 
473 static
474 void
475 clean_tree(struct undo_hist_entry_rb_tree *tree)
476 {
477 	struct undo_hist_entry *tse;
478 
479 	while ((tse = RB_ROOT(tree)) != NULL) {
480 		RB_REMOVE(undo_hist_entry_rb_tree, tree, tse);
481 		free(tse);
482 	}
483 }
484 
485 static
486 void
487 collect_history(int fd, int *errorp, struct undo_hist_entry_rb_tree *tse_tree)
488 {
489 	struct hammer_ioc_history hist;
490 	struct undo_hist_entry *tse;
491 	struct stat st;
492 	int istmp;
493 	int i;
494 
495 	/*
496 	 * Setup
497 	 */
498 	bzero(&hist, sizeof(hist));
499 	hist.beg_tid = HAMMER_MIN_TID;
500 	hist.end_tid = HAMMER_MAX_TID;
501 	hist.head.flags |= HAMMER_IOC_HISTORY_ATKEY;
502 	hist.key = 0;
503 	hist.nxt_key = HAMMER_MAX_KEY;
504 
505 	*errorp = 0;
506 
507 	if (tse_tree == NULL) {
508 		tse_tree = malloc(sizeof(*tse_tree));
509 		RB_INIT(tse_tree);
510 		istmp = 1;
511 	} else {
512 		istmp = 0;
513 	}
514 
515 	/*
516 	 * Save the inode so inode changes can be reported.
517 	 */
518 	st.st_ino = 0;
519 	fstat(fd, &st);
520 
521 	/*
522 	 * Collect a unique set of transaction ids
523 	 */
524 	if (ioctl(fd, HAMMERIOC_GETHISTORY, &hist) < 0) {
525 		*errorp = errno;
526 		goto done;
527 	}
528 	for (;;) {
529 		for (i = 0; i < hist.count; ++i) {
530 			tse = malloc(sizeof(*tse));
531 			tse->tse = hist.hist_ary[i];
532 			tse->inum = st.st_ino;
533 			if (RB_INSERT(undo_hist_entry_rb_tree, tse_tree, tse)) {
534 				free(tse);
535 			}
536 		}
537 		if (hist.head.flags & HAMMER_IOC_HISTORY_EOF)
538 			break;
539 		if (hist.head.flags & HAMMER_IOC_HISTORY_NEXT_KEY) {
540 			hist.key = hist.nxt_key;
541 			hist.nxt_key = HAMMER_MAX_KEY;
542 		}
543 		if (hist.head.flags & HAMMER_IOC_HISTORY_NEXT_TID)
544 			hist.beg_tid = hist.nxt_tid;
545 		if (ioctl(fd, HAMMERIOC_GETHISTORY, &hist) < 0) {
546 			*errorp = errno;
547 			break;
548 		}
549 	}
550 
551 	/*
552 	 * Cleanup
553 	 */
554 done:
555 	if (istmp) {
556 		clean_tree(tse_tree);
557 		free(tse_tree);
558 	}
559 }
560 
561 static
562 void
563 collect_dir_history(const char *filename, int *errorp,
564 		    struct undo_hist_entry_rb_tree *dir_tree)
565 {
566 	char *dirname;
567 	int fd;
568 	int error;
569 
570 	*errorp = 0;
571 	if (strrchr(filename, '/')) {
572 		dirname = strdup(filename);
573 		*strrchr(dirname, '/') = 0;
574 	} else {
575 		dirname = strdup(".");
576 	}
577 	if ((fd = open(dirname, O_RDONLY)) > 0) {
578 		collect_history(fd, &error, dir_tree);
579 		close(fd);
580 	}
581 }
582 
583 static
584 hammer_tid_t
585 parse_delta_time(const char *timeStr)
586 {
587 	hammer_tid_t tid;
588 
589 	tid = strtoull(timeStr, NULL, 0);
590 	return(tid);
591 }
592 
593 static void
594 runcmd(int fd, const char *cmd, ...)
595 {
596 	va_list va;
597 	pid_t pid;
598 	char **av;
599 	int ac;
600 	int i;
601 
602 	va_start(va, cmd);
603 	for (ac = 0; va_arg(va, void *) != NULL; ++ac)
604 		;
605 	va_end(va);
606 
607 	av = malloc((ac + 1) * sizeof(char *));
608 	va_start(va, cmd);
609 	for (i = 0; i < ac; ++i)
610 		av[i] = va_arg(va, char *);
611 	va_end(va);
612 	av[i] = NULL;
613 
614 	if ((pid = fork()) < 0) {
615 		perror("fork");
616 		exit(1);
617 	} else if (pid == 0) {
618 		if (fd != 1) {
619 			dup2(fd, 1);
620 			close(fd);
621 		}
622 		execv(cmd, av);
623 		_exit(1);
624 	} else {
625 		while (waitpid(pid, NULL, 0) != pid)
626 			;
627 	}
628 	free(av);
629 }
630 
631 /*
632  * Convert tid to timestamp.
633  */
634 static char *
635 timestamp(hammer_ioc_hist_entry_t hen)
636 {
637 	static char timebuf[64];
638 	time_t t = (time_t)hen->time32;
639 	struct tm *tp;
640 
641 	tp = localtime(&t);
642 	strftime(timebuf, sizeof(timebuf), "%d-%b-%Y %H:%M:%S", tp);
643 	return(timebuf);
644 }
645 
646 static
647 int
648 undo_hist_entry_compare(struct undo_hist_entry *he1,
649 			struct undo_hist_entry *he2)
650 {
651 	if (he1->tse.tid < he2->tse.tid)
652 		return(-1);
653 	if (he1->tse.tid > he2->tse.tid)
654 		return(1);
655 	return(0);
656 }
657 
658 static void
659 usage(void)
660 {
661 	fprintf(stderr, "undo [-adDiuv] [-o outfile] "
662 			"[-t transaction-id] [-t transaction-id] path...\n"
663 			"    -a       Iterate all historical segments\n"
664 			"    -d       Forward diff\n"
665 			"    -D       Reverse diff\n"
666 			"    -i       Dump history transaction ids\n"
667 			"    -u       Generate .undo files\n"
668 			"    -v       Verbose\n"
669 			"    -o file  Output to the specified file\n"
670 			"    -t TID   Retrieve as of transaction-id, TID\n"
671 			"             (a second `-t TID' to diff two versions)\n");
672 	exit(1);
673 }
674 
675