Lock-free Data Structures

1. Atomic Primitives

The bedrock of any lock-free design is the compare-and-swap (CAS) primitive. Modern CPUs expose it via instructions like CMPXCHGon x86 and LDREX/STREXon ARM. Treat every shared word as an atomic and reason about memory ordering explicitly.

2. The ABA Problem

CAS only checks the current value, not the history. If a pointer goes A -> B -> A, a stale CAS will succeed and silently corrupt your structure. Common mitigations: tagged pointers (pack a version counter in the high bits), hazard pointers, or epoch-based reclamation. Pick one before you write a single line of code.

3. Treiber Stack

The canonical lock-free stack. Push and pop both spin on a CAS against the head pointer. Below is a minimal sketch using C++ atomics, suitable as a starting template before you layer in safe reclamation:

template<typename T>
class TreiberStack {
  struct Node { T value; Node* next; };
  std::atomic<Node*> head_{nullptr};
public:
  void push(T v) {
    Node* n = new Node{std::move(v), nullptr};
    n->next = head_.load(std::memory_order_relaxed);
    while (!head_.compare_exchange_weak(
        n->next, n,
        std::memory_order_release,
        std::memory_order_relaxed)) {}
  }
  bool pop(T& out) {
    Node* old = head_.load(std::memory_order_acquire);
    while (old && !head_.compare_exchange_weak(
        old, old->next,
        std::memory_order_acquire,
        std::memory_order_relaxed)) {}
    if (!old) return false;
    out = std::move(old->value);
    return true;
  }
};