Loading...
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 | /*
* Copyright (c) 2018-2019 Nordic Semiconductor ASA
*
* SPDX-License-Identifier: Apache-2.0
*/
/**
* Memory FIFO permitting enqueue at tail (last) and dequeue from head (first).
*
* Implemented as a circular queue over buffers. Buffers lie contiguously in
* the backing storage.
*
* Enqueuing is a 2 step procedure: Alloc and commit. We say an allocated
* buffer yet to be committed, exists in a limbo state - until committed.
* It is only safe to write to a buffer while it is in limbo.
*
* Invariant: last-index refers to the buffer that is safe to write while in
* limbo-state. Outside limbo state, last-index refers one buffer ahead of what
* has been enqueued.
*
* There are essentially two APIs, distinguished by the buffer-type:
* API 1 Value-type : MFIFO_DEFINE(name1, sizeof(struct foo), cnt1);
* API 2 Pointer-type : MFIFO_DEFINE(name2, sizeof(void *), cnt2);
*
* Enqueuing is performed differently between APIs:
* | Allocate | Commit
* ------+------------------------+----------------------
* API 1 | MFIFO_ENQUEUE_GET | MFIFO_ENQUEUE
* API 2 | MFIFO_ENQUEUE_IDX_GET | MFIFO_BY_IDX_ENQUEUE
*
* TODO: Reduce size: All functions except mfifo_enqueue should not be inline
*/
/**
* @brief Define a Memory FIFO implemented as a circular queue.
* @details API 1 and 2.
* Contains one-more buffer than needed.
*
* TODO: We can avoid string-concat macros below by setting type in
* MFIFO_DEFINE struct or use a typedef. Yes the size of field 'm' may be
* different, but it is trailing and sizeof is not applied here, so it can
* be a flexible array member.
*/
#define MFIFO_DEFINE(name, sz, cnt) \
struct { \
/* TODO: const, optimise RAM use */ \
/* TODO: Separate s,n,f,l out into common struct */ \
u8_t const s; /* Stride between elements */ \
u8_t const n; /* Number of buffers */ \
u8_t f; /* First. Read index */ \
u8_t l; /* Last. Write index */ \
u8_t MALIGN(4) m[MROUND(sz) * ((cnt) + 1)]; \
} mfifo_##name = { \
.n = ((cnt) + 1), \
.s = MROUND(sz), \
.f = 0, \
.l = 0, \
}
/**
* @brief Initialize an MFIFO to be empty
* @details API 1 and 2. An MFIFO is empty if first == last
*/
#define MFIFO_INIT(name) \
mfifo_##name.f = mfifo_##name.l = 0
/**
* @brief Non-destructive: Allocate buffer from the queue's tail, by index
* @details API 2. Used internally by API 1.
* Note that enqueue is split in 2 parts, allocation and commit:
* 1. Allocation: Buffer allocation from tail. May fail.
* 2. Commit: If allocation was successful, the enqueue can be committed.
* Committing can not fail, as only allocation can fail.
* Allocation is non-destructive as operations are performed on index copies,
* however the buffer remains in a state of limbo until committed.
* Note: The limbo state opens up a potential race where successive
* un-committed allocations returns the same buffer index.
*
* @param idx[out] Index of newly allocated buffer
* @return True if buffer could be allocated; otherwise false
*/
static inline bool mfifo_enqueue_idx_get(u8_t count, u8_t first, u8_t last,
u8_t *idx)
{
/* Non-destructive: Advance write-index modulo 'count' */
last = last + 1;
if (last == count) {
last = 0U;
}
/* Is queue full?
* We want to maintain the invariant of emptiness defined by
* first == last, but we just advanced a copy of the write-index before
* and may have wrapped. So if first == last the queue is full and we
* can not continue
*/
if (last == first) {
return false; /* Queue is full */
}
*idx = last; /* Emit the allocated buffer's index */
return true; /* Successfully allocated new buffer */
}
/**
* @brief Non-destructive: Allocate buffer from named queue
* @details API 2.
* @param i[out] Index of newly allocated buffer
* @return True if buffer could be allocated; otherwise false
*/
#define MFIFO_ENQUEUE_IDX_GET(name, i) \
mfifo_enqueue_idx_get(mfifo_##name.n, mfifo_##name.f, \
mfifo_##name.l, (i))
/**
* @brief Commit a previously allocated buffer (=void-ptr)
* @details API 2
*/
static inline void mfifo_by_idx_enqueue(u8_t *fifo, u8_t size, u8_t idx,
void *mem, u8_t *last)
{
/* API 2: fifo is array of void-ptrs */
void **p = (void **)(fifo + (*last) * size); /* buffer preceding idx */
*p = mem; /* store the payload which for API 2 is only a void-ptr */
*last = idx; /* Commit: Update write index */
}
/**
* @brief Commit a previously allocated buffer (=void-ptr)
* @details API 2
*/
#define MFIFO_BY_IDX_ENQUEUE(name, i, mem) \
mfifo_by_idx_enqueue(mfifo_##name.m, mfifo_##name.s, (i), \
(mem), &mfifo_##name.l)
/**
* @brief Non-destructive: Allocate buffer from named queue
* @details API 1.
* The allocated buffer exists in limbo until committed.
* To commit the enqueue process, mfifo_enqueue() must be called afterwards
* @return Index of newly allocated buffer; only valid if mem != NULL
*/
static inline u8_t mfifo_enqueue_get(u8_t *fifo, u8_t size, u8_t count,
u8_t first, u8_t last, void **mem)
{
u8_t idx;
/* Attempt to allocate new buffer (idx) */
if (!mfifo_enqueue_idx_get(count, first, last, &idx)) {
/* Buffer could not be allocated */
*mem = NULL; /* Signal the failure */
return 0; /* DontCare */
}
/* We keep idx as the always-one-free, so we return preceding
* buffer (last). Recall that last has not been updated,
* so idx != last
*/
*mem = (void *)(fifo + last * size); /* preceding buffer */
return idx;
}
/**
* @brief Non-destructive: Allocate buffer from named queue
* @details API 1.
* The allocated buffer exists in limbo until committed.
* To commit the enqueue process, MFIFO_ENQUEUE() must be called afterwards
* @param mem[out] Pointer to newly allocated buffer; NULL if allocation failed
* @return Index to the buffer one-ahead of allocated buffer
*/
#define MFIFO_ENQUEUE_GET(name, mem) \
mfifo_enqueue_get(mfifo_##name.m, mfifo_##name.s, \
mfifo_##name.n, mfifo_##name.f, \
mfifo_##name.l, (mem))
/**
* @brief Atomically commit a previously allocated buffer
* @details API 1.
* Destructive update: Update the queue, bringing the allocated buffer out of
* limbo state -- thus completing its enqueue.
* Can not fail.
* The buffer must have been allocated using mfifo_enqueue_idx_get() or
* mfifo_enqueue_get().
*
* @param idx[in] Index one-ahead of previously allocated buffer
* @param last[out] Write-index
*/
static inline void mfifo_enqueue(u8_t idx, u8_t *last)
{
*last = idx; /* Commit: Update write index */
}
/**
* @brief Atomically commit a previously allocated buffer
* @details API 1
* The buffer should have been allocated using MFIFO_ENQUEUE_GET
* @param idx[in] Index one-ahead of previously allocated buffer
*/
#define MFIFO_ENQUEUE(name, idx) \
mfifo_enqueue((idx), &mfifo_##name.l)
/**
* @brief Number of available buffers
* @details API 1 and 2
* Empty if first == last
*/
static inline u8_t mfifo_avail_count_get(u8_t count, u8_t first, u8_t last)
{
if (last >= first) {
return last - first;
} else {
return count - first + last;
}
}
/**
* @brief Number of available buffers
* @details API 1 and 2
*/
#define MFIFO_AVAIL_COUNT_GET(name) \
mfifo_avail_count_get(mfifo_##name.n, mfifo_##name.f, \
mfifo_##name.l)
/**
* @brief Non-destructive peek
* @details API 1
*/
static inline void *mfifo_dequeue_get(u8_t *fifo, u8_t size, u8_t first,
u8_t last)
{
if (first == last) {
return NULL;
}
/* API 1: fifo is array of some value type */
return (void *)(fifo + first * size);
}
/**
* @details API 1
*/
#define MFIFO_DEQUEUE_GET(name) \
mfifo_dequeue_get(mfifo_##name.m, mfifo_##name.s, \
mfifo_##name.f, mfifo_##name.l)
/**
* @brief Non-destructive: Peek at head (oldest) buffer
* @details API 2
*/
static inline void *mfifo_dequeue_peek(u8_t *fifo, u8_t size, u8_t first,
u8_t last)
{
if (first == last) {
return NULL; /* Queue is empty */
}
/* API 2: fifo is array of void-ptrs */
return *((void **)(fifo + first * size));
}
/**
* @brief Non-destructive: Peek at head (oldest) buffer
* @details API 2
*/
#define MFIFO_DEQUEUE_PEEK(name) \
mfifo_dequeue_peek(mfifo_##name.m, mfifo_##name.s, \
mfifo_##name.f, mfifo_##name.l)
static inline void *mfifo_dequeue_iter_get(u8_t *fifo, u8_t size, u8_t count,
u8_t first, u8_t last, u8_t *idx)
{
void *p;
u8_t i;
if (*idx >= count) {
*idx = first;
}
if (*idx == last) {
return NULL;
}
i = *idx + 1;
if (i == count) {
i = 0U;
}
p = (void *)(fifo + (*idx) * size);
*idx = i;
return p;
}
#define MFIFO_DEQUEUE_ITER_GET(name, idx) \
mfifo_dequeue_iter_get(mfifo_##name.m, mfifo_##name.s, \
mfifo_##name.n, mfifo_##name.f, \
mfifo_##name.l, (idx))
/**
* @brief Dequeue head-buffer from queue of buffers
*
* @param fifo[in] Contigous memory holding the circular queue
* @param size[in] Size of each buffer in circular queue
* @param count[in] Number of buffers in circular queue
* @param last[in] Tail index, Span: [0 .. count-1]
* @param first[in,out] Head index, Span: [0 .. count-1]. Will be updated
* @return Head buffer; or NULL if queue was empty
*/
static inline void *mfifo_dequeue(u8_t *fifo, u8_t size, u8_t count,
u8_t last, u8_t *first)
{
u8_t _first = *first; /* Copy read-index */
void *mem;
/* Queue is empty if first == last */
if (_first == last) {
return NULL;
}
/* Obtain address of head buffer.
* API 2: fifo is array of void-ptrs
*/
mem = *((void **)(fifo + _first * size));
/* Circular buffer increment read-index modulo 'count' */
_first += 1U;
if (_first == count) {
_first = 0U;
}
*first = _first; /* Write back read-index */
return mem;
}
/**
* @brief Dequeue head-buffer from named queue of buffers
*
* @param name[in] Name-fragment of circular queue
* @return Head buffer; or NULL if queue was empty
*/
#define MFIFO_DEQUEUE(name) \
mfifo_dequeue(mfifo_##name.m, mfifo_##name.s, \
mfifo_##name.n, mfifo_##name.l, \
&mfifo_##name.f)
|