X-Git-Url: https://git.ozlabs.org/?p=ccan;a=blobdiff_plain;f=ccan%2Ftdb%2Ftools%2Freplay_trace.c;h=c12011acaaa9847cae2f7641eaffa938d6abffac;hp=f48c7d1f3474e56f0723606ef3a161cec577f813;hb=4f148f842e1b61fe637200ab7bbc6d1b8f4338d1;hpb=555c01c93fdd67f86f5f943ac2d4eae18eb3894c diff --git a/ccan/tdb/tools/replay_trace.c b/ccan/tdb/tools/replay_trace.c index f48c7d1f..c12011ac 100644 --- a/ccan/tdb/tools/replay_trace.c +++ b/ccan/tdb/tools/replay_trace.c @@ -448,30 +448,14 @@ find_keyword (register const char *str, register unsigned int len); struct depend { /* We can have more than one */ - struct list_node list; - unsigned int file; - unsigned int op; -}; - -struct depend_xmit { - unsigned int dst_op; - unsigned int src_file, src_op; + struct list_node pre_list; + struct list_node post_list; + unsigned int needs_file; + unsigned int needs_opnum; + unsigned int satisfies_file; + unsigned int satisfies_opnum; }; -static void remove_matching_dep(struct list_head *deps, - unsigned int file, unsigned int op) -{ - struct depend *dep; - - list_for_each(deps, dep, list) { - if (dep->file == file && dep->op == op) { - list_del(&dep->list); - return; - } - } - errx(1, "Failed to find depend on file %u line %u\n", file, op+1); -} - static void check_deps(const char *filename, struct op op[], unsigned int num) { #ifdef DEBUG_DEPS @@ -489,16 +473,18 @@ static void dump_pre(char *filename[], unsigned int file, struct depend *dep; printf("%s:%u still waiting for:\n", filename[file], i+1); - list_for_each(&op[i].pre, dep, list) - printf(" %s:%u\n", filename[dep->file], dep->op+1); + list_for_each(&op[i].pre, dep, pre_list) + printf(" %s:%u\n", + filename[dep->satisfies_file], dep->satisfies_opnum+1); check_deps(filename[file], op, i); } +/* We simply read/write pointers, since we all are children. */ static void do_pre(char *filename[], unsigned int file, int pre_fd, struct op op[], unsigned int i) { while (!list_empty(&op[i].pre)) { - struct depend_xmit dep; + struct depend *dep; #if DEBUG_DEPS printf("%s:%u:waiting for pre\n", filename[file], i+1); @@ -516,12 +502,11 @@ static void do_pre(char *filename[], unsigned int file, int pre_fd, #if DEBUG_DEPS printf("%s:%u:got pre %u from %s:%u\n", filename[file], i+1, - dep.dst_op+1, filename[dep.src_file], dep.src_op+1); + dep->needs_op, dep->satisfies_file, dep->satisfies_op+1); fflush(stdout); #endif /* This could be any op, not just this one. */ - remove_matching_dep(&op[dep.dst_op].pre, - dep.src_file, dep.src_op); + talloc_free(dep); } } @@ -530,20 +515,15 @@ static void do_post(char *filename[], unsigned int file, { struct depend *dep; - list_for_each(&op[i].post, dep, list) { - struct depend_xmit dx; - - dx.src_file = file; - dx.src_op = i; - dx.dst_op = dep->op; + list_for_each(&op[i].post, dep, post_list) { #if DEBUG_DEPS printf("%s:%u:sending to file %s:%u\n", filename[file], i+1, - filename[dep->file], dep->op+1); + filename[dep->needs_file], dep->needs_opnum+1); #endif - if (write(pipes[dep->file].fd[1], &dx, sizeof(dx)) - != sizeof(dx)) + if (write(pipes[dep->needs_file].fd[1], &dep, sizeof(dep)) + != sizeof(dep)) err(1, "%s:%u failed to tell file %s", - filename[file], i+1, filename[dep->file]); + filename[file], i+1, filename[dep->needs_file]); } } @@ -1133,6 +1113,14 @@ static void sort_ops(struct keyinfo hash[], char *filename[], struct op *op[]) } } +static int destroy_depend(struct depend *dep) +{ + list_del(&dep->pre_list); + list_del(&dep->post_list); + return 0; +} + +static unsigned int dep_count; static void add_dependency(void *ctx, struct op *op[], char *filename[], @@ -1141,7 +1129,7 @@ static void add_dependency(void *ctx, unsigned int satisfies_file, unsigned int satisfies_opnum) { - struct depend *post, *pre; + struct depend *dep; unsigned int needs_start, sat_start; /* We don't depend on ourselves. */ @@ -1186,15 +1174,16 @@ static void add_dependency(void *ctx, } } - post = talloc(ctx, struct depend); - post->file = needs_file; - post->op = needs_opnum; - list_add(&op[satisfies_file][satisfies_opnum].post, &post->list); + dep = talloc(ctx, struct depend); + dep->needs_file = needs_file; + dep->needs_opnum = needs_opnum; + dep->satisfies_file = satisfies_file; + dep->satisfies_opnum = satisfies_opnum; + list_add(&op[satisfies_file][satisfies_opnum].post, &dep->post_list); + list_add(&op[needs_file][needs_opnum].pre, &dep->pre_list); + talloc_set_destructor(dep, destroy_depend); - pre = talloc(ctx, struct depend); - pre->file = satisfies_file; - pre->op = satisfies_opnum; - list_add(&op[needs_file][needs_opnum].pre, &pre->list); + dep_count++; } #if TRAVERSALS_TAKE_TRANSACTION_LOCK @@ -1251,30 +1240,91 @@ static void make_traverse_depends(char *filename[], dep[i-1].file, dep[i-1].op->trav->end); } talloc_free(dep); + printf("Dep count after traverses: %u\n", dep_count); } #endif /* TRAVERSALS_TAKE_TRANSACTION_LOCK */ +static bool changes_db(const struct op *op) +{ + return gives(op, NULL) != NULL; +} + +static void depend_on_previous(struct op *op[], + char *filename[], + unsigned int num, + struct key_user user[], + unsigned int i, + int prev) +{ + bool deps[num]; + int j; + + if (i == 0) + return; + + if (prev == i - 1) { + /* Just depend on previous. */ + add_dependency(NULL, op, filename, + user[i].file, user[i].op_num, + user[prev].file, user[prev].op_num); + return; + } + + /* We have to wait for the readers. Find last one in *each* file. */ + memset(deps, 0, sizeof(deps)); + deps[user[i].file] = true; + for (j = i - 1; j > prev; j--) { + if (!deps[user[j].file]) { + add_dependency(NULL, op, filename, + user[i].file, user[i].op_num, + user[j].file, user[j].op_num); + deps[user[j].file] = true; + } + } +} + static void derive_dependencies(char *filename[], struct op *op[], unsigned int num_ops[], unsigned int num) { struct keyinfo *hash; - unsigned int i, j; + unsigned int h, i; /* Create hash table for faster key lookup. */ hash = hash_ops(op, num_ops, num); - /* We make the naive assumption that two ops on the same key - * have to be ordered; it's overkill. */ - for (i = 0; i < total_keys * 2; i++) { - for (j = 1; j < hash[i].num_users; j++) { - add_dependency(hash, op, filename, - hash[i].user[j].file, - hash[i].user[j].op_num, - hash[i].user[j-1].file, - hash[i].user[j-1].op_num); + /* Now handle the hard cases: same serial number. */ + sort_ops(hash, filename, op); + + /* Create dependencies back to the last change, rather than + * creating false dependencies by naively making each one + * depend on the previous. This has two purposes: it makes + * later optimization simpler, and it also avoids deadlock with + * same sequence number ops inside traversals (if one + * traversal doesn't write anything, two ops can have the same + * sequence number yet we can create a traversal dependency + * the other way). */ + for (h = 0; h < total_keys * 2; h++) { + int prev = -1; + + if (hash[h].num_users < 2) + continue; + + for (i = 0; i < hash[h].num_users; i++) { + if (changes_db(&op[hash[h].user[i].file] + [hash[h].user[i].op_num])) { + depend_on_previous(op, filename, num, + hash[h].user, i, prev); + prev = i; + } else if (prev >= 0) + add_dependency(hash, op, filename, + hash[h].user[i].file, + hash[h].user[i].op_num, + hash[h].user[prev].file, + hash[h].user[prev].op_num); } } + printf("Dep count after deriving: %u\n", dep_count); #if TRAVERSALS_TAKE_TRANSACTION_LOCK make_traverse_depends(filename, op, num_ops, num);