Skip to contentSkip to conversation

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

RFC Ming Lei 2 participants 4 messages May 26, 2009 – May 27, 2009

lore
Share & tools
lore

Ming Lei

author
#0 lore raw

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,

Signature · 1 line
Lei Ming
#1 lore raw
Quoted 16 lines · 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.

Quoted 6 lines

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.

author
#2 lore raw
Quoted 26 lines · On Tue, 26 May 2009 15:59:34 +0200 Peter Zijlstra <[email protected]>…
Quoted 18 lines · 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.

Quoted 6 lines

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?

Quoted 8 lines

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
Quoted 4 lines

But yes, it wuold be nice to get rid of current recursive algorithm there.

OK, I'll start to do it.

Thanks.

Signature · 1 line
Lei Ming
author
#3 lore raw
In reply to Peter Zijlstra

2009/5/26 Peter Zijlstra <[email protected]>:

Quoted 13 lines · Ming Lei
Quoted 12 lines

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);

Quoted 8 lines
Quoted 8 lines

      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.

Quoted 16 lines
Quoted 2 lines

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.

Signature · 1 line
Lei Ming