pymalloc — Build Your Own Memory Allocator

A drop-in malloc / free / realloc / calloc replacement built in C — explicit doubly-linked free list, boundary-tag coalescing, first-fit placement, block splitting, and a heap consistency checker.

API

void *my_malloc(size_t size);
void  my_free(void *ptr);
void *my_realloc(void *ptr, size_t size);
void *my_calloc(size_t nmemb, size_t size);
void  heap_check(void);   // validates entire heap, asserts on corruption

Design

Property	Detail
Heap extension	sbrk() in 4 KB pages
Block structure	Header (size + alloc bit) + payload + Footer (boundary tag)
Free list	Explicit doubly-linked list (LIFO insertion)
Placement	First-fit search through free list
Coalescing	Immediate 4-case coalescing on free()
Splitting	Remainder block re-inserted if ≥ MIN_BLOCK_SIZE

Quick Start

gcc -O2 -o allocator allocator.c && ./allocator

=== Memory Allocator Test Suite ===
[PASS] Basic malloc/free
[PASS] Coalescing: prev+next free
[PASS] Realloc grow
[PASS] Heap checker: no corruption
...
23/23 tests passed. 108 allocations, 0 heap errors.

Boundary Tag Layout

┌──────────────────────────────┐
│  Header: size | alloc_bit    │  ← 8 bytes
├──────────────────────────────┤
│  Payload (user data)         │
├──────────────────────────────┤
│  Footer: size | alloc_bit    │  ← 8 bytes (enables O(1) prev-block lookup)
└──────────────────────────────┘

What I Learned

• How sbrk() extends the process heap by moving the program break pointer
• Why boundary tags (header + footer) enable O(1) coalescing without traversing the entire list
• The 4 coalescing cases: both neighbors allocated, one free, other free, both free
• How block splitting avoids internal fragmentation while maintaining alignment guarantees

---

Built as part of the Build Your Own X curriculum.