Article Community improvements enabled

Build a Single-Producer, Single-Consumer Ring Buffer in C11

Daniel McCarthy published 1 week ago 5 min read 92 views
New post
Daniel McCarthy remains the original author. Improvements are attributed to their editors and reviewed by the original author before publication.

A producer can have the next event ready while a consumer is still reading a previous one. A bounded ring lets the two threads pass fixed-size events through a shared array. Each slot changes hands twice. The producer publishes a value, then the consumer releases the slot for reuse.

This C11 example has one producer, one consumer, and eight slots. It transfers unsigned integers in FIFO order. Each operation makes one attempt and returns a Boolean result so the caller can decide when to retry.

Give each index one writer

The producer owns head, the index of the next slot to write. The consumer owns tail, the index of the next slot to read. Both indices start at zero, and each thread can read the other thread's index. Wrapping uses a bit mask because the number of slots is a power of two.

Condition Meaning for this operation
head == tail The consumer sees no ready item
advance(head) == tail The producer sees no available slot
Otherwise The operation can use its current slot

One slot remains unused so these two states have different index arrangements. With eight physical slots the usable capacity is seven items. An operation can see an older position while the other side is moving and return false. The caller can try again. Linux documents a comparable one-slot reservation for circular buffers, using its own synchronization primitives. Linux kernel circular buffers

Order both handoffs

On a successful push, the producer writes the payload first and then stores the advanced head with release ordering. When the consumer's acquire load observes that publication, the earlier payload write is ordered before its read. The consumer then copies the value out and stores the advanced tail with release ordering. When the producer's acquire load observes that retirement, the completed read is ordered before any reuse of the slot. Those two directions let the array elements be ordinary uint32_t values. WG14 C11 draft, §§5.1.2.4 and 7.17.3

Atomic index Release store follows Acquire load precedes
head Producer writes the slot Consumer reads a published slot
tail Consumer finishes reading the slot Producer reuses a freed slot

Each thread loads the index it alone writes with relaxed ordering. It uses the other index to decide whether it may touch the shared payload. Initialize both atomic objects before starting the threads. WG14 C11 draft, §7.17.2.2

For example, the first push writes slot 0 and publishes head = 1. The consumer can acquire that value of head, read slot 0, and publish tail = 1. After the producer wraps, it uses tail to tell which slots it may write again. A push that sees a full ring returns before touching a slot.

Run the example

The queue uses C11 atomics. The executable uses POSIX threads, with the main thread acting as the consumer. Save the code as spsc_ring.c. Build with GCC and a pthread implementation. The commands below are for PowerShell and MinGW-w64 GCC with winpthreads, the environment used to test it.

#include <pthread.h>
#include <sched.h>
#include <stdatomic.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>

enum { RING_SLOTS = 8, EVENTS = 250000 };
_Static_assert(RING_SLOTS > 1 && (RING_SLOTS & (RING_SLOTS - 1)) == 0,
               "Ring size must be a power of two greater than one");

struct Ring {
    atomic_size_t head;
    atomic_size_t tail;
    uint32_t slots[RING_SLOTS];
};

static void ring_init(struct Ring *ring)
{
    atomic_init(&ring->head, 0);
    atomic_init(&ring->tail, 0);
}

static size_t advance(size_t index)
{
    return (index + 1) & (RING_SLOTS - 1);
}

/* Only the producer calls this function. */
static bool ring_push(struct Ring *ring, uint32_t value)
{
    const size_t head = atomic_load_explicit(&ring->head, memory_order_relaxed);
    const size_t next = advance(head);
    if (next == atomic_load_explicit(&ring->tail, memory_order_acquire)) {
        return false;
    }

    ring->slots[head] = value;
    atomic_store_explicit(&ring->head, next, memory_order_release);
    return true;
}

/* Only the consumer calls this function. */
static bool ring_pop(struct Ring *ring, uint32_t *value)
{
    const size_t tail = atomic_load_explicit(&ring->tail, memory_order_relaxed);
    if (tail == atomic_load_explicit(&ring->head, memory_order_acquire)) {
        return false;
    }

    *value = ring->slots[tail];
    atomic_store_explicit(&ring->tail, advance(tail), memory_order_release);
    return true;
}

static void *produce(void *argument)
{
    struct Ring *ring = argument;
    for (uint32_t i = 0; i < EVENTS; ++i) {
        while (!ring_push(ring, i)) {
            sched_yield();
        }
    }
    return NULL;
}

int main(void)
{
    struct Ring ring;
    ring_init(&ring);

    pthread_t producer;
    if (pthread_create(&producer, NULL, produce, &ring) != 0) {
        fputs("Could not create the producer thread.\n", stderr);
        return 1;
    }

    bool ordered = true;
    for (uint32_t i = 0; i < EVENTS; ++i) {
        uint32_t value;
        while (!ring_pop(&ring, &value)) {
            sched_yield();
        }
        if (value != i) {
            ordered = false;
        }
    }
    if (pthread_join(producer, NULL) != 0 || !ordered) {
        fputs("Ring check failed.\n", stderr);
        return 1;
    }

    printf("Received %d events in order.\n", EVENTS);
    return 0;
}
gcc -std=c11 -O2 -pthread -Wall -Wextra spsc_ring.c -o spsc_ring.exe
.\spsc_ring.exe
Received 250000 events in order.

The test checks every item against its expected sequence number. It passed at -O0 and -O2. Separate checks filled the ring to seven items, verified that the next push failed, freed a slot, and confirmed that wraparound preserved FIFO order.

The demo retries with sched_yield() to keep the example small. The queue operations themselves leave the retry, wait, or drop decision to the caller. This design requires a single writer on each side. C11 also allows implementations whose atomic types use locks. If progress guarantees matter, check both index objects with atomic_is_lock_free on the target. WG14 C11 draft, §7.17.5

A kernel keyboard buffer is a related example of passing input from the code that receives it to the code that consumes it. My kernel course builds a keyboard driver and includes a lesson on retrieving a key from the keyboard buffer in user space. Developing a Multithreaded Kernel From Scratch

Discussion 0

No comments yet. Start a thoughtful discussion.

Join the discussion

You need an account to contribute.

Sign in