Embedded C - memory pool types

The TL;DR is: use the correct tool for the task. Dynamic memory allocation in the context of embedded microcontroller system is indeed pretty much never the correct tool, for a long list of reasons.

Ask yourself what your actual task is - what is the reason you need dynamic memory? If the answer is something like "I need a shared memory pool" or "I don't know the memory required at compile-time", that's the wrong answer - why do you need a shared memory pool, why don't you know the upper limit of what your program is supposed to be doing? Keep asking why until your answer lands in the specific project requirements. Or if it doesn't land there, then either the requirements are insufficient and should be revisited. Or it could turn out that you are doing some meta task unrelated to the actual project, in which case you should abandon it and get back on track.

I believe that the code in the question comes from Static allocation of opaque data types and it's important to understand that context. If you don't have any opaque types simply declare the object as a plain static file scope variable and don't worry about memory pools.

In the specific scenario when you have an opaque type, achieved by forward declaring an incomplete struct, the application code simply cannot allocate an instance of that object since the struct implementation and size is unknown to the application. Therefore you have two options:

• The opaque type class allocates memory for every object of that type internally, through a constructor-like function, or
• The caller allocates memory in some global memory pool by asking the opaque type class how large one object is, through some manner of "get_size()" API.

For simple applications the former is likely preferred as it makes things less complex. The latter is only preferable when you have a lot of opaque types and you want their memory allocated together (for example for data cache reasons).

Notably one has to be aware that these memory pools that work on a character type array do declare an array with "effective uint8_t type". If we let a struct point into such an array and that struct does not have a similar uint8_t array among its members, then dereferencing the struct will explicitly invoke undefined behavior as per "strict aliasing". There are two ways to avoid it: either don't use a struct but a union between the struct type and a uint8_t array of the same size as the struct. Or simply disable strict aliasing optimizations, which were only ever a problem with the gcc compiler specifically - the option is gcc -fno-strict-aliasing.

But one disadvantage is that if I have to "free" memory from processes that have finished using their memory block

This doesn't make sense in embedded MCU systems and where most people considering dynamic allocation go wrong. The scenario "I don't know how much memory I need at compile-time" does not exist. A microcontroller system, or any high reliability system for that matter, must be fully deterministic and there can be no unknowns. From Why should I not use dynamic memory allocation in embedded systems?:

"Saving memory" and freeing doesn't make sense

Calling free() in a single core microcontroller application never makes any sense - there is nobody to share the memory with, our program has complete control of it all. As established earlier, we need to handle the worst case scenario so we need to allocate that exact amount. Freeing up memory when we are not executing the worst case scenario is senseless, because if there are parts of the code which would actually benefit from that extra available memory, that only means that those very same parts will either perform poorly or fail/crash during the worst case scenario, so that would be a design mistake.

Your requirements and application use-cases must cover all situations including the worst-case ones. Your application must work just as fine in the worst-case scenario as in any other scenario, so you know in advance how much memory you need: exactly as much as is necessary for the worst-case scenario. Not more, not less - you need that exact amount. There is nothing "dynamic" about it.

The need for dynamic memory is typically just one big "XY problem". You think you need solution "dynamic memory" to solve problem X, and so you are looking for various alternatives to dynamic memory when it's likely the wrong solution to your original problem to begin with.

So consider: when exactly will any part of your program be "finished" with a memory block and how does that even make sense from your requirements' and program design's point of view? Did you pick a MCU with insufficient RAM for the project requirements or what? All explanations from there on enters the realm of dirty patches and ad hoc solutions, when we have thrown all good programming practices out the window anyway.

If your processes have to wait for each other to finish just because there is too little memory, then clearly you have picked the wrong MCU to host the RTOS. And why are individual processes even mucking around with a chunk of shared memory instead of using their local process stack for it? (Ie the RTOS' equivalent to thread_local.) At this point we need to stop and question what we are even doing, because our program design is apparently all over the place and maybe we've over-engineered the whole project.

What are some other memory pool architectures/types than this arena type?

There are various even more specialized types and which ones that apply might matter if the data is read/write or read-only.

A linked list implemented on top of a static array with array indexes instead of pointers for example, which can be a handy type for implementing queues or even certain wear leveling algorithms.

Hash tables could make sense if you are dealing with large amounts of data and need more or less constant look-up time. These make most sense when the data is read-only. Same with binary trees, expression parsing trees etc etc.

They key is specialized use, just as the memory pool in the question is a container for specialized use.

posted 3 days ago

CC BY-SA 4.0

Lundin‭

10542 reputation 48 146 1227 200

I disagree that dynamic memory allocation in embedded systems is necessarily a bad idea. It can be a useful concept as long as failure is handled properly.

For example, consider a system where various devices can be plugged in and removed during normal operation. Different devices require different amounts of static state to manage at run time. It makes sense to allocate this per-device state when the device is plugged in, and release it when unplugged. However, insufficient memory available for a new device must be dealt with. This could be lighting a "Full" LED or something, but certainly not adding the new device to the list.

If the memory for the maximum number of devices is available, assuming all the largest (in terms of memory needs) type, then you don't need dynamic memory. You can simply partition the available memory for those N worst-case devices. If smaller devices are used, then part of the fixed block for that device is unused.

However, if it is valuable to allow a user to plug in up to, for example, 16 devices that are small, but only 4 of the largest type, then dynamic allocation can make sense.

In general you want to allocate memory in preference order:

1. At build time. This is often known as statically allocated memory. If you run out of memory, the linker will tell you.

2. One-time, usually when the system is initialized. This type of dynamic memory can not be deallocated at run time.

   I've used this where there are many static configuration options stored in non-volatile memory. The firmware is built with modules for all the possible options present. The setup routine for each of these modules is called during system startup. The setup routine checks how/if it is configured according to the data in non-volatile memory, and configures itself accordingly. If a module is enabled according to the non-volatile data, it may do one-time allocation of dynamic memory, launch a task, etc. If it is disabled, it does none of those things and is not called again. If a module is refused dynamic memory that it needs, it signals an error that is handled by the higher level system initialization logic.

   Using this type of memory is suitable when statically allocating the maximum memory for all modules is impossible, but you can be sure that the memory for any legal combination of enabled modules is available.

3. Live run-time dynamic memory that can also be deallocated, and therefore be available for future re-allocation.

   This is the least desirable and the most dangerous, but I don't consider it wrong if you have thought out the consequences carefully and there is a reasonable way to handle the requested memory not being available.

   Note that after deallocation there can be "holes" in the dynamic memory heap. New request may not be able to use memory from the holes because the holes are too small. The heap becomes fragmented. Effectively, not all heap memory is available for new allocation requests, and the system acts as if it has less memory than it actually does.

   Fragmentation is not necessarily wrong, but is a reason you can't just use the full heap size to calculate how much dynamic memory is really available for use. Of course in all cases, failure to get requested memory must be checked for and handled appropriately.

To serve the two run-time cases above (options 2 and 3), I use dynamic memory routines that allow both permanent and temporary allocation. Such routines for Microchip dsPIC 16 bit microcontrollers are in the DYMEM.INS.DSPIC file in the Embed DSPIC GIT repository. Instead of duplicating the descriptions, here are the header comments from that module documenting the internal structures:

;   Dymanic memory management.  See the header comments in QQQ_DYMEM.INS.DSPIC
;   for the application interface.
;
;   Internal data structure
;
;     The heap is divided into two regions: the permanent pool, and the
;     temporary pool.
;
;     Permanently allocated memory is always taken from the start of the
;     permanent pool.  The start and size of this region are adjusted as each
;     permanent chunk is allocated.  No information is kept on the location and
;     size of individual permanent chunks.  Once a permanent chunk is allocated,
;     its memory is effectively no longer part of the heap, and specific
;     information about the chunk is lost.
;
;     Two local variables are used to describe the permanent pool:
;
;       PERMSTART  -  Start address of the permanent pool.  Always even.
;
;       PERMLEN  -  Length in bytes of the permanent pool.  Always even.
;
;     The temporary pool starts with the first (lowest address) temporarily
;     allocated block, and extends to the end of the heap.
;
;     All the temporarily allocated chunks of memory are tracked in a linked
;     list.  A control entry is allocated immediately preceeding each caller
;     visible chunk.
;
;     To reduce confusion, the following terms are used in this module:
;
;       CHUNK  -  Memory that has been allocated from the heap that is visible
;         to the application.
;
;       BLOCK  -  All the memory used on the heap for a particular chunk.
;
;       CONTROL ENTRY  -  The additional memory allocated on behalf of a
;         temporary chunk beyond that which is visible to the application.
;
;     Permanent blocks have no control entries, so a permanent block is the same
;     as its permanent chunk.  Temporary blocks are comprised of a control entry
;     and its chunk.
;
;     The words of a control entry are:
;
;       Adr + 0  -  Size of this chunk.  This is the caller-visible size, and
;         therefore does not include the control entry for this block.
;
;       Adr + 2  -  Address of the control entry for the next block.  Control
;         entries are linked in ascending address order.  The first control
;         entry is pointed to by the local variable TEMPADR.  TEMPADR is 0 when
;         no temporary memory has been allocated.  This word at Adr+2 being zero
;         indicates the end of the linked list.
;
;   Permanent memory allocation
;
;     Permanent memory is allocated from the start of the permanent pool.  When
;     a chunk is allocated, the start of the permanent pool is moved to
;     immediately after the new chunk, and the length of the permanent region is
;     lowered by the size of the new chunk.  This incurs no overhead, but also
;     keeps no record of permanently allocated chunks.
;
;   Temporary memory allocation
;
;     Temporary memory is allocated from the smallest available region that is
;     large enough to hold the new block.  Note that the available size must
;     include the 2 word overhead for the control entry.
;
;     After multiple temporary allocations and deallocations, it is possible for
;     unused gaps to be between allocated blocks.  The size of these gaps are
;     checked.  The smallest gap that is large enough for the new block is used.
;     If there are multiple such gaps of the same size, then the gap at the
;     highest address is used.
;
;     If there is no gap that is large enough, then the new memory is allocated
;     from the permanent pool.  The size of the permanent pool is decreased
;     accordingly.  When the first (lowest address) temporary block is
;     deallocated, its memory is returned to the permanent pool.
;
;     The new block is always taken from the end (high addresses) of whatever
;     region it is allocated from.

And here are the header comments of QQQ_DYMEM.INS.DSPIC referred to above:

;   Dynamic memory management.  This module allocates memory from a "heap".
;
;   The heap managed here is different from the native heap created by the
;   Microchip assembler and linker.  The Microchip heap has to be configured to
;   a fixed size.  There is no provision to have it occupy all remaining unused
;   memory.
;
;   However, the Microchip tools can be configured to allocate all remaining
;   memory to the stack.  This module uses that mechanism to identify the unused
;   memory.  The stack is reserved from the start of this memory, then the
;   remainder used as the heap.  The preprocessor constant MINSTACK0 must be set
;   to the minimum required stack size in bytes.  This is usually done in the
;   <proj>lib.ins.dspic file.  See the qqqlib.ins.dspic template.
;
;   These routines support two types of dynamic memory allocation, permanent and
;   temporary.  Permanently allocated memory can not be deallocated.  Its
;   advantage is that there is no overhead.  Temporarily allocated memory can
;   be deallocated at a later time.  This requires additional state to keep
;   track of allocated regions so that they can be deallocated.
;
;   In this implementation, permanent memory is allocated from the start of the
;   heap.  Temporary memory is allocated from the end of the smallest available
;   region that is large enough.  When there is no fragmentation, this means
;   temporary memory is allocated from the end (high addresses) of the heap.
;
;   The DYMEM routines do not interact with or reference the Microchip heap.
;   The two can be used independently.
;
;   Exported routines:
;
;     DYMEM_INIT
;
;       One-time module initialization.  Must be first call.  W0 is the address
;       of the start of the heap, and W1 the address of the last word of the
;       heap.
;
;     DYMEM_ALLOC_PERM
;
;       Permanently allocate dynamic memory.
;
;       The number of requested bytes is passed in W0.  W0 is returned the
;       address of the first byte of the new region.  Memory is always allocated
;       in whole 16 bit words.  W0 will therefore always be returned even.
;
;       When there is insufficient space on the heap, W0 is returned 0 and the Z
;       flag is set.  When the memory is allocated, W0 will be non-zero and the
;       Z flag cleared.
;
;     DYMEM_ALLOC_TEMP
;
;       Allocate dynamic memory that can later be de-allocated (returned to the
;       heap).
;
;       The number of requested bytes is passed in W0.  W0 is returned the
;       address of the first byte of the new region.  Memory is always allocated
;       in whole 16 bit words.  W0 will therefore always be returned even.
;
;       When there is insufficient space on the heap, W0 is returned 0 and the Z
;       flag is set.  When the memory is allocated, W0 will be non-zero and the
;       Z flag cleared.
;
;     DYMEM_DEALLOC
;
;       Deallocate a block of temporarily-allocated dynamic memory.  W0 is the
;       address of any byte within the block.  Nothing is done if W0 is not a
;       address somewhere inside a temporarily-allocated block of dynamic
;       memory.
;
;     DYMEM_RESET
;
;       Reset the dynamic memory system to the state it was in immediately after
;       initialization.  All dynamically allocated memory, both temporary and
;       permanent, will be deallocated.  Any pointers to dynamically allocated
;       memory must be considered invalid.  The full original heap will again be
;       available for new allocations.
;
;     DYMEM_SEND
;
;       Send a series of DYMEM responses indicating the current state of the
;       dynamic memory.  This routine only exists when the RSP_DYMEM constant
;       exists.
;
;   Commands:
;
;     DYMEM
;
;       Causes a set of DYMEM responses to be sent indicating the current state
;       of the dynamic memory.  Both this command and the DYMEM response must be
;       enabled for this command to exist.
;
;   Responses:
;
;     DYMEM: id [dat ... dat]
;
;       Provides a piece of information about the current state of the dynamic
;       memory.  ID identifies the specific information.  The data following ID,
;       if any, is dependent on ID.
;
;       A series of these responses are sent together, providing the complete
;       information on the current state of the heap.  The responses are sent in
;       order of ascending ID, starting with 1.  The last response is always ID
;       0.
;
;       The various ID values with their following data are:
;
;         0
;
;           End of dynamic memory info.  This is the last response of a set of
;           DYMEM responses.
;
;         1: adr len
;
;           Location and size of the whole heap as originally defined.  ADR and
;           LEN are 16 bits.
;
;         2: adr len
;
;           ADR is the start address and LEN the length of the part of the heap
;           that dynamic memory can be permanently allocated from.  ADR and LEN
;           are 16 bits.
;
;         3: adr len
;
;           Start address and length of a temporarily allocated block of memory.
;           ADR and LEN are 16 bits.  The block indicated by ADR and LEN is the
;           actual memory available to the application.  It does not include the
;           internal overhead for tracking the location of all
;           temporarily-allocated blocks.  One of these responses is sent for
;           each temporarily-allocated block.

For more details, see the actual code in DYMEM.INS.DSPIC.

posted 6 days ago

CC BY-SA 4.0

Olin Lathrop‭

1407 reputation 1 41 111 17