From: Peter Zijlstra <peterz@infradead.org>
To: David Miller <davem@davemloft.net>
Cc: mingo@elte.hu, linux-kernel@vger.kernel.org
Subject: Re: combinatorial explosion in lockdep
Date: Wed, 30 Jul 2008 09:19:54 +0200 [thread overview]
Message-ID: <1217402394.6364.6.camel@twins> (raw)
In-Reply-To: <20080729.214503.126934382.davem@davemloft.net>
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.
next prev parent reply other threads:[~2008-07-30 7:20 UTC|newest]
Thread overview: 21+ messages / expand[flat|nested] mbox.gz Atom feed top
2008-07-28 22:37 combinatorial explosion in lockdep David Miller
2008-07-28 22:50 ` Jeremy Fitzhardinge
2008-07-28 22:56 ` David Miller
2008-07-28 23:13 ` David Miller
2008-07-28 23:51 ` Ingo Molnar
2008-07-29 0:44 ` David Miller
2008-07-30 4:45 ` David Miller
2008-07-30 6:56 ` David Miller
2008-07-30 7:21 ` Peter Zijlstra
2008-07-30 7:19 ` Peter Zijlstra [this message]
2008-07-30 11:15 ` Peter Zijlstra
2008-07-31 16:50 ` [stable] " Greg KH
2008-07-30 11:26 ` [PATCH] lockdep: change scheduler annotation Peter Zijlstra
2008-07-30 11:34 ` David Miller
2008-07-31 16:34 ` Ingo Molnar
2008-07-31 16:39 ` combinatorial explosion in lockdep Ingo Molnar
2008-08-01 9:22 ` Ingo Molnar
2008-08-01 9:32 ` David Miller
2008-08-01 11:57 ` Hugh Dickins
2008-08-03 8:14 ` David Miller
2008-08-04 12:21 ` Hugh Dickins
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=1217402394.6364.6.camel@twins \
--to=peterz@infradead.org \
--cc=davem@davemloft.net \
--cc=linux-kernel@vger.kernel.org \
--cc=mingo@elte.hu \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).