One of the most common pieces of advice in embedded development is: Don’t use malloc().
But why?
The problem is not that malloc() is inherently bad, nor that dynamic memory allocation is somehow forbidden territory for microcontrollers. The real concerns are external fragmentation and the potentially non-deterministic allocation time associated with searching the heap.
Why Do Embedded Developers Say “Don’t Use malloc()”?#
A general-purpose allocator must find a free region large enough to satisfy each allocation request. As allocations and deallocations occur with different sizes, the heap becomes divided into used and free regions. Over time, this can lead to external fragmentation.
At the same time, finding a suitable free block may require examining multiple free blocks, making allocation potentially O(N), where N is related to the number of free blocks that the allocator needs to inspect.
For systems where memory usage and execution time need to be predictable, both properties are undesirable.
External Fragmentation#
Consider the following 1-KB heap:
Now suppose the application requests 256 bytes. Since the heap is already 1KB, the request is satisfied and 256 bytes are allocated.
Next, another 128 bytes are requested. They are also available and satisfied.
Next, the application frees the 256 bytes block. Now we have free 256 bytes, after which we have allocated 128 bytes, after which we have free 640 bytes.
What happens if the application requests 768 bytes ? The requested memory exists, but it is not as a contiguous block of memory, i.e: no individual free block is large enough to satisfy the request, so the memory manager (malloc) will fail.
This is the essence of external fragmentation: sufficient memory exists, but it is scattered into small, non-contiguous regions.
I’ve already covered this concept, backed with C example in my Advanced C Programming course.
The O(N) Problem#
Fragmentation is not the only concern.
A general-purpose allocator also needs to find a suitable free block.
Depending on the allocator implementation, this may involve traversing a list of free blocks to search through available blocks until a suitable region is found.
If the allocator needs to inspect N free blocks before finding one, the worst case exeution time for malloc scales proportionally with N (i.e: O(n) complexity), which breaks the timing predictability.
The actual complexity depends on the allocator implementation and data structures it uses, so malloc() should not be universally described as O(N). Some allocators use segregated free lists, trees, bins, or other structures to improve average or worst-case behavior.
The important point for embedded systems is that the execution time of a general-purpose allocator is not necessarily constant and predictableو and may depend on the current state of the heap.
Two identical malloc calls may therefore take different amounts of time depending on the allocation history and the current arrangement of free blocks.
For a general-purpose application, this may be perfectly acceptable, while for a hard real-time system, it can make worst-case execution-time analysis significantly more difficult.
These two problem can be solved by using memory pools instead.
Memory Pools#
A memory pool divides a region of memory into a fixed number of equally sized blocks.
For example, a pool may contain three 32-byte blocks, and another pool may contain 3 512-byte blocks:
When an application requests memory, it does not ask for an arbitrary number of bytes.
Instead, it obtains one of the available blocks.
For example, if the application needs 30 bytes, it will get one of the free blocks from the first pool. If it needs a 35 bytes, it will get one of the free blocks from the second pool.
The allocator does not need to search for a block that is “large enough.” Every block in that pool is the same size, so any free block can satisfy the request.
A typical pool maintains a free list containing the available blocks:
Each block points to the next free block, and the pool manager keeps a pointer to the first free block. Once the application requests a block, the pool manager simply returns the block pointed to by that pointer, and update the pointer to point to the next free block. This executes in constant time regardless of number of free block.
A deallocation puts the block back to the list and updates the first free block pointer.
There is no need to search the heap for a differently sized region.
This eliminates external fragmentation within the pool.
If there are ten free blocks, they are ten interchangeable blocks. It does not matter where they are located in the memory region.
But this solution introduces another form of fragmentation.
Internal Fragmentation#
Suppose the pool uses 32-byte blocks and the application needs only 15 bytes.
The allocator still has to provide a complete 32-byte block, but the unused 17 bytes cannot be allocated independently.
This is internal fragmentation: memory is wasted inside an allocated block. At first, this may look like a bad trade, so why deliberately to waste memory?
Because internal fragmentation is bounded and predictable, while external fragmentation is dependent on the application’s allocation history.
External vs. Internal Fragmentation#
External fragmentation#
The amount of usable memory depends on the current layout of the heap. The more malloc/free pairs, the more the heap gets (holes). The total size of these holes may be sufficient for a given memory allocation request, but since these holes are not contigous, a request may fail.
More importantly, the future layout depends on the sequence of allocations and deallocations performed by the application.
Internal fragmentation#
The waste is determined by the allocation scheme.
If all blocks are 32 bytes, the maximum unused space in a single allocation is known in advance. For a request of N bytes, the wasted space is: waste = block_size - N for requests that fit within one block.
Therefore, the maximum waste is bounded by the pool configuration.
For a 32-byte pool, an allocation can waste at most 31 bytes.
The exact system-wide waste can also be estimated from the application’s allocation profile and the number and sizes of pools.
More importantly, this waste does not grow simply because the system has been running longer.
A system that has been running for five minutes and a system that has been running for five years use the same pool structure. Internal fragmentation does not progressively turn the remaining memory into unusable holes.
That predictability is the key reason embedded systems often accept internal fragmentation.
Why Accept Internal Fragmentation?#
External fragmentation is a dynamic and workload-dependent problem that leaves holes between allocated blocks, whose size is unbounded and accordingly can affect future allocation requests. This gives poor predeictablility and harded system design.
Internal fragmentation is design-time trade-off that leaves holes inside the allocated block, where the waste is bounded to the block size. This gives much better predictability. An engineer can calculate how much RAM is assigned to each memory pool and estimate the worst-case amount of unused space. The resulting memory overhead can be accounted for during system design.
So the design philosophy becomes: Don’t allow memory to become unpredictably unusable. Accept a known amount of bounded waste instead.
This is one of the fundamental reasons memory pools are so common in embedded systems.
They trade the flexibility of general-purpose dynamic allocation for a memory model that is easier to analyze, easier to constrain, and more predictable.
Reply by Email