The Hazard Pointer Reclamation
In a lock free structure, one thread may unlink a node while another thread is still reading it. Freeing that node immediately would crash the reader. Hazard pointers are a scheme that lets memory be reclaimed only once no thread can still be using it.
Each thread owns a small set of single writer slots called hazard pointers. Before dereferencing a shared node, a thread writes that node address into a hazard pointer, publishing the fact that it is in use. Other threads can read these published pointers.
- Publish Store a node address in a hazard pointer before reading it.
- Retire When a node is unlinked, add it to a thread local retired list instead of freeing.
- Scan Periodically check all hazard pointers and free only nodes no one protects.
Reclamation happens in batches. When a thread retires enough nodes, it scans the hazard pointers of every thread. Any retired node not currently protected by any hazard pointer is safe to free, while protected nodes wait for the next scan.
The cost is a memory fence and a scan, but the benefit is bounded memory. Because each thread has a fixed number of hazard pointers, the number of nodes pending reclamation is bounded, unlike schemes where a stalled thread can pin unbounded memory.
Key idea
Hazard pointers let threads publish the nodes they are reading so retired nodes are freed only after a scan confirms no hazard pointer protects them.