Cairn
data structures · concurrency · O(1) pop amortized plus O(threads) hazard-scan work per retire, O(n + threads) space, lock-free safe memory reclamation

↩ back to Concurrency

Hazard Pointers

The Treiber Stack's own Pitfalls section demonstrates the classic ABA problem, then names the standard fix and stops: "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. None of those are built on this page; demonstrating the failure they exist to prevent was the point." This page is one of those two schemes, built on top of the exact same stack, racing the exact same two scenarios Treiber's own page already measured — so the fix can be checked against the specific corrupting schedules it's supposed to close, not just asserted to work in general.

Same measure-don't-assume discipline as this site's other ten Concurrency pages: every number below comes from exhaustively searching every reachable interleaving of a small state machine, not a handful of hand-picked traces.

Try it

Pick a scenario (same Minimal/Larger pop-vs-pop-and-push races the Treiber Stack's own page uses), an allocator (Recycle hands a freed slot's own numeric id back out to the next push; Fresh ids only never reuses one, matching real garbage-collected behavior), and a guard variant — Guarded (publish + re-validate) is the real hazard-pointer protocol; Publish-only (no re-validation) skips the one step described in Why it works below. Then either step through by hand with Step T0 / Step T1, or press Explore all schedules to search every reachable interleaving at once. Try Minimal + Recycle + Publish-only first — it corrupts the stack in as few as 10 moves. Switch to Guarded with the same scenario and allocator and it vanishes completely, at every one of the same reachable states.

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

Why it works

The Treiber Stack's bug has one root cause: a popping thread reads a node's next and value fields, then stalls before its compare-and-swap — and in that window, another thread can finish popping the same node, free it, and a later push can recycle its exact numeric id for a brand-new, unrelated node. The stalled thread's compare-and-swap only ever checks "does head still equal the id I saw" — it has no way to tell the original node from its recycled replacement, because both are, by construction, the same id. Hazard pointers don't change that CAS at all. They change when a node is allowed to be freed in the first place.

Every thread gets one shared hazard slot. Before a thread dereferences a node it's about to pop — reading its next and value — it runs three steps, not one: (1) publish — write the node's id into its own hazard slot, announcing "I might still be using this." (2) re-validate — read head again; if it no longer matches the id just published, some other thread already finished with that node (and possibly already freed it) in the gap between the thread's first read and its publish, so the thread clears its hazard and starts over. (3) only once validation passes is it safe to actually read the node's fields and proceed to the CAS. On the freeing side, popping a node never frees it immediately: it goes on a retired list instead, and only gets actually freed (and, under a recycling allocator, handed back out) once a scan of every thread's hazard slot finds nobody still pointing at it.

The re-validate step is the one easy to leave out by mistake, because publishing alone looks like it should already be enough — "I announced my interest, so nobody will free it out from under me." But publishing happens after the thread's first, unguarded read of head, and nothing stops another thread from popping and recycling that exact node in the gap before the publish lands. Re-validating closes that specific gap: if the node was already recycled by the time the hazard was published, re-reading head will no longer show the id the thread just published, and it retries instead of trusting stale data. Pitfalls below measures what happens when that one step is skipped — not a hypothetical, an exhaustively-found corrupting schedule.

Reference implementation

Pseudocode compareAndSwap(ref, expected, next) stands for the real hardware primitive, same as the Treiber Stack's own page. hazard[i] is thread i's single shared hazard slot, readable by every thread.

function pop(threadId) {
  while (true) {
    const oldId = head;             // (1) unguarded read
    hazard[threadId] = oldId;       // (2) publish
    if (head !== oldId) {           // (3) re-validate
      hazard[threadId] = null;
      continue;                     // node may already be recycled — retry from scratch
    }
    const nxt = slots[oldId].next;  // safe to dereference now
    const val = slots[oldId].value;
    if (compareAndSwap('head', oldId, nxt)) {
      retired.push(oldId);          // don't free yet — may still be hazarded by someone else
      hazard[threadId] = null;
      scanAndReclaim();             // free any retired node nobody's hazard still points at
      return val;
    }
    hazard[threadId] = null;        // CAS lost the race — clear and retry
  }
}

function scanAndReclaim() {
  const stillLive = [];
  for (const id of retired) {
    if (hazard.includes(id)) stillLive.push(id);   // still hazarded — leave it
    else actuallyFree(id);                         // nobody's using it — safe to recycle
  }
  retired = stillLive;
}

The demo above runs this exact shape as a step-by-step state machine, with every read, publish, validate, dereference, and CAS as its own independently interleavable move — same discipline as the Treiber Stack's own page, just with two extra sub-steps (publish, validate) inserted before the dereference. push is untouched from the Treiber Stack's own version: it never dereferences the old head's contents, only compares against it, so it was never the vulnerable operation and needs no hazard of its own.

Pitfalls

The guarded protocol never corrupts the stack, at any reachable state, under either allocator — a direct drop from the Treiber Stack's own 1-in-59 and 3-in-179 corrupting schedules to 0 in both, on the identical scenarios. Publish-only, missing just the re-validate step, reopens real corruption under the recycling allocator, at counts in the same range as the original unprotected bug:

scenarioguardallocatorreachable statescorrupt statesshortest schedule
MinimalGuardedFresh ids only1020—
MinimalGuardedRecycle1070—
MinimalPublish-onlyFresh ids only830—
MinimalPublish-onlyRecycle90110 moves
LargerGuardedFresh ids only3310—
LargerGuardedRecycle3530—
LargerPublish-onlyFresh ids only2670—
LargerPublish-onlyRecycle299316 moves

Recycling is still a necessary ingredient, exactly as it was for the original unprotected stack: under Fresh ids only, both guard variants hold at 0 corrupt states, because nothing ever reuses a slot's identity for a different node in the first place — there's no coincidence for either variant's own machinery to be fooled by.

The Publish-only + Recycle corruption in the Minimal scenario, traced move by move: the stack starts as A → B (head A, id 1; B, id 0). T0 reads head (sees A's id, 1) and stalls before publishing. T1 independently reads the same id, publishes, re-validates (it passes — nothing has changed yet), reads A's fields, and successfully pops A: head swings to B (id 0), A's id 1 goes onto the retired list, and since neither thread's hazard slot points at it yet — T1 just cleared its own, and T0 hasn't published yet — the scan frees it immediately and returns it to the allocator's free list. Only now does T0 resume: it publishes its hazard on id 1 — the node it already read but hasn't re-validated yet — then reads slots[1]'s stale leftover fields (still A's old next/ value, untouched since nothing has reallocated that slot yet). T1 then pushes a new value, X, and the recycling allocator hands it id 1 — the exact slot T0 is now holding stale data about. T0's final CAS checks only "does head still equal 1" — it does, coincidentally, because X now lives at that same id — so the CAS succeeds, and T0 reports popping A a second time, using its stale cached value, while physically consuming X's node out from under it. The result: A is reported popped by both threads, and X — genuinely pushed, per T1's own completed result — never appears anywhere, reachable or returned. Not a phantom-empty response like the Michael-Scott Queue's own naive bug; a real duplicate paired with a real loss. Re-validating after publish (the Guarded variant) closes exactly this gap: by the time T0 would dereference id 1, re-reading head no longer shows 1 (it shows B, or later X) — the mismatch is caught, and T0 retries from a fresh read instead of trusting data about a node that was already reclaimed out from under it.

Two things worth being precise about, because this scheme is easy to overstate. First, the scan in this model is deliberately simplified: every retiring thread scans the entire hazard array itself, immediately, as part of its own retire step. Production hazard-pointer implementations batch scans (reclaim in bulk once a retired list crosses some threshold, rather than on every single retire) for exactly the reason the Complexity section below measures: an immediate per-retire scan is real, recurring overhead that batching exists to amortize, not a free safety net. Second, hazard pointers are not the only standard answer to this problem — epoch-based reclamation (defer every free until every thread has passed through a quiescent point at least once, instead of tracking individual node references) is the sibling scheme the Treiber Stack's own page named alongside this one. It's now built too: see Epoch-Based Reclamation, which measures exactly this tradeoff with real numbers — a single stalled thread there holds every node retired since it stalled hostage, unboundedly (1,000 cycles of unrelated work measured to 1,000 stuck nodes), where this page's own hazard slot can only ever block the one id it last published, no matter how long that same stall lasts. See Choosing a Memory Reclamation Scheme for the full side-by-side.

Complexity

Time: the CAS retry loop itself is still O(1) per attempt with no bound on retries under contention, identical to the Treiber Stack. What's new is real, bounded extra work on the successful path of every pop: one extra published write (the hazard slot), one extra read-and-compare (re-validation), and — only on the thread that actually completes a pop — one scan of every thread's hazard slot, O(threads), to decide what can finally be freed. None of this changes the complexity class; it adds a constant-but-real amount of work per operation, the same way the Michael-Scott Queue's lagging-tail help-and-retry adds a bounded extra CAS without changing enqueue/dequeue's own growth rate. Space: O(n) for n live elements, identical to the Treiber Stack, plus O(threads) for the hazard array and whatever's currently sitting on the retired list awaiting reclamation — bounded by how many nodes can be mid-flight at once, not by how many have ever existed.

The reachable-state counts above give a rough, honest sense of that added bookkeeping cost without overstating it as a timing result: the Guarded variant explores 107 states against Publish-only's 90 in the Minimal/Recycle configuration (+19%), and 353 against 299 (+18%) in Larger/Recycle — the extra publish-and-validate sub-steps this page adds over the Treiber Stack's own three-step pop widen the reachable space by roughly a fifth here, not by an order of magnitude. That is a state-space measurement, not a wall-clock one — it says the protocol adds a modest, real number of extra interleaving points, not how many nanoseconds any of them costs on real hardware.