* [RFC] kernel/lockdep: use BFS(breadth-first search) algorithm to search target
@ 2009-05-26 13:54 Ming Lei
2009-05-26 13:59 ` Peter Zijlstra
0 siblings, 1 reply; 4+ messages in thread
From: Ming Lei @ 2009-05-26 13:54 UTC (permalink / raw)
To: mingo, a.p.zijlstra; +Cc: akpm, linux-kernel
Hi,All
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. I plan to 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, we know kernel stack is very limited, eg. 4KB.
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.
Any suggestions, objections or viewpoint?
Thanks,
--
Lei Ming
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: [RFC] kernel/lockdep: use BFS(breadth-first search) algorithm to search target
2009-05-26 13:54 [RFC] kernel/lockdep: use BFS(breadth-first search) algorithm to search target Ming Lei
@ 2009-05-26 13:59 ` Peter Zijlstra
2009-05-26 14:36 ` Ming Lei
2009-05-27 0:30 ` Ming Lei
0 siblings, 2 replies; 4+ messages in thread
From: Peter Zijlstra @ 2009-05-26 13:59 UTC (permalink / raw)
To: Ming Lei; +Cc: mingo, akpm, linux-kernel
On Tue, 2009-05-26 at 21:54 +0800, Ming Lei wrote:
> Hi,All
>
> 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. I plan to 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, we know kernel stack is very limited, eg. 4KB.
>
> 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.
>
> Any suggestions, objections or viewpoint?
Ah, replace the full cycle detection might be worth it, esp with that
pre-allocated stack you used. Its all serialized on the graph lock
anyway.
I'm not sure about 3, though, since we search on adding a each new
dependency we'll only ever have a choice between cycles when one new
dependency generates two cycles at the same time. Something I think is
rare.
But yes, it wuold be nice to get rid of the current recursive algorithm
there.
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: [RFC] kernel/lockdep: use BFS(breadth-first search) algorithm to search target
2009-05-26 13:59 ` Peter Zijlstra
@ 2009-05-26 14:36 ` Ming Lei
2009-05-27 0:30 ` Ming Lei
1 sibling, 0 replies; 4+ messages in thread
From: Ming Lei @ 2009-05-26 14:36 UTC (permalink / raw)
To: Peter Zijlstra; +Cc: mingo, akpm, linux-kernel
On Tue, 26 May 2009 15:59:34 +0200
Peter Zijlstra <a.p.zijlstra@chello.nl> wrote:
> On Tue, 2009-05-26 at 21:54 +0800, Ming Lei wrote:
> > Hi,All
> >
> > 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. I plan to 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, we know kernel stack is very limited, eg.
> > 4KB.
> >
> > 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.
> >
> > Any suggestions, objections or viewpoint?
>
> Ah, replace the full cycle detection might be worth it, esp with that
> pre-allocated stack you used. Its all serialized on the graph lock
> anyway.
>
> I'm not sure about 3, though, since we search on adding a each new
> dependency we'll only ever have a choice between cycles when one new
> dependency generates two cycles at the same time. Something I think is
> rare.
IMHO, maybe it is not much, but is not rare, for example, the prev node
is in a graph(GA) and the next node is in another graph(GB). If GA and
GB is not connected, the edge of prev to next can't generate a cycle.
If GA and GB is connected, it is possible to generate one or multiple
cycles,which depends on the connect degree between GA and GB.
BTW: BFS in the previous patch finds a shorter path in the
thread:
http://marc.info/?l=linux-kernel&m=124211522525625&w=2
>
> But yes, it wuold be nice to get rid of current recursive
> algorithm there.
>
OK, I'll start to do it.
Thanks.
--
Lei Ming
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: [RFC] kernel/lockdep: use BFS(breadth-first search) algorithm to search target
2009-05-26 13:59 ` Peter Zijlstra
2009-05-26 14:36 ` Ming Lei
@ 2009-05-27 0:30 ` Ming Lei
1 sibling, 0 replies; 4+ messages in thread
From: Ming Lei @ 2009-05-27 0:30 UTC (permalink / raw)
To: Peter Zijlstra; +Cc: mingo, akpm, linux-kernel
2009/5/26 Peter Zijlstra <a.p.zijlstra@chello.nl>:
> On Tue, 2009-05-26 at 21:54 +0800, Ming Lei wrote:
>> Hi,All
>>
>> 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. I plan to 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, we know kernel stack is very limited, eg. 4KB.
>>
>> 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.
Another case, there are several lock_list instances in one lock dependency graph
,which all points to one lock_class, BFS can find the one with
shortest distance,but
DFS can't. The scenario should be common, right?
Thanks.
>>
>> Any suggestions, objections or viewpoint?
>
> Ah, replace the full cycle detection might be worth it, esp with that
> pre-allocated stack you used. Its all serialized on the graph lock
> anyway.
>
> I'm not sure about 3, though, since we search on adding a each new
> dependency we'll only ever have a choice between cycles when one new
> dependency generates two cycles at the same time. Something I think is
> rare.
>
> But yes, it wuold be nice to get rid of the current recursive algorithm
> there.
>
>
--
Lei Ming
^ permalink raw reply [flat|nested] 4+ messages in thread
end of thread, other threads:[~2009-05-27 0:30 UTC | newest]
Thread overview: 4+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2009-05-26 13:54 [RFC] kernel/lockdep: use BFS(breadth-first search) algorithm to search target Ming Lei
2009-05-26 13:59 ` Peter Zijlstra
2009-05-26 14:36 ` Ming Lei
2009-05-27 0:30 ` Ming Lei
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).