Hazard Pointers for Safe Memory Reclamation in C++

Hazard pointers are a lock-free memory reclamation technique designed to solve the reader-reclaimer race condition in concurrent C++ applications. In multithreaded environments where lock-free data structures are modified dynamically, deleting a node while another thread is still reading it leads to undefined behavior, data corruption, or segmentation faults. Hazard pointers provide a mechanism where reading threads temporarily "publish" the addresses of nodes they are currently accessing to a globally visible list. Writers wanting to remove a node mark it as retired rather than freeing it immediately, deferring deallocation until no active hazard pointers reference that memory.

The Problem: Memory Reclamation in Lock-Free Code

In concurrent data structures like lock-free stacks, queues, and linked lists, threads modify pointers using atomic operations like std::atomic::compare_exchange_weak. While updating pointers atomically ensures structural integrity, it does not solve the lifecycle problem of the removed node:

  1. Thread A reads a shared pointer to Node X and prepares to access Node X->next.
  2. Thread B preempts Thread A, unlinks Node X from the structure, and immediately calls delete Node X.
  3. Thread A resumes and attempts to dereference Node X->next, accessing memory that has already been deallocated.

Standard C++ smart pointers like std::shared_ptr solve this via reference counting, but atomic operations on std::shared_ptr can introduce substantial cache contention, high overhead, and can still be prone to race conditions if not manipulated via atomic utilities.

The Core Mechanics of Hazard Pointers

The hazard pointer approach decouples structural modification from memory deallocation through four core phases:

1. Allocation and Publication

Each reader thread owns one or more hazard pointer slots—typically implemented as std::atomic<T*> pointers within a globally visible array or list. Before dereferencing a node retrieved from a shared structure, the thread publishes the node's raw address to its hazard pointer slot:

T* ptr = head.load(std::memory_order_acquire);
do {
    hazard_ptr.store(ptr, std::memory_order_release);
    T* current_head = head.load(std::memory_order_acquire);
    if (ptr == current_head) {
        break; // Pointer successfully validated
    }
    ptr = current_head;
} while (true);

2. Validation

Publishing a pointer is not enough because the node could have been unlinked and retired right before the hazard pointer was stored. The reading thread must perform a validation check: verifying that the shared pointer still matches the address stored in the hazard pointer. If the node was unlinked before the publication took effect, the thread clears the hazard pointer and retries.

3. Retirement

When a modifying thread unlinks a node from the global structure, it does not invoke delete. Instead, it adds the node's pointer to a thread-local retired list. Because other threads might still possess valid references to this node that were published before the unlinking, the node must remain valid in memory for the time being.

4. Reclamation and Scanning

Once a thread's retired list reaches a predefined threshold, the thread triggers a reclamation scan:

  1. The thread collects all active hazard pointers published by all threads into a local list.
  2. It sorts or hashes these pointers to allow fast lookups.
  3. It iterates through its retired list. If a retired node's address is found among the collected hazard pointers, it remains in the retired list. If the address is absent, no reading thread is accessing it, and it is safely deallocated using delete.

Concurrency and Memory Ordering in C++

Hazard pointers rely heavily on strict memory orderings defined in the C++ memory model:

  • Acquire-Release Semantics: When a thread publishes to its hazard pointer, it uses std::memory_order_release (or sequentially consistent ordering) to guarantee that any prior setup is visible. The reader reads the shared structure using std::memory_order_acquire.
  • Sequential Consistency: In typical implementations, the publication of the hazard pointer and the subsequent re-read of the structure's pointer must not be reordered by the compiler or the CPU. A std::atomic_thread_fence(std::memory_order_seq_cst) is frequently required between storing the hazard pointer and validating the node.

Hazard Pointers vs. Alternative Reclamation Schemes

  • Epoch-Based Reclamation (EBR): EBR tracks time intervals (epochs). It has lower runtime overhead than hazard pointers because threads do not write to shared memory on every node access. However, if a single thread stalls in an epoch, all memory reclamation across the entire system halts. Hazard pointers do not suffer from this; an unresponsive reader only prevents the deallocation of the specific nodes it holds in its hazard slots.
  • Reference Counting (std::shared_ptr): Atomic reference counting writes to the node's shared control block on every read and write, creating high cache-coherence traffic. Hazard pointers write only to thread-local or pre-assigned memory slots, drastically reducing contention on shared cache lines.

Hazard pointers, which have been formalized in C++26 under the <hazard_pointer> header, strike an optimal balance for high-performance concurrent code: they provide deterministic, non-blocking progress guarantees and bounded memory usage while allowing readers to proceed concurrently without acquisition of mutual-exclusion locks.