§17.2Low-level Mechanisms

Before any policy questions — which chunk should serve a request? — come the mechanisms every allocator shares: cutting chunks, merging chunks, remembering sizes, and the neat trick of storing the free list in the very memory it tracks.

Splitting and Coalescing

Recall the 30-byte heap and its two-entry free list. A request bigger than 10 fails; a request for exactly 10 fits either chunk. But a request for 1 byte? The allocator performs splitting splitting Allocator mechanism: when a request is smaller than any free chunk, split one chunk in two — return the first piece to the caller, keep the remainder on the free list. defined in ch. 17 — open in glossary : pick a chunk, cut it in two, return the first piece, keep the rest listed. Serving that 1 byte from the second chunk:

The corollary mechanism runs the other way. Suppose the middle 10 bytes (the used ones) are freed. Add them to the list without thinking and the whole heap is free — but the list says three shards:

Coalescing coalescing Allocator mechanism: when memory is freed, merge it with any address-adjacent free chunks into one larger chunk — without it, a fully-free heap can still look fragmented into useless pieces. defined in ch. 17 — open in glossary fixes it at free time: look at the addresses of the returning chunk and its neighbors; if they sit adjacent, merge them into one larger chunk. Large extents stay visible to the list, not just theoretically present.

Tracking The Size Of Allocated Regions

free(void *ptr) takes no size — so the library stashes one. Most allocators keep a small header allocation header A small block the allocator stores just before each handed-out chunk (minimally its size, often a magic number for integrity), letting free(ptr) deduce the region's size — so a request for N bytes really searches for N + header bytes. defined in ch. 17 — open in glossary in memory just before each handed-out chunk:

typedef struct {
    int size;
    int magic;
} header_t;

On free(ptr), simple pointer arithmetic recovers the header:

void free(void *ptr) {
    header_t *hptr = (header_t *) ptr - 1;
    assert(hptr->magic == 1234567);   // integrity check
    // freed region size = hptr->size + sizeof(header_t)
    ...
}

Note the small but critical detail: the freed region’s size is the header plus the payload. So when a user requests N bytes, the library doesn’t hunt for a chunk of size N — it hunts for N + the header size. Request 100, consume 108.

Embedding A Free List

The list needs nodes; nodes need memory; and the one thing a memory allocator cannot do is call malloc() for its own bookkeeping. The escape: build the list inside the free space itself.

typedef struct __node_t {
    int              size;
    struct __node_t *next;
} node_t;

// mmap() returns a pointer to a chunk of free space
node_t *head = mmap(NULL, 4096, PROT_READ|PROT_WRITE,
                    MAP_ANON|MAP_PRIVATE, -1, 0);
head->size   = 4096 - sizeof(node_t);
head->next   = NULL;

Each free chunk’s own first bytes describe it. Step through the book’s 4KB heap — init, three allocations, a free, a mess, and the merge that heals it:

Growing The Heap

And if the heap simply runs out? The simplest answer: fail. Returning NULL is an honorable approach — you tried, and though you failed, you fought the good fight. Most traditional allocators, though, start small and ask the OS for more: the sbrk() negotiation from the segmentation chapter — the OS finds free physical pages, maps them into the address space, and returns the new end of the heap. A bigger arena, same mechanisms.