Messages in this thread | | | Subject | Re: combinatorial explosion in lockdep | From | Peter Zijlstra <> | Date | Wed, 30 Jul 2008 09:19:54 +0200 |
| |
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 :-)
Way cool stuff - will try and wrap my brains around it asap.
| |