Re: [PATCH 0/8] kernel:lockdep:replace DFS with BFS

[Ming Lei]

On Mon, 08 Jun 2009 14:22:07 +0200
Peter Zijlstra <a.p.zijlstra@xxxxxxxxx> wrote:

> On Sun, 2009-05-31 at 22:49 +0800, tom.leiming@xxxxxxxxx wrote:
> > Hi,
> > Currently lockdep uses recursion DFS(depth-first search) algorithm
> > to search target in checking lock
> > circle(check_noncircular()),irq-safe ->
> > irq-unsafe(check_irq_usage()) and irq inversion when adding a new
> > lock dependency. This patches replace the current DFS with BFS,
> > based on the following consideration:
> > 
> >      1,no loss of efficiency, no matter DFS or BFS, the running time
> >      are O(V+E) (V is vertex count, and E is edge count of one
> >      graph);
> > 
> >      2,BFS may be easily implemented by circular queue and consumes
> >      much less kernel stack space than DFS for DFS is implemented by
> >      recursion.
> > 
> >      3, The shortest path can be obtained by BFS if the target is
> >      found, but can't be got by DFS. By the shortest path, we can
> >      shorten the lock dependency chain and help to troubleshoot lock
> >      problem easier than before.
> > 
> 
> OK, so I applied the patches and the cleanup below.
> 
> mostly little style nits and moving the circular queue into lockdep.c
> (nobody else uses it, so why share it?).
> 
> One thing though, macros with return statements?! that's seriously bad
> style, don't do that.
> 
> One thing that worries me a little is that we loose DaveM's
> lockdep_dependency_visit() optimization. My brain seems unwilling to
> co-operate on determining if BFS would make that redundant, so a
> little word on that would be appreciated.
> 
> Then I booted it and all hell broke loose, so either I wrecked
> something or you did :-), would you terribly mind poking at that a
> little?

I have fixed the bug, which is introduced in your patch:
	lockdep: clean up after BFS patches.

Please apply and verify the patch,thanks.

I'll go to bed,:-)