</>EmbeddedInterview
← All problems · Data Structures

Lock-Free Ring Buffer (SPSC)

Medium

Implement a byte FIFO for a UART receive path where the ISR is the only producer and the main loop is the only consumer.

  • Capacity is RB_SIZE (a power of two) and all RB_SIZE slots must be usable.
  • rb_put returns false when full; rb_get returns false when empty.
  • rb_count returns the number of stored bytes.
  • No locks and no disabling interrupts.

Write your code on the right and press Run (or Ctrl + Enter). Hidden tests check your functions and print the result below the editor.

Let head and tail count up forever instead of wrapping them at RB_SIZE. Then head - tail (unsigned) is always the fill level, and you index the array with index & (RB_SIZE - 1).

#include <stdio.h>
#include <stdint.h>
#include <stdbool.h>

#define RB_SIZE 8u

typedef struct {
    uint8_t buf[RB_SIZE];
    volatile uint32_t head;
    volatile uint32_t tail;
} ring_t;

#define COMPILER_BARRIER() __asm__ volatile("" ::: "memory")

void rb_init(ring_t *r) { r->head = r->tail = 0; }

uint32_t rb_count(const ring_t *r) { return r->head - r->tail; }

bool rb_put(ring_t *r, uint8_t b)
{
    uint32_t h = r->head;
    if (h - r->tail == RB_SIZE) return false;   /* full */
    r->buf[h & (RB_SIZE - 1u)] = b;
    COMPILER_BARRIER();                         /* data before index */
    r->head = h + 1u;
    return true;
}

bool rb_get(ring_t *r, uint8_t *b)
{
    uint32_t t = r->tail;
    if (r->head == t) return false;             /* empty */
    *b = r->buf[t & (RB_SIZE - 1u)];
    COMPILER_BARRIER();                         /* read data before freeing slot */
    r->tail = t + 1u;
    return true;
}

Each index has exactly one writer, and each update is a single aligned 32-bit store, which is atomic on a 32-bit MCU. The producer stores the byte before publishing the new head, and the consumer reads it before publishing the new tail, so neither side sees a half-finished slot.

Free-running counters solve the classic full-versus-empty ambiguity without wasting a slot, and unsigned subtraction stays correct when the counters wrap past 0xFFFFFFFF (the test checks this).

On a multi-core or out-of-order CPU, replace the compiler barrier with real ordering: C11 atomic_store_explicit(&head, h + 1, memory_order_release) in the producer and an acquire load in the consumer.

solution.c
OutputPress Run to compile and test your code.
Show the hidden tests
/* ---- tests ---- */
static int fails;
#define CHECK(c) do { if (!(c)) { printf("FAIL line %d: %s\n", __LINE__, #c); fails++; } } while (0)
int main(void)
{
    ring_t r; uint8_t b;
    rb_init(&r);
    CHECK(rb_count(&r) == 0 && !rb_get(&r, &b));
    for (unsigned i = 0; i < RB_SIZE; i++) CHECK(rb_put(&r, (uint8_t)i));
    CHECK(!rb_put(&r, 99) && rb_count(&r) == RB_SIZE);
    CHECK(rb_get(&r, &b) && b == 0);
    CHECK(rb_put(&r, 100));
    for (unsigned i = 1; i < RB_SIZE; i++) CHECK(rb_get(&r, &b) && b == i);
    CHECK(rb_get(&r, &b) && b == 100 && rb_count(&r) == 0);
    /* wrap-around of the free-running counters */
    r.head = r.tail = 0xFFFFFFFEu;
    for (unsigned i = 0; i < 5; i++) CHECK(rb_put(&r, (uint8_t)i));
    for (unsigned i = 0; i < 5; i++) CHECK(rb_get(&r, &b) && b == i);
    puts(fails ? "Some tests failed" : "All tests passed");
    return fails != 0;
}