FIFO design

[sangar]

Hello,

I want to design a FIFO C code which should write if there is only  space for 100 bytes(Temp data). It is not like as byte by byte read and write. Because, missing 1 byte in 100 bytes while read, destruct whole application and also it will be asynchoronus read and write. Please any body guide me to do it in an efficient way so that no collapse will occur when read.




Thanks
Muthu

[ebclr]

I would use a circular buffer and 2 pairs of Start and end pointer,

[nctnico]

And if you keep track of the number of bytes written (+1) and read (-1) you always know how many bytes there are in the FIFO and also how many you can write.

[Jeroen3]

Have you tried github? FIFO and buffer implementations can easily be found.
For example, I made one that should fit all my future use cases, which it has so far.
https://github.com/Jeroen6/xIFO

The only thing is does not have is exclusive memory access when working with multiple threads. Since that requires platform/application specific operations.

[NorthGuy]

Or, something like that:

Code: [Select]

#define FIFO_SIZE 64 // must be a power of 2 up to MAX_INT/4
#define FIFO_MASK (FIFO_SIZE-1)

signed int head; // points to where we write to
signed int tail; // points to where we read from
char fifo[FIFO_SIZE];

// returns the number of used elements. Can read only if it is > 0
inline signed int n_used {
  return (head - tail);
}

// returns the number of empty elements. Can write only if it is > 0
inline signed int n_empty {
  return (FIFO_SIZE + tail - head);
}

// write an element. Do NOT call if n_empty() == 0
void write(char x) {
  fifo[head&FIFO_MASK] = x;
  head++; // must be atomic for thread safety
}

// read an element. Do NOT call if n_used() == 0
char read() {
  char x;
  x = fifo[tail&FIFO_MASK];
  tail++; // must be atomic for thread safety
  return x;
}

// look at the i-th element from the tail (if it exists) without removing. i = 0 returns the element at tail
// works if i < n_used(). Otherwise returns garbage.
char peek(signed int i) {
  return fifo[(tail+i)&FIFO_MASK];
}
If all the reads are from the same thread and writes from another, then it is thread-safe (if ++ and -- operations are atomic).

I have just typed it in, so it may require some testing.

[sangar]

Hi,
below is My code. I am trying to fill FIFO with 80 bytes(instead 100 bytes) whenever want to write FIFO. And also I will read 80 bytes whenever I want to read. I don't know how much stable it is.Please give your comments.

Q1: Should I set Size to power of 2?If so, why?



#MAX_ITEMS 801

int fifo_write(uint8_t *buf, int nbytes)    //nbytes=80
{
   int i;
   uint8_t *p;
   p = buf;
   
   if (fifo.head==720 && fifo.tail==0)
   {
      return nbytes;
   }
   for(i=0; i < nbytes; i++)
        {
      //first check to see if there is space in the buffer
      if( (fifo.head + 1 == fifo.tail) ||   ( (fifo.head + 1 == MAX_ITEMS) && (fifo.tail == 0) ))
      {
         return i; //no more room
      }
      else
                {
         fifo.FIFO_BUFFER[fifo.head] = *p++;
         fifo.head++;  //increment the head
         if( fifo.head == MAX_ITEMS )
         {  //check for wrap-around
            fifo.head = 0;
         }
      }
           }
      
}

int fifo_read(uint8_t *buf, int nbytes)   //nbytes=80
{
   int i;
   uint8_t *p;
   p = buf;
   for(i=0; i < nbytes; i++)
       {
      if( fifo.tail != fifo.head )
               {
                         //see if any data is available
         *p++ = fifo.FIFO_BUFFER[fifo.tail];  //grab a byte from the buffer
         fifo.tail++;  //increment the tail
         if( fifo.tail == MAX_ITEMS )
                        { 
                                //check for wrap-around
            fifo.tail = 0;
         }
      }
      else
      {
         return i; //number of bytes read
      }
      }
   return nbytes;
}

Thanks,
Muthu

[NorthGuy]

Q1: Should I set Size to power of 2?If so, why?

Power of 2 usually works better, one way or another.

For example, in the code I posted, it allows to skip wrapping tests. "tail" and "head" are free-running. They hold the number of elements from the beginning of the operation. Therefore, the tests for free/empty are very easy. (head - tail) returns a number of elements currently in the buffer.

In addition, the free-running tail and head allows you to use the whole buffer. If you constrict head and tail to always point to inside the buffer, one of the positions is lost. Not abig deal if your buffer is 1000 elements, but may be quite substantial if it is 4 or 8.

Further. Pointers are free running, but the buffer is circular. Therefore the real position of the byte at head is (head%BUFFER_SIZE) and the position of the byte at tail is (tail%BUFFER_SIZE). Division is usually a long operation which is better avoided. If BUFFER_SIZE is a power of two, it can be replaced with "&(BUFFER_SIZE-1)" which is a very fast operation on any processor. This will come very handy when you want to push your baud rate to the limit.

What happens if you don't want free-running tail and head, and would rather restrict them so that they always point to a valid place in the buffer.  Setting BUFFER_SIZE to a power of 2 is not of that much help any more. However this makes checks for empty/full more complicated. For example, instead of simple subtraction, you do

Code: [Select]

if( (fifo.head + 1 == fifo.tail) ||   ( (fifo.head + 1 == MAX_ITEMS) && (fifo.tail == 0) ))

And you have to do it for every characters!

What if you want to detect the exact number of characters you can read then read them all at once.  With free-running tail and head it is still a simple subtraction. With the restrited head and tail, the check is quite complicated.

Now imagine what you would need to do to implement the peek() function with the constricted tail and head.

Another thing which gets more complicated are increments, such as:

Code: [Select]

fifo.tail++;  //increment the tail
if( fifo.tail == MAX_ITEMS )  { 
   //check for wrap-around
   fifo.tail = 0;
}
instead of a simple increment.

If you want to make it thread-safe (say when you write from the ISR then read from the main), it is even more work:

Code: [Select]

int nexttail = fifo.tail + 1;
if( nexttail == MAX_ITEMS )  { 
   //check for wrap-around
   nexttail = 0;
}
fifo.tail = nexttail; // this last assignment operation must be atomic to ensure thread safety.

Or, if FIFO_SIZE is a power of 2 you can use the following code for the increment:

Code: [Select]

fifo.tail = (fifo.tail+1)&(FIFO_SIZE-1); // the assignment must be atomic for thread safety.

So, it is entirely up to you. Either

- you are prepared to use more complicated code to avoid FIFO_SIZE being power of two.

or

- you are prepared to increase the FIFO_SIZE to the next power of two in favour of better and more efficient code.

[sangar]

Hi,

// returns the number of used elements. Can read only if it is > 0
inline signed int n_used {
  return (head - tail);
}

I am using the above function to read 80 bytes like

if(n_used()>=80)
{
fifo_read(appDataReqBuffer,80);
}

But, after some read, I am getting negative integer from n_used();Results read get stopped.


I think it may come like
inline signed int n_used {
  return (head -tail)&FIFO_MASK;
}

Thanks,
Muthu

[NorthGuy]

// returns the number of used elements. Can read only if it is > 0
inline signed int n_used {
  return (head - tail);
}

I am using the above function to read 80 bytes like

if(n_used()>=80)
{
fifo_read(appDataReqBuffer,80);
}

But, after some read, I am getting negative integer from n_used();Results read get stopped.

head should always be ahead of tail. You maintain this by making sure you only read when there's something to read.

If you do that, the difference stays positive, even when it goes through the overflow. For example, when head overflows (rolls from 2147483647 [hex 0x7fffffff] to -2147483648 [hex 0x80000000] on 32-bit computer) the calculated difference stays correct. (0x80000000 - 0x7fffffff) will still be calculated as 1.

If this relationship is lost, you probably read more than you write.

What values do you get in the head and tail when the problem happens?

There also could be a problem if you do it from different threads, but "tail++" and "head++" are not atomic. This is, of course, platform-dependent.

I think it may come like
inline signed int n_used {
  return (head -tail)&FIFO_MASK;
}

You can do this, but it will only be masking bugs elsewhere, making them harder to find.

<edit>You cannot really do this. You need to preserve at least one extra bit for the calculation to be correct. This is necessary to account for the situations where head has rolled over the fifo boundary, but tail didn't.

[sangar]

Hi,

I have set buffer size to 1024 (2^10). There is always 80 count difference between head and tail after I write FIFO with 80 bytes.

Yes, before read I am calling n_used function to see something is to read. I am seeing problem with nused function's return value. After head points to 1024, it points to 0th position of the buffer. That time tail point to somewhere around 950. Subtracting these two giving negative value (tail-head).

Let us say, tail points to 960 and head points to 40(after one cycle complete). That time, I am seeing -80 which is returned by n_used instead +80.


Thanks,
Muthu

[NorthGuy]

Let us say, tail points to 960 and head points to 40(after one cycle complete). That time, I am seeing -80 which is returned by n_used instead +80.

If you only do "head++" to the head, and "tail++" to the tail, this should never happen.

If you have 80 elements in the buffer and the tail is 960, then the head should be 960 + 80 = 1040. This is because you wrote 1040 elements into the buffer (and incrememted the head 1040 times), and you have read 960 of them (and incremented the tail 960 times). (1040 - 960) = 80 left.

1040 would point outside the buffer. That's why you need to do "&FIFO_MASK".

(1040&FIFO_MASK) = 1040&1023 = 16. The head is 1040 and it points to 16-th element of the buffer.


However, if you have a code such as

Code: [Select]

fifo.head++;
if( fifo.head == MAX_ITEMS )  { 
   //check for wrap-around
   fifo.head = 0;
}
which wraps the head down, then the head will be 16 instead of 1040 and (head - tail) will be negative. In this case, calculating the amount of data in the buffer becomes complicated and simple difference doesn't work. That is precisely why I recommend leaving the head at 1040 and use fifo[1040&FIFO_MASK] to access the buffer.

[sangar]

Hi,

fifo.FIFO_BUFFER[fifo.head&FIFO_MASK] =*p++;
fifo.head++;

This is changing  head to 0 after 1024. I am seeing this change while I debug.

[sangar]

Hi,

Sorry. head and tail not reset to 0. Should I set  32 bit integer for both head and tail.

[NorthGuy]

fifo.FIFO_BUFFER[fifo.head&FIFO_MASK] =*p++;
fifo.head++;

This is changing  head to 0 after 1024. I am seeing this change while I debug.

This souldn't be happening. Could you post your current declaration of the fifo record?

Sorry. head and tail not reset to 0. Should I set  32 bit integer for both head and tail.

They must be the same size. For 1024-byte buffer 16-bit integers are ok. 32-bit integers should work too.

[sangar]

Hi,
Below is My declaration and function usage.


//FIFO Declaration//
typedef struct fifo_t
{
   uint8_t FIFO_BUFFER[FIFO_SIZE];
   int32_t head;
   int32_t tail;
}fifo_t;
static fifo_t fifo;

/*Space check----------------------------*/
int n_empty(void)
{
   return (FIFO_SIZE + fifo.tail - fifo.head);
}

/*returns the number of used elements. Can read only if it is > 0*/
int n_used(void)
{
   return (fifo.head -fifo.tail);
}

/*FIFO-80 Bytes write */
int fifo_write(uint8_t *buf, int nbytes)
{
   int i;
   uint8_t *p;
   p = buf;
   for(i=0; i < nbytes; i++)
   {
   fifo.FIFO_BUFFER[fifo.head&FIFO_MASK] =*p++;
   fifo.head++; // must be atomic for thread safety
   }
   return nbytes;
}

/*Read -80 bytes from FIFO */

int fifo_read(uint8_t *buf, int nbytes)
{
   int i;
   uint8_t *p;
   p = buf;
   for(i=0; i < nbytes; i++)
   {
         *p++ = fifo.FIFO_BUFFER[fifo.tail&FIFO_MASK];  //grab a byte from the buffer
          fifo.tail++;  //increment the tail
   }
   return nbytes;
}

int main(void)
{
while(1)
{
if(n_empty()>=80)   //check if there is space for 80 bytes to write
{
 fifo_write(acqbuf,80);
}
if(n_used()>=80)   // check if there is at-least 80 bytes to read
{
fifo_read(appDataReqBuffer,80);
}
}
}


Thanks,
Muthu

[NorthGuy]

You need to make sure that the counting operations are done on operands of the same size. C has a thing called "integer promotion" - everything that is shorter than "int" gets expanded to "int" before operations are performed. This may screw things up.

Your code:

Code: [Select]

typedef struct fifo_t
{
   uint8_t FIFO_BUFFER[FIFO_SIZE];
   int32_t head;
   int32_t tail;
}fifo_t;

int n_empty(void)
{
   return (FIFO_SIZE + fifo.tail - fifo.head);
}

int n_used(void)
{
   return (fifo.head -fifo.tail);
}
The code above will work if "int" has the same size as "int32_t". But if int was 64-bit it wouldn't work. This is because integer promotion would expand fifo.head and fifo.tail into 64-bit. Consider the following example:

head = 0x80000001, tail = 0x7fffffff

The difference we want to get is 2. But the expansion to 64-bit leads to

head = 0xffffffff80000001, tail = 0x000000007fffffff

The result will be 0xfffffff00000002 (-4294967294 decimal). If you let it go into further calculations this way, everything is screwed. It has to be chopped to the original size of head and tail - 0x00000002 - this is the correct result.

Therefore, you need to make sure that everything has the same type. The size of this type doesn't matter as long as it is big enough. But it must be the same. Any of the following three will work:

Code: [Select]

typedef struct fifo_t
{
   uint8_t FIFO_BUFFER[FIFO_SIZE];
   int32_t head;
   int32_t tail;
}fifo_t;

int32_t n_empty(void)
{
   return (FIFO_SIZE + fifo.tail - fifo.head);
}

int32_t n_used(void)
{
   return (fifo.head -fifo.tail);
}

Code: [Select]

typedef struct fifo_t
{
   uint8_t FIFO_BUFFER[FIFO_SIZE];
   int16_t head;
   int16_t tail;
}fifo_t;

int16_t n_empty(void)
{
   return (FIFO_SIZE + fifo.tail - fifo.head);
}

int16_t n_used(void)
{
   return (fifo.head -fifo.tail);
}

Code: [Select]

typedef struct fifo_t
{
   uint8_t FIFO_BUFFER[FIFO_SIZE];
   int head;
   int tail;
}fifo_t;

int n_empty(void)
{
   return (FIFO_SIZE + fifo.tail - fifo.head);
}

int n_used(void)
{
   return (fifo.head -fifo.tail);
}
But this one won't:

Code: [Select]

typedef struct fifo_t
{
   uint8_t FIFO_BUFFER[FIFO_SIZE];
   int16_t head;
   int16_t tail;
}fifo_t;

int32_t n_empty(void)
{
   return (FIFO_SIZE + fifo.tail - fifo.head);
}

int32_t n_used(void)
{
   return (fifo.head -fifo.tail);
}

[sangar]

Hi,

Thanks.Yes, The problem arised due to different operand size.Now, FIFO working as we expected. Thank you very much for your support.




Thanks,
Muthu