Understanding Memory Partitioning in Custom Allocators

Building a custom memory allocator in C is an excellent way to understand low-level systems programming. When you request a large chunk of memory from the operating system using mmap(), you are given a raw, contiguous block of virtual memory. To manage this region, you must partition it into smaller, manageable blocks.

Your proposed layout — placing metadata headers inline with the usable payload — is the standard and correct approach. This is often referred to as an implicit/explicit free list design with boundary tags. The layout looks like this:

[ Block Header (Metadata) ][ Usable Payload ][ Block Header ][ Usable Payload ]...

Is Your Pointer Arithmetic Correct?

Yes, your pointer arithmetic logic is correct. Because pointer arithmetic on void* is undefined in standard C (though supported as an extension by GCC and Clang), casting to char* is the standard way to perform byte-wise arithmetic.

free_list *next = (free_list *)((char *)free_list_head + sizeof(free_list) + first_block_size);

However, while the logic is correct, this code will likely fail or cause severe performance degradation on modern CPUs if you do not account for memory alignment.

The Importance of Memory Alignment

CPUs do not read from and write to memory in single-byte chunks. Instead, they access memory in word-sized chunks (typically 4 bytes on 32-bit systems and 8 or 16 bytes on 64-bit systems). If a multi-byte variable (like a pointer or a double) is stored at an address that is not a multiple of its size, the CPU has to perform multiple memory cycles to access it. On some architectures (like ARM), misaligned memory accesses can even trigger a hardware exception and crash your program.

To prevent this, your allocator must guarantee that the payload pointer returned to the user is aligned to the system's alignment requirement (typically 8 bytes on 32-bit systems and 16 bytes on 64-bit systems).

How to Align Sizes and Addresses

To implement alignment, you can use a simple bitwise macro. For an alignment value that is a power of two (e.g., 8 or 16), you can round up any size using this formula:

#define ALIGNMENT 8
#define ALIGN(size) (((size) + (ALIGNMENT - 1)) & ~(ALIGNMENT - 1))

Let's break down how this macro works:

  • ALIGNMENT - 1 adds enough bytes to push the size to the next boundary.
  • ~(ALIGNMENT - 1) creates a bitmask that clears the lowest bits, effectively rounding down to the nearest multiple of ALIGNMENT.

Putting It All Together: A Robust Implementation

Below is an updated version of your code that correctly initializes the heap, aligns the block metadata, and ensures that all partitioned blocks conform to proper alignment boundaries.

#include <stddef.h>
#include <sys/mman.h>
#include <stdint.h>
#include <stdio.h>

#define ALIGNMENT 8
#define ALIGN(size) (((size) + (ALIGNMENT - 1)) & ~(ALIGNMENT - 1))

typedef struct free_list {
    size_t size;               // Size of the usable payload, excluding metadata
    struct free_list *next;
} free_list;

#define HEADER_SIZE ALIGN(sizeof(free_list))
#define HEAP_SIZE (10u * 1024u * 1024u)

static free_list *free_list_head = NULL;

void my_heap_init(void)
{
    if (free_list_head == NULL)
    {
        void *raw = mmap(NULL, HEAP_SIZE,
                         PROT_READ | PROT_WRITE,
                         MAP_PRIVATE | MAP_ANONYMOUS,
                         -1, 0);

        if (raw == MAP_FAILED) {
            perror("mmap failed");
            return;
        }

        // Ensure the starting address of our metadata is aligned
        uintptr_t raw_addr = (uintptr_t)raw;
        uintptr_t aligned_addr = ALIGN(raw_addr);
        size_t adjustment = aligned_addr - raw_addr;

        free_list_head = (free_list *)aligned_addr;
        
        // The usable size is the total size minus the metadata size and initial alignment adjustment
        free_list_head->size = HEAP_SIZE - HEADER_SIZE - adjustment;
        free_list_head->next = NULL;
    }
}

// Example of partitioning (splitting) a block
void split_block(free_list *block, size_t requested_size)
{
    size_t aligned_requested = ALIGN(requested_size);
    
    // Ensure there is enough space to fit another metadata header and at least 1 aligned word of payload
    if (block->size >= aligned_requested + HEADER_SIZE + ALIGNMENT)
    {
        // Calculate the address of the new block
        free_list *new_block = (free_list *)((char *)block + HEADER_SIZE + aligned_requested);
        
        // Set up the new block's metadata
        new_block->size = block->size - aligned_requested - HEADER_SIZE;
        new_block->next = block->next;
        
        // Update the current block
        block->size = aligned_requested;
        block->next = new_block;
    }
}

Key Takeaways for Your Custom Allocator

  • Always Align Payloads: Every time a user requests memory, align the requested size upwards before doing any offset calculations.
  • Align Header Sizes: Ensure that sizeof(free_list) is padded to your alignment boundary so that the payload starting immediately after it remains aligned.
  • Prevent Fragmentation: When partitioning blocks, ensure that the remaining fragment is large enough to hold a new header and a minimum payload. If it isn't, don't split the block—just return the larger block to avoid creating unusable "micro-blocks" (external fragmentation).