The Synchronous Blog

A blog about reactive programming languages.

Dynamic Memory Management in Embedded Systems

with 4 comments

Dynamic functionality in embedded systems is usually discouraged due to resource constraints.
However, some types of applications inherently require memory allocation.

As an example, protocols in sensor networks typically forward messages through nodes at a non-deterministic rate, given that the number of neighbors and transmission periods can vary.
Hence, many protocols require dynamic memory management to hold receiving messages until they are successfully forwarded.

A simple FIFO queue might not be always optimal because forwarding a message may involve multiple steps with delays (e.g. transmission acknowledgments).
In such scenario, the protocol would rather handle multiple messages at the same time, raising the possibility of a message received later be discarded first.

Unfortunately, out-of-the-box dynamic memory schemes, such as malloc/free, are not suitable for embedded systems which have quite different requirements in comparison to standard desktop systems.

Follows a list of issues concerning memory management schemes in embedded systems:

  1. Memory corruption
    Many embedded systems lack memory protection, and continuous allocations in the heap may end up corrupting the stack (and vice versa).
  2. Run-time overhead
    Memory management requires extra run-time bookkeeping. Also, in the context of embedded systems, a predictable execution model can be even more important than the fastest scheme on the average.
  3. Metadata overhead
    Metadata used by the memory manager can spend precious bytes (e.g. linked lists of free blocks).
  4. Memory fragmentation
    For constrained memory platforms, unusable holes between and inside allocated blocks (external and internal fragmentation, respectively) can waste a big percentage of available memory.
  5. Unreproducible execution
    Successive executions of the same program may allocate memory in different ways, possibly leading to different outcomes (e.g. an allocation fail).
  6. Deallocation hazards
    Properly deallocating memory is far from trivial. A missed deallocation leads to a memory leak that wastes memory, while deallocating a memory block still in use leads to a dangling pointer that will eventually crash the application.

As the C standard is loose about these issues, out-of-the-box malloc/free can perform bad in all items.
Furthermore, deallocation hazards are inherent in schemes that require an explicit free operation.

Garbage collected systems eliminate deallocation hazards, but may incur unacceptable run-time overheads.

Memory Pools

Embedded systems usually rely on memory pools to manage dynamic memory.
In the context of sensor networks, both TinyOS and Coniki OSes offer and promote the use of memory pools (through Pool and MEMB, respectively).

A memory pool allocates N predefined fixed-sized blocks of memory that can be used by the application.
Most of the raised concerns are alleviated with this scheme:

  1. Because the allocation is static, the maximum amount of memory is known at compile time, reducing considerably the risk of memory corruption.
  2. The run-time overhead is minimal as implementations use simple arrays to hold the memory blocks. For instance, in the TinyOS implementation both allocation and deallocation are O(1).
  3. TinyOS’ Pools use an auxiliary vector of size N to hold pointers for free blocks.
  4. Regardless of different allocation patterns in applications, memory pools will always guarantee the minimal N of memory blocks. Hence, external fragmentation is non-existent. Internal fragmentation, however, can be an issue and is discussed below.
  5. Given that the memory operations are simple and handle fixed-size blocks, the execution is always deterministic and predictable.
  6. Memory pools are still manipulated through malloc/free-like operations. Hence, all challenges to properly deallocate memory still hold.

Internal fragmentation occurs when an allocated memory block is bigger than the requested size.
Given that memory pools can only handle fixed-size blocks, any allocation that requests smaller blocks will contain internal fragmentation (allocation of bigger blocks always fail).
That said, embedded applications are usually simple and contain only one or two different object units that require dynamic allocation.
This way, an application will use a different memory pool for each kind of object, thus also eliminating internal fragmentation.


Memory pools are the way to go for dynamic allocation in embedded systems.

They offer memory compactness, efficient and small operations, and predictable execution.

However, programming dynamic applications is still hard and error prone, given that missing and wrong deallocations may lead to memory leaks and subtle crashes.

In the next post I will show how Céu offers safer and higher level mechanisms for dynamic applications, while using memory pools transparently under the hoods.


Written by francisco

May 20, 2013 at 7:45 pm

4 Responses

Subscribe to comments with RSS.

  1. I absolutely LOVED this article when I was doing research for memory managers.

    It is also what convinced me that I have to roll my own. I am nearly to the Alpha stages of an embedded memory manager that does memory re-use and defragmentation. It does this by using pointer indirection. Take a look!


    April 16, 2015 at 1:41 am

    • Hi Garret, thanks for your comment.
      How does tinymem differ from MEMB?
      As far as I remember, MEMB also uses one level of indirection to avoid fragmentation.


      April 16, 2015 at 9:29 am

      • The major difference (and it is a pretty big one) is that memb requires that “All objects allocated through the same struct memb have the same size”. Tinymem does not have this requirement and is completely dynamic.

        You might be thinking of mmem, which does use pointer indirection and is similar. They are very similar, both in theory and implementation. The difference is in features:
        – mmem does a “full defragmentation” after every mmem_free is called. This means that the entire memory space is moved to the left and then all pointers are updated. This makes free operations VERY expensive. tinymem only does this when necessary (keeping track of free space to use later), and will be doing it in a threading architecture, allowing system critical applications to run beside it.
        – mmem allocates directly off it’s heap, tinymem re-uses freed memory (preventing full defragmentation from being required)
        – tinymem has the resources to continue to develop faster defragmentation methods than moving the entire memory block, as well as support threading and (possibly) interrupts
        – tinymem has implemented many unit tests to ensure it’s functionality and continued development. I couldn’t find any for mmem
        – both are very small libraries, but mmem is extraordinarily small — it is maybe 200 lines of code. tinymem is currently a bit over 1000. Mostly this is a testament to the feature differences.
        – mmem looks like it would be good for small pool sizes (it’s default is 4000 bytes). tinymem is designed for large pools (64kb), and multiple pools (up to 16 pools), allowing managed memory of up to 1MB


        April 16, 2015 at 2:36 pm

  2. Yes, I meant “mmem”. Your explanation is very detailed and clear, thanks!


    May 6, 2015 at 1:33 pm

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: