[RFC v7 00/19] lockdep: Support deadlock detection for recursive read locks

From: Boqun Feng
Date: Fri Aug 07 2020 - 03:43:00 EST

Hi Peter and Waiman,

As promised, this is the updated version of my previous lockdep patchset
for recursive read lock support. It's based on v5.8. Previous versions
can be found at:

V1: https://marc.info/?l=linux-kernel&m=150393341825453
V2: https://marc.info/?l=linux-kernel&m=150468649417950
V3: https://marc.info/?l=linux-kernel&m=150637795424969
V4: https://marc.info/?l=linux-kernel&m=151550860121565
V5: https://marc.info/?l=linux-kernel&m=151928315529363
V6: https://lore.kernel.org/lkml/20180411135110.9217-1-boqun.feng@xxxxxxxxx/

Changes since last version:

* I change the detection algorithm which I present in 2018
plumbers [1], you can find the explanation of the detection
method in patch #2.

* Adjust the irq safe->unsafe changes from Frederic Weisbecker

* Add more tests.

As Peter pointed out:


The lockdep current has a limit support for recursive read locks, the
deadlock case as follow could not be detected:


I got some inspiration from Gautham R Shenoy:


, and came up with this series.

The basic idea is:

* Add recursive read locks into the graph

* Classify dependencies into -(SR)->, -(ER)->, -(SN)->,
-(EN)->, where R stands for recursive read lock, N stands for
other locks(i.e. non-recursive read locks and write locks), S
stands for shared locks (read locks, no matter recursive or
not), and E stands for exclusive locks (i.e. write locks)

* Define strong dependency paths as the paths of dependencies
don't have two adjacent dependencies as -(*R)-> and -(S*)->.

* Extend __bfs() to only traverse on strong dependency paths.

* If __bfs() finds a strong dependency circle, then a deadlock is

The whole series consists of 19 patches:

1. Add documentation for recursive read lock deadlock detection

2. Annotate read_lock() correctly (with queued_read_lock()
semantics into consideration)

3. Do a clean up on the return value of __bfs() and its friends.

4. Make __bfs() able to visit every dependency until a match is
found. The old version of __bfs() could only visit each lock
class once, and this is insufficient if we are going to add
recursive read locks into the dependency graph.

5. Reduce the size of lock_list::distance.

6-7 Extend __bfs() to be able to traverse the stong dependency
patchs after recursive read locks added into the graph.

8. Make __bfs(.math) return bool.

9-11 Adjust check_redundant(), check_noncircular() and
check_irq_usage() with recursive read locks into consideration.

12. Finally add recursive read locks into the dependency graph.

13-14 Adjust lock cache chain key generation with recursive read locks
into consideration, and provide a test case.

15-16 Add more test cases.

17. Revert commit d82fed752942 ("locking/lockdep/selftests: Fix
mixed read-write ABBA tests"),

18-19 Add more test cases (including tests that are specific for

This series passed all the lockdep selftest cases (including those I

Test and comments are welcome!