X-Git-Url: https://git.ozlabs.org/?p=ccan;a=blobdiff_plain;f=ccan%2Ftdb%2Ftools%2Freplay_trace.c;h=db5a07be1cf7c7dd4b3cd7ae18a5770ca1d5ca63;hp=fc0cc15bb8400395dfb6febcac22644096106d2d;hb=d9961fc330a057b0f5359b3d97a5317aee2d6efa;hpb=800715227e588385aafd80e6807b2069895cfac2 diff --git a/ccan/tdb/tools/replay_trace.c b/ccan/tdb/tools/replay_trace.c index fc0cc15b..db5a07be 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,12 @@ 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_opnum+1, filename[dep->satisfies_file], + dep->satisfies_opnum+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 +516,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]); } } @@ -1045,34 +1026,78 @@ static bool satisfies(const TDB_DATA *data, const TDB_DATA *need) return key_eq(*data, *need); } +static void move_to_front(struct key_user res[], unsigned int elem) +{ + if (elem != 0) { + struct key_user tmp = res[elem]; + memmove(res + 1, res, elem*sizeof(res[0])); + res[0] = tmp; + } +} + +static void restore_to_pos(struct key_user res[], unsigned int elem) +{ + if (elem != 0) { + struct key_user tmp = res[0]; + memmove(res, res + 1, elem*sizeof(res[0])); + res[elem] = tmp; + } +} + static bool sort_deps(char *filename[], struct op *op[], struct key_user res[], unsigned num, - const TDB_DATA *data) + const TDB_DATA *data, unsigned num_files) { - unsigned int i; + unsigned int i, files_done; + struct op *this_op; + bool done[num_files]; /* Nothing left? We're sorted. */ if (num == 0) return true; - for (i = 0; i < num; i++) { - struct op *this_op = &op[res[i].file][res[i].op_num]; + memset(done, 0, sizeof(done)); + /* Since ops within a trace file are ordered, we just need to figure + * out which file to try next. Since we don't take into account + * inter-key relationships (which exist by virtue of trace file order), + * we minimize the chance of harm by trying to keep in serial order. */ + for (files_done = 0, i = 0; i < num && files_done < num_files; i++) { + if (done[res[i].file]) + continue; + + this_op = &op[res[i].file][res[i].op_num]; /* Is what we have good enough for this op? */ if (satisfies(data, needs(this_op))) { - /* Try this one next. */ - struct key_user tmp = res[0]; - res[0] = res[i]; - res[i] = tmp; + move_to_front(res, i); if (sort_deps(filename, op, res+1, num-1, - gives(this_op, data))) + gives(this_op, data), num_files)) return true; + restore_to_pos(res, i); } + done[res[i].file] = true; + files_done++; } + /* No combination worked. */ return false; } +static void check_dep_sorting(struct key_user user[], unsigned num_users, + unsigned num_files) +{ +#if DEBUG_DEPS + unsigned int i; + unsigned minima[num_files]; + + memset(minima, 0, sizeof(minima)); + for (i = 0; i < num_users; i++) { + assert(minima[user[i].file] < user[i].op_num); + minima[user[i].file] = user[i].op_num; + } +#endif +} + /* All these ops have the same serial number. Which comes first? * * This can happen both because read ops or failed write ops don't @@ -1081,22 +1106,21 @@ static bool sort_deps(char *filename[], struct op *op[], * in which case we'll deadlock and report: fix manually in that case). */ static void figure_deps(char *filename[], struct op *op[], - struct key_user user[], unsigned start, unsigned end) + struct key_user user[], unsigned num_users, + unsigned num_files) { - unsigned int i; /* We assume database starts empty. */ const struct TDB_DATA *data = &tdb_null; - /* What do we have to start with? */ - for (i = 0; i < start; i++) - data = gives(&op[user[i].file][user[i].op_num], data); - - if (!sort_deps(filename, op, user + start, end - start, data)) - fail(filename[user[start].file], user[start].op_num+1, + if (!sort_deps(filename, op, user, num_users, data, num_files)) + fail(filename[user[0].file], user[0].op_num+1, "Could not resolve inter-dependencies"); + + check_dep_sorting(user, num_users, num_files); } -static void sort_ops(struct keyinfo hash[], char *filename[], struct op *op[]) +static void sort_ops(struct keyinfo hash[], char *filename[], struct op *op[], + unsigned int num) { unsigned int h; @@ -1104,36 +1128,32 @@ static void sort_ops(struct keyinfo hash[], char *filename[], struct op *op[]) int compare_serial(const void *_a, const void *_b) { const struct key_user *a = _a, *b = _b; + + /* First, maintain order within any trace file. */ + if (a->file == b->file) + return a->op_num - b->op_num; + + /* Otherwise, arrange by serial order. */ return op[a->file][a->op_num].serial - op[b->file][b->op_num].serial; } - /* Now sort into seqnum order. */ + /* Now sort into serial order. */ for (h = 0; h < total_keys * 2; h++) { - unsigned int i, same; struct key_user *user = hash[h].user; qsort(user, hash[h].num_users, sizeof(user[0]), compare_serial); - - /* Try to deal with same serial numbers. */ - for (i = 1, same = 0; i < hash[h].num_users; i++) { - if (op[user[i].file][user[i].op_num].serial - == op[user[i-1].file][user[i-1].op_num].serial) { - same++; - continue; - } - - if (same) { - figure_deps(filename, op, user, i-same-1, i); - same = 0; - } - } - if (same) - figure_deps(filename, op, user, i-same-1, i); + figure_deps(filename, op, user, hash[h].num_users, num); } } -static unsigned int dep_count; +static int destroy_depend(struct depend *dep) +{ + list_del(&dep->pre_list); + list_del(&dep->post_list); + return 0; +} + static void add_dependency(void *ctx, struct op *op[], char *filename[], @@ -1142,12 +1162,14 @@ 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. */ - if (needs_file == satisfies_file) + if (needs_file == satisfies_file) { + assert(satisfies_opnum < needs_opnum); return; + } #if DEBUG_DEPS printf("%s:%u: depends on %s:%u\n", @@ -1187,17 +1209,14 @@ 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); - - 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++; + 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); } #if TRAVERSALS_TAKE_TRANSACTION_LOCK @@ -1254,7 +1273,6 @@ 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 */ @@ -1297,6 +1315,57 @@ static void depend_on_previous(struct op *op[], } } +/* This is simple, but not complete. We don't take into account + * indirect dependencies. */ +static void optimize_dependencies(struct op *op[], unsigned int num_ops[], + unsigned int num) +{ + unsigned int i, j; + + /* There can only be one real dependency on each file */ + for (i = 0; i < num; i++) { + for (j = 1; j < num_ops[i]; j++) { + struct depend *dep, *next; + struct depend *prev[num]; + + memset(prev, 0, sizeof(prev)); + + list_for_each_safe(&op[i][j].pre, dep, next, pre_list) { + if (!prev[dep->satisfies_file]) { + prev[dep->satisfies_file] = dep; + continue; + } + if (prev[dep->satisfies_file]->satisfies_opnum + < dep->satisfies_opnum) { + talloc_free(prev[dep->satisfies_file]); + prev[dep->satisfies_file] = dep; + } else + talloc_free(dep); + } + } + } + + for (i = 0; i < num; i++) { + int deps[num]; + + for (j = 0; j < num; j++) + deps[j] = -1; + + for (j = 1; j < num_ops[i]; j++) { + struct depend *dep, *next; + + list_for_each_safe(&op[i][j].pre, dep, next, pre_list) { + if (deps[dep->satisfies_file] + >= (int)dep->satisfies_opnum) + talloc_free(dep); + else + deps[dep->satisfies_file] + = dep->satisfies_opnum; + } + } + } +} + static void derive_dependencies(char *filename[], struct op *op[], unsigned int num_ops[], unsigned int num) @@ -1307,8 +1376,8 @@ static void derive_dependencies(char *filename[], /* Create hash table for faster key lookup. */ hash = hash_ops(op, num_ops, num); - /* Now handle the hard cases: same serial number. */ - sort_ops(hash, filename, op); + /* Sort them by serial number. */ + sort_ops(hash, filename, op, num); /* Create dependencies back to the last change, rather than * creating false dependencies by naively making each one @@ -1338,11 +1407,12 @@ static void derive_dependencies(char *filename[], 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); #endif + + optimize_dependencies(op, num_ops, num); } int main(int argc, char *argv[])