Skip to content

kernel:lockdep:replace DFS with BFS

[email protected] lkml 2 versions – In review

Get series with b4
b4 am [email protected]

Versions newest first · linked by author and title

  1. v1 Latest posting 2/211 patches 42 repliesIn review
  2. v1 posting 1/28 patches 8 repliesSuperseded

Patches in v1 posting 2/2 No applies recorded yet

#Subject and filesSizeRepliesApplied
1/11kernel:lockdep:print the shortest dependency chain if finding a circleinclude/linux/lockdep.h kernel/lockdep.c kernel/lockdep_internals.h+195 -99 replies
2/11kernel:lockdep:improve implementation of BFSkernel/lockdep.c kernel/lockdep_internals.h+39 -192 replies
3/11kernel:lockdep: introduce match function to BFSkernel/lockdep.c+26 -172 replies
4/11kernel:lockdep:implement check_noncircular() by BFSkernel/lockdep.c+37 -525 replies
5/11kernel:lockdep:implement find_usage_*wards by BFSkernel/lockdep.c+72 -1082 replies
6/11kernel:lockdep:introduce print_shortest_lock_dependencieskernel/lockdep.c kernel/lockdep_internals.h+69 -282 replies
7/11kernel:lockdep: implement lockdep_count_*ward_deps by BFSkernel/lockdep.c+25 -272 replies
8/11kernel:lockdep: update memory usage introduced by BFSkernel/lockdep.c+2 -13 replies
9/11kernel:lockdep:add statistics info for max bfs queue depthkernel/lockdep.c kernel/lockdep_internals.h kernel/lockdep_proc.c+9 -22 replies
10/11BFS cleanupinclude/linux/lockdep.h kernel/lockdep.c kernel/lockdep_internals.h+147 -1893 replies
11/11kernel:lockdep:fix return value of check_usage*()kernel/lockdep.c+12 -80 replies

Reviews trailers per patch

No Reviewed-by, Acked-by or Tested-by trailers for v1 yet.

Read the v1 thread

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.