embedded software boot camp

Firmware-Specific Bug #5: Heap Fragmentation

Monday, March 15th, 2010 by Michael Barr

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

Tags: , , , , ,

3 Responses to “Firmware-Specific Bug #5: Heap Fragmentation”

  1. Boudewijn says:

    All data structures created via C’s malloc() standard library routine or C++’s new keyword _DO_NOT_NECESSARILY_ live on the heap! They live on whatever the C/C++ library implementer chose to implement. In some cases, they actually do use the RTOS’ memory pool API, which can be fixed-size chunks, or a limited number of sizes, tuned to the application.

  2. Notan says:

    There is another problem with heap fragmentation. The heap administration of a popular real-time system was structured as several lists of free fragments of increasing sizes.
    The first list held small chunks of 12 to 28 bytes, in a system with plenty of memory (standard PC) the system significantly slowed down when it ran for several days. The problem was due to fragmentation, because the 12 to 60 byte list had some thousand 12 byte chunks at the beginning resulting in a lengthy loop, whenever a chunk of 20 byte was allocated.

  3. […] Unlike fragmentation, memory leaks can happen even with fixed-size […]

Leave a Reply to Firmware-Specific Bug #6: Memory Leak « Barr Code