The reclamation problem
Lock free structures face a hard question: when is it safe to free a removed node? Another thread may have grabbed a pointer to it just before removal and be about to dereference it. Free too early and that thread reads freed memory.
Announcing intent
Hazard pointers solve this by giving each thread a small set of single writer slots. Before dereferencing a shared pointer, a thread:
- Writes the pointer into one of its hazard slots
- Rechecks that the pointer is still the published one, retrying if it changed
- Treats the slot as a public promise that this node must not be freed
Deferred freeing
When a thread removes a node, it does not free it right away. It adds the node to a private retired list. Periodically it scans every thread's hazard slots and frees only the retired nodes that no slot currently protects. Nodes still announced are kept and rechecked later.
Key idea
Hazard pointers let each thread publish the nodes it is about to use, so reclamation frees only nodes that no hazard slot protects.