Electronics > Microcontrollers

Is this Circular Event Buffer thread safe? (STM32G431)

<< < (3/3)

ejeffrey:

--- Quote from: capt bullshot on September 22, 2021, 07:45:25 am ---Looks fine to me. The interrupts don't use the tail pointer, and CPU read access to head pointers should be atomic, so the main will read always a valid variable. Don't forget to declare the pointers modified by the interrupts "volatile", otherwise the compiler might optimise your (Head == Tail) comparison out and you'll get never an input.

--- End quote ---

The entire data structure should be volatile or it could be cached or even optimized away entirely.


--- Quote from: Silicon Wizard ---I personally favor adding an extra member indicating the number of items currently in the queue, instead of comparing Head and Tail. The benefit of this approach is that it makes it easy and fast to determine the current number of items in the queue, but also see if it's full or empty. Without tricks.

A related point is that when using this extra member, only its accesses need to be atomic. You don't need atomic accesses to Head and Tail, as long as there is only one 'thread' writing to the queue and another one reading from it, which is a very common case.

--- End quote ---

One advantage of the head and tail pointers is that each variable is only written from a single context even though it is read from both.  That means you only need atomic load/store which are guaranteed on many platforms simply by using the correct type.  With the size variable you need atomic read-modify-write in the form of increment or decrement operations. 

NorthGuy:

--- Quote from: SiliconWizard on September 22, 2021, 04:57:21 pm ---Another thing I don't quite like with this kind of approach: there is no difference between a queue full and a queue empty condition. Then you may be tempted to work around this with some tricks. It's not pretty and not easy to test and prove correct.

--- End quote ---

It is entirely possible that the buffer cannot overflow by design, in which case you don't need to test for overflows, so his method is perfectly perfect.

I usually maintain head and tail longer than necessary to address the buffer, at least by one bit. This way you can always calculate


--- Code: ---number_of_elements_in_the_buffer = (head - tail);
--- End code ---

and then check if it's full or empty.

When I access the buffer, I just and the tail and head with the mask, e.g.


--- Code: ---value = [tail & MASK];
tail++;
--- End code ---

or


--- Code: ---buffer[head & MASK] = value;
head++;
--- End code ---

assuming the buffer's size is power of 2 (as is the case with all my buffers).

This has added benefit that you can peek on the buffer very easily


--- Code: ---value = buffer[(tail + look_ahead) & MASK];
--- End code ---

without taking the elements out.

Assuming one thread only writes and the other only reads, this is thread safe if head and tail are accessed atomically. For 8-bit CPUs this limits the useful buffer size to 128 bytes, which is typically Ok. For others, never a problem.

syntax333:

--- Quote ---If an interrupt arrives between checking head==tail and entering sleep mode then you have a race condition where the MCU will sleep while there is pending data.  This may turn out OK if you have a periodic timer that wakes up from sleep mode anyway, but otherwise can result in arbitrary delays in processing data.  Disabling interrupts before checking for an empty queue means any subsequent events will leave the interrupt pending bit set and presumably prevent / end sleep mode.  At that time interrupts will be re-enabled and the ISR will fire.

--- End quote ---

Yes that is what I was concerned about. I am going to assume that below code is thread safe(without race condition).
I won't disable/enable interrupts for tail incrementation since only CPU access tail after dispatching event and ISRs access Head.
If I have to post event to event buffer(self event) from main then I disable/enable interrupt for Head pointer and event buffer.


--- Code: ---while(1)
{
    disable_interrupts();
    if(Head != Tail)
    {
         enable_interrupts();
         
         state_machine_dispatch(EventBuffer[Tail]);
         tail = ( tail + 1 ) & BUFFMASK;
    }
    else
    {
      //Low Power Mode
      enable_interrupts();
    }
}

--- End code ---

Thank you everybody for their opinion.

snarkysparky:

Before adding to Que

if(((Head +1) & BUFFMASK) != Tail)
{
    //  Add to que

}
else
{
    loose the message but not the que
}

SiliconWizard:

--- Quote from: ejeffrey on September 22, 2021, 11:29:55 pm ---
--- Quote from: capt bullshot on September 22, 2021, 07:45:25 am ---Looks fine to me. The interrupts don't use the tail pointer, and CPU read access to head pointers should be atomic, so the main will read always a valid variable. Don't forget to declare the pointers modified by the interrupts "volatile", otherwise the compiler might optimise your (Head == Tail) comparison out and you'll get never an input.

--- End quote ---

The entire data structure should be volatile or it could be cached or even optimized away entirely.


--- Quote from: Silicon Wizard ---I personally favor adding an extra member indicating the number of items currently in the queue, instead of comparing Head and Tail. The benefit of this approach is that it makes it easy and fast to determine the current number of items in the queue, but also see if it's full or empty. Without tricks.

A related point is that when using this extra member, only its accesses need to be atomic. You don't need atomic accesses to Head and Tail, as long as there is only one 'thread' writing to the queue and another one reading from it, which is a very common case.

--- End quote ---

One advantage of the head and tail pointers is that each variable is only written from a single context even though it is read from both.  That means you only need atomic load/store which are guaranteed on many platforms simply by using the correct type.  With the size variable you need atomic read-modify-write in the form of increment or decrement operations.

--- End quote ---

Those are all assumptions that depend on the exact target. It's probably even micro-optimizing, while I favor correctness, portability and ease of maintenance. In any case, you can compare the two approaches. Chances are, there won't be much difference in terms of code size and performance. But I still find my approach more portable and easier to get bug-free.

As to your last remark, this is typically done in C11 with the following - assuming 'n' is an atomic type:

atomic_fetch_add(&n, 1); // increment
atomic_fetch_sub(&n, 1); // decrement

Navigation

[0] Message Index

[*] Previous page

There was an error while thanking
Thanking...
Go to full version