Hazard Pointers

The problem in one sentence

In a lock-free data structure without garbage collection, after a node is popped other threads might still be reading it. Free it too soon and they read garbage. Free it too late and memory leaks.

Hazard pointers are the way to know when "soon enough" is.

A picture of the danger

The stack starts as head → A → B → C. Thread 1 is in the middle of a pop. Thread 2 is reading the same node A through the head. The pop completes correctly, but the timing of the free call is what causes the bug.

The pop itself was correct. The bug is that A was freed while Thread 2 still had a pointer to it. Garbage-collected languages sidestep this because the GC will not free A while any thread holds a reference. C and C++ have no such safety net. Hazard pointers are how that safety net is built explicitly.

The trick

Each thread keeps a small array of "I am about to use this pointer" announcements, called hazard slots. Before reading from a shared atomic pointer, the thread writes the pointer it just loaded into one of its own hazard slots. Before freeing a node that was popped earlier, the reclaimer scans every thread's hazard slots. If any slot contains the node's address, the reclaimer holds off on the free until later.

The reader's protocol is:

1. Load the pointer from the shared atomic.
2. Publish that pointer to its hazard slot.
3. Re-read the shared atomic. If the value changed in between, the announcement was published too late and the node may already have been retired; reload and try again.
4. Once the re-read still matches, the pointer is safe to dereference.
5. When done, clear the hazard slot.

The double-check at the top is the subtle part. Publishing alone is not enough, because the publish might happen after a parallel reclaimer has already scanned and decided the node is safe to free. Publishing followed by a re-read of the source closes the gap: if the source still equals the pointer, the announcement reached the reclaimer in time; if the source has moved on, the node may already have been retired and the reader must retry.

A picture of the lifecycle

There are two views to keep in mind. The reader's view of one hazard slot, and the reclaimer's view of one node.

Reader's view of a hazard slot. The slot moves between two states: empty when the thread is doing nothing risky, and holding a pointer when the thread is actively reading the node at that pointer.

Reclaimer's view of a node X. The reclaimer never frees X immediately when X is unlinked. X spends time on a per-thread retired list first. The reclaimer periodically scans every thread's hazard slots. As long as X appears in any slot, X stays on the retired list. Once X appears in no slot, the reclaimer is free to release the memory.

Each thread typically has between one and eight hazard slots. Most lock-free structures only need each reader to hold one or two pointers at a time, so eight slots is plenty.

Comparison with other schemes

Reference counting: each node has an atomic refcount. Increment on access, decrement on release. Free at zero. Simple but the atomic ops on the shared counter dominate performance under contention.

Epoch-based reclamation (RCU-like): each thread maintains a current epoch. Reclamation defers until all threads have advanced past the epoch when the node was unlinked. Lower per-access overhead than hazard pointers (just bump the local epoch counter). Higher reclamation latency.

Hazard pointers: per-access overhead (publish + clear), fast reclamation (free as soon as no hazard). Each access needs a bounded number of slots.

For lock-free queues and stacks accessed by many threads, all three work. The right choice depends on the access pattern: if accesses are short, RCU wins; if access depth is bounded, hazard pointers are predictable; if prompt freeing is required, hazard pointers.

Hazard pointers vs epoch-based reclamation, side by side

This is the choice that comes up when picking a reclamation strategy for a real lock-free structure. The two are competing approaches with mirror-image tradeoffs.

The mental model:

• Hazard pointers: "I'm holding this exact node, please don't free it." Fine-grained, per-access.
• EBR: "Nobody is reading anything from before epoch N." Coarse-grained, per-thread.

When to pick which:

• Many threads with short, bounded accesses (typical lock-free queue): EBR. Lower per-access cost matters more than reclamation latency.
• Few threads with long accesses, or strict memory budgets: hazard pointers. You free promptly and don't accumulate.
• Real-time systems where bounded reclamation latency is required: hazard pointers. EBR has no upper bound.
• Code that already runs in a managed runtime: neither. The GC is the reclamation strategy.

Code-shape comparison for the same operation (pop from a lock-free stack):

// Hazard pointer style
HazardPointer hp = thread_local_hazard_slots[0];
Node* old = head.load(acquire);
do {
    hp.protect(old);                                     // publish
    Node* recheck = head.load(acquire);
    if (recheck != old) { old = recheck; continue; }     // retry
    if (!head.compare_exchange_strong(old, old->next)) continue;
    break;
} while (true);
// dereference old safely
hp.clear();
retire(old);                                              // freed when no hazard

// Epoch-based reclamation style
Guard guard = epoch.pin();                                // bump local epoch
Node* old = head.load(acquire);
while (!head.compare_exchange_weak(old, old->next));
// dereference old safely
defer_free(old, guard);                                   // freed when global epoch advances past current
// guard goes out of scope, releases pin

EBR's hot path is one atomic to bump the epoch and one atomic on the actual data structure. Hazard pointers need an extra publish + re-check on every access. EBR wins per-op; hazard pointers win on reclamation predictability.

In practice

Most application code never touches hazard pointers directly. You use a library (folly's hazard_pointer, crossbeam in Rust) that hides the protocol behind a typed API.

For C++26+ code, std::hazard_pointer (proposed) will provide the standard primitive. For now, copy from folly, or use a library that handles reclamation directly.

In Java and Go, hazard pointers aren't needed; the GC handles the equivalent. Garbage collected languages essentially run hazard-pointer-style logic continuously over all references.

The core insight worth keeping: a lock-free pop is not the same as a safe free. Other threads might still hold the popped pointer, so without GC an explicit reclamation scheme is required. Hazard pointers are one of the standard answers (alongside reference counting and epoch-based reclamation), and what they publish is essentially "I am about to use this". And almost no one should be writing them by hand: use folly, libcds, or the proposed standard primitive. Lock-free reclamation is one of the most error-prone areas of systems programming.