Ring Buffers and the Cost of Telling Full From Empty

A circular buffer is an array plus two indices that wrap. The array is fixed in size, so the structure never allocates, and both ends move at the same rate on average, so the wrap does not accumulate. The single design question that shapes every variant is how the two indices distinguish a buffer that is full from one that is empty. Both states have the head equal to the tail in the modular arithmetic, and everything else follows from how that ambiguity is resolved.

One slot of sacrifice

The classic resolution is to declare that the buffer holds at most N − 1 elements. With N slots and indices taken modulo N, the buffer is empty when head == tail and full when (head + 1) % N == tail. The extra slot is never written, so the two states are distinguishable without any additional state.

#define N 64                       /* slots; usable capacity 63 */

struct ring {
    unsigned head;                 /* next slot to write */
    unsigned tail;                 /* next slot to read */
    int slot[N];
};

static int ring_full(const struct ring *r)  { return (r->head + 1) % N == r->tail; }
static int ring_empty(const struct ring *r) { return r->head == r->tail; }

static int ring_push(struct ring *r, int v) {
    if (ring_full(r)) return -1;
    r->slot[r->head] = v;
    r->head = (r->head + 1) % N;
    return 0;
}

static int ring_pop(struct ring *r, int *out) {
    if (ring_empty(r)) return -1;
    *out = r->slot[r->tail];
    r->tail = (r->tail + 1) % N;
    return 0;
}

The modulo is the part that costs. A general % on a variable divisor compiles to a multiply-and-shift sequence or a division, both of which are slower than an add. When the divisor is a compile-time constant that is a power of two, the compiler replaces the remainder with & (N - 1), one instruction. That substitution needs both properties: the constant to be known, and the value to be a power of two. A struct with a runtime capacity field does not get it.

The mask form also changes the wrap behaviour. The index is incremented without a reset and the mask discards the high bits, so the index is only ever reduced modulo the capacity; the arithmetic is uniform across the wrap and no comparison against N appears on the update path. A copy of k contiguous slots starting at head is then split into at most two runs, the second of which begins at slot zero, and neither run needs a per-element wrap check.

Monotonic counters and the width of the difference

A different resolution keeps both indices as unbounded counters and lets the difference determine occupancy. Write index w, read index r, both monotonically increasing, and the count is w - r for unsigned arithmetic. Full is w - r == N, empty is w - r == 0, and the slot is w & (N - 1). No slot is sacrificed, and no modulo is needed.

The counters wrap at the width of their type. With 32-bit counters and power-of-two N, the difference w - r is correct modulo 2^32 as long as the buffer never holds more than N elements, which the full check enforces. This is the standard technique for lock-free single-producer single-consumer queues. The producer loads r and compares it against w to test for full; the consumer loads w and compares it against its own r to test for empty. Each side’s own index is the one it stores, and that store is where the ordering matters.

The subtlety is ordering, and it is asymmetric. The producer must write the slot before publishing the new w, so its store of w carries release ordering; the consumer loads w with acquire ordering, and the acquire pairs with the release to make the slot write visible before the consumer reads the slot. Going the other way, the consumer must finish reading a slot before it republishes r, so the consumer’s store of r carries release ordering and the producer’s load of r carries acquire. A queue that orders only one direction has a race in the other: the producer can overwrite a slot the consumer has not finished reading, or the consumer can read a slot the producer has not finished writing. That is why a queue written with plain non-atomic loads and stores is incorrect even when each individual access is atomic, and why the release and acquire must be applied to both indices rather than to the data.

/* Requires C11 <stdatomic.h>. Single producer, single consumer:
   each side owns one index. */
static inline size_t idx_load_acquire(const _Atomic size_t *p) {
    return atomic_load_explicit(p, memory_order_acquire);
}
static inline void idx_store_release(_Atomic size_t *p, size_t v) {
    atomic_store_explicit(p, v, memory_order_release);
}

The single-producer/single-consumer case needs no compare-and-swap because each index has exactly one writer. Adding a second producer breaks that property: two producers must agree on which slot to claim, which requires a fetch-and-add or a CAS loop on the write index. The CAS loop reintroduces the contention the design was avoiding, and a failed CAS means a retry that may spin.

Cache lines and the false sharing boundary

A ring buffer’s two indices are written by different threads and read by each other. If they occupy the same cache line, every write by one invalidates the line in the other’s cache, and the two cores ping-pong the line between them. The cost is not the two writes but the coherence traffic each one triggers.

The usual fix is to place each index in its own cache line, padded to 64 bytes, so that a write to one does not invalidate the other. A second refinement places each index in the same line as the slot that its owner is about to write next, which costs one line per index per buffer position rather than one line per index, but keeps the index update and the data store in the same line and therefore in the same coherence transaction. That is only worth it when the index would otherwise be read from a line the other thread is writing.

The data slots themselves have the same issue at the boundary. When the producer writes slot k and the consumer reads slot k − N + 1, the two are far apart in index but may be adjacent in memory if the buffer is small. A ring of 64 slots of 8 bytes is 512 bytes, eight cache lines, and the producer’s write position and the consumer’s read position are never more than the whole buffer apart. For a buffer of a few lines, producer and consumer are therefore working on the same lines most of the time, and the traffic is unavoidable; the buffer has to be large enough that the two ends sit in different lines, and the number of lines in the slack is what bounds how far apart they can be kept.

Capacity, latency, and the drop policy

A fixed ring has a decision to make when the producer outruns the consumer: block, fail, or overwrite. The three correspond to different structures.

Blocking is a bounded queue: the producer waits on a condition variable or a semaphore when full. The cost is a context switch, and the risk is deadlock if the consumer waits on the producer in turn. A pipe is the kernel’s version of this structure: a fixed-capacity buffer whose writer blocks when it is full. The capacity has a default of 16 pages and, since Linux 2.6.35, can be queried and changed with the fcntl operations F_GETPIPE_SZ and F_SETPIPE_SZ, up to a system limit; it is bounded either way and never grows to absorb a burst.

Failing is a non-blocking queue: the producer returns an error or a null, and the caller decides. This is the shape of a socket send buffer under O_NONBLOCK, and the shape of most in-process lock-free queues.

Overwriting is a lossy ring: the producer advances the read index past the oldest element when full. This is the right policy for telemetry and for audio, where the newest data matters more than the oldest, and it is the reason kernel trace buffers are described as overwrite or overwrite-and-drop.

The choice is not reversible at runtime without changing the index semantics. A blocking ring’s indices never indicate “the producer lapped the consumer”, because the producer cannot advance past the consumer. An overwriting ring’s full condition is exactly that lap, so its read index must be moved by the producer, which means the read index has two writers and the single-writer property is gone.

The memory-ordering failure that is hard to see

The classic bug in a lock-free ring is publishing the index before the data. On a machine with a store buffer, the index store can become visible to the other core before the data store, so the consumer sees a full slot whose contents are the previous iteration’s. The failure is timing-dependent, rare in testing, and reproducible under load.

A second bug is the opposite: the consumer advances r before finishing its read, allowing the producer to overwrite the slot mid-read. Both bugs produce data corruption that looks like a logic error elsewhere. The discipline that prevents them is to treat the index as the publication mechanism and the data as the payload, with the ordering always payload-then-index on the write side and read-then-index on the read side.

A third, subtler bug is assuming that size_t loads and stores are atomic because they are single instructions. On the common 64-bit architectures an aligned 8-byte access is atomic in practice, and the language only guarantees it for atomic types. The compiler is entitled to split, reorder, or eliminate a non-atomic access. volatile forbids the compiler from keeping the value in a register across accesses, which is not the same as an ordering guarantee: in the C abstract machine a volatile access is still not sequenced with respect to an ordinary access made by another thread, so the hardware may reorder it. The distinction between volatile and atomic-with-ordering is the distinction between “the compiler will issue a fresh load every time” and “the load is ordered against other accesses in this thread”.

Where the ring is the wrong structure

The ring assumes a fixed capacity known at construction. When the peak occupancy is not known in advance, the alternatives are a growable deque, which reallocates and therefore cannot be used across a thread boundary without a lock, or a linked queue, which allocates per element and pays a pointer chase per access. The reallocation costs that a growable buffer takes on are the subject of Growth Policies in Dynamic Arrays. The deque’s array-of-blocks layout, discussed in Deque Layouts and the Cost of Push at Both Ends, is the compromise: blocks of fixed size, a growable map of blocks, no per-element allocation.

The ring also assumes the consumer keeps up on average. A producer that outruns the consumer permanently fills the buffer and then either blocks forever or loses data, and no index arithmetic changes that. The sizing question — how much capacity absorbs the burst — is a property of the workload, and the structure only determines what happens when the answer was wrong.