X-Git-Url: https://git.ozlabs.org/?p=ccan;a=blobdiff_plain;f=ccan%2Ftdb%2Ftools%2Freplay_trace.c;h=0ca81aaa0386d29aba032162320045231fa9a1a0;hp=e639dcdc6ce656e132230c2057003431daa76623;hb=a08f09dbdc69dafea90f8b67655e936cc6d2019a;hpb=f2050233ad3b995baf239715457b53d64ebbf106 diff --git a/ccan/tdb/tools/replay_trace.c b/ccan/tdb/tools/replay_trace.c index e639dcdc..0ca81aaa 100644 --- a/ccan/tdb/tools/replay_trace.c +++ b/ccan/tdb/tools/replay_trace.c @@ -22,7 +22,7 @@ /* Avoid mod by zero */ static unsigned int total_keys = 1; -#define DEBUG_DEPS 1 +/* #define DEBUG_DEPS 1 */ /* Traversals block transactions in the current implementation. */ #define TRAVERSALS_TAKE_TRANSACTION_LOCK 1 @@ -213,8 +213,7 @@ static void op_add_key(const char *filename, fail(filename, op_num+1, "Expected just a key"); op[op_num].key = make_tdb_data(op, filename, op_num+1, words[2]); - if (op[op_num].op != OP_TDB_TRAVERSE) - total_keys++; + total_keys++; } static void op_add_key_ret(const char *filename, @@ -243,6 +242,16 @@ static void op_add_key_data(const char *filename, 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[]) +{ + if (!words[2] || !words[3] || !words[4] || words[5] + || !streq(words[3], "=")) + fail(filename, op_num+1, "Expected = "); + 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[]) @@ -290,8 +299,9 @@ static void op_add_seqnum(const char *filename, op[op_num].ret = atoi(words[3]); } -static void op_add_traverse(const char *filename, - struct op op[], unsigned int op_num, char *words[]) +static void op_add_traverse_start(const char *filename, + struct op op[], + unsigned int op_num, char *words[]) { if (words[2]) fail(filename, op_num+1, "Expect no arguments"); @@ -310,12 +320,12 @@ static void op_add_transaction(const char *filename, struct op op[], op[op_num].group_len = 0; } -static int op_transaction_start(struct op op[], unsigned int op_num) +static int op_find_start(struct op op[], unsigned int op_num, enum op_type type) { unsigned int i; for (i = op_num-1; i > 0; i--) { - if (op[i].op == OP_TDB_TRANSACTION_START && !op[i].group_len) + if (op[i].op == type && !op[i].group_len) return i; } return 0; @@ -332,7 +342,7 @@ static void op_analyze_transaction(const char *filename, if (words[2]) fail(filename, op_num+1, "Expect no arguments"); - start = op_transaction_start(op, op_num); + start = op_find_start(op, op_num, OP_TDB_TRANSACTION_START); if (!start) fail(filename, op_num+1, "no transaction start found"); @@ -343,11 +353,6 @@ static void op_analyze_transaction(const char *filename, op[i].group_start = start; } -struct traverse_hash { - TDB_DATA key; - unsigned int index; -}; - static void op_analyze_traverse(const char *filename, struct op op[], unsigned int op_num, char *words[]) @@ -364,19 +369,12 @@ static void op_analyze_traverse(const char *filename, } else op[op_num].ret = 0; - for (i = op_num-1; i >= 0; i--) { - if (op[i].op != OP_TDB_TRAVERSE_READ_START - && op[i].op != OP_TDB_TRAVERSE_START) - continue; - if (op[i].group_len) - continue; - break; - } - - if (i < 0) + start = op_find_start(op, op_num, OP_TDB_TRAVERSE_START); + 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"); - start = i; op[start].group_len = op_num - start; for (i = start; i <= op_num; i++) @@ -425,9 +423,10 @@ static void dump_pre(char *filename[], struct op *op[], } /* We simply read/write pointers, since we all are children. */ -static void do_pre(struct tdb_context *tdb, +static bool do_pre(struct tdb_context *tdb, char *filename[], struct op *op[], - unsigned int file, int pre_fd, unsigned int i) + unsigned int file, int pre_fd, unsigned int i, + bool backoff) { while (!list_empty(&op[file][i].pre)) { struct depend *dep; @@ -436,9 +435,17 @@ static void do_pre(struct tdb_context *tdb, printf("%s:%u:waiting for pre\n", filename[file], i+1); fflush(stdout); #endif - alarm(10); + if (backoff) + alarm(2); + else + alarm(10); while (read(pre_fd, &dep, sizeof(dep)) != sizeof(dep)) { if (errno == EINTR) { + if (backoff) { + warnx("%s:%u:avoiding deadlock", + filename[file], i+1); + return false; + } dump_pre(filename, op, file, i); exit(1); } else @@ -455,6 +462,7 @@ static void do_pre(struct tdb_context *tdb, /* This could be any op, not just this one. */ talloc_free(dep); } + return true; } static void do_post(char *filename[], struct op *op[], @@ -484,7 +492,8 @@ static unsigned run_ops(struct tdb_context *tdb, char *filename[], struct op *op[], unsigned int file, - unsigned int start, unsigned int stop); + unsigned int start, unsigned int stop, + bool backoff); struct traverse_info { struct op **op; @@ -502,6 +511,7 @@ static int nontrivial_traverse(struct tdb_context *tdb, { struct traverse_info *tinfo = _tinfo; unsigned int trav_len = tinfo->op[tinfo->file][tinfo->start].group_len; + bool avoid_deadlock = false; if (tinfo->i == tinfo->start + trav_len) { /* This can happen if traverse expects to be empty. */ @@ -515,11 +525,17 @@ static int nontrivial_traverse(struct tdb_context *tdb, fail(tinfo->filename[tinfo->file], tinfo->start + 1, "%s:%u:traverse terminated early"); +#if TRAVERSALS_TAKE_TRANSACTION_LOCK + avoid_deadlock = true; +#endif + /* Run any normal ops. */ tinfo->i = run_ops(tdb, tinfo->pre_fd, tinfo->filename, tinfo->op, - tinfo->file, tinfo->i+1, tinfo->start + trav_len); + tinfo->file, tinfo->i+1, tinfo->start + trav_len, + avoid_deadlock); - if (tinfo->i == tinfo->start + trav_len) + /* We backed off, or we hit OP_TDB_TRAVERSE_END. */ + if (tinfo->op[tinfo->file][tinfo->i].op != OP_TDB_TRAVERSE) return 1; return 0; @@ -548,7 +564,8 @@ static unsigned op_traverse(struct tdb_context *tdb, else tinfo.i = run_ops(tdb, pre_fd, filename, op, file, tinfo.i, - start + op[file][start].group_len); + start + op[file][start].group_len, + false); } return tinfo.i; @@ -564,7 +581,8 @@ unsigned run_ops(struct tdb_context *tdb, char *filename[], struct op *op[], unsigned int file, - unsigned int start, unsigned int stop) + unsigned int start, unsigned int stop, + bool backoff) { unsigned int i; struct sigaction sa; @@ -574,7 +592,8 @@ unsigned run_ops(struct tdb_context *tdb, sigaction(SIGALRM, &sa, NULL); for (i = start; i < stop; i++) { - do_pre(tdb, filename, op, file, pre_fd, i); + if (!do_pre(tdb, filename, op, file, pre_fd, i, backoff)) + return i; switch (op[file][i].op) { case OP_TDB_LOCKALL: @@ -712,7 +731,7 @@ unsigned run_ops(struct tdb_context *tdb, static struct op *maybe_cancel_transaction(const char *filename, struct op *op, unsigned int *num) { - unsigned int start = op_transaction_start(op, *num); + unsigned int start = op_find_start(op, *num, OP_TDB_TRANSACTION_START); if (start) { char *words[] = { "", "tdb_close", NULL }; @@ -873,16 +892,32 @@ static const TDB_DATA *needs(const struct op *op) } -static bool is_transaction(const struct op *op) +static bool starts_transaction(const struct op *op) { return op->op == 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 starts_traverse(const struct op *op) +{ + return op->op == OP_TDB_TRAVERSE_START + || op->op == 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]); +} + /* 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) { - if (is_transaction(op)) { + if (starts_transaction(op)) { unsigned int i; /* Cancelled transactions don't change anything. */ @@ -892,8 +927,7 @@ 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 (op[i].op != OP_TDB_TRAVERSE - && key_eq(op[i].key, *key)) + if (key_eq(op[i].key, *key)) pre = gives(key, pre, &op[i]); } return pre; @@ -915,16 +949,6 @@ static const TDB_DATA *gives(const TDB_DATA *key, const TDB_DATA *pre, return pre; } -static bool in_transaction(const struct op op[], unsigned int i) -{ - return op[i].group_start && is_transaction(&op[op[i].group_start]); -} - -static bool in_traverse(const struct op op[], unsigned int i) -{ - return op[i].group_start && !is_transaction(&op[op[i].group_start]); -} - static struct keyinfo *hash_ops(struct op *op[], unsigned int num_ops[], unsigned int num) { @@ -941,11 +965,6 @@ static struct keyinfo *hash_ops(struct op *op[], unsigned int num_ops[], if (!op[i][j].key.dptr) continue; - /* We don't wait for traverse keys */ - /* FIXME: We should, for trivial traversals. */ - if (op[i][j].op == OP_TDB_TRAVERSE) - continue; - h = hash_key(&op[i][j].key) % (total_keys * 2); while (!key_eq(hash[h].key, op[i][j].key)) { if (!hash[h].key.dptr) { @@ -992,14 +1011,13 @@ static bool satisfies(const TDB_DATA *key, const TDB_DATA *data, { const TDB_DATA *need = NULL; - if (is_transaction(op)) { + if (starts_transaction(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 (op[i].op != OP_TDB_TRAVERSE - && key_eq(op[i].key, *key)) { + if (key_eq(op[i].key, *key)) { need = needs(&op[i]); /* tdb_exists() is special: there might be * something in the transaction with more @@ -1023,18 +1041,13 @@ static bool satisfies(const TDB_DATA *key, const TDB_DATA *data, assert(data != &must_not_exist); assert(data != ¬_exists_or_empty); - /* must_not_exist == must_not_exist, must_exist == must_exist, or - not_exists_or_empty == not_exists_or_empty. */ - if (data->dsize == need->dsize && data->dptr == need->dptr) - return true; - /* Must not exist? data must not exist. */ if (need == &must_not_exist) - return data->dptr == NULL; + return data == &tdb_null; /* Must exist? */ if (need == &must_exist) - return data->dptr != NULL; + return data != &tdb_null; /* Either noexist or empty. */ if (need == ¬_exists_or_empty) @@ -1072,6 +1085,10 @@ static bool sort_deps(char *filename[], struct op *op[], struct op *this_op; bool done[num_files]; + /* None left? We're sorted. */ + if (off == num) + return true; + /* Does this make serial numbers go backwards? Allow a little fuzz. */ if (off > 0) { int serial1 = op[res[off-1].file][res[off-1].op_num].serial; @@ -1086,10 +1103,6 @@ static bool sort_deps(char *filename[], struct op *op[], } } - /* One or none left? We're sorted. */ - if (off + 1 >= num) - return true; - memset(done, 0, sizeof(done)); /* Since ops within a trace file are ordered, we just need to figure @@ -1250,7 +1263,7 @@ static void add_dependency(void *ctx, */ else if (in_traverse(op[needs_file], needs_opnum)) { struct op *need = &op[needs_file][needs_opnum]; - if (op[needs_file][need->group_start].serial < + if (op[needs_file][need->group_start].serial > op[satisfies_file][satisfies_opnum].serial) { needs_opnum = need->group_start; } @@ -1258,7 +1271,7 @@ static void add_dependency(void *ctx, #endif /* If you depend on a transaction, you actually depend on it ending. */ - if (is_transaction(&op[satisfies_file][satisfies_opnum])) { + if (starts_transaction(&op[satisfies_file][satisfies_opnum])) { satisfies_opnum += op[satisfies_file][satisfies_opnum].group_len; #if DEBUG_DEPS @@ -1377,6 +1390,79 @@ static void optimize_dependencies(struct op *op[], unsigned int num_ops[], } } +#if TRAVERSALS_TAKE_TRANSACTION_LOCK +struct traverse_dep { + unsigned int file; + unsigned int op_num; +}; + +/* Force an order among the traversals, so they don't deadlock (as much) */ +static void make_traverse_depends(char *filename[], + struct op *op[], unsigned int num_ops[], + unsigned int num) +{ + unsigned int i, num_traversals = 0; + int j; + struct traverse_dep *dep; + + /* Sort by which one runs first. */ + int compare_traverse_dep(const void *_a, const void *_b) + { + const struct traverse_dep *ta = _a, *tb = _b; + const struct op *a = &op[ta->file][ta->op_num], + *b = &op[tb->file][tb->op_num]; + + if (a->serial != b->serial) + return a->serial - b->serial; + + /* If they have same serial, it means one didn't make any + * changes. Thus sort by end in that case. */ + return a[a->group_len].serial - b[b->group_len].serial; + } + + dep = talloc_array(NULL, struct traverse_dep, 1); + + /* Count them. */ + for (i = 0; i < num; i++) { + for (j = 1; j < num_ops[i]; j++) { + /* Traverse start (ignore those in + * transactions; they're already covered by + * transaction dependencies). */ + if (starts_traverse(&op[i][j]) + && !in_transaction(op[i], j)) { + dep = talloc_realloc(NULL, dep, + struct traverse_dep, + num_traversals+1); + dep[num_traversals].file = i; + dep[num_traversals].op_num = j; + num_traversals++; + } + } + } + qsort(dep, num_traversals, sizeof(dep[0]), compare_traverse_dep); + + for (i = 1; i < num_traversals; i++) { + const struct op *prev = &op[dep[i-1].file][dep[i-1].op_num]; + const struct op *curr = &op[dep[i].file][dep[i].op_num]; + + /* Read traverses don't depend on each other (read lock). */ + if (prev->op == OP_TDB_TRAVERSE_READ_START + && curr->op == OP_TDB_TRAVERSE_READ_START) + continue; + + /* Only make dependency if it's clear. */ + if (compare_traverse_dep(&dep[i], &dep[i-1])) { + /* i depends on end of traverse i-1. */ + add_dependency(NULL, op, filename, + dep[i].file, dep[i].op_num, + dep[i-1].file, dep[i-1].op_num + + prev->group_len); + } + } + talloc_free(dep); +} +#endif + static void derive_dependencies(char *filename[], struct op *op[], unsigned int num_ops[], unsigned int num) @@ -1419,6 +1505,10 @@ static void derive_dependencies(char *filename[], } } +#if TRAVERSALS_TAKE_TRANSACTION_LOCK + make_traverse_depends(filename, op, num_ops, num); +#endif + optimize_dependencies(op, num_ops, num); } @@ -1453,13 +1543,13 @@ int main(int argc, char *argv[]) /* 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], - open_flags[0], 0600, - NULL, hash_key); + 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]); + 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"); @@ -1477,9 +1567,9 @@ int main(int argc, char *argv[]) err(1, "fork failed"); case 0: close(fds[1]); - tdb = tdb_open_ex(argv[1], hashsize[i], tdb_flags[i], - open_flags[i], 0600, - NULL, hash_key); + tdb = tdb_open_ex(argv[1], hashsize[i], + tdb_flags[i]|TDB_NOSYNC, + open_flags[i], 0600, NULL, hash_key); if (!tdb) err(1, "Opening tdb %s", argv[1]); @@ -1487,7 +1577,7 @@ int main(int argc, char *argv[]) if (read(fds[0], &c, 1) != 1) exit(1); run_ops(tdb, pipes[i].fd[0], argv+2, op, i, 1, - num_ops[i]); + num_ops[i], false); check_deps(argv[2+i], op[i], num_ops[i]); exit(0); default: