FIFO for embedded systems

Question

I wrote a simple FIFO based on pieces of code I found online. It's intended for embedded systems with very restricted RAM. It's supposed to be very simple and efficient.

The size is always power of 2 (8, 16, 32, 64, 128 etc).

fifo.h

 #ifndef FIFO_H
 #define FIFO_H
 
 struct fifo
 {
 volatile uint8_t * data_ptr;
 volatile uint16_t size;
 volatile uint16_t write_index;
 volatile uint16_t read_index;
 volatile uint16_t elements;
 };
 
 #endif

fifo.c

#include <stdint.h>
#include <stdbool.h>
#include <string.h>
#include "fifo.h"
void fifo_init(struct fifo * fifo)
{
 memset(fifo->data_ptr, (uint8_t)0, fifo->size);
 fifo->write_index = 0;
 fifo->read_index = 0;
}
bool fifo_is_full(struct fifo * fifo)
{
 if (fifo->elements == fifo->size)
 {
 return 1;
 }
 else
 {
 return 0;
 } 
}
bool fifo_is_empty(struct fifo * fifo)
{
 if (fifo->elements == 0)
 {
 return 1;
 }
 else
 {
 return 0;
 }
}
bool fifo_add_byte(struct fifo * fifo, uint8_t newbyte)
{
 if (fifo_is_full(fifo))
 {
 return 0;
 }
 else
 {
 if (fifo->data_ptr == NULL)
 {
 return 0;
 }
 const uint16_t MASK = fifo->size - 1;
 fifo->data_ptr[fifo->write_index] = newbyte;
 fifo->write_index = (++fifo->write_index) & MASK;
 fifo->elements++;
 return 1;
 }
}
bool fifo_get_byte(struct fifo * fifo, uint8_t * output)
{
 if (fifo_is_empty(fifo))
 {
 return 0;
 }
 else
 {
 if (fifo->data_ptr == NULL)
 {
 return 0;
 }
 const uint16_t MASK = fifo->size - 1;
 *output = fifo->data_ptr[fifo->read_index];
 fifo->read_index = (++fifo->read_index) & MASK;
 fifo->elements--;
 return 1;
 }
}

The actual buffer is implemented at other source files like:

uint8_t rx_buffer[RX_BUFFER_SIZE];
struct fifo fifo = { 
 .data_ptr = rx_buffer,
 .size = RX_BUFFER_SIZE,
};

• Hans-Martin Mosner: Where are size and elements initialized? As it stands, fifo_init() leaves them uninitialized, which may lead to undefined behavior.
• MrBit: @Hans-MartinMosner Yes you are right! It's just an example, it's omitted here. All the elements of the struct need to be initialized before used.
• Raffles: This code looks good to me in that it is very clear. Although I agree with the main review regarding collapsing the if/else return combinations into a single line, I have seen if/return else/return many times in safety related code, where clarity and ease of understanding is important. Side issue: many embedded compilers don't support C99 features, so if you want the code to be portable I'd avoid using them. Finally, although not of concern for non-safety related code, you may want to consider making the code robust to SEUs. In particular, if the buffer pointer is corrupted it can wreak havoc!

Answer 1

Return the condition

When we test for equality, a == b is either 1 if they're equal or 0 if they're not (see C11 §6.5.8 Relational operators). Therefore we can simply return the expression instead of an if-else construct:

bool fifo_is_full(struct fifo * fifo)
{
 return fifo->elements == fifo->size;
}
bool fifo_is_empty(struct fifo * fifo)
{
 return fifo->elements == 0;
}

Feel free to add parentheses around the expression to make it more readable. Alternatively we can use a ternary expression, but that just adds noise and has no additional benefit.

Interrupt safety

fifo_add_byte and fifo_get_byte are not interrupt safe.

Let's say we're using fifo_add_byte somewhere in our usual code but also in an interrupt handler, for example to queue jobs. In main we check current GPIO pin states, and the interrupt comes from some kind of bus.

For the sake of simplicity, let's assume fifo->write_index == 0 and fifo->elements == 0.

We enter fifo_add_byte in main:

// in main:
fifo_add_byte(job_fifo, GPIO_PIN4_STATE);

and follow its definition:

bool fifo_add_byte(struct fifo * fifo, uint8_t newbyte)
{
 if (fifo_is_full(fifo))
 {
 return 0;
 }
 else
 {
 if (fifo->data_ptr == NULL)
 {
 return 0;
 }
 const uint16_t MASK = fifo->size - 1;
 fifo->data_ptr[fifo->write_index] = newbyte;
...

And then an interrupt occurs. We already wrote fifo->data_ptr[0] = GPIO_PIN4_STATE so our data is safe, right?

Well, inside the interrupt handler, we have the following line:

// in interrupt_handler_i2c:
fifo_add_byte(job_fifo, i2c_read_data);

fifo->write_index didn't get updated in our main yet, so our fifo->data_ptr[0] will now be set to i2c_read_data. Afterwards, fifo->write_index gets incremented before we exit the interrupt handler and then again after we enter main again:

// ... back in main:
 fifo->write_index = (++fifo->write_index) & MASK;
 fifo->elements++;
 return 1;
 }
}

Our fifo->data_ptr now contains { i2c_read_data, 0, ... }, fifo->write_index = fifo->elements = 2. However, GPIO_PIN4_STATE's value is lost.

Depending on the plattform, fifo->elements++ or another increment operation might get interrupted and even that operation won't work. And no, volatile isn't a proper solution for interrupts.

We have some ways to remedy this:

• we could use critical sections in our index-logic to prevent interrupts
• we could use atomic indices/sizes, if our platform supports those
• we could mark the fifo "in use" and just return false during an interrupt, but that hinders functionality (it's also very error prone and subject to similar issues)
• we could do nothing and simply state that the FIFO isn't safe to be written to from both the usual program and interrupt handlers (same for reading from both locations)

And that's the least we can do to fix this issue: add documentation.

Documentation

None of our code is documented. At least fifo_init needs a documentation, and it needs a very large warning about using a power-of-two size. Otherwise, our MASK logic will yield most interesting behaviours.

The documentation is also the perfect place to state interrupt safety. The FIFO is safe to use within interrupts*, as long as its only written to from within those and only read from outside of an interrupt context.

Usual C-style comments (or Doxygen comments for fancy exports) can be used within our code:

/**
 * \file fifo.c
 *
 * \warning When you use a FIFO in the context of ISRs, make sure that the information
 * flows only in one direction, e.g. use fifo_add_byte only in ISRs and
 * fifo_get_byte only in the rest of your program or vice versa.
 * 
 * Using fifo_add_byte in both ISRs and the rest of your program might
 * yield unexpected results.
*/
...
/**
 * Adds the given byte to the fifo.
 *
 * \returns false if the fifo is full or the data pointer is invalid
 *
 * \warning This function MUST be either used exclusively from ISRs OR the rest
 * of your program and MUST NOT be used in a recursive ISR context.
*/
bool fifo_add_byte(struct fifo * fifo, uint8_t newbyte)
...

Now, you might think that this is a little bit too much, and you're completely right. The following documentation might prove enough:

/** WARNING WARNING WARNING
 * Only push bytes in interrupt routines and only pull bytes in your `main`
 * (or the other way round)!
*/

However, there should be at least something, even if it will be only read by a future version of you. But that future version will be glad to have some hint why data might get lost or duplicated.

^{*: Truth be told: that depends whether elements++ and elements-- are atomic operations on our platform.}

Parting words

Interrupt safety, code brevity and missing documetation aside: well done. Your code is well-formatted, the overall ring-buffer FIFO design is sound, and it's something I'd write in a similar way. I'm not a fan of the & MASK logic, to be honest, but that's personal preference. Also keep in mind that volatile does not mean thread- or interrupt-safe, so better have a look at the keyword and atomics.

Other than that: Well done.

• Raffles: Regarding "whether elements++ and elements-- are atomic", I think this is a very important caveat, and in fact is very unlikely to be the case. My own comment here would be to avoid the shared variable "element", which is used by both the producer and consumer, and use only "write_index" and "read_index", which are each used by either producer or consumer, but not both. Then all that is needed for this to be interrupt safe between producer and consumer is atomic writes. "int" is probably safe, but given that C99 has already been used, this could be sig_atomic_t, or if C11 is used, _Atomic.