Firmware-Specific Bug #5: Heap Fragmentation

Firmware-Specific Bug #5: Heap Fragmentation: "Dynamic memory allocation is not widely used by embedded software developers—and for good reasons. One of those is the problem of fragmentation of the heap.

All data structures created via C’s malloc() standard library routine or C++’s new keyword live on the heap. The heap is a specific area in RAM of a pre-determined maximum size. Initially, each allocation from the heap reduces the amount of remaining “free” space by the same number of bytes. For example, the heap in a particular system might span 10 KB starting from address 0x20200000. An allocation of a pair of 4-KB data structures would leave 2 KB of free space.

The storage for data structures that are no longer needed can be returned to the heap by a call to free() or use of the delete keyword. In theory this makes that storage space available for reuse during subsequent allocations. But the order of allocations and deletions is generally at least pseudo-random—leading the heap to become a mess of smaller fragments.

To see how fragmentation can be a problem, consider what would happen if the first of the above 4 KB data structures is free. Now the heap consists of one 4-KB free chunk and another 2-KB free chunk; they are not adjacent and cannot be combined. So our heap is already fragmented. Despite 6 KB of total free space, allocations of more than 4 KB will fail.

Fragmentation is similar to entropy: both increase over time. In a long running system (i.e., most every embedded system ever created), fragmentation may eventually cause some allocation requests to fail. And what then? How should your firmware handle the case of a failed heap allocation request?

Best Practice: Avoiding all use of the heap may is a sure way of preventing this bug. But if dynamic memory allocation is either necessary or convenient in your system, there is an alternative way of structuring the heap that will prevent fragmentation. The key observation is that the problem is caused by variable sized requests.

If all of the requests were of the same size, then any free block is as good as any other—even if it happens not to be adjacent to any of the other free blocks. Thus it is possible to use multiple “heaps”—each for allocation requests of a specific size—can using a “memory pool” data structure.

If you like you can write your own fixed-sized memory pool API. You’ll just need three functions:

• handle = pool_create(block_size, num_blocks) - to create a new pool (of size M chunks by N bytes);


• p_block = pool_alloc(handle) - to allocate one chunk (from a specified pool); and


• pool_free(handle, p_block).

But note that many real-time operating systems (RTOSes) feature a fixed-size memory pool API. If you have access to one of those, use it instead of the compiler's malloc() and free() or your own implementation.

Firmware-Specific Bug #4

Firmware-Specific Bug #6 (coming soon)"