# Chapter 24: `synchronized` Classes and Lock Ordering Chapter 19 built spin locks by hand from atomic intrinsics. They work, but nothing ties the lock to the data it protects, nothing stops code from touching that data without the lock, and nothing notices when two CPUs take two locks in opposite orders and deadlock. This chapter covers the language features that close those gaps in `@mode(freestanding)` (Language Reference §3-2.4.13): - `synchronized` classes, whose `modifier` methods run under a lock the compiler inserts; - the rule that a `synchronized` class's mutable state is only touched inside `modifier` methods; - `@lockOrder(n)`, which makes the compiler reject lock acquisitions in the wrong order; - `attachLock(addr)`, for one lock word per instance — per CPU, for example; - plain classes with explicit `acquire()`/`release()` under the same ordering check; - trimming the cost of a lock's hot path. ## A `synchronized` class In freestanding code, a `synchronized class` gets one lock word for the whole class: a compare-and-swap lock, taken at the start of every `modifier` method and released when it returns. Methods that are not `modifier` do not take it. There is no runtime involved; the lock is a few instructions the compiler puts around each `modifier` body. ```loup @mode(freestanding) # The tasks ready to run on this CPU. @lockOrder(10) synchronized class RunQueue { var count: uint64 = 0; var tasks: buffer[uint64, 64]; pub modifier func wake(tid: uint64): bool { if (this.count == 64u64) { return false } this.tasks[this.count as int] = tid this.count = this.count + 1u64 return true } pub modifier func next(): uint64 { if (this.count == 0u64) { return 0u64 # 0: nothing to run } this.count = this.count - 1u64 return this.tasks[this.count as int] } } var runQueue: RunQueue; func wakeTask(tid: uint64): bool { return runQueue.wake(tid) } ``` *Listing 24-1: A run queue whose methods run under a lock* `var runQueue: RunQueue;` declares a module-level instance with every field at its default, without a constructor call; that is how the boot-tested kernels declare their locked objects. Callers just call the methods: `runQueue.wake(tid)` needs no `safe { }` block, because the lock provides the exclusion at run time. Because there is one lock word per class, two instances of the same class exclude each other even though they share no data. That is correct but can be slow; `attachLock`, later in this chapter, gives each instance its own word. Two restrictions from the platform: the lock is a 64-bit compare-and-swap, so `synchronized` classes are refused on Cortex-M targets (use `InterruptGuard` on a single core there, chapter 16); and the lock does not mask interrupts (see "Locks and interrupt handlers" below). ## State is only touched under the lock The lock is held only inside `modifier` methods, so the compiler insists that a `synchronized` class's `var` fields are read and written only there. A getter written the ordinary way is rejected, because its read could tear against a concurrent `wake`: ```loup,does_not_compile @mode(freestanding) @lockOrder(10) synchronized class RunQueue { var count: uint64 = 0; var tasks: buffer[uint64, 64]; pub modifier func wake(tid: uint64): bool { if (this.count == 64u64) { return false } this.tasks[this.count as int] = tid this.count = this.count + 1u64 return true } pub func length(): uint64 { return this.count } } ``` ```text error[E_MODIFIER_REQUIRED]: E_MODIFIER_REQUIRED: reading `var` field 'count' of `self` in non-`modifier` method 'length' of `synchronized` class 'RunQueue' is unsynchronized; declare the method `modifier` so the read occurs under the lock --> src/main.lpfree:18:16 | 18 | return this.count | ^^^^^^^^^^ | ``` The same error, worded for a write, comes from a non-`modifier` method that assigns a field. The fix is to make the method `modifier`, so it runs under the lock: ```loup #~ @mode(freestanding) #~ #~ @lockOrder(10) #~ synchronized class RunQueue { #~ var count: uint64 = 0; #~ var tasks: buffer[uint64, 64]; #~ pub modifier func length(): uint64 { return this.count } #~ } ``` *Listing 24-2: Reading guarded state under the lock* When a racy read really is acceptable — a statistics counter shown on a debug console, where a slightly stale value does no harm — say so with an `unsafe("reason") { … }` region; the compiler then accepts the read without the lock: ```loup #~ @mode(freestanding) #~ @lockOrder(12) synchronized class Stats { var wakeups: uint64 = 0; pub modifier func countWakeup(): void { this.wakeups = this.wakeups + 1u64 } pub func approximateWakeups(): uint64 { var n: uint64 = 0u64 unsafe("stats: a racy read is fine for a debug display") { n = this.wakeups } return n } } ``` *Listing 24-3: An acknowledged unsynchronized read* `let` fields never change after initialization, so any method may read them. A `pub var` field would let code outside the class change the state with no lock at all; the compiler warns about it (here for a class `Counter` that declares `pub var count`): ```text warning[E_PUB_VAR_ON_SYNCHRONIZED]: E_PUB_VAR_ON_SYNCHRONIZED: `pub var` field 'count' on `synchronized` class 'Counter' is accessible externally without the lock, bypassing synchronization; make it non-`pub` (private `var`, mutated via a `modifier`) or `pub let` if immutable ``` In freestanding code these rules apply to `synchronized` classes only; a plain class has no lock and may write its fields from any method (chapter 10). ## `@lockOrder`: deadlock-free by construction A deadlock needs a cycle: CPU 0 holds lock A and waits for B, while CPU 1 holds B and waits for A. The classic discipline is a global order — every lock has a rank, and a CPU only takes locks in increasing rank. `@lockOrder(n)` writes the rank on the class, and the compiler checks the order: - Inside a `modifier` method of a class with rank A, the lock of rank A is held. - Calling a `modifier` method of a `synchronized` class with rank B while rank A is held is allowed only if B > A. Otherwise it is `E_LOCK_ORDER_VIOLATION`. - The check covers nested acquisitions inside one method body; ranks taken inside a separately checked callee are not carried back to the caller. Here a capability table (rank 20) wakes the task that held a revoked capability by calling into the run queue (rank 10) while it still holds its own lock: ```loup,does_not_compile @mode(freestanding) @lockOrder(10) synchronized class RunQueue { var count: uint64 = 0; var tasks: buffer[uint64, 64]; pub modifier func wake(tid: uint64): bool { if (this.count == 64u64) { return false } this.tasks[this.count as int] = tid this.count = this.count + 1u64 return true } } @lockOrder(20) synchronized class CapTable { var owners: buffer[uint64, 128]; # the task holding each capability; 0 = free pub modifier func revokeAndWake(cap: int, edits rq: RunQueue): void { let owner = this.owners[cap] this.owners[cap] = 0u64 if (owner != 0u64) { let _queued = rq.wake(owner) } } } ``` ```text error[E_LOCK_ORDER_VIOLATION]: E_LOCK_ORDER_VIOLATION: calling 'wake' on a synchronized class (lockOrder=10) while a lock with rank 20 is held — nested lock acquisition must be strictly ascending --> src/main.lpfree:26:27 | 26 | let _queued = rq.wake(owner) | ^^^^^^^^^^^^^^ | ``` If some other path takes the run-queue lock and then the capability lock, two CPUs can deadlock; the compiler rejects the descending acquisition no matter whether that other path exists yet. There are two fixes. Either the ranks are wrong — if the capability table really must be locked first, give it the lower rank — or the nesting is unnecessary. Here it is: the table only has to report *which* task to wake, and the caller can wake it after the table's lock is released. Taking locks one after another, with a release in between, is always allowed: ```loup #~ @mode(freestanding) #~ #~ @lockOrder(10) #~ synchronized class RunQueue { #~ var count: uint64 = 0; #~ var tasks: buffer[uint64, 64]; #~ #~ pub modifier func wake(tid: uint64): bool { #~ if (this.count == 64u64) { #~ return false #~ } #~ this.tasks[this.count as int] = tid #~ this.count = this.count + 1u64 #~ return true #~ } #~ } #~ @lockOrder(20) synchronized class CapTable { var owners: buffer[uint64, 128]; # Revoke a capability; returns the task that held it (0 if none). pub modifier func revoke(cap: int): uint64 { let owner = this.owners[cap] this.owners[cap] = 0u64 return owner } } var runQueue: RunQueue; var capTable: CapTable; func revokeAndWake(cap: int): void { let owner = capTable.revoke(cap) # rank 20, taken and released if (owner != 0u64) { let _queued = runQueue.wake(owner) # then rank 10: no nesting } } ``` *Listing 24-4: Acquiring locks one after another instead of nested* ### Rules that follow from the lattice - **No self-calls.** The lock is not reentrant, so a `modifier` that calls another `modifier` on `this` would wait for itself. The compiler reports it the same way, as holding rank A while acquiring rank A. Put the shared code in the calling method, or pass values to a plain helper function. - **Every class in a nested acquisition needs a rank.** A `modifier` that calls a `modifier` of another `synchronized` class when neither carries `@lockOrder` is rejected: ```loup,does_not_compile @mode(freestanding) synchronized class RunQueue { var count: uint64 = 0; pub modifier func wake(tid: uint64): void { this.count = this.count + 1u64 } } synchronized class TimerWheel { var expired: uint64 = 0; pub modifier func expire(edits rq: RunQueue, tid: uint64): void { this.expired = this.expired + 1u64 rq.wake(tid) } } ``` ```text error[E_LOCK_ORDER_MISSING]: E_LOCK_ORDER_MISSING: cross-object modifier call between 'TimerWheel' and 'RunQueue' requires `@lockOrder(n)` on both synchronized classes to prevent deadlocks --> src/main.lpfree:16:9 | 16 | rq.wake(tid) | ^^^^^^^^^^^^ | ``` Give every `synchronized` class that takes part in nested locking a rank. A practical scheme is to number by subsystem, leaving gaps (10 run queues, 20 capability tables, 30 the console…), so a new lock can be slotted in between. ## `attachLock`: one lock word per instance The per-class lock word serializes every instance. For per-CPU run queues that defeats the purpose: CPU 0 and CPU 1 should not wait for each other to touch their own queues. `instance.attachLock(addr)` points one instance's lock at a lock word you provide; its `modifier` methods then compare-and-swap that address instead of the class's shared word. An instance that never called `attachLock` keeps using the class word. ```loup #~ @mode(freestanding) #~ const SLOTS: int = 64 var rqLockWords: buffer[uint64, 4]; # one lock word per CPU var rqCount: buffer[uint64, 4]; # tasks queued on each CPU var rqTasks: buffer[uint64, 256]; # SLOTS task ids per CPU @lockOrder(10) synchronized class RunQueueLock { modifier func push(cpu: int, tid: uint64): bool { let n = rqCount[cpu] if (n == 64u64) { return false } rqTasks[cpu * SLOTS + (n as int)] = tid rqCount[cpu] = n + 1u64 return true } } func wakeOn(cpu: int, tid: uint64): bool { var lock: RunQueueLock; lock.attachLock(addressOf(rqLockWords) + (cpu as uint64) * 8u64) return lock.push(cpu, tid) } ``` *Listing 24-5: Per-CPU lock words with `attachLock`* Here the class carries no data at all: it is the lock and the code that runs under it, and the data lives in per-CPU tables. Each call makes a local instance, attaches it to that CPU's word, and runs `push` under it. This is the shape the toolchain's boot tests use for `attachLock`. Points to keep in mind: - `attachLock` is built into `synchronized` classes; on any other class it is an ordinary unknown method (`type 'Plain' has no method 'attachLock'`). - You own the lock words: they must stay at a fixed address, start at 0, and serve only as lock words. `attachLock` allocates nothing. - Ranks are per class, not per address. Two instances attached to different words still have the same rank, so one CPU may not hold its own run-queue lock while taking another CPU's — take them one after the other, or give the cross-CPU operation (load balancing) its own design. ## Explicit `acquire()` and `release()` Some locks do not fit a method body: a lock held across a sequence of calls, or one taken with interrupts masked (chapter 19). A plain — not `synchronized` — class with `@lockOrder(n)` and methods named `acquire` and `release` is checked by the same lattice: calling `acquire()` while a lock of rank n or higher is held is `E_LOCK_ORDER_ACQUIRE_VIOLATION`, and `release()` drops the rank. The check applies in any function, not only inside `modifier` methods: ```loup,does_not_compile @mode(freestanding) const ACQUIRE: int = 2 const RELEASE: int = 3 @lockOrder(30) class SpinLock { var wordAddr: uint64 = 0; pub modifier func place(addr: uint64): void { this.wordAddr = addr } pub modifier func acquire(): void { while (atomicCompareExchangeU64(this.wordAddr, 0u64, 1u64, ACQUIRE) != 1u64) { asm { "pause" } } } pub modifier func release(): void { atomicStoreU64(this.wordAddr, 0u64, RELEASE) } } @lockOrder(20) class PageLock { pub modifier func acquire(): void { } pub modifier func release(): void { } } var consoleWord: uint64 = 0 var consoleLock: SpinLock; var pageLock: PageLock; func logPageFault(): void { consoleLock.acquire() pageLock.acquire() # ... look up the faulting page, print it ... pageLock.release() consoleLock.release() } ``` ```text error[E_LOCK_ORDER_ACQUIRE_VIOLATION]: E_LOCK_ORDER_ACQUIRE_VIOLATION: acquiring lock with rank 20 while lock with rank 30 is already held — lock ranks must be strictly ascending --> src/main.lpfree:37:5 | 37 | pageLock.acquire() | ^^^^^^^^^^^^^^^^^^ | ``` Here the console lock (rank 30) is held while the page lock (rank 20) is taken. Take the page lock first, collect what you want to print, release it, and only then take the console lock: ```loup #~ @mode(freestanding) #~ #~ const ACQUIRE: int = 2 #~ const RELEASE: int = 3 #~ #~ @lockOrder(30) #~ class SpinLock { #~ var wordAddr: uint64 = 0; #~ #~ pub modifier func place(addr: uint64): void { #~ this.wordAddr = addr #~ } #~ #~ pub modifier func acquire(): void { #~ while (atomicCompareExchangeU64(this.wordAddr, 0u64, 1u64, ACQUIRE) != 1u64) { #~ asm { "pause" } #~ } #~ } #~ #~ pub modifier func release(): void { #~ atomicStoreU64(this.wordAddr, 0u64, RELEASE) #~ } #~ } #~ #~ @lockOrder(20) #~ class PageLock { #~ pub modifier func acquire(): void { } #~ pub modifier func release(): void { } #~ } #~ #~ var consoleWord: uint64 = 0 #~ var consoleLock: SpinLock; #~ var pageLock: PageLock; #~ func consoleInit(): void { consoleLock.place(addressOf(consoleWord)) } func logPageFault(): void { pageLock.acquire() # ... look up the faulting page; copy what will be printed ... pageLock.release() consoleLock.acquire() # ... print it ... consoleLock.release() } ``` *Listing 24-6: An explicitly managed spin lock under the lock-order check* `SpinLock` keeps the *address* of its lock word, because `addressOf` takes module-level variables only (chapter 19); `consoleInit` places it once at boot. Release explicitly on every path: `defer` does not run in 1.25 (chapter 4). ## Locks and interrupt handlers A `synchronized` lock, like a hand-written spin lock, does not mask interrupts. If an interrupt handler calls a `modifier` on a lock that the interrupted code on the same CPU holds, the handler spins forever. The compiler does not catch this: method calls inside interrupt-context code are not checked against `@interruptSafe` (§3-3.24.1). Either keep such locks out of handlers entirely — hand the work to the main loop through a ring (chapter 23) — or mask interrupts around every acquisition of that lock outside the handler (`irqSaveDisable`/`irqRestore`, chapter 16). ## Trimming the lock's hot path Freestanding functions zero their stack slots on entry, so a function never reads garbage from an uninitialized local. On a small hot function — a lock's acquire path, run on every critical section — that zeroing can cost more than the work. `@no_zero_locals` on a module-level function removes it for that function's frame (§3-3.16b): ```loup #~ @mode(freestanding) #~ #~ const ACQUIRE: int = 2 #~ var schedLockWord: uint64 = 0 @no_zero_locals func acquireSchedLock(): void { while (atomicCompareExchangeU64(addressOf(schedLockWord), 0u64, 1u64, ACQUIRE) != 1u64) { asm { "pause" } } } ``` *Listing 24-7: Skipping frame zeroing on a hot path* Use it only on short functions where you can see that every local is written before it is read; a read of an unwritten local then returns whatever was on the stack. It does not affect field defaults of a struct declared without an initializer, which are always materialized. On anything but a function it is rejected (`E_ANNOTATION_TARGET`). For a whole image, `[linker] size_opt = true` keeps the zeroing but emits it as one loop per function, which shrinks the code instead (chapter 18). ## Summary - A freestanding `synchronized class` has one compare-and-swap lock for the class, taken around every `modifier` method; declare instances as module variables (`var runQueue: RunQueue;`). Refused on Cortex-M. - Its `var` fields may only be read or written in `modifier` methods (`E_MODIFIER_REQUIRED`); an `unsafe("reason") { }` region acknowledges a deliberate racy read; `pub var` fields draw `E_PUB_VAR_ON_SYNCHRONIZED`. - `@lockOrder(n)` ranks locks: nested acquisition must strictly increase (`E_LOCK_ORDER_VIOLATION`, including self-calls); unranked nested locking is `E_LOCK_ORDER_MISSING`. Taking locks one after another is always allowed. - `instance.attachLock(addr)` gives an instance its own lock word, for example one per CPU; ranks stay per class. - A plain `@lockOrder` class with `acquire()`/`release()` is checked by the same lattice (`E_LOCK_ORDER_ACQUIRE_VIOLATION`). Release explicitly. - Locks do not mask interrupts, and calls from handlers are not checked; keep locks used by handlers masked everywhere else, or keep them out of handlers. - `@no_zero_locals` removes frame zeroing from a hot function; `size_opt` shrinks zeroing image-wide. This is the last chapter of the Freestanding Book. The Language Reference's compilation volume (§3-3) is the normative description of everything covered here; chapters 21 and 22 are the practical starting point for a kernel of your own.