Why virtual memory changes everything about arena allocators.
The earlier arena did one malloc and called it a day; this one talks directly to the kernel about virtual address space and physical memory as two separate things — and that single change is what makes the design actually scale.
If you've ever written a parser, a game, or a compiler, you've hit the same wall: you don't know how big the arena needs to be. Pick a megabyte and you overflow on a big input. Pick a gigabyte and you've handed the OS a gigabyte of RAM you'll almost never use. Resizing a bump allocator means copying everything, which makes pointers into it dangle.
Virtual memory dissolves the dilemma. Modern operating systems separate two things that malloc conflates:
- Address space — a range of virtual addresses, indistinguishable from "real" memory to the program. Practically free; on a 64-bit machine you can reserve gigabytes.
- Physical memory — actual RAM pages mapped under those addresses. Costly; only what you've touched counts against your RSS.
The first arena promised: one big block, no resize, no copy. This one promises the same thing — but the block can be enormous and you don't pay for it until you fill it.
Two operations, one address range.
Reserving claims virtual addresses without RAM; committing maps RAM under previously-reserved addresses. Decommitting returns the RAM but keeps the addresses; releasing throws both away.
| Operation | Address space | Physical RAM | Cost |
|---|---|---|---|
| reserve | claimed | none | a few bookkeeping bytes in the kernel |
| commit | kept | mapped | the bytes you commit, charged to your RSS |
| decommit | kept | released | RSS drops; addresses still reserved |
| release | released | released | everything goes back to the OS |
starting from a fresh, reserved-but-empty range
The arena's bookkeeping still lives at byte 0 — it just sits on different memory.
The mem_arena struct is still at the start of the block; the difference is the block now spans an enormous range of virtual addresses, of which only the first few pages are real.
reserve_size = 1 GiB → virtual address space, no RAM yet commit_size = 1 MiB → physical RAM mapped at startup [ mem_arena | 1 MiB committed | ......... 1 GiB reserved but no RAM yet ......... ] ^ ^ ^ ^ header base position commit_position end
The header tracks four values: reserve_size, commit_size, position (what the user sees), and commit_position (what the OS sees). Two cursors instead of one — their job is to never disagree.
The header, the macros, the platform-layer prototypes.
#ifndef _ARENA_H
#define _ARENA_H
#include <stdint.h>
typedef int8_t i8; typedef int16_t i16;
typedef int32_t i32; typedef int64_t i64;
typedef uint8_t u8; typedef uint16_t u16;
typedef uint32_t u32; typedef uint64_t u64;
typedef i8 b8; typedef i32 b32;
#define KiB(n) ((u64)(n) << 10)
#define MiB(n) ((u64)(n) << 20)
#define GiB(n) ((u64)(n) << 30)
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) > (b)) ? (a) : (b))
#define ALING_UP_POW2(n, p) (((u64)(n) + (u64)(p) - 1) & (~((u64)(p) - 1)))
typedef struct {
u64 reserve_size; // total reserved virtual address space
u64 commit_size; // commit granularity (typically the page size)
u64 position; // bump cursor — what the user sees
u64 commit_position; // how far we've committed — what the OS sees
} mem_arena;
#define ARENA_BASE_POSITION (sizeof(mem_arena))
#define ARENA_ALING (sizeof(void *))
#define PUSH_STRUCT(arena, T) (T*)arena_push((arena), sizeof(T), false)
#define PUSH_STRUCT_NZ(arena, T) (T*)arena_push((arena), sizeof(T), true)
#define PUSH_ARRAY(arena, T, n) (T*)arena_push((arena), (n)*sizeof(T), false)
#define PUSH_ARRAY_NZ(arena, T, n) (T*)arena_push((arena), (n)*sizeof(T), true)
u32 plat_get_pagesize(void);
void *plat_mem_reserve (u64 size);
b32 plat_mem_commit (void *ptr, u64 size);
b32 plat_mem_decommit(void *ptr, u64 size);
b32 plat_mem_release (void *ptr, u64 size);
#endifFive functions that hide the OS.
The arena is platform-neutral; a tiny adapter underneath maps reserve / commit / decommit / release to mmap on POSIX and VirtualAlloc on Windows.
#include <sys/mman.h>
#include <unistd.h>
u32 plat_get_pagesize(void) { return getpagesize(); }
void *plat_mem_reserve(u64 size) {
// PROT_NONE: claim the addresses, can't read/write yet.
return mmap(NULL, size, PROT_NONE,
MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
}
b32 plat_mem_commit(void *ptr, u64 size) {
return mprotect(ptr, size, PROT_READ | PROT_WRITE) == 0;
}
b32 plat_mem_decommit(void *ptr, u64 size) {
return mprotect(ptr, size, PROT_NONE) == 0;
}
b32 plat_mem_release(void *ptr, u64 size) {
return munmap(ptr, size) == 0;
}#include <windows.h>
u32 plat_get_pagesize(void) {
SYSTEM_INFO sysinfo = {0};
GetSystemInfo(&sysinfo);
return sysinfo.dwPageSize;
}
void *plat_mem_reserve(u64 size) {
return VirtualAlloc(NULL, size, MEM_RESERVE, PAGE_READWRITE);
}
b32 plat_mem_commit(void *ptr, u64 size) {
return VirtualAlloc(ptr, size, MEM_COMMIT, PAGE_READWRITE) != NULL;
}
b32 plat_mem_decommit(void *ptr, u64 size) {
return VirtualFree(ptr, size, MEM_DECOMMIT);
}
b32 plat_mem_release(void *ptr, u64 size) {
return VirtualFree(ptr, 0, MEM_RELEASE);
}The arena doesn't know which platform it's on, and the platform doesn't know about arenas. Five functions, one ABI, the whole portability problem solved at the seam where it's smallest.
Reserve big, commit small, write the header.
mem_arena *arena_create(u64 reserve_size, u64 commit_size) {
u32 pagesize = plat_get_pagesize();
reserve_size = ALING_UP_POW2(reserve_size, pagesize);
commit_size = ALING_UP_POW2(commit_size, pagesize);
mem_arena *arena = plat_mem_reserve(reserve_size);
if (!plat_mem_commit(arena, commit_size)) {
return NULL;
}
arena->reserve_size = reserve_size;
arena->commit_size = commit_size;
arena->position = ARENA_BASE_POSITION;
arena->commit_position = commit_size;
return arena;
}arena_push() grows the commit boundary as it goes.
void *arena_push(mem_arena *arena, u64 size, b32 non_zero) {
u64 pos_aligned = ALING_UP_POW2(arena->position, ARENA_ALING);
u64 new_pos = pos_aligned + size;
if (new_pos > arena->reserve_size) {
return NULL;
}
if (new_pos > arena->commit_position) {
u64 new_commit_pos = new_pos;
new_commit_pos += arena->commit_size - 1;
new_commit_pos -= new_commit_pos % arena->commit_size;
new_commit_pos = MIN(new_commit_pos, arena->reserve_size);
u8 *mem = (u8 *)arena + arena->commit_position;
u64 commit_size = new_commit_pos - arena->commit_position;
if (!plat_mem_commit(mem, commit_size)) {
return NULL;
}
arena->commit_position = new_commit_pos;
}
arena->position = new_pos;
u8 *out = (u8 *)arena + pos_aligned;
if (!non_zero) {
memset(out, 0, size);
}
return out;
}The fast path — push fits in already-committed pages — is a pure bump. The slow path runs only on the first push that needs each new page, amortised across many subsequent pushes.
Why every push rounds up to sizeof(void *).
On x86-64, reading an 8-byte integer from a non-multiple-of-8 address forces two cache-line accesses. On ARM, the same read raises a SIGBUS. Alignment is a hardware contract, not a style preference. ARENA_ALING = sizeof(void *) covers all standard scalar types.
#define ALING_UP_POW2(n, p) (((u64)(n) + (u64)(p) - 1) & (~((u64)(p) - 1)))n = 0 → 7 & ~7 = 0 n = 1 → 8 & ~7 = 8 n = 7 → 14 & ~7 = 8 n = 9 → 16 & ~7 = 16 n = 17 → 24 & ~7 = 24
Move the cursor backward without ever crossing the header.
void arena_pop(mem_arena *arena, u64 size) {
size = MIN(size, arena->position - ARENA_BASE_POSITION);
arena->position -= size;
}
void arena_pop_to(mem_arena *arena, u64 position) {
u64 size = position < arena->position
? arena->position - position
: 0;
arena_pop(arena, size);
}arena_pop doesn't touch commit_position. The RAM stays mapped — if you push 16 MiB, pop it, then push 16 MiB again, the second push hits the fast path because those pages are still committed.
If you really need the RAM back, build an arena_decommit_above(arena, threshold) helper on top of plat_mem_decommit. The primitive is there; the arena just chooses not to call it.
One line of code, one of the most useful patterns in systems programming.
void arena_clear(mem_arena *arena) {
arena_pop_to(arena, ARENA_BASE_POSITION);
}Because clearing keeps the committed pages, an arena that fills up once and clears repeatedly never pays the commit cost again. The first frame is expensive. Every subsequent frame is a single store to position.
Two arenas, one program: a perm_arena that lives the whole run, and a frame_arena that gets arena_cleared every loop iteration.
One syscall and the entire region goes away.
void arena_destroy(mem_arena *arena) {
plat_mem_release(arena, arena->reserve_size);
}On Linux that's one munmap; on Windows it's one VirtualFree(_, 0, MEM_RELEASE). The address space goes back to the kernel, the committed pages are decommitted in the same operation, and every pointer that ever came out of arena_push is now invalid in unison.
Ergonomic macros over arena_push.
typedef struct { f32 x, y, z; } v3;
mem_arena *arena = arena_create(GiB(1), MiB(1));
v3 *origin = PUSH_STRUCT(arena, v3); // zeroed v3
v3 *cloud = PUSH_ARRAY(arena, v3, 1024); // 1024 zeroed v3s
char *buf = PUSH_ARRAY_NZ(arena, char, 4096); // skip the memsetThe _NZ variants skip the memset when you're about to overwrite the whole block anyway.
Watching the arena grow in htop.
int main(void) {
mem_arena *perm_arena = arena_create(GiB(1), MiB(1));
while (true) {
arena_push(perm_arena, MiB(16), false);
getc(stdin); // wait for enter to push again
}
arena_destroy(perm_arena);
}Watch two columns in htop: VIRT jumps to ~1 GiB at startup and never moves; RES starts at a few MiB and grows by ~16 MiB each time you press enter. That gap between the two is the lie virtual memory tells the kernel on your behalf.
On Linux, overcommit settings (/proc/sys/vm/overcommit_memory) and ulimit -v can both refuse a gigabyte-sized reserve. Both are one-line fixes; both are worth knowing about before you ship.
Building arena.c on Linux and Windows.
$ gcc -std=c11 -Wall -Wextra -O2 arena.c main.c -o arena_test
$ ./arena_test
# In another terminal: htop, then watch VIRT and RES.This source calls its macro ALING_UP_POW2 and its constant ARENA_ALING — the typo survives verbatim. Keep it or fix it, but pick one.
What this version taught me.
- The interface between a process and a modern kernel is small and beautiful. Reserve, commit, decommit, release. Four operations and you've replaced
mallocfor whole classes of workload. - Virtual address space is a resource the way RAM is — but a much, much cheaper one. Programs that act like it's free are usually right.
- Two cursors are better than one. Splitting "what the user sees" from "what the OS sees" turns every push into a fast path, and makes the slow path explicit.
Credit: the reserve-vs-commit design follows Ryan Fleury's "Untangling Lifetimes: The Arena Allocator" almost beat for beat. If anything here clicked for you, his original is the next thing to read.
Frequently asked questions
What is the difference between reserving and committing memory?
Reserving memory claims a range of virtual addresses from the kernel without backing any of it with physical RAM. Committing memory tells the kernel to actually map physical pages to those virtual addresses. An arena built on this distinction reserves a huge range up front, then commits pages lazily as the position pointer walks forward.
How does arena_push() commit memory lazily?
arena_push rounds the requested size up to ARENA_ALING and advances position. If the new position is past commit_position, it rounds the new target up to a multiple of commit_size, calls plat_mem_commit for only the new pages, and updates commit_position. Pushes that stay within already-committed memory skip the syscall entirely.
Why use mmap / VirtualAlloc instead of malloc?
malloc hands you bytes that are already committed and already counted against your RSS. mmap and VirtualAlloc let you reserve a huge contiguous virtual range and pay for physical memory only when you touch it.
What happens to the RAM when I call arena_pop or arena_clear?
Nothing — pop and clear move the user-visible position back but never touch commit_position. The committed pages stay mapped, so subsequent pushes hit the fast path immediately.
What is memory alignment and why does it matter?
Memory alignment means placing a value at an address that is a multiple of its natural size. Misaligned reads cost two cache-line fetches on x86 and trap on ARM. The arena's ALING_UP_POW2 rounds every push up to sizeof(void *).