11.2 Dynamic Memory Allocator
malloc(24) requests only 24 bytes, but an allocator cannot return an arbitrary region. The address must satisfy alignment requirements, multiple threads may allocate concurrently, freed holes should be reused, and large regions may need to return to the operating system.
11.1 How Locks Work appears in these paths, but an allocator is not simply "a free list with a global lock." Modern implementations classify memory by size, acquire memory from the operating system in batches, and use thread caches or multiple arenas to reduce shared hotspots. This lesson first implements a small fixed-block pool that can be reasoned about, then explains why production 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) | Allocates 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 | For positive sizes, may move; original remains valid on failure |
free(p) | Ends the allocated lifetime of an object | free(NULL) does nothing |
The address returned by malloc satisfies the basic alignment requirements for objects; use a dedicated interface such as aligned_alloc for stronger alignment, satisfying its supported-alignment and size-multiple requirements. calloc clears all bits; C does not guarantee that all-zero bits represent every implementation’s null pointer or floating-point zero. 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-null pointer passed to free must be the unchanged result of a compatible allocator and not already freed; an interior pointer is invalid. 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 smaller integer, and subsequently writing back using the original number of elements could result in buffer overflow. calloc receives two separate arguments and can detect multiplication overflow and fail. Passing an already-wrapped byte count to malloc has lost the information needed for that check.
Do not overwrite the original pointer directly with realloc. Handle zero size with free explicitly to avoid version and implementation differences; realloc(p, 0) is undefined in C23. Place this fragment inside a function after including stdlib.h. buffer must be a valid allocation or NULL; the application supplies the failure handler:
if (new_size == 0) {
free(buffer);
buffer = NULL;
} else {
void *new_buffer = realloc(buffer, new_size);
if (new_buffer == NULL) {
/* The old buffer remains valid. */
handle_allocation_failure();
} else {
buffer = new_buffer;
}
}2. A Minimal Fixed-Block Byte Pool
It's easy to mess up alignment, splitting, merging, and error paths when writing a compact version of 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 allocate from the list head. This example linearly checks block membership before returning a block to the list. Save as pool.c.
#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) {
for (size_t i = 0; i < BLOCK_COUNT; ++i) {
if (pointer == (const void *)&pool->blocks[i]) {
return 1;
}
}
return 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;
}
}
void *reused = pool_alloc(&pool);
puts(reused != NULL ? "reused" : "failed");
return reused != NULL ? 0 : 4;
}Compile and run:
cc -std=c17 -O2 -Wall -Wextra -Werror pool.c
./a.out
# reusedEach block has at least 64 bytes and fundamental alignment through max_align_t. The pool has a declared C type: it supplies storage for byte access or memcpy, not permission to cast the result to any T* and dereference it merely because alignment matches. A typed pool can include its payload type in the union; generic object storage must separately satisfy C effective-type rules. It still has clear boundaries:
- Capacity and block size are fixed; the pool must stay at the same address and must not be copied while in use;
- Not thread-safe;
- Does not detect double returns or stale handles; each allocation must be returned once;
pool_freeaccepts only the address as originally returned bypool_alloc;- It doesn't request or return pages to the operating system.
Membership checks use pointer equality instead of assuming uintptr_t ordering matches object layout. Validation takes O(BLOCK_COUNT) comparisons; the free-list update itself is O(1). These constraints are 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. Extend Fixed Blocks to Variable Sizes
A fixed-size block pool is fast, but it wastes space on smaller requests and cannot serve requests larger than one block. With variable-size allocations, the allocator must split large free blocks, coalesce adjacent holes, 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 stops at the first sufficient block, but may scan the whole free list in the worst case; layout depends on 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. Internal and External Fragmentation
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 compact objects; that requires a different 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;
- Bytes retained by the allocator but currently unused;
- 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 Unix-like systems, the underlying sources may include:
- Adjusting the program break through brk;
- Creating independent virtual mappings through 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. Scaling Concurrent Allocation by Reducing Sharing
If all threads go through the same free 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 allocation is partitioned, the harder it becomes for free space in one partition to serve another immediately.
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 caches reuse fixed-size objects and improve layout. Where supported and configured, constructors can preserve some initialized state; each use still needs the field initialization required by the object’s interface.
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.
Heap errors often become visible only after corruption 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;
- Allocating with one allocator and freeing with an incompatible one.
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, passed between threads, or vary widely in size, 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 a 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
freeand 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 covers deadlock. The allocator must also acquire multiple locks; once the locking order is inconsistent, even a carefully designed free-list structure may stall indefinitely.