</>EmbeddedInterview

What is heap fragmentation and why does it matter in embedded systems?

MediumPointers & Memory

Short answer: After many allocations and frees of different sizes, free memory is split into many small, non-adjacent holes. An allocation can then fail even though the total free memory is large enough, because no single hole is big enough. Devices that must run for years without rebooting can fail this way after days or months, which makes the bug very hard to reproduce.

Example (a 10 KB heap)

allocate A 2K, B 2K, C 2K, D 2K, E 2K   -> heap full
free B and D                            -> 4 KB free, but as two 2 KB holes
malloc(3K)                              -> FAILS: no hole is 3 KB

External vs internal fragmentation

  • External: free memory exists but is split into pieces (the example above).
  • Internal: memory wasted inside allocated blocks, e.g. a pool with 64-byte blocks used for 20-byte objects, or allocator headers and alignment padding.

Mitigations

  1. Allocate everything at start-up and never free. Simple and deterministic (FreeRTOS heap_1).
  2. Fixed-size memory pools: blocks of one size per pool, so any free block fits any request; no external fragmentation, O(1) allocate/free.
  3. Coalescing allocators: merge adjacent free blocks (FreeRTOS heap_4, TLSF); this reduces but does not eliminate fragmentation.
  4. TLSF (Two-Level Segregated Fit): O(1), bounded fragmentation, used in real-time systems (Zephyr offers it).
  5. Avoid mixing lifetimes: allocate long-lived objects first, and keep short-lived ones in a separate pool or arena.
  6. Arena/region allocation: allocate from a buffer for one operation and release the whole arena at once.

Monitoring: track the largest free block as well as total free memory; a shrinking largest-block size while total free memory stays constant is the signature of fragmentation.

Safety standards (MISRA C, IEC 61508, ISO 26262 guidance, DO-178C practice) generally forbid dynamic allocation after initialisation because of fragmentation and non-deterministic timing.