Messages in this thread | | | Subject | Re: [RESEND PATCH 0/11] kernel:lockdep:replace DFS with BFS | From | Peter Zijlstra <> | Date | Mon, 13 Jul 2009 11:16:14 +0200 |
| |
On Sun, 2009-06-28 at 23:04 +0800, tom.leiming@gmail.com wrote: > Hi,Peter > > 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. This patches 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);
I'd still like to get some feedback on the loss of that generation count optimization done by DaveM, I haven't had time to analyze the ramifications of that.
| |