Lock-Free Ring Buffer (SPSC)
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 allRB_SIZEslots must be usable. rb_putreturnsfalsewhen full;rb_getreturnsfalsewhen empty.rb_countreturns 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.
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;
}