HAMMER Utilities: Use a Red-Black tree to track HAMMER TIDs, use diff -N
[dragonfly.git] / usr.bin / undo / undo.c
index 643c383..fe79497 100644 (file)
@@ -31,7 +31,7 @@
  * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  * SUCH DAMAGE.
  * 
- * $DragonFly: src/usr.bin/undo/undo.c,v 1.1 2008/06/01 02:03:10 dillon Exp $
+ * $DragonFly: src/usr.bin/undo/undo.c,v 1.6 2008/07/17 21:34:47 thomas Exp $
  */
 /*
  * UNDO - retrieve an older version of a file.
@@ -40,6 +40,7 @@
 #include <sys/types.h>
 #include <sys/stat.h>
 #include <sys/wait.h>
+#include <sys/tree.h>
 #include <stdio.h>
 #include <stdlib.h>
 #include <stdarg.h>
 #include <vfs/hammer/hammer_disk.h>
 #include <vfs/hammer/hammer_ioctl.h>
 
+/*
+ * Sorted list of transaction ids
+ */
+struct undo_hist_entry;
+RB_HEAD(undo_hist_entry_rb_tree, undo_hist_entry);
+RB_PROTOTYPE2(undo_hist_entry_rb_tree, undo_hist_entry, rbnode,
+       undo_hist_entry_compare, hammer_tid_t);
+
+struct undo_hist_entry {
+       RB_ENTRY(undo_hist_entry) rbnode;
+       struct hammer_ioc_hist_entry tse;
+};
+
 enum undo_type { TYPE_FILE, TYPE_DIFF, TYPE_RDIFF, TYPE_HISTORY };
 
+static int undo_hist_entry_compare(struct undo_hist_entry *he1,
+                   struct undo_hist_entry *he2);
 static void doiterate(const char *orig_filename, const char *outFileName,
                   const char *outFilePostfix, int mult, enum undo_type type);
 static void dogenerate(const char *filename, const char *outFileName,
                   const char *outFilePostfix,
                   int mult, int idx, enum undo_type type,
-                  hammer_tid_t ts1, hammer_tid_t ts2);
-static hammer_tid_t find_recent(const char *filename);
-static hammer_tid_t output_history(const char *filename, int fd, FILE *fp,
-                  hammer_tid_t **tid_ary, int *tid_num);
+                  struct hammer_ioc_hist_entry ts1,
+                  struct hammer_ioc_hist_entry ts2,
+                  int force);
+static struct hammer_ioc_hist_entry
+           find_recent(const char *filename);
+static struct hammer_ioc_hist_entry
+           output_history(const char *filename, int fd, FILE *fp,
+                  struct undo_hist_entry_rb_tree *tse_tree);
+static struct hammer_ioc_hist_entry
+           collect_history(int fd, int *error,
+                  struct undo_hist_entry_rb_tree *tse_tree);
 static hammer_tid_t parse_delta_time(const char *timeStr);
 static void runcmd(int fd, const char *cmd, ...);
-static char *timestamp(hammer_tid_t tid);
+static char *timestamp(hammer_ioc_hist_entry_t hen);
 static void usage(void);
 
 static int VerboseOpt;
 
+RB_GENERATE2(undo_hist_entry_rb_tree, undo_hist_entry, rbnode,
+       undo_hist_entry_compare, hammer_tid_t, tse.tid);
+
+
 int
 main(int ac, char **av)
 {
@@ -75,15 +102,18 @@ main(int ac, char **av)
        const char *outFilePostfix = NULL;
        enum { CMD_DUMP, CMD_ITERATEALL } cmd;
        enum undo_type type;
-       hammer_tid_t ts1 = 0;
-       hammer_tid_t ts2 = 0;
+       struct hammer_ioc_hist_entry ts1;
+       struct hammer_ioc_hist_entry ts2;
        int c;
        int mult;
 
+       bzero(&ts1, sizeof(ts1));
+       bzero(&ts2, sizeof(ts2));
+
        cmd = CMD_DUMP;
        type = TYPE_FILE;
 
-       while ((c = getopt(ac, av, "dDhiuvo:t:")) != -1) {
+       while ((c = getopt(ac, av, "adDiuvo:t:")) != -1) {
                switch(c) {
                case 'd':
                        if (type != TYPE_FILE)
@@ -100,7 +130,7 @@ main(int ac, char **av)
                                usage();
                        type = TYPE_HISTORY;
                        break;
-               case 'h':
+               case 'a':
                        cmd = CMD_ITERATEALL;
                        break;
                case 'u':
@@ -113,12 +143,12 @@ main(int ac, char **av)
                        outFileName = optarg;
                        break;
                case 't':
-                       if (ts1 && ts2)
+                       if (ts1.tid && ts2.tid)
                                usage();
-                       else if (ts1 == 0)
-                               ts1 = parse_delta_time(optarg);
+                       else if (ts1.tid == 0)
+                               ts1.tid = parse_delta_time(optarg);
                        else
-                               ts2 = parse_delta_time(optarg);
+                               ts2.tid = parse_delta_time(optarg);
                        break;
                default:
                        usage();
@@ -171,8 +201,7 @@ main(int ac, char **av)
                switch(cmd) {
                case CMD_DUMP:
                        dogenerate(*av, outFileName, outFilePostfix,
-                                  mult, -1, type,
-                                  ts1, ts2);
+                                  mult, -1, type, ts1, ts2, 1);
                        break;
                case CMD_ITERATEALL:
                        doiterate(*av, outFileName, outFilePostfix,
@@ -193,45 +222,54 @@ void
 doiterate(const char *orig_filename, const char *outFileName,
           const char *outFilePostfix, int mult, enum undo_type type)
 {
-       hammer_tid_t *tid_ary = NULL;
-       hammer_tid_t ts1;
+       struct undo_hist_entry_rb_tree tse_tree;
+       struct undo_hist_entry *tse1;
+       struct undo_hist_entry *tse2;
+       struct hammer_ioc_hist_entry tid_max;
+       struct hammer_ioc_hist_entry ts1;
        const char *use_filename;
        char *path = NULL;
-       int tid_num = 0;
        int i;
        int fd;
 
+       RB_INIT(&tse_tree);
+
+       tid_max.tid = HAMMER_MAX_TID;
+       tid_max.time32 = 0;
+
        use_filename = orig_filename;
        if ((fd = open(orig_filename, O_RDONLY)) < 0) {
                ts1 = find_recent(orig_filename);
-               if (ts1) {
-                       asprintf(&path, "%s@@0x%016llx", orig_filename, ts1);
+               if (ts1.tid) {
+                       asprintf(&path, "%s@@0x%016llx",
+                                orig_filename, ts1.tid);
                        use_filename = path;
                }
        }
 
        if ((fd = open(use_filename, O_RDONLY)) >= 0) {
                printf("%s: ITERATE ENTIRE HISTORY\n", orig_filename);
-               output_history(NULL, fd, NULL, &tid_ary, &tid_num);
+               output_history(NULL, fd, NULL, &tse_tree);
                close(fd);
 
-               for (i = 0; i < tid_num; ++i) {
-                       if (i && tid_ary[i] == tid_ary[i-1])
-                               continue;
-
-                       if (i == tid_num - 1) {
-                               dogenerate(orig_filename,
-                                          outFileName, outFilePostfix,
-                                          mult, i, type,
-                                          tid_ary[i], HAMMER_MAX_TID);
-                       } else {
+               tse1 = NULL;
+               i = 0;
+               RB_FOREACH(tse2, undo_hist_entry_rb_tree, &tse_tree) {
+                       if (tse1) {
                                dogenerate(orig_filename,
                                           outFileName, outFilePostfix,
                                           mult, i, type,
-                                          tid_ary[i], tid_ary[i+1]);
+                                          tse1->tse, tse2->tse, 0);
                        }
+                       tse1 = tse2;
+                       ++i;
+               }
+               if (!RB_EMPTY(&tse_tree)) {
+                       dogenerate(orig_filename,
+                                  outFileName, outFilePostfix,
+                                  mult, i, type,
+                                  tse1->tse, tid_max, 0);
                }
-
        } else {
                printf("%s: ITERATE ENTIRE HISTORY: %s\n",
                        orig_filename, strerror(errno));
@@ -249,7 +287,9 @@ void
 dogenerate(const char *filename, const char *outFileName,
           const char *outFilePostfix,
           int mult, int idx, enum undo_type type,
-          hammer_tid_t ts1, hammer_tid_t ts2)
+          struct hammer_ioc_hist_entry ts1,
+          struct hammer_ioc_hist_entry ts2,
+          int force)
 {
        struct stat st;
        const char *elm;
@@ -267,34 +307,26 @@ dogenerate(const char *filename, const char *outFileName,
         * Open the input file.  If ts1 is 0 try to locate the most recent
         * version of the file prior to the current version.
         */
-       if (ts1 == 0)
+       if (ts1.tid == 0)
                ts1 = find_recent(filename);
-       asprintf(&ipath1, "%s@@0x%016llx", filename, ts1);
-       if (lstat(ipath1, &st) < 0) {
-               if (VerboseOpt) {
-                       fprintf(stderr, "Cannot locate src/historical "
-                                       "idx=%d %s\n",
-                               idx, ipath1);
-               }
-               goto done;
-       }
+       if (ts1.tid == 0)
+               asprintf(&ipath1, "%s", filename);
+       else
+               asprintf(&ipath1, "%s@@0x%016llx", filename, ts1.tid);
 
-       if (ts2 == 0) {
+       if (ts2.tid == 0)
                asprintf(&ipath2, "%s", filename);
-       } else {
-               asprintf(&ipath2, "%s@@0x%015llx", filename, ts2);
-       }
-       if (lstat(ipath2, &st) < 0) {
-               if (VerboseOpt) {
-                       if (ts2) {
-                               fprintf(stderr, "Cannot locate tgt/historical "
-                                               "idx=%d %s\n",
-                                       idx, ipath2);
-                       } else if (VerboseOpt > 1) {
-                               fprintf(stderr, "Cannot locate %s\n", filename);
-                       }
+       else
+               asprintf(&ipath2, "%s@@0x%016llx", filename, ts2.tid);
+
+       if (lstat(ipath1, &st) < 0 && lstat(ipath2, &st) < 0) {
+               if (force == 0 || VerboseOpt) {
+                       fprintf(stderr, "Unable to access either %s or %s\n",
+                               ipath1, ipath2);
                }
-               ipath2 = strdup("/dev/null");
+               free(ipath1);
+               free(ipath2);
+               goto done;
        }
 
        /*
@@ -341,14 +373,14 @@ dogenerate(const char *filename, const char *outFileName,
                if (mult && type == TYPE_FILE) {
                        if (idx >= 0) {
                                printf("\n>>> %s %04d 0x%016llx %s\n\n",
-                                      filename, idx, ts1, timestamp(ts1));
+                                      filename, idx, ts1.tid, timestamp(&ts1));
                        } else {
                                printf("\n>>> %s ---- 0x%016llx %s\n\n",
-                                      filename, ts1, timestamp(ts1));
+                                      filename, ts1.tid, timestamp(&ts1));
                        }
                } else if (idx >= 0 && type == TYPE_FILE) {
                        printf("\n>>> %s %04d 0x%016llx %s\n\n", 
-                              filename, idx, ts1, timestamp(ts1));
+                              filename, idx, ts1.tid, timestamp(&ts1));
                }
                fp = stdout;
        }
@@ -362,18 +394,19 @@ dogenerate(const char *filename, const char *outFileName,
                }
                break;
        case TYPE_DIFF:
-               printf("diff -u %s %s\n", ipath1, ipath2);
+               printf("diff -N -r -u %s %s (to %s)\n",
+                      ipath1, ipath2, timestamp(&ts2));
                fflush(stdout);
-               runcmd(fileno(fp), "/usr/bin/diff", "diff", "-u", ipath1, ipath2, NULL);
+               runcmd(fileno(fp), "/usr/bin/diff", "diff", "-N", "-r", "-u", ipath1, ipath2, NULL);
                break;
        case TYPE_RDIFF:
-               printf("diff -u %s %s\n", ipath2, ipath1);
+               printf("diff -N -r -u %s %s\n", ipath2, ipath1);
                fflush(stdout);
-               runcmd(fileno(fp), "/usr/bin/diff", "diff", "-u", ipath2, ipath1, NULL);
+               runcmd(fileno(fp), "/usr/bin/diff", "diff", "-N", "-r", "-u", ipath2, ipath1, NULL);
                break;
        case TYPE_HISTORY:
                if ((fi = fopen(ipath1, "r")) != NULL) {
-                       output_history(filename, fileno(fi), fp, NULL, NULL);
+                       output_history(filename, fileno(fi), fp, NULL);
                        fclose(fi);
                }
                break;
@@ -390,21 +423,23 @@ done:
  *
  * XXX if file cannot be found
  */
-static hammer_tid_t
+static
+struct hammer_ioc_hist_entry
 find_recent(const char *filename)
 {
-       hammer_tid_t *tid_ary = NULL;
-       int tid_num = 0;
-       hammer_tid_t tid;
+       struct undo_hist_entry_rb_tree tse_tree;
+       struct undo_hist_entry *tse;
+       struct hammer_ioc_hist_entry hen;
        char *dirname;
        char *path;
        int fd;
-       int i;
+
+       RB_INIT(&tse_tree);
 
        if ((fd = open(filename, O_RDONLY)) >= 0) {
-               tid = output_history(NULL, fd, NULL, NULL, NULL);
+               hen = output_history(NULL, fd, NULL, NULL);
                close(fd);
-               return(tid);
+               return(hen);
        }
 
        /*
@@ -418,59 +453,107 @@ find_recent(const char *filename)
                dirname = strdup(".");
        }
 
-       tid = 0;
+       hen.tid = 0;
+       hen.time32 = 0;
        if ((fd = open(dirname, O_RDONLY)) >= 0) {
-               output_history(NULL, fd, NULL, &tid_ary, &tid_num);
+               output_history(NULL, fd, NULL, &tse_tree);
                close(fd);
                free(dirname);
 
-               for (i = tid_num - 1; i >= 0; --i) {
-                       asprintf(&path, "%s@@0x%016llx", filename, tid_ary[i]);
+               tse = RB_MAX(undo_hist_entry_rb_tree, &tse_tree);
+               while (tse) {
+                       asprintf(&path, "%s@@0x%016llx",
+                                filename, tse->tse.tid);
                        if ((fd = open(path, O_RDONLY)) >= 0) {
-                               tid = output_history(NULL, fd, NULL, NULL, NULL);
+                               hen = output_history(NULL, fd, NULL, NULL);
                                close(fd);
                                free(path);
                                break;
                        }
                        free(path);
+                       tse = RB_PREV(undo_hist_entry_rb_tree, &tse_tree, tse);
                }
        }
-       return(tid);
+       while ((tse = RB_ROOT(&tse_tree)) != NULL) {
+               RB_REMOVE(undo_hist_entry_rb_tree, &tse_tree, tse);
+               free(tse);
+       }
+       return(hen);
 }
 
-/*
- * Collect all the transaction ids representing changes made to the
- * file, sort, and output (weeding out duplicates).  If fp is NULL
- * we do not output anything and simply return the most recent TID we
- * can find.
- */
-static int
-tid_cmp(const void *arg1, const void *arg2)
+static
+struct hammer_ioc_hist_entry
+output_history(const char *filename, int fd, FILE *fp,
+              struct undo_hist_entry_rb_tree *tse_tree)
 {
-       const hammer_tid_t *tid1 = arg1;
-       const hammer_tid_t *tid2 = arg2;
+       struct hammer_ioc_hist_entry hen;
+       struct undo_hist_entry *tse;
+       char datestr[64];
+       struct tm *tp;
+       time_t t;
+       int istmp;
+       int error;
 
-       if (*tid1 < *tid2)
-               return(-1);
-       if (*tid1 > *tid2)
-               return(1);
-       return(0);
+       /*
+        * Setup
+        */
+       if (tse_tree == NULL) {
+               tse_tree = malloc(sizeof(*tse_tree));
+               RB_INIT(tse_tree);
+               istmp = 1;
+       } else {
+               istmp = 0;
+       }
+
+       /*
+        * Collect a unique set of transaction ids
+        */
+       hen = collect_history(fd, &error, tse_tree);
+
+       if (error && filename)
+               printf("%s: %s\n", filename, strerror(errno));
+       else if (filename)
+               printf("%s:\n", filename);
+
+       /*
+        * If fp != NULL dump the history to stdout.
+        */
+       if (fp) {
+               RB_FOREACH(tse, undo_hist_entry_rb_tree, tse_tree) {
+                       t = (time_t)tse->tse.time32;
+                       tp = localtime(&t);
+                       strftime(datestr, sizeof(datestr),
+                                "%d-%b-%Y %H:%M:%S", tp);
+                       printf("\t0x%016llx %s\n", tse->tse.tid, datestr);
+               }
+       }
+
+       /*
+        * Caller did not want a tree returned
+        */
+       if (istmp) {
+               while ((tse = RB_ROOT(tse_tree)) != NULL) {
+                       RB_REMOVE(undo_hist_entry_rb_tree, tse_tree, tse);
+                       free(tse);
+               }
+               free(tse_tree);
+       }
+       return(hen);
 }
 
-static hammer_tid_t
-output_history(const char *filename, int fd, FILE *fp,
-               hammer_tid_t **tid_aryp, int *tid_nump)
+static
+struct hammer_ioc_hist_entry
+collect_history(int fd, int *errorp, struct undo_hist_entry_rb_tree *tse_tree)
 {
+       struct hammer_ioc_hist_entry hen;
        struct hammer_ioc_history hist;
-       char datestr[64];
-       struct tm *tp;
-       time_t t;
-       int tid_max = 32;
-       int tid_num = 0;
+       struct undo_hist_entry *tse;
+       int istmp;
        int i;
-       hammer_tid_t *tid_ary = malloc(tid_max * sizeof(*tid_ary));
-       hammer_tid_t tid;
 
+       /*
+        * Setup
+        */
        bzero(&hist, sizeof(hist));
        hist.beg_tid = HAMMER_MIN_TID;
        hist.end_tid = HAMMER_MAX_TID;
@@ -478,22 +561,33 @@ output_history(const char *filename, int fd, FILE *fp,
        hist.key = 0;
        hist.nxt_key = HAMMER_MAX_KEY;
 
-       tid = 0;
+       hen.tid = 0;
+       hen.time32 = 0;
+
+       *errorp = 0;
+
+       if (tse_tree == NULL) {
+               tse_tree = malloc(sizeof(*tse_tree));
+               RB_INIT(tse_tree);
+               istmp = 1;
+       } else {
+               istmp = 0;
+       }
 
+       /*
+        * Collect a unique set of transaction ids
+        */
        if (ioctl(fd, HAMMERIOC_GETHISTORY, &hist) < 0) {
-               if (filename)
-                       printf("%s: %s\n", filename, strerror(errno));
+               *errorp = errno;
                goto done;
        }
-       if (filename)
-               printf("%s: objid=0x%016llx\n", filename, hist.obj_id);
        for (;;) {
-               if (tid_num + hist.count >= tid_max) {
-                       tid_max = (tid_max * 3 / 2) + hist.count;
-                       tid_ary = realloc(tid_ary, tid_max * sizeof(*tid_ary));
-               }
                for (i = 0; i < hist.count; ++i) {
-                       tid_ary[tid_num++] = hist.tid_ary[i];
+                       tse = malloc(sizeof(*tse));
+                       tse->tse = hist.hist_ary[i];
+                       if (RB_INSERT(undo_hist_entry_rb_tree, tse_tree, tse)) {
+                               free(tse);
+                       }
                }
                if (hist.head.flags & HAMMER_IOC_HISTORY_EOF)
                        break;
@@ -504,32 +598,32 @@ output_history(const char *filename, int fd, FILE *fp,
                if (hist.head.flags & HAMMER_IOC_HISTORY_NEXT_TID) 
                        hist.beg_tid = hist.nxt_tid;
                if (ioctl(fd, HAMMERIOC_GETHISTORY, &hist) < 0) {
-                       if (filename)
-                               printf("%s: %s\n", filename, strerror(errno));
+                       *errorp = errno;
                        break;
                }
        }
-       qsort(tid_ary, tid_num, sizeof(*tid_ary), tid_cmp);
-       if (tid_num == 0)
-               goto done;
-       for (i = 0; fp && i < tid_num; ++i) {
-               if (i && tid_ary[i] == tid_ary[i-1])
-                       continue;
-               t = (time_t)(tid_ary[i] / 1000000000);
-               tp = localtime(&t);
-               strftime(datestr, sizeof(datestr), "%d-%m-%Y %H:%M:%S", tp);
-               printf("\t0x%016llx %s\n", tid_ary[i], datestr);
-       }
-       if (tid_num > 1)
-               tid = tid_ary[tid_num-2];
+
+       /*
+        * Locate next-to-last entry
+        */
+       tse = RB_MAX(undo_hist_entry_rb_tree, tse_tree);
+       if (tse)
+               tse = RB_PREV(undo_hist_entry_rb_tree, tse_tree, tse);
+       if (tse)
+               hen = tse->tse;
+
+       /*
+        * Cleanup
+        */
 done:
-       if (tid_aryp) {
-               *tid_aryp = tid_ary;
-               *tid_nump = tid_num;
-       } else {
-               free(tid_ary);
+       if (istmp) {
+               while ((tse = RB_ROOT(tse_tree)) != NULL) {
+                       RB_REMOVE(undo_hist_entry_rb_tree, tse_tree, tse);
+                       free(tse);
+               }
+               free(tse_tree);
        }
-       return(tid);
+       return(hen);
 }
 
 static
@@ -537,31 +631,8 @@ hammer_tid_t
 parse_delta_time(const char *timeStr)
 {
        hammer_tid_t tid;
-       char *ptr;
-
-       if (timeStr[0] == '0' && (timeStr[1] == 'x' || timeStr[1] == 'X')) {
-               tid = strtoull(timeStr, NULL, 0);
-       } else {
-               tid = strtol(timeStr, &ptr, 0);
 
-               switch(*ptr) {
-               case 'd':
-                       tid *= 24;
-                       /* fall through */
-               case 'h':
-                       tid *= 60;
-                       /* fall through */
-               case 'm':
-                       tid *= 60;
-                       /* fall through */
-               case 's':
-                       break;
-               default:
-                       usage();
-               }
-               tid = time(NULL) - tid;
-               tid *= 1000000000;
-       }
+       tid = strtoull(timeStr, NULL, 0);
        return(tid);
 }
 
@@ -607,31 +678,43 @@ runcmd(int fd, const char *cmd, ...)
  * Convert tid to timestamp.
  */
 static char *
-timestamp(hammer_tid_t tid)
+timestamp(hammer_ioc_hist_entry_t hen)
 {
        static char timebuf[64];
-       time_t t = (time_t)(tid / 1000000000);
+       time_t t = (time_t)hen->time32;
        struct tm *tp;
 
        tp = localtime(&t);
-       strftime(timebuf, sizeof(timebuf), "%d-%m-%Y %H:%M:%S", tp);
+       strftime(timebuf, sizeof(timebuf), "%d-%b-%Y %H:%M:%S", tp);
        return(timebuf);
 }
 
+static
+int
+undo_hist_entry_compare(struct undo_hist_entry *he1,
+                       struct undo_hist_entry *he2)
+{
+       if (he1->tse.tid < he2->tse.tid)
+               return(-1);
+       if (he1->tse.tid > he2->tse.tid)
+               return(1);
+       return(0);
+}
+
 static void
 usage(void)
 {
-       fprintf(stderr, "undo [-dDhiuv] [-t n{s,m,h,d}] [-t n...] "
-                       "file1....fileN\n");
-       fprintf(stderr, "    -d       Forward diff\n"
+       fprintf(stderr, "undo [-adDiuv] [-o outfile] "
+                       "[-t transaction-id] [-t transaction-id] path...\n"
+                       "    -a       Iterate all historical segments\n"
+                       "    -d       Forward diff\n"
                        "    -D       Reverse diff\n"
                        "    -i       Dump history transaction ids\n"
-                       "    -h       Iterate all historical segments\n"
                        "    -u       Generate .undo files\n"
                        "    -v       Verbose\n"
-                       "    -t spec  Retrieve as of n secs,mins,etc ago\n"
-                       "             (a second one to diff two versions)\n"
-                       "             (a 0x TID may also be specified)\n");
+                       "    -o file  Output to the specified file\n"
+                       "    -t TID   Retrieve as of transaction-id, TID\n"
+                       "             (a second `-t TID' to diff two versions)\n");
        exit(1);
 }