Lock-Free Circular Buffer: SPSC Implementation

1. The Need for High-Performance Queues

In embedded systems, it's extremely common to pass data between different execution contexts. For example:

• An Interrupt Service Routine (ISR) produces data that a main loop task consumes.
• A high-priority data acquisition thread produces samples for a lower-priority processing thread.

A simple queue protected by a mutex might seem like an obvious solution, but in performance-critical or real-time systems, locks introduce significant problems:

• Latency: Acquiring and releasing locks takes time.
• Priority Inversion: A high-priority task can be blocked by a lower-priority task holding a lock, leading to missed deadlines.
• Deadlocks: A risk in any system with multiple locks.

A lock-free data structure avoids these issues, making it an ideal choice for high-throughput, low-latency communication.

2. The Single-Producer, Single-Consumer (SPSC) Design

The reason we can create a lock-free circular buffer efficiently is by constraining the problem to a single producer and a single consumer. This allows for a simple but powerful design:

• The producer is the only thread that can add items to the buffer and modify the head index.
• The consumer is the only thread that can remove items and modify the tail index.

Since the head and tail indices are each owned by a single thread, we don't need locks to protect them from simultaneous modification. The challenge then becomes how to coordinate between the two threads so they can safely read the other's index.

3. A Simple (But Flawed) Approach

A common way to implement a circular buffer is to use the indices to determine if the buffer is full or empty. This is often called the "wasted slot" method.

Based on this, our C struct would look like this:

typedef struct {
    size_t head;
    size_t tail;
    size_t capacity; // Must be size of buffer + 1
    uint8_t *buffer;
} circular_buffer_t;

And the logic would be:

• Empty: head == tail
• Full: (head + 1) % capacity == tail

This seems correct, but it hides a subtle and dangerous flaw related to how modern CPUs and compilers optimize code.

4. The Real Challenge: Memory Ordering

The simple C implementation assumes that when the producer writes data and then updates head, the consumer will see these events in the same order. This assumption is not guaranteed!

Both compilers and CPUs are free to reorder memory operations to improve performance, as long as the single-threaded behavior remains correct. In a multi-threaded context, this can lead to disaster.

Consider the producer's actions:

1. buffer[head] = data; // Write the data
2. head = new_head; // Update the index

A weakly-ordered CPU (like ARM, common in embedded) might make the change to head visible to the consumer before the data is visible in memory. The consumer would then read the new head value and retrieve stale or uninitialized data.

To prevent this, we must enforce a specific memory ordering. This is where lock-free programming gets serious.

The core principle is:

• Producer: When writing, we use release semantics. This ensures all memory writes made before the head index is updated are completed and visible to other cores.
• Consumer: When reading, we use acquire semantics. This ensures that after we read the updated head index, we are guaranteed to see the data that was written before it.

This release-acquire pairing creates a synchronization point without using locks.

5. From Theory to a Robust Implementation

Watching an expert walk through the process of building a lock-free queue, starting from a flawed design and incrementally fixing it, is an excellent way to solidify these concepts.

This CppCon talk does exactly that. Although the code is in C++, the concepts of atomics and memory ordering are directly translatable to modern C (stdatomic.h) or compiler built-ins.

6. A Correct C11 Implementation

Now, let's synthesize everything into a correct, lock-free SPSC circular buffer implementation using the C11 stdatomic.h header. This is the modern, portable way to write such code in C.

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

// A struct where head and tail are on different cache lines to prevent false sharing.
// We align to a conservative 128 bytes, as cache line sizes can be 64 or 128.
typedef struct {
    // Producer-modified part
    alignas(128) atomic_size_t head;
    
    // Consumer-modified part
    alignas(128) atomic_size_t tail;

    // Shared read-only data
    const size_t capacity;
    int* const data;
} circular_buffer_t;

// Note: For this to work, capacity must be a power of 2.
// This allows us to use bitwise AND for wraparound instead of the expensive modulo operator.



#define CB_CAPACITY 1024

// Initialize the circular buffer
circular_buffer_t* cb_init() {
    // The actual buffer has one more slot than the usable capacity
    int* buffer = malloc(sizeof(int) * CB_CAPACITY);
    if (!buffer) return NULL;

    circular_buffer_t* cb = aligned_alloc(128, sizeof(circular_buffer_t));
    if (!cb) {
        free(buffer);
        return NULL;
    }

    // Use placement new-like logic to initialize const members
    *(size_t*)&cb->capacity = CB_CAPACITY;
    *(int**)&cb->data = buffer;

    atomic_init(&cb->head, 0);
    atomic_init(&cb->tail, 0);

    return cb;
}

void cb_free(circular_buffer_t* cb) {
    if (!cb) return;
    free(cb->data);
    free(cb);
}

bool cb_push(circular_buffer_t* cb, int item) {
    const size_t head = atomic_load_explicit(&cb->head, memory_order_relaxed);
    
    // We load tail with acquire semantics to ensure we are seeing the latest value 
    // from the consumer thread.
    const size_t tail = atomic_load_explicit(&cb->tail, memory_order_acquire);

    if (((head + 1) & (cb->capacity - 1)) == tail) {
        // The buffer is full
        return false;
    }

    cb->data[head] = item;

    // We store the new head position with release semantics. This ensures that the
    // write to cb->data is visible to the consumer *before* it sees the new head value.
    atomic_store_explicit(&cb->head, (head + 1) & (cb->capacity - 1), memory_order_release);

    return true;
}

bool cb_pop(circular_buffer_t* cb, int* item) {
    const size_t tail = atomic_load_explicit(&cb->tail, memory_order_relaxed);
    
    // We load head with acquire semantics to see the latest write from the producer.
    const size_t head = atomic_load_explicit(&cb->head, memory_order_acquire);

    if (head == tail) {
        // The buffer is empty
        return false;
    }

    *item = cb->data[tail];

    // We store the new tail position with release semantics. This makes the newly freed
    // slot available to the producer.
    atomic_store_explicit(&cb->tail, (tail + 1) & (cb->capacity - 1), memory_order_release);

    return true;
}

Code Walkthrough:

1. Atomic Indices: head and tail are declared as atomic_size_t. This ensures that reads and writes to them are indivisible operations.
2. Memory Order in cb_push:
   • We can load head with memory_order_relaxed because only this thread writes to it.
   • We must load tail with memory_order_acquire to get the latest value from the consumer.
   • We must store the new head with memory_order_release to make our data write visible to the consumer.
3. Memory Order in cb_pop:
   • We load tail with memory_order_relaxed as only this thread writes to it.
   • We must load head with memory_order_acquire to see if the producer has added new data.
   • We store the new tail with memory_order_release to signal to the producer that a slot has been freed.
4. False Sharing (Advanced Topic): Notice the alignas(128). As mentioned in the CppCon talk, if head and tail reside on the same CPU cache line, a write to head by the producer will invalidate that cache line for the consumer, forcing a slow fetch from main memory, even though the consumer only needed to read head. By aligning them to separate cache lines, we prevent this performance issue known as false sharing. Bringing this up in an interview demonstrates a deep understanding of hardware-software interaction.

Conclusion

You have now built a correct, high-performance, lock-free SPSC circular buffer. This is a non-trivial task that showcases a sophisticated understanding of C programming, concurrency, and computer architecture.

Key Takeaways:

• Lock-free data structures are essential for high-performance, low-latency communication in embedded systems.
• The SPSC model is the simplest to implement lock-free because head and tail indices are "owned" by separate threads.
• The "wasted slot" method ((head + 1) % capacity == tail) is a simple way to detect a full buffer without a shared flag.
• Correctness depends critically on enforcing memory ordering using acquire/release semantics to prevent compiler and CPU reordering bugs.
• In C11 and later, stdatomic.h provides the standard tools (atomic_load_explicit, atomic_store_explicit, memory orders) to build these structures portably.
• False sharing is a key performance consideration, solved by aligning shared variables to cache line boundaries.

Preview of the Next Lesson:

We will continue our exploration of advanced data structures by shifting from arrays to pointers. In the next lesson, you will implement an intrusive linked list modeled after the Linux kernel's list_head and container_of pattern. This is another powerful, memory-efficient technique used extensively in low-level system software.