How a General Deadlock Prediction Algorithm Enhances Linux Lockdep for Read‑Write Locks

Background

Deadlocks in multithreaded and distributed programs are difficult to recover from. The Linux kernel uses the Lockdep tool to detect and predict lock‑related deadlocks, but Lockdep historically supports only mutexes. When read‑write locks (rwsem, rwlock, qrwlock) are involved, Lockdep can produce false‑positive and false‑negative predictions.

Motivation

During the resolution of several large‑scale kernel faults, extensive effort was spent tracing lock‑dependency cycles, revealing the need for a generic deadlock‑prediction method that works with all kernel lock types, especially read‑write locks.

Proposed Solution

A universal lock‑dependency algorithm is introduced. It models lock acquisition order as a directed graph and extends the existing two‑thread model (T1 and T2) to handle read‑write locks correctly.

Key Concepts

Lock Dependency Graph : Nodes are lock classes; an edge A→B records that a thread acquired lock B while holding lock A.

Two‑Thread Model : T1 represents the existing lock‑dependency graph; T2 represents the new direct lock dependency being examined.

Lock Types : Recursive‑read < < Read < < Write (mutex). The hierarchy is used for lock‑type promotion.

Lemmas

With read‑write locks, a lock‑order cycle is necessary but not sufficient for a potential deadlock; prediction occurs when the last dependency that would close the cycle appears.

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

Any deadlock can be transformed into an ABBA pattern.

When a direct lock introduces indirect dependencies, the direct lock remains the key for detection.

T2 needs to cover only the current thread’s lock stack.

Checking indirect dependencies in T2 is essential for read‑write locks.

The lock‑stack boundary for T2 is sufficient.

Simple Algorithm

Based on the two‑thread model, the simple algorithm checks whether the lock types of the two edges (X1.A→X1.B and X2.A→X2.B) are mutually exclusive. If they are, a potential deadlock is reported. T1,T2,…,Tn This algorithm fails when indirect dependencies create a cycle, as demonstrated by a counter‑example where the indirect lock X3→X1 is missed.

Final Algorithm

The final algorithm extends the search to handle indirect dependencies:

Continue scanning the lock‑dependency graph (T1) for new cycles.

When a new cycle is found, check whether any lock from T2’s lock stack participates, forming an indirect dependency. Verify whether this indirect dependency creates a potential deadlock.

Terminate when a deadlock is detected or the entire graph has been examined.

Lock‑type promotion upgrades lower‑exclusivity locks to higher‑exclusivity ones (Recursive‑read → Read → Write) so that the dependency type reflects the strongest lock involved.

Implementation and Evaluation

The algorithm has been integrated into the Linux kernel’s Lockdep implementation and submitted for review. The core proof and experimental validation confirm that the algorithm eliminates the previous false‑positive/negative issues with read‑write locks.

For the full patch set and discussion, see https://lkml.org/lkml/2019/8/29/167

Conclusion

The presented universal deadlock‑prediction algorithm resolves the long‑standing limitation of Lockdep with read‑write locks, providing a sound method to predict potential deadlocks in the Linux kernel.