From 4f148f842e1b61fe637200ab7bbc6d1b8f4338d1 Mon Sep 17 00:00:00 2001 From: Rusty Russell Date: Mon, 13 Jul 2009 11:18:05 +0930 Subject: [PATCH 1/1] Simplify dependencies by passing pointers over the pipe: avoid O(n^2) behaviour for searching. Also, using a single structure makes talloc_free convenient for when we do optimization. --- ccan/tdb/tools/replay_trace.c | 82 +++++++++++++++-------------------- 1 file changed, 34 insertions(+), 48 deletions(-) diff --git a/ccan/tdb/tools/replay_trace.c b/ccan/tdb/tools/replay_trace.c index fc0cc15b..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,13 @@ 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[], @@ -1142,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. */ @@ -1187,15 +1174,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 = 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); dep_count++; } -- 2.39.2