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,
};

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.