X-Git-Url: http://git.ozlabs.org/?p=ccan;a=blobdiff_plain;f=ccan%2Ftdb%2Ftools%2Freplay_trace.c;h=0e799a686158fef4bc8c6a8229285d1387cec95a;hp=2099dafbf1f64d38ef986b661aaae718abd29a2c;hb=100444225380d3f5ca29424ea54703d308c7c651;hpb=7ff5fdae5859fc5e7bbe2fa1aad3b8eee73b4891 diff --git a/ccan/tdb/tools/replay_trace.c b/ccan/tdb/tools/replay_trace.c index 2099dafb..0e799a68 100644 --- a/ccan/tdb/tools/replay_trace.c +++ b/ccan/tdb/tools/replay_trace.c @@ -15,13 +15,20 @@ #include #include #include +#include #define STRINGIFY2(x) #x #define STRINGIFY(x) STRINGIFY2(x) +static bool quiet = false; + /* Avoid mod by zero */ static unsigned int total_keys = 1; +/* All the wipe_all ops. */ +static struct op_desc *wipe_alls = NULL; +static unsigned int num_wipe_alls = 0; + /* #define DEBUG_DEPS 1 */ /* Traversals block transactions in the current implementation. */ @@ -31,6 +38,7 @@ struct pipe { int fd[2]; }; static struct pipe *pipes; +static int backoff_fd = -1; static void __attribute__((noreturn)) fail(const char *filename, unsigned int line, @@ -114,15 +122,18 @@ enum op_type { OP_TDB_WIPE_ALL, OP_TDB_TRANSACTION_START, OP_TDB_TRANSACTION_CANCEL, + OP_TDB_TRANSACTION_PREPARE_COMMIT, OP_TDB_TRANSACTION_COMMIT, OP_TDB_TRAVERSE_READ_START, OP_TDB_TRAVERSE_START, OP_TDB_TRAVERSE_END, OP_TDB_TRAVERSE, + OP_TDB_TRAVERSE_END_EARLY, OP_TDB_FIRSTKEY, OP_TDB_NEXTKEY, OP_TDB_FETCH, OP_TDB_DELETE, + OP_TDB_REPACK, }; struct op { @@ -204,98 +215,100 @@ static void add_op(const char *filename, struct op **op, unsigned int i, new->group_start = 0; } -static void op_add_nothing(const char *filename, - struct op op[], unsigned int op_num, char *words[]) +static void op_add_nothing(char *filename[], struct op op[], + unsigned file, unsigned op_num, char *words[]) { if (words[2]) - fail(filename, op_num+1, "Expected no arguments"); + fail(filename[file], op_num+1, "Expected no arguments"); op[op_num].key = tdb_null; } -static void op_add_key(const char *filename, - struct op op[], unsigned int op_num, char *words[]) +static void op_add_key(char *filename[], struct op op[], + unsigned file, unsigned op_num, char *words[]) { if (words[2] == NULL || words[3]) - fail(filename, op_num+1, "Expected just a key"); + fail(filename[file], op_num+1, "Expected just a key"); - op[op_num].key = make_tdb_data(op, filename, op_num+1, words[2]); + op[op_num].key = make_tdb_data(op, filename[file], op_num+1, words[2]); total_keys++; } -static void op_add_key_ret(const char *filename, - struct op op[], unsigned int op_num, char *words[]) +static void op_add_key_ret(char *filename[], struct op op[], + unsigned file, unsigned op_num, char *words[]) { if (!words[2] || !words[3] || !words[4] || words[5] || !streq(words[3], "=")) - fail(filename, op_num+1, "Expected = "); + fail(filename[file], op_num+1, "Expected = "); op[op_num].ret = atoi(words[4]); - op[op_num].key = make_tdb_data(op, filename, op_num+1, words[2]); + op[op_num].key = make_tdb_data(op, filename[file], op_num+1, words[2]); /* May only be a unique key if it fails */ if (op[op_num].ret != 0) total_keys++; } -static void op_add_key_data(const char *filename, - struct op op[], unsigned int op_num, char *words[]) +static void op_add_key_data(char *filename[], struct op op[], + unsigned file, unsigned op_num, char *words[]) { if (!words[2] || !words[3] || !words[4] || words[5] || !streq(words[3], "=")) - fail(filename, op_num+1, "Expected = "); - op[op_num].key = make_tdb_data(op, filename, op_num+1, words[2]); - op[op_num].data = make_tdb_data(op, filename, op_num+1, words[4]); - /* May only be a unique key if it fails */ + fail(filename[file], op_num+1, "Expected = "); + op[op_num].key = make_tdb_data(op, filename[file], op_num+1, words[2]); + op[op_num].data = make_tdb_data(op, filename[file], op_num+1, words[4]); + /* Likely only be a unique key if it fails */ if (!op[op_num].data.dptr) total_keys++; + else if (random() % 2) + total_keys++; } /* We don't record the keys or data for a traverse, as we don't use them. */ -static void op_add_traverse(const char *filename, - struct op op[], unsigned int op_num, char *words[]) +static void op_add_traverse(char *filename[], struct op op[], + unsigned file, unsigned op_num, char *words[]) { if (!words[2] || !words[3] || !words[4] || words[5] || !streq(words[3], "=")) - fail(filename, op_num+1, "Expected = "); + fail(filename[file], op_num+1, "Expected = "); op[op_num].key = tdb_null; } /* Full traverse info is useful for debugging, but changing it to * "traversefn" without the data makes the traces *much* smaller! */ -static void op_add_traversefn(const char *filename, - struct op op[], unsigned int op_num, char *words[]) +static void op_add_traversefn(char *filename[], struct op op[], + unsigned file, unsigned op_num, char *words[]) { if (words[2]) - fail(filename, op_num+1, "Expected no values"); + fail(filename[file], op_num+1, "Expected no values"); op[op_num].key = tdb_null; } /* tdb_store = */ -static void op_add_store(const char *filename, - struct op op[], unsigned int op_num, char *words[]) +static void op_add_store(char *filename[], struct op op[], + unsigned file, unsigned op_num, char *words[]) { if (!words[2] || !words[3] || !words[4] || !words[5] || !words[6] || words[7] || !streq(words[5], "=")) - fail(filename, op_num+1, "Expect = "); + fail(filename[file], op_num+1, "Expect = "); op[op_num].flag = strtoul(words[4], NULL, 0); op[op_num].ret = atoi(words[6]); - op[op_num].key = make_tdb_data(op, filename, op_num+1, words[2]); - op[op_num].data = make_tdb_data(op, filename, op_num+1, words[3]); + op[op_num].key = make_tdb_data(op, filename[file], op_num+1, words[2]); + op[op_num].data = make_tdb_data(op, filename[file], op_num+1, words[3]); total_keys++; } /* tdb_append = */ -static void op_add_append(const char *filename, - struct op op[], unsigned int op_num, char *words[]) +static void op_add_append(char *filename[], struct op op[], + unsigned file, unsigned op_num, char *words[]) { if (!words[2] || !words[3] || !words[4] || !words[5] || words[6] || !streq(words[4], "=")) - fail(filename, op_num+1, "Expect = "); + fail(filename[file], op_num+1, "Expect = "); - op[op_num].key = make_tdb_data(op, filename, op_num+1, words[2]); - op[op_num].data = make_tdb_data(op, filename, op_num+1, words[3]); + op[op_num].key = make_tdb_data(op, filename[file], op_num+1, words[2]); + op[op_num].data = make_tdb_data(op, filename[file], op_num+1, words[3]); op[op_num].append.post - = make_tdb_data(op, filename, op_num+1, words[5]); + = make_tdb_data(op, filename[file], op_num+1, words[5]); /* By subtraction, figure out what previous data was. */ op[op_num].append.pre.dptr = op[op_num].append.post.dptr; @@ -305,64 +318,75 @@ static void op_add_append(const char *filename, } /* tdb_get_seqnum = */ -static void op_add_seqnum(const char *filename, - struct op op[], unsigned int op_num, char *words[]) +static void op_add_seqnum(char *filename[], struct op op[], + unsigned file, unsigned op_num, char *words[]) { if (!words[2] || !words[3] || words[4] || !streq(words[2], "=")) - fail(filename, op_num+1, "Expect = "); + fail(filename[file], op_num+1, "Expect = "); op[op_num].key = tdb_null; op[op_num].ret = atoi(words[3]); } -static void op_add_traverse_start(const char *filename, - struct op op[], - unsigned int op_num, char *words[]) +static void op_add_traverse_start(char *filename[], struct op op[], + unsigned file, unsigned op_num, char *words[]) { if (words[2]) - fail(filename, op_num+1, "Expect no arguments"); + fail(filename[file], op_num+1, "Expect no arguments"); op[op_num].key = tdb_null; op[op_num].group_len = 0; } -static void op_add_transaction(const char *filename, struct op op[], - unsigned int op_num, char *words[]) +static void op_add_transaction(char *filename[], struct op op[], + unsigned file, unsigned op_num, char *words[]) { if (words[2]) - fail(filename, op_num+1, "Expect no arguments"); + fail(filename[file], op_num+1, "Expect no arguments"); op[op_num].key = tdb_null; op[op_num].group_len = 0; } -static void op_add_chainlock(const char *filename, - struct op op[], unsigned int op_num, char *words[]) +static void op_add_chainlock(char *filename[], struct op op[], + unsigned file, unsigned op_num, char *words[]) { if (words[2] == NULL || words[3]) - fail(filename, op_num+1, "Expected just a key"); + fail(filename[file], op_num+1, "Expected just a key"); /* A chainlock key isn't a key in the normal sense; it doesn't * have to be in the db at all. Also, we don't want to hash this op. */ - op[op_num].data = make_tdb_data(op, filename, op_num+1, words[2]); + op[op_num].data = make_tdb_data(op, filename[file], op_num+1, words[2]); op[op_num].key = tdb_null; op[op_num].group_len = 0; } -static void op_add_chainlock_ret(const char *filename, - struct op op[], unsigned int op_num, - char *words[]) +static void op_add_chainlock_ret(char *filename[], struct op op[], + unsigned file, unsigned op_num, char *words[]) { if (!words[2] || !words[3] || !words[4] || words[5] || !streq(words[3], "=")) - fail(filename, op_num+1, "Expected = "); + fail(filename[file], op_num+1, "Expected = "); op[op_num].ret = atoi(words[4]); - op[op_num].data = make_tdb_data(op, filename, op_num+1, words[2]); + op[op_num].data = make_tdb_data(op, filename[file], op_num+1, words[2]); op[op_num].key = tdb_null; op[op_num].group_len = 0; total_keys++; } +static void op_add_wipe_all(char *filename[], struct op op[], + unsigned file, unsigned op_num, char *words[]) +{ + if (words[2]) + fail(filename[file], op_num+1, "Expected no arguments"); + op[op_num].key = tdb_null; + wipe_alls = talloc_realloc(NULL, wipe_alls, struct op_desc, + num_wipe_alls+1); + wipe_alls[num_wipe_alls].file = file; + wipe_alls[num_wipe_alls].op_num = op_num; + num_wipe_alls++; +} + static int op_find_start(struct op op[], unsigned int op_num, enum op_type type) { unsigned int i; @@ -374,8 +398,8 @@ static int op_find_start(struct op op[], unsigned int op_num, enum op_type type) return 0; } -static void op_analyze_transaction(const char *filename, - struct op op[], unsigned int op_num, +static void op_analyze_transaction(char *filename[], struct op op[], + unsigned file, unsigned op_num, char *words[]) { unsigned int start, i; @@ -383,11 +407,11 @@ static void op_analyze_transaction(const char *filename, op[op_num].key = tdb_null; if (words[2]) - fail(filename, op_num+1, "Expect no arguments"); + fail(filename[file], op_num+1, "Expect no arguments"); start = op_find_start(op, op_num, OP_TDB_TRANSACTION_START); if (!start) - fail(filename, op_num+1, "no transaction start found"); + fail(filename[file], op_num+1, "no transaction start found"); op[start].group_len = op_num - start; @@ -397,16 +421,15 @@ static void op_analyze_transaction(const char *filename, } /* We treat chainlocks a lot like transactions, even though that's overkill */ -static void op_analyze_chainlock(const char *filename, - struct op op[], unsigned int op_num, - char *words[]) +static void op_analyze_chainlock(char *filename[], struct op op[], + unsigned file, unsigned op_num, char *words[]) { unsigned int i, start; if (words[2] == NULL || words[3]) - fail(filename, op_num+1, "Expected just a key"); + fail(filename[file], op_num+1, "Expected just a key"); - op[op_num].data = make_tdb_data(op, filename, op_num+1, words[2]); + op[op_num].data = make_tdb_data(op, filename[file], op_num+1, words[2]); op[op_num].key = tdb_null; total_keys++; @@ -414,21 +437,20 @@ static void op_analyze_chainlock(const char *filename, if (!start) start = op_find_start(op, op_num, OP_TDB_CHAINLOCK_READ); if (!start) - fail(filename, op_num+1, "no initial chainlock found"); + fail(filename[file], op_num+1, "no initial chainlock found"); /* FIXME: We'd have to do something clever to make this work * vs. deadlock. */ if (!key_eq(op[start].data, op[op_num].data)) - fail(filename, op_num+1, "nested chainlock calls?"); + fail(filename[file], op_num+1, "nested chainlock calls?"); op[start].group_len = op_num - start; for (i = start; i <= op_num; i++) op[i].group_start = start; } -static void op_analyze_traverse(const char *filename, - struct op op[], unsigned int op_num, - char *words[]) +static void op_analyze_traverse(char *filename[], struct op op[], + unsigned file, unsigned op_num, char *words[]) { int i, start; @@ -437,7 +459,7 @@ static void op_analyze_traverse(const char *filename, /* = %u means traverse function terminated. */ if (words[2]) { if (!streq(words[2], "=") || !words[3] || words[4]) - fail(filename, op_num+1, "expect = "); + fail(filename[file], op_num+1, "expect = "); op[op_num].ret = atoi(words[3]); } else op[op_num].ret = 0; @@ -446,7 +468,7 @@ static void op_analyze_traverse(const char *filename, if (!start) start = op_find_start(op, op_num, OP_TDB_TRAVERSE_READ_START); if (!start) - fail(filename, op_num+1, "no traversal start found"); + fail(filename[file], op_num+1, "no traversal start found"); op[start].group_len = op_num - start; @@ -486,12 +508,14 @@ static void dump_pre(char *filename[], struct op *op[], { struct depend *dep; - printf("%s:%u (%u) still waiting for:\n", filename[file], i+1, - op[file][i].seqnum); - list_for_each(&op[file][i].pre, dep, pre_list) - printf(" %s:%u (%u)\n", - filename[dep->prereq.file], dep->prereq.op_num+1, - op[dep->prereq.file][dep->prereq.op_num].seqnum); + if (!quiet) { + printf("%s:%u (%u) still waiting for:\n", filename[file], i+1, + op[file][i].seqnum); + list_for_each(&op[file][i].pre, dep, pre_list) + printf(" %s:%u (%u)\n", + filename[dep->prereq.file], dep->prereq.op_num+1, + op[dep->prereq.file][dep->prereq.op_num].seqnum); + } check_deps(filename[file], op[file], i); } @@ -515,8 +539,12 @@ static bool do_pre(struct tdb_context *tdb, while (read(pre_fd, &dep, sizeof(dep)) != sizeof(dep)) { if (errno == EINTR) { if (backoff) { + struct op_desc desc = { file,i }; warnx("%s:%u:avoiding deadlock", filename[file], i+1); + if (write(backoff_fd, &desc, + sizeof(desc)) != sizeof(desc)) + err(1, "writing backoff_fd"); return false; } dump_pre(filename, op, file, i); @@ -607,7 +635,7 @@ static int nontrivial_traverse(struct tdb_context *tdb, tinfo->file, tinfo->i+1, tinfo->start + trav_len, avoid_deadlock); - /* We backed off, or we hit OP_TDB_TRAVERSE_END. */ + /* We backed off, or we hit OP_TDB_TRAVERSE_END/EARLY. */ if (tinfo->op[tinfo->file][tinfo->i].type != OP_TDB_TRAVERSE) return 1; @@ -632,7 +660,8 @@ static unsigned op_traverse(struct tdb_context *tdb, * original traverse went A (delete A), B, we might do B * (delete A). So if we have ops left over, we do it now. */ while (tinfo.i != start + op[file][start].group_len) { - if (op[file][tinfo.i].type == OP_TDB_TRAVERSE) + if (op[file][tinfo.i].type == OP_TDB_TRAVERSE + || op[file][tinfo.i].type == OP_TDB_TRAVERSE_END_EARLY) tinfo.i++; else tinfo.i = run_ops(tdb, pre_fd, filename, op, file, @@ -756,6 +785,10 @@ unsigned run_ops(struct tdb_context *tdb, case OP_TDB_TRANSACTION_CANCEL: try(tdb_transaction_cancel(tdb), op[file][i].ret); break; + case OP_TDB_TRANSACTION_PREPARE_COMMIT: + try(tdb_transaction_prepare_commit(tdb), + op[file][i].ret); + break; case OP_TDB_TRANSACTION_COMMIT: try(tdb_transaction_commit(tdb), op[file][i].ret); break; @@ -768,6 +801,7 @@ unsigned run_ops(struct tdb_context *tdb, tdb_traverse, op, i); break; case OP_TDB_TRAVERSE: + case OP_TDB_TRAVERSE_END_EARLY: /* Terminate: we're in a traverse, and we've * done our ops. */ return i; @@ -793,6 +827,11 @@ unsigned run_ops(struct tdb_context *tdb, case OP_TDB_DELETE: try(tdb_delete(tdb, op[file][i].key), op[file][i].ret); break; + case OP_TDB_REPACK: + /* We do nothing here: the transaction and traverse are + * traced. It's in the trace to mark it, since it + * may become unnecessary in future. */ + break; } do_post(filename, op, file, i); } @@ -801,22 +840,24 @@ unsigned run_ops(struct tdb_context *tdb, /* tdbtorture, in particular, can do a tdb_close with a transaction in * progress. */ -static struct op *maybe_cancel_transaction(const char *filename, +static struct op *maybe_cancel_transaction(char *filename[], unsigned int file, struct op *op, unsigned int *num) { unsigned int start = op_find_start(op, *num, OP_TDB_TRANSACTION_START); if (start) { char *words[] = { "", "tdb_close", NULL }; - add_op(filename, &op, *num, op[start].seqnum, + add_op(filename[file], &op, *num, op[start].seqnum, OP_TDB_TRANSACTION_CANCEL); - op_analyze_transaction(filename, op, *num, words); + op_analyze_transaction(filename, op, file, *num, words); (*num)++; } return op; } -static struct op *load_tracefile(const char *filename, unsigned int *num, +static struct op *load_tracefile(char *filename[], + unsigned int file, + unsigned int *num, unsigned int *hashsize, unsigned int *tdb_flags, unsigned int *open_flags) @@ -825,19 +866,19 @@ static struct op *load_tracefile(const char *filename, unsigned int *num, struct op *op = talloc_array(NULL, struct op, 1); char **words; char **lines; - char *file; + char *contents; - file = grab_file(NULL, filename, NULL); - if (!file) - err(1, "Reading %s", filename); + contents = grab_file(NULL, filename[file], NULL); + if (!contents) + err(1, "Reading %s", filename[file]); - lines = strsplit(file, file, "\n", NULL); + lines = strsplit(contents, contents, "\n"); if (!lines[0]) - errx(1, "%s is empty", filename); + errx(1, "%s is empty", filename[file]); - words = strsplit(lines, lines[0], " ", NULL); + words = strsplit(lines, lines[0], " "); if (!streq(words[1], "tdb_open")) - fail(filename, 1, "does not start with tdb_open"); + fail(filename[file], 1, "does not start with tdb_open"); *hashsize = atoi(words[2]); *tdb_flags = strtoul(words[3], NULL, 0); @@ -846,33 +887,38 @@ static struct op *load_tracefile(const char *filename, unsigned int *num, for (i = 1; lines[i]; i++) { const struct op_table *opt; - words = strsplit(lines, lines[i], " ", NULL); + words = strsplit(lines, lines[i], " "); if (!words[0] || !words[1]) - fail(filename, i+1, "Expected seqnum number and op"); + fail(filename[file], i+1, + "Expected seqnum number and op"); opt = find_keyword(words[1], strlen(words[1])); if (!opt) { if (streq(words[1], "tdb_close")) { if (lines[i+1]) - fail(filename, i+2, + fail(filename[file], i+2, "lines after tdb_close"); *num = i; talloc_free(lines); - return maybe_cancel_transaction(filename, + return maybe_cancel_transaction(filename, file, op, num); } - fail(filename, i+1, "Unknown operation '%s'", words[1]); + fail(filename[file], i+1, + "Unknown operation '%s'", words[1]); } - add_op(filename, &op, i, atoi(words[0]), opt->type); - opt->enhance_op(filename, op, i, words); + add_op(filename[file], &op, i, atoi(words[0]), opt->type); + opt->enhance_op(filename, op, file, i, words); } - fprintf(stderr, "%s:%u:last operation is not tdb_close: incomplete?", - filename, i); - talloc_free(lines); + if (!quiet) + fprintf(stderr, + "%s:%u:last operation is not tdb_close: incomplete?", + filename[file], i); + + talloc_free(contents); *num = i - 1; - return maybe_cancel_transaction(filename, op, num); + return maybe_cancel_transaction(filename, file, op, num); } /* We remember all the keys we've ever seen, and who has them. */ @@ -882,6 +928,44 @@ struct keyinfo { struct op_desc *user; }; +static bool starts_transaction(const struct op *op) +{ + return op->type == OP_TDB_TRANSACTION_START; +} + +static bool in_transaction(const struct op op[], unsigned int i) +{ + return op[i].group_start && starts_transaction(&op[op[i].group_start]); +} + +static bool successful_transaction(const struct op *op) +{ + return starts_transaction(op) + && op[op->group_len].type == OP_TDB_TRANSACTION_COMMIT; +} + +static bool starts_traverse(const struct op *op) +{ + return op->type == OP_TDB_TRAVERSE_START + || op->type == OP_TDB_TRAVERSE_READ_START; +} + +static bool in_traverse(const struct op op[], unsigned int i) +{ + return op[i].group_start && starts_traverse(&op[op[i].group_start]); +} + +static bool starts_chainlock(const struct op *op) +{ + return op->type == OP_TDB_CHAINLOCK_READ + || op->type == OP_TDB_CHAINLOCK; +} + +static bool in_chainlock(const struct op op[], unsigned int i) +{ + return op[i].group_start && starts_chainlock(&op[op[i].group_start]); +} + static const TDB_DATA must_not_exist; static const TDB_DATA must_exist; static const TDB_DATA not_exists_or_empty; @@ -889,8 +973,31 @@ static const TDB_DATA not_exists_or_empty; /* NULL means doesn't care if it exists or not, &must_exist means * it must exist but we don't care what, &must_not_exist means it must * not exist, otherwise the data it needs. */ -static const TDB_DATA *needs(const struct op *op) +static const TDB_DATA *needs(const TDB_DATA *key, const struct op *op) { + /* Look through for an op in this transaction which needs this key. */ + if (starts_transaction(op) || starts_chainlock(op)) { + unsigned int i; + const TDB_DATA *need = NULL; + + for (i = 1; i < op->group_len; i++) { + if (key_eq(op[i].key, *key) + || op[i].type == OP_TDB_WIPE_ALL) { + need = needs(key, &op[i]); + /* tdb_exists() is special: there might be + * something in the transaction with more + * specific requirements. Other ops don't have + * specific requirements (eg. store or delete), + * but they change the value so we can't get + * more information from future ops. */ + if (op[i].type != OP_TDB_EXISTS) + break; + } + } + + return need; + } + switch (op->type) { /* FIXME: Pull forward deps, since we can deadlock */ case OP_TDB_CHAINLOCK: @@ -960,44 +1067,6 @@ static const TDB_DATA *needs(const struct op *op) } -static bool starts_transaction(const struct op *op) -{ - return op->type == OP_TDB_TRANSACTION_START; -} - -static bool in_transaction(const struct op op[], unsigned int i) -{ - return op[i].group_start && starts_transaction(&op[op[i].group_start]); -} - -static bool successful_transaction(const struct op *op) -{ - return starts_transaction(op) - && op[op->group_len].type == OP_TDB_TRANSACTION_COMMIT; -} - -static bool starts_traverse(const struct op *op) -{ - return op->type == OP_TDB_TRAVERSE_START - || op->type == OP_TDB_TRAVERSE_READ_START; -} - -static bool in_traverse(const struct op op[], unsigned int i) -{ - return op[i].group_start && starts_traverse(&op[op[i].group_start]); -} - -static bool starts_chainlock(const struct op *op) -{ - return op->type == OP_TDB_CHAINLOCK_READ - || op->type == OP_TDB_CHAINLOCK; -} - -static bool in_chainlock(const struct op op[], unsigned int i) -{ - return op[i].group_start && starts_chainlock(&op[op[i].group_start]); -} - /* What's the data after this op? pre if nothing changed. */ static const TDB_DATA *gives(const TDB_DATA *key, const TDB_DATA *pre, const struct op *op) @@ -1014,7 +1083,8 @@ static const TDB_DATA *gives(const TDB_DATA *key, const TDB_DATA *pre, for (i = 1; i < op->group_len; i++) { /* This skips nested transactions, too */ - if (key_eq(op[i].key, *key)) + if (key_eq(op[i].key, *key) + || op[i].type == OP_TDB_WIPE_ALL) pre = gives(key, pre, &op[i]); } return pre; @@ -1036,6 +1106,35 @@ static const TDB_DATA *gives(const TDB_DATA *key, const TDB_DATA *pre, return pre; } +static void add_hash_user(struct keyinfo *hash, + unsigned int h, + struct op *op[], + unsigned int file, + unsigned int op_num) +{ + hash[h].user = talloc_realloc(hash, hash[h].user, + struct op_desc, hash[h].num_users+1); + + /* If it's in a transaction, it's the transaction which + * matters from an analysis POV. */ + if (in_transaction(op[file], op_num) + || in_chainlock(op[file], op_num)) { + unsigned i; + + op_num = op[file][op_num].group_start; + + /* Don't include twice. */ + for (i = 0; i < hash[h].num_users; i++) { + if (hash[h].user[i].file == file + && hash[h].user[i].op_num == op_num) + return; + } + } + hash[h].user[hash[h].num_users].op_num = op_num; + hash[h].user[hash[h].num_users].file = file; + hash[h].num_users++; +} + static struct keyinfo *hash_ops(struct op *op[], unsigned int num_ops[], unsigned int num) { @@ -1065,60 +1164,28 @@ static struct keyinfo *hash_ops(struct op *op[], unsigned int num_ops[], talloc_free(op[i][j].key.dptr); op[i][j].key.dptr = hash[h].key.dptr; } - hash[h].user = talloc_realloc(hash, hash[h].user, - struct op_desc, - hash[h].num_users+1); - - /* If it's in a transaction, it's the transaction which - * matters from an analysis POV. */ - if (in_transaction(op[i], j) - || in_chainlock(op[i], j)) { - unsigned start = op[i][j].group_start; - - /* Don't include twice. */ - if (hash[h].num_users - && hash[h].user[hash[h].num_users-1].file - == i - && hash[h].user[hash[h].num_users-1].op_num - == start) - continue; - hash[h].user[hash[h].num_users].op_num = start; - } else - hash[h].user[hash[h].num_users].op_num = j; - hash[h].user[hash[h].num_users].file = i; - hash[h].num_users++; + add_hash_user(hash, h, op, i, j); } } + /* Any wipe all entries need adding to all hash entries. */ + for (h = 0; h < total_keys*2; h++) { + if (!hash[h].num_users) + continue; + + for (i = 0; i < num_wipe_alls; i++) + add_hash_user(hash, h, op, + wipe_alls[i].file, wipe_alls[i].op_num); + } + return hash; } static bool satisfies(const TDB_DATA *key, const TDB_DATA *data, const struct op *op) { - const TDB_DATA *need = NULL; - - if (starts_transaction(op) || starts_chainlock(op)) { - unsigned int i; - - /* Look through for an op in this transaction which - * needs this key. */ - for (i = 1; i < op->group_len; i++) { - if (key_eq(op[i].key, *key)) { - need = needs(&op[i]); - /* tdb_exists() is special: there might be - * something in the transaction with more - * specific requirements. Other ops don't have - * specific requirements (eg. store or delete), - * but they change the value so we can't get - * more information from future ops. */ - if (op[i].type != OP_TDB_EXISTS) - break; - } - } - } else - need = needs(op); + const TDB_DATA *need = needs(key, op); /* Don't need anything? Cool. */ if (!need) @@ -1242,12 +1309,11 @@ static void check_dep_sorting(struct op_desc user[], unsigned num_users, * number unlocked (the race can cause less detectable ordering problems, * in which case we'll deadlock and report: fix manually in that case). */ -static void figure_deps(char *filename[], struct op *op[], - const TDB_DATA *key, struct op_desc user[], +static bool figure_deps(char *filename[], struct op *op[], + const TDB_DATA *key, const TDB_DATA *data, + struct op_desc user[], unsigned num_users, unsigned num_files) { - /* We assume database starts empty. */ - const struct TDB_DATA *data = &tdb_null; unsigned int fuzz; /* We prefer to keep strict seqnum order if possible: it's the @@ -1259,13 +1325,36 @@ static void figure_deps(char *filename[], struct op *op[], } if (fuzz >= 100) - fail(filename[user[0].file], user[0].op_num+1, - "Could not resolve inter-dependencies"); + return false; check_dep_sorting(user, num_users, num_files); + return true; } -static void sort_ops(struct keyinfo hash[], char *filename[], struct op *op[], +/* We're having trouble sorting out dependencies for this key. Assume that it's + * a pre-existing record in the db, so determine a likely value. */ +static const TDB_DATA *preexisting_data(char *filename[], struct op *op[], + const TDB_DATA *key, + struct op_desc *user, + unsigned int num_users) +{ + unsigned int i; + const TDB_DATA *data; + + for (i = 0; i < num_users; i++) { + data = needs(key, &op[user->file][user->op_num]); + if (data && data != &must_not_exist) { + if (!quiet) + printf("%s:%u: needs pre-existing record\n", + filename[user->file], user->op_num+1); + return data; + } + } + return &tdb_null; +} + +static void sort_ops(struct tdb_context *tdb, + struct keyinfo hash[], char *filename[], struct op *op[], unsigned int num) { unsigned int h; @@ -1302,8 +1391,20 @@ static void sort_ops(struct keyinfo hash[], char *filename[], struct op *op[], struct op_desc *user = hash[h].user; qsort(user, hash[h].num_users, sizeof(user[0]), compare_seqnum); - figure_deps(filename, op, &hash[h].key, user, hash[h].num_users, - num); + if (!figure_deps(filename, op, &hash[h].key, &tdb_null, user, + hash[h].num_users, num)) { + const TDB_DATA *data; + + data = preexisting_data(filename, op, &hash[h].key, + user, hash[h].num_users); + /* Give the first op what it wants: does that help? */ + if (!figure_deps(filename, op, &hash[h].key, data, user, + hash[h].num_users, num)) + fail(filename[user[0].file], user[0].op_num+1, + "Could not resolve inter-dependencies"); + if (tdb_store(tdb, hash[h].key, *data, TDB_INSERT) != 0) + errx(1, "Could not store initial value"); + } } } @@ -1552,9 +1653,56 @@ static void make_traverse_depends(char *filename[], } talloc_free(desc); } + +static void set_nonblock(int fd) +{ + if (fcntl(fd, F_SETFL, fcntl(fd, F_GETFL)|O_NONBLOCK) != 0) + err(1, "Setting pipe nonblocking"); +} + +static bool handle_backoff(struct op *op[], int fd) +{ + struct op_desc desc; + bool handled = false; + + /* Sloppy coding: we assume PIPEBUF never fills. */ + while (read(fd, &desc, sizeof(desc)) != -1) { + unsigned int i; + handled = true; + for (i = desc.op_num; i > 0; i--) { + if (op[desc.file][i].type == OP_TDB_TRAVERSE) { + /* We insert a fake end here. */ + op[desc.file][i].type + = OP_TDB_TRAVERSE_END_EARLY; + break; + } else if (starts_traverse(&op[desc.file][i])) { + unsigned int start = i; + struct op tmp = op[desc.file][i]; + /* Move the ops outside traverse. */ + memmove(&op[desc.file][i], + &op[desc.file][i+1], + (desc.op_num-i-1) * sizeof(op[0][0])); + op[desc.file][desc.op_num] = tmp; + while (op[desc.file][i].group_start == start) { + op[desc.file][i++].group_start + = desc.op_num; + } + break; + } + } + } + return handled; +} + +#else /* !TRAVERSALS_TAKE_TRANSACTION_LOCK */ +static bool handle_backoff(struct op *op[], int fd) +{ + return false; +} #endif -static void derive_dependencies(char *filename[], +static void derive_dependencies(struct tdb_context *tdb, + char *filename[], struct op *op[], unsigned int num_ops[], unsigned int num) { @@ -1565,7 +1713,7 @@ static void derive_dependencies(char *filename[], hash = hash_ops(op, num_ops, num); /* Sort them by sequence number. */ - sort_ops(hash, filename, op, num); + sort_ops(tdb, hash, filename, op, num); /* Create dependencies back to the last change, rather than * creating false dependencies by naively making each one @@ -1601,64 +1749,29 @@ static void derive_dependencies(char *filename[], optimize_dependencies(op, num_ops, num); } -int main(int argc, char *argv[]) +static struct timeval run_test(char *argv[], + unsigned int num_ops[], + unsigned int hashsize[], + unsigned int tdb_flags[], + unsigned int open_flags[], + struct op *op[], + int fds[2]) { - struct timeval start, end; - unsigned int i, num_ops[argc], hashsize[argc], tdb_flags[argc], open_flags[argc]; - struct op *op[argc]; - int fds[2]; - char c; + unsigned int i; + struct timeval start, end, diff; bool ok = true; - if (argc < 3) - errx(1, "Usage: %s ...", argv[0]); - - pipes = talloc_array(NULL, struct pipe, argc - 2); - for (i = 0; i < argc - 2; i++) { - printf("Loading tracefile %s...", argv[2+i]); - fflush(stdout); - op[i] = load_tracefile(argv[2+i], &num_ops[i], &hashsize[i], - &tdb_flags[i], &open_flags[i]); - if (pipe(pipes[i].fd) != 0) - err(1, "creating pipe"); - printf("done\n"); - } - - printf("Calculating inter-dependencies..."); - fflush(stdout); - derive_dependencies(argv+2, op, num_ops, i); - printf("done\n"); - - /* Don't fork for single arg case: simple debugging. */ - if (argc == 3) { - struct tdb_context *tdb; - tdb = tdb_open_ex(argv[1], hashsize[0], tdb_flags[0]|TDB_NOSYNC, - open_flags[0], 0600, NULL, hash_key); - printf("Single threaded run..."); - fflush(stdout); - - run_ops(tdb, pipes[0].fd[0], argv+2, op, 0, 1, num_ops[0], - false); - check_deps(argv[2], op[0], num_ops[0]); - - printf("done\n"); - exit(0); - } - - if (pipe(fds) != 0) - err(1, "creating pipe"); - - for (i = 0; i < argc - 2; i++) { + for (i = 0; argv[i+2]; i++) { struct tdb_context *tdb; + char c; switch (fork()) { case -1: err(1, "fork failed"); case 0: close(fds[1]); - tdb = tdb_open_ex(argv[1], hashsize[i], - tdb_flags[i]|TDB_NOSYNC, - open_flags[i], 0600, NULL, hash_key); + tdb = tdb_open(argv[1], hashsize[i], + tdb_flags[i], open_flags[i], 0600); if (!tdb) err(1, "Opening tdb %s", argv[1]); @@ -1677,14 +1790,15 @@ int main(int argc, char *argv[]) /* Let everything settle. */ sleep(1); - printf("Starting run..."); + if (!quiet) + printf("Starting run..."); fflush(stdout); gettimeofday(&start, NULL); /* Tell them all to go! Any write of sufficient length will do. */ if (write(fds[1], hashsize, i) != i) err(1, "Writing to wakeup pipe"); - for (i = 0; i < argc - 2; i++) { + for (i = 0; argv[i + 2]; i++) { int status; wait(&status); if (!WIFEXITED(status)) { @@ -1698,11 +1812,144 @@ int main(int argc, char *argv[]) exit(1); gettimeofday(&end, NULL); - printf("done\n"); + if (!quiet) + printf("done\n"); + + if (end.tv_usec < start.tv_usec) { + end.tv_usec += 1000000; + end.tv_sec--; + } + diff.tv_sec = end.tv_sec - start.tv_sec; + diff.tv_usec = end.tv_usec - start.tv_usec; + return diff; +} + +static void init_tdb(struct tdb_context *master_tdb, + const char *name, unsigned int hashsize) +{ + TDB_DATA key, data; + struct tdb_context *tdb; + + tdb = tdb_open(name, hashsize, TDB_CLEAR_IF_FIRST|TDB_NOSYNC, + O_CREAT|O_TRUNC|O_RDWR, 0600); + if (!tdb) + errx(1, "opening tdb %s", name); + + for (key = tdb_firstkey(master_tdb); + key.dptr; + key = tdb_nextkey(master_tdb, key)) { + data = tdb_fetch(master_tdb, key); + if (tdb_store(tdb, key, data, TDB_INSERT) != 0) + errx(1, "Failed to store initial key"); + } + tdb_close(tdb); +} + +int main(int argc, char *argv[]) +{ + struct timeval diff; + unsigned int i, num_ops[argc], hashsize[argc], tdb_flags[argc], open_flags[argc]; + struct op *op[argc]; + int fds[2]; + struct tdb_context *master; + unsigned int runs = 1; + + if (argc < 3) + errx(1, "Usage: %s [--quiet] [-n ] ...", argv[0]); + + if (streq(argv[1], "--quiet")) { + quiet = true; + argv++; + argc--; + } + if (streq(argv[1], "-n")) { + runs = atoi(argv[2]); + argv += 2; + argc -= 2; + } + + pipes = talloc_array(NULL, struct pipe, argc - 1); + for (i = 0; i < argc - 2; i++) { + if (!quiet) + printf("Loading tracefile %s...", argv[2+i]); + fflush(stdout); + op[i] = load_tracefile(argv+2, i, &num_ops[i], &hashsize[i], + &tdb_flags[i], &open_flags[i]); + if (pipe(pipes[i].fd) != 0) + err(1, "creating pipe"); + /* Don't truncate, or clear if first: we do that. */ + open_flags[i] &= ~(O_TRUNC); + tdb_flags[i] &= ~(TDB_CLEAR_IF_FIRST); + /* Open NOSYNC, to save time. */ + tdb_flags[i] |= TDB_NOSYNC; + if (!quiet) + printf("done\n"); + } + + /* Dependency may figure we need to create seed records. */ + master = tdb_open(NULL, 0, TDB_INTERNAL, O_RDWR, 0); + if (!quiet) { + printf("Calculating inter-dependencies..."); + fflush(stdout); + } + derive_dependencies(master, argv+2, op, num_ops, i); + if (!quiet) + printf("done\n"); + + for (i = 0; i < runs; i++) { + init_tdb(master, argv[1], hashsize[0]); + + /* Don't fork for single arg case: simple debugging. */ + if (argc == 3) { + struct timeval start, end; + struct tdb_context *tdb; + + tdb = tdb_open(argv[1], hashsize[0], tdb_flags[0], + open_flags[0], 0600); + if (!quiet) { + printf("Single threaded run..."); + fflush(stdout); + } + gettimeofday(&start, NULL); + + run_ops(tdb, pipes[0].fd[0], argv+2, op, 0, 1, + num_ops[0], false); + gettimeofday(&end, NULL); + if (!quiet) + printf("done\n"); + tdb_close(tdb); + + check_deps(argv[2], op[0], num_ops[0]); + if (end.tv_usec < start.tv_usec) { + end.tv_usec += 1000000; + end.tv_sec--; + } + diff.tv_sec = end.tv_sec - start.tv_sec; + diff.tv_usec = end.tv_usec - start.tv_usec; + goto print_time; + } + + if (pipe(fds) != 0) + err(1, "creating pipe"); + +#if TRAVERSALS_TAKE_TRANSACTION_LOCK + if (pipe(pipes[argc-2].fd) != 0) + err(1, "creating pipe"); + backoff_fd = pipes[argc-2].fd[1]; + set_nonblock(pipes[argc-2].fd[1]); + set_nonblock(pipes[argc-2].fd[0]); +#endif + + do { + diff = run_test(argv, num_ops, hashsize, tdb_flags, + open_flags, op, fds); + } while (handle_backoff(op, pipes[argc-2].fd[0])); + + print_time: + if (!quiet) + printf("Time replaying: "); + printf("%lu usec\n", diff.tv_sec * 1000000UL + diff.tv_usec); + } - end.tv_sec -= start.tv_sec; - printf("Time replaying: %lu usec\n", - end.tv_sec * 1000000UL + (end.tv_usec - start.tv_usec)); - exit(0); }