Removing a node from a lock-free data structure does not make its memory immediately safe to reuse. Another thread may already hold the node’s address and may still dereference it. If the remover frees that allocation too early, an otherwise correct atomic update can be followed by a use-after-free.
Hazard pointers separate logical removal from physical reclamation. A reader publishes the address it intends to access in a designated hazard slot. A remover can unlink a node and place it on a retired list, but reclamation waits until a scan confirms that no hazard slot protects that address.
This protocol addresses memory lifetime. It does not replace the atomic rules that make the data structure itself correct.
A pointer can outlive its membership
Consider a lock-free stack whose head is an atomic pointer. A reader might begin a pop with:
p = head.load()
next = p.nextThe load of head and the later read of p.next are separate operations. Between them, another thread can remove p. If removal also frees p, the second operation can access storage whose lifetime has ended.
Keeping removed nodes forever avoids the immediate fault but merely trades safety for an unbounded memory leak. A reclamation scheme needs a condition that says when no active reader can still use a retired object.
Hazard pointers provide that condition through explicit publication.
Publication needs a validation loop
Publishing a hazard after reading a shared pointer is not sufficient by itself. The node could be removed between the initial load and publication. A typical acquisition loop therefore publishes and then validates:
repeat:
p = head.load(acquire)
hazard.store(p, seq_cst_or_required_order)
until p == head.load(acquire)
if p != null:
next = p.nextThe exact memory orders depend on the algorithm and implementation. The essential protocol is stable: obtain a candidate, publish it, then verify that the shared source still names the same candidate before dereferencing fields that require protection.
If validation fails, the reader retries with the new value. A remover that retired the old node must account for the published hazard before reclaiming it.
The hazard slot is cleared when the reader no longer needs the protected object:
hazard.store(null, required_order)Clearing too early reopens the lifetime gap. Leaving a slot populated for too long is safe for that reader but can delay reclamation.
Retirement is not reclamation
A successful compare-and-swap may detach a node from the structure:
if CAS(head, p, next):
retire(p)retire(p) should not be treated as free(p). The retired node remains allocated while it may appear in any hazard slot.
Implementations commonly accumulate retired nodes and scan hazard records in batches. Conceptually, a scan computes a set of protected addresses and reclaims retired nodes absent from that set:
protected = snapshot_all_hazards()
for node in retired:
if node.address not in protected:
reclaim(node)
else:
keep_retired(node)Batching amortizes scan cost. It also means memory usage can temporarily exceed the number of nodes currently reachable from the data structure.
Hazard records are part of the protocol
Each participating thread or operation needs access to hazard records whose lifetime is itself managed safely. A record cannot disappear while another participant may scan it.
Systems often use a bounded collection of per-thread slots, a reusable registry, or another stable record-management scheme. The choice affects registration cost, maximum concurrent protection, and cleanup for threads that exit.
Multiple simultaneously protected objects require multiple slots or a protocol that changes traversal behavior. A linked traversal, for example, may need to protect a current node and a successor during a handoff. The algorithm must state which references are protected at each dereference boundary.
A hazard pointer API that hides these constraints behind a plain pointer type can make misuse easy. Publication, validation, slot ownership, and release are semantic operations even when a library wraps them in safer abstractions.
Reclamation scans need a coherent safety rule
A scanner does not need a globally atomic snapshot of every hazard slot in the ordinary sense. It does need memory-ordering rules that prevent a node from being reclaimed while a reader can legitimately proceed with that node protected.
That guarantee comes from the complete protocol: reader publication and validation, remover retirement, scanner observation, and the ordering constraints connecting those steps. Picking relaxed operations independently because each field is atomic can violate the required relation.
The appropriate orders vary across platforms, language memory models, and published hazard-pointer algorithms. Implementations should follow a proved protocol rather than infer orders from intuition about a particular processor.
This is also a boundary for testing. Stress tests can expose races, but passing stress runs cannot establish a memory-ordering proof.
Reuse makes stale addresses especially dangerous
An allocator may reuse a reclaimed address for a different object. A stale raw pointer can then numerically match a valid address while referring to a different lifetime.
This connects memory reclamation to ABA-style failures, but the two concerns are not identical. Versioned pointers can distinguish some state transitions without making an object safe to dereference. Hazard pointers can keep a protected allocation alive without, by themselves, proving every compare-and-swap invariant in the surrounding algorithm.
A lock-free design may therefore need both a reclamation protocol and a separate defense against state-history ambiguity.
Progress properties must include reclamation work
A lock-free container can have non-blocking update operations while reclamation introduces additional shared work. Scanning hazard records takes time proportional to the relevant record set, and retired lists consume memory until scans make progress.
This does not automatically invalidate a lock-free claim for the data-structure operation, but progress terminology should identify what is covered. Registration, allocation, reclamation, and allocator behavior can have different progress properties from the core compare-and-swap loop.
Operational limits matter as well. A stalled thread that leaves a hazard published can keep specific retired nodes from being reclaimed. It does not normally stop unrelated lock-free updates, but retained memory can grow if protected objects or stalled participants accumulate.
Safe reclamation is an ownership boundary
Hazard pointers make a narrow promise: a node selected for reclamation is not currently protected by the participating readers under the protocol. That promise depends on every dereference path publishing protection correctly and every reclamation path consulting the same protection domain.
They do not turn arbitrary pointer access into safe access, repair missing synchronization, or establish correctness for the data structure’s logical transitions. Their role is precise: bridge the interval between removing an object from shared reachability and ending the object’s storage lifetime.
In lock-free code, that interval is part of the algorithm, not cleanup after it.