Lock-Free Memory Reclamation in C

Lock-free data structures in C achieve high concurrency without traditional locks, but they face a critical obstacle known as the safe memory reclamation problem. Because C lacks automatic garbage collection, a thread cannot safely invoke free() on an unlinked node while concurrent reader threads might still be dereferencing it, risking use-after-free vulnerabilities and ABA issues. Hazard Pointers and Epoch-Based Reclamation (EBR) solve this problem by providing structured, deterministic mechanisms to track concurrent reader access and defer deallocation until nodes are guaranteed to be unreferenced.

The Problem: Safe Memory Reclamation and ABA

In a lock-free structure (such as a Treiber stack or Michael-Scott queue), threads modify shared data using atomic operations like atomic_compare_exchange_weak. When a node is detached from the shared structure, other threads may have already read a pointer to that node and may be preempted before accessing its payload. If the removing thread immediately calls free(), any preempted thread will later dereference dangling memory. Furthermore, if that memory is reallocated and reintroduced into the structure at the same address, it can trigger the ABA problem, where an atomic compare-and-swap succeeds incorrectly because the address matches even though the data state has changed.

Hazard Pointers

Hazard pointers solve this issue through fine-grained, thread-local reservations. Each thread owns a small, globally visible array of pointers called hazard pointers.

  1. Acquiring a Reference: Before a reader thread accesses a node, it writes the node's memory address into one of its hazard pointers using an atomic store with appropriate memory ordering (typically memory_order_seq_cst or a fence). It then re-checks whether the node is still part of the data structure. If the node was unlinked before the hazard pointer was set, the thread aborts and retries.
  2. Retiring Nodes: When a thread unlinks a node, it does not call free(). Instead, it places the node into a thread-private "retired list."
  3. Reclamation: Once the retired list reaches a defined threshold, the thread scans the hazard pointer arrays of all active threads. Any retired node whose address does not appear in any thread's hazard pointer list is safely freed via free(). Nodes that are currently protected remain in the retired list for the next reclamation cycle.

Trade-offs: Hazard pointers provide strong safety guarantees and bounded memory usage. A stalled thread can only prevent the reclamation of the specific nodes it actively protects. However, writing to hazard pointers introduces reader-side overhead because readers must execute atomic writes and memory barriers for every node traversal.

Epoch-Based Reclamation (EBR)

Epoch-Based Reclamation shifts the tracking granularity from individual nodes to temporal phases (epochs). The system maintains a global epoch counter (typically cycling through 0, 1, and 2) and an active epoch flag for each thread.

  1. Entering Critical Sections: A reader thread marks itself as active and copies the current global epoch into its thread-local state using atomic_load(&global_epoch).
  2. Access and Exit: The thread traverses the data structure freely without updating shared pointers or performing atomic writes during traversal. Upon finishing, the thread clears its active flag.
  3. Retiring Nodes: When a node is detached, it is added to a retirement list associated with the current global epoch.
  4. Epoch Advancement: A designated thread periodically checks the local states of all active threads. If all threads have observed the current epoch, the global epoch advances (\(E_{new} = (E_{current} + 1) \pmod 3\)). Memory retired two epochs prior (\(E - 2\)) is guaranteed to have no active readers and can be safely passed to free().

Trade-offs: EBR offers high read performance because readers only perform lightweight loads and stores when entering and exiting critical sections, with zero atomic synchronization during node traversal. Its primary drawback is that a single stalled or slow thread inside a critical section halts epoch progression, causing retired nodes to accumulate and resulting in unbounded memory growth.

Summary of Differences

  • Hazard Pointers are reference-centric, track individual pointers, impose higher read-side costs, but strictly bound memory reclamation delays to the specific nodes in use.
  • Epoch-Based Reclamation is time-centric, groups operations into phases, delivers near-zero read overhead, but risks delayed reclamation across the entire system if a thread stalls.