Cairn
data structures · concurrency · O(1) amortized per push/pop barring CAS retries, O(n) space, lock-free (not wait-free, not starvation-free)

↩ back to Concurrency

Treiber Stack

Six of this site's ten other Concurrency entries are software-only: two or more processes coordinating with nothing but ordinary shared-memory reads and writes. This site's own comparison guide already measured what all three mutual-exclusion algorithms lose to once a hardware compare-and-swap (CAS) instruction is available — a real, repeatable 10%–30% edge over Peterson's algorithm on a shared counter — but never built anything on top of that primitive. This page does: a stack with no lock at all, where push and pop each update a single shared head pointer with one CAS instead of acquiring anything. Devised by R. Kent Treiber in 1986, it's the textbook first example of a lock-free data structure, and the first Concurrency entry on this site built around a bug CAS itself introduces rather than one a busy-wait loop gets wrong. (The other three are this site's other CAS-based entries: the Michael-Scott Queue, a lock-free FIFO coordinating two pointers instead of this page's one; Hazard Pointers, which closes the forward reference this page's own Pitfalls section below leaves open; and the Harris Linked List, the first of the three to race over more than a fixed head/tail pointer.)

Same measure-don't-assume discipline as this site's other ten Concurrency pages: every claim below — that plain push/pop never corrupts the stack, and exactly what does — comes from exhaustively searching every reachable interleaving of a small state machine, not a handful of hand-picked traces.

Try it

Pick a scenario (how many push/pop operations each of two threads runs) and an allocator (does a freed node's identity ever get handed back out to a later push?), then either step through by hand — Step T0 / Step T1 run exactly one pending action for that thread — or press Explore all schedules to search every reachable interleaving at once. Try the Minimal (pop + pop-then-push) scenario with Recycling pool first — it's the smallest configuration that reproduces the ABA problem, in as little as 8 moves. Switch to No recycling with the same scenario and the bug vanishes completely, at every one of the same 59 reachable states.

Pick a scenario and allocator, then step each thread by hand.

Why it works

One shared variable, head — a reference to the top node, or null if the stack is empty — plus an ordinary singly-linked node per element (value and next). Both operations loop the same shape: read the current state, compute what the new state should be, then try to commit with a single compare-and-swap: "set head to this new value, but only if it still equals what I just read — otherwise tell me it failed and change nothing." push(v) allocates a new node with next set to the head it just read, then CASes head from that old value to the new node. pop() reads head, reads that node's own next, then CASes head from the old node to next. Either way, if the CAS fails — some other thread changed head first — the loop just rereads head and tries again. Nothing ever blocks: a thread that loses a CAS race didn't wait for anyone, it just did more work.

That's the structural difference from every other Concurrency page here: Peterson's algorithm, Dekker's algorithm, and Lamport's bakery algorithm all guarantee bounded waiting — a process trying to enter is guaranteed to get in within a bounded number of some other process's turns. A lock-free structure gives up that guarantee entirely in exchange for never blocking at all: "lock-free" only promises that some thread's CAS eventually succeeds when multiple threads are contending, not that every thread's does. In principle, one thread could lose every single race forever while others keep succeeding — lock-free is a weaker liveness property than the starvation-freedom Readers-Writers Problem's own fair-ticket fix achieves, not a stronger one. What it buys instead: no thread ever holds anything the way a lock is held, so there's no critical section for a scheduler to preempt a thread inside of — the exact pathology measured in Complexity below.

Plain push/pop correctness rests on one invariant, checked exhaustively rather than assumed: a CAS on head only ever succeeds when the node it names is still genuinely on top of the stack, because nothing else can make head equal that exact node again once it's been removed — every node a fresh push allocates is a new identity, and a popped node is never linked back in by this algorithm. The Pitfalls section below exists entirely because that second half of the invariant — "a removed node's identity never comes back" — is a promise about memory management, not about the CAS loop itself, and it's easy to break without touching a single line of push or pop.

Reference implementation

Pseudocode compareAndSwap(ref, expected, next) below stands for the real hardware primitive: atomically check whether ref still equals expected, and if so set it to next, reporting success or failure as one indivisible step — the only thing in this whole algorithm the scheduler can never interrupt midway.

let head = null; // shared

function push(value) {
  const node = { value: value, next: null };
  while (true) {
    const oldHead = head;        // read
    node.next = oldHead;         // compute
    if (compareAndSwap('head', oldHead, node)) return; // commit, or retry
  }
}

function pop() {
  while (true) {
    const oldHead = head;        // read
    if (oldHead === null) return EMPTY;
    const next = oldHead.next;   // read, captured now — not re-read at CAS time
    if (compareAndSwap('head', oldHead, next)) return oldHead.value; // commit, or retry
  }
}

The demo above runs this exact shape as a step-by-step state machine, with every read, every local computation, and the CAS itself as its own independently interleavable move — including the detail that makes Pitfalls possible: pop's local next is captured once, at read time, and never looked at again until the CAS either commits it or throws it away. Whatever happens to the real node in between is invisible to this thread until then.

Pitfalls

Plain push/pop, with every node a permanently fresh identity, never corrupts the stack — exhaustively confirmed, 0 corrupt states across every scenario tried. "Corrupt" here means either structural damage (the chain from head revisits a node, or runs into one that's already been freed) or a conservation failure (the values reachable from head, plus every value a completed pop already returned, stop matching the values that were ever present or pushed). With a No recycling allocator — every push gets a node identity that's never existed before, matching how a garbage-collected language like this site's own JavaScript actually behaves — all three scenarios below come back clean:

scenarioallocatorreachable statescorrupt statesshortest corrupting schedule
T0: pop · T1: pop, pushNo recycling510—
T0: pop · T1: pop, pushRecycling pool5918 moves
T0: pop · T1: pop, pop, push, pushNo recycling1550—
T0: pop · T1: pop, pop, push, pushRecycling pool179313 moves
T0: push · T1: pushNo recycling230—
T0: push · T1: pushRecycling pool230—

Switching to a Recycling pool allocator — handing a freed node's own slot back out to a later push, the way a manual allocator or a pooled-object optimization would — reproduces the classic ABA problem, in the smallest scenario tried. The name comes from the shape of the bug: a thread reads value A, the value changes to B and back to something that merely looks like A again while that thread wasn't looking, and its CAS can't tell the difference. The minimal reproduction (Minimal scenario, Recycling pool, starting stack head → A → B): T0 calls pop() and reads oldHead = A, next = B — then stalls, before its CAS. T1 calls pop() too, also reading oldHead = A (nothing has changed yet), and its CAS succeeds first: head becomes B, A's slot is freed, T1 returns A. T1 then calls push(X) — the allocator hands back A's own just-freed slot, so the new node X is A's old identity, reused: its next is set to the current head (B), and head becomes that reused identity. T0 now finally runs its CAS: head currently equals the identity T0 is still holding as oldHead — true, bit for bit, because it's literally the same slot — so the CAS succeeds, setting head to T0's stale next = B. Final state: X is unreachable (a successful-looking push, silently vanished) and both T0 and T1 report having popped A (a value handed out twice). Exhaustive search finds exactly 1 such corrupting schedule out of 59 reachable states, and it's reachable in as few as 8 moves — confirmed by running the exact shipped state machine, not a hand-simplified stand-in for it. The Larger scenario (one more pop/push round trip on T1's side) finds 3 corrupting schedules out of 179 states instead of 1, suggesting more churn after the stalled read gives more chances to recycle the exact identity T0 is still holding — not confirmed to scale linearly past these two data points, just the direction it moves in both tried so far.

The Two pushes only scenario stays at 0 corrupt states under either allocator, at every state tried — recycling alone is necessary but not sufficient. Nothing gets freed until a pop commits, so with no pop in the mix there's nothing for the allocator to hand back out in the first place, regardless of policy.

Two things worth being precise about, because this bug is easy to overstate. First, this is not a flaw in Treiber's algorithm — it's what happens when a lock-free CAS loop is combined with a memory-reuse policy that lets the exact same bit pattern mean two different things across time. A garbage-collected runtime can't reproduce the classic form at all: as long as T0's local oldHead reference keeps the original node reachable, the collector can't recycle its memory for anything else, by construction — which is exactly why the No recycling column above matches real JavaScript/Java/Go behavior, not a simplification of it. The bug only resurfaces if code built on top of the GC explicitly reintroduces address reuse anyway — a manual object-pool optimization recycling "freed" nodes for performance, or any non-GC'd language with a real allocator — which is common enough in practice that production lock-free structures guard against it deliberately (tagged pointers that bump a version counter on every reuse so a stale CAS can tell the difference, or deferring the actual free until no thread could still be holding a stale reference — hazard pointers and epoch-based reclamation are the two standard schemes). The first of those two is now built, on this exact bug: see Hazard Pointers, which re-runs both scenarios above and drops the corrupting-schedule count to 0 in each. The second, epoch-based reclamation, is now built too: see Epoch-Based Reclamation, which also drops both scenarios to 0 corrupt states — but comes with a real cost hazard pointers don't share, measured on its own page.

Complexity

Time: O(1) for the read-compute-CAS body of either operation, but with no bound on how many times that body retries under contention — unlike the six other Concurrency pages on this site built on ordinary reads and writes, which all guarantee bounded waiting, a lock-free structure (this page, the Michael-Scott Queue, Hazard Pointers, Epoch-Based Reclamation, and the Harris Linked List) only guarantees that some thread's attempt eventually succeeds, not this one's (see Why it works above). Space: O(n) for n live elements, one node each — identical footprint to an ordinary singly-linked stack, since the only addition is the CAS loop around two existing operations, not any new per-node bookkeeping.

Measured, not asserted, against a single global spinlock protecting the equivalent plain operations: two Node worker_threads each running 1,000,000 push-then-pop pairs through a shared SharedArrayBuffer node pool, median of 9–11 independent runs per configuration, same machine and discipline as the CAS-vs-Peterson's benchmark linked above. At one worker — no real contention at all — the lock-free version was consistently slower, by about 1.4x (two confirming runs, 108ms vs 153ms median): every push/pop here issues two separate CAS operations (one against the shared free-list, one against head), where the locked version does the same bookkeeping inside one critical section at the cost of a single lock acquire. The moment real contention shows up, the direction flips: at two workers (one per core on this 2-core box) the lock-free version was never slower across four separate trial batches, though by a widely varying margin (roughly 1x–2x, noisy enough on shared hardware that a tighter number would be misleading); at four workers (oversubscribing the same 2 cores 2x) the gap widened further and more consistently, 1.6x–4.4x across two batches. That widening under oversubscription matches a mechanism this site's own Busy-Waiting vs. Blocking guide already measured for a plain spin loop: a spinlock can be holding the lock and then get preempted by the scheduler, at which point every other thread spins uselessly until it's rescheduled — a lock-free structure has no such thing as "holding" anything, so it has nothing for a preemption to strand. Peterson's/Dekker's/ Lamport's bakery's own busy-waits share that exact same oversubscription weakness; this is the first page to measure what replacing the lock with CAS all the way down actually buys back.