Common Embedded Patterns: Ring Buffer

This is the first part of a new series where I'll re-explore common embedded patterns, starting with the ring buffer. It's one of those patterns used in serial communication to make sure no frame of data is lost, and it's also a building block for other patterns we'll cover later.

The complete, tested source lives in the companion repo: ileanmjr88/tetzontli. Each pattern in this series is its own module with a full GoogleTest suite, so you can clone it and run the tests yourself.

Basic Concept

The ring buffer uses two indices, head and tail. To add data we put a byte at head and increment head by one. To remove data we get a byte from tail and increment tail by one. Both indices only move forward, the tail chases the head around the buffer.

This pattern can be implemented with a linked list or a fixed-length array. A linked list might be tempting, but on an embedded system you don't want dynamic allocation. On a modern computer with gigabytes of memory, calling malloc is a non-issue. On a microcontroller you have kilobytes, and three bigger problems: the heap fragments over a device that runs for months, allocation timing is non-deterministic, and you often need to add data from inside an interrupt where you can't afford either. A fixed array sidesteps all of it, the space is guaranteed at compile time.

That guaranteed space is what buys the consumer time: bytes arriving faster than you can process them sit safely in the buffer until you get to them, instead of being lost.

Wrapping around the array

An array does not loop. When you reach the end and try to go past it, it doesn't wrap around. You run beyond the allocated space, which can cause a segmentation fault, return a NULL pointer, or hand you garbage data.

Intuition

The intuitive way to loop back around is the modulo operator %, which returns the remainder after division.

Array of length/capacity: 10

Formula: index % capacity -> array index

- index 0: 0 % 10 = 0
- index 1: 1 % 10 = 1
- index 4: 4 % 10 = 4
- index 10: 10 % 10 = 0
- index 11: 11 % 10 = 1

Modulo lets us treat the fixed array as a ring, which makes it a great fit for a ring buffer. It works fine on a modern computer with multiple cores, high clock speeds, and a hardware divide unit. But modulo has a drawback. It requires division, and many microcontrollers have no hardware divide. The compiler emulates it in software, which is slow, and we pay that cost on every byte we move through the buffer.

Optimizing with a bitmask

There's a faster way to do exactly what the modulo operator does, with one restriction: the array length must be a power of two. That restriction is the key that lets us recreate modulo with a single bitwise operation. The formula is index = head & mask, where mask = capacity - 1. Let's walk through the math.

Array of length/capacity: 8 (power of two)

mask = 8 - 1 = 7 = 0b0111

- index 0: 0b0000 & 0b0111 = 0
- index 1: 0b0001 & 0b0111 = 1
- index 2: 0b0010 & 0b0111 = 2
- index 8: 0b1000 & 0b0111 = 0
- index 10: 0b1010 & 0b0111 = 2
- index 14: 0b1110 & 0b0111 = 6

Notice these are the same answers modulo would give: 8 % 8 = 0, 10 % 8 = 2, 14 % 8 = 6. That's not a coincidence. The mask 0b0111 keeps only the lowest three bits and clears everything above, and the lowest three bits of any number are exactly that number modulo 8. Keeping the low bits is taking the remainder. Because the capacity is a power of two, capacity - 1 is a clean run of ones, which is what makes the AND line up perfectly with modulo. Try this with a non power of two and it falls apart: 11 & 9 = 9, but 11 % 10 = 1.

Implementation

Ring buffer structure

We create a struct to keep all the data types together. This makes life easy, because with a single pointer to the data structure we can access: buffer, capacity, mask, head, and tail. It also makes the data easy to pass by pointer for any function that needs to add and read from it.

// modules/ring_buffer/ring_buffer.h
typedef struct {
  uint8_t *buffer;
  size_t capacity;
  size_t mask;
  volatile size_t head;
  volatile size_t tail;
} ring_buffer_t;

As you can see the struct uses a few different types, and each one is deliberate.

• uint8_t: the buffer stores raw bytes. Whatever the source is, serial data from UART, I2C, or anything else, it arrives as octets, so a byte array is the natural storage for the queue.
• size_t: capacity, mask, head, and tail are all size_t. It's an unsigned type sized to the platform (usually an alias for unsigned int or unsigned long), which keeps the index math portable across compilers and avoids signed-overflow issues. The unsignedness matters later, when we rely on head - tail wrapping cleanly.
• volatile: head and tail are marked volatile so the compiler always reads them from memory instead of caching a stale copy in a register. The producer and consumer can run in different execution contexts (for example, an ISR filling the buffer while the main loop drains it), so a value cached in a register could miss the other side's update. Note that volatile only guarantees the read happens, it does not make the access atomic or thread-safe. We'll cover why this design is safe anyway in the section on interrupts.

Initialization and power of two functions

Let's start with init and its helper is_power_of_two. The init function sets up the data structure, and the power-of-two check is the first gate: if the caller asks for a capacity that isn't a power of two, we refuse, because the whole masking scheme depends on it. We'll start with the helper.

// modules/ring_buffer/ring_buffer.c
static bool is_power_of_two(size_t x) {
  return x != 0u && (x & (x - 1u)) == 0u;
}

This implementation does the following:

• x != 0u: checks if x is not 0.
• (x & (x - 1u)) == 0u: this is the part that checks for a single set bit. A power of two has exactly one bit set. Subtracting one flips that bit off and turns every bit below it on, so x and x - 1 share no bits and the AND comes out zero. Take x = 8: 8 - 1 = 7, and 0b1000 & 0b0111 = 0. Now take a number that isn't a power of two, x = 12: 12 - 1 = 11, and 0b1100 & 0b1011 = 0b1000, which is not zero. The leftover bit is the tell that x had more than one bit set. If both conditions are true then x is a power of two, so the function returns true if and only if x is a power of two. Now let's turn to the ring_buffer_init function.

// modules/ring_buffer/ring_buffer.c
bool ring_buffer_init(ring_buffer_t *rb, uint8_t *storage, size_t capacity) {
  if (rb == NULL || storage == NULL || !is_power_of_two(capacity)) {
    return false;
  }

  rb->buffer = storage;
  rb->capacity = capacity;
  rb->mask = capacity - 1u;
  rb->head = 0u;
  rb->tail = 0u;
  return true;
}

init validates its inputs first: a null struct pointer, null storage, or a capacity that isn't a power of two all cause it to bail out and return false. Once the checks pass, it wires up the struct, precomputes mask = capacity - 1 so put and get never have to recompute it, and zeroes both indices.

Notice init doesn't allocate anything. The caller hands us the storage array, so the buffer can live in static or stack memory. This is the no-malloc principle from earlier, made concrete: there's no malloc in sight, and the space was guaranteed the moment the caller declared the array.

Put and get functions

These functions put and get a single byte at a time. We scope them to one byte because sometimes a single byte is all we need, and because the next section's write and read functions are built on top of them. Let's start with ring_buffer_put:

// modules/ring_buffer/ring_buffer.c
bool ring_buffer_put(ring_buffer_t *rb, uint8_t byte) {
  if (rb == NULL || ring_buffer_is_full(rb)) {
    return false;
  }
  rb->buffer[rb->head & rb->mask] = byte;
  rb->head++;
  return true;
}

The function starts by validating that rb isn't NULL, then calls the helper ring_buffer_is_full. If the buffer is full we exit early and return false, telling the caller no byte was stored. We'll see how is_full works in the next section. If there's room, we do the actual write, and this is where the previous section pays off: rb->head & rb->mask computes the array index using the bitwise AND, wrapping the free-running head back into a valid slot. We write the byte there, then increment head by one so the next put lands in the following slot. Notice the order: we write the slot first, then advance head. That ordering matters for interrupt safety, which we'll get to later. Now let's take a look at ring_buffer_get:

// modules/ring_buffer/ring_buffer.c
bool ring_buffer_get(ring_buffer_t *rb, uint8_t *out) {
  if (rb == NULL || out == NULL || ring_buffer_is_empty(rb)) {
    return false;
  }
  *out = rb->buffer[rb->tail & rb->mask];
  rb->tail++;
  return true;
}

The function also starts by validating that rb isn't NULL, then checks that out isn't NULL. This is the pointer where the byte we read gets stored, which is how get hands data back to the caller while keeping its bool return free to report success or failure. Finally it calls the helper ring_buffer_is_empty. If the buffer is empty we exit early and return false, telling the caller no byte was read. We'll see how is_empty works in the next section. If it's not empty, we do the read, and again the previous section pays off: rb->tail & rb->mask computes the array index with the bitwise AND, wrapping the free-running tail into a valid slot. We read the byte, then increment tail by one. Notice get never erases anything. It reads the byte and moves tail forward, and that slot counts as free again the moment tail passes it. The indices alone decide what's data and what's free space.

Is empty, is full, and count

These three helpers, is_empty, is_full, and count, are what put and get lean on to decide whether they can proceed. This is where the free-running indices finally earn their keep. Let's start with ring_buffer_is_empty:

// modules/ring_buffer/ring_buffer.c
bool ring_buffer_is_empty(const ring_buffer_t *rb) {
  return rb->head == rb->tail;
}

The buffer is empty when head and tail hold the same value. That makes sense: tail chases head, and when it catches all the way up there's nothing left to read. Here's the subtle part. In a lot of ring buffer designs the indices get wrapped back into range, and then head == tail is ambiguous, it means both completely empty and completely full, and you can't tell which. Because our indices run free and never wrap, head == tail can only ever mean empty. We'll see in a moment how full is handled without that ambiguity.

Next, ring_buffer_count, which is the heart of it:

// modules/ring_buffer/ring_buffer.c
size_t ring_buffer_count(const ring_buffer_t *rb) {
  return rb->head - rb->tail;
}

Both indices only ever increase. Every put bumps head, every get bumps tail, and neither wraps. So head is always ahead of tail by exactly the number of bytes that have been written but not yet read, which is the fill level. The difference head - tail is the count.

The nice part is what happens when head eventually overflows. size_t has a maximum, and after enough bytes head wraps past it back toward zero. You might expect head - tail to break at that point, but it doesn't. Unsigned subtraction wraps the same way unsigned addition does, so the difference stays correct even across the overflow. This is exactly why head and tail are unsigned, and it's why the buffer can run indefinitely without any special handling for the wraparound.

Finally, ring_buffer_is_full:

// modules/ring_buffer/ring_buffer.c
bool ring_buffer_is_full(const ring_buffer_t *rb) {
  return ring_buffer_count(rb) == rb->capacity;
}

Once we have count, full is trivial: the buffer is full when it holds capacity bytes. No wasted slot, no separate counter to keep in sync, no ambiguity with the empty case. The free-running indices give us empty (head == tail), full (count == capacity), and everything in between, all from two numbers that only count upward.

Write and read functions

These functions write and read more than a single byte of data at a time. Let's start with ring_buffer_write:

// modules/ring_buffer/ring_buffer.c
size_t ring_buffer_write(ring_buffer_t *rb, const uint8_t *data, size_t len) {
  if (rb == NULL || data == NULL) {
    return 0u;
  }
  size_t written = 0u;
  while (written < len && ring_buffer_put(rb, data[written])) {
    written++;
  }
  return written;
}

This function returns the number of bytes actually written, which may be fewer than requested. It returns 0 on the early exit when either the ring buffer rb or the source pointer data is NULL. Otherwise we initialize written to track how many bytes we've copied from data into the buffer. The loop runs on two conditions joined by &&: written < len keeps us from reading past the end of the input, and ring_buffer_put returns false the moment the buffer is full. As long as both hold, we keep copying bytes and incrementing written. The loop stops as soon as either one fails, whether we ran out of input or ran out of room. The count we return tells the caller exactly how much made it in: all of it, part of it, or zero if the buffer was already full.

Next, ring_buffer_read:

// modules/ring_buffer/ring_buffer.c
size_t ring_buffer_read(ring_buffer_t *rb, uint8_t *out, size_t len) {
  if (rb == NULL || out == NULL) {
    return 0u;
  }
  size_t count = 0u;
  while (count < len && ring_buffer_get(rb, &out[count])) {
    count++;
  }
  return count;
}

This function also returns the number of bytes actually read, which may be fewer than requested. It returns 0 on the early exit when either the ring buffer rb or the destination pointer out is NULL. Otherwise we initialize count to track how many bytes we've read from the buffer into out. The loop runs on two conditions joined by &&: count < len keeps us from writing past the end of the output, and ring_buffer_get returns false the moment the buffer is empty. As long as both hold, we keep reading bytes and incrementing count. The loop stops as soon as either one fails, whether the caller's buffer is full or the ring buffer ran dry. The count we return tells the caller exactly how many bytes they got.

Safety with the Interrupt Service Routine (ISR)

For those new to embedded, it might not be obvious why this design is considered safe, or what its typical applications are. The primary use for a ring buffer, as we mentioned earlier, is serial communication. Take the example of two microcontrollers talking to each other, each running its own firmware tailored to its own task. We don't know when either one will need to send data, so to make sure we don't miss a single byte, we set up the data receive (RX) path using the microcontroller's Interrupt Service Routine (ISR). As soon as the start of a transmission arrives, the ISR takes over and captures each byte.

This is the producer side of the buffer. The ISR calls put for every byte it receives. Somewhere else, the main loop is the consumer, calling get when it gets around to processing what came in. The two run in different execution contexts, and here's the catch: the ISR can fire at any moment, between any two instructions the main loop is running. So the fair question is, if the interrupt lands in the middle of a get, can the two step on each other and corrupt the buffer?

The answer is no, and the reason is that each index has exactly one writer. put is the only function that writes head, and it only ever runs in the ISR. get is the only function that writes tail, and it only ever runs in the main loop. Neither side writes the other's index. The producer reads tail to check whether the buffer is full, and the consumer reads head to check whether it's empty, but reading is safe. Since no index has two writers racing to change it, there's nothing to corrupt, and we don't need to disable interrupts or reach for a lock. This is what people mean by single-producer, single-consumer, or SPSC.

That single-writer rule is also the boundary. The moment you have two things calling put, or two things calling get, the guarantee is gone and you need real synchronization. This buffer is safe for exactly one producer and one consumer, no more.

One more detail makes it work, and it's the ordering we flagged back in put:

rb->buffer[rb->head & rb->mask] = byte; // 1. write the data
rb->head++; // 2. then publish it

We write the byte into the slot first, then increment head. That order is not an accident. head is the signal that tells the consumer a new byte is available. If we bumped head first and the interrupt timing worked out badly, the consumer could see the new head, go read that slot, and pull out a byte we hadn't actually written yet. By writing the slot before advancing head, we guarantee that the instant the consumer can see the byte, the byte is really there. The index update publishes the data, so it comes last. get mirrors this: we read the byte out first, then advance tail, so we never mark a slot free before we've taken its contents.

A couple of honest caveats for the readers who want them. First, volatile gets us visibility, not atomicity. This design assumes reading or writing head and tail happens in a single, uninterruptible machine operation, which is true when they're word-sized on the target. On an 8-bit MCU where size_t spans multiple bytes, an index update could be split across instructions and torn by an interrupt, and you'd need to account for that. Second, on a single-core microcontroller with an ISR, volatile plus the write-then-publish ordering is enough. On a multi-core system with weak memory ordering you'd reach for atomics with explicit acquire and release semantics to guarantee the slot write is seen before the index write. For the classic ISR-and-main-loop case this buffer is built for, we're on solid ground.

Wrap-up

That's a complete, working ring buffer in a couple hundred lines of C. It does no dynamic allocation, wraps with a single bitwise AND instead of a division, tells full from empty without wasting a slot or keeping a separate counter, and it's safe to fill from an interrupt while draining it from the main loop. For a structure this small, there's a surprising amount of nuance packed in.

It's worth being honest about what this design does not do, because every one of these is a deliberate trade, not an oversight:

• Capacity must be a power of two. This is the price of replacing modulo with a mask. If you need to hold exactly 100 bytes you round up to 128 and waste a little space. On an embedded system that's almost always a trade worth making.
• Single producer, single consumer only. One writer per index is what makes it lock-free. Two ISRs writing, or two contexts reading, and you need real synchronization.
• No overwrite-oldest mode. When the buffer is full, put refuses the new byte rather than discarding the oldest one. Some applications want the opposite (keep the newest samples, drop the stale ones). That's a reasonable variant, just not this one.
• Bytes only. This buffer stores uint8_t. Storing wider elements, or arbitrary structs, means generalizing the element size, which changes the index math and the storage. None of these are hard to lift. They're the natural next questions, and a few of them turn into their own patterns later in this series.

Speaking of which, the ring buffer is a foundation, not a destination. It shows up underneath several of the patterns still to come: an event queue is a ring buffer of messages instead of bytes, a moving-average filter is a ring buffer of samples, and the command dispatcher we'll build reads its input straight out of one. Next in the series we'll tackle the memory pool. The ring buffer gave us fixed storage for bytes; the memory pool gives us fixed storage for objects, and it's what lets an event queue hold structs instead of raw data. See you there.