Lock-Free Ring Buffer 구현 — SPSC·Power-of-2·Memory Order

1
#define RING_SIZE 64   /* power of 2 */
2
#define RING_MASK (RING_SIZE - 1)
3

4
typedef struct {
5
    uint8_t buf[RING_SIZE];
6
    volatile uint16_t head;   /* producer writes */
7
    volatile uint16_t tail;   /* consumer writes */
8
} ring_t;
9

10
bool ring_push(ring_t *r, uint8_t b) {
11
    uint16_t h = r->head;
12
    uint16_t next = (h + 1) & RING_MASK;
13
    if (next == r->tail) return false;   /* full */
14
    r->buf[h] = b;
15
    r->head = next;   /* commit */
16
    return true;
17
}
18

19
bool ring_pop(ring_t *r, uint8_t *out) {
20
    uint16_t t = r->tail;
21
    if (t == r->head) return false;   /* empty */
22
    *out = r->buf[t];
23
    r->tail = (t + 1) & RING_MASK;
24
    return true;
25
}

1
uint16_t next = (h + 1) & RING_MASK;   /* AND — 1 cycle */
2
/* vs */
3
uint16_t next = (h + 1) % RING_SIZE;   /* MOD — 10+ cycle (div) */

1
#include <stdatomic.h>
2

3
bool ring_push_atomic(ring_t *r, uint8_t b) {
4
    uint16_t h = atomic_load_explicit(&r->head, memory_order_relaxed);
5
    uint16_t next = (h + 1) & RING_MASK;
6
    uint16_t t = atomic_load_explicit(&r->tail, memory_order_acquire);
7
    if (next == t) return false;
8

9
    r->buf[h] = b;   /* data write */
10
    atomic_store_explicit(&r->head, next, memory_order_release);
11
                                          /* ↑ data write가 head 갱신 *전*에 가시화 */
12
    return true;
13
}

1
/* Cortex-M3/M4 single core — pipeline in-order */
2
/* DMB 없이도 program order 유지 */
3

4
volatile uint16_t head, tail;   /* volatile은 컴파일러 차단만 */

1
/* Cortex-A SMP 또는 RP2040 dual-M0+ */
2
atomic_store_explicit(&head, next, memory_order_release);

1
typedef struct {
2
    alignas(64) volatile uint16_t head;
3
    char pad1[64 - sizeof(uint16_t)];
4

5
    alignas(64) volatile uint16_t tail;
6
    char pad2[64 - sizeof(uint16_t)];
7

8
    alignas(64) uint8_t buf[RING_SIZE];
9
} ring_t;

1
size_t ring_push_n(ring_t *r, const uint8_t *data, size_t n) {
2
    uint16_t h = r->head, t = r->tail;
3
    size_t free = (t - h - 1) & RING_MASK;
4
    if (n > free) n = free;
5

6
    /* Split copy across wrap */
7
    size_t first = RING_SIZE - h;
8
    if (first > n) first = n;
9
    memcpy(&r->buf[h], data, first);
10
    memcpy(&r->buf[0], data + first, n - first);
11

12
    r->head = (h + n) & RING_MASK;
13
    return n;
14
}

1
ring_t uart_rx_ring;
2

3
void UART_IRQHandler(void) {
4
    uint8_t byte = UART->RDR;
5
    ring_push(&uart_rx_ring, byte);   /* lock-free */
6
}
7

8
void uart_task(void *p) {
9
    uint8_t byte;
10
    for (;;) {
11
        if (ring_pop(&uart_rx_ring, &byte)) {
12
            process(byte);
13
        } else {
14
            vTaskDelay(1);   /* yield */
15
        }
16
    }
17
}

1
ring_t uart_rx_ring;
2
volatile bool data_ready;
3

4
void UART_IRQHandler(void) {
5
    BaseType_t pxHP = pdFALSE;
6
    uint8_t byte = UART->RDR;
7
    if (ring_push(&uart_rx_ring, byte)) {
8
        if (!data_ready) {
9
            data_ready = true;
10
            xSemaphoreGiveFromISR(uart_sem, &pxHP);
11
        }
12
    }
13
    portYIELD_FROM_ISR(pxHP);
14
}
15

16
void uart_task(void *p) {
17
    for (;;) {
18
        xSemaphoreTake(uart_sem, portMAX_DELAY);
19
        data_ready = false;
20
        uint8_t byte;
21
        while (ring_pop(&uart_rx_ring, &byte)) {
22
            process(byte);
23
        }
24
    }
25
}

1
struct cell {
2
    atomic_size_t sequence;
3
    T data;
4
};
5

6
bool mpmc_push(mpmc_t *q, T item) {
7
    size_t pos = atomic_load(&q->enq_pos);
8
    while (1) {
9
        struct cell *c = &q->buf[pos & MASK];
10
        size_t seq = atomic_load(&c->sequence);
11
        if (seq == pos) {
12
            if (atomic_compare_exchange_weak(&q->enq_pos, &pos, pos + 1)) {
13
                c->data = item;
14
                atomic_store(&c->sequence, pos + 1);
15
                return true;
16
            }
17
        } else if (seq < pos) {
18
            return false;   /* full */
19
        } else {
20
            pos = atomic_load(&q->enq_pos);
21
        }
22
    }
23
}

1
SPSC — producer/consumer 각 1개
2
  → head는 producer만, tail은 consumer만 변경
3
  → 같은 변수 두 thread가 write 안 함 → ABA 없음

1
static ring_t g_uart_ring;   /* static — heap 안 씀 */
2

3
ring_t *get_ring(void) { return &g_uart_ring; }

1
struct rte_ring *r = rte_ring_create("name", 1024,
2
                                       SOCKET_ID_ANY,
3
                                       RING_F_SP_ENQ | RING_F_SC_DEQ);
4

5
rte_ring_sp_enqueue(r, obj);
6
rte_ring_sc_dequeue(r, &obj);

1
/* DMA가 ring buffer에 직접 write */
2
HAL_UART_Receive_DMA(&huart, ring.buf, RING_SIZE);
3

4
/* Task — DMA NDTR로 head 계산 */
5
void uart_task(void *p) {
6
    for (;;) {
7
        uint16_t dma_ndtr = DMA->NDTR;   /* 남은 count */
8
        uint16_t head = RING_SIZE - dma_ndtr;
9

10
        while (ring.tail != head) {
11
            process(ring.buf[ring.tail]);
12
            ring.tail = (ring.tail + 1) & RING_MASK;
13
        }
14
        vTaskDelay(1);
15
    }
16
}

1
StreamBufferHandle_t sb = xStreamBufferCreate(256, 1);
2

3
/* ISR */
4
xStreamBufferSendFromISR(sb, &byte, 1, &pxHP);
5

6
/* Task */
7
xStreamBufferReceive(sb, buf, n, portMAX_DELAY);

1
#define RING_SIZE 100   /* ← MOD operation 매번 */

1
volatile uint16_t head;   /* SMP에선 부족 */

1
struct { volatile uint16_t head, tail; uint8_t buf[]; } ring;
2
/* head·tail 같은 line — SMP에서 ping-pong */

1
/* 2 ISR이 같은 ring push */
2
ring_push(r, b);   /* race — SPSC 보장 깨짐 */