The Reclamation Problem: Hazard Pointers and Epochs

The question the lock used to answer for you

By guide 3 you can pop a node off a Treiber stack or dequeue from a Michael-Scott queue without ever holding a lock. The CAS swings the head pointer past the node, and as far as the structure is concerned the node is gone. So you call free() on it — and that is where the floor gives way. Under a lock this was a non-question: nobody could be inside the structure while you held the mutex, so once you unlinked a node it was provably yours to destroy. Remove the lock and that proof evaporates.

Here is the picture, frame by frame. Thread A is about to pop. It reads head, gets node N, and then — between reading the pointer and reading N's next field — the scheduler pauses it. Thread B now pops N, swings head past it, and calls free(N). The allocator hands that memory back to the system or recycles it for something else. Thread A wakes up holding a pointer to N and dereferences it to read N's next. That dereference is a textbook use-after-free: the bytes under the pointer are no longer the node, they are garbage, or someone else's object, or unmapped memory that segfaults on touch.

This is the memory reclamation problem, and notice it is the very same root we found beneath the ABA problem in guide 2: a node was freed and its memory reused while another thread still held a pointer into it. The deep difficulty is that there is no central place to ask "is anyone still looking at N?" The threads are the only ones who know which nodes they are reading, and each knows only its own. So the whole game of safe reclamation is this: get every thread to publish enough about what it is reading that a thread wanting to free a node can prove nobody is touching it. The two classic designs differ only in what gets published and how coarsely.

Hazard pointers: announce what you are about to touch

The first answer is delightfully direct. Before a thread dereferences a node, it loudly announces "I am about to use this one — do not free it yet." That announcement is a hazard pointer: a single-writer, many-reader slot, owned by one thread, in which that thread publishes the address of the node it is currently protecting. Each thread has a small fixed number of these slots — usually one or two, because most operations only ever hold a pointer to one or two nodes at a time. The set of all threads' hazard slots forms a global, scannable list of every address that is currently off-limits to free().

The subtlety is that publishing and reading race, so the protocol must be exactly right. You cannot just write your hazard slot and charge ahead — between your write and your dereference, the node might already have been unlinked and freed. So the read side does a publish-then-verify dance: store the node's address into your hazard slot, then re-read the source pointer (the head, say) and confirm it still points at the same node. If it changed, the node may be in flight to being freed, so you drop it and retry. Only after the slot is set and the pointer re-confirmed is it safe to dereference. This re-check is the whole correctness argument, and it is easy to get wrong.

// READER: protect a node before touching it (one hazard slot 'hp')
for (;;) {
    node *n = atomic_load(&head);      // 1. read the pointer
    atomic_store(&hp, n);              // 2. publish: "protecting n"
    if (atomic_load(&head) == n)       // 3. re-check it didn't move
        break;                         //    confirmed safe to use n
    // else: n may be getting freed; loop and try again
}
// ... safe to dereference n here ...
atomic_store(&hp, NULL);               // done: clear the slot

// RETIRER: thread that unlinked a node
retire(node *n) {
    add_to_my_retired_list(n);         // do NOT free yet
    if (retired_count >= THRESHOLD)    // amortize the scan
        scan_and_reclaim();            // free only nodes in NO hazard slot
}

Now the other half. A thread that unlinks a node does not free it immediately. It puts the node on a private retired list and walks away. Periodically — when its retired list grows past a threshold, to amortize the cost — it runs a scan: collect every address currently sitting in any thread's hazard slots into a set, then for each node on its retired list, free it only if its address is not in that set. Nodes that are still hazarded stay retired and get re-checked next sweep. Because a node is reclaimed only once no hazard slot names it, the use-after-free is impossible by construction.

Why the memory ordering on a hazard pointer is not optional

It is tempting to read the protocol as plain stores and loads and assume the order you wrote them is the order they run. It is not, and this is where last rung's acquire/release ordering stops being abstract and becomes load-bearing. The reader's publish (store to the hazard slot) and re-check (load of head) must not be reordered by the compiler or CPU — if the re-load floated above the publish, the slot might still be empty at the instant a retirer scans, and the node could be freed out from under the reader. The retirer's scan of hazard slots must, symmetrically, see the reader's published write. Get the fences wrong and the algorithm is silently, intermittently broken on exactly the hardware you do not test on.

Step back and weigh hazard pointers honestly. The cost is paid on the read side: every protected access does an extra atomic store and an extra load with a memory barrier, on the hot path, every single time. For read-heavy structures that overhead is real and measurable. The wins are equally real: the amount of unreclaimed ("floating") garbage is tightly bounded — at most one or two nodes per thread per hazard slot — so memory use stays predictable, and a stalled or descheduled thread holds back only the handful of nodes it actually named. Hazard pointers also fix ABA for free, since a hazarded node cannot be freed and its address cannot be recycled while you hold it.

Epochs: protect a span of time, not a node

Epoch-based reclamation flips the question. Instead of asking "which nodes is each thread protecting?", it asks the coarser, cheaper question "is any thread still inside an operation that began before now?" The structure keeps a single global counter — the epoch. When a thread starts an operation it enters a critical region: it reads the current global epoch and announces, in its own slot, "I am active in epoch e." When it finishes, it marks itself inactive. A retired node is tagged with the epoch in which it was unlinked, and it becomes safe to free only once every thread has been observed to have moved past that epoch.

The advance rule is the heart of it. A thread trying to make progress checks: are all active threads now in the current epoch e (none still lagging in e-1)? If so, it bumps the global epoch to e+1. The key insight is what that guarantees: once everyone has been seen in epoch e, no thread can still hold a pointer it grabbed back in epoch e-2, because to be reading it would have meant being active in e-2, and we just confirmed nobody is. So nodes retired in epoch e-2 are now provably untouchable and can be freed in a batch. Reclamation lags the present by a bounded couple of epochs — typically three are kept in flight — and that lag is the price of the coarse grain.

Walk one concrete picture. The global epoch is 5; threads T1 and T2 have announced themselves active in epoch 5, but T3 is still active in epoch 4 — it has not finished the operation it started a while ago. No thread may advance the epoch yet, because T3 lagging in 4 means a reader from epoch 4 is still live. Later T3 finishes, marks itself inactive, and on its next operation re-enters and announces epoch 5. Now every active thread is at 5 or beyond, so any thread may bump the global epoch to 6 — and at that instant every node that was retired back in epoch 4 is provably unreachable (no live reader could be holding a pointer that old), so the whole batch is freed at once.

What you bought is a much cheaper read path: entering a critical region is essentially one store of the current epoch into your slot, with no per-node bookkeeping at all — you can dereference a hundred nodes inside one critical region for the price of one announcement. That is why epoch schemes (and their cousins in crossbeam for Rust, or the Linux kernel's userspace-RCU library) are popular for read-mostly structures. The honest cost is the mirror image of hazard pointers: protection is coarse and time-based, so a single stalled thread that never leaves its critical region pins the epoch forever, and retired memory piles up without bound. Hazard pointers leak a couple of nodes per stuck thread; epochs can leak everything.

Choosing, and the family this opens onto

Put them side by side and the choice becomes a question about your reads. Hazard pointers protect individual nodes and make you pay an atomic store-and-fence per protected pointer, but they bound floating garbage tightly and tolerate a stalled thread gracefully — pick them when reads are small, memory is precious, or worst-case latency matters. Epochs protect a window of time and make reads almost free, but reclamation lags and one stuck thread can stall it indefinitely — pick them when reads are frequent, touch many nodes, and you can trust threads to leave their critical regions promptly. Neither is a default; each is a deliberate trade of read-cost against reclamation-promptness.

1. Are reads tiny (touch one or two nodes) and is bounded memory or worst-case latency a hard requirement? Lean hazard pointers.
2. Are reads frequent and read-mostly, traversing many nodes per operation, with threads that reliably finish quickly? Lean epoch-based reclamation.
3. Can any thread block, sleep, or be preempted for a long time mid-operation? That is poison for epochs (it pins the epoch); hazard pointers degrade far more gracefully.
4. Is your workload overwhelmingly reads with rare writes, on a known platform? Then the specialized cousin in the next guide — RCU — may beat both.

That last step points straight at where this rung is going. Epoch-based reclamation is one face of a broader idea: let readers run unimpeded, defer every reclamation until you can prove all the old readers are gone, and pay almost nothing on the read path. Push that philosophy to its extreme — readers that take no locks, do no atomic writes, and barely announce themselves at all — and you arrive at read-copy-update (RCU), the technique that quietly underpins huge swaths of the Linux kernel. Guide 5 takes it apart, and then steps back to ask the honest closing question of this whole rung: given how many razor-thin orderings every one of these schemes depends on, why is getting lock-free code right so genuinely, famously hard?