Lockdep: Proving Lock Order Without Running the Deadlock

A deadlock between two locks requires a cycle: some path takes A then B, another takes B then A, and the two interleave. Finding that cycle by testing means producing the interleaving, which may need a specific pair of threads, a specific timing, and a specific hardware configuration. The lock validator takes a different route. It observes which locks are held at the moment each lock is acquired, records that relation, and checks whether the relation ever closes into a cycle. A cycle found this way is a proof that some schedule deadlocks, not a suspicion, not a statistical inference.

Classes, not instances

The first thing the validator does is refuse to reason about individual lock objects. A kernel may have thousands of struct mutex instances, most of them acquired in the same few orders, and tracking relations between instances would produce a graph too large to check and too specific to be useful. Instead, every lock is assigned to a class at initialisation, identified by the place in the source where the lock was declared: the file, the line, and the initialisation macro.

Two locks of the same class are treated as interchangeable. That is a deliberate over-approximation: if a driver allocates an array of identical mutexes and always takes them in index order, the validator sees a class taking itself and reports a possible self-deadlock, even though the actual code never does. The report is a false positive in the strict sense, and the fix is to give the locks distinct classes (a documented annotation that says these two objects are never held in a cycle) or to avoid nested acquisition of same-class locks.

The over-approximation is the source of the validator’s value. Because it reasons about classes, it catches cycles that would require a configuration the developer does not have, a code path that only runs on one filesystem, or an interrupt that only fires under load. The cost is that it also reports cycles that the code’s own invariants prevent, and the annotations that suppress those reports are themselves a claim about the code that must be true.

The graph and the check

Each acquisition is recorded as a directed edge: for the lock being taken, an edge from every lock currently held by this task, in every context that could be running. The relation is stored per class pair together with the acquisition that created it, and the search for a path runs when an edge is added rather than lazily at report time, which is what bounds the work to the cost of one graph traversal per acquisition.

The check is a breadth-first search from the new edge’s target back to its source, and breadth-first because the path it finds is the shortest one, which is also the most readable one to put in a report. If the target can already reach the source, the new edge closes a cycle and the validator reports it. The report names the classes involved, the order in which the edges were added, and, for each edge, a stack trace of the acquisition that created it, which is what makes the report actionable, since it points at the two code paths whose orders conflict.

The graph is not a simple lock-order graph. It distinguishes contexts: a lock taken in process context and a lock taken in interrupt context are different vertices, because a deadlock can arise from a lock taken in an interrupt handler while the interrupted code holds a different lock. The validator tracks which interrupts are enabled or disabled at each acquisition and adds the corresponding edges. This is why the report sometimes describes a cycle that involves a lock the developer never wrote code to acquire: the edge came from an interrupt handler that the hardware can deliver at that point.

There is also the question of what “held” means across a context switch. A task that acquires A, sleeps, and later acquires B while still holding A produces an edge from A to B, correctly, because the sleep does not release A. But the validator must also handle the case where a lock is released and reacquired, and where a task holds no locks at all. The bookkeeping is per-task and per-CPU, and it is why the validator has a fixed limit on how many held locks it will track per task. Exceeding that limit is not a local failure: the kernel prints a warning, switches the validator off for the whole machine, and from then on reports nothing, so a run that produced no further reports may have been blind rather than clean. The same shutdown happens for several other bookkeeping overflows, and the first line of a lockdep report usually says which one ended validation.

#include <linux/mutex.h>

static DEFINE_MUTEX(outer);
static DEFINE_MUTEX(inner);

static void take_both(void)
{
	mutex_lock(&outer);
	mutex_lock(&inner);   /* records the edge outer -> inner */
	mutex_unlock(&inner);
	mutex_unlock(&outer);
}

static void take_reversed(void)
{
	mutex_lock(&inner);
	mutex_lock(&outer);   /* second edge closes the cycle: reported */
	mutex_unlock(&outer);
	mutex_unlock(&inner);
}

The report for this pair appears the first time take_reversed runs, not when the two functions actually interleave. That is the difference from a runtime detector: no deadlock has to occur, and none of the timing conditions have to hold.

What it cannot see

The validator reasons about the locks it is told about. A lock acquired by hand-written assembly, or by a primitive that does not call the annotation macros, contributes no edges. A lock embedded in a structure that is accessed through a raw pointer without the accessor that records it is invisible. The kernel’s own locking primitives are instrumented; a driver that implements its own spinlock in a device register is not.

Second, it cannot see ordering enforced by something other than the lock graph. If a cycle is broken by a flag that prevents two paths from running concurrently (a state machine that guarantees one path cannot reach the second acquisition), the validator will still report the cycle, because the flag is not a lock and contributes no edge. Those reports are resolved with annotations that assert the exclusion, and the assertion is a promise by the developer, not a proof by the tool.

Third, it cannot distinguish a cycle that is reachable in practice from one that is not, because reachability depends on inputs and configuration. A cycle involving two filesystems that can never be mounted together is still a cycle in the graph. The reasoning behind closing such a report is that the two subsystems cannot coexist, which is why the validator’s output is best read as a question about the code rather than a verdict on the system.

Fourth, it does not cover every synchronisation primitive. Reference counts, RCU grace periods, and completion variables create ordering constraints that can deadlock, and the validator models only some of them. The relation between a lock and an RCU read-side section, for example, is tracked because the kernel annotates it, but the relation between two different kinds of deferred work is not.

The cost of being always on

The bookkeeping is not free. Every lock acquisition becomes a graph update, and the graph is protected by its own lock, so enabling the validator changes the very timing it is observing: acquisition paths become longer, lock hold times become longer, and a system that was merely slow becomes a system that is too slow to test. The kernel’s response is to make the validator a debug option, disabled in ordinary builds, and to keep the per-acquisition cost bounded so that it can be left enabled in those builds: recording an edge is a fixed number of operations, and the cycle search runs only when an edge is added rather than on every scheduling decision.

Even when enabled, the validator is not a proof about all executions. It is a proof about the orders that were exercised. A cycle whose edges come from two code paths that never both ran in the same boot will not be found. The usual practice is to enable it during development and during test runs that exercise as many paths as possible, and to treat the absence of a report as evidence about coverage rather than evidence about correctness.

A cycle in the lock graph is one deadlock mechanism, and a high-priority task blocked on a lock held by a low-priority task that is preempted by a medium-priority task is another. The validator does not detect the second, because no cycle exists in the lock graph; the ordering is fine and the problem is scheduling. Distinguishing the two when a hang is reported is a matter of reading the stacks, which is only possible because the unwind tables described in stack unwinding without frame pointers cover the paths the compiler compiled without a frame chain. It is the same skill as reading the fault report that a hung-task detector produces.

Reading a report

A lockdep report is long, and the useful part is at the top: the class names and the direction of the offending edge. A class is named after the stringified expression used at its initialisation, so the printed names read as variables or as access paths into structures, and a trailing suffix distinguishes subclasses of the same lock. Below that, each existing edge is printed with the stack trace that created it, most recent first, which shows the call path that established the order.

The most common resolution is that one of the two paths does not need to hold its lock across the other acquisition. Shortening the critical section removes the edge and the cycle with it, and it is usually the right fix because the lock was being held for longer than the invariant required. The second most common is a genuine ordering violation that requires reordering the acquisitions on one path. The annotations that suppress a report (declaring that two classes may be taken in either order) are the last resort, because they remove the validator’s ability to check that pair permanently, and a later change that makes the cycle real will produce no report at all.