When you write malloc(100) in C, you’re asking for 100 bytes of memory. A pointer comes back, you use it, and eventually you call free() to give it back. But what’s actually happening behind that simple interface?
Where Does Dynamic Memory Live?
Your program’s memory is divided into several regions. The stack holds local variables and function call information, growing and shrinking automatically as functions are called and return. The heap is different: it’s a pool of memory that your program can draw from and return to at will, and it persists until you explicitly free it.
The heap isn’t managed by the compiler. It’s managed by the allocator, which is a chunk of code (usually part of your C library) that sits between your malloc calls and the operating system.
What malloc Actually Does
When you call malloc, the allocator needs to find a contiguous block of memory large enough for your request. This is trickier than it sounds.
The allocator maintains data structures to track which parts of the heap are in use and which are free. A simple implementation might keep a linked list of free blocks. When you request memory, it walks the list looking for a block that’s big enough. Different allocators use different strategies here: first-fit (take the first block that’s large enough), best-fit (find the smallest block that’s large enough), or more sophisticated approaches.
When the allocator finds a suitable block, it might be larger than you need. If you ask for 100 bytes and there’s a free block of 500 bytes, the allocator will often split that block — give you 100 bytes and keep the remaining 400 bytes on the free list for future requests.
Here’s the important bit: the allocator typically stores metadata alongside your allocation. If you ask for 100 bytes, the allocator might actually use 108 or 116 bytes internally — the extra space holds information like the size of the allocation, pointers for the free list, or flags. This metadata usually sits just before the pointer you receive. When you call free(ptr), the allocator looks at the bytes just before ptr to figure out how big the block is.
What you think you got: [---- 100 bytes of usable memory ----]
What's actually there: [header][---- 100 bytes of usable memory ----]
^
|
size, flags, etc.This is why freeing an invalid pointer or overwriting memory before your allocation can corrupt the heap — you’re trashing the allocator’s bookkeeping.
Where Does the Memory Come From?
The allocator itself needs to get memory from somewhere. On Unix-like systems, it typically uses system calls like sbrk or mmap. sbrk extends the heap by moving the “program break”, which is the boundary between the heap and unused address space. mmap asks the kernel to map a chunk of memory into your process’s address space.
Calling into the kernel is expensive, so allocators don’t do it for every malloc. Instead, they request large chunks from the operating system and then carve those chunks up to satisfy individual allocations. When you malloc(100), the allocator might have already obtained a 128KB block from the OS, and it just hands you a piece of that.
What free Actually Does
When you call free(ptr), the allocator marks that block as available for reuse. It reads the metadata to determine the block’s size, then adds it back to its free list.
Crucially, free usually doesn’t return memory to the operating system. The memory stays in your process’s address space, available for future malloc calls. This is why a program’s memory usage (as reported by the OS) often doesn’t decrease after freeing memory — the allocator is holding onto it in case you need it again soon.
Some allocators will return large blocks to the OS, particularly those allocated with mmap, but smaller allocations typically just go back into the pool.
Fragmentation
Over time, as you allocate and free memory of varying sizes, the heap can become fragmented. You might have plenty of free memory in total, but it’s scattered across many small non-contiguous blocks. When you ask for a large allocation, there’s no single free block big enough to satisfy it, even though the total free memory exceeds your request.
[used][free 50][used][free 30][used][free 80][used][free 40]
Total free: 200 bytes
Largest contiguous block: 80 bytesIf you request 100 bytes here, you’re out of luck as there’s no contiguous block large enough. The allocator would need to request more memory from the OS, even though 200 bytes are technically free.
Good allocators use various strategies to combat fragmentation: coalescing adjacent free blocks, using different pools for different allocation sizes, or organising memory in ways that reduce fragmentation in the first place.
Coalescing: Merging Free Blocks
When you free a block, a good allocator checks whether the adjacent blocks are also free. If they are, it merges them into a single larger block. This is called coalescing.
Before free(B): [A: free][B: used][C: free]
After free(B): [-- one big free block ---]Without coalescing, you’d accumulate lots of small free blocks that individually aren’t useful for larger allocations. Coalescing helps keep the free list healthy.
Why This Matters
Memory overhead: every allocation costs more than you asked for, because of metadata. Allocating millions of tiny objects is wasteful as you’ll pay the overhead on each one.
Performance: allocation isn’t free. The allocator has to search for suitable blocks, possibly split them, update its data structures. For performance-critical code, you might want to allocate in bulk or use a custom allocator.
Memory doesn’t go down: your program’s resident memory can grow but rarely shrinks, because free doesn’t return memory to the OS. This isn’t a leak, the memory is available for reuse within your process, but it can be surprising.
Corruption is catastrophic: writing past the end of an allocation or freeing the same pointer twice corrupts the allocator’s data structures. The program might not crash immediately, but the heap is now in an inconsistent state. Future allocations might return overlapping memory, or the allocator might crash much later, far from the original bug.
A Note on Modern Allocators
Real-world allocators like glibc’s ptmalloc, jemalloc, or tcmalloc are significantly more sophisticated than the simple model I’ve described. They use multiple arenas to reduce contention in multithreaded programs, maintain separate free lists for different size classes, use thread-local caches to avoid locking on every allocation, and employ various clever tricks to improve performance and reduce fragmentation.
But the fundamentals remain the same: carve up memory into blocks, track what’s free, satisfy requests from the pool, and try not to fragment things too badly in the process.
As always, thanks for joining me on this journey into embedded development!