Memory Allocator From Scratch

/memory-allocator-from-scratch

When to Use

• Implementing malloc/free/realloc semantics from raw memory (e.g. over mmap/sbrk, or a fixed byte array) for teaching, an embedded target, or a custom-runtime project.
• Choosing between allocator strategies (bump, free-list, buddy, slab) for a specific workload and needing the actual tradeoffs, not just the names.
• Debugging fragmentation, use-after-free, or double-free in a hand-rolled allocator.

Do NOT use for

• Application-level memory management in a language with a GC or a mature allocator (JS, Python, Go, Java) — there is nothing to build here, use the runtime's allocator.
• General performance profiling of memory usage — see memory-leak-detection and profiling-benchmarking instead.
• Production allocator replacement — use jemalloc/mimalloc/tcmalloc; this skill is for understanding the mechanism, not shipping a faster malloc than decades of tuned production allocators.

Strategy Decision

Need the simplest possible allocator, never freeing individual objects?
  → Bump allocator (Step 1) — O(1) alloc, no free, reset all at once

Need general alloc/free of variable sizes, simplicity over raw speed?
  → Free-list allocator (Step 2) — the "classic malloc" approach

Need to minimize external fragmentation with fast coalescing?
  → Buddy allocator (Step 3) — power-of-2 sizes, easy merge, some internal waste

Need fast alloc/free of many same-sized objects (e.g. a fixed struct)?
  → Slab allocator (Step 4) — pre-carved fixed-size slots, near-zero overhead per alloc

Step 1: Bump Allocator (baseline)

Simplest possible allocator: keep one pointer to the next free byte, hand out size bytes and advance the pointer. No free() — the whole arena resets or is discarded at once (common in arena/region allocators for a single request's lifetime, e.g. a per-frame game allocator or a per-HTTP-request arena).

alloc(size):
  aligned = align_up(next_free, ALIGNMENT)
  if aligned + size > arena_end: return OUT_OF_MEMORY
  next_free = aligned + size
  return aligned

Step 2: Free-List Allocator

The mechanism behind classic malloc. Every allocated AND free block gets a small header before the returned pointer:

struct BlockHeader {
  size_t size;       // payload size, not including header
  bool   is_free;
  BlockHeader* next; // intrusive linked list of free blocks
}

alloc(size): walk the free list looking for a block big enough.

• First-fit: take the first block that fits — fast, can fragment.
• Best-fit: scan for the smallest block that fits — less waste per allocation, slower, can leave many tiny unusable fragments over time.
• If the found block is much bigger than needed, split it: carve off the requested size, leave the remainder as a new (smaller) free block.

free(ptr): walk back from ptr to its header, mark is_free = true, then coalesce with adjacent free blocks (check the block immediately before and after in memory address order, merge if both are free) — without coalescing, freed memory fragments into unusable slivers over time even though total free bytes is fine.

Alignment: most platforms require allocations aligned to 8 or 16 bytes (SIMD types need more). Round the requested size up to the alignment boundary before computing block size — an unaligned pointer returned to the caller can crash on some architectures (e.g. ARM strict alignment) or silently corrupt SIMD loads.

Step 3: Buddy Allocator

Only allocates in power-of-2 sizes. The whole arena starts as one free block of size 2^max. To satisfy a request, repeatedly split the smallest available block in half ("buddies") until you reach the smallest power-of-2 that fits the request. To free, check if your buddy (computable directly from your address via XOR with the block size) is also free — if so, merge back into the parent block, and recurse the check upward.

Tradeoff vs free-list: coalescing is O(log n) and address-computable (no list walk needed to find the buddy), but every allocation rounds up to the next power of 2 — a 65-byte request costs 128 bytes (internal fragmentation).

Step 4: Slab Allocator

For a workload that allocates/frees many objects of the SAME fixed size (e.g. kernel task_struct, a game's particle objects): pre-allocate a "slab" (a page or arena) already carved into fixed-size slots, and track free slots with a simple bitmap or intrusive free list of slot indices. Alloc and free are both O(1) with no header-walking or fragmentation concerns, since every slot is identical size.

What NOT to Do

• Don't skip the header — without per-block metadata, free() has no way to know a block's size or its free-list neighbors.
• Don't forget alignment — misaligned pointers are a portability bug that won't show up on every platform/compiler, making it easy to ship broken and not notice.
• Don't free() without coalescing adjacent blocks — a free-list allocator that never merges will eventually report "out of memory" while holding plenty of free (but fragmented) bytes.
• Don't reach for buddy or slab allocators before a free-list works correctly — they solve fragmentation/speed problems a working free-list doesn't have yet.