General Deadlock Prediction Algorithm for Linux Kernel Read‑Write Locks

Deadlock is a common and severe problem in multithreaded and distributed programs. It is destructive, hard to recover from, and often occurs only under specific, hard‑to‑reproduce conditions. The Linux kernel uses the Lockdep tool to detect and predict lock‑related deadlocks, but Lockdep currently supports only mutexes and cannot handle more complex read‑write locks, especially recursive read locks, leading to false‑positive and false‑negative predictions.

This work first reverse‑engineers Lockdep and then proposes a universal lock deadlock prediction algorithm that treats mutexes as the write‑lock variant of a read‑write lock. The algorithm is proved to be correct and comprehensive.

The motivation stems from the author’s experience fixing three major kernel faults that severely impacted Didi’s large server clusters. The time spent locating the exact lock cycles delayed fault resolution, prompting the search for a generic method to handle deadlocks.

Deadlock is analogous to a traffic circle where each vehicle waits for the one ahead, forming a circular wait that prevents forward progress. In software, participants form a circular wait for lock releases, causing the system to stall.

Solutions to deadlock are typically categorized as detection (finding an existing deadlock at runtime), prevention (avoiding the formation of a deadlock), and prediction (statically or dynamically identifying potential deadlocks before they occur).

Lockdep records lock classes and the ordering of lock acquisitions (e.g., if a thread acquires lock A then lock B without releasing A, a dependency A→B is recorded). An ABBA pattern (A→B and B→A) indicates a potential deadlock. However, with read‑write locks, the dependency analysis becomes more complex.

Linux provides several read‑write lock implementations (rwsem, rwlock, qrwlock). Because read‑write locks allow multiple readers, the simple ABBA rule no longer suffices, and Lockdep’s lack of support for these locks results in inaccurate predictions.

The paper introduces a series of lemmas to build the algorithm:

Lemma 1: In the presence of read‑write locks, a lock‑order cycle is necessary but not sufficient for a potential deadlock; the cycle is predicted when the last dependency that would close the cycle appears.

Lemma 2: All deadlock scenarios can be represented using two virtual threads (T1 and T2).

Lemma 3: Any deadlock can be transformed into an ABBA pattern.

Lemma 4: Indirect lock dependencies introduced by a direct dependency are also critical for detection.

Lemma 5: T2 only needs to be expanded to the current thread’s lock stack.

Lemma 6: Checking indirect dependencies in T2 is necessary because read‑write locks break the simple ABBA rule.

Lemma 7: The lock stack of the current thread is a sufficient boundary for T2.

Based on these lemmas, a two‑thread model is defined: T1 contains all previously recorded lock dependencies (forming a graph), and T2 represents the current lock stack of the thread under inspection. A simple algorithm checks whether the new direct dependency X1→X2 is mutually exclusive with an existing dependency X2→X1; if so, a potential deadlock is reported.

When the simple algorithm fails (e.g., because indirect dependencies are ignored), the final algorithm extends the search:

Search the lock‑dependency graph (T1) for a new cycle.

If the cycle contains locks from T2, treat the combination of T1’s indirect dependency and T2’s direct dependency as a potential deadlock and verify it.

Repeat until the entire graph is examined or a deadlock is found.

The final algorithm successfully resolves the failure cases of the simple algorithm, as demonstrated by the illustrated examples.

The algorithm has been implemented in Lockdep and submitted to the Linux kernel community for review (see https://lkml.org/lkml/2019/6/28/272 and https://lkml.org/lkml/2019/8/29/167). The author, Du Yuyang, is a senior expert engineer at Didi focusing on Linux kernel stability and architecture.

T1,T2,…,Tn