Epoch-Based Reclamation in Lock-Free C++

Epoch-based reclamation (EBR) is a memory management strategy designed to safely reclaim dynamically allocated memory in lock-free concurrent data structures without relying on a tracing garbage collector. This article covers the fundamental mechanics of EBR, why it is critical for resolving safe memory reclamation problems in concurrent systems, how global and local epochs interact, and how to implement this pattern effectively using modern C++ memory ordering and synchronization primitives.

The Memory Reclamation Problem in Lock-Free Code

In concurrent, lock-free data structures (such as lock-free linked lists, queues, or skip lists), removing a node typically involves atomically swinging a pointer to bypass that node via std::atomic::compare_exchange_strong or compare_exchange_weak.

However, detaching a node from the shared structure does not mean it can be immediately deallocated with delete. Other reader threads may have loaded a pointer to that node just before the pointer swap occurred and may still be reading its contents. Freeing the memory immediately causes a data race and undefined behavior via use-after-free. Postponing deletion indefinitely causes memory leaks, while using traditional reference counting mechanisms (std::shared_ptr) often introduces atomic increment/decrement bottlenecks that negate the performance benefits of lock-free architectures.

EBR solves this dilemma by deferring the destruction of detached objects until it is mathematically impossible for any reader thread to still hold a reference to them.

Core Mechanics of Epoch-Based Reclamation

EBR coordinates threads using a small set of generational counters, typically cycling through three states: 0, 1, and 2. The system is governed by three primary components:

Global Epoch Counter: A single atomic integer (ranging 0 to 2) visible to all threads.
Thread-Local Epochs and Active Flags: Each thread maintains an active flag indicating whether it is currently accessing shared memory, along with a local snapshot of the epoch it observed when it began reading.
Retirement Lists: Buffers that hold retired nodes earmarked for deletion, segregated by the epoch in which they were detached.

Critical Section Lifecycle

When a thread interacts with a lock-free data structure, it wraps its operations in a critical section:

Entry: The thread marks itself as active and reads the current global epoch into its thread-local epoch storage.
Access: The thread navigates and reads lock-free nodes safely.
Exit: The thread marks itself as inactive.

Object Retirement and Reclamation Cycle

When a mutating thread unlinks a node from the concurrent structure:

The node is not deleted; instead, it is placed into a retirement queue tagged with the current global epoch (\(e\)).
Periodically, a thread attempts to advance the global epoch from \(e\) to \((e + 1) \pmod 3\).
The epoch can only advance if no active thread is still registered in the epoch prior to \(e\).
Because threads can only observe nodes that were reachable when they entered, and no thread remains in epoch \((e - 2) \pmod 3\), all nodes retired during epoch \((e - 2) \pmod 3\) are guaranteed to be unreferenced.
Memory from epoch \((e - 2) \pmod 3\) is then safely freed.

Applying EBR to C++ Lock-Free Patterns

Implementing EBR in C++ requires leveraging the C++11 memory model, atomic operations, thread-local storage, and RAII (Resource Acquisition Is Initialization).

1. Managing Thread State with Thread-Local Variables

Each thread tracks its state using thread-local storage to prevent cross-core cache invalidations on read-heavy workloads:

#include <atomic>
#include <vector>

struct ThreadEpochState {
    std::atomic<bool> is_active{false};
    std::atomic<uint64_t> local_epoch{0};
};

inline thread_local ThreadEpochState tl_state;

2. RAII Guard for Critical Sections

An RAII guard ensures that a thread’s active status is reset even if exceptions occur:

class EpochGuard {
public:
    EpochGuard(std::atomic<uint64_t>& global_epoch) {
        tl_state.local_epoch.store(global_epoch.load(std::memory_order_relaxed), 
                                  std::memory_order_relaxed);
        tl_state.is_active.store(true, std::memory_order_seq_cst);
    }

    ~EpochGuard() {
        tl_state.is_active.store(false, std::memory_order_release);
    }

    EpochGuard(const EpochGuard&) = delete;
    EpochGuard& operator=(const EpochGuard&) = delete;
};

Using std::memory_order_seq_cst or appropriate acquire/release fences ensures that memory reads inside the critical section cannot be reordered prior to setting is_active to true.

3. Retirement Queues and Deferred Destruction

Retired nodes are stored using polymorphic deleters or simple linked buffers:

struct RetiredNode {
    void* ptr;
    void (*deleter)(void*);
};

class EpochManager {
    std::atomic<uint64_t> global_epoch{0};
    std::vector<ThreadEpochState*> registry;
    std::vector<RetiredNode> retired_bins[3];

public:
    template <typename T>
    void retire(T* ptr) {
        uint64_t current = global_epoch.load(std::memory_order_relaxed);
        retired_bins[current % 3].push_back({
            ptr, 
            [](void* p) { delete static_cast<T*>(p); }
        });
    }

    void try_advance_and_reclaim() {
        uint64_t current = global_epoch.load(std::memory_order_relaxed);

        // Verify that all active threads have caught up to the current epoch
        for (auto* thread : registry) {
            if (thread->is_active.load(std::memory_order_acquire)) {
                if (thread->local_epoch.load(std::memory_order_relaxed) != current) {
                    return; // A thread is still in an older epoch; abort epoch advance
                }
            }
        }

        // Advance the global epoch
        global_epoch.store((current + 1), std::memory_order_relaxed);

        // It is now safe to free memory retired two epochs ago
        size_t safe_bin = (current + 2) % 3; 
        for (auto& item : retired_bins[safe_bin]) {
            item.deleter(item.ptr);
        }
        retired_bins[safe_bin].clear();
    }
};

Trade-offs and Best Practices in C++

Throughput: EBR delivers near-zero overhead on read paths compared to hazard pointers, as it relies on thread-local operations rather than atomic updates per node read.
The Stalling Hazard: If a single thread stalls, blocks on I/O, or experiences an OS descheduling event while inside an EpochGuard, the global epoch cannot advance. Consequently, retired nodes accumulate across all threads, leading to unbounded memory usage.
Short Critical Sections: In C++, lock-free algorithms utilizing EBR must ensure that critical sections are short and deterministic. Never perform I/O, block on condition variables, or yield CPU control while an epoch guard is active.