Re: combinatorial explosion in lockdep

[David Miller <davem@davemloft.net>]

From: David Miller <davem@davemloft.net>
Date: Mon, 28 Jul 2008 15:37:02 -0700 (PDT)

> I'm still digging on what exactly makes this happen, but I wanted to
> get the information out as soon as I had something useful like this.

As a simple hack, I tried mitigating these effects using a
generation-count based "visited" scheme to bypass traversing
lock_class chains we've already walked down.

It seems to work.

But I wonder if the real problem is that there is some unintended
loop in the chains, or something like that.

Anyways, just some more info...

diff --git a/include/linux/lockdep.h b/include/linux/lockdep.h
index 2486eb4..1bfdc30 100644
--- a/include/linux/lockdep.h
+++ b/include/linux/lockdep.h
@@ -89,6 +89,7 @@ struct lock_class {
 
 	struct lockdep_subclass_key	*key;
 	unsigned int			subclass;
+	unsigned int			dep_gen_id;
 
 	/*
 	 * IRQ/softirq usage tracking bits:
diff --git a/kernel/lockdep.c b/kernel/lockdep.c
index d38a643..59218a0 100644
--- a/kernel/lockdep.c
+++ b/kernel/lockdep.c
@@ -959,6 +959,18 @@ static int noinline print_infinite_recursion_bug(void)
 	return 0;
 }
 
+static unsigned int dependency_gen_id;
+
+static bool dependency_visit(struct lock_class *source, unsigned int depth)
+{
+	if (!depth)
+		dependency_gen_id++;
+	if (source->dep_gen_id == dependency_gen_id)
+		return true;
+	source->dep_gen_id = dependency_gen_id;
+	return false;
+}
+
 /*
  * Prove that the dependency graph starting at <entry> can not
  * lead to <target>. Print an error and return 0 if it does.
@@ -968,6 +980,9 @@ check_noncircular(struct lock_class *source, unsigned int depth)
 {
 	struct lock_list *entry;
 
+	if (dependency_visit(source, depth))
+		return 1;
+
 	debug_atomic_inc(&nr_cyclic_check_recursions);
 	if (depth > max_recursion_depth)
 		max_recursion_depth = depth;
@@ -1011,6 +1026,9 @@ find_usage_forwards(struct lock_class *source, unsigned int depth)
 	struct lock_list *entry;
 	int ret;
 
+	if (dependency_visit(source, depth))
+		return 1;
+
 	if (depth > max_recursion_depth)
 		max_recursion_depth = depth;
 	if (depth >= RECURSION_LIMIT)
@@ -1050,6 +1068,9 @@ find_usage_backwards(struct lock_class *source, unsigned int depth)
 	struct lock_list *entry;
 	int ret;
 
+	if (dependency_visit(source, depth))
+		return 1;
+
 	if (!__raw_spin_is_locked(&lockdep_lock))
 		return DEBUG_LOCKS_WARN_ON(1);