Epoch-based reclamation

Epoch-based reclamation (EBR) is a memory-management technique for lock-free data structures. The problem it solves: when a thread removes a node from a concurrent structure, other readers might still hold a pointer to that node. Freeing immediately would let those readers dereference freed memory. Reference counting works but adds per-access atomic increments. EBR avoids the per-access overhead.

The scheme works in three pieces:

• A global epoch counter, incremented by reclaimers. Two or three values rotate (e.g., 0, 1, 2).
• Each registered thread maintains a local epoch stamped when it pins, and a limbo list of nodes it has retired in that epoch.
• Before touching the structure, a thread pins by copying the global epoch into its local. Pinned means "I might be holding pointers from this epoch onward."

When a node is removed it's not freed — it's appended to the current thread's limbo list, tagged with the current global epoch. A node is safe to free only once every registered thread's local epoch has advanced past the node's retirement epoch. A background or piggybacked pass walks the limbo lists, frees what's safe, and the global counter advances.

The cost model is the opposite of refcounting: zero per-access overhead in the hot path (one relaxed read of the global epoch on pin/unpin), at the cost of bounded memory bloat — freed memory can sit in limbo as long as one thread stays pinned. The standard mitigation is a per-thread retirement threshold that forces a reclamation pass when the limbo list grows.

EBR is the default reclamation scheme in many lock-free libraries: Crossbeam in Rust, userspace RCU (URCU) on Linux, the gregburd/skiplist C library, and most academic lock-free skip-list and queue implementations. The main alternative is hazard pointers, which trades higher per-access overhead for tighter worst-case memory bounds.