/* 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
union {
int flag; /* open and store */
- struct traverse *trav; /* traverse start */
struct { /* append */
TDB_DATA pre;
TDB_DATA post;
} append;
- unsigned int transaction_end; /* transaction start */
+ unsigned int group_len; /* transaction/traverse start */
};
};
fail(filename, op_num+1, "Expect no arguments");
op[op_num].key = tdb_null;
- op[op_num].trav = NULL;
+ op[op_num].group_len = 0;
}
static void op_add_transaction(const char *filename, struct op op[],
fail(filename, op_num+1, "Expect no arguments");
op[op_num].key = tdb_null;
- op[op_num].transaction_end = 0;
+ op[op_num].group_len = 0;
}
static void op_analyze_transaction(const char *filename,
fail(filename, op_num+1, "Expect no arguments");
for (i = op_num-1; i >= 0; i--) {
- if (op[i].op == OP_TDB_TRANSACTION_START &&
- !op[i].transaction_end)
+ if (op[i].op == OP_TDB_TRANSACTION_START && !op[i].group_len)
break;
}
fail(filename, op_num+1, "no transaction start found");
start = i;
- op[start].transaction_end = op_num;
+ op[start].group_len = op_num - i;
/* This rolls in nested transactions. I think that's right. */
for (i++; i <= op_num; i++)
unsigned int index;
};
-/* A traverse is a hash of keys, each one associated with ops. */
-struct traverse {
- /* How many traversal callouts should I do? */
- unsigned int num;
-
- /* Where is traversal end op? */
- unsigned int end;
-
- /* For trivial traversals. */
- struct traverse_hash *hash;
-};
-
-/* A trivial traversal is one which doesn't terminate early and only
- * plays with its own record. We can reliably replay these even if
- * traverse order changes. */
-static bool is_trivial_traverse(struct op op[], unsigned int end)
-{
-#if 0
- unsigned int i;
- TDB_DATA cur = tdb_null;
-
- if (op[end].ret != 0)
- return false;
-
- for (i = 0; i < end; i++) {
- if (!op[i].key.dptr)
- continue;
- if (op[i].op == OP_TDB_TRAVERSE)
- cur = op[i].key;
- if (!key_eq(cur, op[i].key))
- return false;
- }
- return true;
-#endif
- /* With multiple things happening at once, no traverse is trivial. */
- return false;
-}
-
static void op_analyze_traverse(const char *filename,
struct op op[], unsigned int op_num,
char *words[])
{
int i, start;
- struct traverse *trav = talloc(op, struct traverse);
op[op_num].key = tdb_null;
} else
op[op_num].ret = 0;
- trav->num = 0;
- trav->end = op_num;
for (i = op_num-1; i >= 0; i--) {
- if (op[i].op == OP_TDB_TRAVERSE)
- trav->num++;
if (op[i].op != OP_TDB_TRAVERSE_READ_START
&& op[i].op != OP_TDB_TRAVERSE_START)
continue;
- if (op[i].trav)
+ if (op[i].group_len)
continue;
break;
}
fail(filename, op_num+1, "no traversal start found");
start = i;
- op[start].trav = trav;
+ op[start].group_len = op_num - start;
for (i = start; i <= op_num; i++)
op[i].group_start = start;
-
- if (is_trivial_traverse(op+i, op_num-i)) {
- /* Fill in a plentiful hash table. */
- op[start].trav->hash = talloc_zero_array(op[i].trav,
- struct traverse_hash,
- trav->num * 2);
- for (i = start; i < op_num; i++) {
- unsigned int h;
- if (op[i].op != OP_TDB_TRAVERSE)
- continue;
- h = hash_key(&op[i].key) % (trav->num * 2);
- while (trav->hash[h].index)
- h = (h + 1) % (trav->num * 2);
- trav->hash[h].index = i+1;
- trav->hash[h].key = op[i].key;
- }
- } else
- trav->hash = NULL;
}
/* Keep -Wmissing-declarations happy: */
#endif
}
-static void dump_pre(char *filename[], unsigned int file,
- struct op op[], unsigned int i)
+static void dump_pre(char *filename[], struct op *op[],
+ unsigned int file, unsigned int i)
{
struct depend *dep;
- printf("%s:%u still waiting for:\n", filename[file], i+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);
+ printf("%s:%u (%u) still waiting for:\n", filename[file], i+1,
+ op[file][i].serial);
+ list_for_each(&op[file][i].pre, dep, pre_list)
+ printf(" %s:%u (%u)\n",
+ filename[dep->satisfies_file], dep->satisfies_opnum+1,
+ op[dep->satisfies_file][dep->satisfies_opnum].serial);
+ check_deps(filename[file], op[file], 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)
+static void do_pre(struct tdb_context *tdb,
+ char *filename[], struct op *op[],
+ unsigned int file, int pre_fd, unsigned int i)
{
- while (!list_empty(&op[i].pre)) {
+ while (!list_empty(&op[file][i].pre)) {
struct depend *dep;
#if DEBUG_DEPS
alarm(10);
while (read(pre_fd, &dep, sizeof(dep)) != sizeof(dep)) {
if (errno == EINTR) {
- dump_pre(filename, file, op, i);
+ dump_pre(filename, op, file, i);
exit(1);
} else
errx(1, "Reading from pipe");
#if DEBUG_DEPS
printf("%s:%u:got pre %u from %s:%u\n", filename[file], i+1,
- dep->needs_op, dep->satisfies_file, dep->satisfies_op+1);
+ dep->needs_opnum+1, filename[dep->satisfies_file],
+ dep->satisfies_opnum+1);
fflush(stdout);
#endif
/* This could be any op, not just this one. */
}
}
-static void do_post(char *filename[], unsigned int file,
- const struct op op[], unsigned int i)
+static void do_post(char *filename[], struct op *op[],
+ unsigned int file, unsigned int i)
{
struct depend *dep;
- list_for_each(&op[i].post, dep, post_list) {
+ list_for_each(&op[file][i].post, dep, post_list) {
#if DEBUG_DEPS
printf("%s:%u:sending to file %s:%u\n", filename[file], i+1,
filename[dep->needs_file], dep->needs_opnum+1);
static unsigned run_ops(struct tdb_context *tdb,
int pre_fd,
char *filename[],
+ struct op *op[],
unsigned int file,
- struct op op[],
unsigned int start, unsigned int stop);
struct traverse_info {
- struct op *op;
+ struct op **op;
char **filename;
unsigned file;
int pre_fd;
unsigned int i;
};
-/* Trivial case: do whatever they did for this key. */
-static int trivial_traverse(struct tdb_context *tdb,
- TDB_DATA key, TDB_DATA data,
- void *_tinfo)
-{
- struct traverse_info *tinfo = _tinfo;
- struct traverse *trav = tinfo->op[tinfo->start].trav;
- unsigned int h = hash_key(&key) % (trav->num * 2);
-
- while (trav->hash[h].index) {
- if (key_eq(trav->hash[h].key, key)) {
- run_ops(tdb, tinfo->pre_fd, tinfo->filename,
- tinfo->file, tinfo->op, trav->hash[h].index,
- trav->end);
- tinfo->i++;
- return 0;
- }
- h = (h + 1) % (trav->num * 2);
- }
- fail(tinfo->filename[tinfo->file], tinfo->start + 1,
- "unexpected traverse key");
-}
-
/* More complex. Just do whatever's they did at the n'th entry. */
static int nontrivial_traverse(struct tdb_context *tdb,
TDB_DATA key, TDB_DATA data,
void *_tinfo)
{
struct traverse_info *tinfo = _tinfo;
- struct traverse *trav = tinfo->op[tinfo->start].trav;
+ unsigned int trav_len = tinfo->op[tinfo->file][tinfo->start].group_len;
- if (tinfo->i == trav->end) {
+ if (tinfo->i == tinfo->start + trav_len) {
/* This can happen if traverse expects to be empty. */
- if (tinfo->start + 1 == trav->end)
+ if (trav_len == 1)
return 1;
fail(tinfo->filename[tinfo->file], tinfo->start + 1,
"traverse did not terminate");
}
- if (tinfo->op[tinfo->i].op != OP_TDB_TRAVERSE)
+ if (tinfo->op[tinfo->file][tinfo->i].op != OP_TDB_TRAVERSE)
fail(tinfo->filename[tinfo->file], tinfo->start + 1,
"%s:%u:traverse terminated early");
/* Run any normal ops. */
- tinfo->i = run_ops(tdb, tinfo->pre_fd, tinfo->filename, tinfo->file,
- tinfo->op, tinfo->i+1, trav->end);
+ tinfo->i = run_ops(tdb, tinfo->pre_fd, tinfo->filename, tinfo->op,
+ tinfo->file, tinfo->i+1, tinfo->start + trav_len);
- if (tinfo->i == trav->end)
+ if (tinfo->i == tinfo->start + trav_len)
return 1;
return 0;
unsigned int file,
int (*traversefn)(struct tdb_context *,
tdb_traverse_func, void *),
- struct op op[],
+ struct op *op[],
unsigned int start)
{
- struct traverse *trav = op[start].trav;
struct traverse_info tinfo = { op, filename, file, pre_fd,
start, start+1 };
- /* Trivial case. */
- if (trav->hash) {
- int ret = traversefn(tdb, trivial_traverse, &tinfo);
- if (ret != trav->num)
- fail(filename[file], start+1,
- "short traversal %i", ret);
- return trav->end;
- }
-
traversefn(tdb, nontrivial_traverse, &tinfo);
/* Traversing in wrong order can have strange effects: eg. if
* 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 != trav->end) {
- if (op[tinfo.i].op == OP_TDB_TRAVERSE)
+ while (tinfo.i != start + op[file][start].group_len) {
+ if (op[file][tinfo.i].op == OP_TDB_TRAVERSE)
tinfo.i++;
else
- tinfo.i = run_ops(tdb, pre_fd, filename, file, op,
- tinfo.i, trav->end);
+ tinfo.i = run_ops(tdb, pre_fd, filename, op, file,
+ tinfo.i,
+ start + op[file][start].group_len);
}
- return trav->end;
+ return tinfo.i;
}
static void break_out(int sig)
unsigned run_ops(struct tdb_context *tdb,
int pre_fd,
char *filename[],
+ struct op *op[],
unsigned int file,
- struct op op[], unsigned int start, unsigned int stop)
+ unsigned int start, unsigned int stop)
{
unsigned int i;
struct sigaction sa;
sigaction(SIGALRM, &sa, NULL);
for (i = start; i < stop; i++) {
- do_pre(filename, file, pre_fd, op, i);
+ do_pre(tdb, filename, op, file, pre_fd, i);
- switch (op[i].op) {
+ switch (op[file][i].op) {
case OP_TDB_LOCKALL:
- try(tdb_lockall(tdb), op[i].ret);
+ try(tdb_lockall(tdb), op[file][i].ret);
break;
case OP_TDB_LOCKALL_MARK:
- try(tdb_lockall_mark(tdb), op[i].ret);
+ try(tdb_lockall_mark(tdb), op[file][i].ret);
break;
case OP_TDB_LOCKALL_UNMARK:
- try(tdb_lockall_unmark(tdb), op[i].ret);
+ try(tdb_lockall_unmark(tdb), op[file][i].ret);
break;
case OP_TDB_LOCKALL_NONBLOCK:
- unreliable(tdb_lockall_nonblock(tdb), op[i].ret,
+ unreliable(tdb_lockall_nonblock(tdb), op[file][i].ret,
tdb_lockall(tdb), tdb_unlockall(tdb));
break;
case OP_TDB_UNLOCKALL:
- try(tdb_unlockall(tdb), op[i].ret);
+ try(tdb_unlockall(tdb), op[file][i].ret);
break;
case OP_TDB_LOCKALL_READ:
- try(tdb_lockall_read(tdb), op[i].ret);
+ try(tdb_lockall_read(tdb), op[file][i].ret);
break;
case OP_TDB_LOCKALL_READ_NONBLOCK:
- unreliable(tdb_lockall_read_nonblock(tdb), op[i].ret,
+ unreliable(tdb_lockall_read_nonblock(tdb),
+ op[file][i].ret,
tdb_lockall_read(tdb),
tdb_unlockall_read(tdb));
break;
case OP_TDB_UNLOCKALL_READ:
- try(tdb_unlockall_read(tdb), op[i].ret);
+ try(tdb_unlockall_read(tdb), op[file][i].ret);
break;
case OP_TDB_CHAINLOCK:
- try(tdb_chainlock(tdb, op[i].key), op[i].ret);
+ try(tdb_chainlock(tdb, op[file][i].key),
+ op[file][i].ret);
break;
case OP_TDB_CHAINLOCK_NONBLOCK:
- unreliable(tdb_chainlock_nonblock(tdb, op[i].key),
- op[i].ret,
- tdb_chainlock(tdb, op[i].key),
- tdb_chainunlock(tdb, op[i].key));
+ unreliable(tdb_chainlock_nonblock(tdb, op[file][i].key),
+ op[file][i].ret,
+ tdb_chainlock(tdb, op[file][i].key),
+ tdb_chainunlock(tdb, op[file][i].key));
break;
case OP_TDB_CHAINLOCK_MARK:
- try(tdb_chainlock_mark(tdb, op[i].key), op[i].ret);
+ try(tdb_chainlock_mark(tdb, op[file][i].key),
+ op[file][i].ret);
break;
case OP_TDB_CHAINLOCK_UNMARK:
- try(tdb_chainlock_unmark(tdb, op[i].key), op[i].ret);
+ try(tdb_chainlock_unmark(tdb, op[file][i].key),
+ op[file][i].ret);
break;
case OP_TDB_CHAINUNLOCK:
- try(tdb_chainunlock(tdb, op[i].key), op[i].ret);
+ try(tdb_chainunlock(tdb, op[file][i].key),
+ op[file][i].ret);
break;
case OP_TDB_CHAINLOCK_READ:
- try(tdb_chainlock_read(tdb, op[i].key), op[i].ret);
+ try(tdb_chainlock_read(tdb, op[file][i].key),
+ op[file][i].ret);
break;
case OP_TDB_CHAINUNLOCK_READ:
- try(tdb_chainunlock_read(tdb, op[i].key), op[i].ret);
+ try(tdb_chainunlock_read(tdb, op[file][i].key),
+ op[file][i].ret);
break;
case OP_TDB_PARSE_RECORD:
- try(tdb_parse_record(tdb, op[i].key, get_len, NULL),
- op[i].ret);
+ try(tdb_parse_record(tdb, op[file][i].key, get_len,
+ NULL),
+ op[file][i].ret);
break;
case OP_TDB_EXISTS:
- try(tdb_exists(tdb, op[i].key), op[i].ret);
+ try(tdb_exists(tdb, op[file][i].key), op[file][i].ret);
break;
case OP_TDB_STORE:
- try(tdb_store(tdb, op[i].key, op[i].data, op[i].flag),
- op[i].ret);
+ try(tdb_store(tdb, op[file][i].key, op[file][i].data,
+ op[file][i].flag),
+ op[file][i].ret);
break;
case OP_TDB_APPEND:
- try(tdb_append(tdb, op[i].key, op[i].data), op[i].ret);
+ try(tdb_append(tdb, op[file][i].key, op[file][i].data),
+ op[file][i].ret);
break;
case OP_TDB_GET_SEQNUM:
- try(tdb_get_seqnum(tdb), op[i].ret);
+ try(tdb_get_seqnum(tdb), op[file][i].ret);
break;
case OP_TDB_WIPE_ALL:
- try(tdb_wipe_all(tdb), op[i].ret);
+ try(tdb_wipe_all(tdb), op[file][i].ret);
break;
case OP_TDB_TRANSACTION_START:
- try(tdb_transaction_start(tdb), op[i].ret);
+ try(tdb_transaction_start(tdb), op[file][i].ret);
break;
case OP_TDB_TRANSACTION_CANCEL:
- try(tdb_transaction_cancel(tdb), op[i].ret);
+ try(tdb_transaction_cancel(tdb), op[file][i].ret);
break;
case OP_TDB_TRANSACTION_COMMIT:
- try(tdb_transaction_commit(tdb), op[i].ret);
+ try(tdb_transaction_commit(tdb), op[file][i].ret);
break;
case OP_TDB_TRAVERSE_READ_START:
i = op_traverse(tdb, pre_fd, filename, file,
* done our ops. */
return i;
case OP_TDB_TRAVERSE_END:
- fail(filename[file], i+1, "unepxected end traverse");
+ fail(filename[file], i+1, "unexpected end traverse");
/* FIXME: These must be treated like traverse. */
case OP_TDB_FIRSTKEY:
- if (!key_eq(tdb_firstkey(tdb), op[i].data))
+ if (!key_eq(tdb_firstkey(tdb), op[file][i].data))
fail(filename[file], i+1, "bad firstkey");
break;
case OP_TDB_NEXTKEY:
- if (!key_eq(tdb_nextkey(tdb, op[i].key), op[i].data))
+ if (!key_eq(tdb_nextkey(tdb, op[file][i].key),
+ op[file][i].data))
fail(filename[file], i+1, "bad nextkey");
break;
case OP_TDB_FETCH: {
- TDB_DATA f = tdb_fetch(tdb, op[i].key);
- if (!key_eq(f, op[i].data))
+ TDB_DATA f = tdb_fetch(tdb, op[file][i].key);
+ if (!key_eq(f, op[file][i].data))
fail(filename[file], i+1, "bad fetch %u",
f.dsize);
break;
}
case OP_TDB_DELETE:
- try(tdb_delete(tdb, op[i].key), op[i].ret);
+ try(tdb_delete(tdb, op[file][i].key), op[file][i].ret);
break;
}
- do_post(filename, file, op, i);
+ do_post(filename, op, file, i);
}
return i;
}
if (sat_start) {
if (op[satisfies_file][sat_start].op
== OP_TDB_TRANSACTION_START) {
- satisfies_opnum
- = op[satisfies_file][sat_start].transaction_end;
+ satisfies_opnum = sat_start
+ + op[satisfies_file][sat_start].group_len;
#ifdef DEBUG_DEPS
printf(" -> Depends on %u\n", satisfies_opnum+1);
fflush(stdout);
}
}
+ assert(op[needs_file][needs_opnum].op != OP_TDB_TRAVERSE);
+ assert(op[satisfies_file][satisfies_opnum].op != OP_TDB_TRAVERSE);
+
dep = talloc(ctx, struct depend);
dep->needs_file = needs_file;
dep->needs_opnum = needs_opnum;
struct traverse_dep {
unsigned int file;
unsigned int op_num;
- const struct op *op;
};
-/* Sort by which one runs first. */
-static int compare_traverse_dep(const void *_a, const void *_b)
-{
- const struct traverse_dep *a = _a, *b = _b;
- const struct traverse *trava = a->op->trav, *travb = b->op->trav;
-
- if (a->op->serial != b->op->serial)
- return a->op->serial - b->op->serial;
-
- /* If they have same serial, it means one didn't make any changes.
- * Thus sort by end in that case. */
- return a->op[trava->end - a->op_num].serial
- - b->op[travb->end - b->op_num].serial;
-}
-
-/* Traversals can deadlock against each other. Force order. */
+/* Traversals can deadlock against each other, and transactions. Force
+ * order. */
static void make_traverse_depends(char *filename[],
struct op *op[], unsigned int num_ops[],
unsigned int num)
unsigned int i, j, num_traversals = 0;
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 = 0; j < num_ops[i]; j++) {
- if (op[i][j].op == OP_TDB_TRAVERSE_START
- || op[i][j].op == OP_TDB_TRAVERSE_READ_START) {
+ for (j = 1; j < num_ops[i]; j++) {
+ /* Transaction or traverse start. */
+ if (op[i][j].group_start == j) {
dep = talloc_realloc(NULL, dep,
struct traverse_dep,
num_traversals+1);
dep[num_traversals].file = i;
dep[num_traversals].op_num = j;
- dep[num_traversals].op = &op[i][j];
num_traversals++;
}
}
for (i = 1; i < num_traversals; i++) {
/* 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->trav->end);
+ dep[i-1].file, dep[i-1].op_num
+ + op[dep[i-1].file][dep[i-1].op_num].group_len);
}
talloc_free(dep);
}
continue;
}
if (prev[dep->satisfies_file]->satisfies_opnum
- > dep->satisfies_opnum) {
+ < dep->satisfies_opnum) {
talloc_free(prev[dep->satisfies_file]);
prev[dep->satisfies_file] = dep;
} else
printf("Single threaded run...");
fflush(stdout);
- run_ops(tdb, pipes[0].fd[0], argv+2, 0, op[0], 1, num_ops[0]);
+ run_ops(tdb, pipes[0].fd[0], argv+2, op, 0, 1, num_ops[0]);
check_deps(argv[2], op[0], num_ops[0]);
printf("done\n");
/* This catches parent exiting. */
if (read(fds[0], &c, 1) != 1)
exit(1);
- run_ops(tdb, pipes[i].fd[0], argv+2, i, op[i], 1,
+ run_ops(tdb, pipes[i].fd[0], argv+2, op, i, 1,
num_ops[i]);
check_deps(argv[2+i], op[i], num_ops[i]);
exit(0);