Re: combinatorial explosion in lockdep

[Peter Zijlstra <peterz@infradead.org>]

On Tue, 2008-07-29 at 21:45 -0700, David Miller wrote:
> From: David Miller <davem@davemloft.net>
> Date: Mon, 28 Jul 2008 17:44:15 -0700 (PDT)
> 
> > From: Ingo Molnar <mingo@elte.hu>
> > Date: Tue, 29 Jul 2008 01:51:33 +0200
> > 
> > > Any chance to get the "cat /proc/lockdep*" output, so that we could see 
> > > and check the expected behavior of the full graph?
> > 
> > /proc/lockdep loops forever in count_forward_deps() :-)
> > 
> > I was able to capture a copy of lockdep_chains:
> > 
> > http://vger.kernel.org/~davem/lockdep_chains.bz2
> 
> As a followup I dumped the full backwards search graph once the cost
> got up to about (1 * 1024 * 1024) checks or so.
> 
> I didn't find any loops, but it is clear that the cost is huge because
> of the runqueue lock double-locking, without the generation count
> patch I posted the other day.
> 
> For example, if you start with the first runqueue lock you search one
> entry:
> 
> 	1
> 
> Next, if you start with the second runqueue lock you search two
> entries:
> 
> 	2, 1
> 
> Next, if you start with the third runqueue lock you search
> 4 entries:
> 
> 	3, 2, 1, 1
> 
> And the next series is:
> 
> 	4, 3, 2, 1, 1, 2, 1, 1
> 
> and so on and so forth.  So the cost of a full backwards graph
> traversal for N cpus is on the order of "1 << (N - 1)".  So with just
> 32 cpus the cost is on the order of a few billions of checks.
> 
> And then you have to factor in all of those runqueue locks's backwards
> graphs that don't involve other runqueue locks (on my machine each
> such sub-graph is about 200 locks deep).
> 
> Here is an updated version of my patch to solve this problem.  The only
> unnice bit is that I had to move the procfs dep counting code into
> lockdep.c and run it under the lockdep_lock.  This is the only way to
> safely employ the dependency generation ID marking algorithm the
> short-circuiting uses.
> 
> If we can agree on this as a fix, it should definitely be backported
> and submitted for -stable :-)

Agreed adding the stable team to the CC

> ----------------------------------------
> 
> lockdep: Fix combinatorial explosion in lock subgraph traversal.
> 
> When we traverse the graph, either forwards or backwards, we
> are interested in whether a certain property exists somewhere
> in a node reachable in the graph.
> 
> Therefore it is never necessary to traverse through a node more
> than once to get a correct answer to the given query.
> 
> Take advantage of this property using a global ID counter so that we
> need not clear all the markers in all the lock_class entries before
> doing a traversal.  A new ID is choosen when we start to traverse, and
> we continue through a lock_class only if it's ID hasn't been marked
> with the new value yet.
> 
> This short-circuiting is essential especially for high CPU count
> systems.  The scheduler has a runqueue per cpu, and needs to take
> two runqueue locks at a time, which leads to long chains of
> backwards and forwards subgraphs from these runqueue lock nodes.
> Without the short-circuit implemented here, a graph traversal on
> a runqueue lock can take up to (1 << (N - 1)) checks on a system
> with N cpus.
> 
> For anything more than 16 cpus or so, lockdep will eventually bring
> the machine to a complete standstill.
> 
> Signed-off-by: David S. Miller <davem@davemloft.net>

Acked-by: Peter Zijlstra <a.p.zijlstra@chello.nl>

> 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..6999e64 100644
> --- a/kernel/lockdep.c
> +++ b/kernel/lockdep.c
> @@ -372,6 +372,19 @@ unsigned int nr_process_chains;
>  unsigned int max_lockdep_depth;
>  unsigned int max_recursion_depth;
>  
> +static unsigned int lockdep_dependency_gen_id;
> +
> +static bool lockdep_dependency_visit(struct lock_class *source,
> +				     unsigned int depth)
> +{
> +	if (!depth)
> +		lockdep_dependency_gen_id++;
> +	if (source->dep_gen_id == lockdep_dependency_gen_id)
> +		return true;
> +	source->dep_gen_id = lockdep_dependency_gen_id;
> +	return false;
> +}
> +
>  #ifdef CONFIG_DEBUG_LOCKDEP
>  /*
>   * We cannot printk in early bootup code. Not even early_printk()
> @@ -558,6 +571,9 @@ static void print_lock_dependencies(struct lock_class *class, int depth)
>  {
>  	struct lock_list *entry;
>  
> +	if (lockdep_dependency_visit(class, depth))
> +		return;
> +
>  	if (DEBUG_LOCKS_WARN_ON(depth >= 20))
>  		return;
>  
> @@ -959,6 +975,67 @@ static int noinline print_infinite_recursion_bug(void)
>  	return 0;
>  }
>  
> +unsigned long __lockdep_count_forward_deps(struct lock_class *class,
> +					   unsigned int depth)
> +{
> +	struct lock_list *entry;
> +	unsigned long ret = 1;
> +
> +	if (lockdep_dependency_visit(class, depth))
> +		return 0;
> +
> +	/*
> +	 * Recurse this class's dependency list:
> +	 */
> +	list_for_each_entry(entry, &class->locks_after, entry)
> +		ret += __lockdep_count_forward_deps(entry->class, depth + 1);
> +
> +	return ret;
> +}
> +
> +unsigned long lockdep_count_forward_deps(struct lock_class *class)
> +{
> +	unsigned long ret, flags;
> +
> +	local_irq_save(flags);
> +	__raw_spin_lock(&lockdep_lock);
> +	ret = __lockdep_count_forward_deps(class, 0);
> +	__raw_spin_unlock(&lockdep_lock);
> +	local_irq_restore(flags);
> +
> +	return ret;
> +}
> +
> +unsigned long __lockdep_count_backward_deps(struct lock_class *class,
> +					    unsigned int depth)
> +{
> +	struct lock_list *entry;
> +	unsigned long ret = 1;
> +
> +	if (lockdep_dependency_visit(class, depth))
> +		return 0;
> +	/*
> +	 * Recurse this class's dependency list:
> +	 */
> +	list_for_each_entry(entry, &class->locks_before, entry)
> +		ret += __lockdep_count_backward_deps(entry->class, depth + 1);
> +
> +	return ret;
> +}
> +
> +unsigned long lockdep_count_backward_deps(struct lock_class *class)
> +{
> +	unsigned long ret, flags;
> +
> +	local_irq_save(flags);
> +	__raw_spin_lock(&lockdep_lock);
> +	ret = __lockdep_count_backward_deps(class, 0);
> +	__raw_spin_unlock(&lockdep_lock);
> +	local_irq_restore(flags);
> +
> +	return ret;
> +}
> +
>  /*
>   * Prove that the dependency graph starting at <entry> can not
>   * lead to <target>. Print an error and return 0 if it does.
> @@ -968,6 +1045,9 @@ check_noncircular(struct lock_class *source, unsigned int depth)
>  {
>  	struct lock_list *entry;
>  
> +	if (lockdep_dependency_visit(source, depth))
> +		return 1;
> +
>  	debug_atomic_inc(&nr_cyclic_check_recursions);
>  	if (depth > max_recursion_depth)
>  		max_recursion_depth = depth;
> @@ -1011,6 +1091,9 @@ find_usage_forwards(struct lock_class *source, unsigned int depth)
>  	struct lock_list *entry;
>  	int ret;
>  
> +	if (lockdep_dependency_visit(source, depth))
> +		return 1;
> +
>  	if (depth > max_recursion_depth)
>  		max_recursion_depth = depth;
>  	if (depth >= RECURSION_LIMIT)
> @@ -1050,6 +1133,9 @@ find_usage_backwards(struct lock_class *source, unsigned int depth)
>  	struct lock_list *entry;
>  	int ret;
>  
> +	if (lockdep_dependency_visit(source, depth))
> +		return 1;
> +
>  	if (!__raw_spin_is_locked(&lockdep_lock))
>  		return DEBUG_LOCKS_WARN_ON(1);
>  
> diff --git a/kernel/lockdep_internals.h b/kernel/lockdep_internals.h
> index c3600a0..68d44ec 100644
> --- a/kernel/lockdep_internals.h
> +++ b/kernel/lockdep_internals.h
> @@ -53,6 +53,9 @@ extern unsigned int nr_process_chains;
>  extern unsigned int max_lockdep_depth;
>  extern unsigned int max_recursion_depth;
>  
> +extern unsigned long lockdep_count_forward_deps(struct lock_class *);
> +extern unsigned long lockdep_count_backward_deps(struct lock_class *);
> +
>  #ifdef CONFIG_DEBUG_LOCKDEP
>  /*
>   * Various lockdep statistics:
> diff --git a/kernel/lockdep_proc.c b/kernel/lockdep_proc.c
> index 9b0e940..6252ff7 100644
> --- a/kernel/lockdep_proc.c
> +++ b/kernel/lockdep_proc.c
> @@ -63,34 +63,6 @@ static void l_stop(struct seq_file *m, void *v)
>  {
>  }
>  
> -static unsigned long count_forward_deps(struct lock_class *class)
> -{
> -	struct lock_list *entry;
> -	unsigned long ret = 1;
> -
> -	/*
> -	 * Recurse this class's dependency list:
> -	 */
> -	list_for_each_entry(entry, &class->locks_after, entry)
> -		ret += count_forward_deps(entry->class);
> -
> -	return ret;
> -}
> -
> -static unsigned long count_backward_deps(struct lock_class *class)
> -{
> -	struct lock_list *entry;
> -	unsigned long ret = 1;
> -
> -	/*
> -	 * Recurse this class's dependency list:
> -	 */
> -	list_for_each_entry(entry, &class->locks_before, entry)
> -		ret += count_backward_deps(entry->class);
> -
> -	return ret;
> -}
> -
>  static void print_name(struct seq_file *m, struct lock_class *class)
>  {
>  	char str[128];
> @@ -124,10 +96,10 @@ static int l_show(struct seq_file *m, void *v)
>  #ifdef CONFIG_DEBUG_LOCKDEP
>  	seq_printf(m, " OPS:%8ld", class->ops);
>  #endif
> -	nr_forward_deps = count_forward_deps(class);
> +	nr_forward_deps = lockdep_count_forward_deps(class);
>  	seq_printf(m, " FD:%5ld", nr_forward_deps);
>  
> -	nr_backward_deps = count_backward_deps(class);
> +	nr_backward_deps = lockdep_count_backward_deps(class);
>  	seq_printf(m, " BD:%5ld", nr_backward_deps);
>  
>  	get_usage_chars(class, &c1, &c2, &c3, &c4);
> @@ -350,7 +322,7 @@ static int lockdep_stats_show(struct seq_file *m, void *v)
>  		if (class->usage_mask & LOCKF_ENABLED_HARDIRQS_READ)
>  			nr_hardirq_read_unsafe++;
>  
> -		sum_forward_deps += count_forward_deps(class);
> +		sum_forward_deps += lockdep_count_forward_deps(class);
>  	}
>  #ifdef CONFIG_DEBUG_LOCKDEP
>  	DEBUG_LOCKS_WARN_ON(debug_atomic_read(&nr_unused_locks) != nr_unused);