Lock ordering invariants

Required reading before touching any lock nesting — authoritative source: docs/architecture/lock-ordering.md (INV-LOCK-*)

§1The global lock-order table

Level 0  IRQ (interrupt-disabled state)
Level 1  preempt (the preemption counter)
Level 2a GRQ (the global run queue)
           ├─ Level 3a  zone (buddy)
           └─ Level 3b  futex buckets → Level 4  wait slots
Level 2b the process tree    Level 2c  inode    Level 2d  dcache
  • Same-level branches (2a/2b/2c/2d) never nest; vertical acquisition only from lower to higher numbers.
  • SleepMutexes sit outside the layers: VFS_MUTATION_LOCK → EXT4_BIG_LOCK is the only legal sleeping-lock order (INV-LOCK-8).
  • virtio: read this page and the in-source comments before touching any virtio path — net's one-way {rx|tx}_queue → stats order (INV-LOCK-6) was once proven by an AB-BA of two CPUs spinning against each other.

§2Named invariants (INV-LOCK-*)

IDContent
INV-LOCK-5/6driver-queue locks → stats locks, one way; watchdog-guarded (a poll holding stats across refill once spun two CPUs against each other)
INV-LOCK-7per-mm PTE locks: a global epoch (RwSpinlock reads) + per-mm spinlock split mode; ordered after vma_manager, before page_desc; uniform across the three architectures
INV-LOCK-8the only sleeping-lock order: VFS_MUTATION_LOCK → EXT4_BIG_LOCK
INV-LOCK-PI-1the new PI-futex class: plain buckets → PI buckets → PI pool slots

§3Typed lock keys (divergence D-11): nesting is a compile-time fact

  • Zero-sized key types (GrqKey / FutexBucketKey / NetQueueKey / WaiterSlotKey…); the nesting relation is a CanNestInside trait-impl table.
  • The outer guard casts a NestProof; the inner lock_nested(&proof) consumes it — reverse acquisition does not compile, zero runtime cost.
  • Cautionary tale: the first GRQ protocol wrapper let lock()'s returned guard drop as a bare statement, so no critical section was mutually excluded — withdrawn after a 13-boot paired measurement; both keyed guard types are now #[must_use] and protocol callers use lock_claim().
  • Adopted by: the GRQ itself, the futex HASH_HEADS buckets, the WAITER_POOL slots (futex_wake's wakeup chain asks for the proof at every hop).

§4The runtime guard net

  • Four SPIN models: futex_wait_wake / lock_ordering / interrupt_preempt / sched_enqueue_dequeue — make spin.
  • The S-1 loom/Kani mirror: the SleepMutex state machine proves INV-M1..M5; it caught a real pid-0 recursion bug within its first 90 seconds of operation.
  • The spinlock watchdog (debug=watchdog, legacy): deadlock warnings trigger a full task snapshot automatically, output carries the key name.
  • census + heal: per-task per-field tick observation, phantom-preempt adjudication after 200 ticks; model-vs-reality MISS=0 (64.5k/52.1k heals measured).
  • allocwatch: cross-CPU lock-holder naming (the waiter cannot self-report — printing allocates, and it is stuck inside the allocator).

§5Lock-semantics policy

Lock/synchronization-primitive semantics follow Linux exactly; nothing is invented here. "A non-sleeping caller holding the lock" is fixed at the call site (trylock/deferral), never by changing the lock's path. Fairness experiments (e.g. "spin 2 s then steal") were adjudicated and rejected — those branches never merge.