In a lock-free data structure written without garbage collection, why is it unsafe for the thread that unlinks a node to free that node immediately, and what problem must any safe-memory-reclamation scheme solve?

## The core difficulty In a lock-based structure, deletion is easy: a remover holds the lock, so no reader can be inside the structure, and freeing under the lock is safe. Lock-free structures buy their progress guarantee by removing exactly that rendezvous. A reader traverses by loading pointers with plain atomic loads and announces nothing. So when a writer unlinks node N with a compare-and-swap, the only fact established is *no future traversal starting now will reach N*. Threads that loaded a pointer to N microseconds earlier are still holding it and may dereference it at any later moment — after a preemption, a page fault, or a scheduler quantum boundary that can be milliseconds long. Freeing N immediately produces two distinct defects: 1. **Use-after-free.** A concurrent reader dereferences memory returned to the allocator. It may read a reused object's bytes as if they were the node's fields, follow a garbage `next` pointer into unmapped memory, or write into an object now owned by someone else. In manual-memory languages this is undefined behaviour, and the observable symptom (a crash, a corrupted unrelated structure) is usually far from the cause. 2. **ABA re-entry.** A freed address is prime material for reuse. When the allocator hands the same address back and it is pushed into the structure again, an old pointer value recurs — the precondition for a stale compare-and-swap succeeding. The two are related but separable: version tags fix (2) and not (1); reclamation schemes fix (1) and, by suppressing premature reuse, largely defuse (2) as well. ## The shared shape of every solution Every scheme splits deletion into **retire** and **free**. `retire(N)` removes N from the structure and puts it on a deferred list. `free(N)` happens only once the scheme can prove no thread holds a reference. The proof always comes from readers publishing *something* cheap: **Hazard pointers.** Each thread owns a small set of single-writer, multi-reader slots. Before dereferencing a pointer it writes that pointer into a slot, then re-validates that the pointer is still reachable in the structure (the publish-then-verify step is essential — without it the node could be retired between the load and the publication). A reclaimer collects retired nodes and scans all threads' slots; anything not listed is unreachable and can be freed. Properties: **bounded** garbage (at most a fixed number of protected nodes per thread plus the retire batch), but a store plus a memory fence plus a re-check on every pointer traversal, which is real cost in read-heavy traversals. **Epoch-based reclamation.** A global epoch counter advances periodically. Each thread, on entering a critical region, publishes the current epoch in a per-thread slot and clears it on exit. A node retired during epoch `e` is safe to free once every thread has been observed either inactive or in an epoch later than `e` — that guarantees every reader that could have seen the node has finished. Properties: reads are almost free (one store, no per-pointer bookkeeping), but garbage is **unbounded**: a single thread that stalls inside a critical region — preempted, blocked on I/O, or hit by a page fault — pins the epoch and the deferred list grows without limit. This is a memory-exhaustion failure mode, not a correctness one. **Read-copy-update.** The same deferred-free discipline exposed as a read side that is essentially free and a writer side that publishes a new version and waits for a *grace period* — an interval after which every reader that existed at retire time has finished its read-side critical section. It shines where reads vastly outnumber writes and where the runtime can detect quiescence cheaply (in kernels, by observing context switches). **Reference counting** is the obvious alternative and mostly a trap here: incrementing a count requires already holding a safe reference, which is the very thing in question, so naive per-node reference counting has a race at the acquire step and needs split counters or deferred techniques anyway — and it makes every read a contended atomic write on shared cache lines. ## Practical framing The honest senior answer is that safe reclamation, not the algorithm itself, is the hard and expensive part of hand-written lock-free code. Most production systems avoid the whole category: use structures the runtime or a vetted library already implements, keep removals rare, use per-thread ownership so nothing is shared, or accept a lock. Choosing to hand-roll a lock-free structure with manual memory means signing up for a reclamation scheme, its failure mode, and the test infrastructure to trust it.