Memory Allocation

malloc(size) returns a pointer to at least size bytes of usable heap memory. Behind the scenes, the allocator manages a complex data structure of free blocks, splitting and coalescing as needed.

Why It Matters

Every C program that handles variable-size data uses dynamic allocation. Understanding how allocators work explains why free can’t know the size (it’s in a hidden header), why fragmentation kills long-running programs, and when to use alternative allocators.

The malloc/free Interface

#include <stdlib.h>
 
int *arr = malloc(100 * sizeof(int));  // allocate
if (!arr) { perror("malloc"); exit(1); }
 
arr = realloc(arr, 200 * sizeof(int)); // grow (may move the block)
if (!arr) { /* old pointer is still valid if realloc fails */ }
 
int *zeroed = calloc(100, sizeof(int)); // allocate + zero-fill
 
free(arr);     // return to allocator
free(zeroed);

Function	Behavior
malloc(n)	Allocate n bytes, uninitialized
calloc(count, size)	Allocate count*size bytes, zero-filled
realloc(ptr, n)	Resize to n bytes, may move data
free(ptr)	Return block to free list

Under the Hood

Block Metadata

Every allocated block has a hidden header (typically 8-16 bytes) stored just before the returned pointer:

        ┌──────────┬────────────────────┐
        │  header   │   usable memory    │
        │ (size,    │   (what malloc     │
        │  flags)   │    returns)        │
        └──────────┴────────────────────┘
                    ↑
              pointer returned to you

This is why free(ptr) doesn’t need a size argument — it reads the header. It’s also why writing before the pointer corrupts allocator metadata (heap corruption).

Free List Strategies

Strategy	How It Works	Tradeoff
First-fit	Use first block that’s big enough	Fast but causes fragmentation
Best-fit	Use smallest sufficient block	Less waste, slower search
Buddy system	Split power-of-2 blocks	Fast coalescing, internal waste

sbrk vs mmap

Method	How	When
sbrk(n)	Extends heap break linearly	Small allocations (<128KB)
mmap()	Maps fresh anonymous pages	Large allocations (≥128KB)

mmap allocations are returned directly to the OS on free. sbrk memory stays in the process — the heap break rarely shrinks.

Fragmentation

After many malloc/free cycles:
┌────┐┌──┐┌────┐┌──┐┌────┐
│used││free││used││free││used│  ← external fragmentation
└────┘└──┘└────┘└──┘└────┘
Total free = 200 bytes, but no single block > 100 bytes

• External fragmentation: free memory is scattered in small non-contiguous blocks
• Internal fragmentation: allocated blocks are bigger than requested (alignment padding)

Long-running programs (servers, daemons) are most affected. This is why custom allocators exist.

Arena Allocator

For batch-allocate/batch-free patterns (parsing, per-request memory):

typedef struct {
    char *buf;
    size_t offset;
    size_t cap;
} Arena;
 
Arena arena_new(size_t cap) {
    return (Arena){.buf = malloc(cap), .cap = cap};
}
 
void *arena_alloc(Arena *a, size_t size) {
    size = (size + 7) & ~7;  // align to 8 bytes
    if (a->offset + size > a->cap) return NULL;
    void *ptr = a->buf + a->offset;
    a->offset += size;
    return ptr;
}
 
void arena_reset(Arena *a) { a->offset = 0; }  // "free" everything at once
void arena_free(Arena *a) { free(a->buf); }

Arena allocators are O(1) allocation with zero fragmentation — ideal for request handlers, game frames, or parsers.

Related

• Pointers and Memory — pointer bugs that corrupt the heap
• Memory Management — OS-level view (virtual memory, page tables)
• System Calls — brk and mmap syscalls the allocator uses