Messages in this thread | | | Subject | Re: [RFC] kernel/lockdep: use BFS(breadth-first search) algorithm to search target | From | Peter Zijlstra <> | Date | Tue, 26 May 2009 15:59:34 +0200 |
| |
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.
| |