Lock-Free Stack with CAS

A First Attempt: The Naive Lock-Free Stack

Let's start by designing the push and pop operations. A stack is a linked list where we only ever modify the head.

• Push: To add a new element, we need to:
  1. Create a new node.
  2. Set the new node's next pointer to the current head of the stack.
  3. Atomically update the head to point to our new node.
• Pop: To remove an element, we need to:
  1. Read the current head node.
  2. Atomically update the head to point to head->next.
  3. Return the old head node's data.

The "atomic update" step is where our CAS loop comes in. We will optimistically prepare our changes and then use CAS to commit them, retrying if another thread modified the stack in the meantime.

The following resource provides a simple C11 implementation that directly translates this logic into code.

The logic seems sound, right? We read the current head, prepare the new head, and use CAS to swap it in. If the CAS fails, orig is updated with the latest value of lfstack, and we loop to try again. It perfectly matches the optimistic concurrency pattern we learned.

However, as the article hints at the end, this implementation contains a severe and classic bug.

The ABA Problem: When "Unchanged" is a Lie

The fundamental assumption of our CAS loop is that if head still contains the value we expected, then nothing has changed. This assumption is false.

Consider this sequence of events with two threads, Thread 1 and Thread 2:

1. Initial State: The stack is C -> B -> A -> NULL. The head points to node C.
2. Thread 1 Reads: Thread 1 wants to pop. It reads head (which is C) into its local orig variable and determines the next value will be B.
3. Context Switch: Before Thread 1 can execute its CAS, it is preempted.
4. Thread 2 Runs: Thread 2 is fast. It runs and executes three operations:
   • It pops C. The stack is now B -> A -> NULL.
   • It pops B. The stack is now A -> NULL.
   • It pushes C back onto the stack. Since memory for nodes is often recycled, it might get the exact same memory address for C that it just freed. The stack is now C -> A -> NULL.
5. Context Switch Back: Thread 1 resumes execution.
6. Thread 1's CAS: Thread 1's atomic_compare_exchange_weak runs. It compares the current head (C) with its expected value (also C). They match! The CAS succeeds.
7. Corruption: Thread 1 now sets the head to what it calculated in step 2: node B. But B is no longer part of the stack; it was popped in step 4. The stack now incorrectly points to B, and node A is lost forever.

This is the ABA problem. The pointer value changed from A to B and then back to A (in our case, C -> B -> C), tricking the CAS into thinking the underlying state was static.

This image provides a great visualization of the problem.

As you can see, simple pointer comparison is not enough. We need to detect not just that the pointer's value is the same, but that it has remained untouched.

Solving the ABA Problem with a Version Counter

The most common solution is to augment the pointer with a version counter or "tag". Instead of just swapping a pointer, we atomically swap a structure containing both the pointer and a counter.

The logic becomes:

1. Read the (pointer, counter) pair.
2. Prepare the new (new_pointer, counter + 1) pair.
3. Use CAS to swap the entire pair.

Now, if another thread modifies the stack, it will increment the counter. Even if it manages to make the pointer value revert to its original state (the 'A' in ABA), the counter will be different. Our CAS will fail, correctly detecting the intermediate modification and forcing a retry.

To atomically compare-and-swap a structure that is twice the size of a pointer (e.g., 16 bytes on a 64-bit system), we need hardware support. On x86-64, this is the cmpxchg16b instruction, often called Double-Word Compare-And-Swap (DWCAS). Modern C11 and C++ compilers will automatically use this instruction when you perform an atomic_compare_exchange on a struct that fits the criteria.

The following resource provides a superb, detailed walkthrough of building a robust lock-free stack in C11 that correctly solves the ABA problem.

The Final Piece: Memory Reclamation

There's one more subtle but critical problem. Look at this line in the pop function from the article: next.node = orig.node->next;.

What happens if, after we load orig but before we execute this line, another thread pops orig.node and frees the memory it points to? Our code would then try to dereference a dangling pointer, leading to a crash or undefined behavior. This is a use-after-free bug.

Lock-free algorithms cannot use malloc() and free() naively during their core operations. Managing memory is one of their greatest challenges. The article you just read (LINK) uses a simple and effective strategy:

• Node Recycling: Instead of freeing a popped node, it's pushed onto a separate internal free stack. The push operation then gets its nodes from this free stack. All nodes are pre-allocated at initialization, and nothing is truly freed until the entire stack is destroyed. This ensures that a pointer to a node is always valid, even if the node has been "popped" and is waiting on the free list.

This is a form of deferred reclamation. For more dynamic data structures where pre-allocation isn't feasible, more complex techniques are needed.

The Complete Lock-Free Stack Implementation

Now, let's put it all together. Here is a complete implementation based on the C11 Lock-free Stack article. It incorporates both the ABA counter and the node recycling strategy for memory safety.

Review this code carefully. Notice how the public-facing lstack_push and lstack_pop orchestrate the movement of nodes between the free stack and the head stack, while the internal push and pop functions contain the core atomic logic.

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

// A node in the linked list
typedef struct lstack_node {
    void *value;
    struct lstack_node *next;
} lstack_node_t;

// The head of a stack (value stack or free stack)
// This struct will be atomically manipulated.
typedef struct lstack_head {
    uintptr_t aba;       // Version counter to prevent the ABA problem
    lstack_node_t *node; // Pointer to the top node
} lstack_head_t;

// The main stack object
typedef struct {
    lstack_node_t *node_buffer;           // Pre-allocated pool of nodes
    _Atomic lstack_head_t head, free;     // The value stack and the free node stack
    _Atomic size_t size;                  // An approximate size of the value stack
} lstack_t;

// Internal function to pop a node from a stack head (either value or free)
static lstack_node_t* internal_pop(_Atomic lstack_head_t *head) {
    lstack_head_t next, orig = atomic_load(head);
    do {
        if (orig.node == NULL) {
            return NULL; // Stack is empty
        }
        // Prepare the new head for the CAS
        next.aba = orig.aba + 1;         // Increment ABA counter
        next.node = orig.node->next;     // New top node is the next one
    } while (!atomic_compare_exchange_weak(head, &orig, next));
    // CAS succeeded, orig.node is the old top node
    return orig.node;
}

// Internal function to push a node onto a stack head
static void internal_push(_Atomic lstack_head_t *head, lstack_node_t *node) {
    lstack_head_t next, orig = atomic_load(head);
    do {
        node->next = orig.node;          // Link our new node to the old head
        // Prepare the new head for the CAS
        next.aba = orig.aba + 1;         // Increment ABA counter
        next.node = node;                // New head is our node
    } while (!atomic_compare_exchange_weak(head, &orig, next));
}

// Public API: Initialize the stack
int lstack_init(lstack_t *s, size_t max_size) {
    lstack_head_t head_init = {0, NULL};
    s->head = ATOMIC_VAR_INIT(head_init);
    atomic_store(&s->size, 0);

    s->node_buffer = malloc(max_size * sizeof(lstack_node_t));
    if (s->node_buffer == NULL) return ENOMEM;

    // Link all pre-allocated nodes into a list
    for (size_t i = 0; i < max_size - 1; i++) {
        s->node_buffer[i].next = &s->node_buffer[i + 1];
    }
    s->node_buffer[max_size - 1].next = NULL;

    // The free stack initially contains all nodes
    lstack_head_t free_init = {0, s->node_buffer};
    s->free = ATOMIC_VAR_INIT(free_init);
    return 0;
}

// Public API: Push a value onto the stack
int lstack_push(lstack_t *s, void *value) {
    // 1. Get a node from the free list
    lstack_node_t *node = internal_pop(&s->free);
    if (node == NULL) return ENOMEM; // No free nodes available

    // 2. Set its value and push it onto the main stack
    node->value = value;
    internal_push(&s->head, node);
    atomic_fetch_add(&s->size, 1);
    return 0;
}

// Public API: Pop a value from the stack
void* lstack_pop(lstack_t *s) {
    // 1. Pop a node from the main stack
    lstack_node_t *node = internal_pop(&s->head);
    if (node == NULL) return NULL; // Stack is empty

    // 2. Extract the value and return the node to the free list
    void *value = node->value;
    atomic_fetch_sub(&s->size, 1);
    internal_push(&s->free, node);
    return value;
}

// Public API: Clean up the stack
void lstack_free(lstack_t *s) {
    free(s->node_buffer);
}

Conclusion

Congratulations! You have now designed and analyzed a complete, correct, and non-trivial lock-free data structure. This is a significant step up from basic mutexes and condition variables.

Key Takeaways:

• A simple lock-free stack can be implemented using a CAS loop on the head pointer.
• This naive implementation is vulnerable to the ABA problem, which can lead to silent data corruption.
• The ABA problem is solved by pairing the pointer with a version counter and using a double-word CAS (DWCAS) to update them together.
• Lock-free algorithms must use a safe memory reclamation strategy to prevent use-after-free bugs. A simple method is to pre-allocate and recycle nodes instead of using free().

Preview of the Next Lesson:
The ABA problem is so fundamental and challenging that it deserves its own dedicated focus. In the next lesson, we will analyze the challenges of the ABA problem in CAS-based algorithms in greater depth, exploring scenarios beyond the simple stack and discussing other mitigation strategies.