blob: a4616f426e5f4abc2e9bd5a18f5a77fd3176c9dc [file] [log] [blame]
/*
* 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 */ \
uint8_t const s; /* Stride between elements */ \
uint8_t const n; /* Number of buffers */ \
uint8_t f; /* First. Read index */ \
uint8_t l; /* Last. Write index */ \
uint8_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(uint8_t count, uint8_t first, uint8_t last,
uint8_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(uint8_t *fifo, uint8_t size, uint8_t idx,
void *mem, uint8_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 */
cpu_dmb(); /* Ensure data accesses are synchronized */
*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 uint8_t mfifo_enqueue_get(uint8_t *fifo, uint8_t size, uint8_t count,
uint8_t first, uint8_t last, void **mem)
{
uint8_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(uint8_t idx, uint8_t *last)
{
cpu_dmb(); /* Ensure data accesses are synchronized */
*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 uint8_t mfifo_avail_count_get(uint8_t count, uint8_t first, uint8_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(uint8_t *fifo, uint8_t size, uint8_t first,
uint8_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(uint8_t *fifo, uint8_t size, uint8_t first,
uint8_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(uint8_t *fifo, uint8_t size, uint8_t count,
uint8_t first, uint8_t last, uint8_t *idx)
{
void *p;
uint8_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(uint8_t *fifo, uint8_t size, uint8_t count,
uint8_t last, uint8_t *first)
{
uint8_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)