From fadb7502774b18a0621446eb177b0e5cf2af2276 Mon Sep 17 00:00:00 2001
From: Rusty Russell <rusty@rustcorp.com.au>
Date: Thu, 16 Jul 2009 12:56:07 +0930
Subject: [PATCH 1/1] Partial ordering of traverses: reduces number of
 deadlocks by factor of 10.

---
 ccan/tdb/tools/replay_trace.c | 79 ++++++++++++++++++++++++++++++++++-
 1 file changed, 78 insertions(+), 1 deletion(-)

diff --git a/ccan/tdb/tools/replay_trace.c b/ccan/tdb/tools/replay_trace.c
index 652af3a4..0968dedd 100644
--- a/ccan/tdb/tools/replay_trace.c
+++ b/ccan/tdb/tools/replay_trace.c
@@ -941,9 +941,15 @@ 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 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[],
@@ -1393,6 +1399,73 @@ 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 (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)
@@ -1435,6 +1508,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);
 }
 
-- 
2.39.2