kernel:lockdep:replace DFS with BFS
Get series with b4
b4 am [email protected]Versions newest first · linked by author and title
- v1 Latest posting 2/211 patches 42 repliesIn review
- v1 posting 1/28 patches 8 repliesSuperseded
Patches in v1 posting 2/2 No applies recorded yet
| # | Subject and files | Size | Replies | Applied |
|---|---|---|---|---|
| 1/11 | kernel:lockdep:print the shortest dependency chain if finding a circleinclude/ kernel/ kernel/ | +195 | 9 replies | |
| 2/11 | kernel:lockdep:improve implementation of BFSkernel/ kernel/ | +39 | 2 replies | |
| 3/11 | kernel:lockdep: introduce match function to BFSkernel/ | +26 | 2 replies | |
| 4/11 | kernel:lockdep:implement check_noncircular() by BFSkernel/ | +37 | 5 replies | |
| 5/11 | kernel:lockdep:implement find_usage_*wards by BFSkernel/ | +72 | 2 replies | |
| 6/11 | kernel:lockdep:introduce print_shortest_lock_dependencieskernel/ kernel/ | +69 | 2 replies | |
| 7/11 | kernel:lockdep: implement lockdep_count_*ward_deps by BFSkernel/ | +25 | 2 replies | |
| 8/11 | kernel:lockdep: update memory usage introduced by BFSkernel/ | +2 | 3 replies | |
| 9/11 | kernel:lockdep:add statistics info for max bfs queue depthkernel/ kernel/ kernel/ | +9 | 2 replies | |
| 10/11 | BFS cleanupinclude/ kernel/ kernel/ | +147 | 3 replies | |
| 11/11 | kernel:lockdep:fix return value of check_usage*()kernel/ | +12 | 0 replies |
Reviews trailers per patch
No Reviewed-by, Acked-by or Tested-by trailers for v1 yet.
Cover letter [RESEND PATCH 0/11] kernel:lockdep:replace DFS with BFS
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);
2,BFS may be easily implemented by circular queue and consumes much less kernel stack space than DFS for DFS is implemented by recursion.
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.