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.
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.
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.
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.
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:
| scenario | guard | allocator | reachable states | corrupt states | shortest schedule |
|---|---|---|---|---|---|
| Minimal | Guarded | Fresh ids only | 102 | 0 | — |
| Minimal | Guarded | Recycle | 107 | 0 | — |
| Minimal | Publish-only | Fresh ids only | 83 | 0 | — |
| Minimal | Publish-only | Recycle | 90 | 1 | 10 moves |
| Larger | Guarded | Fresh ids only | 331 | 0 | — |
| Larger | Guarded | Recycle | 353 | 0 | — |
| Larger | Publish-only | Fresh ids only | 267 | 0 | — |
| Larger | Publish-only | Recycle | 299 | 3 | 16 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.
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.