Ring buffer: the bridge between an interrupt and the main loop

A UART receive interrupt has to run briefly for each byte. If it also processed the byte, it would miss the next one. So the interrupt only puts the byte in a buffer and the main loop does the parsing. The ring buffer is what joins the two.

Structure

One array and two indices (head, tail). On reaching the end it wraps to the start.

#define N 64                      // with a power of two, use & instead of the remainder operator
static volatile uint8_t buf[N];
static volatile uint16_t head, tail;

void rb_put(uint8_t b) {          // called from the ISR
    uint16_t next = (head + 1) & (N - 1);
    if (next != tail) { buf[head] = b; head = next; }  // dropped when full
}
int rb_get(uint8_t *b) {          // called from the main loop
    if (tail == head) return 0;   // empty
    *b = buf[tail]; tail = (tail + 1) & (N - 1);
    return 1;
}

Why it is safe without a lock

The writer changes only head and the reader only tail. With one producer and one consumer, and index reads that are atomic, interrupts do not have to be turned off. One slot is left empty to tell "full" from "empty".

Choosing the size

Calculate from the baud rate and the worst-case main-loop period. At 115200 bps about 11520 bytes arrive per second; if the main loop takes 5 ms, about 58 bytes arrive meanwhile, so 64 bytes is tight and 128 is safe.

In a picture

One array and two indices are all there is. The writer moves only head and the reader only tail.

RoadmapSee where this note sits in Data Structures & Algorithms→

The complete code

#define RB_SIZE 64u                      // a power of two
typedef struct {
    uint8_t buf[RB_SIZE];
    volatile uint16_t head;              // changed only by the ISR
    volatile uint16_t tail;              // changed only by the main loop
} ring_t;

static inline bool rb_put(ring_t *r, uint8_t d) {      // called from the ISR
    uint16_t next = (r->head + 1u) & (RB_SIZE - 1u);
    if (next == r->tail) return false;                 // full
    r->buf[r->head] = d;
    r->head = next;                                    // move it after writing the data
    return true;
}

static inline bool rb_get(ring_t *r, uint8_t *d) {     // called from the main loop
    if (r->tail == r->head) return false;              // empty
    *d = r->buf[r->tail];
    r->tail = (r->tail + 1u) & (RB_SIZE - 1u);
    return true;
}

Design decisions

• Make the size a power of two: wrapping takes one AND instead of a remainder operation (%). On a Cortex-M0, which has no divide instruction, the difference is large.
• Leave one slot empty: equal head and tail was agreed to mean "empty", so "full" is defined as one slot left. A 64-slot buffer holds up to 63 bytes.
• When no lock is needed: only with a single writer and a single reader. If two interrupts write to the same buffer, protection is needed.
• Choosing the size: it must exceed the longest time the main loop is away × the bytes arriving per second. 115200 bps is about 11520 bytes per second, so if the main loop cannot read for 5 ms, 58 bytes pile up.

Problems that come up in practice

• Dropping silently when full makes the cause hard to find. Keep a counter of overflows and include it in the debug output.
• If head is moved before the data is written, the reader can read a slot that has not been written yet. Keep the order.
• If an index is wider than the MCU's word size, its value can change in the middle of a read. On an 8-bit MCU make the indices uint8_t.