malloc · free · realloc · calloc
A from-scratch dynamic memory allocator in C using segregated free lists, a previous-allocated bit flag, and a 16-byte small-block optimisation — 8 bytes overhead per allocation.
Performance
Block Layout
Allocated Block
Free Block
Small Free Block (16B)
Allocated blocks have no footer — the prev-allocated bit in each header records whether the preceding block is free, enabling coalescing without a footer round-trip.
Key Design Decisions
Segregated Free Lists
8 size classes starting at 16 bytes. malloc searches the appropriate class for best-fit, falling back to larger classes before calling sbrk.
Prev-Allocated Bit
The second-lowest bit of every header records whether the preceding block is allocated — eliminating the need for a footer in allocated blocks.
Small Block Optimisation
16-byte free blocks reuse header/footer fields as prev/next free-list pointers — no separate link fields needed, reducing minimum block size.
Immediate Coalescing
Freed blocks are merged with adjacent free neighbours on every free() call using boundary tags and the prev-allocated bit.
Header Structure
/* 64-bit header word layout */ /* Bit 0 — BIT_ALLOCATED (this block is in use) */ /* Bit 1 — BIT_PREVIOUS_ALLOCATED (preceding block is in use) */ /* Bit 2 — BIT_SMALL_FREE_BLOCK (this is a 16-byte free block)*/ /* Bits 3+ — block size (always a multiple of 16) */ typedef uint64_t header_t; #define BIT_ALLOCATED 0x1 #define BIT_PREVIOUS_ALLOCATED 0x2 #define BIT_SMALL_FREE_BLOCK 0x4 #define FLAG_MASK 7 #define SIZE_MASK (~FLAG_MASK) #define NUM_FREE_LISTS 8 /* segregated size classes */ #define SMALL_FREE_BLOCK_SIZE 16 /* special-cased block type */