Skip to content
lockfree

lockfree/typestates/mpmc_pop

MPMC Pop operation lifecycle typestate (Vyukov per-slot sequence protocol).

State machine: Start -> SlotClaimed | Empty | Start (3-arm: claim succeeded / generation empty / retry) SlotClaimed -> T (terminal: read data + re-arm seq)

Key invariant: Once a slot is claimed via CAS on head, the data MUST be read and the per-slot seq MUST be advanced to pos + N (release). That release is the consumer->next-generation-producer happens-before edge.

Memory ordering follows Vyukov canonical: moRelaxed on the global head CAS (the per-slot seq does the data-ordering work), moAcquire on the seq load (pairs with producer's release at pos + 1), and moRelease on the seq store at pos + N (gates the next-generation producer).

Backoff: this verb returns the Start arm to signal "retry". The facade holds var spins = InitialSpin and calls backoffOnRetry(spins) between iterations on the Start arm.

Types

Section titled “Types”

MPMCPopStart

Section titled “MPMCPopStart”
MPMCPopStart[N] = object

Entry point. No data yet.

MPMCPopSlotClaimed

Section titled “MPMCPopSlotClaimed”
MPMCPopSlotClaimed[N] = object
  pos*: uint64
  slot*: PhysicalSlotN[N]

CAS on head succeeded - we own the slot at pos mod N. MUST read data and publish the seq advance (re-arm for next gen).

MPMCPopEmpty

Section titled “MPMCPopEmpty”
MPMCPopEmpty[N] = object

Terminal: queue was empty this generation (per-slot seq lags).

MPMCPopOpState

Section titled “MPMCPopOpState”
MPMCPopOpState = enum
  fsMPMCPopEmpty, fsMPMCPopSlotClaimed, fsMPMCPopStart

MPMCPopOpStates

Section titled “MPMCPopOpStates”
MPMCPopOpStates[N] = MPMCPopEmpty[N] | MPMCPopSlotClaimed[N] | MPMCPopStart[N]

MPMCPopClaimResultKind

Section titled “MPMCPopClaimResultKind”
MPMCPopClaimResultKind = enum
  mMPMCPopSlotClaimed, mMPMCPopEmpty, mMPMCPopStart

MPMCPopClaimResult

Section titled “MPMCPopClaimResult”
MPMCPopClaimResult[N] = object
  case kind*: MPMCPopClaimResultKind
  of mMPMCPopSlotClaimed:
    mpmcpopslotclaimed*: MPMCPopSlotClaimed[N]
  of mMPMCPopEmpty:
    mpmcpopempty*: MPMCPopEmpty[N]
  of mMPMCPopStart:
    mpmcpopstart*: MPMCPopStart[N]

MpmcBase

Section titled “MpmcBase”
MpmcBase[N; P; C; T] = object
  head* {.align: 128.}: Atomic[uint64]
  tail* {.align: 128.}: Atomic[uint64]
  cells*: MPMCCellArrayN[N, SlotEncoding(T)]

Procedures & Functions

Section titled “Procedures & Functions”

state

Section titled “state”
proc state[N: static int](f: MPMCPopEmpty[N]): MPMCPopOpState

Runtime state inspection for MPMCPopEmpty. Returns the enum value for pattern matching in case expressions.

state

Section titled “state”
proc state[N: static int](f: MPMCPopSlotClaimed[N]): MPMCPopOpState

Runtime state inspection for MPMCPopSlotClaimed. Returns the enum value for pattern matching in case expressions.

state

Section titled “state”
proc state[N: static int](f: MPMCPopStart[N]): MPMCPopOpState

Runtime state inspection for MPMCPopStart. Returns the enum value for pattern matching in case expressions.

$

proc `$`[N: static int](s: MPMCPopEmpty[N]): string

String representation for state ‘MPMCPopEmpty’. Returns the bare state name (no fs prefix).

$

Section titled “$”
proc `$`[N: static int](s: MPMCPopSlotClaimed[N]): string

String representation for state ‘MPMCPopSlotClaimed’. Returns the bare state name (no fs prefix).

$

Section titled “$”
proc `$`[N: static int](s: MPMCPopStart[N]): string

String representation for state ‘MPMCPopStart’. Returns the bare state name (no fs prefix).

$

Section titled “$”
proc `$`(s: MPMCPopOpState): string {.raises: [], tags: [], forbids: [].}

String representation of MPMCPopOpState enum. Strips the fs prefix for human-friendly output.

toMPMCPopClaimResult

Section titled “toMPMCPopClaimResult”
proc toMPMCPopClaimResult[N: static int](s: sink MPMCPopSlotClaimed[N]): MPMCPopClaimResult[
    N]

toMPMCPopClaimResult

Section titled “toMPMCPopClaimResult”
proc toMPMCPopClaimResult[N: static int](s: sink MPMCPopEmpty[N]): MPMCPopClaimResult[
    N]

toMPMCPopClaimResult

Section titled “toMPMCPopClaimResult”
proc toMPMCPopClaimResult[N: static int](s: sink MPMCPopStart[N]): MPMCPopClaimResult[
    N]

$

Section titled “$”
proc `$`[N: static int](r: MPMCPopClaimResult[N]): string

String representation of branching union ‘MPMCPopClaimResultN’. Returns the active branch’s bare state name.

start

Section titled “start”
proc start[N: static int](): MPMCPopStart[N] {.inline.}

Begin a pop operation.

tryClaim

Section titled “tryClaim”
proc tryClaim[N, P, C: static int; T](op: MPMCPopStart[N];
                                      queue: var MpmcBase[N, P, C, T]): MPMCPopClaimResult[
    N] {.inline, raises: [], tags: [TypestateOp, RootEffect].}

Vyukov consumer claim. Returns one of:

  • SlotClaimed: head CAS won; caller must call complete.

  • Empty: per-slot seq says producer hasn't written this generation yet. Caller returns false to user.
  • Start: CAS race or consumer raced ahead; caller backs off and retries.

complete

Section titled “complete”
proc complete[N, P, C: static int; T](op: MPMCPopSlotClaimed[N];
                                      queue: var MpmcBase[N, P, C, T]): T {.
    inline, notATransition.}

Read value from the claimed slot, then re-arm the seq for the next generation. The seq.store(pos+N, moRelease) is the consumer->next- producer edge; the next producer at virtual position pos + N will see this seq value via its acquire load and proceed to claim.

Note: the old protocol had a "fire-and-forget head advance" CAS here because head/reservedHead were separate. Vyukov has a single head cursor advanced by the claimant at C3, so no follow-up CAS is needed.

Templates

Section titled “Templates”

->

Section titled “->”
template `->`[N: static int](_: typedesc[MPMCPopClaimResult[N]];
                             s: sink MPMCPopSlotClaimed[N]): MPMCPopClaimResult[
    N]

->

Section titled “->”
template `->`[N: static int](_: typedesc[MPMCPopClaimResult[N]];
                             s: sink MPMCPopEmpty[N]): MPMCPopClaimResult[N]

->

Section titled “->”
template `->`[N: static int](_: typedesc[MPMCPopClaimResult[N]];
                             s: sink MPMCPopStart[N]): MPMCPopClaimResult[N]

Macros

Section titled “Macros”

match

Section titled “match”
macro match[N: static int](value: MPMCPopClaimResult[N]; arms: untyped): untyped

Pattern-match on a branching union; rewrites into a case over the kind discriminator. The value being matched must be a var binding. Branch fields are extracted with move(), which requires a mutable binding. Syntax is StateName(bind):, not of StateName as bind:.

match

Section titled “match”
macro match[N: static int](value: MPMCPopOpStates[N]; arms: untyped): untyped

Single-target pattern match on states of typestate ‘MPMCPopOp’; rewrites to block: let bind = move(value); body. Syntax is <StateName>(bind):, with exactly one arm.

MPMCPopOp

Section titled “MPMCPopOp”
macro MPMCPopOp(initial`gensym0: untyped; typeDef`gensym0: untyped): untyped

Typestate-attachment pragma (auto-generated; see §3.7 of the v0.9.0 design doc). Apply to a type declaration to bind the type to this typestate with initial as the starting state. Validates TA-002..TA-004 at compile time and populates typestateAttachments.