Chapter 19: Multicore and Atomics

With more than one CPU, two pieces of code really do run at the same time against the same memory. You need operations that complete as one indivisible step, and a way to say which other memory accesses must be visible before or after them. This chapter covers what @mode(freestanding) provides for that:

• the atomic intrinsics — bare-name functions that need no import;
• memory ordering, with the C11 numbering the intrinsics use;
• building a spin lock, a ticket lock and once-only initialization from them;
• the mistakes these intrinsics invite, and what is not available.

Chapter 24 covers synchronized classes and @lockOrder, which build locks on top of these primitives and let the compiler check lock ordering.

The atomic intrinsics

Freestanding code gets a fixed family of atomic operations as compiler intrinsics: they are always in scope, need no import, and lower directly to the target's atomic instructions (Language Reference §3-3.4.2).

Each 64-bit operation has a 32-bit twin (atomicLoadU32, atomicStoreU32, atomicFetchAddU32, atomicFetchSubU32, atomicCompareExchangeU32). addr is the address of a naturally aligned cell — 8 bytes for the U64 forms, 4 for U32 — and a misaligned address is undefined behaviour. Every intrinsic returns a uint64; the U32 forms zero-extend their result.

The address of a module-level variable comes from addressOf(name). It accepts exactly that: a bare name of a module-level var or let. A local or a field has no stable address to give, so put shared atomic cells at module level (or in memory whose address you computed, such as a lock-word array).

@mode(freestanding)

const RELAXED: int = 0
const ACQUIRE: int = 2
const RELEASE: int = 3
const SEQ_CST: int = 5

# Packets received, counted by every CPU's network interrupt.
var packetsReceived: uint64 = 0

func countPacket(): void {
    let _old = atomicFetchAddU64(addressOf(packetsReceived), 1u64, RELAXED)
}

func packetTotal(): uint64 {
    return atomicLoadU64(addressOf(packetsReceived), RELAXED)
}

Listing 19-1: A counter shared by all CPUs

RELAXED is enough here: the counter only has to be exact, and no other data is published through it. The next section explains when it is not enough.

The hosted atomics modules are not available

Coming from hosted Loup, or from Rust's core::sync::atomic, you may look for an atomics module to import:

@mode(freestanding)

from core.atomic import (fetchAdd, Ordering);

var packetsReceived: uint64 = 0

error[E0001]: `@mode(freestanding)` module cannot import `@mode(host.scripted)` module
 --> src/main.lpfree:3:1
  |
3 | from core.atomic import (fetchAdd, Ordering);
  | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  |

core.atomic is a hosted module whose operations work on a SharedBuffer, and the shipped native.atomic is a host.native module (x86-64 fence helpers only). A freestanding file can import neither. The intrinsics above are the freestanding atomics.

⚠ Planned. The Language Reference lists a typed native.atomic module for freestanding code — load[T], store[T], compareExchange[T], fetchAdd[T], fetchSub[T], fence(), readInterruptFlags()/writeInterruptFlags(), hwFence(MemoryOrder) (§3-3.20). None of it is available in freestanding code in 1.25. Use the intrinsics, irqSaveDisable/irqRestore for the interrupt flags (chapter 16), and an asm barrier for device ordering (chapter 15).

Memory ordering

An atomic operation is indivisible, but that alone does not make other memory accesses visible in the right order. Both the compiler and weakly ordered CPUs (AArch64, RISC-V) may move ordinary loads and stores across an atomic operation unless the operation says otherwise. The last argument of every intrinsic says how much ordering it imposes, using the C11 / GCC __ATOMIC_* numbers:

Give the numbers names, as the listings in this chapter do. A backend may make an ordering stronger but never weaker: the self-hosted LLVM backend currently performs every atomic except atomicFence as seq_cst, while Stage0's backends honour the argument. Pass 5 unless you have chosen something weaker on purpose.

The pattern that needs acquire and release is publishing data. One CPU writes some ordinary memory and then sets a flag; another CPU sees the flag and reads the data. The writer's flag store must be a release, so the data writes cannot move after it; the reader's flag load must be an acquire, so its data reads cannot move before it. Together they guarantee that a reader who sees the flag also sees the data.

# A one-message mailbox from the boot CPU to a secondary CPU.
var mailbox: buffer[uint64, 4];
var mailboxFull: uint64 = 0

func post(entry: uint64, stackTop: uint64, cpuId: uint64, flags: uint64): void {
    mailbox[0] = entry
    mailbox[1] = stackTop
    mailbox[2] = cpuId
    mailbox[3] = flags
    atomicStoreU64(addressOf(mailboxFull), 1u64, RELEASE)      # publish
}

func tryReceive(edits out: buffer[uint64, 4]): bool {
    if (atomicLoadU64(addressOf(mailboxFull), ACQUIRE) != 1u64) {
        return false
    }
    out[0] = mailbox[0]                                          # sees what post() wrote
    out[1] = mailbox[1]
    out[2] = mailbox[2]
    out[3] = mailbox[3]
    atomicStoreU64(addressOf(mailboxFull), 0u64, RELEASE)      # the slot is free again
    return true
}

Listing 19-2: Publishing data with a release store and an acquire load

With RELAXED on either side the program still compiles and usually works on x86_64, whose stores are not reordered with each other. On AArch64 or RISC-V the receiver can see mailboxFull == 1 and still read stale mailbox words.

atomicFence(order) is a stand-alone fence between CPUs, for when the ordering does not belong to one particular atomic operation. It orders memory as other CPUs see it; it is not a barrier for device registers (chapter 15).

The 32-bit forms return uint64

Because every intrinsic returns uint64, comparing a U32 result with a uint32 value mixes widths:

@mode(freestanding)

var cpusOnline: uint32 = 0

func allCpusUp(expected: uint32): bool {
    return atomicLoadU32(addressOf(cpusOnline), 2) == expected
}

error[E0001]: E_NUMERIC_TYPE_MISMATCH: mixed 'uint64' and 'uint32' operands for operator '==' — integer widths do not promote; convert one operand explicitly (`as uint32`)
 --> src/main.lpfree:6:12
  |
6 |     return atomicLoadU32(addressOf(cpusOnline), 2) == expected
  |            ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  |

Narrow the result explicitly (the value always fits, because the U32 forms zero-extend):

var cpusOnline: uint32 = 0

func allCpusUp(expected: uint32): bool {
    return (atomicLoadU32(addressOf(cpusOnline), 2) as uint32) == expected
}

Listing 19-3: Narrowing the result of a 32-bit atomic

A spin lock

A spin lock is a word that is 0 when free and 1 when held. Acquiring it is a compare-exchange from 0 to 1 with acquire ordering, retried until it succeeds; releasing it is a store of 0 with release ordering. Between attempts, spin on a plain load so that waiting CPUs do not keep stealing the cache line from the holder, and tell the CPU you are spinning (pause on x86_64, yield on AArch64).

var consoleLock: uint64 = 0

func cpuRelax(): void {
    asm { "pause" }            # x86_64; write `yield` on AArch64
}

func lockConsole(): void {
    while (atomicCompareExchangeU64(addressOf(consoleLock), 0u64, 1u64, ACQUIRE) != 1u64) {
        while (atomicLoadU64(addressOf(consoleLock), RELAXED) != 0u64) {
            cpuRelax()
        }
    }
}

func unlockConsole(): void {
    atomicStoreU64(addressOf(consoleLock), 0u64, RELEASE)
}

Listing 19-4: A test-and-test-and-set spin lock

Release the lock on every path out of the critical section, explicitly: a defer block is accepted but never runs in Loup 1.25 (chapter 4).

Compare-exchange returns a flag, not the old value

In C11 and Rust, a compare-exchange gives back the value it found, and code tests that value. Here the result is a success flag. Code written with the other habit compiles and misbehaves:

# Each set bit is a slot in use. Claim the lowest free slot; -1 when full.
var usedMask: uint64 = 0

func claimSlot(): int {
    while (true) {
        let current = atomicLoadU64(addressOf(usedMask), ACQUIRE)
        if (current == 0xFFFF_FFFF_FFFF_FFFFu64) {
            return -1
        }
        var bit = 0
        while (((current >> (bit as uint64)) & 1u64) != 0u64) {
            bit = bit + 1
        }
        let wanted = current | (1u64 << (bit as uint64))
        if (atomicCompareExchangeU64(addressOf(usedMask), current, wanted, SEQ_CST) == current) {
            return bit
        }
    }
}

Listing 19-5: A compare-exchange result tested as if it were the old value

Trace the first call on an empty table. current is 0, the exchange succeeds and returns 1, and 1 == 0 is false, so the loop goes round again. Slot 0 is now taken, but nobody owns it. On the second pass current is 1, the exchange claims slot 1, returns 1, and 1 == 1 is true: the caller gets slot 1, and slot 0 has leaked for good. For other values of current every success reads as a failure. The fix is to test the flag:

        if (atomicCompareExchangeU64(addressOf(usedMask), current, wanted, SEQ_CST) == 1u64) {
            return bit
        }

Listing 19-6: Testing the success flag

Spin locks and interrupt handlers

If an interrupt handler takes a lock that the interrupted code on the same CPU already holds, the handler spins forever: the holder cannot run until the handler returns. Any lock that a handler also takes must be held with interrupts masked:

func lockConsoleIrqSave(): uint64 {
    let token = irqSaveDisable()        # mask first, then spin
    lockConsole()
    return token
}

func unlockConsoleIrqRestore(token: uint64): void {
    unlockConsole()
    irqRestore(token)                   # unlock first, then unmask
}

Listing 19-7: Holding a lock with interrupts masked

A ticket lock

A plain spin lock is unfair: under contention, one CPU can win the lock again and again. A ticket lock serves waiters in arrival order. Each CPU takes the next ticket with a fetch-add and waits until the "now serving" counter reaches it; unlocking advances the counter.

var nextTicket: uint64 = 0
var nowServing: uint64 = 0

func ticketLock(): void {
    let mine = atomicFetchAddU64(addressOf(nextTicket), 1u64, RELAXED)
    while (atomicLoadU64(addressOf(nowServing), ACQUIRE) != mine) {
        cpuRelax()
    }
}

func ticketUnlock(): void {
    let _served = atomicFetchAddU64(addressOf(nowServing), 1u64, RELEASE)
}

Listing 19-8: A FIFO ticket lock

atomicFetchAddU64 returns the old value, which is exactly "my ticket". Both counters wrap at 2⁶⁴, which no kernel reaches.

Initializing something once

Code that may first run on any CPU — building a lookup table, probing a device — needs to run its setup exactly once, with every other CPU waiting until it is done. Three states and a compare-exchange are enough:

const INIT_NONE: uint64 = 0u64
const INIT_RUNNING: uint64 = 1u64
const INIT_DONE: uint64 = 2u64

var tablesState: uint64 = 0

func buildTables(): void {
    # ... fill the tables ...
}

func ensureTables(): void {
    if (atomicLoadU64(addressOf(tablesState), ACQUIRE) == INIT_DONE) {
        return                                          # the fast path
    }
    if (atomicCompareExchangeU64(addressOf(tablesState), INIT_NONE, INIT_RUNNING, ACQUIRE) == 1u64) {
        buildTables()                                   # this CPU won
        atomicStoreU64(addressOf(tablesState), INIT_DONE, RELEASE)
        return
    }
    while (atomicLoadU64(addressOf(tablesState), ACQUIRE) != INIT_DONE) {
        cpuRelax()                                      # another CPU is building
    }
}

Listing 19-9: Once-only initialization

The release store of INIT_DONE publishes everything buildTables wrote, and every acquire load that sees INIT_DONE sees those writes.

What is not available

• Mutex[T], RwLock[T], condition variables, semaphores. These need a scheduler that can block a thread. Hosted Loup has them as compiler built-ins; freestanding code has no runtime behind them. The 1.25 checker does not reject Mutex.new(...) in a freestanding file, so this is a rule you keep. Use the locks in this chapter, or synchronized classes (chapter 24); blocking primitives belong to your own scheduler.
• Atomics on Cortex-M. The U64 forms are refused on every Cortex-M target (M-profile has no 64-bit exclusive load/store), and every atomic is refused on thumbv6m (Cortex-M0/M0+). The compiler reports these at build time rather than calling a library routine that does not exist. On a single-core microcontroller, use InterruptGuard (chapter 16) instead.
• Atomic operations on structs. Only 32- and 64-bit integer cells are atomic. Protect anything larger with a lock.

Summary

• The atomic intrinsics — atomicLoad/Store/FetchAdd/FetchSub/CompareExchange in U64 and U32 forms, plus atomicFence — need no import and take an address from addressOf(moduleVariable).
• The last argument is the C11 ordering number (0 relaxed, 2 acquire, 3 release, 4 acq_rel, 5 seq_cst). Publish data with a release store and read it after an acquire load. Pass 5 unless you chose otherwise.
• Every intrinsic returns uint64; narrow U32 results with as uint32 (E_NUMERIC_TYPE_MISMATCH otherwise).
• Compare-exchange returns 1 for success and 0 for failure, never the old value. Testing it against the expected value compiles and leaks or loses updates.
• Spin locks, ticket locks and once-only initialization are a few lines each. Mask interrupts while holding a lock that a handler also takes. Release explicitly; defer does not run in 1.25.
• core.atomic and native.atomic cannot be imported; the typed native.atomic API is planned. Hosted locks are not available. Cortex-M refuses 64-bit atomics.

Next: the standard library available to freestanding code.