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_LOCKis 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 → statsorder (INV-LOCK-6) was once proven by an AB-BA of two CPUs spinning against each other.
§2Named invariants (INV-LOCK-*)
| ID | Content |
|---|---|
| INV-LOCK-5/6 | driver-queue locks → stats locks, one way; watchdog-guarded (a poll holding stats across refill once spun two CPUs against each other) |
| INV-LOCK-7 | per-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-8 | the only sleeping-lock order: VFS_MUTATION_LOCK → EXT4_BIG_LOCK |
| INV-LOCK-PI-1 | the 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
CanNestInsidetrait-impl table. - The outer guard casts a
NestProof; the innerlock_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 uselock_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.