Hazard pointers

Deep dive

How it works

In: a shared pointer source to read; unlinked objects to retire · Out: a pointer safe to dereference until cleared; freed objects no hazard names · State: H hazard slots, one retired list per thread · Cost: protect O(1) with a store-load fence (order of 10-30 ns); scan amortized O(1) per retired object at R = 2H

reader                                   reclaimer
p = src.load()                           unlink node X (CAS src)
loop: hp = p; fence(SeqCst)              retired.push(X)
      if src.load() == p: break          if retired.len() >= R:
      p = src.load()                         fence(SeqCst); H = all hazards
use *p ... hp = null                         free retired - H

1. Protect: load p, store it into a hazard slot, fence(SeqCst), reload the source; if it changed, repeat with the new value. On success p cannot be freed until the slot is cleared.
2. Retire: after unlinking X from every shared location, append X to the thread's retired list.
3. Scan (when the list reaches R, e.g. 2H): fence, snapshot all hazard slots into a sorted array or hash set, free retired objects not in it, keep the rest.
4. The two fences form a Dekker pattern: either the reader's re-validation sees the unlink (and retries) or the reclaimer's scan sees the hazard.
5. With R = 2H, each scan frees at least H objects, so scan cost is amortized O(1) (hash set) per retired object.

Code

use std::ptr;
use std::sync::atomic::{fence, AtomicBool, AtomicPtr, Ordering::{Acquire, Relaxed, Release, SeqCst}};

const H: usize = 128; // total hazard slots in the domain

#[repr(align(64))]
struct Slot { hazard: AtomicPtr<u8>, used: AtomicBool }

pub struct Domain { slots: [Slot; H] }

impl Domain {
    pub fn new() -> Self {
        Domain { slots: std::array::from_fn(|_| Slot { hazard: AtomicPtr::new(ptr::null_mut()), used: AtomicBool::new(false) }) }
    }
    pub fn hazard(&self) -> Hazard<'_> {
        for (i, s) in self.slots.iter().enumerate() {
            if s.used.compare_exchange(false, true, Acquire, Relaxed).is_ok() { return Hazard { d: self, i }; }
        }
        panic!("out of hazard slots");
    }
}

pub struct Hazard<'d> { d: &'d Domain, i: usize }

impl Hazard<'_> {
    /// Returns the current value of `src`, protected until `clear()` or drop.
    pub fn protect<T>(&self, src: &AtomicPtr<T>) -> *mut T {
        let hp = &self.d.slots[self.i].hazard;
        let mut p = src.load(Relaxed);
        loop {
            hp.store(p.cast(), Relaxed);
            fence(SeqCst); // hazard visible before we re-validate (store -> load ordering)
            let q = src.load(Acquire);
            if q == p { return p; }
            p = q;
        }
    }
    pub fn clear(&self) { self.d.slots[self.i].hazard.store(ptr::null_mut(), Release); }
}
impl Drop for Hazard<'_> {
    fn drop(&mut self) { self.clear(); self.d.slots[self.i].used.store(false, Release); }
}

/// Per-thread retired list.
pub struct Retired<'d> { d: &'d Domain, list: Vec<(*mut u8, Box<dyn FnOnce()>)> }

impl<'d> Retired<'d> {
    pub fn new(d: &'d Domain) -> Self { Retired { d, list: Vec::new() } }

    /// # Safety: `p` came from `Box::into_raw` and is unlinked from every shared location.
    pub unsafe fn retire<T: 'static>(&mut self, p: *mut T) {
        self.list.push((p.cast(), Box::new(move || unsafe { drop(Box::from_raw(p)) })));
        if self.list.len() >= 2 * H { self.scan(); }
    }

    pub fn scan(&mut self) {
        fence(SeqCst); // our unlinks are ordered before reading hazards
        let mut hz: Vec<*mut u8> =
            self.d.slots.iter().map(|s| s.hazard.load(Acquire)).filter(|p| !p.is_null()).collect();
        hz.sort_unstable();
        let (keep, free): (Vec<_>, Vec<_>) =
            std::mem::take(&mut self.list).into_iter().partition(|(p, _)| hz.binary_search(p).is_ok());
        self.list = keep;
        for (_, f) in free { f(); }
    }
}

// Reader: let h = domain.hazard(); let node = h.protect(&head); if !node.is_null() { unsafe { (*node).value } }

Complexity and constants

• Protect: 1 store + mfence/dmb ish + 1 load, order of 10-30 ns; retries only when the source changed.
• Scan: H loads of hazard lines (cache misses, order of H × 50 ns worst case) + sort/hash; amortized over ≥ H freed objects.
• Memory bound: each thread holds < R retired objects plus at most H protected overall.
• Hart et al. found hazard pointers slower than EBR/QSBR on traversals because of the per-node fence, but immune to stalled threads.

Efficiency

• Cost: protect is one store, one fence and one reload, order of 10-30 ns on x86; a retry only when the source changed. A scan reads H hazard lines (order of H × 50 ns worst case) and is amortized over at least H freed objects. Memory is bounded: under R retired objects per thread plus at most H protected. Bound: the store-load fence per protected pointer.
• Levers:
  • asymmetric fences — the reader's fence becomes a plain store, the reclaimer pays a membarrier or FlushProcessWriteBuffers (order of µs to tens of µs per scan) (Folly) — read-heavy workloads
  • scan threshold R = 2H — each scan frees at least H objects, so O(1) amortized — always
  • hash set or sorted array of hazards — O(1) or O(log H) lookups per retired object — large H
  • shared retired list with a counter — avoids every thread scanning H slots — many threads
  • fewer hops per operation — one fence per hop — prefer for queues, stacks, hash buckets; use EBR for long traversals
• Naive → standard → state of the art:
  • reference count per node · a shared-counter write on every hop
  • hazard pointers with a SeqCst fence per protect · order of 10-30 ns per hop
  • asymmetric fences, or hazard eras/IBR · plain store on the read path, bounded garbage

Implementation notes

• Asymmetric fences (Folly): replace the reader's fence(SeqCst) with a compiler-only barrier and have the reclaimer issue a process-wide barrier (membarrier(MEMBARRIER_CMD_PRIVATE_EXPEDITED) on Linux 4.14+, FlushProcessWriteBuffers on Windows). Readers become a plain store; scans cost a syscall with IPIs (order of µs to tens of µs).
• Hand-over-hand traversal needs two slots: protect the next node in slot B while still holding the current in slot A, then swap roles.
• Validation must also check the node is still logically in the structure when the protocol requires it (e.g. Michael's list checks the predecessor's mark bit).
• Pre-allocate per-thread slots in a thread-local cache to avoid the CAS search in hazard().
• Cohorts and tagged retirement (Folly) let a whole structure's garbage be reclaimed at destruction.
• Batch scans across threads (a shared retired list with a counter) to avoid every thread scanning H slots.

Pitfalls

• Skipping re-validation after publishing the hazard: the object may have been freed between the load and the store.
• Missing the fence (or using Release/Acquire only): the store-buffer reordering lets both sides miss each other.
• Protecting a pointer read from a node that is itself not protected (e.g. node->next after node was freed).
• Retiring an object that is still reachable through another path.
• Retired lists of exiting threads must be handed off, or they leak.
• Using hazard pointers for ABA protection is fine only while the object is protected; tagged pointers or sequence counters are still needed for CAS on recycled nodes in some algorithms.

Variants and alternatives

In production

Language standard and libraries: C++26 std::hazard_pointer (from P2530), Folly hazptr (used by Folly's ConcurrentHashMap and queues), libcds (C++), Rust crate haphazard (port of Folly's design). Reclamation-scheme toolkits: xenium (C++) ships hazard pointers next to epoch-based reclaimers.

Implementations

Sources

• Maged M. Michael, Hazard Pointers: Safe Memory Reclamation for Lock-Free Objects, IEEE Transactions on Parallel and Distributed Systems 15(6), 2004. paper
• Thomas E. Hart, Paul E. McKenney, Angela Demke Brown, Jonathan Walpole, Performance of Memory Reclamation for Lockless Synchronization, JPDC 67(12), 2007. paper
• Maged Michael, Michael Wong, Paul McKenney, et al., P2530: Hazard Pointers for C++26, WG21 proposal. paper · code
• Pedro Ramalhete, Andreia Correia, Brief Announcement: Hazard Eras - Non-Blocking Memory Reclamation, SPAA 2017.