Post History

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

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, <b>insufficient memory available for a new device must be dealt with</b>.  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:<ol>

<li>At build time.  This is often known as <i>statically allocated</i> memory.  If you run out of memory, the linker will tell you.

<p><li>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.

<li>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.

</ol>

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 <a href="https://github.com/EmbedInc/dspic">Embed DSPIC GIT repository</a>.  Instead of duplicating the descriptions, here are the header comments from that module documenting the internal structures:

<pre>
;   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.
</pre>

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

<pre>
;   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
;   &lt;proj&gt;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.
</pre>

For more details, see the actual code in <a href="https://github.com/EmbedInc/dspic/blob/master/dymem.ins.dspic">DYMEM.INS.DSPIC</a>.