sysl.sync

Every declaration in sysl.sync, with its signature: the generated API page. This page is the argument — what the module is for, and how its pieces fit; that one is the list.

sysl.sync is two types and five names, and the most important thing about it is what it does not require. There is no requires clause on the module at all, so a program that has given up its allocator and its operating system can still reach every name in it:

@no_alloc
@no_os

import sysl.sync.*

var hits = Atomic(0)
var guard = SpinLock(0)

guard.lock()
hits.add(1)
guard.unlock()

print(hits.load(), guard.held)

1 0

That is the whole reason this module exists apart from sysl.threads. A word the processor can touch indivisibly is something a bare machine has; a thread is not, because creating one needs a scheduler underneath. A module’s capability requirement is module-wide, so putting one type that needed os in here would have taken Atomic[T] out of reach of the allocator, the scheduler, and the interrupt handler — the three pieces of code that need a lock before there is anything to schedule.

This is the *T tier of concurrency in the same sense *T is the unsafe tier of memory: nothing here is checked, everything is greppable, and it is how a kernel is written. What sits above it — Mutex[T], spawn, and the crossing rule — is on the sysl.threads page.

Ordering

An ordering is not a property of the value. Every ordering reads the same bits; what differs is the promise about what else is guaranteed to have happened around the read. That is why it is an argument rather than something fixed on the variable: the same word is read with Relaxed in a statistics counter and with Acquire in the handoff that publishes a structure, and only the operation knows which it is.

These are C11’s and LLVM’s, named the same way. Nothing here is sysl’s invention, so the standards text and the machine documentation a reader already has apply unchanged.

SeqCst is the strongest and the slowest, and it is what every method here defaults to, because it is the one that makes an ordinary program behave the way its author read it.

A load and a store take three of the five

A release publishes the writes that came before it, and a load makes none; an acquire sees what a release published, and a store reads nothing. So Release and AcqRel name loads that do not exist, Acquire and AcqRel name stores that do not exist, and no machine has an instruction for any of them. Ordering answers the question directly, which is what lets a wrapper taking an ordering as a value check it:

@no_alloc
@no_os

import sysl.sync.*

print(SeqCst.orders_a_load(), Release.orders_a_load(), AcqRel.orders_a_load())
print(SeqCst.orders_a_store(), Acquire.orders_a_store(), AcqRel.orders_a_store())

true false false
true false false

Read the two rows against each other: SeqCst is in both, and it is worth being clear that this is not a special case. It is stronger than an acquire rather than a release in disguise, and stronger than a release rather than an acquire in disguise, so it orders either operation. AcqRel is in neither, because it is exactly the ordering that asks for both halves at once.

This is a fact about what the operations are, not about any particular machine, and a stronger processor would not lift it.

The ordering is written at the call

Below Atomic[T] sit nine forms in the language’s raw tier, beside sizeof and ptr_cast. Each is one machine instruction that no sysl body could have written, and each takes an address:

atomic_load(p, ord)                  atomic_swap(p, v, ord)
atomic_store(p, v, ord)              atomic_cas(p, expected, desired, ord)
atomic_add / _sub / _and / _or / _xor(p, v, ord)
atomic_fence(ord)

The ordering on one of these has to be one of Ordering‘s names, spelled there, because it becomes a keyword in the emitted instruction rather than a value the instruction reads. An ordering held in a variable is well-typed sysl that cannot be lowered:

import sysl.sync.*

var q = Atomic(0)
var ord = Acquire

print(atomic_load(&q.v, ord))

'atomic_load' spells its ordering into the instruction, so it has to be one of Ordering's names written here — not a value carrying one. Where a caller chooses, branch on their choice and write a call per ordering

The last clause is the whole implementation strategy of the module above: each method on Atomic[T] is a match from the ordering it was given to the ordering it writes, one arm per name. That is also what core::sync::atomic does in Rust, for the same reason.

And it costs nothing. At every ordinary call the scrutinee is a constant, so the match folds away and the method call becomes the single instruction it names. Measured on AArch64 at -O1: a.add(1) is ldaddal, a.add(1, Relaxed) is ldadd, a.load(Acquire) is ldapr, and a.store(v, Release) is stlr.

The module is the gate

The five names live in sysl.sync and nowhere else, and none of the nine forms accepts a name a program declared for itself. So a program that never imported the module has no ordering it can write, and the raw tier is closed to it by the ordinary rules about names rather than by a rule of its own. Importing the type is not importing the names:

import sysl.sync.Atomic

var a = Atomic(0)

print(a.load(Relaxed))

undefined name 'Relaxed'

import sysl.sync.* is therefore the ordinary way to reach this module — there are eight names in it, five of them are orderings, and a program using Atomic or SpinLock almost always wants some of the five.

A fence has no wrapper, and the omission is deliberate

atomic_fence(ord) is the fence. It is a barrier the whole thread passes through rather than an operation on any one location, so there is no value for it to be a member of and nothing for a struct to hold. What a free function beside it could add is the default — and the default is what it could not survive, because Relaxed is refused:

import sysl.sync.*

atomic_fence(Relaxed)

a fence is nothing but its ordering, so 'Relaxed' would ask for a barrier that orders nothing — write 'Acquire', 'Release', 'AcqRel' or 'SeqCst', or drop the fence

A wrapper taking an Ordering would need a Relaxed arm, and the only two things that arm could do are call a form that refuses it or quietly do nothing. Softening that diagnostic is worse than writing the form out, so the form is what a program writes.

What no ordering reaches

The five orderings relate memory accesses to memory accesses, and nothing else. A kernel also orders memory against things that are not accesses: a write to a system register that raises an interrupt on another core, a translation-table walk, a TLB invalidation, a device in a wider shareability domain than the cores. No ordering — SeqCst and atomic_fence(SeqCst) included — says any of those, and on AArch64 the answer is a barrier, dsb(ishst) before the register write and the rest: System registers and barriers has the table. The compiler keeps program order around those forms; the barrier is what makes the processor keep it too.

Which instructions an atomic becomes is the build’s, not the call’s. An AArch64 core with the LSE extension does a read-modify-write in one instruction (ldadd, swp, cas), and without it in a load-exclusive/store-exclusive loop; an Armv8.0 row assumes the loop, and a project whose cores all have LSE says so in its manifest, codegen { extensions = ["lse"] } (packages). The orderings mean the same either way.

Atomic[T]

Atomic[T] is an ordinary struct with one field, and its methods take the address of that field and hand it to the forms above. There is nothing else to it, and that is the point: the type a program reaches for lives in the library where a reader can open it, rather than inside the compiler where they cannot.

@no_alloc
@no_os

import sysl.sync.*

var a = Atomic(0)

a.store(7)

var was = a.swap(9)

print(was, a.load())

7 9

Every method takes a *self receiver, including load — and that is worth stating, because a read looks like it should not need one. A self receiver is handed a copy of the struct, and the address of a copy is not the address the other threads are writing to. It would compile, it would be atomic, and it would read the wrong word.

Every read-modify-write answers what was there before

That is the property, and it is what makes an atomic increment usable as a ticket: every caller gets a different number and none of them is skipped.

@no_alloc
@no_os

import sysl.sync.*

var next = Atomic(0)
var t1 = next.add(1)
var t2 = next.add(1)
var t3 = next.add(1)

print(t1, t2, t3, next.load())

0 1 2 3

The same shape covers the bitwise members. or is how a flag is set in a word other threads are setting their own flags in, and the answer tells the caller whether it was the one that set it:

@no_alloc
@no_os

import sysl.sync.*

var flags = Atomic(0b1100)
var o = flags.or(0b0011)
var n = flags.and(0b0110)
var x = flags.xor(0b1111)

print(o, n, x, flags.load())

12 15 6 9

cas answers the value it found

Not a bool, and not an Option. A caller learns whether it swapped by comparing the answer against what it expected — one comparison it was going to make anyway — and on failure the answer is the value to retry against, so the whole retry loop is one line:

@no_alloc
@no_os

import sysl.sync.*

var slot = Atomic(1)
var seen = slot.load()

while slot.cas(seen, seen * 10) != seen
    seen = slot.load()

print(seen, slot.load())

1 10

Nothing else is running here, so the exchange succeeded the first time round and the body never ran — which is the ordinary case, and the reason the loop is worth writing this way rather than as a bool plus a second load.

Naming another ordering

An ordering on the surface is a parameter with a default, and this is the one place in the design where the ordering is not written at the raw call — it is written at this call, one level up:

@no_alloc
@no_os

import sysl.sync.*

var stats = Atomic(0)

for i in 0..<5
    stats.add(1, Relaxed)

print(stats.load(Acquire))

5

What T may be

An integer of 8, 16, 32 or 64 bits, or a pointer — what the machine has an instruction for, and on a 32-bit board that stops at 32 (below). Nothing in the declaration says so, and there is no bound that could: sysl’s integers are an open family, so u12 is a type a program may name and no impl list could have covered it. What refuses the type is the form inside, where the instruction would have had to be chosen:

import sysl.sync.*

var wide = Atomic(0u12)

print(wide.load())

'atomic_load' is one machine instruction, and a machine has one for 8, 16, 32 and 64 bits — u12 is 12, so there is nothing to emit

An aggregate is refused for a different reason and with a different message, because it is a different mistake — there is no width to round to, and what the author wanted was a lock:

import sysl.sync.*

struct Point
    x: i32
    y: i32

var here = Atomic(Point(1, 2))

print(here.load().x)

'atomic_load' reaches a word the machine can touch indivisibly — an integer of 8, 16, 32 or 64 bits, or a pointer — and Point is neither

A float is in the same position, and it is the one people are most surprised by — a real is 64 bits wide and there is still no instruction that loads one atomically as a float:

import sysl.sync.*

var f = Atomic(1.5)

print(f.load())

'atomic_load' reaches a word the machine can touch indivisibly — an integer of 8, 16, 32 or 64 bits, or a pointer — and real is neither. An aggregate is what a 'SpinLock' or a '&sync Mutex[T]' is for (`06`)

How wide is the build’s, too. Every 64-bit processor sysl targets, and 32-bit x86 and wasm, has a 64-bit atomic. A 32-bit Arm M-profile core does not — Armv7-M and Armv8-M stop at a 32-bit ldrex/strex, Armv6-M has no exclusive pair at all (below), and RV32’s atomics are a word — so there an Atomic[i64] would be a call into __atomic_fetch_add_8, which no board’s runtime defines. It is refused where the instruction would have been chosen, naming the target, and a usize or a pointer is the machine’s own word and always fits:

import sysl.sync.*

var ticks: Atomic[i64] = Atomic(0)

@export("tick")
tick() -> i64 = ticks.add(1, Relaxed)

'atomic_add' is one machine instruction, and 'thumbv7em-freestanding' has one for 32 bits at most — long is 64, so there is nothing to emit

The arithmetic members are refused on a pointer, and for a third reason again: an address plus a number is a question the raw tier does not answer.

import sysl.sync.*

var raw: *u8 = null
var ap = Atomic(raw)
var sum = ap.add(raw)

print(sum == null)

'atomic_add' is arithmetic, and what an address plus a number means is the question the raw tier does not answer — use 'atomic_swap' or 'atomic_cas' to change a pointer, or do the arithmetic on a 'usize' beside it

Read where those four diagnostics point. The caret is on a line in library/sysl/sync/atomic.sysl, not on the line the program wrote — because the form that refuses is inside the method, and the method is ordinary library sysl like everything else here. It is the honest place for it to land, and it is also the clearest demonstration on this page that Atomic[T] really is a struct somebody wrote rather than a type the compiler knows about.

The narrowing on load and store lands at run time

This is the one check in the module that does, and the reason is exactly the boundary the module sits on. The form refuses a releasing load where the name is written, and it cannot see a name that arrived in a variable — which is precisely what a method taking an Ordering hands it. So load and store carry a require over the two predicates above.

import sysl.sync.*

var a = Atomic(0)

print(a.load(Release))

That compiles, and the process traps when it runs: the contract clause lowers to a trap instruction, so there is no message and no unwinding, the shell reports signal 5, and anything still sitting in the output buffer never reaches the terminal. It folds away entirely wherever the ordering was written at the call, which is every ordinary use.

What the check buys is that an ordering that cannot be honoured stops the program rather than being quietly promoted to SeqCst. Promotion would be sound — it is strictly stronger — and it is not what the author asked for, which is the more useful thing to find out.

Reading the field directly

Atomic[T].v is not hidden, and that is deliberate rather than an oversight:

@no_alloc
@no_os

import sysl.sync.*

var done = Atomic(0)

done.store(1, Release)

print(done.v)

1

A thread that knows it is alone with the value — the one that built it, or the one left after every other has been joined — is entitled to the cheap read, and hiding it would only have meant a method doing the same thing less visibly. Everywhere else it is a data race, and it is greppable, which is the bargain the whole *T tier makes.

SpinLock

The lock a kernel has before it has a scheduler. Blocking means handing the processor to something else, which means there is something else to hand it to — and the allocator, the scheduler’s own run queue, and an interrupt handler are all code that has to take a lock before any of that exists.

@no_alloc
@no_os

import sysl.sync.*

var lk = SpinLock(0)
var first = lk.try_lock()
var second = lk.try_lock()

print(first, second, lk.held)

lk.unlock()

var third = lk.try_lock()

print(lk.held, third)

lk.unlock()
lk.lock()

print(lk.held)

lk.unlock()

true false 1
1 true
1

try_lock never spins and answers whether it took the lock; lock spins until it is free. Neither takes an Ordering and there is no overload that does, because a lock’s orderings are fixed by what a lock means: the exchange that takes it is an acquire, the store that frees it is a release, and that pairing is the whole of what makes the guarded data safe to touch.

Where the hold fits a block, with is the form to write: it takes the lock, runs a closure, releases the lock and answers what the closure answered, so the release cannot be forgotten or skipped by an early return. try_with is the same without spinning, answering None where the lock was held. The closure is a direct call, so both work under @no_alloc:

@no_alloc
@no_os

import sysl.sync.*

var lk = SpinLock(0)
val lp = &lk
var count = 0
val total = lk.with(() -> count + 41)
val busy = lk.with(() -> lp.try_with(() -> 1).is_none())

print(total, busy, lk.held)

41 true 0

lock and unlock stay for the hold a block cannot express — a scheduler’s run-queue lock taken on one thread and released on the next, after the switch. A spinlock hands out no address, so unlike Mutex[T] there is nothing the raw pair could let outlive the hold.

Three things it will not do for you

It guards nothing by construction. A spinlock is a flag beside the data, and what the data is stays the programmer’s to remember. That is the difference against Mutex[T], which owns what it protects — and it is deliberate, because the code that needs a spinlock is code that is also reaching through raw pointers, where a type that owned its contents would have nothing coherent to own.

Nothing checks that the releasing thread is the one that took it, or that it was held at all. That would be a second word to maintain on every take, paid by every correct program, to diagnose a bug the discipline below already asks the reader to hold to.

A thread that spins burns its processor for as long as it waits. So this is right only where the hold is short and bounded: a few instructions under the lock, no allocation, no system call, and above all no second lock. Where a wait may be long, or where the holder might be descheduled mid-hold, the answer is a Mutex[T] and a real blocking primitive underneath it. On one processor with no preemption a spin is a deadlock outright — nothing can release what nothing else is running to release.

Why the flag is not an Atomic[i32]

It is used as exactly that, and it is written as three raw calls anyway. SpinLock is declared in the same file as Atomic[T], and a lock whose entire implementation is three atomic operations reads better as those three than as a wrapper around a wrapper.

The implementation is worth reading for one detail, which is that lock does not spin on the exchange:

while atomic_swap(&self.held, 1, Acquire) != 0
    var busy = atomic_load(&self.held, Relaxed)

    while busy != 0
        spin_hint()
        busy = atomic_load(&self.held, Relaxed)

A read-modify-write has to take the cache line exclusively every time round, so waiters spinning on the exchange itself fight each other for the line — and worse, they fight the holder trying to write the release, which is the one thread whose progress everybody is waiting on. A relaxed load spins in a shared line and costs nobody anything, and spin_hint() on each round tells the processor that is what it is doing.

Armv6-M changes nothing atomically

An Armv6-M core — a Cortex-M0 or M0+ — reads and writes a word indivisibly, and that is all. It has no ldrex/strex, so load and store of up to 32 bits are a plain ldr and str with the barriers their ordering needs, and every read-modify-write — swap, cas, add and the rest — would be a call into __sync_*_4, which no board’s runtime defines. A program that reaches one is refused at its own call, a SpinLock included, since its flag is taken with an exchange:

import sysl.sync.*

var ticks: Atomic[u32] = Atomic(0)

@export("tick")
tick() -> u32 = ticks.add(1, Relaxed)

this reaches 'sysl.sync.Atomic.add', which changes memory with an atomic read-modify-write, and 'thumbv6m-freestanding' has no instruction for one — use an 'IrqLock' where the code runs on one core, or a board's hardware lock (the RP2040's SIO spinlocks) through 'Guarded[L, T]'

import sysl.sync.*

var guard: SpinLock = SpinLock(0)

@export("enter")
enter() = guard.lock()

'SpinLock' takes its flag with an atomic exchange, and 'thumbv6m-freestanding' has no instruction for one

The refusal is of what the program reaches, not of what the standard module holds: the module is built whole for every target, and its SpinLock is there on an M0+ for a program that never takes it.

IrqLock

Mutual exclusion on one Cortex-M core, held by masking interrupts. lock saves PRIMASK and runs cpsid i; unlock puts PRIMASK back as lock found it, so holds nest — an inner hold taken with interrupts already masked leaves them masked when it lets go. Nothing waits, so try_lock always answers true. It implements Lock, so the table of records that would be Guarded[SpinLock, T] elsewhere is Guarded[IrqLock, T] on an M0+:

import sysl.sync.*

var counts: Guarded[IrqLock, int] = Guarded.new(IrqLock(0), 0)

@export("on_tick")
on_tick() = counts.with((n) -> *n = *n + 1)

It excludes interrupt handlers, not other cores. A second core runs straight through it, so it is right only where everything that touches the data runs on the core taking the lock — the main loop and that core’s handlers. A dual-core part such as the RP2040 needs its hardware lock, which its own package provides as a Lock for Guarded[L, T].

It exists on every Cortex-M target — Armv6-M, Armv7-M and Armv8-M — and a program reaching it for any other machine is refused:

import sysl.sync.*

var l: IrqLock = IrqLock(0)

l.lock()
l.unlock()

'IrqLock' masks interrupts through a Cortex-M core's PRIMASK, and 'aarch64-macos' has none — it is for an Armv6-M, Armv7-M or Armv8-M core; elsewhere use a 'SpinLock', or a 'sysl.threads.Mutex[T]' where there are threads

spin_hint

Every machine with a pipeline worth the name has an instruction meaning “this loop is waiting for another processor”: yield on AArch64 and Thumb, pause on x86 and on RISC-V. spin_hint() is that instruction and nothing else, so it belongs in the body of every busy-wait:

import sysl.sync.*

var ready = Atomic(0)
var rounds = 0

ready.store(1, Release)

while ready.load(Acquire) == 0
    spin_hint()
    rounds += 1

print(rounds)

0

What it buys depends on the core: a core sharing its pipeline with another hardware thread hands that thread the cycles, a hypervisor may run another virtual processor, and an x86 core stops filling its pipeline with speculative loads it will have to throw away when the line finally changes. Where it means nothing it costs a few cycles. RISC-V’s pause belongs to the Zihintpause extension and is encoded as a fence that orders nothing, so a core without the extension runs it harmlessly; a wasm module has no such instruction, and there the call is empty.

It is not a wait. Nothing sleeps and no event is awaited — the loop still loads the word it is waiting on. AArch64’s wfe does sleep until the line changes, but only when the load in the loop is a load-exclusive that arms the monitor, which atomic_load is not; a kernel that wants it writes that loop in assembly.

It takes nothing:

import sysl.sync.*

spin_hint(4)

function 'sysl.sync.spin_hint' takes 0 arguments, but 1 argument was given

What is not here

volatile is not a synchronization tool, and the mistake is worth naming because C’s own reference material used to recommend the qualifier for shared variables. It constrains the compiler — it stops accesses being elided, merged, or reordered relative to one another — and says nothing about other cores, about ordering, or about tearing. It is for device memory and for nothing else. Two threads sharing a counter want Atomic[T]; a volatile counter is a race with a keyword in front of it.

&sync T is the language’s, not this module’s. The sigil that makes a reference’s refcount atomic is a spelling the compiler checks, and it lives on memory. It makes the reference safe to share and not the object safe to mutate — the fields are still mutable through any alias — so &sync Mutex[T] and &sync Atomic[i32] are how shared mutable state is actually reached.

The channel is sysl.threads, not this module, and the split is the one everything else here follows: a channel has to wait, so it needs a scheduler to sleep on, and this module requires nothing. What it is for is the message-passing half of the model — where the rule about which values may cross a domain boundary is asked of a value rather than of an address, which is the one place on that rule where the question was specification with nothing asking it.

Next: sysl.threads — spawning, joining, and the mutex above the spinlock.