Safe memory reclamation: hazard pointers and RCU

The Treiber stack from the previous skill has a hole you could only paper over: when try_pop wins the CAS on head, it owns the node — but it can't delete it, because another thread may have loaded the same head a moment earlier and be about to read node->next. Keeping every popped node until the stack dies (deferred reclamation) is correct but leaks memory for as long as the structure lives.

This skill solves the problem properly, twice:

• Hazard pointers — each reader announces the one object it is about to use; a reclaimer frees only objects nobody has announced.
• RCU (read-copy-update), here as epoch-based reclamation — readers announce that they're reading; a writer replaces the shared pointer and waits for a grace period until every reader that could have seen the old version has finished.

Both are coming to the standard library in C++26 (<hazard_pointer>, <rcu>), but GCC 16 doesn't ship them yet — so you'll build the mechanisms yourself. All code in this skill runs under ThreadSanitizer.

1. The reclamation problem, precisely

B did nothing wrong: it read a pointer that was the head. The question a reclamation scheme answers is: when can no thread still hold a pointer to this node? "When it was removed from the structure" is not the answer.

2. Hazard pointers

Each thread owns a few hazard slots — single-writer atomic pointers that anyone can read. To use a shared object, a thread publishes its address in a slot. To free a removed object, a thread retires it onto a list; a scan reads every slot and frees retired objects that no slot holds.

#include <array>
#include <atomic>
#include <print>
#include <vector>

struct Domain {
    std::array<std::atomic<const int*>, 4> slots{};
    std::vector<int*> retired;

    void retire(int* p) { retired.push_back(p); }

    int scan() {
        std::array<const int*, 4> hz{};
        for (std::size_t i = 0; i < slots.size(); ++i) hz[i] = slots[i].load(std::memory_order_seq_cst);
        int freed = 0;
        std::vector<int*> keep;
        for (int* p : retired) {
            bool protected_ = false;
            for (const int* h : hz) protected_ |= (h == p);
            if (protected_) keep.push_back(p);
            else { delete p; ++freed; }
        }
        retired.swap(keep);
        return freed;
    }
};

int main() {
    Domain d;
    int* a = new int(1);
    int* b = new int(2);
    d.slots[0].store(a);           // someone is reading a
    d.retire(a);
    d.retire(b);
    std::println("freed {}", d.scan());   // only b
    d.slots[0].store(nullptr);     // reader done
    std::println("freed {}", d.scan());   // now a
}

Two details make or break it.

Publish, then re-validate

Publishing the pointer you loaded is not enough. Between src.load() and your store into the slot, the object may have been removed, retired and scanned — the scan saw no hazard, freed it, and your hazard arrived too late. So after publishing, load the source again; only if it still holds the same pointer was the object reachable when your hazard became visible, and any later reclaimer must see the hazard:

template <class Src>
auto protect(const Src& src) -> decltype(src.load()) {
    auto p = src.load(std::memory_order_seq_cst);
    for (;;) {
        slot.store(p, std::memory_order_seq_cst);          // publish
        auto again = src.load(std::memory_order_seq_cst);  // re-validate
        if (again == p) return p;
        p = again;                                         // it moved: try again
    }
}

Why seq_cst — the store-load handshake

Look at the two sides:

Each thread stores to one variable and then loads the other. This is the classic Dekker pattern: with acquire/release (or relaxed), both loads may read the old values — the reader thinks it's protected, the reclaimer thinks it isn't. Only memory_order_seq_cst on both stores and both loads (or seq_cst fences between them) guarantees that at least one side sees the other. x86 hides this mistake surprisingly often; ARM does not.

There's a second, simpler ordering: when a reader clears its hazard, its reads of the object must happen-before the delete. That needs (at least) a release store when clearing and an acquire load in scan. ThreadSanitizer checks exactly this one — it reports the reader's access racing with delete.

Retire lists and scan thresholds

Scanning reads every slot, so don't do it on every retire. Scan when the retired list reaches a threshold proportional to the number of slots (say 2 × slots): each scan then frees at least half the list, because at most slots objects can be protected. That bounds memory — even if a reader stalls forever, it pins at most the objects in its slots.

Hazard pointers kill ABA too

A Treiber stack's pop can be fooled when a node is freed and its address reused while another thread still compares against it (ABA). With the node protected, it can't be freed, so its address can't be reused, so the CAS can't be fooled.

3. Worked example: the reclaiming stack

std::optional<T> try_pop() {
    HazardDomain::Guard guard(domain_);
    for (;;) {
        Node* n = guard.protect(head_);
        if (!n) return std::nullopt;
        Node* next = n->next;                       // safe: n can't be freed
        if (head_.compare_exchange_strong(n, next)) {
            guard.reset();                          // we own n now
            std::optional<T> out{std::move(n->value)};
            domain_.retire(n);                      // freed by a later scan
            return out;
        }
        // CAS failed: n may already be retired. Re-protect from scratch.
    }
}

Note the failure path: after a failed CAS, n might be gone — never reuse a pointer you no longer protect; start over with protect.

4. RCU and epoch-based reclamation

Hazard pointers protect one object per slot and pay a seq_cst handshake per object. RCU flips the costs: readers do almost nothing, writers do the waiting.

• Readers enter a read-side critical section, read the current pointer, use it, leave. While inside, the object they saw stays alive.
• A writer builds a new version, publishes it with one atomic exchange (readers never see a half-updated object), then waits for a grace period: until every reader that might have seen the old version has left its critical section. Then it frees the old version.

A practical implementation is epoch-based: a global epoch counter, and one slot per reader recording the epoch it entered in (0 = not reading).

#include <atomic>
#include <cstdint>
#include <print>
#include <string>
#include <thread>

std::atomic<std::uint64_t> epoch{1};
std::atomic<std::uint64_t> reader_slot{0};   // one reader, for the demo
std::atomic<std::string*> current{new std::string("v1")};

void writer_update(std::string next) {
    std::string* old = current.exchange(new std::string(std::move(next)));
    std::uint64_t old_epoch = epoch.fetch_add(1);
    for (;;) {                                   // grace period
        std::uint64_t e = reader_slot.load();
        if (e == 0 || e > old_epoch) break;
        std::this_thread::yield();
    }
    delete old;
}

int main() {
    reader_slot.store(epoch.load());             // reader enters
    const std::string* mine = current.load();
    std::jthread w([] { writer_update("v2"); }); // blocks in the grace period...
    std::println("reader still sees {}", *mine); // ...so this is safe
    reader_slot.store(0);                        // reader leaves; writer frees v1
    w.join();
    std::println("now {}", *current.load());
    delete current.load();
}

Why is it safe for the writer to not wait for readers with a newer epoch? A reader stores its epoch, then loads current. The writer exchanges current, then bumps the epoch, then reads the slots. Same store-load handshake as before, again with seq_cst: if the writer saw the reader's slot as 0 or newer, the reader's load of current is guaranteed to see the new version.

Faded example — your turn

Fill in the reader's guard. What must the constructor store, and in what order relative to loading current? What must the destructor do?

ReadGuard(RcuCell& c) : c_(&c), slot_(c.acquire_reader()) {
    /* ??? announce */
    p_ = c.current_.load(std::memory_order_seq_cst);
}
~ReadGuard() {
    /* ??? leave */
}

5. Trade-offs

std::atomic<std::shared_ptr<T>> (C++20) also solves reclamation — the reference count keeps an object alive while anyone holds it — but every reader writes to a shared counter (cache-line ping-pong), and libstdc++'s implementation isn't lock-free.

6. The C++26 API (not yet in GCC 16)

When your standard library catches up, the same ideas look like this:

// C++26, not yet in GCC 16 — shown for reference only.
#include <hazard_pointer>
struct Node : std::hazard_pointer_obj_base<Node> { int value; Node* next; };

std::atomic<Node*> head;
std::hazard_pointer hp = std::make_hazard_pointer();
Node* n = hp.protect(head);      // publish + re-validate, like ours
// ... use n ...
hp.reset_protection();
n->retire();                     // freed once unprotected

// C++26, not yet in GCC 16 — shown for reference only.
#include <rcu>
struct Config : std::rcu_obj_base<Config> { int timeout; };
std::atomic<Config*> cfg;

{   // reader: the default domain is Lockable — lock() = enter, unlock() = leave
    std::scoped_lock lk(std::rcu_default_domain());
    use(cfg.load()->timeout);
}
// writer
Config* old = cfg.exchange(new Config{30});
old->retire();                   // freed after a grace period
std::rcu_synchronize();          // or wait for the grace period explicitly

Summary

• Removing a node from a lock-free structure doesn't stop other threads from holding it. Reclamation schemes decide when nobody can.
• Hazard pointers: publish, then re-validate; retire, then scan; seq_cst for the publish/re-check and remove/scan handshake; memory stays bounded.
• RCU / epochs: readers announce an epoch, writers exchange and wait for a grace period; reads are nearly free, but a stalled reader delays reclamation.
• atomic<shared_ptr> is the simple, slower option.