Why writing your own malloc teaches you more than reading about it.
Writing an allocator forces you to confront, in a single file, the relationship between a program, the kernel, and the memory model that sits between them.
Most working programmers use malloc the way most drivers use a gearbox: a familiar lever that does the thing. You ask for sixty-four bytes, sixty-four bytes appear; you give them back, they vanish. Behind that lever is a small, dense piece of software whose job is to keep the heap from devolving into chaos, and the only way to really feel how it works is to write one.
This article walks through an_malloc, the allocator I wrote after reading “malloc is not magic” and wanting to actually feel what was going on. It is not a production allocator. It is a teaching allocator — small enough to read in one sitting, complete enough to actually replace malloc for a real program, and honest about the trade-offs it makes.
What the allocator does, briefly:
- Grows the heap a page at a time with
sbrk(). - Tracks every region with a small header struct laid out in a doubly-linked list.
- Allocates with a best-fit policy, splitting blocks when the leftover is worth keeping.
- Coalesces adjacent free blocks on
free()and returns whole pages to the OS when possible. - Protects every public entry point with a single spinlock.
- Validates its own headers with a magic-number sentinel — the cheapest debugger you can build.
None of these ideas are new. The point is to put them together and watch them work.
The heap and sbrk().
sbrk() is the system call that moves the program break — the top of the data segment — up or down a fixed number of bytes, which is how an allocator grows and shrinks the heap.
Every process on Linux has a contiguous region of virtual memory called the data segment. The top of that segment is the program break. Calling sbrk(n) tells the kernel to bump the break up by n bytes and hand you back a pointer to where the break used to be — that is, the start of the new region.
It is the simplest interface to "more memory" that POSIX exposes. We will only ever ask for whole pages:
// allocator.h
// Custom memory allocator interface
#ifndef _ALLOCATOR_H
#define _ALLOCATOR_H
#include <unistd.h>
#include <stdbool.h>
#include <stdint.h>
#define PAGE_SIZE 4096
typedef uint8_t u8;
typedef uint16_t u16;
typedef uint32_t u32;
typedef uint64_t u64;
typedef int8_t i8;
typedef int16_t i16;
typedef int32_t i32;
typedef int64_t i64;
// Each block in the linked list carries this header
typedef struct free_area {
int marker; // BLOCK_MARKER sentinel
struct free_area *prev;
bool InUse;
u32 length; // payload size, header excluded
struct free_area *next;
} area;
// Heap-wide stats kept at the very start of the heap
typedef struct stast {
int magical_bytes; // ensures the allocator was initialized
bool my_simple_lock; // spin-style guard around malloc / free
u32 amount_of_blocks;
u32 amount_of_pages;
} my_stats;
void *heap_start = NULL;
void *heap_end = NULL;
#endifAnd growing the heap looks like this:
// allocator.c
#include <stdio.h>
#include <stdbool.h>
#include <unistd.h>
#include <assert.h>
#include <string.h>
#include <sys/wait.h>
#include <stdlib.h>
#include "allocator.h"
// MAGICAL_BYTES: stamped at the start of the heap to detect re-init
// BLOCK_MARKER : stamped on every block header to detect corruption
const int MAGICAL_BYTES = 0x55;
const int BLOCK_MARKER = 0xDD;A single byte of malloced memory still costs 4096 bytes of system memory the first time around. The whole game from here is making good use of that page.
The area block header and the global my_stats.
Every region of memory the allocator manages is preceded by a small header — a magic number, a size, a used flag, and pointers to the neighbours in a doubly-linked list.
The allocator needs to remember, for every region: how big it is, whether it is currently in use, and where its neighbours are. We store that in a header struct placed at the start of each region:
// get_malloc_header(): return the my_stats header that sits at heap_start
my_stats *get_malloc_headear() {
return (my_stats *)heap_start;
}
// find_last_block(): walk to the tail of the linked list
area *find_last_block() {
area *block = (area *)((char *)heap_start + sizeof(my_stats));
while (block->next != NULL) {
block = block->next;
}
return block;
}And we keep a single global to hold the heap's bookkeeping. It lives in BSS, costs us nothing at startup, and is the only mutable state outside the heap itself:
// an_malloc(): public entry point
// - on first call: grow heap by one page, lay down magical_bytes + my_stats
// - on every call: delegate to add_used_block()
//
// heap layout:
// [ my_stats | first_block payload ........... ]
// ^ ^
// heap_start heap_start + sizeof(my_stats)
int *an_malloc(ssize_t size) {
if (heap_start == NULL) {
heap_start = sbrk(0); // current top of the data segment
sbrk(4096); // grow heap by 1 page
}
heap_end = sbrk(0);
long int length = heap_end - heap_start;
// first execution? stamp the magical bytes and lay the first block
if (*(char *)heap_start != MAGICAL_BYTES) {
*(char *)heap_start = MAGICAL_BYTES;
my_stats *malloc_header = (my_stats *)heap_start;
malloc_header->amount_of_blocks = 1;
malloc_header->amount_of_pages = 1;
// the first block fills the heap; later we split it
area *fst_block = (area *)((char *)heap_start + sizeof(my_stats));
fst_block->marker = BLOCK_MARKER;
fst_block->prev = NULL;
fst_block->InUse = false;
fst_block->length = length - sizeof(my_stats) - sizeof(area);
fst_block->next = NULL;
}
return add_used_block(size);
}That is the entire data model. A list of headers, anchored at my_stats.head, that walks from low addresses to high. Every pointer the allocator hands out is just (char *)block + HEADER_SIZE. Every pointer we receive in an_free can be turned back into a header by subtracting HEADER_SIZE.
my_stats.head → list of area_block_t in address order
The first call to an_malloc() and the magic bytes.
On the first allocation the heap is empty, so we ask the kernel for a page, place a single free header at the start of it, and stamp every header we ever build with a magic number we can check later.
The first time an_malloc runs, my_stats.head is NULL. Before anything else can happen we have to seed the heap with at least one block:
// the magical_bytes check inside an_malloc() guarantees the heap was set up
// before any allocation happens. if my_malloc is called without initialising
// the allocator first, *(char *)heap_start will not equal MAGICAL_BYTES (0x55).
//
// my_simple_lock is a tiny mutex on the heap header; threads spin with sleep(1)
// until the holder releases it, which prevents two an_malloc / an_free calls
// from racing on the free list at the same time.
// example of how add_used_block() acquires the lock:
my_stats *malloc_header = get_malloc_headear();
while (malloc_header->my_simple_lock) {
sleep(1); // wait for the other thread to finish
}
malloc_header->my_simple_lock = true;
// ... critical section ...
malloc_header->my_simple_lock = false;The MAGICAL_BYTES field is the cheapest possible self-test. Every time we receive a pointer or walk a header, we check it:
// Every time we walk a block in the free list we assert its marker matches
// BLOCK_MARKER. If a write overflows the previous block's payload, the first
// thing it tramples is this byte on the next block's header — turning an
// invisible bug into a loud assertion failure.
while (block != NULL) {
assert(block->marker == BLOCK_MARKER);
// ... use block ...
block = block->next;
}If the user writes past the end of a buffer, the first thing they trample is the header of the next block. Eight known bytes at the start of every header turn an invisible bug ("the heap is mysteriously broken") into a loud one ("corrupted header at 0x7ff…"). For 8 bytes per allocation, that is an excellent trade.
Best-fit: add_used_block().
Best-fit walks every free block in the heap and picks the smallest one that is still large enough to hold the request, which minimizes wasted space but produces small leftover fragments.
The first interesting decision an allocator makes is which free block to use when several would fit. The three classic choices are:
- First-fit. Take the first block big enough. Fast, leaves big blocks alone for later, but slowly drifts toward fragmentation near the front of the heap.
- Best-fit. Walk every free block, pick the smallest that fits. Wastes the least per allocation, but produces tiny, unusable fragments.
- Worst-fit. Pick the biggest. Optimizes for the leftover being usable. In practice it is rarely a good idea.
I went with best-fit. It is a reasonable default for a teaching allocator: the policy is one line of code, and the consequences (small fragments) are exactly the kind of thing we want to see in the heap dump.
request: 40 B · candidates: every free block that fits
// best-fit search inside add_used_block(): walk every block, remember
// the smallest free one that still fits the request
area *block = (area *)((char *)heap_start + sizeof(my_stats));
area *smallest_block = NULL;
area *last_block = block;
while (block != NULL) {
assert(block->marker == BLOCK_MARKER);
// does this block fit the request and is it actually free?
if ((block->length + sizeof(area)) >= size && block->InUse == false) {
if (smallest_block == NULL || smallest_block->length > block->length) {
smallest_block = block;
}
}
last_block = block;
block = block->next;
}The public entry point is then just a matter of locking, possibly initializing, searching, possibly growing the heap, and handing the payload pointer back:
int *add_used_block(ssize_t size) {
// format heap_start with the shape of my_stats
my_stats *malloc_header = get_malloc_headear();
while (malloc_header->my_simple_lock) {
sleep(1); // wait for the other thread to finish
}
malloc_header->my_simple_lock = true;
// find the smallest free block that fits (best-fit)
area *block = (area *)((char *)heap_start + sizeof(my_stats));
area *smallest_block = NULL;
area *last_block = block;
while (block != NULL) {
assert(block->marker == BLOCK_MARKER);
if ((block->length + sizeof(area)) >= size && block->InUse == false) {
if (smallest_block == NULL || smallest_block->length > block->length) {
smallest_block = block;
}
}
last_block = block;
block = block->next;
}
// no block big enough — ask the OS for more pages until the tail fits
if (smallest_block == NULL) {
area *last_block = find_last_block();
while (last_block->length < size) {
sbrk(4096);
last_block->length += 4096;
malloc_header->amount_of_pages += 1;
}
smallest_block = last_block;
}
smallest_block->InUse = true;
// size of the leftover after carving the request out
// -1 guarantees the new leftover block holds at least 1 byte of payload
int must_have_size = smallest_block->length - size - sizeof(area) - 1;
if (must_have_size <= 0) {
sbrk(4096);
malloc_header->amount_of_pages += 1;
smallest_block->length += 4096;
must_have_size = smallest_block->length - size - sizeof(area) - 1;
}
int remaining_sizes = must_have_size + 1;
malloc_header->amount_of_blocks += 1;
// create the leftover block right after the carved-out payload
area *new_block = (area *)((char *)smallest_block + sizeof(area) + size);
new_block->marker = BLOCK_MARKER;
new_block->InUse = false;
new_block->length = remaining_sizes;
new_block->prev = smallest_block;
new_block->next = smallest_block->next;
if (new_block->next != NULL) {
(new_block->next)->prev = new_block;
}
smallest_block->next = new_block;
smallest_block->length = size;
malloc_header->my_simple_lock = false;
return (int *)((char *)smallest_block + sizeof(area));
}Creating the leftover block.
When the chosen free block is much larger than the request, we carve a new header out of its tail and turn the leftover into a fresh free block — otherwise we hand the block over whole and waste a few bytes.
If a request for 16 bytes lands on a 4000-byte free block, we obviously should not let those 16 bytes consume the whole region. We split it. The trick is deciding when splitting is worth it: a leftover that is smaller than a single header plus a useful payload is just clutter.
Pre malloc · the heap before the request
Post malloc · the chosen free block is carved in two
// after picking smallest_block and marking it in-use, we carve a new
// header out of its tail and turn the leftover into a fresh free block
int must_have_size = smallest_block->length - size - sizeof(area) - 1;
if (must_have_size <= 0) {
sbrk(4096); // not enough room — grow the heap
malloc_header->amount_of_pages += 1;
smallest_block->length += 4096;
must_have_size = smallest_block->length - size - sizeof(area) - 1;
}
int remaining_sizes = must_have_size + 1;
malloc_header->amount_of_blocks += 1;
// the new (free) block lives right after the now-used payload
area *new_block = (area *)((char *)smallest_block + sizeof(area) + size);
new_block->marker = BLOCK_MARKER;
new_block->InUse = false;
new_block->length = remaining_sizes;
new_block->prev = smallest_block;
new_block->next = smallest_block->next;
if (new_block->next != NULL) {
(new_block->next)->prev = new_block;
}
smallest_block->next = new_block;
smallest_block->length = size;Notice that maybe_split never touches the payload bytes. It rewrites four pointers and two sizes, full stop. The original block's contents are untouched. This is what lets you split mid-allocation without ever copying memory — splitting is metadata work, not data work.
an_free(), zeroing, and coalescing neighbours.
Freeing flips the used flag, zeros the payload as a safety net, and merges the block with any adjacent free neighbours so the heap does not slowly fragment into useless slivers.
The public an_free entry point is small:
bool an_free(void *ptr) {
bool marker_state;
my_stats *malloc_header = get_malloc_headear();
while (malloc_header->my_simple_lock) {
sleep(1);
}
malloc_header->my_simple_lock = true;
// each block has a header behind it; back up one header to reach it
area *block = ptr - sizeof(area);
if (block->marker != BLOCK_MARKER) {
marker_state = false; // header corrupted — refuse to free
} else {
block->InUse = false;
memset(ptr, 0, block->length); // wipe the payload (defensive)
// coalesce with the next neighbour if it is free
if (block->next != NULL && (block->next)->InUse == false) {
area *not_used_next_block = block->next;
block->next = not_used_next_block->next;
if (not_used_next_block->next != NULL) {
(not_used_next_block->next)->prev = block;
} else {
block->next = NULL;
}
block->length += not_used_next_block->length + sizeof(area);
memset((void *)not_used_next_block, 0,
sizeof(area) + not_used_next_block->length);
malloc_header->amount_of_blocks -= 1;
// coalesce with the previous neighbour if it is free too
if (block->prev != NULL && (block->prev)->InUse == false) {
area *to_delete_block = block;
block = block->prev;
block->length += to_delete_block->length + sizeof(area);
block->next = to_delete_block->next;
}
if (block->next != NULL) {
block->next->prev = block;
}
malloc_header->amount_of_blocks -= 1;
}
reduce_heap_size_if_possible();
marker_state = true;
}
malloc_header->my_simple_lock = false;
return marker_state;
}Zeroing the payload on free is not necessary for correctness, but it is the kind of cheap safety net that has saved me from more than one use-after-free bug in lab. The interesting work is in coalesce:
// merge with the next neighbour if it is free
if (block->next != NULL && (block->next)->InUse == false) {
area *not_used_next_block = block->next;
block->next = not_used_next_block->next;
if (not_used_next_block->next != NULL) {
(not_used_next_block->next)->prev = block;
} else {
block->next = NULL;
}
block->length += not_used_next_block->length + sizeof(area);
memset((void *)not_used_next_block, 0,
sizeof(area) + not_used_next_block->length);
malloc_header->amount_of_blocks -= 1;
// and merge with the previous neighbour if it is free too
if (block->prev != NULL && (block->prev)->InUse == false) {
area *to_delete_block = block;
block = block->prev;
block->length += to_delete_block->length + sizeof(area);
block->next = to_delete_block->next;
}
if (block->next != NULL) {
block->next->prev = block;
}
}Why coalescing matters
Without it, every free() leaves behind a small free island. After enough cycles the heap has plenty of free space in total, but not a single contiguous region big enough to satisfy a request — the worst kind of fragmentation, because it is invisible to the program until allocations start failing.
Before free(B)
After coalesce
reduce_heap_size_if_possible() and sbrk(-PAGE_SIZE).
If the last block in the heap is free and at least one page in size, we hand the page back to the kernel by calling sbrk() with a negative argument.
Growing the heap is half the story. A polite allocator gives memory back to the OS when it no longer needs it. The condition is strict: the last block in our list has to be free, and it has to be at least one full page wide:
void reduce_heap_size_if_possible() {
area *last_block = find_last_block();
area *prev_used_block = find_previous_used_block(last_block);
if (prev_used_block == NULL) {
if (last_block->length > PAGE_SIZE) {
last_block->length = PAGE_SIZE;
}
prev_used_block = last_block;
}
// new_end = where the last used block actually ends in memory
void *new_end = (void *)prev_used_block + sizeof(area) + prev_used_block->length;
void *heap_end = sbrk(0); // current top of the heap
// peel whole pages off the top while there is still room above new_end
while (new_end < heap_end - PAGE_SIZE) {
sbrk(-PAGE_SIZE); // return one page to the OS
heap_end = sbrk(0);
my_stats *malloc_header = get_malloc_headear();
malloc_header->amount_of_pages -= 1;
}
// most of the time there is a small gap between the last used block and
// the new heap top — fit a free block in there if it can hold at least 1 B
// [ last_block_used ][ leftover space ][ end of heap ]
if (heap_end - new_end > sizeof(area) + 1) {
area *new_not_used_block = (area *)new_end;
new_not_used_block->marker = BLOCK_MARKER;
new_not_used_block->InUse = false;
new_not_used_block->prev = prev_used_block;
new_not_used_block->next = NULL;
new_not_used_block->length = heap_end - new_end - sizeof(area);
prev_used_block->next = new_not_used_block;
}
}
// helper used by reduce_heap_size_if_possible(): walk backwards from a block
// until we find one that is in use (returns NULL if none exist)
area *find_previous_used_block(area *ptr) {
area *last_block = ptr->prev;
while (last_block != NULL) {
if (last_block->InUse == true) {
return last_block;
}
last_block = last_block->prev;
}
return NULL;
}The reason this only works at the tail is that sbrk() can only move the top of the heap. A free block in the middle of the heap stays where it is, no matter how big it gets.
The my_simple_lock spinlock pattern.
Every public entry point is wrapped in a one-byte atomic spinlock, which keeps the implementation single-threaded inside the allocator without paying for a kernel-level mutex.
The simplest correct lock you can write in C, given a modern compiler, is two lines:
// my_simple_lock lives inside my_stats (one bool at the start of the heap).
// Every public entry point grabs it before touching the free list and drops
// it on the way out. Threads that find it taken spin with sleep(1).
void critical_section_example() {
my_stats *malloc_header = get_malloc_headear();
while (malloc_header->my_simple_lock) {
sleep(1); // wait until the other thread releases
}
malloc_header->my_simple_lock = true;
// ... walk the free list, split, coalesce, etc. ...
malloc_header->my_simple_lock = false;
}A spinlock is the right tool for an allocator because the critical sections are tiny — a handful of pointer rewrites — and contention is rare. Going through the kernel for a futex on every malloc would dominate the cost of the allocation itself.
Real allocators (glibc, jemalloc, mimalloc) use per-thread arenas so threads almost never wait on each other. A single global spinlock is fine for a coursework allocator and a useful demonstration of why per-thread arenas exist.
call_test(), fork(), and four test cases.
Each test runs in its own forked child so a crash in one test cannot poison the others, and the parent process aggregates the exit codes.
An allocator is the kind of code where one buggy test can corrupt the heap for every test that follows it. The cleanest way to isolate test cases is to fork() a fresh process for each one and let the kernel hand us back a clean address space when the child dies:
// call_test(): run a single test in its own forked child so a crash in one
// test cannot corrupt the heap of the next one. The parent waits and prints
// whether the child died with a signal or exited cleanly.
void call_test(void (*test_func)(), const char *msg) {
pid_t pid = fork();
if (pid == 0) {
test_func();
exit(0);
} else {
int status;
waitpid(pid, &status, 0);
if (WIFSIGNALED(status)) {
printf("%s crashed with signal %d\n", msg, WTERMSIG(status));
} else {
printf("%s passed\n", msg);
}
}
}
// the four tests
void test_basic_malloc() {
int *ptr = (int *)an_malloc(sizeof(int));
assert(ptr != NULL);
*ptr = 42;
assert(*ptr == 42);
an_free(ptr);
}
void test_bigger_than_available_malloc() {
uint16_t *ptr = (uint16_t *)an_malloc(5000);
area *first_block = (void *)ptr - sizeof(area);
for (uint16_t i = 0; i <= 2499; i++) {
*(ptr + i) = i;
}
assert(first_block->marker == BLOCK_MARKER);
assert(*ptr == 0);
assert(*(ptr + 2499) == 2499);
}
void test_free() {
int *ptr = (int *)an_malloc(sizeof(int));
*ptr = 99;
bool result = an_free(ptr);
assert(result == true);
area *block = (area *)((char *)ptr - sizeof(area));
assert(block->InUse == false);
}
void complex_set_of_malloc_and_free_calls() {
int *a = (int *)an_malloc(sizeof(int));
int *b = (int *)an_malloc(sizeof(int) * 10);
int *c = (int *)an_malloc(sizeof(int) * 100);
*a = 1;
for (int i = 0; i < 10; i++) *(b + i) = i;
for (int i = 0; i < 100; i++) *(c + i) = i;
assert(*a == 1 && *(b + 9) == 9 && *(c + 99) == 99);
an_free(b); an_free(a); an_free(c);
int *d = (int *)an_malloc(sizeof(int));
*d = 77;
assert(*d == 77);
an_free(d);
}
int main() {
call_test(test_basic_malloc, "Basic Malloc");
call_test(test_bigger_than_available_malloc,"Request more memory Malloc");
call_test(test_free, "Basic Free");
call_test(complex_set_of_malloc_and_free_calls, "Complex");
printf("DONE\n");
return 0;
}What each test checks
- basic malloc/free. Allocate, write a byte pattern, read it back, free. The bottom of the pyramid.
- split and coalesce. Allocate three blocks, free the middle one, then free the outer two and assert the heap is back to a single block.
- shrink after big free. Allocate something larger than a page, free it, and check that
sbrk()moved the program break down. - many small allocs. Run 10 000 small allocations and frees in random order — a smoke test for fragmentation and header corruption.
Why -D_DEFAULT_SOURCE is needed with -std=c99.
Under strict C99 the compiler does not expose POSIX extensions, so sbrk() is not declared in unistd.h unless you ask for them with the _DEFAULT_SOURCE feature-test macro.
The first time I compiled with -std=c99 -Wall -Wextra I got two warnings I did not understand:
allocator.c: implicit declaration of function 'sbrk' [-Wimplicit-function-declaration]
allocator.c: implicit declaration of function 'fork' [-Wimplicit-function-declaration]The compiler was right. sbrk() and fork() are POSIX extensions, not part of ISO C99. Under -std=c99 the headers hide every declaration that is not in the C standard. The fix is to enable the feature test macro that re-exposes the BSD/POSIX corner of glibc:
# Two ways to compile this allocator
# Option A: no strict standard — sbrk() is declared by default
gcc -Wall -Wextra -g allocator.c -o test
# Option B: strict C99 + POSIX feature-test macro
gcc -Wall -Wextra -g -D_DEFAULT_SOURCE -std=c99 allocator.c -o test
# Why? sbrk() is a POSIX extension. With -std=c99 alone, glibc hides its
# declaration in <unistd.h>, so the compiler assumes sbrk() returns int
# (32 bits) instead of void * (64 bits). The truncated pointer segfaults
# at runtime. -D_DEFAULT_SOURCE re-exposes the BSD/POSIX corner of glibc.With -D_DEFAULT_SOURCE the compiler stays in C99 mode for the language itself, but the library headers behave the way they would on a normal POSIX system. sbrk() is declared, fork() is declared, and everything builds clean.
Older glibc used _BSD_SOURCE for this; it was renamed to _DEFAULT_SOURCE in glibc 2.20 (2014). On any modern Linux you want the new name.
What this taught me.
Three things stayed with me after writing this:
- The interface between a process and the kernel is small. Two pointers and a system call get you a heap.
- Most of the difficulty of a real allocator is not the algorithm. It is the boundary cases — empty heap, page-aligned frees, the tail block, the lock — and the day-to-day work of not getting them wrong.
- A magic byte at the top of every header is worth every cycle it costs.
The source code, the tests, and the Makefile live in the repository on GitHub. If you find a bug — and there will be bugs — open an issue. I will probably learn more from it than you will.
Frequently asked questions
How does a custom memory allocator work in C?
It asks the operating system for raw memory through sbrk() or mmap(), divides that memory into blocks tracked by tiny metadata headers, and serves allocation requests by finding a free block large enough to fit. On free, adjacent free blocks are merged (coalesced) and whole pages are returned to the OS when possible.
What is sbrk() and why do allocators use it?
sbrk() is a POSIX system call that moves the program break — the top of the data segment — up or down. sbrk(PAGE_SIZE) extends the heap by one page; sbrk(-PAGE_SIZE) returns a page back to the OS. It is the simplest interface a Unix-like kernel offers for growing and shrinking the heap, which is why teaching allocators almost always start there.
What is best-fit allocation?
Best-fit walks the list of free blocks and picks the smallest block that is still large enough to hold the request. It minimizes wasted space inside the chosen block, but tends to leave small, hard-to-reuse fragments behind. Real allocators usually use segregated free lists or slab allocators instead, but best-fit is a great teaching policy because the trade-off is visible.
Why must adjacent free blocks be coalesced?
Without coalescing, every free() leaves behind a separate small free block. After many allocate/free cycles the heap fragments into pieces too small to satisfy larger requests, even though the total free space would be enough. Merging adjacent free blocks restores the long contiguous regions that real workloads need.
Why is -D_DEFAULT_SOURCE required to compile?
Under -std=c99 the compiler only exposes ISO C99 declarations in the standard headers. sbrk() is a POSIX/BSD extension, so without -D_DEFAULT_SOURCE (or _BSD_SOURCE on older glibc) it is not declared in unistd.h and the program will not compile cleanly.