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 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;
-};
-
static void op_analyze_traverse(const char *filename,
struct op op[], unsigned int op_num,
char *words[])
} 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++)
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]);
+}
+
/* 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. */
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) {
{
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
#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
}
}
+#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);
}
projects / ccan / blobdiff