Binary Decomposition Principle

Any positive integer can be decomposed into a sum of distinct powers of two (2ⁿ, where n ≥ 0). This mathematical property, which forms the foundation of binary representation, is the core mechanism leveraged by the Buddy allocation system.

Kernel Buddy System Data Structure Hierarchy

The architecture of the Buddy system is structured across four distinct levels:

1. pglist_data (pgdat): Represents a single NUMA memory node.
2. zone: Divides the node into memory zones.
3. free_area: Tracks free blocks of a specific order. The Page Frame Number (PFN) of blocks within this area strictly satisfies the alignment assertion: pfn & ((1 << order) - 1) == 0. The total number of free pages in a specific order is calculated as free_area[order].nr_free * (1 << order).
4. Migration Type: Blocks within a specific order are further categorized and linked into separate lists based on their migration attributes.

As implied by the alignment assertion, pages linked into an order-specific free list must be order-aligned. Furthermore, only the first page of a contiguous block will pass the PageBuddy test. Except for order-0 blocks, the linked lists in free_area[order] only contain the head pages of buddy blocks, with each head implicitly representing 1 << order contiguous physical pages.

User-Space Buddy Allocator Simulation

The following code demonstrates a simplified user-space implementation of the Buddy allocator, modeling the core logic of the kernel's memory management:

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <stdbool.h>
#include "ll_list.h"

#define MAX_BUDDY_ORDER 11
#define PHYS_MEM_PAGES (4096)

struct mem_frame {
    struct ll_head node;
    uint32_t idx;
    uint32_t block_order;
    bool is_buddy_head;
};

struct ll_head free_lists[MAX_BUDDY_ORDER];
struct mem_frame frame_pool[PHYS_MEM_PAGES];

static void init_free_lists(void) {
    for (int i = 0; i < MAX_BUDDY_ORDER; i++) {
        LL_INIT_LIST_HEAD(&free_lists[i]);
    }
}

static void init_frame_pool(void) {
    for (int i = 0; i < PHYS_MEM_PAGES; i++) {
        LL_INIT_LIST_HEAD(&frame_pool[i].node);
        frame_pool[i].idx = i;
        frame_pool[i].block_order = 0;
        frame_pool[i].is_buddy_head = false;
    }
}

static bool is_pfn_valid(uint32_t pfn) {
    return (pfn < PHYS_MEM_PAGES);
}

static bool check_buddy_head(uint32_t pfn, uint32_t order) {
    struct mem_frame *frm;
    ll_for_each_entry(frm, &free_lists[order], node) {
        if (frm->idx == pfn) return true;
    }
    return false;
}

static void unlink_buddy(uint32_t pfn) {
    ll_list_del(&frame_pool[pfn].node);
    LL_INIT_LIST_HEAD(&frame_pool[pfn].node);
}

static uint32_t calc_buddy_pfn(uint32_t pfn, uint32_t order) {
    return pfn ^ (1 << order);
}

static void mark_buddy_head(struct mem_frame *frm, uint32_t order) {
    frm->block_order = order;
    frm->is_buddy_head = true;
}

static void clear_buddy_head(struct mem_frame *frm) {
    if (!frm->is_buddy_head) {
        fprintf(stderr, "Error: clearing non-buddy page.\n");
        exit(EXIT_FAILURE);
    }
    frm->is_buddy_head = false;
}

static void attach_to_free_list(struct mem_frame *frm, uint32_t order) {
    mark_buddy_head(frm, order);
    ll_list_add(&frm->node, &free_lists[order]);
}

static int return_frames(struct mem_frame *frm, uint32_t order) {
    uint32_t cur_pfn = frm->idx;
    if (cur_pfn & ((1 << order) - 1)) return -1; // Alignment check

    while (order < MAX_BUDDY_ORDER) {
        uint32_t buddy_pfn = calc_buddy_pfn(cur_pfn, order);

        if (!is_pfn_valid(buddy_pfn) || !check_buddy_head(buddy_pfn, order) || (order == MAX_BUDDY_ORDER - 1))
            break;

        unlink_buddy(buddy_pfn);
        uint32_t merged_pfn = buddy_pfn & cur_pfn;
        frm = &frame_pool[merged_pfn];
        cur_pfn = merged_pfn;
        order++;
    }
    attach_to_free_list(frm, order);
    return 0;
}

static int release_single_frame(struct mem_frame *frm) {
    return return_frames(frm, 0);
}

static void split_block(struct mem_frame *frm, uint32_t target_order, uint32_t current_order) {
    uint32_t size = 1 << current_order;
    while (current_order > target_order) {
        current_order--;
        size >>= 1;
        attach_to_free_list(&frame_pool[frm->idx + size], current_order);
    }
}

static struct mem_frame* acquire_frames(uint32_t order) {
    for (uint32_t i = order; i < MAX_BUDDY_ORDER; i++) {
        if (ll_list_empty(&free_lists[i])) continue;

        struct mem_frame *frm = ll_entry(free_lists[i].next, struct mem_frame, node);
        ll_list_del(&frm->node);
        split_block(frm, order, i);
        clear_buddy_head(frm);
        return frm;
    }
    return NULL;
}

int main(void) {
    init_free_lists();
    init_frame_pool();

    for (int i = 0; i < PHYS_MEM_PAGES; i++) {
        release_single_frame(&frame_pool[i]);
    }

    struct mem_frame *block = acquire_frames(6);
    if (block) {
        return_frames(block, 6);
    }
    return 0;
}

PageBuddy Flag Mechanics

When a page is allocated from the Buddy system, its PageBuddy flag is immediately cleared, meaning newly allocated hot pages will fail the PageBuddy test. When a page is returned to the allocator, if it does not merge with an adjacent buddy, the kernel stack trace (originating from __free_one_page down to free_pages) will re-apply the PageBuddy flag via set_page_order. For order-0 blocks, every page linked in the free list acts as a buddy head. For higher-order blocks, only the leading page passes the PageBuddy check.

All pages within a free buddy block have a reference count of 0. However, their mapcounts differ: tail pages retain a mapcount of -1, while the head page shows -129 due to union overlaps within the struct page definition. Upon allocation, only the head page's refcount is incremented to 1; tail pages remain at 0.

Identifying Free Pages in the Buddy System

While the PageBuddy flag identifies a buddy block head, determining if an arbitrary page belongs to a free buddy block requires scanning potential block alignments. This logic is exposed to userspace via /proc/kpageflags and driven by the is_free_buddy_page function. It iterates upward through possible orders, calculating the corresponding head page. If a head page is found with PageBuddy set and its order encompasses the target page, the page is confirmed free.

bool check_page_is_free(struct page *pg) {
    struct zone *z = page_zone(pg);
    unsigned long pfn = page_to_pfn(pg);
    unsigned long flags;
    unsigned int ord;

    spin_lock_irqsave(&z->lock, flags);
    for (ord = 0; ord < MAX_ORDER; ord++) {
        struct page *head = pg - (pfn & ((1 << ord) - 1));

        if (PageBuddy(head) && page_order(head) >= ord)
            break;
    }
    spin_unlock_irqrestore(&z->lock, flags);

    return ord < MAX_ORDER;
}

Buddy Address Calculation and Hardware Alignment

The algorithm to locate a buddy's address uses an XOR operation based on the order. This mechanism does not require physical addresses to start at zero, but it does require PFNs to be aligned to MAX_ORDER. In the Linux kernel, the default MAX_ORDER is 11, making the maximum valid order 10. Thus, the lower 10 bits of the PFN must be zero, enforcing a 1024-page alignment. With a standard 4K page size, physical memory must be mapped to 4MB aligned addresses to satisfy the Buddy algorithm's hardware constraints.

Strategies for Large Memory Allocations in x86

With a default MAX_ORDER of 11, the Buddy system caps contiguous physical memory allocations at 4MB. To allocate larger contiguous regions, several alternatives exist:

• CMA/ION Memory: Reserve memory at boot time via kernel command line parameters. CMA utilizes bitmap management instead of the Buddy system, allowing theoretically unlimited contiguous allocations within physical limits.
• Adjusting MAX_ORDER: Recompile the kernel with a modified CONFIG_FORCE_MAX_ZONEORDER. This approach lacks granularity; requesting 64MB forces the system to also support 32MB, 16MB, and 8MB maximum blocks.
• Boot-time Allocation: Utilize alloc_bootmem during kernel initialization before the Buddy system takes over the memory landscape.
• Huge Pages: Leverage architecture-supported huge pages (e.g., 2MB, 1GB) and map them directly to drivers or peripherals.