Why Build an Allocator?

Every malloc(N), every new, every object your favorite language creates ends up at an allocator. The operating system deals in whole pages — 4 KB chunks handed out by mmap or sbrk — and a syscall 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 user-space allocator exists to amortize 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.

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

ALLOC size returns the CURRENT bump value, then advances it. Allocation is one comparison plus one addition — nothing is faster. The price: freeing an individual block is impossible, because nothing records where blocks begin or end. The only reclamation is RESET, which rewinds bump to 0 and implicitly frees everything at once.

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

The rules your grader enforces

• INIT <size> — capacity = size, bump = 0, print OK.
• ALLOC <size> — if bump + size > heap_size, print OOM and change nothing. Otherwise print the bump value FIRST, then advance it by size.
• RESET — bump back to 0, print OK.
• USED — print the current bump value.

Two boundary decisions hide in that spec. First, the OOM comparison is strictly greater-than: a request that exactly fills the heap succeeds. Second, a failed ALLOC must not move the pointer.

Your exercise

Test 3 is the exactly-full case: INIT 16 then ALLOC 16. The grader expects 0 — the allocation succeeds and fills the heap — then USED prints 16 and ALLOC 1 prints OOM. If you wrote the capacity check as bump + size >= heap_size, your first ALLOC prints OOM instead of 0 and the test fails. A hidden test guards the second decision: on a 200-byte heap filled by four ALLOC 50, a further ALLOC 1 prints OOM — and USED must still print 200, not 201. If you advance bump before checking capacity, that final line is wrong.