Why Build an Allocator?

Every malloc(N), every new, every object your favorite language creates ends up at an allocator. In this lesson your program becomes the simplest allocator that exists: one integer that only moves forward.

Why a user-space allocator exists

The operating system deals in whole pages, 4 KB chunks handed out by mmap or sbrk, and a system call costs on the order of a microsecond. A program that made one syscall per allocation would spend most of its life trapping in and out of the kernel. The allocator amortizes that cost: grab pages from the OS occasionally, then serve thousands of small requests from the cached pool in nanoseconds each.

Every allocator design is a position in a four-way trade-off:

• Speed: how few instructions between the request and the returned address.
• Memory efficiency: how little is lost to fragmentation and metadata.
• Thread scalability: whether 32 cores fight over one lock.
• Robustness: whether double-frees and overflows get detected or silently corrupt the heap.

You cannot maximize all four. dlmalloc (Doug Lea's classic, ancestor of glibc's ptmalloc) favors memory efficiency: boundary tags, aggressive coalescing, best-fit bins. tcmalloc (Google, used by Chrome) and jemalloc (FreeBSD-born, used by Firefox and Redis) spend memory on per-thread caches to buy speed and scalability. mimalloc (Microsoft) pushes the lock-free fast path further still. Same problem, four different answers, because their workloads differ. This course builds each ingredient of those designs, bottom-up.

The floor of the design space: the bump allocator

The bottom is one integer. Here is a heap of 100 bytes after two requests:

INIT 100                 bump = 0
ALLOC 10  -> prints 0    bump = 10
ALLOC 20  -> prints 10   bump = 30

byte 0        10                  30                      100
  |  block A  |      block B      |......free tail........|
                                  ^ bump

An allocation returns the CURRENT value of the pointer and then advances it by the request size. That is one comparison plus one addition; nothing is faster. The price is that freeing an individual block is impossible: nothing records where blocks begin or end, so there is nothing to give back. The only reclamation is rewinding the pointer, which frees everything at once.

That sounds useless until you notice how much software has exactly this lifetime shape: a compiler's per-function syntax tree, a game frame's scratch data, a server request's temporaries. Arena allocators, which are bump pointers with an explicit lifetime, are everywhere for this reason, and they come back in the Real-World Allocators lesson.

The rules your grader enforces

• INIT <size> sets the capacity, puts the pointer at 0 and prints OK.
• ALLOC <size> prints the address of the new block, or OOM if it does not fit.
• RESET puts the pointer back at 0 and prints OK.
• USED prints the current pointer.

Two boundary decisions hide in that spec. First, how much room counts as "fits": a request that exactly fills the heap must succeed, so the failure test is strictly "past the end". Second, a failed ALLOC must leave the allocator exactly as it was: same pointer, same capacity, and a later smaller request can still succeed.

Common mistakes

• Using >= for the capacity check. INIT 16 then ALLOC 16 must print 0, not OOM; the heap has exactly 16 bytes and the request wants exactly 16.
• Advancing the pointer before checking. After INIT 200 and four ALLOC 50, an ALLOC 1 prints OOM and USED must still print 200, not 201.
• Printing the pointer AFTER the advance. The address of a new block is where the pointer WAS; printing 10 for the first ALLOC 10 hands the caller memory that belongs to the next block.
• Forgetting that INIT starts over. A second INIT with a new size must clear the old pointer.

Your exercise

The starter already reads the commands and prints the collected output. Fill in the four command branches. The tests include the exactly-full heap, a zero-byte request, a long run of equal-sized requests that ends in OOM, and a failed request followed by a smaller one that still succeeds.