Epoch-Based Reclamation, in depth: the epoch invariant, fences, crossbeam-epoch and stalled readers

The idea: protect intervals, not pointers

Hazard pointers protect individual pointers: a reader publishes exactly which node it is about to touch. EBR protects time intervals instead. A thread announces "I am inside an operation" when it starts (it pins) and "I am out" when it finishes (it unpins). Between those points it may hold any number of pointers into the structure without further bookkeeping. A node removed at some moment can be freed once every thread that was pinned at that moment has unpinned, since any thread that pins afterwards cannot reach a node that is already unlinked.

Tracking "every thread that was pinned at that moment" per node would be expensive, so EBR quantises time into epochs. There are three pieces of state:

• a global epoch counter G, shared by all threads;
• a per-thread announcement slot, holding either "quiescent" or the epoch the thread observed when it pinned;
• per-thread lists of retired nodes, each tagged with an epoch (conceptually three "limbo bags", because only three epochs of garbage can be alive at once).

The protocol and why two epochs are enough

The protocol has four operations.

1. Pin. Read G, store it into your announcement slot, then execute a full (sequentially consistent) fence before touching any shared pointer.
2. Retire. After a node has been unlinked so that no new reader can find it, append it to your limbo list tagged with the current global epoch.
3. Try to advance. Occasionally, read G and scan every announcement slot. If every pinned thread announced G, compare-and-swap G to G + 1. If anyone announced an older epoch, give up for now.
4. Collect. Free every node in your limbo list whose tag t satisfies t + 2 ≤ G.

Why is t + 2 safe? Suppose a node was unlinked while the global epoch was t. A thread that still holds a pointer to it must have pinned before the unlink, so it announced some epoch at most t. G can move from t + 1 to t + 2 only after every pinned thread has announced t + 1, which forces that reader to have unpinned. Threads pinning later cannot find the node at all. So once G = t + 2, no thread can hold it. The same argument shows that at any instant pinned threads have announced either G or G − 1, which is why three bags suffice: G − 2 is free, and G − 1 and G may still be in use.

Two details in that argument are easy to get wrong. First, the tag must be the global epoch read after the unlink, not the epoch the retiring thread pinned in, because G may have moved on while the retirer was pinned, and a reader may have pinned in the newer epoch before the unlink. Second, the announcement must be visible to other threads before the pinned thread's first load of a shared pointer. That is a store-then-load ordering, which on x86 and Arm is only guaranteed by a full fence; acquire and release are not enough.

A teaching implementation in C++

Here is a compact C++ version showing every moving part. It is teaching code (fixed thread registry, no nested pins); in production use a library such as liburcu or Folly.

#include <atomic>
#include <cstdint>
#include <vector>

constexpr unsigned kMaxThreads = 64;
constexpr uint64_t kQuiescent  = ~0ull;

struct alignas(64) Slot { std::atomic<uint64_t> epoch{kQuiescent}; };  // one cache line each
std::atomic<uint64_t> g_epoch{0};
Slot g_slots[kMaxThreads];

struct Retired { void* p; void (*del)(void*); uint64_t tag; };
thread_local unsigned t_id;                  // set when the thread registers
thread_local std::vector<Retired> t_limbo;
thread_local unsigned t_retires = 0;

void pin() {
  g_slots[t_id].epoch.store(g_epoch.load(std::memory_order_relaxed),
                            std::memory_order_relaxed);
  std::atomic_thread_fence(std::memory_order_seq_cst);   // announce BEFORE any shared load
}

void unpin() {
  g_slots[t_id].epoch.store(kQuiescent, std::memory_order_release);  // reads happen-before this
}

bool try_advance() {
  uint64_t g = g_epoch.load(std::memory_order_seq_cst);
  for (unsigned i = 0; i < kMaxThreads; ++i) {
    uint64_t e = g_slots[i].epoch.load(std::memory_order_seq_cst);
    if (e != kQuiescent && e != g) return false;          // someone is behind
  }
  return g_epoch.compare_exchange_strong(g, g + 1, std::memory_order_seq_cst);
}

void collect() {
  uint64_t g = g_epoch.load(std::memory_order_acquire);
  size_t keep = 0;
  for (Retired& r : t_limbo) {
    if (r.tag + 2 <= g) r.del(r.p);                       // two advances later: unreachable
    else t_limbo[keep++] = r;
  }
  t_limbo.resize(keep);
}

template <class T> void retire(T* p) {                   // call while pinned, AFTER unlinking p
  t_limbo.push_back({p, [](void* q) { delete static_cast<T*>(q); },
                     g_epoch.load(std::memory_order_seq_cst)});
  if (++t_retires % 64 == 0) { try_advance(); collect(); }
}

A pop from a Treiber stack then looks like: pin(); load head; load head->next; CAS head to next; on success retire(head); unpin(). The dereference of head->next is safe even if another thread pops the same node concurrently, because that thread can only retire it, and retirement cannot complete while we are pinned. EBR also removes the classic ABA hazard on freed-and-reused nodes, as discussed in lock-free stacks, since a node's memory cannot be recycled while any thread that saw it is still pinned.

Idiomatic EBR in Rust with crossbeam-epoch

In Rust, crossbeam-epoch packages the same protocol behind the type system. epoch::pin() returns a Guard; pointers loaded through it are Shared<'g, T> values whose lifetime is tied to the guard, so the compiler rejects code that keeps one after unpinning. Retirement is guard.defer_destroy(ptr), which is unsafe because only you know the node has been unlinked. The pop below follows the crate's own Treiber stack example.

use crossbeam_epoch::{self as epoch, Atomic, Owned};
use std::mem::ManuallyDrop;
use std::ptr;
use std::sync::atomic::Ordering::{Acquire, Relaxed, Release};

pub struct Stack<T> { head: Atomic<Node<T>> }
struct Node<T> { data: ManuallyDrop<T>, next: Atomic<Node<T>> }

impl<T> Stack<T> {
    pub fn push(&self, t: T) {
        let mut n = Owned::new(Node { data: ManuallyDrop::new(t), next: Atomic::null() });
        let guard = epoch::pin();
        loop {
            let head = self.head.load(Relaxed, &guard);
            n.next.store(head, Relaxed);
            match self.head.compare_exchange(head, n, Release, Relaxed, &guard) {
                Ok(_) => return,
                Err(e) => n = e.new,                    // CAS failed: get the node back, retry
            }
        }
    }

    pub fn pop(&self) -> Option<T> {
        let guard = epoch::pin();                         // pinned until guard drops
        loop {
            let head = self.head.load(Acquire, &guard);
            let h = unsafe { head.as_ref() }?;
            let next = h.next.load(Relaxed, &guard);
            if self.head.compare_exchange(head, next, Relaxed, Relaxed, &guard).is_ok() {
                unsafe {
                    guard.defer_destroy(head);            // freed two epochs from now
                    return Some(ManuallyDrop::into_inner(ptr::read(&h.data)));
                }
            }
        }
    }
}

Two crate details matter operationally. Deferred destructors are buffered thread-locally and moved to a global queue in batches, so a thread that retires rarely can sit on garbage; guard.flush() pushes it out. And the crate makes no promise about when a destructor runs, only that it will not run while any thread pinned at retirement time is still pinned, so avoid destructors with side effects.

Worked example: what one stalled reader costs

EBR's weakness follows directly from the advance rule: if one pinned thread stops making progress, G stops advancing, and nobody frees anything. To see the size of the effect, here is a step simulation. Four threads take random turns; each turn pins, retires one node and unpins, and every 64 retirements someone tries to advance. Optionally thread 0 pins and is then descheduled.

import random

def simulate(threads=4, steps=6000, stall=None, advance_every=64, seed=1):
    # Three-epoch EBR as a step simulation. stall = (tid, start, end) pins tid and freezes it.
    rnd = random.Random(seed)
    g = 0                                  # global epoch
    local = [None] * threads               # None = not pinned, else the epoch read at pin
    bags = [0, 0, 0]                       # retired-node counts per epoch, mod 3
    pending = peak = since = 0
    for step in range(steps):
        t = rnd.randrange(threads)
        if stall and t == stall[0] and stall[1] <= step < stall[2]:
            if local[t] is None:
                local[t] = g               # pinned, then descheduled mid-operation
            continue
        local[t] = g                       # pin
        bags[g % 3] += 1                   # retire one unlinked node
        pending += 1
        local[t] = None                    # unpin
        since += 1
        if since >= advance_every:
            since = 0
            if all(e is None or e == g for e in local):
                g += 1
                pending -= bags[(g + 1) % 3]   # epoch g-2's bag is now safe to free
                bags[(g + 1) % 3] = 0
        peak = max(peak, pending)
    return g, pending, peak

Without a stall, garbage stays near two advance intervals' worth (peak 127). A 3,000-step stall inflates the peak almost 19-fold until the thread resumes. A permanent stall turns EBR into a leak: every retirement after step 1,000 stays in memory. In a real system the "stall" is a reader preempted by the OS, a thread blocked on I/O while holding a guard, or a long scan that pins for its whole duration.

Variants that fix the weak spot

• Quiescent-state-based reclamation (QSBR), the scheme behind classic kernel RCU, removes even the pin cost: threads periodically declare "I hold no references", and a grace period ends when everyone has done so. It is faster still, but every thread must cooperate by reporting quiescence.
• DEBRA (Trevor Brown, 2015) makes EBR's bookkeeping cheap and amortised, and its DEBRA+ extension uses signals to neutralise stalled threads, restoring bounded garbage.
• Hazard eras and interval-based reclamation attach birth and retire epochs to every node, so a stalled thread only blocks nodes that were alive during its interval. They sit between EBR's speed and hazard pointers' bounds.

Operational guidance

• Keep guards short. Pin for one operation, never across I/O, locks, user callbacks or an await point. In Rust, do not store a Guard in a long-lived struct; use Guard::repin in long loops.
• Export the backlog. Track the current epoch, how long since it last advanced, and retired-but-unfreed bytes. An epoch that stops advancing is the earliest warning of a stuck reader, long before memory alarms fire.
• Tune the advance interval. Trying to advance on every retire makes the announcement scan a hot spot; trying too rarely grows the backlog. Every 32 to 128 retirements per thread is a common range. Measure with your own workload.
• Account for thread exit. A thread that exits with garbage must hand it to a global list, and its slot must be marked quiescent, or both leak.
• Expect bursty frees. Freeing a whole bag at once can stall the collecting thread and stress the allocator; cap how many nodes one collect frees.

Failure modes

• Missing fence on pin. Storing the announcement with release ordering and then loading a shared pointer lets the load be reordered before the store. An advancer can miss the announcement and free a node the reader is about to touch. x86 allows this reordering too, so the bug is not Arm-only; it just appears only under load.
• Tagging with the retirer's local epoch. If G advanced while the retirer was pinned, a newer reader may hold the node, and the bag is freed one epoch early.
• Retiring before unlinking. If a node is still reachable when it is retired, new readers can find it after the bag ages out.
• Using a retired node after unpinning. The guard ends protection; copy out what you need first. Rust's lifetimes catch this, C++ does not.
• Unbounded memory with a stalled reader, as measured above. This is the reason to prefer hazard pointers when readers can block or when memory must be bounded.

Trade-offs against hazard pointers

EBR wins throughput for short, read-heavy operations on hash maps, skip lists and the structures in lock-free queues; hazard pointers win when memory must stay bounded under any scheduling.

What to do next

1. Run the simulation, then vary advance_every and the number of threads and plot peak unfreed nodes; confirm the stall result yourself.
2. Port the Rust stack to a project with crossbeam-epoch, and run it under Miri or ThreadSanitizer while removing defer_destroy to see the leak, then adding a premature free to see the failure.
3. Audit every place your code pins: list what it does while pinned and move I/O, locks and callbacks outside the guard.
4. Add three metrics to any service using EBR: current epoch, seconds since the last advance and unfreed bytes, with an alert on a stalled epoch.
5. Decide per structure whether stalled readers are possible; if they are, read hazard pointers and consider a bounded scheme for that structure.