Messages in this thread |  | | | Date | Tue, 26 May 2009 22:36:39 +0800 | | From | Ming Lei <> | | Subject | Re: [RFC] kernel/lockdep: use BFS(breadth-first search) algorithm to search target |
| |
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
|  |