HAMMER Utilities: Use a Red-Black tree to track HAMMER TIDs, use diff -N
[dragonfly.git] / usr.bin / undo / undo.c
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 };
66
67 enum undo_type { TYPE_FILE, TYPE_DIFF, TYPE_RDIFF, TYPE_HISTORY };
68
69 static int undo_hist_entry_compare(struct undo_hist_entry *he1,
70                     struct undo_hist_entry *he2);
71 static void doiterate(const char *orig_filename, const char *outFileName,
72                    const char *outFilePostfix, int mult, enum undo_type type);
73 static void dogenerate(const char *filename, const char *outFileName,
74                    const char *outFilePostfix,
75                    int mult, int idx, enum undo_type type,
76                    struct hammer_ioc_hist_entry ts1,
77                    struct hammer_ioc_hist_entry ts2,
78                    int force);
79 static struct hammer_ioc_hist_entry
80             find_recent(const char *filename);
81 static struct hammer_ioc_hist_entry
82             output_history(const char *filename, int fd, FILE *fp,
83                    struct undo_hist_entry_rb_tree *tse_tree);
84 static struct hammer_ioc_hist_entry
85             collect_history(int fd, int *error,
86                    struct undo_hist_entry_rb_tree *tse_tree);
87 static hammer_tid_t parse_delta_time(const char *timeStr);
88 static void runcmd(int fd, const char *cmd, ...);
89 static char *timestamp(hammer_ioc_hist_entry_t hen);
90 static void usage(void);
91
92 static int VerboseOpt;
93
94 RB_GENERATE2(undo_hist_entry_rb_tree, undo_hist_entry, rbnode,
95         undo_hist_entry_compare, hammer_tid_t, tse.tid);
96
97
98 int
99 main(int ac, char **av)
100 {
101         const char *outFileName = NULL;
102         const char *outFilePostfix = NULL;
103         enum { CMD_DUMP, CMD_ITERATEALL } cmd;
104         enum undo_type type;
105         struct hammer_ioc_hist_entry ts1;
106         struct hammer_ioc_hist_entry ts2;
107         int c;
108         int mult;
109
110         bzero(&ts1, sizeof(ts1));
111         bzero(&ts2, sizeof(ts2));
112
113         cmd = CMD_DUMP;
114         type = TYPE_FILE;
115
116         while ((c = getopt(ac, av, "adDiuvo:t:")) != -1) {
117                 switch(c) {
118                 case 'd':
119                         if (type != TYPE_FILE)
120                                 usage();
121                         type = TYPE_DIFF;
122                         break;
123                 case 'D':
124                         if (type != TYPE_FILE)
125                                 usage();
126                         type = TYPE_RDIFF;
127                         break;
128                 case 'i':
129                         if (type != TYPE_FILE)
130                                 usage();
131                         type = TYPE_HISTORY;
132                         break;
133                 case 'a':
134                         cmd = CMD_ITERATEALL;
135                         break;
136                 case 'u':
137                         outFilePostfix = ".undo";
138                         break;
139                 case 'v':
140                         ++VerboseOpt;
141                         break;
142                 case 'o':
143                         outFileName = optarg;
144                         break;
145                 case 't':
146                         if (ts1.tid && ts2.tid)
147                                 usage();
148                         else if (ts1.tid == 0)
149                                 ts1.tid = parse_delta_time(optarg);
150                         else
151                                 ts2.tid = parse_delta_time(optarg);
152                         break;
153                 default:
154                         usage();
155                         /* NOT REACHED */
156                         break;
157                 }
158         }
159
160         /*
161          * Option validation
162          */
163         if (outFileName && outFilePostfix) {
164                 fprintf(stderr, "The -o option may not be combined with -u\n");
165                 usage();
166         }
167
168         ac -= optind;
169         av += optind;
170         mult = (ac > 1);
171
172         if (ac == 0)
173                 usage();
174
175         /*
176          * Validate the output template, if specified.
177          */
178         if (outFileName && mult) {
179                 const char *ptr = outFileName;
180                 int didStr = 0;
181
182                 while ((ptr = strchr(ptr, '%')) != NULL) {
183                         if (ptr[1] == 's') {
184                                 if (didStr) {
185                                         fprintf(stderr, "Malformed output "
186                                                         "template\n");
187                                         usage();
188                                 }
189                                 didStr = 1;
190                                 ++ptr;
191                         } else if (ptr[1] != '%') {
192                                 fprintf(stderr, "Malformed output template\n");
193                                 usage();
194                         } else {
195                                 ptr += 2;
196                         }
197                 }
198         }
199
200         while (ac) {
201                 switch(cmd) {
202                 case CMD_DUMP:
203                         dogenerate(*av, outFileName, outFilePostfix,
204                                    mult, -1, type, ts1, ts2, 1);
205                         break;
206                 case CMD_ITERATEALL:
207                         doiterate(*av, outFileName, outFilePostfix,
208                                   mult, type);
209                         break;
210                 }
211                 ++av;
212                 --ac;
213         }
214         return(0);
215 }
216
217 /*
218  * Iterate through a file's history
219  */
220 static
221 void
222 doiterate(const char *orig_filename, const char *outFileName,
223            const char *outFilePostfix, int mult, enum undo_type type)
224 {
225         struct undo_hist_entry_rb_tree tse_tree;
226         struct undo_hist_entry *tse1;
227         struct undo_hist_entry *tse2;
228         struct hammer_ioc_hist_entry tid_max;
229         struct hammer_ioc_hist_entry ts1;
230         const char *use_filename;
231         char *path = NULL;
232         int i;
233         int fd;
234
235         RB_INIT(&tse_tree);
236
237         tid_max.tid = HAMMER_MAX_TID;
238         tid_max.time32 = 0;
239
240         use_filename = orig_filename;
241         if ((fd = open(orig_filename, O_RDONLY)) < 0) {
242                 ts1 = find_recent(orig_filename);
243                 if (ts1.tid) {
244                         asprintf(&path, "%s@@0x%016llx",
245                                  orig_filename, ts1.tid);
246                         use_filename = path;
247                 }
248         }
249
250         if ((fd = open(use_filename, O_RDONLY)) >= 0) {
251                 printf("%s: ITERATE ENTIRE HISTORY\n", orig_filename);
252                 output_history(NULL, fd, NULL, &tse_tree);
253                 close(fd);
254
255                 tse1 = NULL;
256                 i = 0;
257                 RB_FOREACH(tse2, undo_hist_entry_rb_tree, &tse_tree) {
258                         if (tse1) {
259                                 dogenerate(orig_filename,
260                                            outFileName, outFilePostfix,
261                                            mult, i, type,
262                                            tse1->tse, tse2->tse, 0);
263                         }
264                         tse1 = tse2;
265                         ++i;
266                 }
267                 if (!RB_EMPTY(&tse_tree)) {
268                         dogenerate(orig_filename,
269                                    outFileName, outFilePostfix,
270                                    mult, i, type,
271                                    tse1->tse, tid_max, 0);
272                 }
273         } else {
274                 printf("%s: ITERATE ENTIRE HISTORY: %s\n",
275                         orig_filename, strerror(errno));
276         }
277         if (path)
278                 free(path);
279 }
280
281 /*
282  * Generate output for a file as-of ts1 (ts1 may be 0!), if diffing then
283  * through ts2.
284  */
285 static
286 void
287 dogenerate(const char *filename, const char *outFileName,
288            const char *outFilePostfix,
289            int mult, int idx, enum undo_type type,
290            struct hammer_ioc_hist_entry ts1,
291            struct hammer_ioc_hist_entry ts2,
292            int force)
293 {
294         struct stat st;
295         const char *elm;
296         char *ipath1 = NULL;
297         char *ipath2 = NULL;
298         FILE *fi;
299         FILE *fp; 
300         char *buf;
301         char *path;
302         int n;
303
304         buf = malloc(8192);
305
306         /*
307          * Open the input file.  If ts1 is 0 try to locate the most recent
308          * version of the file prior to the current version.
309          */
310         if (ts1.tid == 0)
311                 ts1 = find_recent(filename);
312         if (ts1.tid == 0)
313                 asprintf(&ipath1, "%s", filename);
314         else
315                 asprintf(&ipath1, "%s@@0x%016llx", filename, ts1.tid);
316
317         if (ts2.tid == 0)
318                 asprintf(&ipath2, "%s", filename);
319         else
320                 asprintf(&ipath2, "%s@@0x%016llx", filename, ts2.tid);
321
322         if (lstat(ipath1, &st) < 0 && lstat(ipath2, &st) < 0) {
323                 if (force == 0 || VerboseOpt) {
324                         fprintf(stderr, "Unable to access either %s or %s\n",
325                                 ipath1, ipath2);
326                 }
327                 free(ipath1);
328                 free(ipath2);
329                 goto done;
330         }
331
332         /*
333          * elm is the last component of the input file name
334          */
335         if ((elm = strrchr(filename, '/')) != NULL)
336                 ++elm;
337         else
338                 elm = filename;
339
340         /*
341          * Where do we stuff our output?
342          */
343         if (outFileName) {
344                 if (mult) {
345                         asprintf(&path, outFileName, elm);
346                         fp = fopen(path, "w");
347                         if (fp == NULL) {
348                                 perror(path);
349                                 exit(1);
350                         }
351                         free(path);
352                 } else {
353                         fp = fopen(outFileName, "w");
354                         if (fp == NULL) {
355                                 perror(outFileName);
356                                 exit(1);
357                         }
358                 }
359         } else if (outFilePostfix) {
360                 if (idx >= 0) {
361                         asprintf(&path, "%s%s.%04d", filename,
362                                  outFilePostfix, idx);
363                 } else {
364                         asprintf(&path, "%s%s", filename, outFilePostfix);
365                 }
366                 fp = fopen(path, "w");
367                 if (fp == NULL) {
368                         perror(path);
369                         exit(1);
370                 }
371                 free(path);
372         } else {
373                 if (mult && type == TYPE_FILE) {
374                         if (idx >= 0) {
375                                 printf("\n>>> %s %04d 0x%016llx %s\n\n",
376                                        filename, idx, ts1.tid, timestamp(&ts1));
377                         } else {
378                                 printf("\n>>> %s ---- 0x%016llx %s\n\n",
379                                        filename, ts1.tid, timestamp(&ts1));
380                         }
381                 } else if (idx >= 0 && type == TYPE_FILE) {
382                         printf("\n>>> %s %04d 0x%016llx %s\n\n", 
383                                filename, idx, ts1.tid, timestamp(&ts1));
384                 }
385                 fp = stdout;
386         }
387
388         switch(type) {
389         case TYPE_FILE:
390                 if ((fi = fopen(ipath1, "r")) != NULL) {
391                         while ((n = fread(buf, 1, 8192, fi)) > 0)
392                                 fwrite(buf, 1, n, fp);
393                         fclose(fi);
394                 }
395                 break;
396         case TYPE_DIFF:
397                 printf("diff -N -r -u %s %s (to %s)\n",
398                        ipath1, ipath2, timestamp(&ts2));
399                 fflush(stdout);
400                 runcmd(fileno(fp), "/usr/bin/diff", "diff", "-N", "-r", "-u", ipath1, ipath2, NULL);
401                 break;
402         case TYPE_RDIFF:
403                 printf("diff -N -r -u %s %s\n", ipath2, ipath1);
404                 fflush(stdout);
405                 runcmd(fileno(fp), "/usr/bin/diff", "diff", "-N", "-r", "-u", ipath2, ipath1, NULL);
406                 break;
407         case TYPE_HISTORY:
408                 if ((fi = fopen(ipath1, "r")) != NULL) {
409                         output_history(filename, fileno(fi), fp, NULL);
410                         fclose(fi);
411                 }
412                 break;
413         }
414
415         if (fp != stdout)
416                 fclose(fp);
417 done:
418         free(buf);
419 }
420
421 /*
422  * Try to find a recent version of the file.
423  *
424  * XXX if file cannot be found
425  */
426 static
427 struct hammer_ioc_hist_entry
428 find_recent(const char *filename)
429 {
430         struct undo_hist_entry_rb_tree tse_tree;
431         struct undo_hist_entry *tse;
432         struct hammer_ioc_hist_entry hen;
433         char *dirname;
434         char *path;
435         int fd;
436
437         RB_INIT(&tse_tree);
438
439         if ((fd = open(filename, O_RDONLY)) >= 0) {
440                 hen = output_history(NULL, fd, NULL, NULL);
441                 close(fd);
442                 return(hen);
443         }
444
445         /*
446          * If the object does not exist acquire the history of its
447          * directory and then try accessing the object at each TID.
448          */
449         if (strrchr(filename, '/')) {
450                 dirname = strdup(filename);
451                 *strrchr(dirname, '/') = 0;
452         } else {
453                 dirname = strdup(".");
454         }
455
456         hen.tid = 0;
457         hen.time32 = 0;
458         if ((fd = open(dirname, O_RDONLY)) >= 0) {
459                 output_history(NULL, fd, NULL, &tse_tree);
460                 close(fd);
461                 free(dirname);
462
463                 tse = RB_MAX(undo_hist_entry_rb_tree, &tse_tree);
464                 while (tse) {
465                         asprintf(&path, "%s@@0x%016llx",
466                                  filename, tse->tse.tid);
467                         if ((fd = open(path, O_RDONLY)) >= 0) {
468                                 hen = output_history(NULL, fd, NULL, NULL);
469                                 close(fd);
470                                 free(path);
471                                 break;
472                         }
473                         free(path);
474                         tse = RB_PREV(undo_hist_entry_rb_tree, &tse_tree, tse);
475                 }
476         }
477         while ((tse = RB_ROOT(&tse_tree)) != NULL) {
478                 RB_REMOVE(undo_hist_entry_rb_tree, &tse_tree, tse);
479                 free(tse);
480         }
481         return(hen);
482 }
483
484 static
485 struct hammer_ioc_hist_entry
486 output_history(const char *filename, int fd, FILE *fp,
487                struct undo_hist_entry_rb_tree *tse_tree)
488 {
489         struct hammer_ioc_hist_entry hen;
490         struct undo_hist_entry *tse;
491         char datestr[64];
492         struct tm *tp;
493         time_t t;
494         int istmp;
495         int error;
496
497         /*
498          * Setup
499          */
500         if (tse_tree == NULL) {
501                 tse_tree = malloc(sizeof(*tse_tree));
502                 RB_INIT(tse_tree);
503                 istmp = 1;
504         } else {
505                 istmp = 0;
506         }
507
508         /*
509          * Collect a unique set of transaction ids
510          */
511         hen = collect_history(fd, &error, tse_tree);
512
513         if (error && filename)
514                 printf("%s: %s\n", filename, strerror(errno));
515         else if (filename)
516                 printf("%s:\n", filename);
517
518         /*
519          * If fp != NULL dump the history to stdout.
520          */
521         if (fp) {
522                 RB_FOREACH(tse, undo_hist_entry_rb_tree, tse_tree) {
523                         t = (time_t)tse->tse.time32;
524                         tp = localtime(&t);
525                         strftime(datestr, sizeof(datestr),
526                                  "%d-%b-%Y %H:%M:%S", tp);
527                         printf("\t0x%016llx %s\n", tse->tse.tid, datestr);
528                 }
529         }
530
531         /*
532          * Caller did not want a tree returned
533          */
534         if (istmp) {
535                 while ((tse = RB_ROOT(tse_tree)) != NULL) {
536                         RB_REMOVE(undo_hist_entry_rb_tree, tse_tree, tse);
537                         free(tse);
538                 }
539                 free(tse_tree);
540         }
541         return(hen);
542 }
543
544 static
545 struct hammer_ioc_hist_entry
546 collect_history(int fd, int *errorp, struct undo_hist_entry_rb_tree *tse_tree)
547 {
548         struct hammer_ioc_hist_entry hen;
549         struct hammer_ioc_history hist;
550         struct undo_hist_entry *tse;
551         int istmp;
552         int i;
553
554         /*
555          * Setup
556          */
557         bzero(&hist, sizeof(hist));
558         hist.beg_tid = HAMMER_MIN_TID;
559         hist.end_tid = HAMMER_MAX_TID;
560         hist.head.flags |= HAMMER_IOC_HISTORY_ATKEY;
561         hist.key = 0;
562         hist.nxt_key = HAMMER_MAX_KEY;
563
564         hen.tid = 0;
565         hen.time32 = 0;
566
567         *errorp = 0;
568
569         if (tse_tree == NULL) {
570                 tse_tree = malloc(sizeof(*tse_tree));
571                 RB_INIT(tse_tree);
572                 istmp = 1;
573         } else {
574                 istmp = 0;
575         }
576
577         /*
578          * Collect a unique set of transaction ids
579          */
580         if (ioctl(fd, HAMMERIOC_GETHISTORY, &hist) < 0) {
581                 *errorp = errno;
582                 goto done;
583         }
584         for (;;) {
585                 for (i = 0; i < hist.count; ++i) {
586                         tse = malloc(sizeof(*tse));
587                         tse->tse = hist.hist_ary[i];
588                         if (RB_INSERT(undo_hist_entry_rb_tree, tse_tree, tse)) {
589                                 free(tse);
590                         }
591                 }
592                 if (hist.head.flags & HAMMER_IOC_HISTORY_EOF)
593                         break;
594                 if (hist.head.flags & HAMMER_IOC_HISTORY_NEXT_KEY) {
595                         hist.key = hist.nxt_key;
596                         hist.nxt_key = HAMMER_MAX_KEY;
597                 }
598                 if (hist.head.flags & HAMMER_IOC_HISTORY_NEXT_TID) 
599                         hist.beg_tid = hist.nxt_tid;
600                 if (ioctl(fd, HAMMERIOC_GETHISTORY, &hist) < 0) {
601                         *errorp = errno;
602                         break;
603                 }
604         }
605
606         /*
607          * Locate next-to-last entry
608          */
609         tse = RB_MAX(undo_hist_entry_rb_tree, tse_tree);
610         if (tse)
611                 tse = RB_PREV(undo_hist_entry_rb_tree, tse_tree, tse);
612         if (tse)
613                 hen = tse->tse;
614
615         /*
616          * Cleanup
617          */
618 done:
619         if (istmp) {
620                 while ((tse = RB_ROOT(tse_tree)) != NULL) {
621                         RB_REMOVE(undo_hist_entry_rb_tree, tse_tree, tse);
622                         free(tse);
623                 }
624                 free(tse_tree);
625         }
626         return(hen);
627 }
628
629 static
630 hammer_tid_t
631 parse_delta_time(const char *timeStr)
632 {
633         hammer_tid_t tid;
634
635         tid = strtoull(timeStr, NULL, 0);
636         return(tid);
637 }
638
639 static void
640 runcmd(int fd, const char *cmd, ...)
641 {
642         va_list va;
643         pid_t pid;
644         char **av;
645         int ac;
646         int i;
647
648         va_start(va, cmd);
649         for (ac = 0; va_arg(va, void *) != NULL; ++ac)
650                 ;
651         va_end(va);
652
653         av = malloc((ac + 1) * sizeof(char *));
654         va_start(va, cmd);
655         for (i = 0; i < ac; ++i)
656                 av[i] = va_arg(va, char *);
657         va_end(va);
658         av[i] = NULL;
659
660         if ((pid = fork()) < 0) {
661                 perror("fork");
662                 exit(1);
663         } else if (pid == 0) {
664                 if (fd != 1) {
665                         dup2(fd, 1);
666                         close(fd);
667                 }
668                 execv(cmd, av);
669                 _exit(1);
670         } else {
671                 while (waitpid(pid, NULL, 0) != pid)
672                         ;
673         }
674         free(av);
675 }
676
677 /*
678  * Convert tid to timestamp.
679  */
680 static char *
681 timestamp(hammer_ioc_hist_entry_t hen)
682 {
683         static char timebuf[64];
684         time_t t = (time_t)hen->time32;
685         struct tm *tp;
686
687         tp = localtime(&t);
688         strftime(timebuf, sizeof(timebuf), "%d-%b-%Y %H:%M:%S", tp);
689         return(timebuf);
690 }
691
692 static
693 int
694 undo_hist_entry_compare(struct undo_hist_entry *he1,
695                         struct undo_hist_entry *he2)
696 {
697         if (he1->tse.tid < he2->tse.tid)
698                 return(-1);
699         if (he1->tse.tid > he2->tse.tid)
700                 return(1);
701         return(0);
702 }
703
704 static void
705 usage(void)
706 {
707         fprintf(stderr, "undo [-adDiuv] [-o outfile] "
708                         "[-t transaction-id] [-t transaction-id] path...\n"
709                         "    -a       Iterate all historical segments\n"
710                         "    -d       Forward diff\n"
711                         "    -D       Reverse diff\n"
712                         "    -i       Dump history transaction ids\n"
713                         "    -u       Generate .undo files\n"
714                         "    -v       Verbose\n"
715                         "    -o file  Output to the specified file\n"
716                         "    -t TID   Retrieve as of transaction-id, TID\n"
717                         "             (a second `-t TID' to diff two versions)\n");
718         exit(1);
719 }
720