kernel/lockdep: use BFS(breadth-first search) algorithm to search target
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
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.
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 onegraph); 2,BFS may be easily implemented by circular queue andconsumes 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
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