/* 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
TDB_DATA pre;
TDB_DATA post;
} append;
- unsigned int group_len; /* transaction/traverse start */
+ /* transaction/traverse start/chainlock */
+ unsigned int group_len;
};
};
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,
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 <key> = <data>");
+ op[op_num].key = tdb_null;
+}
+
/* <serial> tdb_store <rec> <rec> <flag> = <ret> */
static void op_add_store(const char *filename,
struct op op[], unsigned int op_num, char *words[])
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");
op[op_num].group_len = 0;
}
-static int op_transaction_start(struct op op[], unsigned int op_num)
+static void op_add_chainlock(const char *filename,
+ struct op op[], unsigned int op_num, char *words[])
+{
+ if (words[2] == NULL || words[3])
+ fail(filename, 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].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[])
+{
+ if (!words[2] || !words[3] || !words[4] || words[5]
+ || !streq(words[3], "="))
+ fail(filename, op_num+1, "Expected <key> = <ret>");
+ op[op_num].ret = atoi(words[4]);
+ op[op_num].data = make_tdb_data(op, filename, op_num+1, words[2]);
+ op[op_num].key = tdb_null;
+ op[op_num].group_len = 0;
+ total_keys++;
+}
+
+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;
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");
op[i].group_start = start;
}
-struct traverse_hash {
- TDB_DATA key;
- unsigned int index;
-};
+/* 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[])
+{
+ unsigned int i, start;
+
+ if (words[2] == NULL || words[3])
+ fail(filename, op_num+1, "Expected just a key");
+
+ op[op_num].data = make_tdb_data(op, filename, op_num+1, words[2]);
+ op[op_num].key = tdb_null;
+ total_keys++;
+
+ start = op_find_start(op, op_num, OP_TDB_CHAINLOCK);
+ if (!start)
+ start = op_find_start(op, op_num, OP_TDB_CHAINLOCK_READ);
+ if (!start)
+ fail(filename, 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?");
+
+ 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,
} 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;
+ /* Don't roll in nested traverse/chainlock */
for (i = start; i <= op_num; i++)
- op[i].group_start = start;
+ if (!op[i].group_start)
+ op[i].group_start = start;
}
/* Keep -Wmissing-declarations happy: */
}
/* 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;
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
/* This could be any op, not just this one. */
talloc_free(dep);
}
+ return true;
}
static void do_post(char *filename[], struct op *op[],
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;
{
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. */
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;
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;
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;
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:
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[] = { "<unknown>", "tdb_close", NULL };
}
-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]);
+}
+
+static bool starts_chainlock(const struct op *op)
+{
+ return op->op == OP_TDB_CHAINLOCK_READ || op->op == 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)
{
- if (is_transaction(op)) {
+ if (starts_transaction(op) || starts_chainlock(op)) {
unsigned int i;
/* Cancelled transactions don't change anything. */
if (op[op->group_len].op == OP_TDB_TRANSACTION_CANCEL)
return pre;
- assert(op[op->group_len].op == OP_TDB_TRANSACTION_COMMIT);
+ assert(op[op->group_len].op == OP_TDB_TRANSACTION_COMMIT
+ || op[op->group_len].op == OP_TDB_CHAINUNLOCK_READ
+ || op[op->group_len].op == OP_TDB_CHAINUNLOCK);
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;
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)
{
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) {
/* If it's in a transaction, it's the transaction which
* matters from an analysis POV. */
- if (in_transaction(op[i], j)) {
+ if (in_transaction(op[i], j)
+ || in_chainlock(op[i], j)) {
unsigned start = op[i][j].group_start;
/* Don't include twice. */
{
const TDB_DATA *need = NULL;
- if (is_transaction(op)) {
+ 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 (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
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;
}
}
- /* 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
* traverse/transaction, it creates a dependency between the
* two groups. */
if ((in_traverse(op[satisfies_file], satisfies_opnum)
- && op[needs_file][needs_opnum].group_start)
+ && (starts_transaction(&op[needs_file][needs_opnum])
+ || starts_traverse(&op[needs_file][needs_opnum])))
|| (in_traverse(op[needs_file], needs_opnum)
- && op[satisfies_file][satisfies_opnum].group_start)) {
+ && (starts_transaction(&op[satisfies_file][satisfies_opnum])
+ || starts_traverse(&op[satisfies_file][satisfies_opnum])))){
unsigned int sat;
/* We are satisfied by end of group. */
}
#endif
- /* If you depend on a transaction, you actually depend on it ending. */
- if (is_transaction(&op[satisfies_file][satisfies_opnum])) {
+ /* If you depend on a transaction or chainlock, you actually
+ * depend on it ending. */
+ if (starts_transaction(&op[satisfies_file][satisfies_opnum])
+ || starts_chainlock(&op[satisfies_file][satisfies_opnum])) {
satisfies_opnum
+= op[satisfies_file][satisfies_opnum].group_len;
#if DEBUG_DEPS
}
}
+#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)
}
}
+#if TRAVERSALS_TAKE_TRANSACTION_LOCK
+ make_traverse_depends(filename, op, num_ops, num);
+#endif
+
optimize_dependencies(op, num_ops, num);
}
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");
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:
projects / ccan / blobdiff