[RFC] kernel/lockdep: use BFS(breadth-first search) algorithm to search target

[RFC] kernel/lockdep: use BFS(breadth-first search) algorithm to search target

[Ming Lei]

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

Re: [RFC] kernel/lockdep: use BFS(breadth-first search) algorithm to search target

[Peter Zijlstra]

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.

Re: [RFC] kernel/lockdep: use BFS(breadth-first search) algorithm to search target

[Ming Lei]

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

Re: [RFC] kernel/lockdep: use BFS(breadth-first search) algorithm to search target

[Ming Lei]

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