Lock-Free Data Structures in C Using Atomic CAS

A lock-free data structure is a thread-safe data format that allows concurrent access and modification without using traditional mutual exclusion primitives like mutexes. Instead of blocking competing threads, lock-free algorithms guarantee that at least one thread makes system-wide progress in a finite number of steps. This article explains the fundamentals of lock-free architecture, how the hardware-level atomic compare-and-swap (CAS) operation works, and how to implement a practical lock-free stack in the C programming language using the standard <stdatomic.h> library.

What Is a Lock-Free Data Structure?

Traditional concurrent data structures rely on locks to protect shared state. While simple to implement, locks introduce issues such as deadlocks, priority inversion, and significant latency overhead caused by operating system context switches when threads block.

A data structure is considered lock-free if the suspension or failure of any arbitrary thread cannot prevent other threads from making progress. Lock-free systems achieve this by using atomic read-modify-write CPU instructions, allowing threads to execute speculative updates and commit them only if the underlying data has not been modified by another thread in the interim.

The Compare-and-Swap (CAS) Operation

Compare-and-swap is the fundamental atomic building block for most lock-free data structures. It performs an atomic comparison and conditional assignment:

It reads a memory location.
It compares the current value with an expected value.
If the values match, it writes a new value to that memory location and returns success.
If the values do not match, the memory location remains untouched, and the operation returns failure (often updating the expected value with the actual current value).

In C11 and later, the standard library provides this functionality via <stdatomic.h> through functions such as atomic_compare_exchange_weak and atomic_compare_exchange_strong. The weak variant is permitted to fail spuriously on architectures like ARM, making it ideal inside retry loops, while strong guarantees success if the values match.

Implementing a Lock-Free Treiber Stack in C

The classic lock-free data structure is the Treiber stack. It is a singly linked list where additions (push) and removals (pop) are performed exclusively at the top node using CAS operations.

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <stdatomic.h>

typedef struct Node {
    int value;
    struct Node* next;
} Node;

typedef struct {
    _Atomic(Node*) top;
} LockFreeStack;

void init_stack(LockFreeStack* stack) {
    atomic_init(&stack->top, NULL);
}

void push(LockFreeStack* stack, int value) {
    Node* new_node = (Node*)malloc(sizeof(Node));
    new_node->value = value;
    
    // Read the current top pointer
    Node* current_top = atomic_load(&stack->top);
    
    // Loop until the top pointer is successfully updated to new_node
    do {
        new_node->next = current_top;
    } while (!atomic_compare_exchange_weak(&stack->top, &current_top, new_node));
}

bool pop(LockFreeStack* stack, int* result) {
    Node* current_top = atomic_load(&stack->top);
    
    // Loop until we either determine the stack is empty or successfully pop
    while (current_top != NULL) {
        Node* next_node = current_top->next;
        
        if (atomic_compare_exchange_weak(&stack->top, &current_top, next_node)) {
            *result = current_top->value;
            
            // Note: Immediate free() is unsafe in production concurrent code
            // due to the ABA problem and concurrent read races.
            free(current_top); 
            return true;
        }
        // If CAS fails, current_top is automatically updated with the latest stack->top
    }
    
    return false; // Stack is empty
}

How the Implementation Works

In the push routine, a new node is allocated, and its next pointer is set to the current top. The atomic_compare_exchange_weak function evaluates whether stack->top still equals current_top. If no other thread has pushed or popped an item, stack->top is atomically swapped to new_node. If another thread modified the stack in the meantime, the CAS fails, current_top receives the newly updated top value, and the loop retries.

In the pop routine, the thread reads current_top. If non-null, it attempts to atomically replace current_top with current_top->next. If the CAS succeeds, the top node is detached, and the value is returned.

Real-World Considerations: The ABA Problem and Memory Reclamation

While the core mechanics of CAS are straightforward, production lock-free code in C must address two primary challenges:

The ABA Problem: A thread reads value A, gets preempted, and another thread changes A to B and back to A. When the original thread resumes, the CAS succeeds because the value is still A, even though the intermediate changes may have rendered structural pointers invalid. This is typically solved using tagged pointers (coupling a pointer with a monotonic modification counter) or double-word CAS (atomic_compare_exchange_strong on architectures supporting 128-bit atomics).
Safe Memory Reclamation (SMR): In the provided pop example, calling free() immediately can cause a segmentation fault if another concurrent thread reads current_top->next simultaneously. To safely release memory without locks, developers use techniques like Hazard Pointers, Read-Copy-Update (RCU), or Epoch-Based Reclamation (EBR).