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.

@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:

@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
    }
}

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:

    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:

@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):

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:

@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)
        }
    }
}

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:

@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:

@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)
    }
}

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.

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:

@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()
}

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:

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):

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.