Hazard Pointers, in depth: publish and validate, slot counts per structure, hand-over-hand traversal, the scan bound and the C++26 API

The protocol and its fences

The read side is a publish-then-validate loop. Load the pointer p from the shared location, store p into your hazard slot, then load the shared location again. If it still holds p, the node is protected: it was reachable at a moment after your hazard became visible, so it cannot yet have been retired, and any scan that sees it retired later will also see your slot. If the location changed, retry.

The memory ordering is the subtle part. The store to the slot must be visible to other threads before the re-load reads the source; that is a store-to-load ordering, which acquire and release do not give you. Use a sequentially consistent store or a full fence between them. On the reclaim side, the unlink must happen before the scan reads the slots, again with a full fence. Do not assume x86 protects you: store-to-load reordering through the store buffer is the one reordering x86 allows, so a missing fence is a real bug there too, just a rare one that ordinary tests seldom hit.

The fence on every protect is the main read-side cost. Production libraries such as folly's hazptr use asymmetric fences: the reader issues only a compiler barrier, and the reclaimer issues a heavyweight process-wide barrier (on Linux, the membarrier system call) before scanning, which is a good trade because scans are rare.

A minimal domain and a stack pop

Here is a minimal domain with a fixed number of slots per thread, and a Treiber stack pop that uses one slot. It shows the structure, not a tuned implementation.

constexpr int kMaxThreads = 64, kSlots = 2;
constexpr int H = kMaxThreads * kSlots;          // total hazard slots
constexpr int R = 2 * H;                         // scan threshold

struct alignas(64) Slot { std::atomic<void*> p{nullptr}; };
Slot g_slots[H];
thread_local std::vector<Node*> t_retired;

template <class T>
T* protect(int slot, const std::atomic<T*>& src) {
    T* p = src.load(std::memory_order_relaxed);
    for (;;) {
        g_slots[slot].p.store(p, std::memory_order_seq_cst);  // publish
        T* q = src.load(std::memory_order_seq_cst);          // validate
        if (q == p) return p;
        p = q;
    }
}
void clear(int slot) { g_slots[slot].p.store(nullptr, std::memory_order_release); }

void scan() {
    std::atomic_thread_fence(std::memory_order_seq_cst);
    std::unordered_set<void*> hazards;
    for (auto& s : g_slots)
        if (void* p = s.p.load(std::memory_order_acquire)) hazards.insert(p);
    std::vector<Node*> keep;
    for (Node* n : t_retired)
        if (hazards.count(n)) keep.push_back(n); else delete n;
    t_retired.swap(keep);
}
void retire(Node* n) {
    t_retired.push_back(n);
    if (t_retired.size() >= R) scan();
}

// Treiber stack pop: my_slot is this thread's first slot index.
Node* pop(std::atomic<Node*>& top, int my_slot) {
    for (;;) {
        Node* t = protect(my_slot, top);
        if (!t) { clear(my_slot); return nullptr; }
        Node* next = t->next;                  // safe: t is protected
        if (top.compare_exchange_weak(t, next)) {
            clear(my_slot);
            return t;      // caller reads the value, then calls retire(t)
        }
    }
}

Two details carry the correctness. Reading t->next is safe only because t is protected. And the CAS cannot suffer ABA on t: while t sits in a hazard slot it cannot be freed, so its address cannot be reused by a new node.

Worked trace: a pop racing a pop

Walk through the race the scheme exists for. The stack holds A on top of B. Thread T1 starts a pop and thread T2 pops concurrently.

1. T1 loads top and gets A.
2. T2 completes a pop: its CAS moves top from A to B, and it calls retire(A). A is now on T2's retire list, not freed.
3. T1 stores A into its slot, issues the fence, and re-reads top. It sees B, not A, so validation fails and T1 never dereferences A. It retries with B.
4. Alternative timing: T1 publishes A and validates before T2's CAS. T1 now holds a protected A. T2 unlinks and retires A, and when T2's list later reaches R, scan finds A in T1's slot and keeps it. T1 reads A->next safely, its CAS fails because top is now B, and it clears the slot. The next scan frees A.
5. Without hazard pointers, T2 could free A and allocate a new node at the same address, push it, and T1's CAS from A to its stale next would succeed and corrupt the stack. With A protected that reuse cannot happen.

In both orders, the only window where A is dereferenced is one where a fence-ordered slot holds it, and every scan reads slots only after the retire is visible.

How many slots each structure needs

Each structure needs as many slots as the number of nodes a thread must hold simultaneously, and that is a property of the algorithm:

Traversal uses hand-over-hand protection. To step from cur to next, protect next in a free slot, then check that cur->next still equals next and that cur is not logically deleted (the Harris-Michael list marks the low bit of the next pointer). If either check fails, cur may already be unlinked, and a retired node gives no guarantee that its next pointer leads anywhere live; restart from the head. Then rotate the slot roles so the old prev slot becomes free.

This restart rule is the real cost of hazard pointers in long traversals: under heavy concurrent deletion a reader can restart repeatedly, and each step pays a publish and a validation.

The scan threshold and the memory bound

Let H be the total number of hazard slots across threads and R the per-thread threshold that triggers a scan. A scan keeps only nodes that some slot names, so at most H nodes survive it. With R = 2H, every scan frees at least R - H = H nodes, and with a hash set for the snapshot each scan costs O(R) expected time, so reclamation is O(1) amortized per retire.

The memory bound is the point: each thread holds at most R retired nodes plus the ones its last scan kept, so the total is O(P · R) for P threads no matter what any thread is doing. A thread that stalls holding hazards pins at most its own few nodes. Compare epoch-based reclamation, where one stalled reader inside a critical section prevents every thread from freeing anything.

Worked example: 64 threads with 2 slots each give H = 128 and R = 256. Each thread scans after 256 retires, reads 128 slots, and frees at least 128 nodes. Worst-case garbage is about 64 × 256 = 16,384 nodes, roughly 1 MB at 64 bytes per node, a bound you can state in a capacity plan.

The C++26 standard interface

C++26 standardises the scheme in the <hazard_pointer> header, derived from folly's implementation (proposal P2530, voted into the C++26 working draft in 2023). The interface, as listed on cppreference: objects derive from std::hazard_pointer_obj_base<T, D>, which provides retire(D d = D()); a thread obtains a std::hazard_pointer from std::make_hazard_pointer() and calls protect(const std::atomic<T*>&), try_protect or reset_protection.

#include <hazard_pointer>

struct Config : std::hazard_pointer_obj_base<Config> {
    std::string endpoint;
    int timeout_ms;
};
std::atomic<Config*> g_config;

int current_timeout() {
    std::hazard_pointer hp = std::make_hazard_pointer();
    Config* c = hp.protect(g_config);      // publish + validate loop inside
    return c->timeout_ms;                  // hp's destructor clears the protection
}

void update(Config* fresh) {
    Config* old = g_config.exchange(fresh);
    old->retire();                         // freed once no hazard names it
}

Check whether your standard library ships the header before relying on it; folly's hazptr is the production-tested reference in the meantime. Rust users should compare a hazard-pointer crate with crossbeam-epoch, which is epoch-based.

Operational guidance

• Pad slots to a cache line. Slots are written by one thread and read by every scanner; sharing a line between threads causes false sharing on every protect.
• Retire, never delete. Make direct deletes of shared nodes a code-review failure, and route all frees through the domain.
• Export metrics. Retire-list length per thread, scans per second and nodes freed per scan. A list that grows without bound means a slot is leaked or a thread exited without handing off.
• Mind node size. The bound counts nodes, not bytes; a structure of 1 MB buffers needs a lower threshold or a byte-based trigger.
• Register threads dynamically in real systems instead of a fixed maximum, reusing slot records released by exited threads.

Failure modes

• Missing store-load fence between publish and validate: a reclaimer misses the hazard and frees a node in use. Rare, architecture-dependent crashes.
• Protecting after dereferencing. Any read through the pointer before validation succeeds is unprotected.
• Traversing from a retired node. Validation of the source pointer is mandatory at every step; restart instead of continuing.
• Leaked slots. A slot never cleared pins one node forever; tie slots to RAII objects.
• Thread exit with a non-empty retire list. Hand leftovers to a global list or a surviving thread, or memory leaks per short-lived thread.
• Too few slots for the algorithm, which silently reuses a slot that still guards a needed node.

Trade-offs against other reclamation schemes

Prefer epochs or RCU for read-mostly structures where readers are short and well behaved, and hazard pointers where memory must be bounded, readers can be preempted for long periods, or nodes are large.

What to do next

1. Write the minimal domain above and a Treiber stack, then stress it under AddressSanitizer and ThreadSanitizer on both x86 and Arm.
2. Delete the seq_cst fence on purpose and confirm your stress test catches it; if it does not, the test is too weak.
3. Count the slots your structure needs before coding, using the table above.
4. Instrument retire-list length and scan frequency, and check the O(P · R) bound holds.
5. Read the lock-free stack, lock-free queues, atomic operations and the lock-free introduction.