A generic queue that transfers data from interrupt to main program

Question

This code aims to implement a queue, which transfers data from interrupt to main program in a bare metal embedded system. There are two execution points, the main program and the irq handler. Both execute in the same core.

The implementation should be:

1. Free from data race. Writing and reading concurrently should not have data race.
2. Efficient. Appending data to the queue in irq handler should be O(1). The interrupt should not be turned off for too long when the main program consumes data.
3. Generic. The queue should support any data type and buffer size.

The main idea of the implementation is

1. Use a circular queue to store data.
2. Turn off interrupt to avoid data race.
3. Use user provided functions to be generic.

// IrqQueue.h
#ifndef IRQQUEUE_H
#define IRQQUEUE_H
#include <stdbool.h>
#include <stddef.h>
struct IrqQueueBase;
typedef void (*Q_SetIrqEnableFn)(bool enable); // set enable of the irq
// write value to the idx th element in q
typedef void (*Q_WriteValueFn)(struct IrqQueueBase *q, size_t idx,
 const void *value);
// The base struct. User needs to define derived struct
typedef struct IrqQueueBase {
 // fn and data needed for the queue to be generic
 const Q_SetIrqEnableFn setIrqEnable; // how to enable/disable irq
 const Q_WriteValueFn writeValue; // how to write value to buf
 const size_t maxLen; // max length of elements
 volatile size_t writeIdx; // next position to write into
 // how many elements have been written since last BeginRead
 volatile size_t writeLen;
 volatile size_t readingLen; // the reading length
 // the derived struct should add `volatile DataType buf[maxLen];` after
 // IrqQueueBase
} IrqQueueBase;
// Helper macro to create initial value of IrqQueueBase
#define Q_INIT_VALUE(setIrqEnableFn, writeValueFn, maxLen) \
 { setIrqEnableFn, writeValueFn, maxLen, 0U, 0U, 0U }
typedef struct {
 size_t idx;
 size_t len;
} Q_Range;
// Append value to the queue. Return whether it's successful or not
bool Q_AppendFromIsr(IrqQueueBase *q, const void *value);
// Return the range that is available for reading
Q_Range Q_BeginRead(IrqQueueBase *q);
// Need to be called to free the range returned by BeginRead
void Q_EndRead(IrqQueueBase *q);
// Get the index of next element
static inline size_t Q_NextIdx(size_t idx, size_t maxLen) {
 return (idx + 1U) % maxLen;
}
#endif

// IrqQueue.c
#include "IrqQueue.h"
// Get the index of the first element
static size_t Q_HeadIdx(size_t writeIdx, size_t len, size_t maxLen) {
 return (maxLen + writeIdx - len) % maxLen;
}
bool Q_AppendFromIsr(IrqQueueBase *q, const void *value) {
 const size_t writeLen = q->writeLen;
 const bool full = (writeLen + q->readingLen) >= q->maxLen;
 if (!full) {
 const size_t writeIdx = q->writeIdx;
 q->writeValue(q, writeIdx, value);
 q->writeIdx = Q_NextIdx(writeIdx, q->maxLen);
 q->writeLen = writeLen + 1U;
 }
 return !full;
}
Q_Range Q_BeginRead(IrqQueueBase *q) {
 q->setIrqEnable(false);
 const size_t readingLen = q->writeLen;
 const size_t readIdx = Q_HeadIdx(q->writeIdx, readingLen, q->maxLen);
 q->readingLen = readingLen;
 q->writeLen = 0U;
 q->setIrqEnable(true);
 Q_Range r = {.idx = readIdx, .len = readingLen};
 return r;
}
void Q_EndRead(IrqQueueBase *q) {
 q->setIrqEnable(false);
 q->readingLen = 0U;
 q->setIrqEnable(true);
}

// main.c
#include "IrqQueue.h"
#include <stdint.h>
typedef uint32_t DataType;
#define MAX_LEN 5
typedef struct {
 IrqQueueBase base;
 volatile DataType buf[MAX_LEN];
} IrqQueueU32;
static void WriteValueU32(struct IrqQueueBase *qBase, size_t idx,
 const void *value) {
 IrqQueueU32 *q = (IrqQueueU32 *)qBase;
 q->buf[idx] = *(DataType *)value;
}
/* if (enable) { turns on the interrupt } else { turns off the interrupt } */
static void SetIrqEnable(bool enable) { /*...*/ }
static uint32_t g_overflowCount;
static IrqQueueU32 g_q = {
 .base = Q_INIT_VALUE(SetIrqEnable, WriteValueU32, MAX_LEN), .buf = {0}};
void Irq(DataType data) { // called on hardware interrupt
 IrqQueueBase *qBase = (IrqQueueBase *)&g_q;
 bool ok = Q_AppendFromIsr(qBase, (void *)&data);
 if (!ok) {
 ++g_overflowCount;
 }
}
static void ProcessData(size_t idx, DataType data) { /*...*/ }
static void Step(IrqQueueU32 *const q) {
 IrqQueueBase *const qBase = (IrqQueueBase *)q;
 const Q_Range r = Q_BeginRead(qBase);
 size_t idx = r.idx;
 for (size_t i = 0U; i < r.len; ++i) {
 ProcessData(idx, q->buf[idx]);
 idx = Q_NextIdx(idx, MAX_LEN);
 }
 Q_EndRead(qBase);
}
void Delay(uint32_t ms) { /*...*/ }
int main() {
 IrqQueueU32 *q = &g_q;
 for (;;) {
 Step(q);
 Delay(10);
 }
}

Please help review whether the requirements are met. Most importantly, does this code have data race?

• Madagascar: size_t i = 0U ==> Elide the U, I see no need for it.

Answer 1

in main : IrqQueueU32 *q = &g_q;

g_q is a global variable, that erroneous to create a pointer to it, if you use it that way use a local variable. (even if i think that not gonna stay like that anyway.)

in Irq: IrqQueueBase *qBase = (IrqQueueBase *)q;

Be careful about using different structure types to refer to the same memory. Even if that can work is cleaner to point q to q->base to make your statement.

Here a example of why :

struct a { int size; char *data; };
struct b { int size; char *data; };
struct a foo;
struct a *p = &foo;
struct b *q = (struct b *) &foo;
p->size = 0;
q->size = 1;
x = p->size;

That allows GNU C to assume that p->size is still zero when it is copied into x. The GNU C compiler "knows" that q points to a struct b and this is not supposed to overlap with a struct a. And other compilers might also do this optimization.

The ISO C standard considers such code erroneous, precisely so that this optimization will not be incorrect.

I also want say your program is really hard to read, you should clean it a bit. Otherwise, it's looking good to me.