The reclamation problem
In a lock free structure one thread may try to free a node while another is about to dereference it. Freeing too early is a use after free bug. Hazard pointers solve this by making each thread announce the pointers it is currently protecting.
How it works
Each thread owns a small set of single writer, multi reader hazard pointer slots.
- Before dereferencing a node, the thread stores that node address into one of its hazard slots.
- It then re validates that the node is still reachable, because it might have been removed between the read and the publish.
- After finishing, it clears the slot.
Deferred freeing
When a thread removes a node, it does not free it immediately. It puts the node on a private retired list. Periodically it scans all threads hazard slots; any retired node not appearing in any hazard slot is provably unreferenced and safe to free. Nodes still hazarded are kept for the next scan.
This bounds outstanding garbage to a small multiple of the number of threads and hazard slots.
Key idea
Hazard pointers let each thread publish the nodes it is about to touch, so a remover only frees retired nodes that no thread has hazarded, preventing use after free.