TopicTrick Logo
Topictrick
Home
Courses
YouTube
Blog

Learning Hubs

TOGAF & Enterprise ArchitectureMainframe: COBOL, CICS, IMS, DB2Claude API & AI Engineering
Utilities
Junior
Shop
Pricing
Loading...
CProjects

Project: Building a Custom Heap Memory Allocator in C (malloc & free from Scratch)

TT
TopicTrick Team
•
Project: Building a Custom Heap Memory Allocator in C (malloc & free from Scratch)
← Back to C Mastery

Project: Building a Custom Heap Memory Allocator in C (malloc & free from Scratch)

Phase 2 Capstone. You've mastered pointers, pointer arithmetic, and heap concepts. Now you'll build the engine that powers C's memory management — implementing your own malloc() and free() that manages a 1MB private heap from a static array. This is exactly how glibc's ptmalloc2, jemalloc, and Google's tcmalloc work at their core.

Table of Contents

How Real Allocators Work

glibc's malloc maintains a free list of available memory blocks in the heap. Each block has a small header storing its size and whether it's in use. When you call malloc(n), the allocator:

  1. Searches the free list for a block large enough.
  2. Splits it if it's much larger than needed.
  3. Marks it as in use and returns a pointer past the header.

When you call free(ptr), the allocator:

  1. Walks back to the header (at ptr - sizeof(Header)).
  2. Marks it as free.
  3. Checks if adjacent blocks are also free — if so, merges them (coalescing).

After free(C) and free(D): they coalesce into [Header: 768B, FREE].

The Block Header Design

Every allocated and free block begins with a header storing its metadata:

c
#include <stddef.h>
#include <stdint.h>
#include <stdbool.h>
#include <stdio.h>
#include <string.h>

// Each block in our heap has this header
// Placed immediately BEFORE the returned user pointer
typedef struct Block {
    size_t       size;      // Payload size (bytes available to user)
    bool         is_free;   // Is this block available?
    struct Block *prev;     // Previous block in free list (or heap)
    struct Block *next;     // Next block in free list (or heap)
} Block;

// Alignment: returned pointers must be 8-byte aligned
// sizeof(Block) must also be a multiple of 8
#define ALIGNMENT     8
#define ALIGN(size)   (((size) + (ALIGNMENT-1)) & ~(ALIGNMENT-1))
#define HEADER_SIZE   ALIGN(sizeof(Block))

// Our private 1MB heap
#define HEAP_SIZE     (1024 * 1024)  // 1 MB
static uint8_t  heap_memory[HEAP_SIZE];
static Block   *heap_head = NULL;
static bool     heap_initialized = false;

Heap Initialization

c
void heap_init(void) {
    if (heap_initialized) return;
    
    // The entire heap is a single, large free block
    heap_head = (Block*)heap_memory;
    heap_head->size    = HEAP_SIZE - HEADER_SIZE; // All space minus the header itself
    heap_head->is_free = true;
    heap_head->prev    = NULL;
    heap_head->next    = NULL;
    
    heap_initialized = true;
    printf("[Heap] Initialized: %zu bytes available\n", heap_head->size);
}

tmalloc: First-Fit Allocation

Scan the block list and return the first free block that's large enough:

c
void* tmalloc(size_t requested_size) {
    if (!heap_initialized) heap_init();
    if (requested_size == 0) return NULL;
    
    // Align the request size to ensure alignment of subsequent headers
    size_t aligned_size = ALIGN(requested_size);
    
    Block *current = heap_head;
    while (current != NULL) {
        if (current->is_free && current->size >= aligned_size) {
            // Found a suitable block — split it if it's much larger
            block_split(current, aligned_size);
            
            current->is_free = false;
            
            // Return pointer PAST the header — this is what the user sees
            void *user_ptr = (char*)current + HEADER_SIZE;
            
            printf("[malloc] Allocated %zu bytes at %p\n", aligned_size, user_ptr);
            return user_ptr;
        }
        current = current->next;
    }
    
    // No block large enough found
    fprintf(stderr, "[malloc] Out of memory! Requested %zu bytes\n", requested_size);
    return NULL;
}

Block Splitting: Avoiding Waste

If we have a 512-byte free block and the user requests 64 bytes, we'd waste 448 bytes by using the entire block. Splitting creates a smaller allocated block and leaves the remainder as a new free block:

c
#define MINIMUM_SPLIT_SIZE (HEADER_SIZE + ALIGNMENT) // Minimum useful block size

static void block_split(Block *block, size_t requested_size) {
    // Only split if remaining space would form a valid block
    size_t remaining = block->size - requested_size;
    
    if (remaining < MINIMUM_SPLIT_SIZE) {
        // Too small to split — give the user the whole block (slight over-allocation)
        return;
    }
    
    // Create a new free block from the leftover space
    Block *new_block = (Block*)((char*)block + HEADER_SIZE + requested_size);
    new_block->size    = remaining - HEADER_SIZE;
    new_block->is_free = true;
    new_block->prev    = block;
    new_block->next    = block->next;
    
    if (block->next) block->next->prev = new_block;
    block->next = new_block;
    block->size = requested_size; // Shrink current block to exact request size
    
    printf("[split] Split into %zu + %zu bytes\n", block->size, new_block->size);
}

tfree: Marking Blocks Free

c
void tfree(void *ptr) {
    if (!ptr) return; // Free(NULL) is always safe
    
    // Walk back to the block header (just before the user pointer)
    Block *block = (Block*)((char*)ptr - HEADER_SIZE);
    
    if (block->is_free) {
        fprintf(stderr, "[free] ERROR: Double-free detected at %p!\n", ptr);
        return; // Prevent double-free corruption
    }
    
    block->is_free = true;
    printf("[free] Freed %zu bytes at %p\n", block->size, ptr);
    
    // Attempt to coalesce with adjacent free blocks
    coalesce(block);
}

Coalescing: Preventing Fragmentation

Without coalescing, a heap of many small free blocks can't satisfy a large allocation even when total free space is sufficient:

c
static void coalesce(Block *block) {
    // Try to merge with the NEXT block (if it's also free)
    if (block->next && block->next->is_free) {
        block->size += HEADER_SIZE + block->next->size; // Absorb next block
        block->next  = block->next->next;
        if (block->next) block->next->prev = block;
        printf("[coalesce] Merged with next: now %zu bytes\n", block->size);
    }
    
    // Try to merge with the PREVIOUS block (if it's also free)
    if (block->prev && block->prev->is_free) {
        block->prev->size += HEADER_SIZE + block->size;
        block->prev->next  = block->next;
        if (block->next) block->next->prev = block->prev;
        printf("[coalesce] Merged with prev: now %zu bytes\n", block->prev->size);
    }
}

trealloc: Minimal Realloc

c
void* trealloc(void *ptr, size_t new_size) {
    if (!ptr) return tmalloc(new_size);
    if (new_size == 0) { tfree(ptr); return NULL; }
    
    Block *block = (Block*)((char*)ptr - HEADER_SIZE);
    
    // If current block is large enough, just return it
    if (block->size >= ALIGN(new_size)) {
        block_split(block, ALIGN(new_size));
        return ptr;
    }
    
    // Allocate new, copy data, free old
    void *new_ptr = tmalloc(new_size);
    if (!new_ptr) return NULL;
    
    memcpy(new_ptr, ptr, block->size); // Copy old data
    tfree(ptr);                         // Free old block
    return new_ptr;
}

Testing Your Allocator

c
int main(void) {
    heap_init();
    
    // Test 1: Basic allocation and free
    int *arr = tmalloc(10 * sizeof(int));
    for (int i = 0; i < 10; i++) arr[i] = i * i;
    printf("arr[5] = %d (expected 25)\n", arr[5]);
    tfree(arr);
    
    // Test 2: Allocate multiple blocks
    char *s1 = tmalloc(64);
    char *s2 = tmalloc(128);
    char *s3 = tmalloc(256);
    strcpy(s1, "Hello");
    strcpy(s2, "World");
    tfree(s2);          // Free middle block
    tfree(s1);          // Free first block — should coalesce with s2's region
    
    // Test 3: Large allocation (verify coalescing reclaimed space)
    char *large = tmalloc(160); // Should fit in the coalesced s1+s2 region
    if (large) printf("Large allocation succeeded!\n");
    tfree(large);
    tfree(s3);
    
    // Test 4: Realloc
    int *data = tmalloc(5 * sizeof(int));
    for (int i = 0; i < 5; i++) data[i] = i;
    data = trealloc(data, 10 * sizeof(int));
    printf("data[4] = %d (expected 4, preserved)\n", data[4]);
    tfree(data);
    
    printf("All tests passed!\n");
    return 0;
}

Extension Challenges

Push your allocator further:

  1. Best-Fit Strategy: Instead of first-fit, scan all free blocks and choose the smallest one that fits — reduces fragmentation at the cost of slower allocation.
  2. Free List Index: Maintain a separate linked list of only free blocks — allocation becomes O(free_count) instead of O(total_count).
  3. Size Classes: Maintain separate free lists for small sizes (8, 16, 32, 64 bytes) — hugely reduces fragmentation for small allocations (this is what glibc and tcmalloc do).
  4. Memory Statistics: Track total allocated, total free, fragmentation ratio, peak usage.
  5. Thread Safety: Add a pthread_mutex_t around both tmalloc and tfree — your allocator is now multi-thread safe.

Phase 2 Reflection

Building this allocator reveals that malloc isn't magic — it's careful bookkeeping. The fundamental pattern (block header + first-fit + splitting + coalescing) is exactly what glibc's ptmalloc2, Google's tcmalloc (thread-local size class caches), and Facebook's jemalloc (arena-based multi-thread allocator) are built upon.

You now understand why memory allocation has performance implications beyond just "how many bytes am I using" — fragmentation, free list traversal, and alignment constraints all affect throughput in ways invisible to higher-level languages.

Read next: Phase 3: Advanced Data Structures →

Frequently Asked Questions

Q: How does a simple heap memory allocator work at the implementation level? A basic allocator requests a large block of memory from the OS via sbrk() or mmap() and manages it internally. It maintains a free list — a linked list of free blocks, each with a header storing the block size and a pointer to the next free block. malloc(n) searches the free list for a block large enough (first-fit or best-fit), splits it if much larger, and returns a pointer past the header. free(ptr) walks back to the header, marks the block free, and inserts it into the free list, coalescing adjacent free blocks to prevent fragmentation.

Q: What is memory fragmentation and how does an allocator address it? External fragmentation occurs when free memory is split into many small non-contiguous blocks — a large allocation can fail even though total free memory is sufficient. Coalescing merges adjacent free blocks when free() is called. Boundary tags (a footer mirror of the header) make coalescing O(1) by letting you check the previous block's status without traversing the list. Internal fragmentation is wasted space within an allocated block due to alignment rounding — minimised by keeping block sizes aligned to 8 or 16 bytes.

Q: What is the difference between sbrk() and mmap() for a custom allocator? sbrk() extends the process's data segment (the heap) by moving the program break pointer — simple but contiguous, meaning you cannot return memory to the OS in the middle of the heap. mmap(MAP_ANONYMOUS) maps a fresh page of memory anywhere in the address space and can be returned individually with munmap() — better for large allocations. Modern allocators like glibc malloc use sbrk for small allocations (to amortise syscall overhead) and mmap for large ones (so they can be returned to the OS independently).

Part of the C Mastery Course — 30 modules from C basics to expert systems engineering.