Skip to main content

Heap Allocation: malloc, free, Fragmentation, Allocators

What This Concept Is​

malloc(size) asks the C library's allocator for a block of at least size bytes, suitably aligned, whose lifetime is "until someone calls free." free(p) returns a previously allocated block to the allocator; the memory may or may not go back to the OS.

At the implementation level, an allocator:

  • asks the OS for big chunks (via sbrk or mmap) and carves them up
  • tracks which blocks are free, usually with a free list, bins by size class, or a tree
  • merges adjacent free blocks (coalescing) so future requests can be satisfied
  • stores bookkeeping (size, free flag, link pointers) in headers next to or inside each block

A real-world allocator like glibc's ptmalloc2 or jemalloc or tcmalloc adds per-thread caches, size classes, and fast paths; the principles are the same.

Why It Matters Here​

Heap discipline is the difference between a program and a reliable system:

  • every malloc needs a matching free (or an explicit "the process exits soon" decision)
  • every allocation can return NULL; a program that does not check will crash
  • long-running servers accumulate fragmentation if free blocks are small and scattered
  • multi-threaded allocators trade memory for throughput with per-thread arenas

Concrete Example​

A simple free-list layout (conceptual, one bin, 8-byte aligned):

                 header    payload         header  payload     header payload
heap start ->  +--------+-----------+---+--------+---------+---+-------+-------+ ...
               | size=32|  USED     |   | size=16|  FREE   |   |size=48| USED  |
               | flags  |  (24 B)   |   | flags  | (8 B)   |   | flags | (40B) |
               +--------+-----------+---+--------+---------+---+-------+-------+
                         ^                                      ^
                         p1 = malloc(24)                        p3 = malloc(40)
                                         free block in bin

malloc walks the free list (or the size-class bin), picks a block, splits it if it is much larger than requested, and returns a pointer to the payload. free(p) flips the flag and (usually) merges with free neighbors.

Fragmentation comes in two flavors:

  • external: total free bytes are enough, but no single free block is big enough for the next request. Think "holes in swiss cheese."
  • internal: the allocator gave you a block larger than you asked for (rounded up to alignment or size class), and the slack is wasted until free.

Common Confusion / Misconception​

"free returns memory to the OS." Usually not. Most allocators keep freed blocks for reuse. The process's RSS shrinks mainly when an mmap-backed chunk is unmapped or when malloc_trim is called explicitly.

"malloc initializes memory to zero." No. Use calloc(n, size) or memset if you need zeroed memory.

"If malloc returns NULL, it is out of RAM." Often it is actually over-commit limits, per-process RLIMIT_AS, or a bad request (size == SIZE_MAX). Always check; do not assume.

How To Use It​

For every heap allocation you write:

  1. Record in a comment who owns it and who will free it.
  2. Check the return value for NULL before dereferencing.
  3. After free(p);, write p = NULL; unless the pointer is about to go out of scope.
  4. Prefer calloc when zero init is needed; use realloc only after reading its exact semantics.

Check Yourself​

  1. What is the difference between external and internal fragmentation, with a one-line example of each?
  2. Why is free(p); free(p); a bug even if p looks like a valid address?
  3. What does realloc(p, 0) do, and why is its behavior implementation-defined?

Mini Drill or Application​

Sketch a bump allocator that only allocates (never frees):

#include <stddef.h>
#include <stdint.h>
#include <assert.h>

static unsigned char arena[1 << 20];
static size_t bump = 0;

void *bump_alloc(size_t n, size_t align) {
    size_t a = (bump + align - 1) & ~(align - 1);
    if (a + n > sizeof arena) return NULL;
    void *p = &arena[a];
    bump = a + n;
    return p;
}

Build with gcc -Wall -Wextra -c bump.c and write three tests: small allocation, aligned allocation, exhaustion returns NULL. Then extend to a single-linked free list that supports bump_free. Note where coalescing would be needed.

Read This Only If Stuck​