Skip to content

Support recursive-read lock deadlock detection

Yuyang Du lkml 4 versions – New

Get series with b4
b4 am [email protected]

Versions newest first · linked by author and title

  1. v4 Latest30 patches 0 repliesNew
  2. v330 patches 5 repliesSuperseded
  3. v217 patches 3 repliesSuperseded
Earlier versions · 1
VersionPostedPatchesRepliesStatus
v117 patches4 repliesSuperseded

Changes in v4 from the cover letter

- Reworded some changelogs
- Rebased to current code base
- Per Boqun's suggestion, reordered patches
- Much more time elapsed

Patches in v4 No applies recorded yet

#Subject and filesSizeRepliesApplied
1/30locking/lockdep: Rename deadlock check functionskernel/locking/lockdep.c+8 -70 replies
2/30locking/lockdep: Change return type of add_chain_cache()kernel/locking/lockdep.c+11 -110 replies
3/30locking/lockdep: Change return type of lookup_chain_cache_add()kernel/locking/lockdep.c+10 -130 replies
4/30locking/lockdep: Pass lock chain from validate_chain() to check_prev_add()kernel/locking/lockdep.c+7 -50 replies
5/30locking/lockdep: Add lock chain list_head field in struct lock_list and lock_chaininclude/linux/lockdep.h+3 -00 replies
6/30locking/lockdep: Update comments in struct lock_list and held_lockinclude/linux/lockdep.h+8 -90 replies
7/30locking/lockdep: Remove indirect dependency redundancy checkkernel/locking/lockdep.c kernel/locking/lockdep_internals.h kernel/locking/lockdep_proc.c+0 -440 replies
8/30locking/lockdep: Skip checks if direct dependency is already presentkernel/locking/lockdep.c+19 -150 replies
9/30locking/lockdep: Remove chain_head argument in validate_chain()kernel/locking/lockdep.c+7 -110 replies
10/30locking/lockdep: Remove useless lock type assignmentkernel/locking/lockdep.c+0 -70 replies
11/30locking/lockdep: Remove irq-safe to irq-unsafe read checkkernel/locking/lockdep.c+2 -40 replies
12/30locking/lockdep: Specify the depth of current lock stack in lookup_chain_cache_add()kernel/locking/lockdep.c+26 -220 replies
13/30locking/lockdep: Treat every lock dependency as in a new lock chainkernel/locking/lockdep.c+108 -1150 replies
14/30locking/lockdep: Combine lock_lists in struct lock_class into an arrayinclude/linux/lockdep.h kernel/locking/lockdep.c kernel/locking/lockdep_proc.c+32 -390 replies
15/30locking/lockdep: Consolidate forward and backward lock_lists into oneinclude/linux/lockdep.h kernel/locking/lockdep.c kernel/locking/lockdep_proc.c+131 -890 replies
16/30locking/lockdep: Add lock chains to direct lock dependency graphkernel/locking/lockdep.c+81 -40 replies
17/30locking/lockdep: Use lock type enum to explicitly specify read or write locksinclude/linux/lockdep.h include/linux/rcupdate.h kernel/locking/lockdep.c+32 -160 replies
18/30ocking/lockdep: Add read-write type for a lock dependencyinclude/linux/lockdep.h kernel/locking/lockdep.c+37 -30 replies
19/30locking/lockdep: Add helper functions to operate on the searched pathkernel/locking/lockdep.c+31 -00 replies
20/30locking/lockdep: Update direct dependency's read-write type if it existskernel/locking/lockdep.c+26 -00 replies
21/30locking/lockdep: Introduce chain_hlocks_type for held lock's read-write typekernel/locking/lockdep.c+10 -00 replies
22/30locking/lockdep: Hash held lock's read-write type into chain keyinclude/linux/lockdep.h kernel/locking/lockdep.c+40 -160 replies
23/30locking/lockdep: Adjust BFS algorithm to support multiple matcheskernel/locking/lockdep.c+26 -250 replies
24/30locking/lockdep: Define the two task model for lockdep checks formallykernel/locking/lockdep.c+68 -00 replies
25/30locking/lockdep: Introduce mark_lock_unaccessed()kernel/locking/lockdep.c+9 -00 replies
26/30locking/lockdep: Add nest lock typekernel/locking/lockdep.c kernel/locking/lockdep_internals.h+7 -20 replies
27/30locking/lockdep: Add lock exclusiveness tablekernel/locking/lockdep.c+30 -00 replies
28/30locking/lockdep: Support read-write lock's deadlock detectionkernel/locking/lockdep.c+178 -490 replies
29/30locking/lockdep: Adjust selftest case for recursive read locklib/locking-selftest.c+18 -140 replies
30/30locking/lockdep: Add more lockdep selftest caseslib/locking-selftest.c+1077 -00 replies

Reviews trailers per patch

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

Read the v4 thread

Cover letter [PATCH v4 00/30] Support recursive-read lock deadlock detection

Hi Peter and Ingo,

This patchset proposes a general read-write lock deadlock detection algorithm on the premise that exclusive locks can be seen as a special/partial usage of read-write locks. The current Linux kernel locks are all considered in this algorithm. Prominently, the recursive-read lock can be well supported, which has not been for more than a decade.

The bulk of the algorithm is in patch #27. Now that the recursive-read locks are suppported, we have all the 262 cases passed.

Please, some of the minor fix and/or no-functional-change patches may be reviewed at least.

Changes from v3:

- Reworded some changelogs
- Rebased to current code base
- Per Boqun's suggestion, reordered patches
- Much more time elapsed

Changes from v2:

- Handle correctly rwsem locks hopefully.
- Remove indirect dependency redundancy check.
- Check direct dependency redundancy before validation.
- Compose lock chains for those with trylocks or separated by trylocks.
- Map lock dependencies to lock chains.
- Consolidate forward and backward lock_lists.
- Clearly and formally define two-task model for lockdep.

--

Yuyang Du (30):
locking/lockdep: Rename deadlock check functions locking/lockdep: Change return type of add_chain_cache() locking/lockdep: Change return type of lookup_chain_cache_add() locking/lockdep: Pass lock chain from validate_chain() to
check_prev_add()
locking/lockdep: Add lock chain list_head field in struct lock_list
and lock_chain
locking/lockdep: Update comments in struct lock_list and held_lock locking/lockdep: Remove indirect dependency redundancy check locking/lockdep: Skip checks if direct dependency is already present locking/lockdep: Remove chain_head argument in validate_chain() locking/lockdep: Remove useless lock type assignment locking/lockdep: Remove irq-safe to irq-unsafe read check locking/lockdep: Specify the depth of current lock stack in
lookup_chain_cache_add()
locking/lockdep: Treat every lock dependency as in a new lock chain locking/lockdep: Combine lock_lists in struct lock_class into an array locking/lockdep: Consolidate forward and backward lock_lists into one locking/lockdep: Add lock chains to direct lock dependency graph locking/lockdep: Use lock type enum to explicitly specify read or
write locks
ocking/lockdep: Add read-write type for a lock dependency locking/lockdep: Add helper functions to operate on the searched path locking/lockdep: Update direct dependency's read-write type if it
exists
locking/lockdep: Introduce chain_hlocks_type for held lock's
read-write type
locking/lockdep: Hash held lock's read-write type into chain key locking/lockdep: Adjust BFS algorithm to support multiple matches locking/lockdep: Define the two task model for lockdep checks formally locking/lockdep: Introduce mark_lock_unaccessed() locking/lockdep: Add nest lock type
locking/lockdep: Add lock exclusiveness table locking/lockdep: Support read-write lock's deadlock detection locking/lockdep: Adjust selftest case for recursive read lock locking/lockdep: Add more lockdep selftest cases

 include/linux/lockdep.h            |   91 ++-
 include/linux/rcupdate.h           |    2 +-
 kernel/locking/lockdep.c           | 1227 ++++++++++++++++++++++++------------
 kernel/locking/lockdep_internals.h |    3 +-
 kernel/locking/lockdep_proc.c      |    8 +-
 lib/locking-selftest.c             | 1109 +++++++++++++++++++++++++++++++-
 6 files changed, 1981 insertions(+), 459 deletions(-)
Signature · 1 line
1.8.3.1