Implementing a Buddy Memory Allocator in C

This article provides a practical guide to designing and implementing a buddy memory allocator from scratch using the C programming language. Memory allocators manage raw byte pools for dynamic allocation, and the buddy system balances speed and fragmentation by dividing memory into power-of-two blocks and coalescing adjacent "buddies" upon deallocation. Below, you will explore the mathematical foundations of the algorithm, the required data structures, and a working C implementation covering block splitting and merging.

Core Concepts of the Buddy Allocator

The buddy allocation algorithm manages a contiguous memory pool whose total size is a power of two (\(2^U\)). Allocation requests are rounded up to the nearest power of two (\(2^K\)) that accommodates both the payload and any metadata headers.

  1. Splitting: When a block of size \(2^K\) is requested, the allocator checks if an idle block of that size exists. If none is available, it finds the smallest available block of size \(2^{K+1}\) (or higher) and splits it into two equal halves called buddies. One half is returned or further divided; the other half is added to the free list for size \(2^K\).
  2. Coalescing (Merging): When a block of size \(2^K\) is freed, the allocator calculates the address of its buddy. If the buddy is also free and unallocated, both are merged into a single block of size \(2^{K+1}\). This merging repeats recursively until the buddy is either allocated or the maximum block size is reached.

Finding a Buddy via Bitwise Math

Because every block is aligned to its own power-of-two size, the address of a block's buddy can be computed using a bitwise XOR operation relative to the base address of the pool:

\[\text{Buddy Offset} = \text{Block Offset} \oplus \text{Block Size}\]

In C, assuming pointers are converted to byte offsets from the pool start:

uintptr_t block_offset = (uintptr_t)block - (uintptr_t)pool_base;
uintptr_t buddy_offset = block_offset ^ block_size;
void* buddy_address = (void*)((uintptr_t)pool_base + buddy_offset);

Data Structures

A standard implementation utilizes an array of doubly linked lists, where each index \(i\) corresponds to an "order" representing blocks of size \(2^i \times \text{MIN\_BLOCK\_SIZE}\).

#include <stdint.h>
#include <stdbool.h>
#include <stddef.h>

#define MIN_ORDER 4    // 2^4 = 16 bytes minimum block size
#define MAX_ORDER 16   // 2^16 = 65,536 bytes total pool size
#define NUM_ORDERS (MAX_ORDER - MIN_ORDER + 1)

typedef struct BlockHeader {
    struct BlockHeader* next;
    struct BlockHeader* prev;
    uint8_t order;
    bool is_free;
} BlockHeader;

typedef struct {
    uint8_t* pool;
    size_t pool_size;
    BlockHeader* free_lists[NUM_ORDERS];
} BuddyAllocator;

Implementing Initialization and List Operations

Before allocating, the free lists are initialized, and the entire memory pool is placed into the list corresponding to the maximum order.

static size_t order_to_size(uint8_t order) {
    return (size_t)1 << (MIN_ORDER + order);
}

static uint8_t size_to_order(size_t size) {
    uint8_t order = 0;
    while (order_to_size(order) < size) {
        order++;
    }
    return order;
}

static void list_push(BuddyAllocator* alloc, uint8_t order, BlockHeader* block) {
    block->prev = NULL;
    block->next = alloc->free_lists[order];
    if (alloc->free_lists[order]) {
        alloc->free_lists[order]->prev = block;
    }
    alloc->free_lists[order] = block;
}

static void list_remove(BuddyAllocator* alloc, uint8_t order, BlockHeader* block) {
    if (block->prev) {
        block->prev->next = block->next;
    } else {
        alloc->free_lists[order] = block->next;
    }
    if (block->next) {
        block->next->prev = block->prev;
    }
    block->next = NULL;
    block->prev = NULL;
}

void buddy_init(BuddyAllocator* alloc, void* raw_memory) {
    alloc->pool = (uint8_t*)raw_memory;
    alloc->pool_size = order_to_size(NUM_ORDERS - 1);

    for (int i = 0; i < NUM_ORDERS; i++) {
        alloc->free_lists[i] = NULL;
    }

    BlockHeader* root = (BlockHeader*)alloc->pool;
    root->order = NUM_ORDERS - 1;
    root->is_free = true;
    list_push(alloc, root->order, root);
}

Allocation Logic

The buddy_alloc routine determines the appropriate order, removes a block from the matching free list, or splits higher-order blocks until an appropriate size is reached.

void* buddy_alloc(BuddyAllocator* alloc, size_t size) {
    size_t total_size = size + sizeof(BlockHeader);
    if (total_size > alloc->pool_size) return NULL;

    uint8_t target_order = size_to_order(total_size);
    uint8_t current_order = target_order;

    // Find the smallest available block large enough
    while (current_order < NUM_ORDERS && alloc->free_lists[current_order] == NULL) {
        current_order++;
    }

    if (current_order == NUM_ORDERS) {
        return NULL; // Out of memory
    }

    // Pop the block from the free list
    BlockHeader* block = alloc->free_lists[current_order];
    list_remove(alloc, current_order, block);

    // Split blocks until reaching the target order
    while (current_order > target_order) {
        current_order--;
        size_t split_size = order_to_size(current_order);

        BlockHeader* buddy = (BlockHeader*)((uint8_t*)block + split_size);
        buddy->order = current_order;
        buddy->is_free = true;
        list_push(alloc, current_order, buddy);
    }

    block->order = target_order;
    block->is_free = false;

    // Return the memory area directly following the header
    return (void*)((uint8_t*)block + sizeof(BlockHeader));
}

Deallocation and Coalescing

When buddy_free is called, the allocator marks the block as free and checks whether its buddy can be merged into a higher-order block.

void buddy_free(BuddyAllocator* alloc, void* ptr) {
    if (!ptr) return;

    BlockHeader* block = (BlockHeader*)((uint8_t*)ptr - sizeof(BlockHeader));
    block->is_free = true;

    while (block->order < NUM_ORDERS - 1) {
        uintptr_t block_offset = (uintptr_t)((uint8_t*)block - alloc->pool);
        size_t block_size = order_to_size(block->order);
        uintptr_t buddy_offset = block_offset ^ block_size;
        BlockHeader* buddy = (BlockHeader*)(alloc->pool + buddy_offset);

        // Conditions to coalesce: buddy must be free and must have the same order
        if (!buddy->is_free || buddy->order != block->order) {
            break;
        }

        // Remove buddy from free list and coalesce
        list_remove(alloc, block->order, buddy);

        if (buddy < block) {
            block = buddy;
        }

        block->order++;
    }

    list_push(alloc, block->order, block);
}

Key Trade-offs

The buddy allocator performs both allocations and deallocations in predictable logarithmic time (\(O(\log N)\)) with minimal external fragmentation. However, it can suffer from internal fragmentation because any request that marginally exceeds a power of two requires nearly double the requested memory. In operating systems such as the Linux kernel, buddy allocators are often paired with slab allocators, where the buddy system handles large page-sized blocks and the slab allocator serves small, fixed-size object caches out of those pages.