Lesson 52. A lock-free SPSC ring buffer

1. Today's topic

SPSC means Single Producer / Single Consumer. It is a ring buffer in which exactly one producer writes head and exactly one consumer writes tail. It suits fast paths:

UART ISR -> EC25 parser task
ADC DMA ISR -> ADC processing task
CAN RX ISR -> protocol task
DMA completion -> buffer-owner task

The main idea: SPSC is simple precisely because contention over the same indices has been excluded in advance.

2. Why this matters in your projects

For EC25 UART, it is preferable to pass a byte stream or chunk descriptors without using an RTOS queue for every byte. For ADC DMA, put descriptors for ready blocks into the SPSC ring rather than samples. For CAN/RS-485, the ISR quickly drains the hardware FIFO and passes a descriptor to the owner task.

3. Theory

When SPSC cannot be used

One SPSC ring cannot serve two ISR producers or two consumer tasks. That is MPSC/MPMC and requires a different algorithm.

Publication problem

The producer must write the slot first and only then publish head.

slot = item
store-release(head)

The consumer must first observe head using acquire, then read the slot:

load-acquire(head)
item = slot

C11 atomics

volatile is not enough. Use stdatomic.h.

_Static_assert(ATOMIC_INT_LOCK_FREE == 2,
               "SPSC atomic indices must always be lock-free");

Monotonic counters

Instead of treating head % N as the state, use monotonic counters:

used = head - tail;
index = counter & (CAPACITY - 1U);

It is preferable for Capacity to be a power of two.

Producer implementation

static bool spsc_try_push(spsc_ring_t *ring, const rx_descriptor_t *item)
{
    unsigned int head = atomic_load_explicit(&ring->head, memory_order_relaxed);
    unsigned int tail = atomic_load_explicit(&ring->tail, memory_order_acquire);
    if (head - tail >= SPSC_CAPACITY) {
        ring->producer_overflows++;
        return false;
    }
    ring->slots[head & SPSC_MASK] = *item;
    atomic_store_explicit(&ring->head, head + 1U, memory_order_release);
    return true;
}

Consumer implementation

static bool spsc_try_pop(spsc_ring_t *ring, rx_descriptor_t *item)
{
    unsigned int tail = atomic_load_explicit(&ring->tail, memory_order_relaxed);
    unsigned int head = atomic_load_explicit(&ring->head, memory_order_acquire);
    if (head == tail) {
        return false;
    }
    *item = ring->slots[tail & SPSC_MASK];
    atomic_store_explicit(&ring->tail, tail + 1U, memory_order_release);
    return true;
}

Why CAS is unnecessary

Only the producer changes head, and only the consumer changes tail. Compare-exchange is therefore not required.

Task notification as a doorbell

The ring stores data; a task notification only wakes the task. The notification count is not the number of elements. Consumer pattern:

for (;;) {
    while (spsc_try_pop(&ring, &desc)) {
        process(desc);
    }
    ulTaskNotifyTake(pdTRUE, portMAX_DELAY);
}

4. Common mistakes

1. Using SPSC with two producers.
2. Using volatile head/tail instead of atomics.
3. Making every operation memory_order_relaxed.
4. Publishing head before writing the slot.
5. Letting the producer change tail.
6. Implementing overwrite-oldest by letting the producer update tail.
7. Using head > tail after wraparound.
8. Not checking whether atomics are lock-free for ISR use.
9. Making the consumer task spin in a loop.
10. Treating a notification as a queue element.
11. Notifying only on a naive EMPTY->NONEMPTY transition and causing a lost wake-up.
12. Ignoring overflow.
13. Reading diagnostic fields without synchronisation and causing a data race.

5. Practical task

Create SPSC_POLICY.md:

# SPSC policy
1. Every SPSC ring has exactly one producer.
2. Every SPSC ring has exactly one consumer.
3. Producer exclusively modifies head.
4. Consumer exclusively modifies tail.
5. Element data is published before head.
6. Slot reuse occurs only after tail publication.
7. Indices use lock-free atomics.
8. Capacity is a power of two.
9. Overflow policy is explicit.
10. Wake-up notification is not the data source.
11. Large payloads are passed by handles.
12. Every ring exposes overflow diagnostics.

Implement a ring for dma_desc_t and test:

empty pop
push/pop
FIFO order
full condition
reuse after drain
wraparound near UINT32_MAX

Then create a host stress test: the producer thread writes 0..9 999 999, and the consumer checks the order. Build with ThreadSanitizer.

6. What to try next

• Integrate the SPSC descriptor ring with the DMA buffer pool from lesson 51.
• Compare ISR duration for xQueueSendFromISR() versus SPSC push + task notification.
• Check ESP32 core affinity: producer ISR and consumer task on the same core or different cores.