Re: [avr-gcc-list] generic queue library for AVR GCC?

[Paul Haas]

On Thu, 11 Nov 2004, gouy yann wrote:

> I'm using it with a preemptible multi-tasks kernel of
> my own and I've never notice any problem.

> I have taken care the tests and modifications of the
> number of elements in the fifo to be done in the right
> sequence, up to now it seems sufficient for reading
> and writing characters from the USART or for
> inter-tasks communication.

It would be safe if all 4 of these conditions were true:
   1. only one task calls FIFO_get()
   2. only one task calls FIFO_put()
   3. f->nb++ in FIFO_put() is atomic
   4. f->nb-- in FIFO_get() is atomic

I wrote a little function:
   typedef struct {
     short val;
   } f;
   void incr(f* fp) {
     fp->val++;
   }

and compiled it with avr-gcc -S -O3 -c incr.c
    .global incr
            .type   incr, @function
    incr:
  1.        mov r31,r25
  2.        mov r30,r24
  3.        ld r24,Z
  4.        ldd r25,Z+1
  5.        adiw r24,1
  6.        st Z,r24
  7.        std Z+1,r25
  8.        ret

Imagine that I have one task called plus which calls incr() and another 
task called minus that calls the matching decr() function.  Assume that 
val starts at 2.

If we have the sequence of calls:
function   fp->val
 incr()      3
 decr()      2
 incr()      3

The final value is 3 and everything is cool.  However if incr() is 
interrupted at line 5, right after it finishes the adiw, then we get the 
sequence:
        function         fp->val     r24,r25
first half of  incr()     2           3
        decr()            1 
second half of incr()     3
        incr()            4

Producing a final value of 4 after two calls to incr() and one call to 
decr().

You may not notice a bug like this for a long time.  The window for 
corruption is only 4 instructions long and the exact opposite kind of 
corruption can happen on the decr() side.  If you are lucky, the lost 
increments will cancel out the lost decrements.  Or it will look like line 
noise or lost characters, and you'll blame the serial port.  Very rarely 
will it lead to total failure.

If you're very very carefull and you know what you're doing, you can write 
fifo routines that don't require critical sections as long as only one 
task reads, only one task writes and the fifo has 255 bytes or less. 
Critical sections make it all easier.


> bye.
>   Yann
>
> --- Geoffrey Wossum <address@hidden> a écrit :
> > On Thursday 11 November 2004 1:32 pm, gouy yann
> > wrote:
> >
> > > here is my implementation of a fifo.
> > > I hope this will help you.
> >
> > I took a quick look at these routines.  I noticed
> > that they lack any type of
> > "critical section" around where the queue data and
> > pointers are modified.
> > Calling these routines as-is from an ISR context and
> > from a non-ISR context
> > might result in race conditions and odd,
> > intermittent behavior.
> >
> > Here's my critical section routines.  The enter just
> > pushes the global
> > interrupt state and then disables interrupts, the
> > exit pops the interrupt
> > state.  Observant list readers might note an uncanny
> > resemblance to NutOS's
> > critical section code...
> >
> > extern inline void utos_enter_cs(void)
> > {
> >     asm volatile(
> >         "in  __tmp_reg__, __SREG__" "\n\t"
> >         "push __tmp_reg__"          "\n\t"
> >         "cli"                       "\n\t"
> >     );
> > }
> >
> > extern inline void utos_exit_cs(void)
> > {
> >     asm volatile(
> >         "pop __tmp_reg__"           "\n\t"
> >         "out __SREG__, __tmp_reg__" "\n\t"
> >     );
> > }
> >
> > Since these routines push and pop from the stack,
> > you have to be careful to
> > balance them within a function.  I'll leave where to
> > insert them into the
> > code as an exercise to the reader ;)
> >
> > Maybe lack of critical sections is the problem with
> > the original posters code?
> >
> > ---
> > Geoffrey Wossum
> > Long Range Systems - http://www.pager.net
---
Paul Haas
http://hamjudo.com