Dynamic Memory Allocator

Secure high-performance malloc/free/realloc from scratch. A 64-bit dynamic memory allocator in C with segregated free lists, quick-list caching, immediate and delayed coalescing, 16-byte payload alignment, and XOR-obfuscated headers and footers for heap-corruption detection.

What it is

A from-scratch replacement for the C standard allocator exposing sf_malloc, sf_free, and sf_realloc. The heap grows a page at a time via a provided sf_mem_grow() primitive; all bookkeeping — size classes, free lists, coalescing, alignment, corruption detection — is implemented from first principles with no calls to the C library allocator. Also exposes sf_fragmentation() and sf_utilization() heap-health instrumentation.

By the numbers

Architecture

Header bit layout
[ 32 bits payload size | 28 bits block size | 2 unused | in_qklst | allocated ]

Allocation path
  size round-up -> quick list hit? -> first-fit seg list ->
  split if remainder >= min -> miss: grow page, coalesce, retry

Free path
  validate (align, range, magic parity, alloc bit, not in qklst) ->
  quick-list push (mark IN_QUICK_LIST) -> flush at MAX=5: coalesce all ->
  large blocks skip qklst, coalesce immediately

Key features

• Segregated free lists — 12 size classes indexed by power-of-two multiples of the minimum block size; circular doubly linked, LIFO insert.
• Quick lists — 12 singly linked LIFO caches for recently freed small blocks, bypassing coalescing for hot reuse.
• Immediate and delayed coalescing — large blocks merge with adjacent free neighbors on free; quick-list flush at QUICK_LIST_MAX = 5 triggers coalesce of all held blocks.
• Obfuscated headers and footers — every header and footer word is XORed with a runtime MAGIC; corruption, double-free, and invalid free are detected on every access.
• Prologue and epilogue guards — sentinel blocks at heap boundaries eliminate edge cases in coalescing logic.
• Block splitting — allocations split free blocks when the remainder meets the minimum block size; no splinters.
• Instrumentation — tracks peak payload and aggregate live payload for fragmentation and utilization reporting.

What makes it stand out

• Structural test suite, not smoke tests. Every one of the 20 tests asserts both correctness of returned pointers and the exact shape of the free-list and quick-list state afterward.
• Corruption detection by construction. Magic-XORed metadata turns any casual stomp into a detectable parity violation on the next read.
• Zero libc allocator calls. Heap grows exclusively through sf_mem_grow() in 4096-byte increments; every invariant is maintained by the implementation itself.

Stack

Built Feb–Mar 2025 for CSE 320 (Systems Fundamentals II) at Stony Brook University.

Links

• Source: https://github.com/FardinIqbal/dynamic-memory-allocator