How to use ring buffer in embedded applications and guarantee integrity

Question

I am building an app in a micro controller. The question is, I'm receiving data in the serial port. It is written using interruptions, what I guess is the same as a thread. So, how could I get this data in the buffer and guarantee some integrity if I can't use lock?

Answer 1

Just disable the receive interrupt when you access protected variables (like the ringbuffer, the read and write position) outside the interrupt, so in your case when you need the number of bytes in the input buffer or you need to pop a byte:

int GetBytesAvailable()
{
    int result;        
    DisableReceiveInterrupt();
    result = writePos - readPos;
    EnableReceiveInterrupt();
    if (result < 0)
        result += RINGBUFFER_SIZE;
    return result;
}

int GetNextByte()
{
    int result = -1;
    DisableReceiveInterrupt();
    if (readPos != writePos)
    {
        result = RingBuffer[readPos++];
        readPos %= RINGBUFFER_SIZE;
    }
    EnableReceiveInterrupt();
    return result;
}

When the microcontroller receives a byte while the interrupt is disabled. The interrupt handler will be called as soon as you re-enable the interrupt.

Answer 2

You can accomplish this by disabling interrupts around the instructions in the consumer code which access the buffer and update it's head/tail or whatever pointers.

Pretty much every useful serial peripheral can buffer a received word while receiving the next, so you can get away with disabling interrupts for a small fraction of a word time.

If writing in a language such as C, you will need to use the volatile keyword on shared variables to prevent the compiler from optimizing the actual access in ways which could break sharing between normal and interrupt contexts.

Answer 3

If you have three variables controlling your queue: put_index, get_index, and count, put_indexis only used by the producer thread, get_index by the consumer thread, and count by both.

For your particular platform, updating a particular data type will be atomic; if you use such a data type for count, then if the put() operation checks count and if it is not full adds the data at the put_index, updates put_index then increments count as the last operation. The the get() operation checks count and if it is non zero, gets the data from the get_index, updates get_index and decrements it as the last operation.

By ensuring that count is volatile and atomic, and ensuring that it is only incremented after the data written and index are valid, and decremented only after the data is read then no lock is required.

The critical thing is to ensure a reliance on only a single atomic shared variable rather than determining buffer state through the separate put and get indices.

Answer 4

If you can make your buffer size a power of two, the simplest approach is to simply use two suitably-sized unsigned values which are capable of handling numbers up to the buffer size, along with the buffer. One value says how many bytes have been put into the buffer; the other says how many bytes have been removed. Do not peg these values to the size of the buffer; just let them increase and let them wrap around the integer size in question.

unsigned short fetch_inx, stuff_inx;
unsigned char buff[1024];

void stuff_byte(uint8_t dat)
{
  if ((unsigned short)(stuff_inx - fetch_inx) >= 1024)
    // buffer is full
  else
  {
    buff[stuff_inx & 1023] = dat;
    stuff_inx++;
  }
}
int fetch_byte(void)
{
  uint8_t result;
  if (fetch_inx == stuff_inx)
    return -1;
  result = buff[fetch_inx & 1023];
  fetch_inx++; // Must be done after previous statement--see text
  return result;
}

If the buffer size is exactly 256 or 65,536 bytes, one may use 8-bit or 16-bit "index" values if one doesn't allow more than 255 or 65,535 bytes to be placed into the buffer. Note also that if one doesn't allow the buffer to be completely filled, the fetch_byte routine may use return buff[(fetch_inx++) & 1023];, but that would be unsafe if the buffer could be filled completely (since the buffer slot which was about to be read would become eligible for recycling before it actually gets read).

Provided that stuff_byte doesn't write [stuff_inx] until after data is in the buffer, and fetch_byte doesn't write [fetch_inx] until after data is read, both routines should be able to execute independently in different interrupt or main-line contexts without interference.