Dynamic Memory
Every other language hands out memory as you ask for it. C will too, and on a microcontroller that is usually a mistake. This volume builds a small allocator so you can watch it fragment, then replaces it with the two things firmware really uses: buffers decided at compile time, and pools of identical blocks.
- What malloc actually does, headers and all, in an allocator small enough to read
- How free memory becomes unusable while the total stays the same
- Why static allocation lets the linker prove your program fits
- How a fixed-block pool gives constant-time allocation that cannot fragment
- The six classic memory bugs, and which of them nothing will report
14.1 malloc and free
malloc asks the heap for some memory while the program is running. It is the one tool in C that can fail at any moment, for reasons your code did not cause.
Volume 09 drew the heap: the region of RAM between the end of .bss and the stack coming down.
malloc hands out pieces of it and free gives them back.
uint8_t *buffer = malloc(64u);
if (buffer == NULL) { /* and this line is not optional */
return ERR_NO_MEMORY;
}
/* ... use it ... */
free(buffer);
What it does underneath
The heap is not a magic pool. It is an ordinary array of bytes, cut into blocks, each with a small header saying how big it is and whether it is in use. Here is a real first-fit allocator, shrunk to 96 bytes so the whole heap fits on one line.
typedef struct {
uint16_t size; /* payload bytes in this block */
uint8_t used;
uint8_t magic;
} header_t; /* four bytes, in front of every block */
static void *tiny_malloc(uint16_t want)
{
uint32_t at = 0u;
while (at < HEAP_BYTES) {
header_t h = read_header(at);
if (!h.used && h.size >= want) {
if (h.size >= want + HEADER + GRAIN) {
header_t rest = { (uint16_t)(h.size - want - HEADER), 0u, MAGIC };
write_header(at + HEADER + want, rest); /* split what is left */
h.size = want;
}
h.used = 1u;
write_header(at, h);
return &heap[at + HEADER];
}
at += HEADER + h.size; /* on to the next */
}
return NULL;
}
Two things follow from that code, and both matter on a small chip.
It walks the blocks. So malloc does not take a fixed amount of time. It takes longer when the heap
is busy, and you cannot say in advance how much longer.
And every block costs a header. Ask for 60 bytes in three pieces and you spend rather more:
empty [H.......................] free 92 total, 92 in the largest block
three blocks of 20 [H#####H#####H#####H.....] free 20 total, 20 in the largest block
60 bytes asked for, 76 bytes of heap consumed - headers are not free
Asking for memory in lots of small pieces. Sixteen allocations of four bytes cost sixteen headers, which on a typical allocator is more overhead than payload. If you need many small things, allocate one array of them.
Why can malloc take a different amount of time on each call?
Show the answer
Answer: B. It walks the list of blocks until it finds one that fits. How many it visits depends on the state of the heap, which depends on everything the program has done so far.
14.2 Fragmentation
Fragmentation is having plenty of memory and none of it usable. It is the reason malloc is rare in firmware, and adding RAM does not fix it.
Three blocks of twenty. Free the middle one. Now there is a hole.
after freeing the middle [H#####H.....H#####H.....] free 40 total, 20 in the largest block
Forty bytes are free, in two pieces of twenty, with a block still in use between them. So ask for forty:
now ask for 40 bytes, when 40 are free:
tiny_malloc(40) returned NULL
the memory exists, but not in one piece. That is fragmentation.
Nothing is broken. No bug has been committed. The allocator did exactly what it should, and the program is out of memory with half its heap free.
A car park with forty spaces, thirty-eight taken, and the two free ones at opposite ends. A caravan needs two spaces together. There is plenty of room, and nowhere to put it.
Merging helps, and not enough
Free a block next to another free block and the two can be joined:
after freeing the first too [H...........H#####H.....] free 64 total, 44 in the largest block
tiny_malloc(40) now returned a pointer, because two holes merged into one
But merging only works when the free blocks happen to touch. Free everything, in an order that left a used block between two holes, and the heap still does not fully recover:
everything freed [H...........H...........] free 88 total, 44 in the largest block
every byte is free, and the largest block is still only 44
this allocator merges a freed block with the one after it, and no further
merging backwards as well needs another pointer in every header
real allocators do that, and it still does not prevent fragmentation
On a desktop the heap is enormous and the program exits eventually. A microcontroller has a few kilobytes and runs for years. Fragmentation accumulates, and the failure arrives after months, in a device that is already installed, at a line of code that did nothing wrong.
Can you not just defragment it
Not in C, because the program holds raw addresses. Moving a block would mean finding and updating every pointer to it, and nothing knows where they all are.
Languages with garbage collection can compact the heap, precisely because the runtime does know where every reference lives. That is the trade. They get compaction, and you get to know exactly where every byte went. Firmware generally prefers the second.
Your firmware fails with "out of memory" after four days, and a report says 3 KB of an 8 KB heap is free. What is happening?
Show the answer
Answer: C. A leak would show a shrinking free total. Here the total is healthy and allocation still fails, so no single gap is big enough. Four days of allocating and freeing different sizes is exactly how that arises.
14.3 Static allocation instead
Decide the sizes at compile time. Then the linker can tell you whether your program fits, before it has ever run.
Static allocation is the default in firmware, and it is not a compromise. It is a stronger guarantee than any amount of careful run-time checking.
uint8_t *rx = malloc(RX_SIZE);
if (rx == NULL) {
/* now what? */
}
/* ... */
free(rx);
static uint8_t rx[RX_SIZE];
/* nothing to check, nothing
to free, and the map file
already proved it fits */
The left-hand version pushes the question to run time, on a device with no user, no log and nowhere to report to. The right-hand version answers it while you are still at your desk. If it does not fit, the link fails.
If a buffer exists for the whole life of the program, it should be static, not allocated. That
covers most buffers in most firmware.
What about things that come and go
Not everything is permanent. Messages arrive and are dealt with, connections open and close. The usual answers, in order of preference:
That last step is worth pausing on. Allocating during initialisation and never freeing gets you the flexibility of run-time sizing with none of the fragmentation, because nothing is ever returned. Some certified systems allow exactly that and forbid everything else.
Sizing a static buffer by guessing. The point of static allocation is to know, so work out the worst case: the longest message, the deepest queue, the most connections at once. If you cannot work it out, that is a design question rather than an allocation question.
What is the main advantage of deciding buffer sizes at compile time?
Show the answer
Answer: A. It usually uses more RAM, not less, because everything is reserved whether it is in use or not. What you buy is certainty: the linker either fits it or refuses, and no failure mode is left at run time.
14.4 Memory pools
A pool hands out blocks that are all the same size. That one restriction removes fragmentation completely, and makes every allocation take the same time.
If every block is identical then any free block satisfies any request. There is nothing to search for, nothing to split, and nothing to merge.
static uint8_t pool[POOL_BLOCKS][BLOCK_BYTES];
static uint8_t next_free[POOL_BLOCKS]; /* the free list, as indexes */
static uint8_t free_head;
static void *pool_alloc(void)
{
if (free_head == NONE) {
return NULL;
}
uint8_t i = free_head;
free_head = next_free[i]; /* take the first one off the list */
next_free[i] = NONE;
return pool[i];
}
static void pool_free(void *p)
{
uint8_t i = (uint8_t)(((uint8_t *)p - &pool[0][0]) / BLOCK_BYTES);
next_free[i] = free_head; /* put it back on the front */
free_head = i;
}
Four lines each, and no loops, so both take the same time on every call whatever the pool has been
doing. That is what makes a pool usable inside an interrupt handler, where malloc never is.
empty [........] 0 of 8 in use
three taken [###.....] 3 of 8 in use
freed the middle one [#.#.....] 2 of 8 in use
asked for one more [###.....] 3 of 8 in use
it got block 1 back - the same one, with no searching at all
Compare that with the heap in Module 2. The same pattern of use - take three, free the middle, ask for another - left the heap unable to serve a request. The pool simply hands the block back.
Full means full
completely full [########] 8 of 8 in use
one more request returned NULL
full means full, and it says so straight away
This is the honest failure that fragmentation never gives you. A pool fails only when every block is genuinely in use, which is a fact about your program's behaviour rather than about the history of its allocations.
Keep a high-water mark of how many blocks were ever in use at once, exactly as Volume 09 measured the stack. Run the worst case you can construct, read the number, and add a margin. The pool in the example reported its own: the most ever held at once.
Threading the list through the blocks
The example keeps a separate array of indexes, which costs one byte per block and is easy to read. Production pools usually avoid even that, by storing the "next free" pointer inside the free block itself. A block that is free is not holding anything, so its first few bytes are available.
That makes the bookkeeping free, at the cost of a block having to be at least as large as a pointer, and of the code being harder to follow. Both arrangements are common, and neither changes the property that matters: constant time, and no fragmentation.
Choosing a block size by averaging. A pool block has to fit the largest thing that goes in it, so an average wastes memory on small items and fails on large ones. If the sizes really are very different, use two pools of different sizes rather than one compromise.
Why can a pool allocator run inside an interrupt handler when malloc cannot?
Show the answer
Answer: B. A handler needs a known worst-case time. A pool takes one item off a list, which is a handful of
instructions regardless of state. malloc searches, so its worst case depends on the heap.
14.5 The six classic memory bugs
Six bugs account for almost every memory fault in C. Five of them can be caught by an allocator that is looking for them. The sixth reports nothing at all.
Each of these is undefined behaviour with a real malloc, which means anything may happen,
including nothing. So the demonstration uses a guarded allocator instead: it writes a
canary after every block, fills freed memory with a recognisable pattern, and
keeps a record of every block.
One: the leak
uint8_t *tmp = g_alloc(16u);
tmp = NULL; /* the only address of that block is gone */
1. a leak: allocate, then lose the only pointer to it
no error yet - a leak is invisible until the memory runs out
A leak is not an event. It is the absence of one. The program carries on perfectly, a little poorer, and the only symptom arrives hours or weeks later as a failed allocation somewhere unrelated.
Two: use after free
2. use after free: read through a pointer to freed memory
before freeing, p[0] is 42
after freeing, p[0] is 222
222 is 0xDE, the pattern this allocator writes over freed memory
with a real malloc it might still be 42, until the day it is not
That last line is the danger. Freeing does not erase anything, so the old value is usually still sitting there and the bug appears to work. It breaks on the day something else is allocated into that space, which is a different day from the one you wrote the bug on.
Set a pointer to NULL immediately after freeing it. It turns a
use after free, which may silently work, into a
null pointer fault, which does not.
Three, four and five: the ones tools catch
3. double free: give the same block back twice
CAUGHT: double free - this block was already freed
4. buffer overrun: write one element past the end
CAUGHT: buffer overrun - something was written past the end of a block
5. freeing a pointer that did not come from the allocator
CAUGHT: free of a pointer that was never allocated - it does not point at the start of any block
A double free usually corrupts the allocator's own bookkeeping, so the
crash happens in the next unrelated malloc. The overrun in step 4 was a loop written i <= 8
instead of i < 8, which is the most common single mistake in C.
Six: not checking the result
6. not checking the result: keep allocating until it fails
got 4 blocks, then the allocator returned NULL
writing through that NULL is the bug, and it is the one
that turns a full heap into a crash somewhere else entirely
3 problems were caught, and the leak in step 1 was not one of them
that is the whole difficulty with leaks: nothing reports them
The technique in this file is worth keeping. Wrap your allocator in a debug version that writes canaries, poisons freed memory and counts live blocks, and enable it in test builds. It turns several of these bugs from mysteries into messages, on the real board, at the moment they happen.
Assuming a memory bug is where the crash is. Corruption and the crash it causes are usually in different functions, often in different files. The place the program died is where the damage was noticed, not where it was done.
Which of these memory bugs will nothing report, even with a debug allocator?
Show the answer
Answer: D. The others are all actions the allocator can inspect. A leak is the absence of an action: the
program simply never calls free, which looks exactly like memory still being in use.
What you learned
mallocwalks a list of blocks, so it has no fixed worst-case time- Every block carries a header, so many small allocations waste more than they use
- Fragmentation means free memory in pieces too small to use, and the total stays healthy while requests fail
- Merging adjacent free blocks helps, needs extra bookkeeping, and does not solve the problem
- A heap cannot be compacted in C, because the program holds raw addresses
- Static allocation moves the question from run time to link time, which is a far stronger guarantee
- Prefer, in order: a static buffer, one reused buffer, a ring buffer, a pool, then
malloconce and never free - A pool of equal blocks cannot fragment, and allocates in constant time
- A pool can be used in an interrupt handler;
malloccannot - Size a pool by measuring the high-water mark, exactly as you size a stack
- Set a pointer to
NULLafter freeing it, so a use after free fails loudly - Of the six classic bugs, a debug allocator catches five, and nothing at all reports a leak
Practice
A radio driver receives packets between 8 and 200 bytes, up to four outstanding at once, and frees
each when it has been handled. Design the memory for it, without malloc.
Show the solution
A pool of five blocks of 200 bytes, statically allocated: 1000 bytes of RAM, decided at compile time.
#define PACKET_MAX 200u
#define PACKET_SLOTS 5u /* four outstanding, plus one being filled */
static uint8_t packet_pool[PACKET_SLOTS][PACKET_MAX];
Every block is the largest packet, so an 8-byte packet wastes 192 bytes. That is the price, and it buys a system that cannot fragment and cannot fail unpredictably.
If wasting that is unacceptable, use two pools - say eight blocks of 32 bytes and three of 200 - and choose by size. That recovers most of the memory and keeps both properties. What you must not do is make one pool of the average size, because the large packets then have nowhere to go.
The fifth slot matters. If exactly four can be outstanding, a fifth is needed for the one currently arriving, or the driver has nowhere to put it while the other four are being handled.
Find the three bugs.
char *make_label(int n)
{
char *s = malloc(8);
sprintf(s, "item %d", n);
return s;
}
void show(void)
{
char *a = make_label(1);
printf("%s\n", a);
free(a);
printf("%s\n", a);
}
Show the solution
One: the result of malloc is never checked. If it returns NULL, sprintf writes to address
zero and the board faults.
Two: the buffer is too small. "item 1" is six characters plus a terminator, which just fits in
eight. "item 1000" is nine plus a terminator, which does not, and sprintf writes past the end.
Volume 06 met this: snprintf with the real size, and check what it returns.
Three: use after free. The second printf reads a after it has been freed. It will usually
print the right thing, which is exactly why it survives testing.
#define LABEL_MAX 16u
bool make_label(char *out, size_t out_size, int n)
{
int wrote = snprintf(out, out_size, "item %d", n);
return wrote > 0 && (size_t)wrote < out_size;
}
void show(void)
{
char label[LABEL_MAX];
if (make_label(label, sizeof label, 1)) {
printf("%s\n", label);
}
}
The repair removes the allocation entirely. The caller owns the buffer, so there is nothing to leak, nothing to free twice and nothing to use afterwards.
A device works for weeks on the bench and fails after about ten days in the field. Free heap is reported as 40 per cent. What are the two likely explanations, and how would you tell them apart?
Show the solution
Fragmentation, or a leak that has not finished yet. The 40 per cent figure points at the first, but does not settle it.
To tell them apart, record two numbers rather than one: total free, and the largest single free block. Then:
- Total free falling steadily over days means a leak
- Total free steady while the largest block shrinks means fragmentation
Log both periodically and the graph answers it within a day or two.
There is a third possibility worth ruling out: the stack growing into the heap. That shows as corruption rather than allocation failure, and Volume 09's painted stack will reveal it.
Whichever it is, the fix is the same direction of travel: move the repeated allocations to a pool or to static buffers, so that neither failure can occur.
Write pool_free so that freeing the same block twice is detected rather than corrupting the free
list. What does it cost?
Show the solution
The free list in the example already has somewhere to record it. A block on the list has a next
index; a block in use has NONE. So a block being freed should have NONE, and anything else means
it was already free.
static bool pool_free_checked(void *p)
{
if (p == NULL) {
return true;
}
uint8_t i = (uint8_t)(((uint8_t *)p - &pool[0][0]) / BLOCK_BYTES);
if (i >= POOL_BLOCKS) {
return false; /* not from this pool at all */
}
if (next_free[i] != NONE || free_head == i) {
return false; /* already on the free list */
}
next_free[i] = free_head;
free_head = i;
return true;
}
The free_head == i test is needed because the most recently freed block has whatever the old head
was in its next, which may legitimately be NONE when the pool was full.
It costs two comparisons, which is nothing, and the function still runs in constant time. That is why this check is worth having in the release build, not only in debug.
Your project must never call malloc. A library you need calls it internally. What can you do?
Show the solution
Several options, roughly in order of preference.
Check whether it only allocates at start-up. Many libraries take everything they need during
initialisation and never allocate again. That is usually acceptable even under a no-malloc rule,
because nothing is ever freed and so nothing can fragment.
Look for a static configuration. Good embedded libraries offer one: a macro to supply a buffer, or a build option that removes dynamic allocation.
Provide your own malloc. The symbol can be replaced with an implementation backed by a fixed
pool. It will fail when the pool is empty, but it will fail predictably, and it can be instrumented
to report what the library actually asked for.
Replace the library. If it allocates and frees continuously during normal running, and there is no option to stop it, then it was not written for this kind of system.
The measurement to take first is simple: wrap malloc and free, log every call with its size, and
run the worst case. Often the result shows the problem is much smaller than feared.
Interview corner
malloc in firmware
"Why is dynamic allocation discouraged in embedded systems?"
Show the solution
"Three reasons, and they compound.
It can fail, and there is usually nowhere sensible to report that on a device with no user. Handling it correctly at every call site is hard, and most code does not.
It has no bounded worst-case time, because it searches. That breaks the timing guarantees a real-time system depends on, and it rules it out of an interrupt handler.
And it fragments. Free memory ends up in pieces too small to use, so a request fails while the total free figure still looks healthy. On a device that runs for years, that failure arrives long after shipping.
What I would use instead is static allocation wherever the lifetime is the whole program, and a pool of fixed-size blocks where things genuinely come and go."
Fragmentation
"Explain memory fragmentation, and whether a bigger heap fixes it."
Show the solution
"Fragmentation is free memory split into pieces too small to satisfy a request. Allocating and freeing different sizes leaves gaps between the blocks still in use, and those gaps only merge if they are next to each other.
A bigger heap delays it rather than fixing it. The ratio of largest block to total free still decays over time, so the failure moves further out and still arrives. What actually fixes it is removing the variability. Equal-sized blocks from a pool, so that any free block serves any request. Or static allocation, so that nothing is ever returned in the first place.
I would measure it by logging both the total free and the largest free block. If the total is steady while the largest shrinks, that is fragmentation rather than a leak."
Use after free
"Why is use after free so hard to find?"
Show the solution
"Because freeing does not erase anything. The bytes are still there, so the code usually reads the value it expected and works perfectly. It only breaks when something else gets allocated into that space and overwrites it. That depends on what the rest of the program did, so it is timing dependent and does not reproduce.
Two habits help. Set the pointer to NULL immediately after freeing, so a later use faults
immediately and near the actual bug. And in test builds, fill freed memory with a recognisable
pattern like 0xDE, so stale data becomes obviously wrong instead of plausibly right.
The deeper fix is ownership: be clear about which piece of code owns a buffer and is responsible for releasing it. Most of these bugs come from two places both believing they own something."
Designing without a heap
"How would you handle variable-length messages with no dynamic allocation?"
Show the solution
"A pool of fixed-size blocks, sized for the longest message, statically allocated. Any free block serves any message, so it cannot fragment, and allocation is a few instructions, so it can happen in the receive interrupt.
If the size range is wide enough that one block size wastes too much, I would use two or three pools at different sizes and pick the smallest that fits. That keeps the properties and recovers most of the memory.
I would size them by measurement, not by guesswork: keep a high-water mark of blocks in use, run the worst traffic I can generate, and add a margin. And I would make the allocation failure path real - count the drops and report them - rather than pretending it cannot happen."
Next, Volume 15 steps back from the chip and looks at the tools. What the preprocessor really does before the compiler ever sees your code, why header guards exist, and what happens between a folder of source files and one binary.
Key words from this volume
Every word below has a plain-English entry in the glossary.
- malloc
- Heap
- Fragmentation
- Static allocation
- Memory pool
- Canary
- Memory leak
- Use after free
- NULL
- Double free