Building a Lock-Free Stack in C for High-Performance Concurrency

Concurrent programming shapes much of today's software, from trading engines in Sydney's financial district to the backend services powering Melbourne-based startups. When threads must exchange data without blocking each other, lock-free structures offer an alternative to mutexes that scales gracefully under heavy contention. A lock-free stack is often the first data structure developers build when learning this discipline, because the interface is small yet the implementation exposes many subtle issues that haunt real concurrent code.

This article walks through building such a stack in C using the C11 atomic primitives defined in <stdatomic.h>. We will examine the push and pop operations, discuss the ABA problem and its mitigations, and review memory ordering considerations that separate correct from subtly broken code. By the end, you should have a working mental model and a small tested implementation you can adapt for production work or competitive programming.

The Core Idea Behind Lock-Free Stacks

A lock-free stack rests on a single atomic primitive: compare-and-swap, usually abbreviated CAS. It reads a memory location, compares it against an expected value, and writes a new one only if the comparison matches, all atomically. Threads race to update the head pointer, and only the winner of each race sees its update take effect. Losers simply retry with refreshed state.

The push operation tries to install a new node on top of the stack by setting its next pointer to the current head, then atomically updating the head to point at the new node. Pop reverses the process: capture the current head, read its next, then CAS the head to next. If any other thread modified the head in between, the CAS fails and the operation retries. The algorithm is lock-free because at every step, some thread makes progress, even when others spin uselessly.

Lock-free programming trades complexity for raw scalability. On a server in a Brisbane data centre handling thousands of requests per second, a mutex-protected stack can quickly become a bottleneck as threads queue for the lock. A lock-free version lets threads make progress in parallel with minimal coordination overhead. The trade-off is that the code is harder to reason about and harbours subtle bugs that appear only under specific interleavings on multi-core CPUs.

C11 Atomics and Memory Ordering

The C11 standard introduced portable atomic operations through <stdatomic.h>. The relevant type for our stack is _Atomic(struct node *). The CAS primitive lives in atomic_compare_exchange_weak, which returns whether the swap succeeded and updates the expected value on failure. The weak variant paired with a retry loop can be cheaper than the strong variant on architectures such as ARM, where spurious failures are common.

Memory ordering is where many developers stumble. The default memory_order_seq_cst is the safest but slowest. For our stack, memory_order_relaxed is fine when reading a node's next pointer after it has been published, while memory_order_acquire and memory_order_release are needed to ensure that the data inside a node is visible to whichever thread successfully pops it. Wrong ordering can introduce bugs that pass casual testing but fail unpredictably in production, particularly on weak-memory-model CPUs used in modern devices from Sydney to Perth.

Release stores synchronise with acquire loads. When a thread performs a release CAS on the head, any thread that performs an acquire CAS observing that head is guaranteed to see all the writes that happened before the release. This establishes the happens-before relation that makes the algorithm correct.

Avoiding the ABA Problem

The ABA problem is the classic trap of lock-free pointer manipulation. Imagine thread A reads the head as X, gets preempted, and during that delay thread B pops X, frees it, pushes several new nodes, and one of them lands at a recycled address that happens to equal X. When thread A resumes and does CAS against X, the comparison succeeds even though the structure has changed. The pointer value matches; the reality does not.

For a stack, ABA typically corrupts the linked list rather than crashing outright, which makes it especially insidious. Mitigations include tagged pointers, hazard pointers, or reference counting. For educational implementations on 64-bit systems where aligned pointers leave a few low-order bits free, tagged pointers are often the simplest approach.

If tagged pointers are infeasible, a deferral scheme such as hazard pointers ensures that no thread frees a node while others might still hold a reference. Epoch-based reclamation is a coarser alternative that works well when threads access the stack frequently and rarely sit idle.

A Minimal Implementation

Below is a compact example showing the structure of a C11 lock-free stack. It is deliberately simplified; real-world versions add alignment guarantees and a dedicated reclamation scheme. Note the use of acquire and release memory orders on the CAS operations, which establish the required synchronisation.

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

typedef struct node {
    void *data;
    struct node *next;
} node_t;

typedef struct {
    _Atomic(node_t *) head;
} lf_stack_t;

void lf_stack_push(lf_stack_t *s, void *data) {
    node_t *n = malloc(sizeof(node_t));
    n->data = data;
    node_t *old = atomic_load(&s->head);
    do {
        atomic_store_explicit(&n->next, old, memory_order_relaxed);
    } while (!atomic_compare_exchange_weak_explicit(
        &s->head, &old, n,
        memory_order_release, memory_order_relaxed));
}

void *lf_stack_pop(lf_stack_t *s) {
    node_t *old = atomic_load_explicit(&s->head, memory_order_acquire);
    node_t *next;
    do {
        if (!old) return NULL;
        next = atomic_load_explicit(&old->next, memory_order_relaxed);
    } while (!atomic_compare_exchange_weak_explicit(
        &s->head, &old, next,
        memory_order_acquire, memory_order_relaxed));
    void *data = old->data;
    free(old);
    return data;
}

The free call inside pop is technically unsafe under contention because of the ABA and use-after-free risks discussed above, so in practice you would plug in a hazard-pointer or tagged-pointer scheme at that exact line.

Testing and Real-World Use

Lock-free code demands rigorous testing. ThreadSanitizer catches data races at runtime, and stress tests on machines with at least as many cores as your worst-case deployment expose interleaving bugs. A typical test spins up many threads pushing and popping concurrently, counts the elements pushed and popped, and verifies they balance. Running this on an M-series MacBook or on a Linux box in a Canberra research lab often reveals issues that simpler rigs miss.

In production, lock-free stacks appear in scheduler run queues, in-memory caches, and the internals of memory allocators. Australian fintech firms processing transactions across AEST trading hours rely on such structures to feed order books with minimal latency. Atlassian and Canva, both headquartered locally, build scalable services that include custom concurrent data structures in their hot paths. The principles here scale from interview-level problems such as the "Design a Stack With Increment Operation" challenge to genuine engineering workloads.

The regulatory angle matters too. The Privacy Act 1988 and the Australian Privacy Principles require reasonable security and accuracy of personal information, which means concurrent data structures must preserve invariants even under crash scenarios. A lock-free stack that loses data on failure could create exposure under the Notifiable Data Breaches scheme, which is reason enough to test the implementation as carefully as any business logic.

Common Pitfalls and Best Practices

When working on lock-free stacks, several mistakes tend to recur. Keeping the following points in mind can save hours of debugging.

• Use _Atomic for the head pointer and pass it by address to the atomic functions.
• Pair every release store on the producer side with an acquire load on the consumer side.
• Avoid freeing nodes immediately inside pop without a deferred reclamation scheme.
• Prefer tagged pointers to defend against ABA on 64-bit platforms with spare low-order bits.
• Validate the stack under contention with ThreadSanitizer before shipping.
• Account for memory budget; each node carries a pointer-sized next plus a payload, which adds up quickly at scale.
• Document every memory ordering choice so reviewers understand the intended invariants.

For deeper exploration of pointer manipulation in C, the walkthrough of red-black tree insertion in C shows how non-recursive rotation logic complements what we have covered here. Readers looking for broader context can explore the hello ML site for tutorials on Python, machine learning, and algorithm design, and the data structures section for related patterns such as queues and linked lists.