Messages in this thread | | | From | Boqun Feng <> | Subject | [RFC tip 0/5] lockdep: Support deadlock detection for recursive read locks | Date | Mon, 28 Aug 2017 22:56:52 +0800 |
| |
Hi Ingo and Peter,
As Peter pointed out:
https://marc.info/?l=linux-kernel&m=150349072023540
The lockdep current has a limit support for recursive read locks, the deadlock case as follow could not be detected:
read_lock(A); lock(B); lock(B); write_lock(A);
I got some inspiration from Gautham R Shenoy:
https://lwn.net/Articles/332801/
, and came up with this series.
The basic idea is:
* Add recursive read locks into the graph
* Classify dependencies into R->R, N->R, R->N, N->N, where R stands for recursive read lock, N stands for other locks.
* Extend __bfs() to go through all kinds of dependencies and the read/write status could be changed in the traverse(i.e. with dependency N(A)->R(B) and N(B)->R(C), BFS could go from A to B and then to C).
* But don't allow use a lock B as a transfer station if B only has *->R dependencies to the previous lock and R->* dependencies to the next lock. This is because if a BFS traverse has such a B as a transfer station, the following exists:
CPU0 CPU1 CPU2 CPU3 lock(X); lock(Y); lock(Y); rlock(B); rlock(B); lock(P); lock(P); lock(Q);
The lock dependency breaks between CPU1 and CPU2, no deadlock.
In this way, we can reflect the real dependencies while taking recursive read locks into considerations.
This is readlly an RFC, as I'm 100% sure I cover all the cases related to read recursive locks, but I do add two sets of self testcases, and they did pass ;-)
This series consists of 5 patches:
Patch #1 introduces a new test case to test chain cache behavior on the recursive read deadlock detection.
Patch #2 introduces more complex cases for recursive read deadlock detection.
Patch #3 does a little bit clean-up on the return value of __bfs() and its friends.
Patch #4 adds recursive locks into dependency graph and extends BFS to allow deadlock detection for recursive read locks.
Patch #5 fixes the problem that lock chains and chainkeys don't treat read/write locks differently, which could miss the chance to detect a deadlock because a lock chain cache hit.
I plan to write more tests and play about this in next weeks, just send out for suggestions and comments.
Reviews and tests are welcome!
Regards, Boqun
| |