epoch-based reclamation (EBR)
/ EP-uhk /
Hazard pointers protect each individual node a thread touches — which is precise but costs a publish on every access. Epoch-based reclamation takes a coarser, cheaper view: instead of tracking which exact nodes are in use, it tracks which broad time-window a thread is operating in, and only frees memory once it knows every thread has moved past the window in which that memory was removed. It trades precision for very low per-access overhead.
Here is the mechanism. There is a single global epoch counter that ticks forward occasionally. Each thread, when it enters a section that touches the shared structure (a read-side critical section), announces the current global epoch and marks itself active; when it finishes, it marks itself inactive (quiescent). When a node is removed, it is retired into a bin tagged with the current epoch. A node is safe to free only once every thread has either gone quiescent or advanced to a newer epoch — at that point you are certain no thread can still be in the epoch when the node was live, so no one holds a pointer to it. The global epoch can advance whenever all active threads agree they have seen the current one. Quiescent-state-based reclamation (QSBR) is the closely related variant where threads simply pass through known quiescent points (such as the top of an event loop) rather than bracketing every critical section.
The appeal is speed: entering and leaving an epoch critical section is a couple of cheap atomic operations, far less than hazard pointers' per-pointer publishing, so reads are almost free. The honest cost is the other side of that coin — a single thread that stalls inside a critical section, or simply never reaches a quiescent state, prevents the epoch from advancing, and retired memory piles up unbounded until that thread cooperates. EBR therefore assumes threads pass through quiescent states promptly and is a poor fit if a thread can block arbitrarily long while inside the structure. Crossbeam (Rust) and many database engines use EBR for exactly its read-side cheapness.
/* Read-side: bracket the critical section by entering/leaving the epoch. */ epoch_enter(); /* announce current global epoch, mark active */ Node *p = lookup(key); use(p->data); epoch_leave(); /* mark quiescent */ /* Remove side: retire(node) tags it with the current epoch; the node is freed only once all threads have left that epoch (or gone quiescent). */
Reads are bracketed by cheap enter/leave calls; a retired node waits until every thread has advanced past the epoch in which it was removed.
EBR's reads are nearly free, but one thread that stalls inside a critical section (or never goes quiescent) stops the epoch advancing and lets retired memory grow without bound. It assumes threads quiesce promptly.