Concurrency in a bare metal environment

[JPortici]

Yesterday i was updating an old library because a problem emerged with a FIFO, as data was being lost because it was something i wrote years ago when i did things with more ingenuity.
The usual scenario:
-Single core MCU, not running an RTOS
-Interrupt happens when there is more data to be processed (a new byte on UART, a new CAN Frame, a new word from the ADC or maybe the DMA has finished its block transfer)
-Data is then put on a circular buffer, indexes and flags updated
-The appropriate function in the superloop get data from the circular buffer, indexes and flags are updated, data is processed

And my goto circular buffer

Code: [Select]

#define BUF_SIZE SOMENUMBER

typedef struct {
  type_t buf[BUFSIZE];
  int rdIdx;
  int wrIdx;
  bool isFull;
  bool isEmpty;
} cBuf_t

void cBuf_init(cBuf_t *cBuf) {
  int idx;
  for (idx=0;idx<BUF_SIZE;idx++ {
    cBuf->buf[idx] = 0;   //Or the appropriate empty entry
  }
  cBuf->rdIdx = 0;
  cBuf->wrIdx = 0;
  cBuf->isFull = false;
  cBuf->isEmpty = true;
}
bool cBuf_push(cBuf_t *cBuf, type_t data) {
  if (!cBuf->isFull) {
    cBuf->isEmpty = false;
    cBuf->buf[cBuf->wrIdx] = data;
    cBuf->wrIdx = (cBuf->wrIdx + 1) % BUF_SIZE;
    if (cBuf->wrIdx == cBuf->rdIdx) {
      cBuf->isFull = true;
    }
    return true;
  }
  else {
    return false;
  }
}
type_t cBuf_pop(cBuf_t *cBuf, bool *success) {
  type_t data = 0;        //Or the appropriate empty entry
  if (!cBuf->isEmpty) {
    cBuf->isFull = false;
    data = cBuf->buf[cBuf->rdIdx];
    cBuf->rdIdx = (cBuf->rdIdx + 1) % BUF_SIZE;
    if (cBuf->rdIdx == cBuf->wrIdx) {
      cBuf->isEmpty = true;
    }
    *success = true;
  }
  else {
    *success = false;
  }
  return data;
}
In this case i'm using a generic type_t so we can't make assumptions on atomicity of read from/write to buffer. It could even be a pointer to heap space.

In any case,
Usually either push or pop happen inside an interrupt, the other in the superloop context. In this case what i do is disable the related interrupt flag during access.
But i'm trying to understand if there is a better approach. Well, this looks as good as it can be in a bare metal environment but maybe something more generic.
What i would really like to do is not having to disable interrupt/run/enable interrupt, in order to mantain the code more processor independent, but i don't know if it's actually possible.
the clear/set interrupt enable could become a macro that needs to be defined somewhere in the hardware abstraction layer but it's really the same thing, i wonder if there is actually a different solution.

[Nominal Animal]

In general, you only need to manipulate the indexes atomically.

If you use GCC, you can use the atomic built-in functions, volatile, and asm volatile ("" : : : "memory"); as a generic write memory barrier (on most hardware architectures).  For example, a completely generic interruptible single-producer, single-producer circular buffer in GNU C:

Code: [Select]

#include <stdbool.h>
#include <string.h>

typedef struct {
    volatile char *volatile  head;   /* Read pointer */
    volatile char *volatile  tail;   /* Write pointer */
    unsigned int             unit;   /* Size of each data unit */
    volatile char           *data;   /* Start of data buffer */
    volatile char           *ends;   /* Just past the end of the data buffer */
} cbuffer;

bool cbuffer_get(cbuffer *cb, void *to)
{
    volatile char *const  data = cb->data;
    volatile char *const  ends = cb->ends;
    const unsigned int    unit = cb->unit;

    volatile char *const  head = __atomic_load_n((char **)&(cb->head), __ATOMIC_SEQ_CST);
    volatile char *const  next = (head + unit < ends) ? head + unit : data;

    /* Empty? */
    if (head == __atomic_load_n((char **)&(cb->tail), __ATOMIC_SEQ_CST))
        return false;

    memmove(to, (void *)head, unit);
    asm volatile ("" : : : "memory"); /* Write memory barrier */

    __atomic_store((char **)&(cb->head), (char **)&next, __ATOMIC_SEQ_CST);
    return true;
}

bool cbuffer_put(cbuffer *cb, const void *from)
{
    volatile char *const  data = cb->data;
    volatile char *const  ends = cb->ends;
    const unsigned int    unit = cb->unit;

    volatile char *const  tail = __atomic_load_n((char **)&(cb->tail), __ATOMIC_SEQ_CST);
    volatile char *const  next = (tail + unit < ends) ? tail + unit : data;

    /* Full? */
    if (next == __atomic_load_n((char **)&(cb->head), __ATOMIC_SEQ_CST))
        return false;

    memmove((void *)tail, from, unit);
    asm volatile ("" : : : "memory"); /* Write memory barrier */

    __atomic_store((char **)&(cb->tail), (char **)&next, __ATOMIC_SEQ_CST);
    return true;
}
This uses the standard "never completely full" semantics, so that there is always at least one unused element in the circular buffer.

The purpose of the write memory barrier is to ensure the data copy occurs before the index is updated.  I do believe a volatile assignment suffices on all single-core hardware architectures.

Neither cbuffer_get() nor cbuffer_put() ever blocks, and they both may be interrupted by the other; just not nested.

[snarkysparky]

Nominal.   Just a quick question.

I recently codes a very similar situation.   I declared the struct as volatile.

Should that ensure that all the elements are considered volatile or do I need to individually tag them.

Sorry for the hijack but it seems relevant.

[JPortici]

In my case the compiler is GCC but C11 is not supported
I'll look into that implementation

[SiliconWizard]

Usually either push or pop happen inside an interrupt, the other in the superloop context. In this case what i do is disable the related interrupt flag during access.

That's something I've done a lot on MCUs. It just works.

Other methods may or may not be available depending on the MCU/CPU you're targetting. Some have atomic access in their instruction set, others do not. Some also have more complex memory controllers than others, with caches and all sorts of nice stuff that can become very nasty in those situations.

For a "generic" approach, you may indeed take a look at C11. Which GCC version are you using? I think C11 has been supported in GCC for literally years now, and an already significant number of major versions! But that said, even if your compiler supported C11, I think stdatomic is optional in the standard, so it's not guaranteed to be available depending on the platform. And for targets not having native atomic instructions, it's likely it's not going to be available. So I'm afraid I don't know of a really "generic" approach, but if I'm using C, I would favor using C11 stdatomic when available, and ad-hoc solutions when it's not.

[rstofer]

Briefly disabling interrupts in the super loop works with every compiler on every platform and probably in every language.  Portability should weigh into the decision at some point.

[Nominal Animal]

I declared the struct as volatile.

That should be equivalent to declaring each member volatile, yes.

In my case the compiler is GCC but C11 is not supported

Those are GCC atomic built-ins, provided by GCC regardless of the C or C++ standard used.  They are available regardless.  The only reason C++11 is mentioned is that the way they are defined is compatible with C++11, that's all.

There is an even older set of __sync built-ins, which have even better semantics in a microcontroller environment: GCC implements them as a full barrier, so the write barrier I used above is not necessary.

On architectures where loads and stores of native sizes are atomic (so essentially all microcontrollers!), __atomic_load(), __atomic_load_n(), __atomic_store(), and __atomic_store_n() compile to ordinary loads and stores.  GCC does not generate "superfluous synchronization primitives" in such cases.

[JPortici]

Ah, the current target is XC16, which IIRC is GCC 4.something, but don't mind the compiler version too much.
on dsPIC load/store is atomic regardless of the size (even if it has a 16 bit data bus, the 32bit MOV.D is not interruptible)

[Nominal Animal]

Ah, the current target is XC16, which IIRC is GCC 4.something, but don't mind the compiler version too much.
on dsPIC load/store is atomic regardless of the size (even if it has a 16 bit data bus, the 32bit MOV.D is not interruptible)

In that case, you don't need to use the builtins at all, just make sure that the accesses to the indexes/pointers and the data are volatile.

(The data access being volatile is not to try and make it atomic, but to make sure the compiler does not reorder it with respect to the index/pointer update.  Because it is a straightforward copy, and the only access and reference to the data, it has no side effects.)

So, the polymorphic C header file for a circular buffer using index variables (as opposed to pointers) would be

Code: [Select]

/* SPDX-License-Identifier: CC0-1.0
   Before including this header file, define:
        TYPE    as the circular buffer type name
        DTYPE   as the buffer element data type
        COUNT   as the number of elements in the buffer
        ITYPE   as the buffer index type
   and optionally some/all of
        INIT    as the buffer initialization function name
        GET     as the dequeue function name
        PUT     as the enqueue function name
        EMPTY   as the name of a function that checks if the buffer is empty
        FULL    as the name of a function that checks if the buffer is full
   These will be undefined after the include.
*/
typedef struct {
    volatile ITYPE  head;           /* Read index */
    volatile ITYPE  tail;           /* Write index */
    volatile DTYPE  data[COUNT];    /* Can be a pointer, no changes needed */
} TYPE;

#ifdef INIT
static inline void INIT(TYPE *const cb)
{
    cb->head = 0;
    cb->tail = 0;
}
#undef INIT
#endif

#ifdef GET
static inline bool GET(TYPE *const cb, DTYPE *const to)
{
    const ITYPE  head = cb->head;
    if (head == cb->tail)
        return false;
    const ITYPE  next = (head + 1 < COUNT) ? head + 1 : 0;
    *(volatile DTYPE *)to = *(volatile DTYPE *)(cb->data + head);
    cb->head = next;
    return true;
}
#undef GET
#endif

#ifdef PUT
static inline bool PUT(TYPE *const cb, DTYPE *const from)
{
    const ITYPE  tail = cb->tail;
    const ITYPE  next = (tail + 1 < COUNT) ? tail + 1 : 0;
    if (next == cb->head)
        return false;
    *(volatile DTYPE *)(cb->data + head) = *(volatile DTYPE *)from;
    cb->tail = next;
    return true;
}
#undef PUT
#endif

#ifdef EMPTY
static inline bool EMPTY(TYPE *const cb)
{
    return (cb->head == cb->tail);
}
#undef EMPTY
#endif

#ifdef FULL
static inline bool FULL(TYPE *const cb)
{
    const ITYPE  tail = cb->tail;
    const ITYPE  next = (tail + 1 < COUNT) ? tail + 1 : 0;
    return (next == cb->head);
}
#undef FULL
#endif

#undef ITYPE
#undef COUNT
#undef DTYPE
#undef TYPE
or, using pointers instead of indexes,

Code: [Select]

/* SPDX-License-Identifier: CC0-1.0
   Before including this header file, define:
        TYPE    as the circular buffer type name
        DTYPE   as the buffer element data type
        COUNT   as the number of elements in the buffer
   and optionally some/all of
        INIT    as the buffer initialization function name
        GET     as the dequeue function name
        PUT     as the enqueue function name
        EMPTY   as the name of a function that checks if the buffer is empty
        FULL    as the name of a function that checks if the buffer is full
   These will be undefined after the include.
*/
typedef struct {
    volatile DTYPE *head;           /* Read index */
    volatile DTYPE *tail;           /* Write index */
    volatile DTYPE *data;           /* Start of the buffer */
    volatile DTYPE *ends;           /* Just past the end of the buffer */
} TYPE;

#ifdef INIT
static inline void INIT(TYPE *const cb, DTYPE *const data, const size_t size)
{
    cb->head = data;
    cb->tail = data;
    cb->data = data;
    cb->ends = data + size;
}
#undef INIT
#endif

#ifdef GET
static inline bool GET(TYPE *const cb, DTYPE *const to)
{
    volatile DTYPE *const  head = cb->head;
    if (head == cb->tail)
        return false;
    *(volatile DTYPE *)to = *head;
    cb->head = (head + 1 < cb->ends) ? head + 1 : cb->data;
    return true;
}
#undef GET
#endif

#ifdef PUT
static inline bool PUT(TYPE *const cb, DTYPE *const from)
{
    volatile DTYPE *const  tail = cb->tail;
    volatile DTYPE *const  next = (tail + 1 < cb->ends) ? tail + 1 : cb->data;
    if (next == cb->head)
        return false;
    *tail = *(volatile DTYPE *)from;
    cb->tail = next;
    return true;
}
#undef PUT
#endif

#ifdef EMPTY
static inline bool EMPTY(TYPE *const cb)
{
    return (cb->head == cb->tail);
}
#undef EMPTY
#endif

#ifdef FULL
static inline bool FULL(TYPE *const cb)
{
    volatile DTYPE *const  tail = cb->tail;
    volatile DTYPE *const  next = (tail + 1 < cb->ends) ? tail + 1 : cb->data;
    return (next == cb->head);
}
#undef FULL
#endif

#undef COUNT
#undef DTYPE
#undef TYPE
If the above are named cbi.h and cbp.h, I would be very interested to see what -Os -Wall -march=yourArch -S emits for the following:

Code: [Select]

#include <stdbool.h>
#define  static  /* nothing */
#define  inline  /* nothing */

#define  TYPE   cbi
#define  DTYPE  char
#define  ITYPE  int
#define  COUNT  200
#define  INIT   cbi_init
#define  GET    cbi_get
#define  PUT    cbi_put
#include "cbi.h"

#define  TYPE   cbp
#define  DTYPE  char
#define  COUNT  200
#define  INIT   cbp_init
#define  GET    cbp_get
#define  PUT    cbp_put
#include "cbp.h"
generates.  (The -S flags means the assembly output is saved in a .s file, which is what I'd love to see.)

Both of these implementations assume volatile stores to cb->head and cb->tail are uninterruptible.  It's just that some instruction sets generate better code when indexes are used, and others when pointers are used; I'm just overly nosy to see which one dsPIC falls into.

[SiliconWizard]

Ah, the current target is XC16, which IIRC is GCC 4.something, but don't mind the compiler version too much.

That would explain it. If I'm not mistaken, C11 has been well supported and default since v.6.x? And GCC is now at 10.2.

GCC 4.x? Yeah. Haven't worked with XC16 in a few years now, but apparently Microchip has never gone past GCC 4.5.x for XC16. I dunno what's their intention there. Anyway, as I said, even with the latest GCC, I think stdatomic may not be guaranteed to be provided.

And yes, depending on what it is exactly you need to guard against concurrent access, you may not need to do anything. For instance, if you just need to guard some index increment/decrement and this operation is natively atomic, there is nothing to be done. But often you'll need to guard several consecutive instructions, in which case you need to implement some kind of mutex (selectively disabling interrupts here being one simple way of doing it.) For instance, if you're implementing a circular buffer, then the index increment also needs to roll over. If the buffer size is a power of two, then it just requires a mask (AND operation.) I don't know or don't remember if those PICs have instructions to atomically do both an increment and a mask for circular buffer indexing. If so and this operation is atomic, then again you wouldn't necessarily need to implement any guarding. That said, if you're strictly programming in C or C++, I would be wary of counting on the compiler using any exotic instruction by itself, or it could depend on optimization level, so that's not good.

All in all, unless again you have access to C11 and stdatomic is implemented on a given platform, you're pretty much on your own for atomic operations. You may try and use some compiler built-ins if available, but that wouldn't be very generic either.

IMHO, if you really want something generic here, I think some generic implementation of simple mutexes would fit the bill. You can implement that with functions or macros and make the platform-dependent implementation through conditional compilation. If you want something already made and tested, and supporting a decent range of targets, you may consider extracting the relevant part (only the minimum required for concurrent access) from some open RTOS.

[coppice]

Ah, the current target is XC16, which IIRC is GCC 4.something, but don't mind the compiler version too much.
on dsPIC load/store is atomic regardless of the size (even if it has a 16 bit data bus, the 32bit MOV.D is not interruptible)

GCC 4 is a strange version to stick with. GCC 3.3 and 3.4 gave good results with small CPUs, like the AVR and MSP430. The generated code quality went badly downhill with GCC 4, as they focussed on complex pipelined and cached CPUs. I think more recent versions have recovered a lot of that lost ground.

[JPortici]

There was a post somewhere in the microchip by a guy forums from the 16bit team that explained why they sticked to GCC 4.5.2. I can't find it, but it was essentially "we tested newer GCC but code quality was worse"
the latest mention from the devs i could find is something like "this version of GCC works fine for us so we have no reason to update"
I don't say i disagree with them, given that it's more or less the only compiler for dsPIC and it has a number of custom extensions (for memory space, codeguard and such) i prefer they concentrate on device support, code quality and documentation, almost all of which i am really, really happy with.

(The -S flags means the assembly output is saved in a .s file, which is what I'd love to see.)

Both of these implementations assume volatile stores to cb->head and cb->tail are uninterruptible.  It's just that some instruction sets generate better code when indexes are used, and others when pointers are used; I'm just overly nosy to see which one dsPIC falls into.

will try to make some time one of these evenings (i've already had to move on to something else

[DiTBho]

My professional approach here can be questioned, but for critical code sections I only write assembly in order to avoid to deal with the C compiler's change of circumstances or fortune.

Quite a bit extreme, and it depends on the ABI, but it's what I do in these cases rather than having to fight with the inner details and mysteries of a family of compilers.

[tggzzz]

My professional approach here can be questioned, but for critical code sections I only write assembly in order to avoid to deal with the C compiler's change of circumstances or fortune.

Quite a bit extreme, and it depends on the ABI, but it's what I do in these cases rather than having to fight with the inner details and mysteries of a family of compilers.

I don't disagree, and I'll note it has the benefit of strongly encouraging you to keep critical sections small

[julian1]

I am trying to understand the initial problem,

In the interrupt handler - one will not get the same interrupt again - if the enable flag is left unenabled in the handler until after the circular buffer is updated. So writing the value at the write_index and incrementing the write_index does not need to be done in a critical section/mutex protected, and ordering does not matter - since there is no other interrupt handler enabled that could trample over the same memory.

In the superloop, one is dealing only with read_index and read value, which are separate memory locations (in all but one case), so interrupts in this context don't matter. I don't see that it even matters to disable the write interrupt in the superloop code, when reading/consuming the circular buffer.

The exception to this is if the circular buffer overflows and read_index == write_index.  In this case all bets are off. But, data is going to be lost anyway, so the best one can do is detect the condition and raise a flag - and then let higher level logic deal with it.

Alternatively the buffer should be increased and super loop max time limited, so that any sequence of interrupts can be handled. This avoids the write and read indexes ever pointing to same location. 

Is there a case where this approach fails?

[SiliconWizard]

There was a post somewhere in the microchip by a guy forums from the 16bit team that explained why they sticked to GCC 4.5.2. I can't find it, but it was essentially "we tested newer GCC but code quality was worse"
the latest mention from the devs i could find is something like "this version of GCC works fine for us so we have no reason to update"

Yeah. We could use that argument to never update anything. GCC is at v. 10.2 now, that's 6 major versions behind. They may have had little incentive to update to GCC 5.x or 6.x (except that they are missing on newer features and, most of all, support for newer revisions of the C std...), but come on.

From XC16's history and what I gathered, I suspect updating their target code to a newer GCC version is difficult, and they just don't want to bother. As long as customers don't complain, that just means Microchip has put almost zero effort on XC16  for years now. That looks like a good deal from a business POV.

[JPortici]

From XC16's history and what I gathered, I suspect updating their target code to a newer GCC version is difficult, and they just don't want to bother. As long as customers don't complain, that just means Microchip has put almost zero effort on XC16  for years now. That looks like a good deal from a business POV.

Pretty much, yeah. Last major update was adding the support for the dsPIC33C, the new instructions and dual core support

[coppice]

From XC16's history and what I gathered, I suspect updating their target code to a newer GCC version is difficult, and they just don't want to bother. As long as customers don't complain, that just means Microchip has put almost zero effort on XC16  for years now. That looks like a good deal from a business POV.

Pretty much, yeah. Last major update was adding the support for the dsPIC33C, the new instructions and dual core support

Supporting newer versions of GCC isn't too much work. Its gdb that makes the real work. Target support for an old version of gdb needs more or less a 100% rewrite for a modern gdb.

[SiliconWizard]

From XC16's history and what I gathered, I suspect updating their target code to a newer GCC version is difficult, and they just don't want to bother. As long as customers don't complain, that just means Microchip has put almost zero effort on XC16  for years now. That looks like a good deal from a business POV.

Pretty much, yeah. Last major update was adding the support for the dsPIC33C, the new instructions and dual core support

Supporting newer versions of GCC isn't too much work.

You're probably underestimating the changes in GCC from version 4 to current versions. A lot of things, including some pretty deep stuff, so I'd expect this to be significant work indeed. You're likely also underestimating the relative mess Microchip's code for this target is. And lastly, supporting a 16-bit target in general with GCC is already not that trivial.

I remember a similar discussion on this forum a while ago. I don't remember if you were in it, but a couple people were also claiming how easy building XC16 from source was (which IMHE is already pretty horrible), and how easy it would be to port it to newer GCC versions. If it really is, please have at it. I'm sure many people would be interested in having, not just an XC16 compiler based on a recent GCC version, but a compiler built from source with no license checking. I for one do not know of something like this. I remember we also talked about licenses, but apparently we didn't find anything that would prevent anyone from distributing binaries compiled from source, as this is, well, open source. Even on current Linux distributions, packages for XC16 are binaries from Microchip as far as I've seen... and that's the kind of context where maintainers favor building their distributed binaries from source rather than using third-party binaries every time it's at all possible, either technically or from a license POV. Or maybe here there is some license trick Microchip pulled off that would make this risky?

Anyway, I'm not saying it's impossible, just that it looks difficult. And if anyone is ready to take the challenge, I'm sure this would make many people happy. And possibly give Microchip a lesson along the way. So... anyone?

[coppice]

Supporting newer versions of GCC isn't too much work.

You're probably underestimating the changes in GCC from version 4 to current versions. A lot of things, including some pretty deep stuff, so I'd expect this to be significant work indeed. You're likely also underestimating the relative mess Microchip's code for this target is. And lastly, supporting a 16-bit target in general with GCC is already not that trivial.

If the GCC changes trouble you, I can assure you the GDB changes will be really depressing. Been there. Done that.

[SiliconWizard]

Supporting newer versions of GCC isn't too much work.

You're probably underestimating the changes in GCC from version 4 to current versions. A lot of things, including some pretty deep stuff, so I'd expect this to be significant work indeed. You're likely also underestimating the relative mess Microchip's code for this target is. And lastly, supporting a 16-bit target in general with GCC is already not that trivial.

If the GCC changes trouble you, I can assure you the GDB changes will be really depressing. Been there. Done that.

I do not doubt that! GDB seems to have grown to some monster...

[JPortici]

I remember a similar discussion on this forum a while ago. I don't remember if you were in it, but a couple people were also claiming how easy building XC16 from source was (which IMHE is already pretty horrible), and how easy it would be to port it to newer GCC versions.

which one  ? at least twice a year let it be here on in the microchip forum there is a new thread from yet another RMS paladin who says he's going to show everybody, because paying for optimizations is wrong* never coming back with results.
The most i've seen is the (old) github repo from a guy who compiled g++ for dsPIC (would love to have c++ for it) but i think he abandoned after being able to compile a simple hello world

*i agree but i partly understand the reasoning behind paying for support, other than -O3 and -Os, otherwise beancounters would see the compiler team as an expense that must be cut. Luckily we have most optimizations for free