Chapter 17: Guided Project: Custom Memory Allocator

This project takes you deep into the heart of low-level C programming: memory management. You’ve used malloc() and free() extensively, but have you ever wondered how they work? In this guided project, you will build a simplified version of a memory allocator.

This project is significantly more complex than the calculator but offers unparalleled insights into:

Pointers and Pointer Arithmetic: Extensive use of raw memory addresses.
Structures: To define memory block metadata.
Dynamic Memory Allocation: Understanding sbrk() (or similar system calls) for getting raw memory from the OS.
Memory Layout: How memory is organized and managed at a low level.
Error Handling: Crucial for robust memory management.

Disclaimer: This will be a very basic allocator. Real-world malloc implementations are highly optimized and complex, involving techniques like freelists, memory pools, mutexes for thread safety, and elaborate block splitting/merging algorithms. Our goal is conceptual understanding.

Project Objective

Implement a simplified pair of functions, my_malloc() and my_free(), that allocate and deallocate blocks of memory from a larger, pre-allocated pool (our “heap”).

Allocator Strategy: First Fit

We’ll use a simple “First Fit” strategy:

When my_malloc is called, it searches for the first available memory block large enough to satisfy the request.
If found, it might split the block if the remaining part is large enough to be a new free block.
If no block is large enough, it tries to expand the heap (if possible).
When my_free is called, the freed block is marked as free. We’ll also implement basic coalescing (merging adjacent free blocks) for efficiency.

Step 1: Defining Memory Block Structure

Our allocator will manage memory in chunks, each preceded by a header that describes the block. This header needs to know the block’s size and whether it’s currently free or allocated.

my_allocator.h (Header File):

Let’s create a header file for our allocator functions and data structures.

// my_allocator.h
#ifndef MY_ALLOCATOR_H
#define MY_ALLOCATOR_H

#include <stddef.h> // For size_t

// Structure to define a memory block header
typedef struct BlockHeader {
    size_t size;           // Size of the block (including this header)
    struct BlockHeader *next; // Pointer to the next block in our linked list
    int is_free;           // Flag: 1 if free, 0 if allocated
    // Add more fields here if needed for alignment, magic numbers, etc.
} BlockHeader;

// Function prototypes
void *my_malloc(size_t size);
void my_free(void *ptr);

#endif // MY_ALLOCATOR_H

Explanation of BlockHeader:

size: The total size of the block, including the header itself. This is important for pointer arithmetic.
next: We’ll manage our memory blocks as a singly linked list. This pointer points to the next BlockHeader.
is_free: A flag to indicate the block’s status.

Task for Step 1:

Create my_allocator.h and paste the code above.

Step 2: Global Variables and Initializing the Heap

We need a way to manage our “heap.” In real systems, malloc gets memory from the OS using system calls like sbrk (on Unix-like systems) or VirtualAlloc (on Windows). For simplicity, we’ll simulate this by having a fixed-size buffer that acts as our “heap,” or use sbrk if available.

We’ll need a global pointer to the head of our linked list of memory blocks.

my_allocator.c (Source File):

// my_allocator.c
#include "my_allocator.h"
#include <unistd.h> // For sbrk (on Unix-like systems)
#include <stdio.h>  // For perror, printf

// --- Global variables for the allocator ---
static BlockHeader *head = NULL; // Head of our linked list of memory blocks
static void *program_break = NULL; // Initial program break (sbrk)

// Define minimum size for a free block to be split
// If remaining_size < MIN_BLOCK_SPLIT_SIZE, don't split
// Minimum size for a block must be at least sizeof(BlockHeader)
#define MIN_BLOCK_SPLIT_SIZE (sizeof(BlockHeader) + 16) // Header + small data

// Helper function to request more memory from the system (like sbrk)
// Returns NULL on failure, pointer to start of new memory on success
static BlockHeader *request_more_memory(size_t size) {
    void *request_start;
    BlockHeader *header;

    // Align size to a multiple of BlockHeader size for simplicity (optional, but good practice)
    // Or align to largest fundamental type (e.g., double) for general usage.
    size = (size + sizeof(BlockHeader) - 1) & ~(sizeof(BlockHeader) - 1); // Align up

    request_start = sbrk(0); // Get current program break
    if (sbrk(size + sizeof(BlockHeader)) == (void *)-1) { // Request more memory
        perror("sbrk failed to extend heap");
        return NULL; // Failed to get more memory
    }

    header = (BlockHeader *)request_start;
    header->size = size + sizeof(BlockHeader);
    header->is_free = 0; // Initially allocated
    header->next = NULL;

    return header;
}

// --- my_malloc implementation ---
void *my_malloc(size_t size) {
    if (size == 0) {
        return NULL;
    }

    // Align the requested size to ensure good alignment for data types
    // E.g., align to 8 bytes for double or pointer types
    // We'll align to `sizeof(void*)` or `sizeof(long double)` if larger
    const size_t ALIGN_SIZE = sizeof(long double) > sizeof(void*) ? sizeof(long double) : sizeof(void*);
    size = (size + ALIGN_SIZE - 1) & ~(ALIGN_SIZE - 1);

    BlockHeader *current;
    BlockHeader *prev = NULL;

    // If this is the first call, initialize the heap
    if (head == NULL) {
        // Request initial chunk of memory from the system
        // Let's start with a reasonable size or a minimum amount
        size_t initial_heap_size = 4096; // E.g., 4KB
        BlockHeader *first_block = request_more_memory(initial_heap_size - sizeof(BlockHeader));
        if (first_block == NULL) {
            return NULL; // Failed to get initial memory
        }
        first_block->is_free = 1; // Mark as free for subsequent allocations
        head = first_block;
    }

    // First Fit strategy: search for the first free block
    current = head;
    while (current != NULL) {
        if (current->is_free && current->size >= (size + sizeof(BlockHeader))) {
            // Found a free block that is large enough

            // Check if we can split the block
            size_t remaining_size = current->size - (size + sizeof(BlockHeader));
            if (remaining_size >= MIN_BLOCK_SPLIT_SIZE) {
                // Split the block
                BlockHeader *new_block = (BlockHeader *)((char *)current + size + sizeof(BlockHeader));
                new_block->size = remaining_size;
                new_block->is_free = 1;
                new_block->next = current->next; // Link new block to current's next

                current->size = size + sizeof(BlockHeader); // Update current block's size
                current->next = new_block; // Link current block to the new split block
            }

            current->is_free = 0; // Mark current block as allocated
            // Return pointer to the data area (after the header)
            return (void *)(current + 1); // Equivalent to (char*)current + sizeof(BlockHeader)
        }
        prev = current;
        current = current->next;
    }

    // No large enough block found, request more memory from system
    BlockHeader *newly_requested_block = request_more_memory(size);
    if (newly_requested_block == NULL) {
        return NULL; // Failed to get more memory
    }

    // Link the new block to the end of our list
    if (prev != NULL) {
        prev->next = newly_requested_block;
    } else {
        // This case implies head was NULL initially, but it should be handled above
        // unless request_more_memory() fails on first attempt and then succeeds later.
        // For robustness, ensure head is correctly set if first block.
        head = newly_requested_block; // Should only happen if initial head was requested in my_malloc
    }
    newly_requested_block->is_free = 0; // Already marked as allocated by request_more_memory

    return (void *)(newly_requested_block + 1);
}

// --- my_free implementation ---
void my_free(void *ptr) {
    if (ptr == NULL) {
        return;
    }

    // Get the block header by subtracting the header size from the data pointer
    BlockHeader *block_to_free = (BlockHeader *)ptr - 1;

    // Basic validation: Check if block is already free (double free)
    if (block_to_free->is_free) {
        fprintf(stderr, "Warning: Attempted to double-free memory at %p\n", ptr);
        return;
    }

    block_to_free->is_free = 1; // Mark the block as free

    // Coalesce adjacent free blocks (simple version)
    BlockHeader *current = head;
    BlockHeader *prev = NULL;

    while (current != NULL) {
        if (current->is_free) {
            // Check if current block can be merged with previous
            if (prev != NULL && prev->is_free && ((char *)prev + prev->size == (char *)current)) {
                // Merge current into prev
                prev->size += current->size;
                prev->next = current->next;
                // Move current pointer back to prev to continue checking for more merges
                current = prev; // Stay at prev, as it might merge with the *new* next
            } else {
                // Current block is free, but cannot merge with previous (or no previous)
                prev = current;
            }
        } else {
            // Current block is allocated, cannot merge with it
            prev = current;
        }
        current = current->next;
    }
}

Task for Step 2:

Create my_allocator.c and paste the code.
Understand sbrk(): sbrk(0) returns the current “program break” (the end of the data segment). sbrk(increment) increases the program break by increment bytes and returns the old program break. This effectively “gives” your process more memory from the OS. Handle its potential failure.
Pointer Arithmetic: Pay close attention to how we calculate the data pointer: (BlockHeader *)ptr - 1 gets the header from a data pointer, and (void *)(current + 1) gets the data pointer from a header.

Step 3: Testing the Allocator

Let’s create a main.c file to test our my_malloc and my_free functions.

main.c (Test Program):

// main.c
#include "my_allocator.h"
#include <stdio.h>
#include <string.h>
#include <stdlib.h> // For original malloc/free for comparison

int main() {
    printf("--- Custom Memory Allocator Test ---\n");

    // Test 1: Simple allocations and deallocations
    int *a = (int *)my_malloc(sizeof(int));
    if (a == NULL) { fprintf(stderr, "my_malloc failed for a\n"); return 1; }
    *a = 100;
    printf("Allocated 'a' at %p, value = %d\n", (void *)a, *a);

    char *b = (char *)my_malloc(20 * sizeof(char));
    if (b == NULL) { fprintf(stderr, "my_malloc failed for b\n"); return 1; }
    strcpy(b, "Hello Custom Malloc!");
    printf("Allocated 'b' at %p, value = \"%s\"\n", (void *)b, b);

    double *c = (double *)my_malloc(sizeof(double));
    if (c == NULL) { fprintf(stderr, "my_malloc failed for c\n"); return 1; }
    *c = 3.14159;
    printf("Allocated 'c' at %p, value = %.5f\n", (void *)c, *c);

    printf("\nFreeing 'b'...\n");
    my_free(b);
    // b = NULL; // Good practice after freeing

    // Test 2: Allocation after a free (should reuse 'b's space if possible)
    char *d = (char *)my_malloc(10 * sizeof(char));
    if (d == NULL) { fprintf(stderr, "my_malloc failed for d\n"); return 1; }
    strcpy(d, "Short text");
    printf("Allocated 'd' at %p, value = \"%s\"\n", (void *)d, d);

    // Test 3: Array allocation
    int *arr = (int *)my_malloc(5 * sizeof(int));
    if (arr == NULL) { fprintf(stderr, "my_malloc failed for arr\n"); return 1; }
    for (int i = 0; i < 5; i++) {
        arr[i] = (i + 1) * 10;
    }
    printf("Allocated 'arr' at %p, values: ", (void *)arr);
    for (int i = 0; i < 5; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    // Test 4: Freeing all
    printf("\nFreeing all allocated memory...\n");
    my_free(a);
    my_free(c);
    my_free(d);
    my_free(arr);

    // Test 5: Attempt to double-free (should print warning)
    printf("\nAttempting to double-free 'a'...\n");
    my_free(a); // This is actually an invalid pointer access, but we try to illustrate the free check

    // Test 6: Allocating a large chunk (may require sbrk to extend again)
    printf("\nAllocating a large chunk (1KB)...\n");
    void *large_chunk = my_malloc(1024);
    if (large_chunk == NULL) { fprintf(stderr, "my_malloc failed for large_chunk\n"); return 1; }
    printf("Allocated large chunk at %p\n", large_chunk);
    my_free(large_chunk);

    printf("\n--- Test Complete ---\n");

    return 0;
}

Compilation (Linux/macOS):

gcc -Wall -Wextra -std=c11 my_allocator.c main.c -o my_allocator_test

-Wall -Wextra: Enable many warnings (good practice).
-std=c11: Use C11 standard.

Run:

./my_allocator_test

Expected Output: You should see memory addresses and values. Observe if d gets allocated at a similar address to where b was, suggesting reuse. Also, note the Warning: Attempted to double-free if you try to double free.

Further Enhancements (Self-Study Challenges)

Our basic allocator has many limitations. Here are ideas for improvement, ranging from simple to very complex:

Robust Error Handling for sbrk(): Our request_more_memory is basic. In a production system, you’d handle sbrk failures more gracefully.
Proper Coalescing in my_free(): The current my_free only coalesces the block being freed with its immediate neighbors. A more robust approach would be to iterate through the entire freelist (or a portion) to find all adjacent free blocks. This might involve keeping the freelist sorted by address.
Different Allocation Strategies:
- Best Fit: Search for the smallest free block that can satisfy the request. (Less fragmentation, slower search).
- Worst Fit: Search for the largest free block and split it. (Leaves larger chunks for subsequent requests, potentially faster search).
External Fragmentation: When memory becomes fragmented into many small, unusable free blocks. A real allocator would try to mitigate this.
Alignment for All Types: Our ALIGN_SIZE is a simple approach. A robust allocator needs to ensure any returned pointer is aligned correctly for any type (e.g., a double allocated with my_malloc should be 8-byte aligned on systems where doubles require it).
- You can enforce this by always returning pointers aligned to the largest common alignment requirement (e.g., sizeof(max_align_t) from <stddef.h>).
Thread Safety: Our allocator is not thread-safe. Multiple threads calling my_malloc or my_free simultaneously would lead to race conditions. This requires mutexes (from <pthread.h>).
More Robust Validation: Add “magic numbers” or checksums to BlockHeader to detect memory corruption (e.g., overwriting a header).
Heap Metadata: Display the current state of your heap (e.g., void print_heap_state()).

This project, though simplified, should give you a profound appreciation for the complexity and critical nature of memory allocators. It’s one of the foundational pieces of any operating system or runtime environment, and understanding it brings you much closer to mastering low-level C programming.

You’ve now tackled one of the most challenging and insightful projects in low-level C: a custom memory allocator. This journey into the inner workings of memory management has significantly deepened your understanding of pointers, data structures, and system interaction. You’re now well-equipped to appreciate how C empowers you to wield immense control over your machine’s resources. In the final chapter, we’ll provide a roadmap for your continued learning in the exciting world of systems programming.

Chapter 17: Guided Project: Custom Memory Allocator

// table of contents

Chapter 17: Guided Project: Custom Memory Allocator

Project Objective

Step 1: Defining Memory Block Structure

Step 2: Global Variables and Initializing the Heap

Step 3: Testing the Allocator

Further Enhancements (Self-Study Challenges)