Урок 52. Lock-free SPSC ring buffer

1. Тема дня

SPSC означает Single Producer / Single Consumer. Это кольцевой буфер, где ровно один producer пишет head, а ровно один consumer пишет tail. Он подходит для быстрых путей:

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

Главная мысль: SPSC прост именно потому, что мы заранее исключили конкуренцию за одни и те же индексы.

2. Зачем это нужно в твоих проектах

Для EC25 UART лучше передавать поток байтов или chunk descrip- tors без RTOS queue на каждый байт. Для ADC DMA лучше класть в SPSC-ring не samples, а descriptors готовых blocks. Для CAN/RS- 485 ISR быстро освобождает аппаратный FIFO и передаёт descrip- tor owner-task.

3. Теория

Когда SPSC нельзя использовать

Нельзя использовать один SPSC-ring для двух ISR-producers или двух consumer tasks. Это уже MPSC/MPMC, другой алгоритм.

Publication problem

Producer обязан сначала записать slot, а только потом опубликовать head.

slot = item
store-release(head)

Consumer обязан сначала увидеть head через acquire, а потом читать slot:

load-acquire(head)
item = slot

C11 atomics

volatile недостаточно. Используем stdatomic.h.

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

Monotonic counters

Вместо head % N как состояния используем monotonic counters:

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

Capacity лучше делать степенью двойки.

Реализация producer

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

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;
}

Почему CAS не нужен

head изменяет только producer, tail изменяет только consumer. Поэтому compare-exchange не требуется.

Task notification как doorbell

Ring хранит данные, task notification только будит задачу. Notifi- cation count не равен числу элементов. Consumer pattern:

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

4. Типичные ошибки

1. Использовать SPSC с двумя producers.
2. Использовать volatile head/tail вместо atomics.
3. Сделать все операции memory_order_relaxed.
4. Публиковать head до записи slot.
5. Producer изменяет tail.
6. Реализовать overwrite-oldest через producer update tail.
7. Использовать head > tail после wraparound.
8. Не проверить lock-free atomics для ISR.
9. Делать spin-loop consumer task.
10. Считать notification элементом queue.
11. Пытаться уведомлять только при наивном EMPTY->NONEMPTY и получить lost wake-up.
12. Игнорировать overflow.
13. Читать diagnostics fields без синхронизации и получить data race.

5. Практическое задание

Создай 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.

Реализуй ring для dma_desc_t, протестируй:

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

Затем сделай host stress test: producer thread пишет 0..9 999 999, consumer проверяет порядок. Собери с ThreadSanitizer.

6. Что попробовать дальше

• Интегрировать SPSC descriptor ring с DMA buffer pool из урока 51.
• Сравнить ISR duration для xQueueSendFromISR() и SPSC push + task notification.
• Проверить core affinity на ESP32: producer ISR и consumer task на одном ядре или разных.