Lock-Free Programming

Obstruction-free → Lock-free → Wait-free
(blocking)          (≥1 thread  (all threads
                    progresses) progress)

#include <atomic>

std::atomic<int>    a;
std::atomic<double> b;

bool a_lf = a.is_lock_free();          // C++11: runtime query
bool b_lf = b.is_lock_free();          // double is not lock-free on all platforms

// C++17: compile-time query
static_assert(std::atomic<int>::is_always_lock_free);
static_assert(std::atomic<void*>::is_always_lock_free);
// std::atomic<double>::is_always_lock_free is false on some platforms

std::atomic<int> val{0};

// compare_exchange_weak: may spuriously fail on LL/SC architectures (ARM, PowerPC, RISC-V)
// Spurious failure means: val == expected but CAS returns false anyway.
// Always use inside a retry loop — the compiler/hardware exploits this for efficiency.
int expected = 0;
bool ok = val.compare_exchange_weak(expected, 42,
                                    std::memory_order_acq_rel,   // success order
                                    std::memory_order_acquire);  // failure order

// compare_exchange_strong: only fails if val != expected.
// Use when the transformation inside the loop is expensive and spurious retries hurt.
ok = val.compare_exchange_strong(expected, 42);

// Canonical CAS loop: atomically apply a function to the current value
int old_val = val.load(std::memory_order_relaxed);
int new_val;
do {
    new_val = expensive_transform(old_val);
} while (!val.compare_exchange_weak(old_val, new_val,
                                    std::memory_order_release,
                                    std::memory_order_relaxed));
// Postcondition: val was changed atomically from old_val to new_val
// old_val holds the value that was in val at the moment of the winning CAS

// relaxed — atomicity only; no ordering constraints relative to other operations
// Correct for independent counters where only the count matters, not ordering.
hits.fetch_add(1, std::memory_order_relaxed);

// release (stores) / acquire (loads) — the standard producer-consumer pair
// A release store synchronizes-with a subsequent acquire load on the same atomic.
// All stores before the release become visible after a matching acquire.
data = compute();                                   // non-atomic write
ready.store(true, std::memory_order_release);       // publishes data

// ... on another thread:
while (!ready.load(std::memory_order_acquire));     // waits for publication
process(data);                                      // guaranteed to see compute() result

// acq_rel — for read-modify-write ops that act as both acquire and release
// Use in the success arm of compare_exchange on a node that links to prior stores.
head.compare_exchange_weak(old, node,
                           std::memory_order_acq_rel,   // success
                           std::memory_order_acquire);  // failure

// seq_cst — total order across ALL seq_cst operations globally (the default)
// Required to prevent IRIW (Independent Reads of Independent Writes) reorderings
// that release/acquire alone cannot prevent. Costs a full barrier on ARM (dmb ish).
val.store(1);     // seq_cst by default
val.load();       // seq_cst by default

template<typename T>
class TreiberStack {
    struct Node {
        T     value;
        Node* next;
    };
    std::atomic<Node*> top_{nullptr};

public:
    void push(T value) {
        Node* node = new Node{std::move(value), nullptr};
        // Load current top into node->next before entering CAS loop
        node->next = top_.load(std::memory_order_relaxed);
        // Release so that readers who acquire-load this node see value initialized
        while (!top_.compare_exchange_weak(node->next, node,
                                           std::memory_order_release,
                                           std::memory_order_relaxed))
            ;  // CAS failure updates node->next automatically — no extra load
    }

    std::optional<T> pop() {
        Node* old_top = top_.load(std::memory_order_acquire);
        while (old_top) {
            // WARNING: old_top->next is read here before we own the node.
            // A concurrent pop could delete old_top between our load and this read.
            // This is a use-after-free in any multi-threaded program that frees nodes.
            // Safe reclamation (hazard pointers, epoch-based, RCU) is required.
            Node* next = old_top->next;
            if (top_.compare_exchange_weak(old_top, next,
                                           std::memory_order_acquire,
                                           std::memory_order_acquire))
                break;  // old_top is updated to current top on CAS failure
        }
        if (!old_top) return std::nullopt;
        T value = std::move(old_top->value);
        delete old_top;  // safe: CAS success means we uniquely own this node
        return value;
    }
};

struct TaggedPtr {
    Node*    ptr;
    uint64_t tag;  // increment on every push/pop
};
// Requires 128-bit CAS: __int128 on GCC/Clang, or CMPXCHG16B intrinsic on x86-64
std::atomic<TaggedPtr> top_;

#include <atomic>
#include <memory>

struct Config { std::string endpoint; int timeout_ms; };

// C++20: std::atomic<shared_ptr<T>> — proper specialization (not just free functions)
std::atomic<std::shared_ptr<const Config>> g_config{
    std::make_shared<Config>("https://api.example.com", 5000)
};

// Writer: old config lives until the last reader drops its shared_ptr
void reload(Config c) {
    g_config.store(std::make_shared<Config>(std::move(c)));
}

// Readers: lock-free snapshot, no possibility of dangling pointer
void handle_request() {
    auto cfg = g_config.load();              // atomic refcount bump
    send(cfg->endpoint, cfg->timeout_ms);   // cfg pinned for the lifetime of this scope
}                                            // shared_ptr destructor releases refcount

class Spinlock {
    std::atomic_flag flag_ = ATOMIC_FLAG_INIT;  // C++11 required for guaranteed clear state
    // C++20: {} value-initialization is sufficient
public:
    void lock()   { while (flag_.test_and_set(std::memory_order_acquire)); }
    void unlock() { flag_.clear(std::memory_order_release); }
};

// hazard_pointer_obj_base<T, D = default_delete<T>>
// Inherit from this to make T retirable via the HP runtime.
// Provides retire() — schedules deferred deletion once no hazard slot holds &obj.
template<class T, class D = std::default_delete<T>>
class std::hazard_pointer_obj_base;

// hazard_pointer — RAII slot handle (single-writer, multi-reader)
// Obtained via make_hazard_pointer(); released when it goes out of scope.
class std::hazard_pointer {
public:
    template<class T> T* protect(const std::atomic<T*>& src) noexcept;
    // Atomically loads src, publishes the address into this slot, then
    // re-validates. Loops internally if the value changed between load and
    // publish. Returns the protected pointer (may be null).

    template<class T> bool try_protect(T*& ptr, const std::atomic<T*>& src) noexcept;
    // Non-looping variant; returns false if validation fails.

    template<class T> void reset_protection(const T* ptr) noexcept;
    void reset_protection(std::nullptr_t = nullptr) noexcept;
    // Clear the slot — stop protecting the current pointer.

    bool empty() const noexcept;
};

std::hazard_pointer std::make_hazard_pointer(); // acquire a slot from the runtime pool

#include <hazard_pointer>
#include <atomic>
#include <optional>

template<typename T>
class TreiberStack {
    struct Node : std::hazard_pointer_obj_base<Node> {
        T     value;
        Node* next;
    };
    std::atomic<Node*> top_{nullptr};

public:
    void push(T value) {
        Node* node = new Node{std::move(value), nullptr};
        node->next = top_.load(std::memory_order_relaxed);
        while (!top_.compare_exchange_weak(node->next, node,
                                           std::memory_order_release,
                                           std::memory_order_relaxed))
            ;
    }

    std::optional<T> pop() {
        // One hazard slot per pop() call; RAII-cleared when hp goes out of scope.
        std::hazard_pointer hp = std::make_hazard_pointer();
        Node* old_top;

        do {
            // protect() loads top_ and publishes the address atomically.
            // No concurrent thread may reclaim this node while hp holds it.
            old_top = hp.protect(top_);
            if (!old_top) return std::nullopt;

            // Safe: old_top is protected — it cannot be freed between the
            // protect() call above and the CAS below.
            Node* next = old_top->next;

            if (top_.compare_exchange_weak(old_top, next,
                                           std::memory_order_acquire,
                                           std::memory_order_acquire))
                break;  // We own old_top exclusively after a successful CAS.
        } while (true);

        hp.reset_protection();      // Release the hazard slot before retiring.
        T value = std::move(old_top->value);
        old_top->retire();          // Schedules deletion; runtime frees when safe.
        return value;
    }
};

// C++11
#include <atomic>
#include <array>
#include <thread>
#include <functional>
#include <vector>

static constexpr int MAX_THREADS = 64;

// Per-thread hazard slots — one pointer per thread, per protected operation.
// Must be accessed only by the owning thread (write) and reclaimer (read).
struct HazardSlot {
    std::atomic<void*> ptr{nullptr};
};
std::array<HazardSlot, MAX_THREADS> g_hazard_slots;

// Thread-local index into g_hazard_slots; assigned once per thread on first use.
inline int get_thread_slot() {
    static std::atomic<int> next_slot{0};
    thread_local int slot = next_slot.fetch_add(1, std::memory_order_relaxed);
    return slot;
}

// Protect a pointer: publish it before dereferencing so no reclaimer frees it.
template<class T>
T* hazard_protect(std::atomic<T*>& src) {
    int slot = get_thread_slot();
    T* p;
    do {
        p = src.load(std::memory_order_acquire);
        g_hazard_slots[slot].ptr.store(p, std::memory_order_release);
        // Re-validate: if src changed between load and publish, retry.
    } while (p != src.load(std::memory_order_acquire));
    return p;
}

// Release protection for the calling thread's slot.
inline void hazard_release() {
    g_hazard_slots[get_thread_slot()].ptr.store(nullptr, std::memory_order_release);
}

// Retire a pointer: free it only once no hazard slot holds its address.
// In practice, accumulate retired pointers in a thread-local list and
// scan lazily (e.g., every R retired pointers, where R = k * MAX_THREADS).
template<class T>
void hazard_retire(T* p, std::vector<std::pair<void*, std::function<void(void*)>>>& retired) {
    retired.emplace_back(p, [](void* ptr) { delete static_cast<T*>(ptr); });
    if (retired.size() < 2 * MAX_THREADS) return;  // batch threshold

    // Snapshot all hazard slots.
    std::vector<void*> hazards;
    hazards.reserve(MAX_THREADS);
    for (auto& slot : g_hazard_slots)
        if (void* h = slot.ptr.load(std::memory_order_acquire); h)
            hazards.push_back(h);

    // Keep nodes that are still protected; free the rest.
    auto it = retired.begin();
    while (it != retired.end()) {
        bool protected_ = std::find(hazards.begin(), hazards.end(), it->first) != hazards.end();
        if (!protected_) { it->second(it->first); it = retired.erase(it); }
        else             { ++it; }
    }
}

// C++11
#include <atomic>
#include <optional>

template<typename T>
class MPSCQueue {
    struct Node {
        T                  value;
        std::atomic<Node*> next{nullptr};
    };

    // Producers update tail_; consumer owns head_.
    // Stub node eliminates empty-queue special cases.
    Node*              head_;       // consumer-only; no atomic needed
    std::atomic<Node*> tail_;

public:
    MPSCQueue() {
        Node* stub = new Node{};    // sentinel: head == tail == stub when empty
        head_ = stub;
        tail_.store(stub, std::memory_order_relaxed);
    }

    ~MPSCQueue() {
        while (dequeue());          // drain
        delete head_;               // delete the stub
    }

    // Producer path: lock-free, contention only on tail_ swap.
    void enqueue(T value) {
        Node* node = new Node{std::move(value)};
        // Atomically swing tail_ to the new node, get back the previous tail.
        Node* prev = tail_.exchange(node, std::memory_order_acq_rel);
        // Link the previous tail to the new node.  This store is visible to
        // the consumer once the acquire on the dequeue side sees tail_.
        prev->next.store(node, std::memory_order_release);
    }

    // Consumer path: single-threaded; no atomics required on head_.
    std::optional<T> dequeue() {
        Node* next = head_->next.load(std::memory_order_acquire);
        if (!next) return std::nullopt;  // queue is empty

        // Advance head_ past the stub/previous-front node.
        // The old head_ becomes the new stub.
        T value = std::move(next->value);
        delete head_;
        head_ = next;
        return value;
    }
};

// C++11
// Build: clang++ -std=c++17 -fsanitize=thread -fno-omit-frame-pointer -g -O1 test.cpp
// Run normally — TSan reports race reports to stderr with full stack traces.
// Note: -O1 is recommended over -O0; some races only manifest with optimizations.

#include <atomic>
#include <thread>

std::atomic<int> counter{0};

void bad_race() {
    // TSan will NOT flag this — it IS atomic.
    counter.fetch_add(1, std::memory_order_relaxed);
}

int shared = 0;  // non-atomic

void actual_race() {
    // TSan WILL flag this — non-atomic write from two threads is a data race.
    shared++;     // UB: concurrent non-atomic access
}

// C++11
// Development workflow: start with seq_cst, verify, then relax.
// Step 1: all seq_cst — proves algorithm structure is correct.
head_.compare_exchange_weak(old, node,
    std::memory_order_seq_cst,   // success
    std::memory_order_seq_cst);  // failure

// Step 2: after CDSChecker/Relacy passes, relax to minimum required:
head_.compare_exchange_weak(old, node,
    std::memory_order_acq_rel,   // success: pairs with acquire in pop
    std::memory_order_acquire);  // failure: we'll re-read through 'old'