The heap & allocation

The problem the stack can’t solve

The stack is fast, but it has two limits. First, a frame’s size is fixed when the function is compiled. If you read a file whose size you only find out while the program runs, you can’t make room for it in the frame. Second, everything in a frame disappears when its function returns. If a function builds a list that the rest of the program needs, the list can’t live there. The heap solves both. It’s a large pool of memory where you can ask for a block of any size at any time, and the block stays valid until you explicitly give it back. The cost: something has to keep track of which parts are in use, and you have to remember to give blocks back.

Asking for memory and giving it back

In C the two operations are malloc(n) (“give me n bytes”) and free(ptr) (“I’m done with this”). In Zig, as you’ll see in Part II, they’re allocator.alloc(T, n) and allocator.free(slice). Either way the idea is the same:

You ask for some bytes.
The allocator (the code managing the heap) finds a free region, marks it as used, and gives you its address.
You use the memory for as long as you like, passing the pointer around.
You hand it back, and the allocator marks that region as free for future requests. If you come from JavaScript or TypeScript, this is the job a garbage collector does for you. Every object you create in JS lives on a heap, and the GC frees it once nothing refers to it any more. In systems languages like Zig and C there’s no GC: you decide when memory is freed.

Where heap memory comes from

The allocator has to get memory from somewhere: the operating system. The OS hands out memory in pages, usually 4 KiB each, through system calls (mmap, and on Linux also the older brk). System calls are relatively slow, and a page is much bigger than most requests. So allocators like glibc’s malloc ask the OS for big regions now and then, and carve them into small pieces themselves. Likewise, free usually doesn’t hand memory back to the OS. The allocator keeps the freed block on a free list so the next request of a similar size can reuse it quickly. (Very large blocks, 128 KiB and up by default in glibc, are the exception: they’re mapped and returned to the OS directly.)

Three ways to build an allocator

Different strategies trade off speed, flexibility and wasted space:

Bump (arena) allocator. Keep one buffer and one offset. For each request, move the offset forward and return the old position. You can’t free individual objects; instead you reset the offset and free everything at once. It’s incredibly fast and simple, and perfect when many objects share one lifetime: everything for one web request, one frame of a game, one compiler pass.
Free-list allocator. Keep track of freed blocks in a linked list and reuse them. Objects can be freed in any order, at the cost of bookkeeping and searching. General-purpose malloc implementations are sophisticated versions of this.
Pool allocator. Divide memory into equal slots for one kind of object. Allocating and freeing are just “take a slot” and “return a slot”. Great when you create and destroy lots of the same thing (particles in a game, network connections). The bump allocator is short enough to read in full:

const std = @import("std");

const Bump = struct {
    buf: []u8,
    end: usize = 0,

    fn alloc(self: *Bump, n: usize, alignment: usize) ?[]u8 {
        const start = std.mem.alignForward(usize, self.end, alignment);
        if (start + n > self.buf.len) return null;
        self.end = start + n;
        return self.buf[start..self.end];
    }

    fn reset(self: *Bump) void {
        self.end = 0; // "frees" everything at once
    }
};

Walk through alloc:

alignForward rounds the current offset up to the requested alignment. That’s the padding idea from the memory lesson.
If the request doesn’t fit in what’s left of the buffer, return null (no memory).
Otherwise move end forward past the new block and return that piece of the buffer. reset sets end back to 0, which “frees” every allocation in a single step. (This version aligns offsets within buf, so give it a buffer that’s aligned to begin with.)

Fragmentation

General-purpose allocators face a puzzle. Imagine a 100-byte heap. You allocate four 25-byte blocks, then free the 1st and the 3rd. Now 50 bytes are free, but as two separate 25-byte holes. A request for 40 bytes fails even though there’s “enough” memory in total.

[ free 25 ][ used 25 ][ free 25 ][ used 25 ]   → a 40-byte request can't fit anywhere

This is fragmentation, and a lot of the cleverness in real allocators goes into limiting it: grouping objects by size, merging neighbouring free blocks. Arenas and pools avoid the problem altogether.

The classic bugs

Managing memory by hand gives you control and speed, and also three famous ways to get it wrong:

Leak: you never free a block. In a short program nobody notices. In a server running for weeks, memory use keeps growing until something kills it.
Use-after-free: you keep using a pointer after freeing its block. The allocator may already have handed that memory to something else, so you read garbage or silently corrupt another object. It’s one of the most common sources of security holes in C and C++ programs.
Double free: you free the same block twice. The allocator’s bookkeeping gets corrupted, often causing a crash far away from the actual mistake. Zig has no garbage collector and no borrow checker, but it gives you good tools against all three: allocators passed explicitly so you can see who allocates, defer to put the free right next to the allocation, and a debug allocator that reports leaks and catches double frees. Those come in Part II.

Recap

The heap holds data whose size is only known at runtime, or that must outlive the function that made it.
Allocators get big regions from the OS in pages and split them into small blocks.
Bump/arena: fastest, frees everything at once. Free list: flexible. Pool: equal-size slots.
Fragmentation means free memory split into holes too small to use.
The three classic bugs are leaks, use-after-free and double free.