Lock debugging

Four defense lines against lock-ordering defects: compile-time lock keys, the runtime watchdog, model checking, and automated capture — each line's design, coverage and field records · Canonical doc: docs/architecture/lock-ordering.md (INV-LOCK-*), kernel/src/sync/, kernel/verify/

§1The lock-order hierarchy (the design-side input)

docs/architecture/lock-ordering.md maintains the named lock-order hierarchy (INV-LOCK-*): Level 0 IRQ → Level 1 preempt → Level 2a GRQ → Level 3a zone / 3b futex bucket → Level 4 waiter slot; SleepMutex sits outside the hierarchy; VFS_MUTATION_LOCK → EXT4_BIG_LOCK → I/O is the filesystem-side order; the INV-LOCK-8 rules constrain nesting details. Any new lock pair is named here first, then decides whether it earns a compile-time key.

§2Defense line 1: typed lock keys (D-11, compile time)

  • Mechanism: lock-order classes carry zero-sized key types (GrqKey, FutexBucketKey, NetQueueKey, NetStatsKey); a permitted nesting is an explicit impl CanNestInside<Outer> for Inner; a held guard mints a zero-sized NestProof, and acquiring the nested lock consumes the proof (lock_nested/lock_irqsave_nested) — without the impl it does not compile. Zero runtime cost (the key is PhantomData; the acquire paths inline to the raw protocol's instructions).
  • Covered slices: the GRQ lock itself (RawSpinlock→KeyedRawSpinlock<GrqKey>); the futex hash buckets + the wake chain (waking under the bucket lock with GRQ nested is the everyday path; the reverse is a machine-wide deadlock); the futex WAITER_POOL slot locks.
  • Field record (the 2b092c49 withdrawal incident): the first GRQ keying failed on an API-shape bug — KeyedRawSpinlock::lock() returns a guard, but a pre-existing bare self.lock.lock(); statement discarded it, and Drop released the lock at statement end: every "GRQ-held" section actually ran unexcluded (a 13-boot paired bisection: 6/6 x86 exitwalk boots panicked in the CFS timeline btree walk, riscv64 R74 double-run). Established in 623c4736, root-caused in 75dbf637; both keyed guard types are #[must_use] since; protocol wrappers never touch the guard-returning lock (the claim surface lock_claim/try_lock_claim/unlock). The incident is the working textbook for guard-ownership discipline.

§3Defense line 2: the spin watchdog (runtime)

  • RawSpinlock::DEADLOCK_WARN_ITERS = 100,000,000: past the spin threshold a warning prints (SBI-direct, independent of printk; cpu, lock address, ra).
  • dfx=watchdog: an automatic whole-task snapshot follows the warning (the taskdump path).
  • The compile-time feature dfx-lock-owner: one atomic store per lock/unlock; the warning carries holder=<cpu> + the holder task + the heap span + one REMOTE-BT cross-CPU stack capture per unique lock (via an IRQ_WORK IPI) — a holder stuck at IF=0 has a dead tick of its own and must be named by an observer.

§4Defense line 3: model checking and formal verification

  • SPIN (kernel/verify/spin/, 4 models: lock_ordering/futex_wait_wake/interrupt_preempt/sched_enqueue_dequeue): deadlock-freedom proofs over documented paths; the key nesting (INV-LOCK-5: bucket_lock → GRQ allowed, GRQ → bucket forbidden) is explicit in the model.
  • Kani: 164 #[kani::proof] harnesses prove the core unsafe code and protocol invariants for all inputs.
  • loom: an interleaving model check of the extracted SleepMutex state machine (8 scenarios) — within its first 90 seconds it caught a real pid-0 recursion defect (011a71c5); Kani proves INV-M1..M5.
  • Together the three cover the layers beyond "unnamed lock pairs + unmodeled paths": concrete paths by SPIN, concrete code by Kani, concurrent interleavings by loom.

§5lockdep-lite (runtime order recording: the honest status)

Linux's lockdep shape (a lock-class graph + runtime cycle detection) has this position in Rux: planned, not in main. The gap table (docs/development/dfx-align-plan.md) records Locking | lockdep-class | absent; P0 (a static lock-order registry + boot-time validation) and P1 (runtime acquire recording + cycle detection on new edges + two-lock-name/acquire-point splats) live on the implementation branch and will not merge before passing the gate. The three defense lines above are the actual coverage on main — stating this gap is itself part of observability honesty.

§6hunt-wedge: automated hang capture

./scripts/test/hunt-wedge.sh [rounds]   # 6 rounds default; stops on capture. exit 0=captured, 2=not reproduced
  • Builds a kernel with dfx-lock-owner automatically, then loops smoke + nettest + pipe-bomb workloads; watches two hang classes — class A: lock-deadlock warnings; class B: a pipe silent for >30 s.
  • On a hit, captures per-CPU registers/stacks/disassembly through the QEMU monitor into /tmp/rux-hunt/ and keeps that round's kernel.elf.
  • The three-step analysis: classify the hang from hunt.log → symbolize hunt.dump's pc=/ra= with addr2line -e /tmp/rux-hunt/kernel.elf -f -C → scan the stack words for kernel ra values to restore the call chain.

§7Working practices

  1. Suspect your own lock order first: when a deadlock is suspected, the first step is re-checking every acquire level of the call chain against lock-ordering.md — not blaming the hardware or the scheduler.
  2. Every new lock pair gets named: into the lock-ordering.md hierarchy; frequent, error-prone nesting pairs earn a compile-time key (D-11).
  3. Guard discipline: keyed-lock return values must bind (#[must_use] enforces it); protocol wrappers use the claim surface.
  4. Reading a warning: the watchdog's three facts = the spinning CPU, the lock address, the ra — the address identifies the object, the ra the acquire point; cross-locate the holder with the dfx-lock-owner holder line.
  5. Reproduction: THREAD=single make run for deterministic reproduction; hunt-wedge for automated injection.
Canonical doc: docs/architecture/lock-ordering.md (the full INV-LOCK table), docs/architecture/design-divergences.md D-11. Code: kernel/src/sync/ (spinlock/preempt/percpu), kernel/verify/ (spin/kani/loom). Observation: the lock event group + rux:spinwatch (see tracepoints); the dfx-lock-owner feature.