Atomic FIFO

This implementation of the FIFO buffer allows accessing the data in the buffer atomically, from the main loop and interrupts, without the need of interrupt locking. The mechanism implemented here can be applied in an application in which access can be distributed between the main loop and any interrupts (with many levels). However, it will not work in an application where the FIFO access is distributed between different tasks in a multithreaded preemptive operating system.

Usage

Before you can use an instance of the FIFO, you must first create and initialize it.

NRF_ATFIFO_DEF(my_fifo, uint32_t, 16);

int main(void)
{
 NRF_ATFIFO_INIT(my_fifo);

 // Now my_fifo may be used

}

The macro NRF_ATFIFO_DEF creates the FIFO buffer using the target data type. It means that the data in the buffer will be properly aligned in memory.

Writing to the FIFO is based on the following scheme:

1. Allocate - Reserve space in the FIFO buffer. The pointer to the buffer is returned.
2. Write item data - Write data using the returned pointer. In the simplest solution, you can use memcpy. However, data may be accessed in a more efficient way than byte-by-byte copying:

   struct point
   {
    int x, y;
   }point_t;
   NRF_ATFIFO_DEF(point_fifo, point_t, 16);
   
   int main(void)
   {
    NRF_ATFIFO_INIT(my_fifo);
   
    nrf_atfifo_context_t context;
    point_t * point;
    if(NULL != (point = nrf_atfifo_item_alloc(point_fifo, &context)))
    {
    // Direct access to the fifo data
    point->x = a;
    point->y = b;
    if(nrf_atfifo_item_put(point_fifo, &context))
    {
    // Send information to the rest of the system
    // that there is new data in the FIFO available to read.
    }
    }
    else
    {
    // Error handling
    }
   }

3. Put - Move the pointer of the data that is ready to be read. The nrf_atfifo_item_put function returns true if the data is currently visible. If it returns false, it means that the current FIFO access interrupts some other access, and the data will be available for reading when the interrupted access finishes.
4. Get - Give access to the variable in a buffer that is already available for reading. The read pointer is moved, but the free space pointer is left intact. It means that the data may be safely accessed until the Free operation on the item is finished. Then, the space in the buffer is released.
5. Process item data
6. Free

Other simple instructions are also available, like nrf_atfifo_alloc_put and nrf_atfifo_get_free. They are using memcpy internally and take care of buffer allocation or freeing. In most cases, memcpy is less efficient than direct buffer access, but in simple usage, using them greatly limits code typing overhead.

Requirements

This FIFO implementation requires the presence of LDREX and STREX instructions. The exclusive access instructions are not available in Cortex M0. It limits the usage of this atomic FIFO implementation to nRF52 only.

Handling interruptions

The implementation assumes that the possible interruption of FIFO access operation works like a stack. A task has to finish the whole access before exiting. It might be interrupted by another task, but this interrupting task must also finish its access. The following is the underlying mechanism of handling interruptions:

1. Task A allocates space in FIFO.
2. Interrupt interrupts the access and allocates space in FIFO.
3. Interrupt pushes a new value into the allocated space.
   • During pushing, it detects that access was interrupted before.
   • The new data is not available, but the space in the FIFO is reserved and data is present here.
4. Task A pushes data into the allocated space.
   • During pushing, it detects that another piece of data is present.
   • Two new data items are available now.

Multithreaded preemptive operating system limitation

This kind of atomic FIFO access works well if access can be split between the main loop and any interrupts. It will not work however, if the FIFO access is distributed between different tasks in a multithreaded preemptive operating system. The problem with a multithreaded preemptive operating system is that the operation might be interrupted by another operation, which would not be finished before going back to the previous operation. For example:

1. Task A allocates space in FIFO.
2. Task B interrupts and allocates space in FIFO.
3. Task A interrupts and pushes data into the FIFO. A problem arises:
   • Task A detects that there is new data in the FIFO.
   • Task A marks two pieces of data available - the one from Task A and the one from Task B.
   • However, there is no valid data from Task B as the space was only booked and no data was set.
4. Task B interrupts and pushes its data. Now the FIFO state is valid, but there was a moment when data was corrupted.

Implementation details

For a simple FIFO, two indexes are remembered: tail and head. Tail is a pointer that keeps track of the historically last element in a list. Head is a pointer that keeps track of the first free space in a list. Thus, it points to an element just after the last stored value.

In the atomic FIFO implementation, these indices are not simple values. They are nrf_atfifo_postag_t structures. They holds read index and write index, 16 bits each. Together, they create a 32-bit value, which makes them available for single LDREX and STREX instructions. Each operation on this pair of read/write indices is run atomically. Therefore, even if the operation is interrupted while new indices are processed, they are just processed once again.

Every allocation moves only the write pointer, leaving the read pointer intact. During a push operation, if it is detected that the old read pointer equals the old write pointer, the read pointer is moved to the current write pointer. Because the implementation uses LDREX and STREX, it is possible to keep track of the fact that the processing during the copying was interrupted, so no data loss is possible at this point.

The old index is stored in operation context - compare it with nrf_atfifo_item_alloc and nrf_atfifo_item_put.

When data is read from the FIFO, the read pointer is moved in the read/write tag in a tail and the pointer to the data is returned. If some interrupt decides to read another data, then the next piece of data is accessed, but during the free operation, nothing is released because it is detected that the old read position does not equal the write position. When the free operation from the first task is executed, all the currently read data is marked as free. The write part of the tail tag is then changed to be equal to the read part.