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

[Peter Zijlstra <a.p.zijlstra@chello.nl>]

On Thu, 2009-07-16 at 12:39 +0800, Ming Lei wrote:
> 2009/7/13 Peter Zijlstra <a.p.zijlstra@chello.nl>:
> > On Sun, 2009-06-28 at 23:04 +0800, tom.leiming@gmail.com wrote:
> >> Hi,Peter
> >>
> >> 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);
> >
> > I'd still like to get some feedback on the loss of that generation count
> > optimization done by DaveM, I haven't had time to analyze the
> > ramifications of that.
> >
> >
> 
> Hi, Ingo and Peter
> 
> As you said, BFS patch-set is valuable(decrease kernel stack consume
> largely, and report
> the shortest circle).
> 
> It has been pending on lkml silently for several monthes, and I hope
> it may be merged to
> tip-tree or other tree. I don't know what we should and can do to make
> it being accepted by tip-tree.
> Anyway, I'd like to do any fixes for it to be merged.
> 
> Any suggestions, ideas or objections?

I've asked several times to comment on the removal of that generation
count DaveM did. Is that a normal part of DFS, or was that an
optimization on top particular to this problem, can something similar be
done for BFS, etc.

Other than that it does seem to hold up, I've got the patches running on
my laptop. Don't worry they're not getting lost.