multithreading · advanced

Safe Reclamation: Hazard Pointers & RCU

Lock-free data structures make removing a node easy with CAS, but they cannot free it immediately because another thread may still hold a pointer to the removed node and be about to dereference it — freeing too early is a use-after-free and is exactly what enables the ABA problem. The central question of safe memory reclamation is therefore: when is a removed node no longer referenced by any thread, so it can be freed? Hazard pointers answer this by having each thread publish, in a per-thread slot, the pointer it is about to dereference; when a thread retires a removed node it scans all threads' hazard slots, deferring the free (onto a retire-list) if any thread has published that node and freeing it otherwise — so a node is reclaimed only once no hazard pointer covers it, giving tightly bounded memory at the cost of a store-plus-fence per access and a scan per reclaim (C++26 adds std::hazard_pointer; folly has a mature implementation). RCU (read-copy-update) instead optimizes the read path: readers enter a lightweight read-side critical section and dereference freely (no atomics or locks in the classic kernel form), while a writer copies the data, modifies it, and atomically swaps the pointer, freeing the old version only after a grace period — once every reader that could have observed the old pointer has exited its critical section. RCU is ideal for read-mostly data (the Linux kernel relies on it heavily) but makes writers heavier and defers reclamation; choose hazard pointers when you need bounded memory and RCU when reads must be near-free.

The code

// The lock-free reclamation problem:
Node* n = head.load();        // reader is about to use *n
// ... meanwhile another thread pops n and calls delete n;
use(n->value);                // USE-AFTER-FREE  (also enables ABA)

// Q: in lock-free code, WHEN is it safe to free a removed node?
//    Two answers: HAZARD POINTERS and RCU.

What this lesson walks through

1. 01The deferred-reclamation problem
2. 02Hazard pointers — readers publish what they use
3. 03Gotcha — publish before deref; defer the free
4. 04RCU — read-copy-update

In lock-free structures, removing a node from the structure is easy with CAS — but you can't immediately delete it, because another thread may still hold a pointer to it and be about to dereference it. Freeing too early is a use-after-free and is also what enables the ABA problem. The core question is: when is no thread still using a removed node, so it is safe to free? Two standard answers: hazard pointers and RCU.