39. Writing a real allocator: free lists, coalescing, and dlmalloc's ideas

malloc/free (Section 10) aren't magic — they're a C library on top of the OS's mmap/sbrk syscalls. Here's a simplified allocator using the same free-list-with-coalescing idea as Doug Lea's dlmalloc (the design most production allocators, including glibc's, descend from):

#include <stddef.h>
#include <sys/mman.h>

typedef struct Block {
    size_t       size;    // payload size, not including this header
    int          free;
    struct Block *next;   // next block in address order (for coalescing)
} Block;

#define HEADER_SIZE sizeof(Block)
static Block *heap_start = NULL;

static Block *request_from_os(size_t size) {
    size_t total = size + HEADER_SIZE;
    Block *b = mmap(NULL, total, PROT_READ | PROT_WRITE,
                     MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
    if (b == MAP_FAILED) return NULL;
    b->size = size;
    b->free = 0;
    b->next = NULL;
    return b;
}

void *my_malloc(size_t size) {
    Block *b = heap_start, *prev = NULL;
    while (b) {                                    // first-fit search of the free list
        if (b->free && b->size >= size) { b->free = 0; return (char *)b + HEADER_SIZE; }
        prev = b;
        b = b->next;
    }
    Block *new_block = request_from_os(size);       // nothing fit — ask the OS for more
    if (!new_block) return NULL;
    if (prev) prev->next = new_block; else heap_start = new_block;
    return (char *)new_block + HEADER_SIZE;
}

void my_free(void *ptr) {
    if (!ptr) return;
    Block *b = (Block *)((char *)ptr - HEADER_SIZE);  // walk back to the header — same trick as sds (Section 34)
    b->free = 1;

    // Coalesce adjacent free blocks so a big enough contiguous run is
    // available for future large allocations, instead of staying
    // fragmented into many small free blocks forever.
    Block *cur = heap_start;
    while (cur && cur->next) {
        if (cur->free && cur->next->free) {
            cur->size += HEADER_SIZE + cur->next->size;
            cur->next = cur->next->next;
        } else {
            cur = cur->next;
        }
    }
}

The (char *)ptr - HEADER_SIZE trick to recover the header from the pointer malloc handed out is the exact same pattern as Section 34's sds header and Section 19's container_of — "hide bookkeeping data immediately before/around the pointer you give the caller" is one idea that recurs across allocators, dynamic strings, and intrusive containers because it lets the caller treat the returned pointer as if it were the raw payload, with zero extra indirection.

Real-world example. First-fit (used above) is the simplest strategy; real allocators use segregated free lists (separate lists per size class, so small allocations never have to scan past large free blocks) and per-thread arenas (so threads don't contend on one global free list) — exactly the optimizations that separate dlmalloc from ptmalloc2 (glibc's allocator) from jemalloc/tcmalloc (used by Firefox/Chrome and many high-throughput servers respectively).