Lock-Free Architecture, Hardware CAS & The ABA Problem

Traditional mutexes block threads via operating system sleep queues, introducing context switching latency (thousands of CPU cycles). In ultra-low-latency networking, audio processing, and high-frequency trading, developers build Lock-Free Data Structures.

A lock-free algorithm guarantees that regardless of thread contention, at least one thread in the system makes forward progress in a finite number of CPU instructions.

Compare-And-SwapLow Latency

CAS

The core hardware instruction (LOCK CMPXCHG) enabling lock-free state transitions without OS mutexes.

1. The Compare-And-Swap (CAS) Primitive#

At the heart of every lock-free data structure is the Compare-And-Swap (CAS) CPU instruction:

\text{Success} & \text{if } *Addr == Old \implies *Addr \gets New \\ \text{Failure} & \text{if } *Addr \ne Old \implies \text{No Change}

In Rust atomics, this is exposed via compare_exchange and compare_exchange_weak:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
use std::sync::atomic::{AtomicU32, Ordering};

fn lock_free_add(atomic_val: &AtomicU32, delta: u32) {
    let mut current = atomic_val.load(Ordering::Relaxed);
    loop {
        let new = current + delta;
        // Attempt atomic transition from 'current' to 'new':
        match atomic_val.compare_exchange_weak(
            current, 
            new, 
            Ordering::AcqRel,  // Memory ordering on success
            Ordering::Relaxed  // Memory ordering on failure
        ) {
            Ok(_) => break, // Successfully updated without locks!
            Err(actual) => current = actual, // Spurious failure or contention: retry!
        }
    }
}

compare_exchange vs compare_exchange_weak

On architectures like ARM and RISC-V (Load-Linked / Store-Conditional), compare_exchange_weak can fail spuriously due to cache line invalidation. In a retry loop, always use compare_exchange_weak for optimal hardware pipeline performance.

2. Lock-Free Stack (Treiber Stack)#

A classic example of lock-free architecture is the Treiber Stack:

Architecture Diagram

Rendering diagram...

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
use std::sync::atomic::{AtomicPtr, Ordering};
use std::ptr;

struct Node<T> {
    data: T,
    next: *mut Node<T>,
}

pub struct LockFreeStack<T> {
    head: AtomicPtr<Node<T>>,
}

impl<T> LockFreeStack<T> {
    pub fn new() -> Self {
        LockFreeStack { head: AtomicPtr::new(ptr::null_mut()) }
    }

    pub fn push(&self, data: T) {
        let new_node = Box::into_raw(Box::new(Node {
            data,
            next: ptr::null_mut(),
        }));

        let mut current_head = self.head.load(Ordering::Relaxed);
        loop {
            unsafe { (*new_node).next = current_head; }
            match self.head.compare_exchange_weak(
                current_head,
                new_node,
                Ordering::Release,
                Ordering::Relaxed,
            ) {
                Ok(_) => break,
                Err(actual) => current_head = actual,
            }
        }
    }
}

3. The Classic ABA Problem#

The ABA Problem is the primary hazard in lock-free memory reclamation:

Architecture Diagram

Rendering diagram...

Mitigating the ABA Problem#

Generational Tagged Pointers: Pair pointer addresses with an integer version counter:

\text{TaggedPointer} = \bigl(\text{Address: usize}, \, \text{VersionTag: usize}\bigr)

Even if the address is reused, the version increments ( $A_1 \ne A_2$ ), causing CAS to fail safely.

Hazard Pointers / Epoch-Based Reclamation: Libraries like crossbeam-epoch delay memory deallocation until all concurrent threads have exited reading critical sections.

4. Concept Verification#

Test your understanding of lock-free architecture:

Concept check

What is the ABA problem in lock-free memory management?

Concept check

Why is compare_exchange_weak preferred over compare_exchange inside retry loops?