the memory-reclamation problem

When you remove a node from a lock-free data structure, the obvious next move is to free it. But here is the trap that makes lock-free programming genuinely hard: at the very moment you unlink and free a node, some OTHER thread may have read a pointer to that same node a microsecond ago and be about to dereference it. If you free it now, that thread reads freed memory — a use-after-free, which is undefined behavior and a security hole. You cannot just call free(). This is the memory-reclamation problem, and it has no easy answer.

The deep reason it is hard is that in a lock-free design there is no single moment when you can be sure nobody is looking at a node. With a lock, the thread holding the lock has exclusive access, so when it removes a node it KNOWS no one else can be mid-read. Lock-free has no such exclusion — many threads roam the structure at once, reading pointers, and a node you just unlinked from the structure's visible state may still be reachable through a stale pointer that another thread loaded before you unlinked it. So removal from the structure and safe deletion of the memory are two different events, and the gap between them is where the danger lives.

Every solution is therefore a way to defer the free until you can prove no thread still holds a reference. The major families each make that proof differently: hazard pointers, where each thread publishes the exact pointers it is currently using so a would-be reclaimer scans and skips them; epoch-based reclamation and quiescent-state reclamation, where you wait until every thread has passed a safe point at which it holds no references; reference counting, which tracks the count of holders directly; and RCU, which waits for a grace period after which all pre-existing readers have finished. They trade off reader cost, reclamation latency, and memory held in limbo — but all exist solely to answer one question: when is it finally safe to free this node?