🧩Live coding: the SPSC ring buffer

I would pause and turn the exercise into a contract before writing code.

The questions I would ask are:

• What is stored: bytes, pointers, fixed-size events, or generic void * items?
• Is it exactly single producer and single consumer, each on its own thread?
• Should push/pop be non-blocking, or should they spin/block?
• What should happen when the ring is full: fail, overwrite, or wait?
• Is capacity fixed at init time, and can we require a power-of-two size?
• Do we need full capacity, or is leaving one slot empty acceptable?
• Are we targeting portable C11 atomics, Linux kernel style, or a specific platform?

For a live interview I would propose the simplest useful contract: fixed capacity, one producer thread, one consumer thread, non-blocking push and pop, return false on full/empty, power-of-two capacity, and leave one slot empty to disambiguate full from empty.

I would start with a narrow API so the synchronization rules are easy to reason about. For the live exercise I would store pointers, because packet/event rings often pass ownership of buffers rather than copying payloads.

#include <stdatomic.h>
#include <stdbool.h>
#include <stddef.h>

struct spsc_ring {
    size_t cap;
    size_t mask;
    _Atomic size_t head;   /* producer writes */
    _Atomic size_t tail;   /* consumer writes */
    void **slots;
};

bool ring_init(struct spsc_ring *r, void **storage, size_t cap);
bool ring_push(struct spsc_ring *r, void *item);
bool ring_pop(struct spsc_ring *r, void **item_out);

I would say out loud that head is the next slot the producer will write, and tail is the next slot the consumer will read. The array index is idx & mask, so cap must be a power of two. This version leaves one slot empty, so usable capacity is cap - 1.

If they prefer storing objects instead of pointers, I would make the element type explicit rather than using void *. For a first implementation, clear ownership beats a clever generic interface.

I would first write the single-threaded version to make the ring mechanics visible. Then I would upgrade the ordering.

static bool is_power_of_two(size_t x)
{
    return x != 0 && (x & (x - 1)) == 0;
}

bool ring_init(struct spsc_ring *r, void **storage, size_t cap)
{
    if (!r || !storage || !is_power_of_two(cap) || cap < 2)
        return false;

    r->cap = cap;
    r->mask = cap - 1;
    atomic_init(&r->head, 0);
    atomic_init(&r->tail, 0);
    r->slots = storage;
    return true;
}

bool ring_push_naive(struct spsc_ring *r, void *item)
{
    size_t head = atomic_load_explicit(&r->head, memory_order_relaxed);
    size_t tail = atomic_load_explicit(&r->tail, memory_order_relaxed);
    size_t next = (head + 1u) & r->mask;

    if (next == tail)
        return false;

    r->slots[head] = item;
    atomic_store_explicit(&r->head, next, memory_order_relaxed);
    return true;
}

bool ring_pop_naive(struct spsc_ring *r, void **item_out)
{
    size_t tail = atomic_load_explicit(&r->tail, memory_order_relaxed);
    size_t head = atomic_load_explicit(&r->head, memory_order_relaxed);

    if (tail == head)
        return false;

    *item_out = r->slots[tail];
    atomic_store_explicit(&r->tail, (tail + 1u) & r->mask, memory_order_relaxed);
    return true;
}

I would call this naive deliberately. It gets the circular buffer logic right, but the all-relaxed version is not yet portable for two threads because the index update can become visible before the slot contents are visible.

If cap is a power of two, wraparound can use idx & (cap - 1). For example with capacity 1024, idx & 1023 maps a monotonically increasing index into the array.

The reasons are:

• & mask is cheaper and predictable in a hot path.
• It avoids a division-like % operation when the compiler cannot prove the divisor is constant.
• It matches how many descriptor rings are sized in low-level datapaths.

I would not overstate it. If the ring is not hot, % cap is simpler and may be compiled well. But in a live SPSC exercise for a NIC-style role, I would choose power-of-two capacity because it is conventional and keeps the index math cheap.

One detail: I prefer monotonically increasing head and tail counters, then mask only when indexing. That makes occupancy head - tail natural. The earlier naive code wrapped the counters themselves, which is simpler to show but less flexible for full-capacity variants.

I would switch to monotonic indices. Only the producer writes head; only the consumer writes tail. Each side may read the other side's index.

bool ring_push(struct spsc_ring *r, void *item)
{
    size_t head = atomic_load_explicit(&r->head, memory_order_relaxed);
    size_t tail = atomic_load_explicit(&r->tail, memory_order_acquire);

    if (head - tail == r->cap - 1)
        return false;

    r->slots[head & r->mask] = item;
    atomic_store_explicit(&r->head, head + 1u, memory_order_release);
    return true;
}

bool ring_pop(struct spsc_ring *r, void **item_out)
{
    size_t tail = atomic_load_explicit(&r->tail, memory_order_relaxed);
    size_t head = atomic_load_explicit(&r->head, memory_order_acquire);

    if (tail == head)
        return false;

    *item_out = r->slots[tail & r->mask];
    atomic_store_explicit(&r->tail, tail + 1u, memory_order_release);
    return true;
}

The producer writes the slot, then publishes the new head with release. The consumer reads head with acquire before reading the slot. That pair prevents the consumer from seeing the new index but stale slot contents.

The reverse direction is for space: the consumer finishes reading the slot, then publishes tail with release. The producer reads tail with acquire before deciding the slot is free to reuse.

It does not need a lock because there is no contention on writes to the same index.

The ownership split is:

• Producer is the only writer of head.
• Consumer is the only writer of tail.
• Producer writes a slot only before publishing head.
• Consumer reads a slot only after observing published head.
• Producer reuses a slot only after observing published tail.

So the atomics are not protecting a shared read-modify-write. They are providing visibility and ordering between two ownership domains.

The statement becomes false if there are two producers, two consumers, a shared count, a resize operation while the ring is active, or any side touching slots outside the ownership protocol. For MPSC or MPMC, two threads can try to claim the same slot or update the same index, so you need a stronger reservation mechanism such as compare-exchange, per-slot sequence numbers, or a lock.

With only relaxed atomics, the atomic operations are indivisible, but there is no ordering relationship between the slot access and the index publish.

The producer code logically says:

r->slots[head & r->mask] = item;
atomic_store_explicit(&r->head, head + 1u, memory_order_relaxed);

But on a weak memory model, another core may observe the head store before the slot store is visible to it. Then the consumer sees head != tail, reads the slot, and gets an old pointer or uninitialized value.

The consumer side has the mirror issue. If it publishes tail before its slot read is effectively complete, the producer may reuse that slot while the consumer is still reading it.

On x86 TSO, normal stores are observed in store order by other cores, so the first bug is often hidden in practice. But I should not write code whose correctness depends on x86 behavior if the target could be ARM, or if I want portable C11 reasoning. Acquire/release states the actual contract: data first, then publish; observe publish, then consume data.

volatile would not fix this. It only constrains some compiler optimizations on the volatile access. It does not create the cross-core happens-before relationship that the ring needs.

Yes, but only where the ordering is not carrying ownership between threads.

The load of my own index can be relaxed because only I write it:

• Producer loads head relaxed.
• Consumer loads tail relaxed.

The publish stores should be release:

• Producer release-stores head after writing the slot.
• Consumer release-stores tail after reading the slot.

The load of the other side's index is where I use acquire:

• Consumer acquire-loads head before reading a produced slot.
• Producer acquire-loads tail before reusing a consumed slot.

Some implementations weaken the producer's load of tail if slot lifetime is otherwise safe, but in an interview I would keep acquire there because it cleanly expresses that tail means the consumer is finished with the slot. I would rather be correct and explain the possible optimization than remove ordering prematurely.

head and tail are written by different cores. If they sit on the same cache line, the cache line bounces between producer and consumer even though they are not logically sharing a writable variable. That is false sharing.

I would pad or align the hot fields so producer-owned and consumer-owned state are on separate cache lines.

#define CACHELINE 64

struct spsc_ring_padded {
    size_t cap;
    size_t mask;
    void **slots;

    _Alignas(CACHELINE) _Atomic size_t head;
    char pad1[CACHELINE - sizeof(_Atomic size_t)];

    _Alignas(CACHELINE) _Atomic size_t tail;
    char pad2[CACHELINE - sizeof(_Atomic size_t)];
};

In production I would be careful with portability around cache-line size and padding expressions, but the intent is simple: keep producer-written state and consumer-written state from invalidating each other's cache lines.

I would also avoid putting hot indices next to cold debug counters that another core updates. A small layout mistake can turn an otherwise good lock-free ring into a cache-coherency benchmark.

The single-item API is easy to reason about, but it pays atomic loads and stores per item. In a datapath, I would add batch operations so the producer reserves or checks a run of free slots, writes several items, then publishes head once. The consumer similarly reads head once, drains several items, then publishes tail once.

Conceptually:

size_t ring_push_many(struct spsc_ring *r, void **items, size_t n)
{
    size_t head = atomic_load_explicit(&r->head, memory_order_relaxed);
    size_t tail = atomic_load_explicit(&r->tail, memory_order_acquire);
    size_t used = head - tail;
    size_t free_slots = (r->cap - 1u) - used;
    size_t count = n < free_slots ? n : free_slots;

    for (size_t i = 0; i < count; i++)
        r->slots[(head + i) & r->mask] = items[i];

    atomic_store_explicit(&r->head, head + count, memory_order_release);
    return count;
}

The tradeoff is latency versus throughput. Batching reduces atomic/cache traffic and branch overhead, but if the producer waits too long to publish a batch, the first item in the batch waits longer. For a live answer I would say: expose both single-item and batch APIs, measure tail latency, and tune batch size to the workload.

I would start with deterministic single-thread tests because most ring bugs are plain arithmetic and boundary bugs before they are memory-ordering bugs.

The first tests:

• Init rejects null pointers, non-power-of-two capacity, and capacity less than 2.
• Empty ring: pop returns false.
• Fill until usable capacity cap - 1; the next push returns false.
• Pop all items and verify exact FIFO order.
• Wraparound: push/pop repeatedly across several multiples of cap.
• Alternating push/pop leaves the ring usable and ordered.
• Invariant checks: occupancy is never greater than cap - 1; every pushed item is popped once.

I would also test small capacities, especially cap == 2, because leaving one slot empty means it can hold only one item. Tiny capacities expose off-by-one mistakes quickly.

Only after that passes would I move to two-thread stress, because a stress failure is much harder to diagnose if the basic wrap logic is already wrong.

I would run a two-thread producer/consumer stress where the producer pushes a monotonically increasing sequence number and the consumer verifies exact order with no duplicates and no gaps.

The stress should vary:

• Ring capacity: tiny, medium, and large.
• Producer/consumer speed: add deliberate pauses or yields on either side.
• Batch size if batching exists.
• CPU affinity: same core, sibling cores, different cores if possible.
• Runtime: short deterministic tests in CI and longer randomized stress locally.

I would compile and run with ThreadSanitizer when possible. Correct C11 atomics should avoid data races on head and tail; the slot accesses are non-atomic but should be ordered by the acquire/release protocol. If TSan reports races on slots, I would inspect whether the tool understands the synchronization; if not, I would still use the report as a prompt to verify the happens-before edges.

I would add counters for failed pushes and failed pops, but not treat them as correctness failures unless the test expects no backpressure. In a non-blocking ring, full and empty are normal states.

I would benchmark after correctness, and I would define the latency measurement carefully. For a ring, useful measurements are enqueue-to-dequeue latency and operation cost under different producer/consumer rates.

For a low-level benchmark I might use rdtsc or rdtscp on x86, but I would say the caveats out loud: pin threads, use invariant TSC, serialize enough for the measurement, avoid migrating between cores with unsynchronized counters, and subtract measurement overhead where possible.

I would include:

• Warmup before recording, so cold caches and page faults do not dominate.
• Preallocated memory; no allocation in the measured path.
• CPU affinity and fixed frequency settings if the environment allows it.
• Percentiles: p50, p90, p99, p999, not only mean.
• Separate throughput and latency modes, because batching can improve one and hurt the other.

I would also use a histogram rather than just printing averages. For this team, tail latency is the interesting part: a mean can look fine while rare cache misses, scheduler events, or false sharing create spikes.

The simple design leaves one slot empty:

• Empty: head == tail.
• Full: head - tail == cap - 1.
• Usable capacity: cap - 1.

That is the version I would choose first because the invariants are clean.

If all slots must be usable, I have options:

• Use monotonic counters and define full as head - tail == cap, empty as head == tail.
• Use a separate count, but that is unattractive in SPSC because both sides may need to update it.
• Use per-slot sequence numbers, which scales better to more complex queues but adds metadata and logic.

With monotonic counters, masking is only for indexing: slots[idx & mask]. The counters themselves keep enough history to tell full from empty. I would still be careful about unsigned wraparound and choose a wide type like size_t or uint64_t.

For the interview I would say: I started with one empty slot for clarity. If product requirements demand full capacity, monotonic counters are the next clean step.

Not safely in the simple design. The slot array, mask, and capacity are part of the synchronization contract. If one thread changes them while the other is indexing, the other thread can read from freed storage, use the wrong mask, or lose items.

The practical answers are:

• Do not resize; choose capacity from the workload and expose full/drop counters.
• Stop both producer and consumer, drain or quiesce the ring, allocate a new ring, then restart.
• Add a much more complex indirection/versioning scheme, but that is no longer the simple SPSC exercise.

For a NIC-style datapath, I would usually prefer fixed-size rings. Dynamic resize in the hot path is a source of latency spikes and ownership bugs. If bursts overflow the ring, I would first ask whether the capacity, batching, backpressure, or consumer scheduling is wrong before adding live resize.

MPMC changes the problem fundamentally. In SPSC, each index has one writer. In MPMC, multiple producers may try to claim the same head, and multiple consumers may try to claim the same tail. A simple load/store index update is no longer enough.

I would need a reservation protocol, usually based on compare-exchange or fetch-add, and often per-slot sequence numbers so each slot carries its own state. The producer claims a sequence, waits until that slot is free, writes the item, then publishes that slot. The consumer claims a sequence, waits until that slot is ready, reads it, then marks it free for a future wrap.

The costs are higher:

• More atomic read-modify-write operations.
• More cache-line contention on shared indices.
• More complicated full/empty and fairness behavior.
• Harder testing and more subtle ABA/wraparound issues.

So I would not casually generalize the SPSC code. If the requirement is truly MPMC, I would either use a proven queue implementation or design it explicitly around per-slot sequence numbers. For the AMD exercise, the important point is knowing exactly which simplification SPSC bought us: single writer per index.