Re: [stable] combinatorial explosion in lockdep

[Greg KH <greg@kroah.com>]

On Wed, Jul 30, 2008 at 01:15:19PM +0200, Peter Zijlstra wrote:
> 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

Great, please send the stable team the patch when it hits Linus's tree.

thanks,

greg k-h