From bf31f16d7937923167381552a5820cc8ed3317c3 Mon Sep 17 00:00:00 2001 From: Matthew Dillon Date: Wed, 25 Feb 2009 14:24:23 -0800 Subject: [PATCH] HAMMER Utilities: Use a Red-Black tree to track HAMMER TIDs, use diff -N Begin using a red-black tree to track the TIDs used to generate diff sets. Use diff -N to deal with pre-creation/post-creation undo diffs. Use diff -r. However, running undo -a -d on a directory is not yet meaningful because only the directory TIDs are used right now. --- usr.bin/undo/undo.c | 301 +++++++++++++++++++++++++++----------------- 1 file changed, 184 insertions(+), 117 deletions(-) diff --git a/usr.bin/undo/undo.c b/usr.bin/undo/undo.c index 4e55e52e9d..fe794977d6 100644 --- a/usr.bin/undo/undo.c +++ b/usr.bin/undo/undo.c @@ -40,6 +40,7 @@ #include #include #include +#include #include #include #include @@ -50,8 +51,23 @@ #include #include +/* + * 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, @@ -64,7 +80,10 @@ 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 hammer_ioc_hist_entry **hist_ary, int *tid_num); + 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_ioc_hist_entry_t hen); @@ -72,6 +91,10 @@ 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) { @@ -199,16 +222,18 @@ void doiterate(const char *orig_filename, const char *outFileName, const char *outFilePostfix, int mult, enum undo_type type) { - hammer_ioc_hist_entry_t tid_ary = NULL; + 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 j; int fd; + RB_INIT(&tse_tree); + tid_max.tid = HAMMER_MAX_TID; tid_max.time32 = 0; @@ -224,24 +249,26 @@ doiterate(const char *orig_filename, const char *outFileName, 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); + tse1 = NULL; i = 0; - for (j = 1; j < tid_num; ++j) { - if (tid_ary[i].tid == tid_ary[j].tid) - continue; - dogenerate(orig_filename, - outFileName, outFilePostfix, - mult, i, type, - tid_ary[i], tid_ary[j], 0); - i = j; + RB_FOREACH(tse2, undo_hist_entry_rb_tree, &tse_tree) { + if (tse1) { + dogenerate(orig_filename, + outFileName, outFilePostfix, + mult, i, type, + tse1->tse, tse2->tse, 0); + } + tse1 = tse2; + ++i; } - if (tid_num && tid_ary) { + if (!RB_EMPTY(&tse_tree)) { dogenerate(orig_filename, outFileName, outFilePostfix, mult, i, type, - tid_ary[tid_num - 1], tid_max, 0); + tse1->tse, tid_max, 0); } } else { printf("%s: ITERATE ENTIRE HISTORY: %s\n", @@ -282,40 +309,24 @@ dogenerate(const char *filename, const char *outFileName, */ if (ts1.tid == 0) ts1 = find_recent(filename); - asprintf(&ipath1, "%s@@0x%016llx", filename, ts1.tid); - if (lstat(ipath1, &st) < 0) { - free(ipath1); + if (ts1.tid == 0) asprintf(&ipath1, "%s", filename); - if (force == 0 || lstat(ipath1, &st) < 0) { - fprintf(stderr, "Cannot locate src/historical " - "idx=%d %s@@0x%016llx,\n" - "the file may have been renamed " - "or deleted at this point.\n", - idx, filename, ts1.tid); - goto done; - } - fprintf(stderr, - "WARNING: %s was renamed at some point in the past,\n" - "attempting to continue with current version\n", - filename); - } + else + asprintf(&ipath1, "%s@@0x%016llx", filename, ts1.tid); - if (ts2.tid == 0) { + if (ts2.tid == 0) asprintf(&ipath2, "%s", filename); - } else { + else asprintf(&ipath2, "%s@@0x%016llx", filename, ts2.tid); - } - if (lstat(ipath2, &st) < 0) { - if (VerboseOpt) { - if (ts2.tid) { - fprintf(stderr, "Cannot locate tgt/historical " - "idx=%d %s\n", - idx, ipath2); - } else if (VerboseOpt > 1) { - fprintf(stderr, "Cannot locate %s\n", filename); - } + + 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; } /* @@ -383,19 +394,19 @@ dogenerate(const char *filename, const char *outFileName, } break; case TYPE_DIFF: - printf("diff -u %s %s (to %s)\n", + 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; @@ -416,16 +427,17 @@ static struct hammer_ioc_hist_entry find_recent(const char *filename) { - hammer_ioc_hist_entry_t tid_ary = NULL; - int tid_num = 0; + 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) { - hen = output_history(NULL, fd, NULL, NULL, NULL); + hen = output_history(NULL, fd, NULL, NULL); close(fd); return(hen); } @@ -444,58 +456,104 @@ find_recent(const char *filename) 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].tid); + 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) { - hen = 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); } } + 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 struct hammer_ioc_hist_entry *tid1 = arg1; - const struct hammer_ioc_hist_entry *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->tid < tid2->tid) - return(-1); - if (tid1->tid > tid2->tid) - 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 struct hammer_ioc_hist_entry -output_history(const char *filename, int fd, FILE *fp, - struct hammer_ioc_hist_entry **hist_aryp, int *tid_nump) +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_ioc_hist_entry_t hist_ary = malloc(tid_max * sizeof(*hist_ary)); + /* + * Setup + */ bzero(&hist, sizeof(hist)); hist.beg_tid = HAMMER_MIN_TID; hist.end_tid = HAMMER_MAX_TID; @@ -506,20 +564,30 @@ output_history(const char *filename, int fd, FILE *fp, 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; - hist_ary = realloc(hist_ary, tid_max * sizeof(*hist_ary)); - } for (i = 0; i < hist.count; ++i) { - hist_ary[tid_num++] = hist.hist_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; @@ -530,43 +598,30 @@ 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(hist_ary, tid_num, sizeof(*hist_ary), tid_cmp); - if (tid_num == 0) - goto done; /* - * If fp != NULL dump the history to stdout. + * Locate next-to-last entry */ - for (i = 0; fp && i < tid_num; ++i) { - if (i && hist_ary[i].tid == hist_ary[i-1].tid) - continue; - t = (time_t)hist_ary[i].time32; - tp = localtime(&t); - strftime(datestr, sizeof(datestr), "%d-%b-%Y %H:%M:%S", tp); - printf("\t0x%016llx %s\n", hist_ary[i].tid, datestr); - } + 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; /* - * Locate the next-to-last entry, ignoring any duplicates. + * Cleanup */ - if (tid_num > 1) { - for (i = tid_num - 2; i > 0; --i) { - if (hist_ary[i].tid != hist_ary[tid_num-1].tid) - break; - } - hen = hist_ary[i]; - } done: - if (hist_aryp) { - *hist_aryp = hist_ary; - *tid_nump = tid_num; - } else { - free(hist_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(hen); } @@ -634,11 +689,23 @@ timestamp(hammer_ioc_hist_entry_t hen) 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 [-adDiuv] [-o outfile] " - "[-t transaction-id] [-t transaction-id] file...\n" + "[-t transaction-id] [-t transaction-id] path...\n" " -a Iterate all historical segments\n" " -d Forward diff\n" " -D Reverse diff\n" -- 2.41.0