Memory Allocation: malloc, Fragmentation and Allocators
User programs allocate with malloc/new; the C library's allocator gets memory from the kernel in large chunks:
Concept
Where Dynamic Memory Comes From User programs allocate with malloc/new; the C library's allocator gets memory from the kernel in large chunks:
brk/sbrk — grows the heap segment (glibc uses it for small blocks);
mmap — separate anonymous mappings for large blocks (glibc: ≥ 128 KB by default, the *mmap threshold*), returned to the OS immediately on free.
The allocator then carves these chunks into blocks. Each block has a hidden header (size, flags) and alignment padding (16 bytes on x86-64), and free blocks are kept in free lists / bins by size. glibc uses per-thread caches (tcache) and arenas to reduce lock contention; jemalloc, tcmalloc and mimalloc are popular alternatives.
Internal — wasted space *inside* an allocated block (rounding 100 bytes up to 112, or 70 KB to a 128 KB buddy block).
External — enough total free memory, but split into pieces too small for a request.
Classic Placement Strategies (contiguous allocation) The first hole big enough Fast; fragments the beginning of memory The smallest hole big enough Leaves tiny, useless holes The largest hole
Leaves big holes, but uses up large holes quickly First fit, continuing from the last position
Buddy allocator (Linux page allocator): blocks of 2ᵏ pages; a request is rounded up to a power of two, larger blocks are split in halves ("buddies"), and freed buddies merge again. Fast, low external fragmentation, some internal fragmentation.
Slab allocator (SLUB in Linux): caches of equal-sized kernel objects (inodes, task_structs) carved from pages — no per-object fragmentation, fast reuse.
Memory pools / arenas in applications (and embedded systems that forbid malloc after start-up) follow the same idea: fixed-size blocks, deterministic time.
Why It Matters
Memory leaks, fragmentation in long-running services and embedded systems, allocator lock contention in multithreaded servers, and allocation latency in real-time code are everyday engineering problems. Safety standards (MISRA C, AUTOSAR) restrict dynamic allocation for exactly these reasons.
Syntax
void *p = malloc(n); free(p);
void *q = aligned_alloc(64, 4096); /* cache-line aligned */
size_t usable = malloc_usable_size(p); /* glibc */
void *top = sbrk(0); /* current program break */Example
21.1 Where glibc's malloc gets its memory 21.2 Placement strategies and a buddy allocator
#define _GNU_SOURCE
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <malloc.h>
static void region_of(const char *label, void *p)
{
FILE *f = fopen("/proc/self/maps", "r");
char line[256];
while (fgets(line, sizeof line, f)) {
unsigned long lo, hi; char name[128] = "";
sscanf(line, "%lx-%lx %*s %*s %*s %*s %127s", &lo, &hi, name);
if ((unsigned long)p >= lo && (unsigned long)p < hi) {
printf("%-26s %p in %s\n", label, p, name[0] ? name : "[anonymous mmap]");
break;
}
}
fclose(f);
}
int main(void)
{
void *brk0 = sbrk(0);
char *small = malloc(100);
char *medium = malloc(64 * 1024);
char *large = malloc(1024 * 1024); /* above the mmap threshold (128 KB by default) */
region_of("malloc(100)", small);
region_of("malloc(64 KB)", medium);
region_of("malloc(1 MB)", large);
printf("program break moved by %ld KB for the small blocks\n", ((char *)sbrk(0) - (char *)brk0) / 1024);
/* every block carries hidden bookkeeping: usable size >= requested size */
printf("malloc(100) usable size: %zu bytes; malloc(1) usable size:
…"""Contiguous allocation strategies (first/best/worst fit) and a buddy allocator."""
def place(holes, requests, choose):
holes = holes[:]
result = []
for r in requests:
fits = [i for i, h in enumerate(holes) if h >= r]
if not fits:
result.append(f"{r}K:wait"); continue
i = choose(fits, holes)
result.append(f"{r}K->hole{i}")
holes[i] -= r
return result, holes
holes = [100, 500, 200, 300, 600]
requests = [212, 417, 112, 426]
for name, choose in [("first fit", lambda f, h: f[0]),
("best fit", lambda f, h: min(f, key=lambda i: h[i])),
("worst fit", lambda f, h: max(f, key=lambda i: h[i]))]:
res, left = place(holes, requests, choose)
print(f"{name:<9}: {', '.join(res):<46} holes left {left}")
# buddy allocator over 1024 KB: sizes are powers of two, free blocks merge with their buddy
free = {1024: [0]}
def alloc(kb):
size = 1
while size < kb: size *= 2
s = size
while s <= 1024 and not free.get(s): s *= 2
if s > 1024: return None
addr = free[s].pop(0)
while s > size: # split, keeping the upper half free
…Expected Result
Small and medium blocks came from the [heap] grown with brk (the first growth is 132 KB); the 1 MB block got its own anonymous mmap.
A 1-byte request really occupies a 24-usable-byte chunk, and two 24-byte requests are 32 bytes apart: header plus 16-byte alignment — internal fragmentation.
A freed block is reused for the next request of the same size (per-thread cache).
For the holes 100/500/200/300/600 KB, first fit and worst fit can't place the 426 KB request although 959 KB (first fit) are free in total — external fragmentation. Best fit places all four.
The buddy allocator rounded 70 KB up to 128 KB (58 KB internal fragmentation), split larger blocks to serve the requests, and merged everything back into one 1024 KB block after all were freed.
malloc(100) 0x55f5e45722a0 in [heap]
malloc(64 KB) 0x55f5e4572310 in [heap]
malloc(1 MB) 0x78563a8ff010 in [anonymous mmap]
program break moved by 132 KB for the small blocks
malloc(100) usable size: 104 bytes; malloc(1) usable size: 24 bytes
two consecutive malloc(24) blocks are 32 bytes apart (24 data + 8 header, 16-byte aligned)
malloc(200) after free reuses the same address: yesfirst fit: 212K->hole1, 417K->hole4, 112K->hole1, 426K:wait holes left [100, 176, 200, 300, 183]
best fit : 212K->hole3, 417K->hole1, 112K->hole2, 426K->hole4 holes left [100, 83, 88, 88, 174]
worst fit: 212K->hole4, 417K->hole1, 112K->hole4, 426K:wait holes left [100, 83, 200, 300, 276]
buddy allocator (1024 KB):
alloc A 70 KB -> 128 KB block at 0 (internal fragmentation 58 KB)
alloc B 35 KB -> 64 KB block at 128 (internal fragmentation 29 KB)
alloc C 80 KB -> 128 KB block at 256 (internal fragmentation 48 KB)
free lists: {64: [192], 128: [384], 512: [512]}
after freeing all, merged back to: {1024: [0]}Common Mistakes
Memory leaks (lost pointers), double free, use after free, writing past the end of a block (corrupts the allocator's headers).
Assuming free returns memory to the OS (heap memory usually stays in the process for reuse).
Allocating and freeing in tight loops in hot paths.
Using malloc in interrupt handlers or hard real-time code.
Best Practices
Use tools: AddressSanitizer (-fsanitize=address), Valgrind, LeakSanitizer.
Reuse buffers; use pools or arenas for many same-sized objects.
In embedded/safety code, allocate everything at start-up.
Consider jemalloc/tcmalloc/mimalloc for allocation-heavy multithreaded servers — measure first.
Interview Relevance
High: "how does malloc work?", "internal vs external fragmentation?", "first/best/worst fit?", "explain the buddy system", "what is a slab allocator?", "how would you find a memory leak?", "implement a fixed-size memory pool".
Practice Questions
Allocate 1 million 16-byte blocks and compare the process's RSS with 16 MB. Explain the difference.
Change the mmap threshold with mallopt(M_MMAP_THRESHOLD, ...) and rerun 21.1.
Simulate the buddy allocator with requests 100, 240, 64, 256 KB and free them in a different order.
Write a leak on purpose and find it with -fsanitize=address.
Quick Quiz
Q1. (Multiple choice) Rounding a 70 KB request up to 128 KB is: A) External fragmentation B) Internal fragmentation C) Thrashing D) Compaction Answer: B (verified: 58 KB wasted).
Q2. (Predict the output) Where does glibc place a 1 MB malloc by default?
Answer: In its own anonymous mmap, not in [heap] (verified).
Q3. (True/False) In the placement example, first fit fails to place 426 KB even though the free total exceeds 426 KB.
Answer: True (verified) — external fragmentation.
Q4. (Find the bug) char *s = malloc(strlen(src)); strcpy(s, src);
Answer: No room for the terminating '\0': allocate strlen(src) + 1 bytes (the overflow corrupts the next block's header).
Coding Challenge
Implement a fixed-size block pool (8 blocks of 32 bytes) with O(1) pool_alloc and pool_free using an embedded free list; allocate all blocks, show that a 9th allocation fails, free one and allocate again.
#include <stdio.h>
#include <stddef.h>
enum { BLOCKS = 8, BLOCK_SIZE = 32 };
typedef union Block { union Block *next; unsigned char data[BLOCK_SIZE]; } Block;
static Block pool[BLOCKS];
static Block *free_list;
static void pool_init(void)
{
for (int i = 0; i < BLOCKS - 1; i++) pool[i].next = &pool[i + 1];
pool[BLOCKS - 1].next = NULL;
free_list = &pool[0];
}
static void *pool_alloc(void)
{
Block *b = free_list;
if (b) free_list = b->next; /* pop the head of the free list */
return b;
}
static void pool_free(void *p)
{
Block *b = p;
b->next = free_list; /* push back onto the free list */
free_list = b;
}
int main(void)
{
pool_init();
void *blocks[BLOCKS];
for (int i = 0; i < BLOCKS; i++) blocks[i] = pool_alloc();
printf("9th allocation: %s\n", pool_alloc() ? "succeeded" : "failed (pool exhausted)");
pool_free(blocks[3]);
void *again = pool_alloc();
printf("after freeing block 3, allocation returns block %td\n", (Block *)again - pool);
return 0;
}