/* 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
}
/* 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:
return op[i].group_start && is_transaction(&op[op[i].group_start]);
}
+static bool is_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 && !is_transaction(&op[op[i].group_start]);
+ return op[i].group_start && is_traverse(&op[op[i].group_start]);
}
static struct keyinfo *hash_ops(struct op *op[], unsigned int num_ops[],
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
}
}
+#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 (is_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];
+
+ /* 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