Implement a ring buffer in C for high-speed data acquisition.
- User
Implement a ring buffer in C for high-speed data acquisition.
Assistant
The user wants an implementation of a ring buffer (circular buffer) in C, specifically tailored for "high-speed data acquisition" (DAQ).
Key Requirements for High-Speed DAQ:
- Speed: The operations (read/write) must be extremely fast. No heavy computation inside the critical sections.
- Thread Safety (Producer-Consumer): High-speed DAQ usually involves an interrupt service routine (ISR) or a dedicated hardware thread writing data, while a main processing thread reads it. The buffer must handle this concurrency correctly without locks if possible (lock-free) or with minimal locking.
- Atomicity: Updating indices (head/tail) must be atomic or protected to prevent race conditions.
- Memory Layout: Contiguous memory is usually best for cache locality.
- Overflow Policy: What happens when the buffer is full? Overwrite old data (circular) or reject new data? For DAQ, overwriting is often dangerous (lost data), but blocking is impossible in an ISR. Usually, "reject" is safer for data integrity, but "overwrite" is used for continuous streaming. I should probably provide the standard "reject" approach but mention the other. Actually, for high-speed, lock-free, "overwrite" is tricky to implement safely without complex logic. The standard
headandtailindex approach with modulo arithmetic is best. - Data Type:
uint8_t(byte buffer) is generic, but often DAQ deals with specific structs or integers. I'll usevoid*or atypedefto make it adaptable, or justuint8_tfor simplicity and let the user handle chunk sizes. Let's go with a template-style approach in C using macros orvoid*with element size.- Decision: Let's stick to a fixed-size type (like
uint16_torint) or a byte-oriented buffer with a size parameter. A byte-oriented buffer is the most versatile.
- Decision: Let's stick to a fixed-size type (like
Design Choices:
-
Lock-free vs. Mutex:
- True Lock-free: Requires C11 atomics or inline assembly. This is the "correct" high-speed way.
- Simple Volatile: Often used in embedded, but technically not guaranteed safe on all architectures (out-of-order execution).
- Mutex: Slower, but portable and safe.
- Decision: Since the prompt asks for "high-speed", I should implement a lock-free version using C11
<stdatomic.h>. This allows single producer / single consumer (SPSC) operation without OS overhead.
-
Structure:
typedef struct { _Atomic uint32_t head; _Atomic uint32_t tail; uint8_t *buffer; uint32_t size; // Must be power of 2 for masking optimization } ring_buffer_t; -
Optimization: Power of 2: If the buffer size is a power of 2, we can use bitwise AND (
&) instead of modulo (%) for index wrapping. Modulo is a division instruction which is slow. Bitwise AND is a single cycle. -
Implementation Details:
- Write: Check if full. If not, write data, then update head.
- Read: Check if empty. If not, read data, then update tail.
- Ordering: Crucial.
- Write: Write data to memory before updating head index (release semantics).
- Read: Read head index before reading data (acquire semantics).
Drafting the Code:
- Headers:
stdint.h,stdatomic.h,stdbool.h,string.h. - Struct: Handle, buffer pointer, mask/size.
- Init: Allocate memory.
- Write:
- Get current head and tail.
- Check full condition:
(head - tail) == size. - Write value.
- Update head:
head = (head + 1) & mask.
- Read:
- Get current head and tail.
- Check empty:
head == tail. - Read value.
- Update tail:
tail = (tail + 1) & mask.
Refining for "High Speed":
- Use
static inlinefunctions for accessors to avoid function call overhead. - Force size to be a power of 2.
- Handle multi-element reads/writes (memcpy chunks) for DMA or bulk transfers? The prompt asks for a "ring buffer", usually implying item-by-item or block-by-block. I'll implement block operations (
write_buffer,read_buffer) as they are much faster for DAQ than byte-by-byte loops.
Addressing Concurrency:
- Single Producer Single Consumer (SPSC): This is the standard for ISR <-> Main Loop. I will explicitly state this assumption. C11 atomics make this robust.
Code Structure:
ring_buffer.h(Interface)ring_buffer.c(Implementation) - Wait, for high speed, putting logic in a.cfile prevents inlining unless LTO is on. I should implement it as a header-only library or static inline functions in the header.
Let's stick to the specific constraint: "High-speed".
- Power of 2 optimization: Essential.
- Memory Barriers: Essential for correctness on weakly ordered CPUs (ARM, etc.).
- Bulk transfers: Essential for efficiency.
The Plan:
- Define a struct.
- Create init/free functions.
- Create
write(push) andread(pop) for single elements. - Create
write_chunkandread_chunkfor blocks of data (crucial for DAQ). - Use
volatileoratomic.- Self-correction: Standard
volatileis often misunderstood as thread-safe. It isn't on multi-core. C11 Atomics are the modern way. However, simple embedded C often avoids C11. I will provide a C11 version because it's "correct" high-speed code. I will also add a note about thevolatilekeyword for older compilers (C99).
- Self-correction: Standard
Let's write the C11 Atomic version.
- Full check:
next_head == tail(standard approach) OR(head - tail) == size(math approach). The math approach requires unsigned integer wrapping, which is defined behavior in C. It allows keeping indices monotonically increasing (mostly) which simplifies things, OR mapping them to array indices. Let's stick to mapped indices0..Size-1but use a Power of 2 mask.
Algorithm (SPSC - Single Producer Single Consumer):
-
Buffer size (power of 2).
-
head: write pointer. -
tail: read pointer. -
push(data):next_head = (head + 1) & mask- if
next_head == tail: return FULL buf[head] = datahead = next_head- Correction: For C11 atomics, we need
memory_order_releasewhen updating head so the consumer sees the data.
-
pop(data):- if
head == tail: return EMPTY *data = buf[tail]tail = (tail + 1) & mask
- if
Wait, what about the "chunk" operations? Implementing a thread-safe chunk operation on a ring buffer is complex because the wrap-around point might split the chunk. However, for "High Speed DAQ", you usually move chunks. Let's stick to the fundamental byte/word access first, maybe add a helper for chunks.
Refined Plan:
- Header-only implementation (for inlining).
- C11 Atomics for strict correctness.
- Power of 2 enforcement for bitwise modulo.
- Type agnostic: Use
size_tfor sizes, storeuint8_t(bytes) but handle element size.
Let's refine the type genericity. Option A: Macro-based generic type (like
#define DEFINE_RING_BUFFER(type)). Option B: Byte buffer (void*). Option B is more "C-ish" for generic libraries, but Option A is faster because it avoidsmemcpyinside the loop if you are reading structs. Given "High Speed", usually DAQ writes raw samples (e.g.,int16_torfloat). I will implement a Byte-Oriented ring buffer. It is the most flexible. If the user wants ints, they cast.Corner Case: Wrap-around. If I need to read 100 bytes, and 80 are at the end of the linear array, and 20 are at the start. The
read_chunkfunction must handle this partial copy logic.Final Code Structure:
- Struct with
uint8_t* buffer,size,mask,atomic head,atomic tail. rb_init: Allocates memory. Enforces power of 2.rb_push: Single byte.rb_pop: Single byte.rb_write: Bulk bytes (handles wrap).rb_read: Bulk bytes (handles wrap).rb_available: How much can read.rb_free: How much can write.
Let's double check the
headandtailupdate ordering. Producer:- Write data to
buffer[head]. - Atomic Store Release
head.
Consumer:
- Atomic Load Acquire
head. - Read data from
buffer[tail]. - Atomic Store Release
tail.
Actually, since only the producer writes
headand only consumer writestail, we just need to ensure visibility. Producer:atomic_store_explicit(&head, new_head, memory_order_release);Consumer:curr_head = atomic_load_explicit(&head, memory_order_acquire);This ensures that when the consumer sees the new head, the data in the buffer is already committed to memory.
Let's generate the response. I will provide a robust, C11-compliant, SPSC (Single Producer Single Consumer) implementation. This is the standard pattern for Interrupt -> Main Loop communication in embedded systems.
Features to Highlight:
- Lock-Free: Uses C11 atomics. No mutexes.
- Optimized Indexing: Requires Power-of-2 size to use
&instead of%. - Bulk Operations: Optimized for moving blocks of data.
- Memory Barriers: Correctly handles cache coherency.
Code Outline:
- Includes.
- Typedef struct.
- Helper:
is_power_of_two. - Init/Free.
- Write/Read (Single).
- Write/Read (Chunk).
- Utilities (Flush, Count).
I will write the implementation as a
.hfile becausestatic inlineis crucial for performance here.One detail: Does the user need a specific data type (like
int)? DAQ usually streams bytes or samples. I'll make it auint8_tbuffer (raw bytes) as it's the most universal interface.Let's verify the logic for
rb_write(chunk). Inputs:rb,data,length.- Check free space. If
length > free, return error or write partial? For strict DAQ, usually return error (preserve data integrity). - Split logic:
len1 = min(length, size - head)memcpy(buf + head, data, len1)memcpy(buf, data + len1, length - len1) - Update head.
This looks correct.
One final check: False Sharing. If
headandtailare in the same cache line, the producer and consumer updating them constantly will cause cache thrashing (the cache line bounces between cores). Optimization: Pad the struct to ensureheadandtailare on different cache lines (usually 64 bytes). I will add padding to the struct. This is a "Pro Tip" for high-speed concurrency.Final Plan:
- Intro explaining the SPSC approach.
- The Header file code (
ring_buffer.h). - Example usage file (
main.c). - Explanation of the optimizations (Power of 2, Atomics, Padding).
Wait, standard C struct padding isn't guaranteed to separate variables unless I use
alignas(C11) or a char array padding. I'll usealignas(64)or manual padding. Actually, let's keep the code relatively standard but mention padding in comments. Addingalignasmight be too compiler-specific for some older embedded compilers, though C11 supports it. I'll stick to standard C11 atomic but maybe skip explicit cache line padding to ensure maximum portability, but mention it in the text. No, actually, I'll include a padding array.Let's refine the
rb_writereturn value. Should it return the number of bytes written? Yes, standard POSIX style.Okay, ready to write. Here is a complete, high-performance, lock-free Ring Buffer implementation in C.
Design Philosophy
For high-speed data acquisition (DAQ), standard library locks (
mutex) introduce unpredictable latency and overhead. This implementation uses a Single Producer / Single Consumer (SPSC) lock-free design.- Atomic Operations: Uses C11
<stdatomic.h>to ensure thread safety between the ISR (Interrupt Service Routine) and the main loop without hardware locks. - Power-of-2 Sizing: Forces the buffer size to be a power of 2. This allows the expensive modulo operator (
%) to be replaced by a bitwise AND (&), which is significantly faster. - Bulk Transfers: Includes functions to read/write chunks of data, minimizing function call overhead.
- Memory Barriers: Correctly uses
memory_ordersemantics to prevent instruction reordering by the compiler or CPU.
The Implementation
1. Header File (
ringbuffer.h)This file defines the structure and the API. It uses
static inlinefunctions to allow the compiler to optimize the code directly into your loops.#ifndef RINGBUFFER_H #define RINGBUFFER_H #include <stdint.h> #include <stddef.h> #include <stdatomic.h> #include <stdbool.h> #include <string.h> // Define the data type for your DAQ samples (e.g., int16_t, float) typedef int16_t sample_t; // Mask for calculating indices (Size MUST be power of 2) typedef struct { sample_t *buffer; uint32_t size; // Total capacity uint32_t mask; // Bitmask for fast modulo (size - 1) // Atomic indices for thread safety // Align to cache line (64 bytes) to prevent "false sharing" performance hits alignas(64) _Atomic uint32_t head; // Write pointer (Producer) alignas(64) _Atomic uint32_t tail; // Read pointer (Consumer) } RingBuffer; // Initialize the buffer. Returns false on allocation failure. bool rb_init(RingBuffer *rb, uint32_t size); // Free the buffer memory void rb_free(RingBuffer *rb); // --- Producer API (Write) --- // Write a single sample static inline void rb_push(RingBuffer *rb, sample_t data) { uint32_t current_head = atomic_load_explicit(&rb->head, memory_order_relaxed); uint32_t next_head = (current_head + 1) & rb->mask; // Simple overflow protection: drop data if full // In DAQ, you might prefer to overwrite or log an error. if (next_head == atomic_load_explicit(&rb->tail, memory_order_acquire)) { return; // Buffer full } rb->buffer[current_head] = data; // Ensure the write happens before updating the index atomic_store_explicit(&rb->head, next_head, memory_order_release); } // Write multiple samples (high performance) static inline uint32_t rb_write(RingBuffer *rb, const sample_t *data, uint32_t count) { uint32_t current_head = atomic_load_explicit(&rb->head, memory_order_relaxed); uint32_t current_tail = atomic_load_explicit(&rb->tail, memory_order_acquire); uint32_t available = (current_tail - current_head - 1 + rb->size) & rb->mask; if (count > available) count = available; if (count == 0) return 0; // Calculate contiguous block logic for memcpy optimization // We might need two memcpy calls if we wrap around the end of the array // First chunk: from head to end of linear memory uint32_t first_chunk = rb->size - current_head; if (first_chunk > count) first_chunk = count; memcpy(&rb->buffer[current_head], data, first_chunk * sizeof(sample_t)); // Second chunk: if we wrapped if (first_chunk < count) { memcpy(rb->buffer, &data[first_chunk], (count - first_chunk) * sizeof(sample_t)); } uint32_t next_head = (current_head + count) & rb->mask; atomic_store_explicit(&rb->head, next_head, memory_order_release); return count; } // --- Consumer API (Read) --- // Read a single sample. Returns true if successful. static inline bool rb_pop(RingBuffer *rb, sample_t *data) { uint32_t current_tail = atomic_load_explicit(&rb->tail, memory_order_relaxed); if (current_tail == atomic_load_explicit(&rb->head, memory_order_acquire)) { return false; // Empty } *data = rb->buffer[current_tail]; uint32_t next_tail = (current_tail + 1) & rb->mask; atomic_store_explicit(&rb->tail, next_tail, memory_order_release); return true; } // Peek at data without removing it static inline uint32_t rb_peek(RingBuffer *rb, sample_t *data, uint32_t count) { uint32_t current_tail = atomic_load_explicit(&rb->tail, memory_order_relaxed); uint32_t current_head = atomic_load_explicit(&rb->head, memory_order_acquire); uint32_t available = (current_head - current_tail + rb->size) & rb->mask; if (count > available) count = available; if (count == 0) return 0; uint32_t first_chunk = rb->size - current_tail; if (first_chunk > count) first_chunk = count; memcpy(data, &rb->buffer[current_tail], first_chunk * sizeof(sample_t)); if (first_chunk < count) { memcpy(&data[first_chunk], rb->buffer, (count - first_chunk) * sizeof(sample_t)); } return count; } // Flush/Acknowledge data after peeking (moves the tail) static inline void rb_flush(RingBuffer *rb, uint32_t count) { uint32_t current_tail = atomic_load_explicit(&rb->tail, memory_order_relaxed); uint32_t next_tail = (current_tail + count) & rb->mask; atomic_store_explicit(&rb->tail, next_tail, memory_order_release); } // Check count available static inline uint32_t rb_available(RingBuffer *rb) { uint32_t current_head = atomic_load_explicit(&rb->head, memory_order_acquire); uint32_t current_tail = atomic_load_explicit(&rb->tail, memory_order_relaxed); return (current_head - current_tail + rb->size) & rb->mask; } #endif2. Implementation File (
ringbuffer.c)Handles the memory allocation and initialization.
#include "ringbuffer.h" #include <stdlib.h> // Helper to check if power of 2 static inline bool is_power_of_two(uint32_t x) { return x && !(x & (x - 1)); } bool rb_init(RingBuffer *rb, uint32_t size) { // Size must be power of 2 for bitwise masking optimization if (!is_power_of_two(size)) { // Option: Round up to next power of 2 here if desired. // For strict embedded systems, explicit sizes are safer. return false; } // Allocate buffer aligned to cache line (optional but good for performance) // Using standard malloc here for portability. rb->buffer = (sample_t *)malloc(size * sizeof(sample_t)); if (!rb->buffer) return false; rb->size = size; rb->mask = size - 1; rb->head = 0; rb->tail = 0; return true; } void rb_free(RingBuffer *rb) { if (rb->buffer) { free(rb->buffer); rb->buffer = NULL; } }Example Usage
Here is a simulation of a DAQ system where an "Interrupt" produces data and the "Main Loop" consumes it.
#include <stdio.h> #include "ringbuffer.h" // 1. Simulated ISR (Producer) // In a real system, this would be void ADC_IRQHandler() void simulate_data_acquisition(RingBuffer *rb) { static int16_t dummy_sensor_value = 0; // Generate a chunk of 10 samples at once for efficiency int16_t batch[10]; for(int i=0; i<10; i++) { batch[i] = dummy_sensor_value++; } uint32_t written = rb_write(rb, batch, 10); if (written < 10) { printf("Buffer Overflow! Data lost.\n"); } } // 2. Main Processing Loop (Consumer) void process_data(RingBuffer *rb) { // Peek to see how much data we have uint32_t count = rb_available(rb); if (count > 0) { // Allocate a scratch buffer on stack (VLA or malloc) int16_t temp_buffer[count]; // Peek copies data but keeps it in ring buffer rb_peek(rb, temp_buffer, count); // Process the data (e.g., FFT, filtering, writing to SD card) printf("Processing %d samples. First: %d, Last: %d\n", count, temp_buffer[0], temp_buffer[count-1]); // Now actually remove it from buffer rb_flush(rb, count); } } int main() { RingBuffer rb; // Initialize with 1024 samples (must be power of 2) if (!rb_init(&rb, 1024)) { fprintf(stderr, "Failed to init buffer\n"); return 1; } // Simulation Loop for (int i = 0; i < 5; i++) { simulate_data_acquisition(&rb); // "ISR" runs fast process_data(&rb); // Main loop processes batches } rb_free(&rb); return 0; }Optimization Details
-
Why
memory_order_acquire/release?- In simple terms:
releaseensures that all memory writes (putting data into the array) are finished before the index pointer is updated. acquireensures that reading the index pointer happens before reading the data from the array.- This creates a perfect handshake without disabling interrupts or using mutexes.
- In simple terms:
-
Why
alignas(64)?- Modern CPUs load memory in "cache lines" (usually 64 bytes).
- If
headandtailare in the same cache line, updatinghead(in the ISR) will force the CPU to re-fetchtail(in the main loop) to maintain cache coherency. This causes massive slowdowns known as False Sharing. Padding ensures they sit on different lines.
-
Why
rb_peekandrb_flush?- In high-speed DAQ, you often don't know how much data you need until you look at it (e.g., looking for a sync byte).
peeklets you inspect data without committing to a read, which avoids the "read byte, check, read byte" loop overhead.
- In high-speed DAQ, you often don't know how much data you need until you look at it (e.g., looking for a sync byte).
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.