11.2 Dynamic Memory Allocator

The central warehouse receives a requisition form with only malloc(24). Twenty-four bytes are scarce, yet the warehouse can't just arbitrarily carve out a piece from the ground: addresses must be aligned, multiple threads might request simultaneously, holes returned must be reused, and large blocks must be returned to the operating system at appropriate times.

11.1 How Locks Work appears in these paths, but the allocator isn't simply "a free list with a global lock." Modern implementations classify memory by size, batch allocate from the operating system, and use thread caches or multiple arenas to reduce shared hotspots. This lesson first builds a small, manageable warehouse to illustrate the concept, then explains why real allocators are more complex.

1. First, clarify the interface contract

In C, dynamic allocation involves at least four commonly used interfaces:

Interface	Purpose	Easy-to-overlook points
malloc(n)	Allocated at least n bytes	Content not initialized
calloc(count, size)	Allocate an array and clear all bits to zero	Needs to handle multiplication overflow
realloc(p, n)	Adjust an existing allocation	May move; original block remains valid on failure
free(p)	Ends the allocated lifetime of an object	free(NULL) No operation

The address returned by malloc satisfies the basic alignment requirements for objects; stronger alignment is required when using specialized interfaces such as aligned_alloc. Requesting 0 bytes may return either a null pointer or a non-null pointer suitable for passing to free, and the program should not dereference it.

A non-empty pointer passed to free must come from an allocation function and have not been freed. Reading or writing after freeing is use-after-free; freeing twice is double free. Neither is "just occasionally wrong", both are undefined behavior.

Array size must be checked first to prevent overflow

The following check must occur before the multiplication:

#include <stdint.h>
#include <stdlib.h>

void *allocate_array(size_t count, size_t element_size) {
    if (count != 0 && element_size > SIZE_MAX / count) {
        return NULL;
    }
    return malloc(count * element_size);
}

Otherwise, a large count * element_size might wrap around into a fractional value, and subsequently writing back using the original number of elements could result in buffer overflow. On some platforms, calloc will perform such checks for the caller, but explicit handling is still required when calculating the total byte count.

realloc Do not directly overwrite the original pointer:

void *new_buffer = realloc(buffer, new_size);
if (new_buffer == NULL && new_size != 0) {
    /* buffer Still valid */
    handle_allocation_failure();
} else {
    buffer = new_buffer;
}

2. An Honest Minimal Model: Fixed-Block Memory Pool

It's easy to mess up alignment, splitting, merging, and error paths when writing a compact version malloc. A fixed-size memory pool is better for first-time implementation: pre-allocate several blocks of equal size at initialization, link the free blocks together with a singly linked list, and keep allocation and deallocation simple by just modifying the list head.

#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <string.h>

enum { BLOCK_SIZE = 64, BLOCK_COUNT = 128 };

typedef union block {
    max_align_t alignment;
    unsigned char bytes[BLOCK_SIZE];
    union block *next;
} block_t;

typedef struct {
    block_t blocks[BLOCK_COUNT];
    block_t *free_head;
} pool_t;

_Static_assert(sizeof(block_t) >= BLOCK_SIZE,
               "block is smaller than its payload");

static void pool_init(pool_t *pool) {
    for (size_t i = 0; i + 1 < BLOCK_COUNT; ++i) {
        pool->blocks[i].next = &pool->blocks[i + 1];
    }
    pool->blocks[BLOCK_COUNT - 1].next = NULL;
    pool->free_head = &pool->blocks[0];
}

static void *pool_alloc(pool_t *pool) {
    block_t *block = pool->free_head;
    if (block == NULL) {
        return NULL;
    }
    pool->free_head = block->next;
    return (void *)block;
}

static int pool_owns(const pool_t *pool, const void *pointer) {
    uintptr_t begin = (uintptr_t)&pool->blocks[0];
    uintptr_t end = (uintptr_t)&pool->blocks[BLOCK_COUNT];
    uintptr_t address = (uintptr_t)pointer;

    return address >= begin
        && address < end
        && (address - begin) % sizeof(block_t) == 0;
}

static int pool_free(pool_t *pool, void *pointer) {
    if (pointer == NULL) {
        return 1;
    }
    if (!pool_owns(pool, pointer)) {
        return 0;
    }

    block_t *block = pointer;
    block->next = pool->free_head;
    pool->free_head = block;
    return 1;
}

int main(void) {
    pool_t pool;
    void *items[BLOCK_COUNT];
    pool_init(&pool);

    for (size_t i = 0; i < BLOCK_COUNT; ++i) {
        items[i] = pool_alloc(&pool);
        if (items[i] == NULL) {
            return 1;
        }
        memset(items[i], (int)i, BLOCK_SIZE);
    }

    if (pool_alloc(&pool) != NULL) {
        return 2;
    }

    for (size_t i = 0; i < BLOCK_COUNT; ++i) {
        if (!pool_free(&pool, items[i])) {
            return 3;
        }
    }

    puts(pool_alloc(&pool) != NULL ? "reused" : "failed");
    return 0;
}

Compile and run:

cc -std=c17 -O2 -Wall -Wextra pool.c
./a.out
# reused

This example ensures each block is at least 64 bytes and uses max_align_t to provide the necessary alignment for basic types. It still has clear boundaries:

• Capacity and block size are fixed;
• Not thread-safe;
• Does not detect duplicate releases;
• pool_free accepts only the address as originally returned by pool_alloc;
• It doesn't request or return pages to the operating system.

These constraints aren't footnotes; they're part of the interface. A specialized object pool will have a very short path if it can accommodate these limitations; if it requires arbitrary sizing, concurrency, and error resilience, its complexity will quickly approach that of a general-purpose allocator.

3. Modify Warehouse to Accept Variable-Size Issue Orders

A fixed-size block pool is like a shelf where every bin is the same size, fast, but it wastes space for items that don't fit. Since actual material requisition forms vary in size, the allocator must cut up large free blocks, consolidate adjacent gaps, and balance speed, fragmentation, and metadata overhead.

Suppose the allocator holds a 128-byte free region and is asked for 40 bytes; it can split it into "allocated 40" and "remaining free 88". In reality, block headers, alignment, and minimum allocatable size must also be considered:

Initial:
[                 free 128                 ]

After splitting:
[ header | used 40 ][ header | free remainder ]

After the middle block is released:
[ used ][ free A ][ used ][ free B ]

Merge and consolidate adjacent free blocks:
[ used ][          larger free           ]

A typical design saves the size and state of blocks and organizes free blocks into linked lists, trees, or bins sorted by size. When allocating, it must select a candidate block:

• first fit finds the first large enough block; searches for short blocks but layout is affected by order;
• best fit finds the closest-fit block, possibly reducing leftover space but increasing search cost;
• Size class maps sizes to fixed bins, offering fast lookup but rounding off requests.

When freeing, the allocator attempts to merge with adjacent free blocks. Boundary tags help locate the previous block from the end, but richer metadata consumes more space and increases the attack surface.

4. Two fragments aren't the same issue

Internal fragmentation occurs within allocated blocks. For example, when requesting 33 bytes, the size category allocates 48 bytes, and the unused portion within that block cannot be given to another request. Alignment, size rounding, and partial metadata overhead all contribute to this kind of waste.

External fragmentation occurs between allocated blocks. The total amount of free space may be sufficient, but it is fragmented into disjoint, non-adjacent pieces that cannot satisfy a large contiguous request.

General heap allocation typically can't arbitrarily move active objects because C pointers might be scattered throughout the program. If a garbage collector runtime can update references, it has the opportunity to compress objects, this is another memory model.

Fragmentation can't be judged solely by examining the process virtual address space. You also need to distinguish:

• The number of bytes requested;
• The allocator retains but currently unused bytes;
• Mapped virtual memory;
• Pages currently residing in physical memory.

"Releasing an object without an immediate drop in RSS" doesn't mean memory leak, freed blocks might remain in the allocator for reuse, and pages might not be returned to the system because they still contain active objects.

5. The Boundary Between Allocators and the Operating System

Allocators typically fetch virtual memory in bulk from the operating system and then divide it into smaller chunks as needed. On class Unix systems, the underlying sources may include:

• Adjust the brk path for program break;
• Establish an independent virtual mapping path mmap;
• Pages in already acquired large regions that are not yet used.

Whether large or small requests use a particular path, or at what threshold pages are returned, are implementation strategies that may vary by version, configuration, and runtime state. Applications should not assume that "every malloc results in a system call" or "every free returns memory to the kernel."

The demand paging introduced in Chapter 6 also applies here: acquiring a virtual address does not mean that the corresponding physical page is already fully in memory. A page fault may occur and a mapping may be established only upon the first access to the page.

6. Thread Pool Scaling: Reduce Sharing Before Replacing the Lock

If all threads go through the same idle linked list and the same lock, allocation hotspots become serialized. Engineering implementations typically combine the following strategies:

Multiple arena or heap regions. Different threads can allocate memory in different regions, reducing contention on a single global lock. The number of arenas is not simply tied to the number of threads or CPUs; the specific strategy is part of the implementation details.

Thread-local caching. Frequently used small blocks are temporarily held near the current thread, avoiding many allocations and deallocations from touching shared structures. The cost is that memory is scattered across thread-local caches, requiring special handling for cross-thread deallocations and thread termination, including transfer or cleanup.

Size categories and bulk allocation. Objects of the same size use the same free list; threads cache a batch of allocations from the central structure and then distribute them individually to the application. This trades more temporary memory for reduced synchronization.

Per-CPU cache. Some runtimes or kernel allocators place hot structures locally on each CPU, reducing cross-core writes to shared memory. Thread migration, NUMA distance, and recycling balance become new concerns.

These designs explain a common phenomenon: increasing concurrent allocation throughput can lead to higher memory peak usage. The more thoroughly a memory is fragmented, the harder it becomes for idle space to be immediately reused by other fragments.

7. Don't Confuse Kernel Objects with User Heap

The Linux kernel uses a buddy system to manage large page blocks organized in powers of two, and then reuses small objects of fixed type or size via slab allocators. User-space malloc manages objects within a process's address space, operating at a different level.

"The buddy system has less fragmentation" also needs qualification: it facilitates quick consolidation of buddies of the same order and efficient acquisition of page blocks, but upward rounding causes internal waste, and prolonged operation may still face insufficient higher-order page blocks. Slab-based caching reduces initialization overhead by reusing pre-constructed objects and improves the layout of small objects.

8. Failure, Security, and Observability

Allocation failure isn't limited to just "physical memory exhaustion." Limits on address space, process quotas, mapping counts, and excessively large contiguous requests can all result in a null pointer. Linux's memory overcommitment also means that "allocation success" does not guarantee that future pages can be used without fail. Reliable programs must explicitly define failure strategies.

Stack errors typically come to light only after a failure has occurred:

• Writing past bounds that corrupts adjacent object or allocator metadata;
• use-after-free reads a newly allocated object that has been reused;
• double free: freeing the same block multiple times in a free list;
• Integer overflow causes insufficient allocation;
• Cross-allocating and releasing among different distributors.

AddressSanitizer, Valgrind-like tools, and allocator diagnostics can bring errors close to their point of occurrence. For production troubleshooting, you should simultaneously monitor allocation rates, live objects, peaks, size distributions, thread caches, page faults, and RSS, avoiding the blanket assumption that all growth constitutes a leak.

9. When Is It Worth Customizing?

Custom allocation strategies typically require clear lifecycle or size patterns:

• A batch of objects can be created and destroyed simultaneously, using an arena/region, releasing the entire region at once;
• Object sizes are fixed and have a clear upper limit, so a fixed-block pool can be used;
• Real-time paths can't tolerate unpredictable searches and system calls; they can be pre-allocated;
• Frequent temporary objects can use stack allocation or a bump allocator.

If objects are arbitrarily deallocated, cross-thread passed, or significantly sized, and require interoperability with general-purpose libraries, mature general-purpose allocators are often safer. Custom solutions must also define alignment, failure handling, thread safety, ownership, and diagnostic interfaces; simply implementing an empty free list is far from sufficient.

10. Summary

The allocator makes a set of mutually constraining choices:

• Increases utilization by splitting, but adds metadata and merge overhead;
• Shortens lookup by size category but introduces internal fragmentation;
• Arena and thread cache reduce contention but may increase memory retention;
• Batch memory allocation from the operating system reduces system calls, yet causes free and RSS to desynchronize.

Fixed block pools make the minimal mechanism visible, while a general malloc must handle arbitrary sizes, concurrency, fragmentation, and error protection. Understanding this gap is more useful than memorizing a specific implementation's threshold.

The next chapter delves into deadlock. The allocator must also acquire multiple locks; once the locking order is inconsistent, even a finely tuned idle structure may stall indefinitely.