How can a lock-order analysis tool report a potential deadlock from a run in which no deadlock actually occurred, and what does it need to observe to do that?

## The four conditions, and which one is observable Deadlock requires mutual exclusion, hold-and-wait, no preemption, and **circular wait**. The first three are properties of the primitives you chose; the fourth is a property of the *order* in which code acquires locks. That fourth condition is the one a runtime tool can observe cheaply and generalize from, because acquisition order is visible on every single acquisition — not only on the rare ones that hang. This is the whole insight. Waiting for an actual deadlock to reproduce is hopeless: it needs two threads to be inside the narrow window at the same time. Watching acquisition *order* needs each path to run **once, independently**, possibly hours apart, possibly in different tests. ## Building the graph The tool instruments every acquire and release, and gives each thread a **held-lock stack**. On acquiring lock B while the stack contains A, it records the edge `A → B`. The graph is global and cumulative for the whole process lifetime. After adding an edge it checks for a cycle reachable through the new edge — in practice a bounded search, since the graph stays small. A cycle `A → B → A` means: somewhere, some thread held A and took B; somewhere else, some thread held B and took A. Nothing says those two ever ran concurrently. That is the point. The report is "your code contains an inconsistent lock order", which is a design defect independent of timing. Longer cycles matter too: `A → B`, `B → C`, `C → A` deadlocks with three threads, and no pair of code paths looks wrong in isolation. A graph finds these; a code reviewer usually does not. ## Classes, not instances If edges were keyed by individual lock objects, the graph would explode and reports would not generalize — you would learn that account #4471 and account #9902 can deadlock, which is a fact about data, not code. So tools key nodes by a **lock class**: the type, the allocation site, or an explicitly declared ordering class. This choice has a cost. Two instances of the same class taken in both orders produce a cycle even if the code provably orders them (the classic "lock both accounts, lower id first" transfer). Correct code, real report. Tools address this with: - **nested/subclass annotations** declaring that these two instances of the same class are ordered by a stated rule, - **explicit ordering ranks**, where each lock class is assigned a level and the tool checks that acquisition is monotonic in level, - **suppression lists** for reviewed cases. Ordering ranks are worth calling out: they turn the analysis from cycle detection into a much simpler invariant — never acquire a lock of rank ≤ the highest rank you already hold. That is checkable in constant time and is the design discipline you want anyway. ## Beyond plain mutexes Mature analyses extend the same graph to other wait relationships: a thread holding a lock while blocking on a condition, a queue, or an I/O completion; a lock taken both with interrupts enabled and inside an interrupt handler; a read-write lock taken for read while a writer waits, where a recursive read can deadlock against a queued writer. Each of these is another kind of edge added to the same cycle check. ## Limits The analysis inherits the dynamic-analysis limitation: an acquisition order in a code path that never executes is never recorded. Because it only needs each path to run *once* rather than needing them to interleave, its effective coverage is far better than schedule-dependent race detection — but it is still coverage-bound. A rarely-taken error path that grabs locks in the reverse order is exactly the classic production deadlock, and it is invisible until a test drives that error path. It also says nothing about deadlocks that do not involve lock cycles at all: a bounded thread pool where every worker blocks waiting on a task that only that pool can run, or two services waiting on each other's responses. Those are resource-exhaustion deadlocks; the lock graph is the wrong instrument for them. ## What good looks like Run the analysis in CI with tests that deliberately exercise error and cleanup paths (that is where reverse ordering hides), key nodes by class, adopt an explicit lock ranking for the handful of locks that are ever nested, and treat any new edge that creates a cycle as a build failure rather than a warning.