memory_allocator.cpp

A little C++ playground implementing two classic allocator strategies from scratch: a segregated free list and a buddy system. No malloc/new under the hood for the actual allocation logic — everything works off a fixed-size char array that stands in for "the heap."

I built this mostly to actually understand how allocators track free/used memory instead of just reading about it. There's a menu-driven CLI at the bottom so you can poke at both allocators interactively and watch how they behave differently under the same workload.

What's in here

SegAllocator — a segregated free list. Free blocks are bucketed into small/medium/large lists based on size, each block has a header (size, free flag, magic number for corruption checks), and freed neighbors get coalesced back together so the heap doesn't fragment into dust over time.

BuddyAllocator — the classic buddy system. Requests get rounded up to a power-of-two-ish level, the tree gets split down to the right size, and when you free something it walks back up and merges with its buddy if that buddy is also free. Unlike the seg allocator, block metadata (the tree of BuddyNodes) lives separately from the heap bytes themselves — malloc() hands back a real pointer into the heap array, and free()/realloc() map that pointer back to its node via the offset.

Both implement the same Allocator interface (malloc, calloc, realloc, free, plus some introspection: show_heap, free_space, used_space, show_fragmentation), so they're easy to swap and compare.

There's also a MemoryTracker riding along in each allocator, logging every alloc/free so you get running stats — peak usage, total allocated, current usage, rough leak detection, that kind of thing.

Building it

Nothing fancy, just a single file:

g++ -std=c++17 -Wall -o allocator memory_allocator.cpp
./allocator

Using it

Run it and you get a menu:

Allocators:
  1. Segregated Free List
  2. Buddy System

Operations:
  A. malloc
  B. calloc
  C. realloc
  D. free
  E. show heap
  F. fragmentation report
  G. run benchmark
  H. switch allocator
  Q. quit

Allocated pointers get stored in numbered slots (up to 32 at once), so when you want to free or realloc something you just refer to it by index rather than typing out an address. H lets you flip between the two allocators mid-session if you want to compare how they handle the same sequence of ops.

G runs a quick synthetic benchmark — random mix of allocs and frees across both allocators for a fixed number of cycles — and prints timing plus free/used space at the end. Handy for eyeballing fragmentation differences between the two strategies.

Some notes on the internals

• Heap size is fixed at 8192 bytes for both allocators (HEAP_SIZE / BUDDY_SIZE). Change the constants if you want more room to play with.
• The buddy allocator's minimum block size is 32 bytes (MIN_SIZE), and it builds a full tree down to level 8 on construction — so there's some setup cost up front, but allocation/free after that is just tree traversal.
• Buddy nodes are pulled from a static pool (make_node()), capped at 256 nodes total. If you shrink MIN_SIZE or grow BUDDY_SIZE you'll want to bump that pool size too or you'll start getting nullptr back from build_tree.
• Double-free protection exists on both allocators — the seg allocator checks a magic number in the block header, the buddy one checks that the node it finds is actually marked allocated with a non-zero requested size before freeing it.
• realloc() on the buddy side copies over min(old_size, new_size) bytes when moving to a new block — worth knowing if you're expecting it to zero out the extra space on growth (it doesn't, that's on you).

Why two allocators instead of one

Honestly, comparing them side by side is the point. Segregated lists are simple and give decent fragmentation behavior for varied allocation sizes, but coalescing is a linear-ish walk. The buddy system trades some internal fragmentation (rounding everything up to a power of two) for very cheap, localized merging on free — you're always looking at exactly one buddy, never the whole heap. Running the benchmark against both is a nice way to see that trade-off show up in the numbers instead of just taking it on faith.

Known limitations / stuff I didn't bother with

• Not thread-safe. There's no locking anywhere, so don't call these from multiple threads.
• Fixed heap size means you can't grow past HEAP_SIZE/BUDDY_SIZE — no sbrk/mmap-style extension.
• The buddy allocator's node pool is static and shared across all BuddyAllocator instances, so creating more than one at a time (the code does, for the seg-vs-buddy comparison in main) will eat into the same 256-node budget. Fine for this demo, would need fixing for anything more serious.
• Error handling is mostly "print a message and return nullptr/return early" rather than anything more structured — this was written to explore the allocation logic, not to be production-hardened.