Custom memory allocator in C

Overview

This project implements a custom malloc/free-style memory allocator in C, built in two stages:

• v1 : Linked-list based allocator with headers only
• v2 : Boundary Tag allocator with implicit free list and O(1) coalescing

The goal of this project was to understand how real allocators:

• Keep track of and manage heap memory
• Reuse free blocks
• Control fragmentation
• Satisfy ABI alignment requirements

Why build a custom malloc

Standard malloc is used in a way that hides a lot of the underlying complexity of it's implementation. This project was my attempt at understand what actually goes on under the hood. Some of the questions that bothered me at the time of learning malloc were along the lines of :

• How does free(ptr) know the size of allocation?
• How do allocators reuse memory safely?
• How do they avoid fragmentation?
• Why does alignment matter?

This project was the result of my research into this topic

Version 1 : Linked List based allocator

Implementation : memory_allocator.h and memory_allocator_v1.c

Design

Each allocation is preceded by a header

[ header ][ user memory ]...

Each header stores

• size of user allocation (size available to user)
• free/used flag
• pointer to next block

All blocks are thus tracked in a singly linked list

Limitations

• Forward coalescing is easy
• Backward coalescing requires O(n) list traversal
• Fragmentation grows over time
• Metadata pointers must be carefully maintained and are prone to bugs.

This version works well, but scales poorly.

Version 2 :

• Implementation : memory_allocator.h and memory_allocator_v2.c
• This version replaces the linked list with boundary tags.

Design

Each block stores it's metadata at both ends

[ header ][ user memory ][ footer ]...

Both header and footer store the total size of block

• total_block_size = sizeof(header) + sizeof(footer) + user_size;

Key insight

Because size information is stored at both ends :

• Next block can be found by adding size
• Previous block footer can be found using sizeof(footer), from which we can travel to previous block header using size and check if block is free
• Coalescing in both directions becomes O(1)

No linked list is required

Allocation strategy

• Implicit free list (heap is walked linearly)
• First-fit search
• Blocks are split when larger than needed
• Adjacent free blocks are immediately coalesced on free

Due to constant size and fixed arithmetic, bidirectional merging is constant time

Alignment guarantees

The allocator guarantees:

• Returned pointers are 16 byte aligned
• This satisfies the x86-64 SysV ABI (max_align_t)
• Required for long double and SIMD types

Alignment is enforced by rounding allocation sizes and verified via debug assertions.

Build and usage

Make sure to use the correct .c file during compilation

gcc memory_allocator_v2.c <your_program>.c

Files

• memory_allocator.h
• memory_allocator_v1.c - Linked list allocator
• memory_allocator_v2.c - boundary tag allocator

Learnings

• How real allocators handle memory without OS support
• Why boundary tags simplify block traversal and handling
• How fragmentation occurs and how to handle it
• Why alignment is an ABI contract, not an optimization

Future work

• calloc/realloc
• Segregated free lists
• Thread safety
• mmap-based large allocations

Safety note: This allocator assumes well-behaved programs. Writing beyond the bounds of an allocation results in undefined behavior and may corrupt allocator metadata (e.g., boundary tags). This is consistent with the C memory model and standard malloc behavior.

Production allocators mitigate this via metadata hardening, guard pages, or sanitizers, which are beyond the scope of this project.