· 6 years ago · Feb 20, 2020, 07:56 PM
1/*!
2 * @file rb.h
3 * @author TheComet
4 * @brief Macros for defining a ring buffer.
5 *
6 * The ring buffer consists of a read and write index, and a chunk of memory:
7 * ```c
8 * struct rb_t {
9 * int read, write;
10 * T data[N];
11 * }
12 * ```
13 *
14 * The buffer is considered empty when rb->read == rb->write. It is considered
15 * full when rb->write is one slot behin rb->write. This is necessary because
16 * otherwise there would be no way to tell the difference between an empty and
17 * a full ring buffer.
18 *
19 * There exist two contexts in which data can be written or read: The interrupt
20 * context or "IRQ", and the non-interrupt context, here referred to as "IRL".
21 * This creates 4 possible variations of the ringbuffer API, depending on how
22 * the data flows.
23 *
24 * - If you are writing from an interrupt and reading from the main thread,
25 * use RB_DEFINE_IRQ2IRL()
26 * - If you are writing from the main thread and reading from an interrupt,
27 * use RB_DEFINE_IRL2IRQ()
28 * - If you are writing to and reading from the main thread, use
29 * RB_DEFINE_IRL2IRL()
30 * - If you are writing to and reading from an interrupt context, use
31 * RB_DEFINE_IRQ2IRQ()
32 *
33 * These macros all take 3 arguments:
34 *
35 * - The "name" becomes part of the function signatures and types, allowing
36 * multiple ring buffers to be created in a single translation unit. The
37 * naming scheme will be of the form "rb_##name##_api" for all symbols.
38 * - The type T of data to store. Elements of type T are copied into and out
39 * of the ring buffer.
40 * - The number of elements N in the buffer. This number MUST be a power of 2.
41 * The total number of bytes in the buffer will be sizeof(T) * N.
42 *
43 * These macros will statically allocate a block of memory to be used by the
44 * ring buffer, and also statically allocate the ring buffer structure. You must
45 * call rb_##name##_init() before using any of the other ring buffer functions.
46 *
47 * Some notes on race conditions and the use of volatile
48 * -----------------------------------------------------
49 * The difference between the 4 macro variations is in how the data is written
50 * and read.
51 *
52 * The key observation to make is that race conditions only occur in main thread
53 * context and not in interrupt context. The fact that you are executing code in
54 * interrupt context necesssarily means you have exclusive access to the data
55 * from the main thread. Therefore, only the main thread must worry about
56 * possible interrupts and all loads and stores in interrupt context are safe,
57 * provided the main thread guarded correctly.
58 *
59 * This is of course not true when data is moving from one interrupt to another,
60 * assuming nested interrupts are enabled. But this situation rarely occurs.
61 *
62 * For instance, if the data flow direction is IRQ2IRL, then obviously
63 * rb->write is only ever updated in interrupt context (when writing data),
64 * and rb->read is only ever updated in the main thread (when reading data).
65 *
66 * The main thread must perform a volatile load of rb->write, because it's
67 * possible that an interrupt will update rb->write at any point in time.
68 * However, it is safe to load and store rb->read in the main thread without
69 * any guards or volatile access, because an interrupt routine will only read
70 * from rb->read. If the main thread is careful to not store intermediate values
71 * to rb->read during update, and only loads rb->write once, the store does not
72 * even require __disable_irq()/enable_irq() guards, as long as the store
73 * instruction is atomic.
74 *
75 * rb_take() does in fact access rb->write multiple times (with a volatile load),
76 * once to check if the buffer has data, and again when it calculates how much
77 * contiguous space can be copied out of the buffer. But this does not in fact
78 * require __disable_irq()/__enable_irq() guards. Let's assume that there is
79 * one item in the ring buffer. RB_IS_EMPTY() will load rb->write (volatile)
80 * and compare it to rb->read to determine that yes, the buffer is not empty.
81 * If at this point an interrupt occurs, and the ISR writes another byte to
82 * the buffer, updating rb->write, then when control returns to the main thread,
83 * RB_COUNT_TO_END() will access rb->write again and see that there are now 2
84 * bytes, even though the RB_IS_EMPTY() check was working with the assumption
85 * that there is only 1 byte. Notice how adding data to the buffer does not
86 * invalidate the assumption made by RB_IS_EMPTY(), and therefore, we can
87 * continue execution without problems.
88 *
89 * All of these properties are also true if the data flow direction were
90 * reversed.
91 *
92 * Notice, however, that on a multi-core system, where interrupt service
93 * routines could be executed on a different core, would make this implementation
94 * very unsafe.
95 */
96#ifndef APPLICATION_RB_H
97#define APPLICATION_RB_H
98
99#include <stdint.h>
100
101#define RB_DEFINE_IRQ2IRL(name, T, N) RB_DEFINE_RAW(name, T, N, _VW)
102#define RB_DEFINE_IRL2IRQ(name, T, N) RB_DEFINE_RAW(name, T, N, _VR)
103#define RB_DEFINE_IRQ2IRQ(name, T, N) RB_DEFINE_RAW(name, T, N, )
104#define RB_DEFINE_IRL2IRL(name, T, N) RB_DEFINE_RAW(name, T, N, )
105
106#define RB_DEFINE_RAW(name, T, N, mode) \
107 struct rb_##name##_t \
108 { \
109 uint16_t read; \
110 uint16_t write; \
111 T buffer[N]; \
112 }; \
113 \
114 static struct rb_##name##_t rb_##name; \
115 \
116 /* -------------------------------------------------------------------- */\
117 __attribute__((unused)) \
118 static void rb_##name##_init() \
119 { \
120 rb_##name.read = 0; \
121 rb_##name.write = 0; \
122 } \
123 \
124 /* -------------------------------------------------------------------- */\
125 __attribute__((unused)) \
126 static int rb_##name##_put_single(const T* data) \
127 { \
128 if (RB_IS_FULL##mode(&rb_##name, N)) \
129 return 0; \
130 \
131 uint16_t write = RB_WRITE##mode(&rb_##name); \
132 rb_##name.buffer[write] = *data; \
133 RB_WRITE##mode(&rb_##name) = (write + 1) & ((N)-1); \
134 return 1; \
135 } \
136 \
137 /* -------------------------------------------------------------------- */\
138 __attribute__((unused)) \
139 static int rb_##name##_put_single_value(T data) \
140 { \
141 return rb_##name##_put_single(&data); \
142 } \
143 \
144 /* -------------------------------------------------------------------- */\
145 __attribute__((unused)) \
146 static int rb_##name##_put(const T* data, int len) \
147 { \
148 if (RB_IS_FULL(&rb_##name, N)) \
149 return 0; \
150 \
151 uint16_t write = RB_WRITE##mode(&rb_##name); \
152 int cont_space = RB_SPACE_TO_END##mode(&rb_##name, N); \
153 cont_space = cont_space > len ? len : cont_space; \
154 memcpy(rb_##name.buffer + write, data, cont_space * sizeof(T)); \
155 RB_WRITE##mode(&rb_##name) = (write + cont_space) & ((N)-1); \
156 \
157 return cont_space + (cont_space == 0 ? 0 : \
158 rb_##name##_put(data + cont_space, len - cont_space)); \
159 } \
160 \
161 /* -------------------------------------------------------------------- */\
162 __attribute__((unused)) \
163 static int rb_##name##_take_single(T* data) \
164 { \
165 if (RB_IS_EMPTY(&rb_##name, N)) \
166 return 0; \
167 \
168 uint16_t read = RB_READ##mode(&rb_##name); \
169 *data = rb_##name.buffer[read]; \
170 RB_READ##mode(&rb_##name) = (read + 1) & ((N)-1); \
171 return 1; \
172 } \
173 \
174 /* -------------------------------------------------------------------- */\
175 __attribute__((unused)) \
176 static int rb_##name##_take(T* data, int maxlen) \
177 { \
178 if (RB_IS_EMPTY(&rb_##name, N)) \
179 return 0; \
180 \
181 uint16_t read = RB_READ##mode(&rb_##name); \
182 int cont_space = RB_COUNT_TO_END(&rb_##name, N); \
183 cont_space = cont_space > maxlen ? maxlen : cont_space; \
184 memcpy(data, rb_##name.buffer + read, cont_space * sizeof(T)); \
185 RB_READ##mode(&rb_##name) = (read + cont_space) & ((N)-1); \
186 \
187 return cont_space + (cont_space == 0 ? 0 : \
188 rb_##name##_take(data + cont_space, maxlen - cont_space)); \
189 }
190
191/*
192 * For the following 6 macros it is very important that each argument is only
193 * accessed once.
194 */
195
196#define RB_COUNT_RAW(read, write, N) \
197 (((write) - (read)) & ((N)-1))
198
199#define RB_SPACE_RAW(read, write, N) \
200 (RB_COUNT_RAW((write)+1, (read), N))
201
202#define RB_IS_FULL_RAW(read, write, N) \
203 (RB_SPACE_RAW(read, write, N) == 0)
204
205#define RB_IS_EMPTY_RAW(read, write, N) \
206 ((read) == (write))
207
208#define RB_COUNT_TO_END_RAW(read, write, N) ({ \
209 int end = (N) - (read); \
210 int n = ((write) + end) & ((N)-1); \
211 n < end ? n : end; \
212 })
213
214#define RB_SPACE_TO_END_RAW(read, write, N) ({ \
215 int end = ((N)-1) - (write); \
216 int n = (end + (read)) & ((N)-1); \
217 n <= end ? n : end + 1; \
218 })
219
220#define RB_COUNT(rb, N) (RB_COUNT_RAW((rb)->read, (rb)->write, N))
221#define RB_SPACE(rb, N) (RB_SPACE_RAW((rb)->read, (rb)->write, N))
222#define RB_IS_FULL(rb, N) (RB_IS_FULL_RAW((rb)->read, (rb)->write, N))
223#define RB_IS_EMPTY(rb, N) (RB_IS_EMPTY_RAW((rb)->read, (rb)->write, N))
224#define RB_COUNT_TO_END(rb, N) (RB_COUNT_TO_END_RAW((rb)->read, (rb)->write, N))
225#define RB_SPACE_TO_END(rb, N) (RB_SPACE_TO_END_RAW((rb)->read, (rb)->write, N))
226
227#define RB_COUNT_VW(rb, N) (RB_COUNT_RAW((rb)->read, *(volatile uint16_t*)&(rb)->write, N))
228#define RB_SPACE_VW(rb, N) (RB_SPACE_RAW((rb)->read, *(volatile uint16_t*)&(rb)->write, N))
229#define RB_IS_FULL_VW(rb, N) (RB_IS_FULL_RAW((rb)->read, *(volatile uint16_t*)&(rb)->write, N))
230#define RB_IS_EMPTY_VW(rb, N) (RB_IS_EMPTY_RAW((rb)->read, *(volatile uint16_t*)&(rb)->write, N))
231#define RB_COUNT_TO_END_VW(rb, N) (RB_COUNT_TO_END_RAW((rb)->read, *(volatile uint16_t*)&(rb)->write, N))
232#define RB_SPACE_TO_END_VW(rb, N) (RB_SPACE_TO_END_RAW((rb)->read, *(volatile uint16_t*)&(rb)->write, N))
233
234#define RB_COUNT_VR(rb, N) (RB_COUNT_RAW(*(volatile uint16_t*)&(rb)->read, (rb)->write, N))
235#define RB_SPACE_VR(rb, N) (RB_SPACE_RAW(*(volatile uint16_t*)&(rb)->read, (rb)->write, N))
236#define RB_IS_FULL_VR(rb, N) (RB_IS_FULL_RAW(*(volatile uint16_t*)&(rb)->read, (rb)->write, N))
237#define RB_IS_EMPTY_VR(rb, N) (RB_IS_EMPTY_RAW(*(volatile uint16_t*)&(rb)->read, (rb)->write, N))
238#define RB_COUNT_TO_END_VR(rb, N) (RB_COUNT_TO_END_RAW(*(volatile uint16_t*)&(rb)->read, (rb)->write, N))
239#define RB_SPACE_TO_END_VR(rb, N) (RB_SPACE_TO_END_RAW(*(volatile uint16_t*)&(rb)->read, (rb)->write, N))
240
241#define RB_READ(rb) ((rb)->read)
242#define RB_WRITE(rb) ((rb)->write)
243
244#define RB_READ_VW(rb) ((rb)->read)
245#define RB_WRITE_VW(rb) (*(volatile uint16_t*)&(rb)->write)
246
247#define RB_READ_VR(rb) (*(volatile uint16_t*)&(rb)->read)
248#define RB_WRITE_VR(rb) ((rb)->write)
249
250#endif