1. Overview

A ring buffer, also known as a circular queue, is a data structure that connects the end of a buffer back to the beginning to create a fixed-size, continuous circular memory space. This structure is ideal for streaming data scenarios where efficient memory reuse is critical.

Common applications include inter-process communication, UART data streaming, logging systems, network packet processing, and media stream buffering. Notable implementations exist in the RT-Thread project (ringbuffer.c) and the Linux kernel (kfifo.c).

Key Characteristics:

• No Data Shifting: Unlike standard arrays, once an element is consumed, other elements do not need to be relocated.
• Fixed Capacity: Best suited for scenarios where the maximum capacity is known in advence.
• Static Allocation: Typically uses a static array to avoid frequent heap fragmentation.
• Overwrite Policy: Depending on the use case, you may choose to either discard old data or reject new writes when the buffer is full.

2. Fundamental Principles

Because physical memory is linear, the "circular" logic is simulated using read and write indices. To manage the buffer, you track four main parameters: the buffer start, total capacity, the current write position, and the current read position.

Handling Full Buffer Scenarios

When the write index reaches the capacity, two strategies are common:

• Drop/Overwrite: Silent replace the oldest data. Useful in real-time media streams where missing a frame is preferable to blocking.
• Block/Reject: Return an error code or wait. Essential in messaging systems where data integrity is paramount.

The Mirroring Logic

Distinguishing between an empty state and a full state is a core challenge since both can result in the read and write indices pointing to the same address. A robust approach is the Mirroring Indicator:

By defining the logical address space as 0 to N-1, we can conceptually map pointers into a 0 to 2N-1 range. If the indices are identical and their "mirror bits" match, the buffer is empty. If they are identical but the mirror bits differ, the buffer is full.

If the buffer size is a power of 2, this optimization becomes even simpler: one can use bitwise AND operators instead of modulo operations for index calculation, significantly improving performance.

3. Implementation Strategies

RT-Thread Approach

RT-Thread uses an explicit structure to store indices and mirror flags. The structure ensures clarity by separating the read/write state:

struct RingBuffer {
    uint8_t *storage;
    uint16_t capacity;
    uint16_t read_idx : 15;
    uint16_t read_mirror : 1;
    uint16_t write_idx : 15;
    uint16_t write_mirror : 1;
};

The core logic handles the buffer as two segments during wrap-around scenarios, performing two memcpy operations if the data crosses the physical end of the array.

Linux Kernel (kfifo) Approach

The Linux kfifo approach is highly optimized for performance, often forcing the buffer size to be a power of 2. This allows the use of bitwise masking:

// Example of index conversion in kfifo
index = pointer & (size - 1);

By letting the in (write) and out (read) pointers naturally overflow in an unsigned integer type, the buffer handles the "circular" nature without complex state management. The difference between the in and out pointers at any given time represents the current occupancy.

4. Best Practices

• Concurrency: For a single-reader/single-writer scenario, ring buffers can be implemented as lock-free structures. However, for multi-producer/multi-consumer models, mutexes or spinlocks are mandatory to maintain consistency.
• Index Management: Always prioritize the use of bitwise operators (&) over division (%) by ensuring you're buffer size is a power of 2 (e.g., 256, 1024).
• Selection: Use a ring buffer when you need a FIFO structure with high throughput and predictable memory usage. If you find yourself constantly resizing or searching for elements in the middle of the buffer, a linked list or dynamic array may be more appropriate.