I wanted to understand how malloc actually works under the hood.
Most explanations I found online described what an allocator does, but completely skipped over the "why" behind its design decisions. Rather than stopping at theory, I decided to build a cross-platform allocator in C that implements malloc, calloc, realloc, and free from scratch.
This article documents the design of that allocator, the architectural tradeoffs I faced, and the core concepts I had to learn along the way.
Table Of Contents
Project Overview
A custom memory allocator does not create physical memory. Instead, it requests pages of raw virtual memory from the operating system and manages how that memory is partitioned, reused, resized, and released by the application.
The goal of this educational project is to implement C's core memory management API using a modular, cross-platform architecture inspired by design principles found in modern allocators, rather than relying on legacy, single-platform tricks.
Design Decisions
#1: Why I am Skipping sbrk
While many classic tutorials use sbrk for educational implementations, I deliberately chose a 100% mmap-based approach for two major reasons:
-
sbrkis a fragile global bottleneck. It works by moving a single pointer (the program break) up and down. This means the allocator assumes it owns a contiguous line of memory. If a third-party library or another thread in the program secretly callssbrkbehind the scenes, the allocator's memory layout can break instantly.mmap, by contrast, provides isolated, independent chunks of memory. -
Cross-Platform Symmetry. Windows has absolutely no equivalent to
sbrk, but it has a direct equivalent tommap:VirtualAlloc. If we usedsbrk, our architectural abstraction (os_alloc) would become awkward because Linux would deal with a moving pointer while Windows dealt with independent pages. Usingmmapkeeps the abstraction perfectly symmetrical: we ask for $N$ pages of memory, and the OS gives us a pointer.
#2: Scope
This project implements a cross-platform, page-backed explicit free-list memory allocator in C.
- Cross-platform because the allocator separates platform-specific memory acquisition (mmap on Linux and VirtualAlloc on Windows) from the allocator logic.
- Page-backed because it requests memory from the operating system in page-sized chunks instead of relying on the legacy sbrk interface.
- Explicit free-list because free memory blocks are tracked using an explicit linked list, allowing blocks to be reused, split, and coalesced over time.
- Modular because the allocator logic is isolated from platform-specific memory acquisition through a small OS abstraction layer.
This is not an arena allocator, a toy bump allocator, slab allocator, or production-grade allocator. The goal is to build a clean, modular allocator that demonstrates the fundamental algorithms and data structures behind dynamic memory management while remaining portable across Linux and Windows.
Architecture and Platform Abstraction
To keep the codebase clean, we decouple the high-level allocation logic (which is identical across platforms) from the low-level OS system calls. The only platform-specific layer is responsible for fetching and releasing large chunks of virtual memory.
Mental Model to Keep
Project Directory Structure
OS Abstraction Layer
The entire platform-specific interface is reduced to just two primary functions declared in os.h:
See the os.h header file
void *os_alloc(size_t size);
void os_free(void *ptr, size_t size);
-
Linux Backend: Maps to
mmapandmunmap. -
Windows Backend: Maps to
VirtualAllocandVirtualFree.
By abstracting these calls, core features like block headers, free-list management, memory splitting, coalescing, and data alignment remain completely platform-independent.
Modern Allocator Strategies
Historically, general-purpose allocators relied heavily on brk/sbrk for heap growth and used mmap primarily for larger allocations.
Modern production-grade allocators take a page-based or arena-based (extremely fast, used in games, compilers, parsers - where many objects have the same lifetime.) approach to minimize fragmentation and maximize multi-threaded performance:
| Allocator | Strategy |
|---|---|
glibc malloc |
Dynamically mixes brk for small, short-lived objects and mmap for larger allocations. |
jemalloc |
Heavily relies on mmap to allocate large chunks ("extents"), optimizing for multi-threaded concurrency and core scaling. |
mimalloc |
Uses page mapping (mmap/VirtualAlloc) to slice memory into uniform-sized blocks, prioritizing predictability and free-list security. |
tcmalloc |
Thread-Caching allocator that utilizes a centralized page heap manager to distribute thread-local memory structures rapidly. |
Core Concept
Virtual Memory
Before an allocator can manage memory, it's important to understand what kind of memory it is actually managing.
User programs do not manipulate physical RAM directly. Instead, every process is given its own virtual address space by the operating system. The kernel maps these virtual addresses onto physical memory as needed, providing isolation between processes and allowing techniques such as demand paging, memory mapping, and copy-on-write.
| Region | Address Direction | Access Rights | Contents & Description |
|---|---|---|---|
| Protected Kernel Space | High to Low | Kernel Only (No User Access) | Operating system core, page tables, and drivers. |
| Stack | High to Low | r-w | Function arguments, local variables, and return addresses. |
| Mapped Memory | High to Low | r-w-x (Depends) | Memory-mapped files (mmap), shared libraries, and thread-local storage. |
| Heap | High to Low | r-w | Dynamically allocated memory (e.g., via malloc in C or new in C++). |
| Program Break (brk) | High to Low | r-w | The boundary/break marking the end of the data segment. It's not an actual region. |
| Text Segment | Low to High | r-x | The compiled machine code/instructions of the program. |
Pages
Virtual memory is divided into fixed-size pages (typically 4 KiB on x86-64 Linux). The operating system maps and protects memory one page at a time rather than one byte at a time.
Consequently, functions like mmap() and VirtualAlloc() allocate memory in page-sized units. Our allocator will request pages from the operating system and then subdivide them into smaller blocks that satisfy individual malloc() requests.
OS Level: [ 4 KiB Page ] -> [ 4 KiB Page ]
↓ ↓
Allocator: [Block][Block][Block] [Block][Block][Block]
This difference in granularity is the entire reason memory allocators exist. The OS manages the pages; our allocator manages the blocks within them.
Anonymous Mapping
This allocator requests anonymous memory mappings rather than mapping files. An anonymous mapping is simply a region of virtual memory backed by the OS rather than a file on disk. Anonymous pages are zero-filled when first mapped by the kernel.
Our OS abstraction layer will utilize this specific wrapper signature:
mmap(
NULL,
size,
PROT_READ | PROT_WRITE,
MAP_PRIVATE | MAP_ANONYMOUS,
-1,
0
);
Block
Applications rarely request memory in page-sized units. Instead, programs request arbitrary numbers of bytes like malloc(24) or malloc(137), while the OS allocates memory in pages (4 KiB). The allocator bridges this difference by subdividing pages into smaller memory blocks.
+-------------------------------------------------------------+
| Header | Data Block | Header | Data Block | Free |
+-------------------------------------------------------------+
Metadata
Raw pages from the OS contain no information about how they're being used. The allocator adds a small metadata header before each allocation so it can track block size, allocation state, and free-list links.
One possible header layout is:
struct BlockHeader {
size_t size;
bool free;
struct BlockHeader *next;
};
A standard explicit free-list structure chains these blocks together using pointers embedded within the metadata or the free payload space:
Tracking Free Memory
Once blocks exist, the allocator needs a way to remember which ones are available for reuse. There are many ways to track free memory, but here are the two basic ones:
Method 1: Implicit free list
[H][Used]
[H][Used]
[H][Free]
[H][Used]
Method 2: Explicit free list
Once blocks are freed by the user, we need a tracking mechanism. While an implicit list forces you to hop through every single block (used or free) to find an empty slot, our allocator will implement an Explicit Free List.
By using the next pointer inside our metadata headers, we link only the available blocks together into a dedicated chain:
Free List Head
│
↓
+---------+ +---------+ +---------+
| Header | --> | Header | --> | Header |
| Free | | Free | | Free |
+---------+ +---------+ +---------+
When a request comes in, we can jump sequentially through this list using search strategies like First-Fit (take the first block that fits) or Best-Fit (find the block closest in size) to find a home for the data.
Alignment
Many architectures require or strongly prefer naturally aligned accesses. Proper alignment avoids undefined behavior on some systems and improves performance on many others. If a user requests malloc(3), we must round that payload size up to 8 bytes. Ignoring alignment leads to severe performance degradation or outright crashes on strict architectures.
malloc(3)
↓
Header
↓
Payload rounded to 8 bytes
↓
Next allocation begins on an aligned boundary
Splitting
If our free list finds a leftover block that is 256 bytes large, but the user only requested malloc(64), we shouldn't waste the remaining space. We split the block: carving out the requested space, stamping a new metadata header on the remaining 192 bytes, and throwing that remnant back into the free list.
+----------------------------------+
(Before) | Free 256 bytes |
+----------------------------------+
↓
Need 64 bytes (malloc(64))
↓
+----------------+-----------------+
(After) | Head | 64 Used | Head | 192 free |
+----------------+-----------------+
Coalescing
Splitting memory introduces a new issue: external fragmentation. If we free a 64-byte block right next to a 192-byte free block, we technically have 256 bytes of contiguous space. However, if our allocator looks at them as two isolated items, a subsequent request for 200 bytes will fail.
When a block is freed, the allocator checks whether the immediately adjacent blocks in memory are also free. If they are, it coalesces them, merging their boundaries into a single large bloc
Basically this:
+-----------+-----------+-----------+-----------+
(Before) | H | Used | H |Free | H |Free | H | Used |
+-----------+-----------+-----------+-----------+
↓
+-----------+-----------------------+-----------+
(After) | H | Used | H | Large Free Block | H | Used |
+-----------+-----------------------+-----------+
What's Next?
The design is now in place.
The allocator has a defined architecture, a platform abstraction layer, and a clear strategy for obtaining and managing memory. The next step is to replace diagrams with code.
In Part 2, I'll implement the operating system abstraction layer by building os_alloc() and os_free() for both Linux and Windows. Once page allocation is working, the allocator itself can begin taking shape—starting with block headers and progressively adding free-list management, splitting, coalescing, and the implementations of malloc(), calloc(), realloc(), and free().
Conclusion
Every memory allocator starts with the same fundamental constraint: the operating system only provides pages of virtual memory. Everything beyond that, block metadata, free lists, alignment, splitting, coalescing, and the standard allocation functions - is an engineering problem built on top of those pages.
This article establishes the design decisions and architecture that will guide the rest of the project. The implementation that follows will build each component incrementally until the allocator becomes a complete, cross-platform implementation of C's dynamic memory allocation API.
If you're interested in following the project as it evolves, the full source code, documentation, and development history are available on GitHub.
Top comments (0)