Epoch-based reclamation

Deep dive

How it works

In: pointers read while pinned; unlinked objects to retire · Out: safe dereference while pinned; deleters run after two epoch advances · State: one global epoch, one local epoch per thread, per-thread garbage bags · Cost: pin/unpin O(1) (order of 5-20 ns), advance O(threads), reclamation amortized O(1) per object

global epoch: 7
thread A: pinned @7    thread B: pinned @7    thread C: not pinned
retire(node) after unlink -> bag tagged with global epoch (7)
all pinned threads @7 -> advance to 8;  all pinned @8 -> advance to 9;  free bags tagged <= 7

1. Pin: local = (global << 1) | 1, then fence(SeqCst) before reading shared pointers.
2. Unpin: local.store(0, Release) once done with all pointers obtained while pinned.
3. Retire: after unlinking an object, fence(SeqCst), read the global epoch e, push (e, deleter) to a thread-local bag.
4. Advance: scan all threads; if every pinned thread shows the current epoch g, CAS global g → g+1.
5. Collect: run deleters whose tag satisfies global - e ≥ 2. A thread pinned at the time of the unlink has epoch ≤ e; the global can reach e+2 only after every such thread has unpinned.

Code

Simplified from crossbeam-epoch's design (fixed thread slots, thread-local bags, no global queue).

use std::sync::atomic::{fence, AtomicUsize, Ordering::{Acquire, Relaxed, Release, SeqCst}};

const MAX_THREADS: usize = 64;
const FREE: usize = usize::MAX; // slot unregistered; 0 = registered, not pinned; (e << 1) | 1 = pinned at e

#[repr(align(128))]
struct Pad<T>(T);

pub struct Collector { global: Pad<AtomicUsize>, locals: [Pad<AtomicUsize>; MAX_THREADS] }

impl Collector {
    pub fn new() -> Self {
        Collector { global: Pad(AtomicUsize::new(0)), locals: std::array::from_fn(|_| Pad(AtomicUsize::new(FREE))) }
    }
    pub fn register(&self) -> Handle<'_> {
        for (i, l) in self.locals.iter().enumerate() {
            if l.0.compare_exchange(FREE, 0, Relaxed, Relaxed).is_ok() {
                return Handle { c: self, i, bag: Vec::new() };
            }
        }
        panic!("more than MAX_THREADS participants");
    }
    fn try_advance(&self) -> usize {
        let g = self.global.0.load(Relaxed);
        fence(SeqCst); // pairs with the fence in pin()
        for l in &self.locals {
            let v = l.0.load(Relaxed);
            if v != FREE && v & 1 == 1 && v >> 1 != g { return g; } // a thread is still pinned in g-1
        }
        fence(Acquire);
        let _ = self.global.0.compare_exchange(g, g + 1, Release, Relaxed);
        self.global.0.load(Relaxed)
    }
}

pub struct Handle<'c> { c: &'c Collector, i: usize, bag: Vec<(usize, Box<dyn FnOnce()>)> }
pub struct Guard<'h, 'c> { h: &'h mut Handle<'c> }

impl<'c> Handle<'c> {
    pub fn pin(&mut self) -> Guard<'_, 'c> {
        let g = self.c.global.0.load(Relaxed);
        self.c.locals[self.i].0.store((g << 1) | 1, Relaxed);
        fence(SeqCst); // announcement is visible before we read any shared pointer
        Guard { h: self }
    }
}
impl Drop for Handle<'_> {
    fn drop(&mut self) { self.c.locals[self.i].0.store(FREE, Release); } // leftover bag is leaked (crossbeam hands it to a global queue)
}

impl Guard<'_, '_> {
    /// `free` must release an object that is already unlinked from every shared location.
    pub fn retire(&mut self, free: impl FnOnce() + 'static) {
        fence(SeqCst); // the unlink is ordered before reading the epoch
        let e = self.h.c.global.0.load(Relaxed);
        self.h.bag.push((e, Box::new(free)));
        if self.h.bag.len() >= 64 { self.collect(); }
    }
    fn collect(&mut self) {
        let g = self.h.c.try_advance();
        let (ready, keep): (Vec<_>, Vec<_>) =
            std::mem::take(&mut self.h.bag).into_iter().partition(|(e, _)| g.wrapping_sub(*e) >= 2);
        self.h.bag = keep;
        for (_, free) in ready { free(); }
    }
}
impl Drop for Guard<'_, '_> {
    fn drop(&mut self) { self.h.c.locals[self.h.i].0.store(0, Release); } // all reads done before unpin
}

// Usage: swap a shared config; readers deref only while pinned.
// let mut g = handle.pin();
// let old = shared.swap(Box::into_raw(Box::new(new_cfg)), AcqRel);
// g.retire(move || unsafe { drop(Box::from_raw(old)) });

Complexity and constants

• Pin/unpin: order of 5-20 ns (the SeqCst fence dominates; crossbeam replaces it on x86 with a cheaper locked instruction).
• Advance: O(threads) loads of other threads' lines (cache misses), amortized by collecting every 64-128 retirements.
• Unreclaimed memory: normally a few bags per thread; unbounded if any thread stays pinned.
• Hart et al. measured EBR and QSBR faster than hazard pointers on traversal-heavy structures, with performance collapsing under thread preemption.

Efficiency

• Cost: pin and unpin are one store plus one SeqCst fence, order of 5-20 ns, with no per-object work for readers. Retire is a push to a thread-local bag; the O(threads) epoch scan is amortized over 64-128 retirements. Memory is a few bags per thread, unbounded while any thread stays pinned. Bound: fence latency on the read path, cache misses of the epoch scan, garbage volume under stalls.
• Levers:
  • pin per operation and repin in long traversals — lets the epoch advance and bounds garbage (crossbeam Guard::repin) — long scans
  • collect every 64-128 retirements — amortizes the O(threads) scan (order of) — high retire rates
  • cheaper fence on x86, a locked instruction instead of mfence (crossbeam-epoch, see Complexity) — hot pin path on x86
  • sealed bags in a global queue — garbage of exited threads still gets freed — thread churn
  • quiescent-state reclamation (RCU QSBR) when you own the thread loops — no pin cost (Hart et al.) — kernel or event-loop code
• Naive → standard → state of the art:
  • reference count per node · a shared-counter write on every read, stops scaling
  • epoch-based reclamation with thread-local bags (crossbeam-epoch) · order of 5-20 ns per pin
  • QSBR, or interval/era schemes with bounded garbage · no pin cost, or epoch-like speed with bounded memory

Implementation notes

• Keep pins short: pin per operation, not per request; never pin across I/O, locks, or await.
• Batch: bags of 64 objects; seal bags into a global lock-free queue so garbage from exited threads still gets freed (crossbeam does this).
• Repin periodically in long traversals (crossbeam Guard::repin) to let the epoch advance.
• The retiring thread need not be the freeing thread; deleters must be Send in a global-queue design.
• Store the participant list in a lock-free list (crossbeam) instead of a fixed array to support any number of threads.
• Pointers obtained while pinned must not escape the guard's lifetime; crossbeam's Shared<'g, T> ties them to the guard in the type system.

Pitfalls

• Freeing (or reusing) a node before unlinking it from all paths: EBR only protects against readers who could reach it before the unlink.
• Long-running pinned threads (a reader stuck on a page fault, a debugger breakpoint, a preempted thread) block reclamation: memory grows until OOM.
• Calling retire for an object still reachable: use-after-free when the epoch advances.
• Nested pins with a non-reentrant implementation: the inner unpin unpins the outer operation.
• Running deleters that themselves pin or take locks: possible deadlocks or reentrancy issues.

Variants and alternatives

In production

Databases: Microsoft FASTER builds its key-value store on an epoch protection framework (SIGMOD 2018); the Bw-Tree uses a centralized epoch-based garbage collection scheme (Wang et al.). OS kernels and network stacks: FreeBSD's epoch(9) ("kernel epoch based reclamation"), used by the network stack via NET_EPOCH_ENTER (sys/net/if.c). Language libraries: crossbeam-epoch (Rust; used by crossbeam-skiplist, crossbeam-deque buffer resizing, many concurrent maps), Keir Fraser's lock-free skip lists and BSTs, libcds (C++; offers HP, DHP and RCU-like schemes), DPDK's QSBR library (rte_rcu_qsbr) for the closely related quiescent-state scheme.

Implementations

Sources

• Keir Fraser, Practical Lock-Freedom, PhD thesis, University of Cambridge, 2004 (UCAM-CL-TR-579). paper
• Thomas E. Hart, Paul E. McKenney, Angela Demke Brown, Jonathan Walpole, Performance of Memory Reclamation for Lockless Synchronization, Journal of Parallel and Distributed Computing 67(12), 2007. paper
• Trevor Brown, Reclaiming Memory for Lock-Free Data Structures: There has to be a Better Way, PODC 2015 (DEBRA). paper
• crossbeam-epoch source and documentation. docs · code