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
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>
regionSharedRegionrequired

the region the ring lives in, as this process mapped it

basei32required

the 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>
regionSharedRegionrequired

the region the ring lives in, as this process mapped it

basei32required

the 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
regionSharedRegionrequired

the 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

slotsi32required

how many records the ring holds at once, a power of two from 2; anything else panics

slotBytesi32required

the 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
regionSharedRegionrequired

the 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

capacityi32required

the 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

returnsi32

how 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
capacityi32required

the ring's data bytes, as initSpscRing will be given them

returnsi32

how 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.