nish/sync/ring
Bounded lock-free queues of byte records in a shared region, for handing work between processes on different cores.
import {
MpscRing,
RING_EMPTY,
RING_TOO_SMALL,
SpscRing,
attachMpscRing,
attachSpscRing,
initMpscRing,
initSpscRing,
mpscRingBytes,
spscRingBytes,
} from "nish/sync/ring";
import { createRegion, openRegion } from "nish/sync/shm"
import { initSpscRing, attachSpscRing, spscRingBytes } from "nish/sync/ring"
const region = createRegion("jobs", spscRingBytes(65536)).expect("region")
const ring = initSpscRing(region, 0, 65536, true)
ring.tryPush(job, 0, toI32(job.length)) // false when full
// The other process opens the region by name and attaches:
const view = openRegion("jobs").expect("open")
const rx = attachSpscRing(view, 0).expect("ring")
const n = rx.popWait(buf, 0, 1000) // the record's length, or RING_EMPTY
attachMpscRing
The MpscRing an initMpscRing wrote at base; an error when there is none.
attachSpscRing
The SpscRing an initSpscRing wrote at base; an error when there is none.
initMpscRing
Writes an MpscRing's header at base and answers the ring: slots slots, a power of two from 2, of slotBytes each, a multiple of 8 from 8, and doorbell for popWait.
initSpscRing
Writes an SpscRing's header at base and answers the ring: capacity data bytes, a power of two from 8, and doorbell for popWait.
mpscRingBytes
The bytes an MpscRing of slots slots of slotBytes takes from its base: the 256-byte header and each slot's 16-byte head and payload.
spscRingBytes
The bytes an SpscRing of capacity data bytes takes from its base: the 256-byte header and the data.
MpscRing
Any number of producers, one consumer, records of at most slotBytes.
SpscRing
One producer, one consumer, records of any length.
Two rings
SpscRing has one producer and one consumer, and holds
records of any length up to its capacity back to back: a record costs its
length rounded up to 4, plus 4, and a record written with reserve may
leave padding at a lap's end (a skip marker, below). MpscRing takes any number of producers
and one consumer, in fixed slots of slotBytes each (Vyukov's bounded
queue: a producer claims a slot with a compare-exchange on the enqueue
position, and each slot's sequence number says whose turn it is). Neither
takes a lock, so a push or a pop in a busy ring is a handful of loads and
stores and no system call.
A ring lives at `base` in a `SharedRegion`
initSpscRing and
initMpscRing write its header there, which the process that creates the
region does once, before anyone attaches; attachSpscRing and
attachMpscRing read it in any other process (or the same one) and refuse
memory with no ring of that kind at base. spscRingBytes and
mpscRingBytes say how many bytes a ring takes from base, which is a
multiple of 64 so the header's counters each have a cache line. Several
rings may share a region at different bases.
In place
An SpscRing producer may write a record into the ring
itself instead of copying one in, and a consumer may read one there:
const w: u8[] = ring.reserve(n) // empty when there is no room now
copyBytes(w, 0, body, 0, k) // any u8[] writer, within w.length
ring.commit(k) // publishes w[0, k) as one record
const r: readonly u8[] = ring.peek() // the next record, in the ring
if (r.length > 0) {
use(r)
ring.release() // frees it for the producer
} else {
ring.tryPop(buf, 0) // none, or one peek cannot lend
}
A window is a SharedRegion.lend window: the ring keeps one for its producer
and one for its consumer and re-points them on every call, so neither path
allocates or makes a system call. commit, abandon and release give the
window back, which empties it: a reference kept past them indexes nothing
(each index panics) until the next reserve or peek re-points it, and then
sees that call's record.
A reserved record is always contiguous: when the rest of the lap is too
short, commit writes a skip marker there (a length word of -1, "the rest of
this lap is padding") and the record starts at the next lap. Every pop steps
over a marker.
A record tryPush wrapped across the end cannot be lent, so peek answers
an empty window for it and tryPop takes it, as it does for a record of
length 0. A reservation is at most capacity / 2 - 4 bytes, so a ring of 8
can never reserve (it panics) and one of 16 allows 4. The reserved bytes are
not zeroed: commit only what was written. A consumer that polls peek on a
doorbell ring has no wait call yet (popWait takes records, not windows).
The format keeps its magic
A ring no producer reserves into is
byte for byte what it was, and a consumer built before the marker that
meets one panics with "the ring is corrupt", never reads padding as a
record. Both ends of a ring are normally one build, so a new magic would
buy a clearer panic at the cost of every attach of an existing ring.
Who may call what is not checked
An SpscRing with two producers, or
either ring with two consumers, loses or repeats records; it never reads or
writes outside its region, because every access is a checked SharedRegion
access, and a length a broken peer wrote that cannot be a record's panics.
An MpscRing producer that dies between claiming a slot and filling it
stalls the consumer at that slot for good: a supervisor that restarts
producers makes a fresh ring.
The doorbell
A ring made with doorbell true lets the consumer sleep
instead of spinning: popWait spins a little, then says it is sleeping in
the header and sleeps on Linux's futex, and a push rings it only when that
flag is set (one SEQ_CST store and load on each side, so neither can miss
the other). A busy ring makes no system calls; an idle one makes two per
record, the consumer's wait and the producer's wake.
Without the doorbell a push is a release store and popWait answers
SHM_UNSUPPORTED, as it does off Linux, where the consumer polls tryPop.
popWait reads the monotonic clock for its deadline, so a program that
imports this module reaches the clock capability as well as ffi.
Private helpers share the importing program's flat symbol namespace
(docs/wp26-stdlib.md §3e), which is why each one carries the module's name.
Functions
attachMpscRing
The MpscRing an initMpscRing wrote at base; an error when there is
none. The magic is loaded ACQUIRE, which pairs with the RELEASE store
of it that the init function makes last.
const attachMpscRing: (
region: SharedRegion,
base: i32,
) => Result<MpscRing, string>
regionSharedRegionrequiredthe region the ring lives in, as this process mapped it
basei32requiredthe byte offset of the ring's header, a multiple of 64 inside the region; anything else panics, and so does a ring whose slots would run past the region's end
returnsResult<MpscRing, string>
a new MpscRing that starts from the consumer's position as the
header holds it now, or the reason there is no ring at base: no MPSC
magic, or a shape no initMpscRing writes
attachSpscRing
The SpscRing an initSpscRing wrote at base; an error when there is
none. The magic is loaded ACQUIRE, which pairs with the RELEASE store
of it that the init function makes last.
const attachSpscRing: (
region: SharedRegion,
base: i32,
) => Result<SpscRing, string>
regionSharedRegionrequiredthe region the ring lives in, as this process mapped it
basei32requiredthe byte offset of the ring's header, a multiple of 64 inside the region; anything else panics, and so does a ring whose data would run past the region's end
returnsResult<SpscRing, string>
a new SpscRing that starts from both positions as the header
holds them now, or the reason there is no ring at base: no SPSC magic,
or a capacity no initSpscRing writes
initMpscRing
Writes an MpscRing's header at base and answers the ring: slots
slots, a power of two from 2, of slotBytes each, a multiple of 8 from 8,
and doorbell for popWait. A ring already there is reset. The header and
every slot's sequence number are stored RELAXED and the magic last with
RELEASE, so an attach whose ACQUIRE load reads that store sees them
all. A reset ring had the magic already, so an attach racing a reset has
no such promise.
const initMpscRing: (
region: SharedRegion,
base: i32,
slots: i32,
slotBytes: i32,
doorbell: boolean,
) => MpscRing
regionSharedRegionrequiredthe region the ring lives in
basei32required
the byte offset of the ring's header, a multiple of 64 with
mpscRingBytes(slots, slotBytes) bytes of the region from it; anything
else panics
slotsi32requiredhow many records the ring holds at once, a power of two from 2; anything else panics
slotBytesi32requiredthe longest record, in bytes, a multiple of 8 from 8; anything else panics
doorbellbooleanrequired
whether a consumer's popWait may sleep on Linux's futex,
at the cost of a SEQ_CST store and load on every push
returnsMpscRing
a new MpscRing on the empty ring, for this process's producer
or consumer
initSpscRing
Writes an SpscRing's header at base and answers the ring: capacity
data bytes, a power of two from 8, and doorbell for popWait. The
memory is the creator's to give; a ring already there is reset. The header
is stored RELAXED and its magic last with RELEASE, so an attach whose
ACQUIRE load reads that store sees the header stored before it. A reset
ring had the magic already, so an attach racing a reset has no such
promise.
const initSpscRing: (
region: SharedRegion,
base: i32,
capacity: i32,
doorbell: boolean,
) => SpscRing
regionSharedRegionrequiredthe region the ring lives in
basei32required
the byte offset of the ring's header, a multiple of 64 with
spscRingBytes(capacity) bytes of the region from it; anything else
panics
capacityi32requiredthe ring's data bytes, a power of two from 8 (anything else panics); a record costs its length rounded up to 4, plus 4
doorbellbooleanrequired
whether a consumer's popWait may sleep on Linux's futex,
at the cost of a SEQ_CST store and load on every push
returnsSpscRing
a new SpscRing on the empty ring, for this process's producer
or consumer
mpscRingBytes
The bytes an MpscRing of slots slots of slotBytes takes from its base:
the 256-byte header and each slot's 16-byte head and payload. Nothing is
checked here; initMpscRing refuses a shape it cannot make.
const mpscRingBytes: (slots: i32, slotBytes: i32) => i32
slotsi32required
how many records the ring holds at once, as initMpscRing
will be given it
slotBytesi32required
the longest record, in bytes, as initMpscRing will be
given it
returnsi32how many bytes from the ring's base the region must hold
spscRingBytes
The bytes an SpscRing of capacity data bytes takes from its base: the
256-byte header and the data. Nothing is checked here; initSpscRing
refuses a capacity that is not a power of two from 8.
const spscRingBytes: (capacity: i32) => i32
capacityi32requiredthe ring's data bytes, as initSpscRing will be given them
returnsi32how many bytes from the ring's base the region must hold
Classes
MpscRing
Any number of producers, one consumer, records of at most slotBytes.
Make it with initMpscRing or attachMpscRing.
class MpscRing
| Member | |
|---|---|
new MpscRing(region: SharedRegion, base: i32) |
Reads the header of the ring at base: its shape, its doorbell and the consumer's position (an ACQUIRE load). It checks nothing; a program gets its ring from initMpscRing or attachMpscRing, which check the place and the magic first. |
head: i64 |
The consumer's position: records ever popped (this object's, as the consumer). |
popBatch(dst: u8[], lens: i32[]): i32 |
Moves up to lens.length records into dst, back to back from 0, while they fit, and sets lens[i] to each one's length: how many it moved. Unlike SpscRing.popBatch it costs what as many tryPops would: an ACQUIRE load and a RELEASE store per record. |
popWait(dst: u8[], off: i32, timeoutMs: i32): i32 |
SpscRing.popWait, for this ring: tryPop, but on an empty ring it polls briefly and then sleeps until a push rings the doorbell, for at most timeoutMs, checked between rounds of polling. A ring without a doorbell, or one off Linux, answers SHM_UNSUPPORTED after a round that finds nothing. |
tryPop(dst: u8[], off: i32): i32 |
Moves the next record into dst from off and answers its length: RING_EMPTY when there is none, RING_TOO_SMALL (keeping it queued) when it is longer than dst.length - off. The slot's sequence number is loaded ACQUIRE, and the slot is freed for the producers with a RELEASE store of it. |
tryPush(src: readonly u8[], off: i32, len: i32): boolean |
Queues src[off, off + len) as one record: false when every slot is taken now. A record longer than a slot panics. The producer claims a slot with a RELAXED compare-exchange on the enqueue position, after an ACQUIRE load of the slot's sequence number; it copies the record in and publishes it with one store of that number, RELEASE, or SEQ_CST followed by the doorbell check on a doorbell ring. |
SpscRing
One producer, one consumer, records of any length. Make it with
initSpscRing or attachSpscRing; each object keeps its own copy of the
position it owns and a cache of the other side's, so a push reads the
consumer's counter only when the ring looks full, and a pop the producer's
only when it looks empty.
class SpscRing
| Member | |
|---|---|
new SpscRing(region: SharedRegion, base: i32) |
Reads the header of the ring at base: its capacity and doorbell, and both positions (each an ACQUIRE load). It checks nothing; a program gets its ring from initSpscRing or attachSpscRing, which check the place and the magic first. |
capacity: i32 |
Data bytes, a power of two. |
head: i64 |
The consumer's position: bytes ever popped (this object's, as a consumer). |
seenTail: i64 |
The producer's position as this object, consuming, last loaded it: the cache a pop compares head with before it loads the producer's counter again. A snapshot, possibly behind the shared counter. |
abandon(): void |
Drops the open reservation, publishing nothing; panics without one. |
commit(len: i32): void |
Publishes the reserved window's first len bytes as one record, the store tryPush makes. The window is given back, so it is empty after. Panics without a reservation, for len outside [0, n], or when a push moved the window out of the ring. |
peek(): readonly u8[] |
The next record, lent in place as the ring's own bytes, without copying or blocking; release frees it for the producer. Empty (length 0) when there is none, and also for a record peek cannot lend: one tryPush wrapped across the end of the ring, or one of length 0. On an empty answer nothing is lent, and tryPop takes the record if there is one. Panics while a record is lent. The producer's position is loaded ACQUIRE when the cache says the ring is empty. |
popBatch(dst: u8[], lens: i32[]): i32 |
Moves up to lens.length records into dst, back to back from 0, while they fit, and sets lens[i] to each one's length: how many it moved. One load of the producer's position and one store of the consumer's, however many records it moves. Panics while peek has a record lent. The load is ACQUIRE and the store, made only when a record moved, is RELEASE. |
popWait(dst: u8[], off: i32, timeoutMs: i32): i32 |
tryPop, but on an empty ring it polls briefly and then sleeps until a push rings the doorbell, for at most timeoutMs in all (negative: no limit): RING_EMPTY only once that has passed. SHM_UNSUPPORTED for a ring without a doorbell, or off Linux, where the caller polls tryPop. Panics while peek has a record lent, from tryPop, so the message names tryPop. The deadline is checked between rounds of polling, so a wait can run past it by one round; a ring without a doorbell still polls one round before it answers SHM_UNSUPPORTED. |
release(): void |
Frees the record peek lent, the store tryPop makes, and gives the window back, so it is empty after. Panics when no record is lent. |
reserve(n: i32): u8[] |
A window of n bytes of the ring's own memory to write a record into, contiguous, without blocking: empty (length 0) when the ring has no room for it now. Nothing is published until commit; abandon drops it. n is from 1 (a window of 0 could not be told from no room; tryPush takes an empty record) to capacity / 2 - 4, so an empty ring always has room for one; outside that, or while a reservation is open, it panics. A ring of 8 has no such n and always panics; one of 16 allows 4. The bytes are not zeroed: they hold whatever the ring last held there. |
tryPop(dst: u8[], off: i32): i32 |
Moves the next record into dst from off and answers its length: RING_EMPTY when there is none, RING_TOO_SMALL (keeping it queued) when it is longer than dst.length - off. Panics while peek has a record lent. The producer's position is loaded ACQUIRE (only when the cache says the ring is empty), and the freed space is handed back with a RELEASE store of the consumer's position. |
tryPush(src: readonly u8[], off: i32, len: i32): boolean |
Appends src[off, off + len) as one record: false when the ring has no room for it now. A record longer than the ring could ever hold panics, and so does a call while a reservation is open. The bytes are plain copies, published to the consumer by one store of the producer's position: RELEASE, or SEQ_CST followed by the doorbell check on a doorbell ring. |
Constants
-1
RING_EMPTY: i32
tryPop, popWait: the ring is empty (or the wait ran out).
-2
RING_TOO_SMALL: i32
tryPop, popWait: the next record is longer than the room after off in dst; it stays queued.

