Lock-Free Concurrency: Memory Barriers, CAS & Hazard Pointers

1. Problem & Context: From Atomic CAS to Safe Memory Reclamation (SMR)

In CORE-M05-001, we established hardware memory models (x86-64 Total Store Order vs. ARM64 Weak Ordering), MESI cache-line coherence, atomic Compare-And-Swap (CAS) loops, and epoch-based Read-Copy-Update (RCU). Yet when building dynamic, pointer-linked lock-free data structures in unmanaged systems languages (C, C++, Rust, Zig)—such as RocksDB MemTable SkipLists, Meta Folly queues, or Linux kernel lockless lists—a critical question remains: when can a thread safely free() an unlinked node?

In a garbage-collected runtime (JVM, Go, V8), unlinked nodes remain valid in heap memory until no thread holds a reference. Without a stop-the-world GC, lock-free memory reclamation faces a severe trade-off between Epoch-Based Reclamation (EBR / RCU) and Hazard Pointers (HP):

1. The Vulnerability of Epoch-Based Reclamation (EBR): As seen in CORE-M05-001, EBR/RCU has near-zero read overhead, but a single stalled or preempted reader thread pins the global epoch, causing unbounded memory growth (OOM) across all retiring threads.
2. The Two-Slot Dereference Race in Lock-Free Queues: In the Michael-Scott Queue, a dequeuing thread must inspect two nodes simultaneously: the sentinel curHead node and its successor next = curHead.next (whose next.value payload is read before advancing head). If another thread dequeues and frees next in that window, dereferencing next.value triggers an immediate use-after-free segmentation fault (SIGSEGV)—and if the allocator recycles that freed block for a new node, a raw pointer CAS suffers the ABA problem.
3. Why Hazard Pointers Bound Memory Deterministically ($K=2$): Maged Michael’s Hazard Pointer protocol assigns each thread $K$ globally visible hazard slots ($K=2$ for the Michael-Scott queue: slot 0 protecting curHead and slot 1 protecting next). Because any node not listed in an active hazard slot can be freed immediately during a batch scan—even if another reader thread is stalled—unreclaimed memory is strictly bounded by $\mathcal{O}(K\cdot P^2)$ across $P$ threads!

2. Mental Model & Architectural Abstraction

The hierarchy of non-blocking concurrency guarantees:

┌────────────────────────────────────────────────────────┐
│  Blocking (Locks / Mutexes / Semaphores)               │
│  - Vulnerable to deadlocks, priority inversion, stalls  │
└──────────────────────────┬─────────────────────────────┘
                           │ (Eliminates OS sleep & context switches)
                           ▼
┌────────────────────────────────────────────────────────┐
│  Lock-Free Guarantee                                   │
│  - At least ONE thread makes forward progress in a     │
│    bounded number of steps. Contending threads retry.  │
│  - Examples: Michael-Scott Queue, Treiber Stack, CAS   │
└──────────────────────────┬─────────────────────────────┘
                           │ (Eliminates individual thread starvation)
                           ▼
┌────────────────────────────────────────────────────────┐
│  Wait-Free Guarantee                                   │
│  - EVERY thread makes forward progress in a bounded    │
│    number of its OWN steps. Zero retries or loops.     │
│  - Examples: Bounded SPSC Ring Buffer, RCU reads       │
└────────────────────────────────────────────────────────┘

The fundamental mental abstraction is the Optimistic Atomic Loop:

1. Read current state $A$.
2. Compute new state $B$ in private CPU registers.
3. Attempt atomic commit via CAS(address, expected=A, new=B).
4. If CAS succeeds: mutation complete.
5. If CAS fails (another core updated the address first): discard private registers, reload the latest state, and retry.

3. Core Terminology & Guarantees

4. System Architecture & Component Anatomy

SYSTEM ARCHITECTURE BLUEPRINTCOMPUTER ARCHITECTURE

⤢Expand

ARCHITECTURAL FLOW · STEP 1 OF 3

1. CPU Reordering and Memory Fences & Hardware Store Buffers

Establishes the ingress and structural boundary across CPU Reordering and Memory Fences & Hardware Store Buffers: CPU writes to fast FIFO buffer Stores visible to other cores late; Release: Stores before fence flush; Acquire: Subsequent loads not hoisted.

Architectural Invariant: Thread 1 reads top Node A (next=B) and pauses before CAS Thread 2 pops A, pops B, and pushes recycled Node A back.

ARCHITECTURAL FLOW · STEP 2 OF 3

2. Catastrophic Corrupted State & Remediation: Tagged Pointers / Version Epochs

Coordinates core data-plane execution and state transitions through Catastrophic Corrupted State & Remediation: Tagged Pointers / Version Epochs: Thread 1 wakes up: CAS(expected=A, new=B) SUCCEEDS!; Stack top is set to freed Node B! Memory corruption / crash. Value matched, but underlying state was mutated and freed; Pack 48-bit memory address with 16-bit monotonic counter Double-Word CAS (CMPXCHG16B on x86) checks (Ptr, Stamp) Tag increments from A(v1) -> B(v2) -> A(v3); CAS cleanly fails!.

Architectural Invariant: When retired list exceeds limit: Check all thread Hazard Pointers Free node ONLY if zero readers hold it.

ARCHITECTURAL FLOW · STEP 3 OF 3

3. Michael-Scott Lock-Free Queue Algorithm (Atomic CAS Enqueue and Dequeue) & Queue Anatomy (Dummy Node Invariant)

Enforces durability, state convergence, and output verification across Michael-Scott Lock-Free Queue Algorithm (Atomic CAS Enqueue and Dequeue) & Queue Anatomy (Dummy Node Invariant): Queue always initialized with 1 sentinel dummy node Head points to dummy node; Tail points to last node Eliminates empty-queue race condition; 1. CAS tail.next from NULL to newNode; 2. CAS Tail pointer from oldTail to newNode.

Architectural Invariant: 3. CAS Head from oldHead to head.next.

Deep Architecture Anatomy:

1. CPU Memory Models (x86 TSO vs. ARM Weak Ordering):
   • x86-64 (Total Store Order - TSO): Strongly ordered. Loads are not reordered with loads; stores are not reordered with stores. Only Store-Load reordering is permitted (stores can be delayed in the hardware store buffer while subsequent loads execute).
   • ARM64 / POWER: Weakly ordered. The hardware aggressively reorders Load-Load, Load-Store, Store-Store, and Store-Load unless explicit memory barrier instructions (DMB ISHLD, DMB ISHST) are emitted.
2. The ABA Problem in Lock-Free Stacks:
   • Thread 1 attempts to pop from a Treiber Stack: reads top node $A$ (which points to $B$).
   • Thread 1 is preempted by the OS scheduler right before executing CAS.
   • Thread 2 pops $A$, pops $B$, frees $B$‘s memory, and pushes $A$ back onto the stack.
   • Thread 1 resumes: calls CAS(top, expected=A, new=B). Because top is still $A$, CAS succeeds!
   • Result: The stack top points to $B$, which was already freed and contains garbage memory!
3. Safe Memory Reclamation (Hazard Pointers):
   • Developed by Maged Michael (2004).
   • Eliminates the need for a runtime garbage collector in systems languages (C, C++, Rust).
   • Guarantees $O(1)$ amortized memory reclamation overhead without taking read locks.

5. Detailed Request Flows & Protocols

5.1 The Michael-Scott Lock-Free Queue Enqueue Flow

Thread 1 (Enqueuer)              Tail Pointer               Tail.next Pointer           New Node (N)
         │                            │                            │                         │
         ├── 1. Read Tail (T) ───────>│                            │                         │
         ├── 2. Read T.next ──────────────────────────────────────>│                         │
         │                            │                            │                         │
         ├── [Case A: T.next == NULL] │                            │                         │
         ├── 3. CAS(T.next, NULL, N) ─────────────────────────────>│ (Atomic Link)          │
         │   (Success!)               │                            │                         │
         │                            │                            │                         │
         ├── 4. CAS(Tail, T, N) ─────>│ (Swing Tail pointer)       │                         │
         │   (Even if step 4 fails,   │                            │                         │
         │    subsequent threads will │                            │                         │
         │    help swing the Tail!)   │                            │                         │

1. Read Current Pointers: Read current Tail and Tail.next.
2. Check Lagging Tail: If Tail.next != NULL, another thread linked a new node but has not yet advanced Tail. The current thread cooperatively helps advance Tail via CAS(Tail, oldTail, tailNext) before continuing.
3. Link New Node: Once Tail.next == NULL, attempt CAS(tail.next, NULL, newNode). If another thread links first, reload and retry.
4. Advance Tail Pointer: Swing Tail to point to newNode via CAS(Tail, oldTail, newNode).

6. Mathematical Modeling & Hardware Physics

6.1 Cost of Memory Barriers and Bus Contention

Modern CPUs communicate cache line state across cores via cache coherence protocols (e.g., MESI).

• When core $C_0$ modifies a cache line held by core $C_1$, $C_0$ must broadcast an Invalidation Request.
• $C_1$ must invalidate its L1/L2 cache line and transmit an Invalidation Acknowledgment.

$$\text{Latency of Uncontended L1 Cache Read}\approx 1\text{ ns}(4\text{ CPU cycles})$$ $$\text{Latency of Cross-Socket Invalidation (MESI)}\approx 40\text{ ns}-100\text{ ns}(200-400\text{ CPU cycles})$$ $$\text{Latency of Full Hardware MFENCE Instruction}\approx 20\text{ ns}-35\text{ ns}$$

If multiple threads execute tight CAS loops on the same memory word, cache lines bounce violently across CPU sockets (Cache-Line Bouncing), causing bus saturation and degrading throughput below that of a standard mutex!

6.2 Hazard Pointers Memory Bound

Let:

• $P$ be the number of concurrent threads.
• $K$ be the number of hazard pointers per thread (typically $K=2$ for queues).
• $R$ be the retired list batch threshold.

The total retired unallocated memory waiting to be freed across the entire system is strictly bounded by:

If we configure $R=2\times K\times P$, the number of scanned hazard pointers during each reclamation run is $O(K\times P)$, ensuring that the amortized cost per retired node is:

7. Production TypeScript Implementation

This self-contained TypeScript simulation implements:

1. HazardPointerManager: Thread-local hazard pointer publishing and retired node scanning.
2. TaggedPointer: Eliminates the ABA problem using monotonic version counters.
3. MichaelScottQueue: Full lock-free concurrent queue with sentinel dummy node and cooperative tail advancement.

Execute with: npx tsx lockfree-concurrency-capstone.ts

/**
 * ARCHITECTURE STUDY: Lock-Free Concurrency, CAS & Hazard Pointers
 * Production architectural simulation: Michael-Scott Queue,
 * Tagged Pointers (ABA prevention), and Hazard Pointer Memory Reclamation.
 */

// ==========================================
// 1. Tagged Pointer (ABA Problem Prevention)
// ==========================================

export class TaggedPointer<T> {
  public value: T | null;
  public tag: number;

  constructor(value: T | null, tag: number = 0) {
    this.value = value;
    this.tag = tag;
  }

  equals(other: TaggedPointer<T>): boolean {
    return this.value === other.value && this.tag === other.tag;
  }
}

// ==========================================
// 2. Hazard Pointers Memory Reclamation
// ==========================================

export class HazardPointerManager<T> {
  // K = 2 hazard pointer slots per thread: slot 0 protects curHead/curTail, slot 1 protects next
  public static readonly SLOTS_PER_THREAD = 2;
  private hazardPointers: Map<number, (T | null)[]> = new Map(); // threadId -> [slot0, slot1]
  private retiredLists: Map<number, T[]> = new Map();            // threadId -> retired nodes
  public totalFreedNodes: number = 0;

  registerThread(threadId: number): void {
    this.hazardPointers.set(
      threadId,
      new Array<T | null>(HazardPointerManager.SLOTS_PER_THREAD).fill(null)
    );
    this.retiredLists.set(threadId, []);
  }

  setHazardPointer(threadId: number, slot: number, ptr: T | null): void {
    let slots = this.hazardPointers.get(threadId);
    if (!slots) {
      slots = new Array<T | null>(HazardPointerManager.SLOTS_PER_THREAD).fill(null);
      this.hazardPointers.set(threadId, slots);
    }
    slots[slot] = ptr;
  }

  clearHazardPointers(threadId: number): void {
    const slots = this.hazardPointers.get(threadId);
    if (slots) {
      slots.fill(null);
    }
  }

  retireNode(threadId: number, node: T): void {
    const list = this.retiredLists.get(threadId) || [];
    list.push(node);
    this.retiredLists.set(threadId, list);

    // Threshold R = 2 * K * P (with K = 2 and P >= 1, min threshold 4)
    const activeThreads = Math.max(1, this.hazardPointers.size);
    const threshold = Math.max(4, 2 * HazardPointerManager.SLOTS_PER_THREAD * activeThreads);
    if (list.length >= threshold) {
      this.scanAndReclaim(threadId);
    }
  }

  scanAndReclaim(threadId: number): void {
    const list = this.retiredLists.get(threadId) || [];
    if (list.length === 0) return;

    // Stage 1: Collect all non-null hazard pointers across all threads and all K slots
    const activeHazards = new Set<T>();
    this.hazardPointers.forEach((slots) => {
      for (const ptr of slots) {
        if (ptr !== null) activeHazards.add(ptr);
      }
    });

    // Stage 2: Reclaim any retired node not protected by an active hazard pointer
    const remainingList: T[] = [];
    for (const node of list) {
      if (!activeHazards.has(node)) {
        // Safe to free! Zero readers hold a reference in any hazard slot
        this.totalFreedNodes++;
      } else {
        // Active reader still inspecting: defer freeing
        remainingList.push(node);
      }
    }
    this.retiredLists.set(threadId, remainingList);
  }
}

// ==========================================
// 3. Michael-Scott Lock-Free Queue
// ==========================================

export interface QueueNode<T> {
  value: T | null;
  next: QueueNode<T> | null;
}

export class MichaelScottQueue<T> {
  private head: QueueNode<T>;
  private tail: QueueNode<T>;
  private hpManager: HazardPointerManager<QueueNode<T>>;

  constructor(hpManager: HazardPointerManager<QueueNode<T>>) {
    this.hpManager = hpManager;
    // Sentinel dummy node invariant
    const dummy: QueueNode<T> = { value: null, next: null };
    this.head = dummy;
    this.tail = dummy;
  }

  enqueue(threadId: number, value: T): void {
    const newNode: QueueNode<T> = { value, next: null };

    while (true) {
      const curTail = this.tail;
      // Protect curTail in slot 0 before dereferencing curTail.next
      this.hpManager.setHazardPointer(threadId, 0, curTail);

      if (curTail !== this.tail) continue; // Inconsistent read, retry

      const next = curTail.next;
      if (curTail === this.tail) {
        if (next === null) {
          // Attempt linking new node to tail.next
          // Simulated atomic CAS(curTail.next, null, newNode)
          curTail.next = newNode;
          // Swing tail pointer to newNode
          this.tail = newNode;
          this.hpManager.clearHazardPointers(threadId);
          return;
        } else {
          // Lagging tail detected: cooperatively help advance tail
          this.tail = next;
        }
      }
    }
  }

  dequeue(threadId: number): T | null {
    while (true) {
      const curHead = this.head;
      // Slot 0 protects the sentinel head node
      this.hpManager.setHazardPointer(threadId, 0, curHead);
      if (curHead !== this.head) continue;

      const curTail = this.tail;
      const next = curHead.next;
      // Slot 1 protects next BEFORE we dereference next.value!
      this.hpManager.setHazardPointer(threadId, 1, next);
      if (curHead !== this.head || curHead.next !== next) continue;

      if (curHead === curTail) {
        if (next === null) {
          // Queue is empty
          this.hpManager.clearHazardPointers(threadId);
          return null;
        }
        // Tail lagging behind: help advance tail
        this.tail = next;
      } else if (next !== null) {
        // Safe to dereference next.value because next is protected in hazard slot 1
        const val = next.value;
        // Simulated atomic CAS(head, curHead, next)
        this.head = next;
        // Clear next's payload after it becomes the new dummy sentinel
        next.value = null;
        this.hpManager.clearHazardPointers(threadId);
        // Safely retire the old dummy head node
        this.hpManager.retireNode(threadId, curHead);
        return val;
      }
    }
  }
}

// ==========================================
// 4. Execution & Verification Harness
// ==========================================

export function runLockFreeDemo() {
  console.log("=== ARCHITECTURE STUDY: Lock-Free Concurrency & Hazard Pointers ===");

  const hpManager = new HazardPointerManager<QueueNode<number>>();
  hpManager.registerThread(1);
  hpManager.registerThread(2);

  const queue = new MichaelScottQueue<number>(hpManager);

  console.log("\n[1] Thread 1 Enqueues Elements (Michael-Scott Algorithm):");
  queue.enqueue(1, 100);
  queue.enqueue(1, 200);
  queue.enqueue(1, 300);
  queue.enqueue(1, 400);
  console.log("  Successfully enqueued 4 elements without mutex locks.");

  console.log("\n[2] Thread 2 Dequeues Elements with Hazard Pointer Protection:");
  const val1 = queue.dequeue(2);
  console.log(`  Thread 2 dequeued: ${val1} (Old sentinel retired to private list)`);
  const val2 = queue.dequeue(2);
  console.log(`  Thread 2 dequeued: ${val2}`);
  const val3 = queue.dequeue(2);
  console.log(`  Thread 2 dequeued: ${val3}`);
  const val4 = queue.dequeue(2);
  console.log(`  Thread 2 dequeued: ${val4}`);
  hpManager.scanAndReclaim(2);

  console.log(`  Total nodes safely reclaimed by Hazard Pointer scans: ${hpManager.totalFreedNodes}`);
  console.log(`  Queue empty check: Dequeue => ${queue.dequeue(2)}`);

  console.log("\n[3] ABA Problem Remediation via Tagged Pointers:");
  const ptrA = { id: "node_A" };
  const ptrB = { id: "node_B" };

  const taggedA1 = new TaggedPointer(ptrA, 1);
  const taggedB = new TaggedPointer(ptrB, 2);
  const taggedA2 = new TaggedPointer(ptrA, 3); // A recycled with incremented tag

  console.log(`  Initial Tagged Pointer: [Address: ${taggedA1.value?.id}, Tag: ${taggedA1.tag}]`);
  console.log(`  Intermediate Tagged Pointer: [Address: ${taggedB.value?.id}, Tag: ${taggedB.tag}]`);
  console.log(`  Recycled Tagged Pointer: [Address: ${taggedA2.value?.id}, Tag: ${taggedA2.tag}]`);

  const casMatches = taggedA1.equals(taggedA2);
  console.log(`  Does CAS(expected=A(tag=1), target=A(tag=3)) succeed? ${casMatches ? 'YES (CORRUPTED)' : 'NO (PROTECTED!)'}`);

  console.log("\n=== Lock-Free Concurrency Simulation Complete. Invariants Verified. ===");
}

runLockFreeDemo();

8. Real-World Case Studies

8.1 LMAX Disruptor

• Ultra-high-performance inter-thread messaging library executing over 6 million orders/second at sub-microsecond latency.
• Completely lock-free: eliminates locks and CAS loops by using a pre-allocated circular ring buffer with cache-line-padded monotonic sequence counters, maximizing CPU L1 cache line prefetching.

8.2 Meta Folly (folly::Hazptr)

• Open-source C++ library deployed across thousands of Meta production servers.
• Implements Hazard Pointers for lock-free reader-writer synchronization in RocksDB block cache tables, eliminating read locks and cutting p99 read latency by $30\%$.

8.3 Java Concurrency Utilities (java.util.concurrent)

• ConcurrentLinkedQueue is an exact implementation of the Michael-Scott lock-free queue using Unsafe.compareAndSwapObject.
• AtomicStampedReference implements tagged pointers to prevent the ABA problem in user-level lock-free algorithms.

9. Edge Cases, Failure Modes & Antipatterns

9.1 Cache-Line Bouncing & False Sharing

• Failure Mode: When multiple CPU cores frequently write to independent atomic variables located within the same 64-byte hardware cache line, the CPU hardware bus invalidates the entire cache line across all cores, degrading performance below that of a coarse-grained mutex.
• Remediation: Apply Cache-Line Padding (e.g., alignas(64) in C++ or padding bytes in Java/Go) to ensure concurrent atomic variables reside in physically distinct 64-byte cache lines.

9.2 Memory Reclamation Leaks in Long-Running Readers

• Failure Mode: If a reader thread sets a hazard pointer and subsequently hangs (e.g., waiting on socket I/O), deleting threads can never free the protected node, causing memory accumulation in retired lists.
• Invariant: Hazard pointers must be acquired strictly for short, non-blocking critical read sections and cleared (HP = NULL) immediately afterward.

9.3 Spin-Lock Thundering Herd on Lock-Free Retries

• Failure Mode: Under extreme thread counts (e.g., 128 cores), if hundreds of threads execute tight CAS retry loops on a single pointer, CPU utilization spikes to 100% while actual system throughput drops toward zero due to memory bus saturation.
• Remediation: Inject Exponential Backoff with Jitter (e.g., PAUSE instruction on x86, YIELD on ARM) into failed CAS retry loops.

10. Observability, Metrics & Production Telemetry

11. Guided Hands-On Lab / Engineering Exercises

Lab 1: Implement a Lock-Free Treiber Stack with Tagged Pointers

• Objective: Implement a lock-free Stack (push and pop) in TypeScript using TaggedPointer.
• Deliverable: Inject an intentional thread delay in pop() and demonstrate that recycling a node fails the tagged CAS, preventing the ABA bug.

Lab 2: Benchmark Lock-Free Queue vs. Mutex Queue

• Objective: Run 8 simulated concurrent worker threads pushing and popping 100,000 items.
• Deliverable: Measure total execution time and CPU context switch count for a Mutex Queue vs. Michael-Scott Lock-Free Queue.

Lab 3: Implement Amortized Hazard Pointer Scanning

• Objective: Extend HazardPointerManager to dynamically adjust the retirement threshold $R=2\times K\times P$ based on active thread registration.
• Deliverable: Verify that retired memory is bounded while scan overhead remains $O(1)$ per freed element.

export interface StackNode<T> {
  value: T;
  next: StackNode<T> | null;
}

export class LockFreeTreiberStack<T> {
  private top = new TaggedPointer<StackNode<T>>(null, 0);

  public push(node: StackNode<T>): void {
    while (true) {
      const curTop = this.top;
      node.next = curTop.value;
      const nextTop = new TaggedPointer<StackNode<T>>(node, curTop.tag + 1);
      if (this.casTop(curTop, nextTop)) return;
    }
  }

  public pop(): StackNode<T> | null {
    while (true) {
      const curTop = this.top;
      if (curTop.value === null) return null;
      const nextNode = curTop.value.next;
      const nextTop = new TaggedPointer<StackNode<T>>(nextNode, curTop.tag + 1);
      if (this.casTop(curTop, nextTop)) return curTop.value;
    }
  }

  public casTop(expected: TaggedPointer<StackNode<T>>, next: TaggedPointer<StackNode<T>>): boolean {
    if (this.top.equals(expected)) {
      this.top = next;
      return true;
    }
    return false;
  }
}

12. Comprehensive Summary & Decision Framework

Concurrency Mechanism Trade-Off Matrix

Production Engineering Checklist

1. Cache-Line Alignment: Pad concurrent atomic head and tail pointers to 64-byte boundaries (alignas(64)) to eliminate false sharing.
2. Double-Word CAS: When implementing pointer-swapping lock-free algorithms, always bind a 64-bit pointer with a 64-bit monotonic tag counter to neutralize the ABA trap.
3. Hazard Pointer Cleansing: Ensure every read path clears its hazard pointer in a finally block or RAII destructor.
4. Acquire-Release Discipline: Use std::memory_order_acquire and std::memory_order_release instead of default std::memory_order_seq_cst unless total global sequential ordering is strictly required.

13. Authoritative References & Version Context

• Maged M. Michael (2004), “Hazard Pointers: Safe Memory Reclamation for Lock-Free Objects”, IEEE Transactions on Parallel and Distributed Systems (TPDS) 15(6) — doi.org/10.1109/TPDS.2004.8
• Trevor Brown (2015), “Reclaiming Memory for Lock-Free Data Structures: There has to be a Better Way”, ACM PODC ‘15 (DEBRA epoch reclamation) — doi.org/10.1145/2767386.2767436
• Martin Thompson, Dave Farley, Michael Barker, Patricia Gee, and Andrew Stewart (2011), “Disruptor: High Performance Alternative to Bounded Queues for Exchanging Data Between Threads”, LMAX Technical Whitepaper — lmax-exchange.github.io/disruptor/
• Version Context: Memory reclamation algorithms reflect GCC 13+ / Clang 17+ atomics, Folly Hazard Pointers (folly::HazardPointer), and Crossbeam Epochs (Rust 1.75+).