Interrupt Safe Ring Buffer Library

Christoper looks through a circular tube

I created a ring buffer library for embedded systems in C some years ago and have been using it when I need to add a simple queue to my software.  I knew it worked correctly since I created unit tests to validate the code.  However, I noticed that it wasn’t interrupt safe since one of the consumer variables is shared by the producer (the count).  This library requires disabling interrupts when consuming.  Not what I wanted.

There are a number of difficulties when designing ring buffers, mostly dealing with efficiencies of code or data, or the struggle between consumers and producers.  My generic ringbuf library had used a single fill count, but the count had to be updated by the interrupt service routine (producer) and by the routine that retrieved the data (consumer).  I tried to use read and write offset indices, but that required that I always keep an element open since the you can’t tell if the ring is empty or full when the head and tail are the same.

Absolute indices appeared to be interrupt safe, although they require that the buffer length be a power of two.  That seemed to be flexible enough for most embedded work.  I modified and tested my ring buffer library using that method, but my ringbuf, which allowed for a fixed length element,  seemed to be overkill for what I was using it for – gathering bytes from a serial interrupt service routine.  Its API also had a slight flaw such that if the consumer retrieved the data (via Pop rather than just viewing the first element), the producer was free to put new data into the buffer, overwriting the data just retrieved.

I had started my ring buffer library as a simple character (one byte) FIFO – first in, first out.  So, I revisited that code, and modified it to use absolute indices.  A simple byte ring buffer, first in, first out.  Now I had interrupt safe code that would work in my serial interrupt service routine.

Why go to the trouble to make a library module to handle a ring buffer when slapping the following quick and dirty ring buffer code (from Stefan) into the serial module would have worked as well?

   #define N 128
   volatile unsigned int head, tail;
   volatile char buffer[N];
   unsigned int inuse() { return head - tail; }
   void put(char c) { if (inuse() != N) { buffer[head++%N] = c; } }
   void get(char* c) { if (inuse() != 0) { *c = buffer[tail++%N]; } }

Because I needed to know that it worked correctly, and I like reusable library modules.  Especially high quality reusable modules.  Especially high quality reusable modules that include unit tests to validate functionality.  Unit tests that also serve as guides for implementers.

The new module files are ringbuf.c and ringbuf.h for the ring buffer with fixed sized elements, and fifo.c and fifo.h for the ring buffer with byte sized elements. All my versions of the ring buffer and the unit testing framework can be found in the ringbuf.zip file.

One of my original non-interrupt safe ringbuffer libraries that uses a count can be found in the ringbuf.tgz file archive.  Another buffer library I wrote is a linked list that is sorted by key as elements are added, and the elements can be retrieved by key, index, or FIFO. This keylist library is useful for caching dynamic data by key.

About skarg

I write software for a living. So, I dedicated some web space for some stuff that I have worked on. I mostly write embedded C for PC based controllers, but I have dabbled in a few other areas as well.
This entry was posted in software. Bookmark the permalink.

3 Responses to Interrupt Safe Ring Buffer Library

  1. Joaquim Torres says:

    What happens when head reaches the max value of an int and returns to zero? I think inuse() will return a wrong value.

  2. skarg says:

    Hi Joaquim,

    head minus tail will only return zero when they are equal, which is the only time that the buffer is empty, even if the value of head reaches the maximum value of an unsigned integer.

    The concept is exploiting unsigned integer overflow in C:
    http://en.wikipedia.org/wiki/Integer_overflow
    “In the C programming language, signed integer overflow causes undefined behavior, while unsigned integer overflow causes the number to be reduced modulo a power of two, meaning that unsigned integers “wrap around” on overflow. ”

    There is more discussion of the various types of Circular Buffers at Wikipedia from the link in the article:
    http://en.wikipedia.org/wiki/Circular_buffer

    Best Regards,

    Steve

  3. Lei says:

    The absolute index method only wraps around then the buffer size is a divisor of the counter’s capacity. So if the buffer size is a power of two and a unsigned integer counter is used, the counter would always wrap around.

Leave a Reply

Your email address will not be published. Required fields are marked *