Reproduce and Diagnose Deadlock; Fix Using Lock Ordering

Topic Overview

Circular Waits

Deadlock needs four conditions simultaneously: mutual exclusion, hold-and-wait, no preemption, and circular wait. In practice you diagnose it by finding a cycle in the wait-for graph: A waits for B's lock, B waits for C, C waits for A.

Lock Ordering Prevention

Impose a global order on mutex acquisition:

• Assign each lock an integer rank
• A thread may only acquire higher ranks while holding lower ones
• Never lock L2 then L1 if rank(L1) < rank(L2)

For example, threads locking account_mutex before log_mutex never deadlock with threads following the same order, even when transferring funds and logging.

Why This Matters in Production

The dining philosophers deadlock Dijkstra formalized in 1965 has a very real modern descendant: database engines like MySQL's InnoDB detect exactly this kind of lock-ordering cycle at runtime and kill one transaction to break it, because the alternative is an indefinite hang. The global lock-ordering fix you implement here is the same discipline the Linux kernel's lockdep validator enforces to catch AB-BA deadlocks before they ship.

Debugging Checklist

Before you call the implementation done, walk failure modes on purpose. Test empty structures, single-element edge cases, maximum concurrency, and errno paths that must not crash the program. OS code usually fails in production when happy-path tests pass but invariants break under contention or memory pressure.

Implementation Notes

Keep structures small and name fields after kernel counterparts when possible. That lets you read man pages and kernel source side by side while you work. Print observable events during development; remove noisy logs once tests pass reliably.

For This Exercise

You will reproduce a two-thread deadlock, capture stack traces or logs, then fix it with ordered locking. The task asks you to document the cycle before and after the fix so the prevention strategy is explicit.

Your Task

Two tools diagnose lock deadlocks. The first is a wait-for graph: a thread waits for a mutex, the mutex is held by a thread, and so on. A cycle in that graph is a deadlock that has already happened. The second is lockdep, the Linux kernel's lock validator. It remembers every "held X, then took Y" order it has ever seen, and warns about an inversion before it deadlocks, the first time a thread takes the locks the other way round. Build both, driven by a sequence of lock operations.

Input

cCopy
Loading…

Threads and mutexes are created by name the first time they are mentioned, even by an operation that is then refused.

Rules

• lock a free mutex: acquire it. A held mutex: block, joining that mutex's FIFO of waiters. Relocking a mutex you hold gives EDEADLK, because mutexes are not recursive.
• unlock requires ownership (otherwise EPERM (not the owner)). The mutex passes straight to the first waiter, if there is one.
• lockdep. When a thread acquires M while holding H (including by hand-off), record the edge H -> M. If M can already reach H through recorded edges (a path of any length), warn once for that pair of locks.
• Deadlock check after every block: follow waiting thread → wanted mutex → owner → the mutex that owner waits for, and so on. If the chain returns to the thread that just blocked, report the cycle and mark everyone in it as deadlocked.
• A blocked thread cannot run: T is blocked, or T is blocked forever (deadlocked).

Output

cCopy
Loading…

The cycle is listed starting from the thread that just blocked. state lists mutexes in order of first use. The summary is always printed last. Any other operation prints unknown operation.

Example

Input:

cCopy
Loading…

Output:

cCopy
Loading…

Requirements

1. Store the learned order as a directed graph over mutexes, and search it for a path. Pairwise checks miss three-lock cycles.
2. Detect deadlock at the moment of blocking, by walking the wait-for chain. Never by timeouts.

Hidden tests cover a three-thread, three-lock cycle whose lockdep warning needs a transitive path, FIFO hand-off to several waiters, relocking, unlocking someone else's mutex, operations on blocked but not deadlocked threads, and unknown operations.