Understanding the Linux Kernel Buddy Memory Allocation Algorithm

The Linux kernel relies on a robust memory‑management subsystem, and the buddy algorithm is a core component that efficiently allocates and frees physical pages while minimizing external fragmentation.

1. Buddy algorithm overview – The system groups free pages into 11 order‑based lists (sizes 1, 2, 4 … 1024 pages). When a request arrives, the algorithm searches the list matching the request size; if none is found it looks in larger orders, splits a larger block in half, and inserts the unused half back into the appropriate list.

2. Allocation principle – Allocation proceeds by locating the smallest suitable block, removing it from its free list, and, if the block is larger than needed, repeatedly splitting it until the desired order is reached, inserting the remaining halves into lower‑order lists.

3. Core data structures

#define MAX_ORDER 11

struct zone {
    ...
    struct free_area free_area[MAX_ORDER];
    ...
};

struct free_area {
    struct list_head free_list;
    unsigned long nr_free; // number of free blocks in this order
};

The zone structure contains an array of free_area , each representing a specific order of contiguous pages.

4. Initialization – During boot, the kernel uses the bootmem bitmap to populate the buddy system. Functions such as mem_init → __free_all_bootmem → free_all_bootmem_core → __free_pages walk every page, clear reservation flags, set reference counts, and insert the page into the appropriate free list, thereby initializing the buddy allocator.

5. Allocation flow

page = __rmqueue(zone, order);
for (current_order = order; current_order < MAX_ORDER; ++current_order) {
    area = zone->free_area + current_order;
    if (list_empty(&area->free_list))
        continue;
    page = list_entry(area->free_list.next, struct page, lru);
    list_del(&page->lru);
    rmv_page_order(page);
    area->nr_free--;
    __mod_zone_page_state(zone, NR_FREE_PAGES, -(1UL << order));
    return expand(zone, page, order, current_order, area);
}
return NULL;

This routine searches from the requested order upward, extracts a suitable block, and calls expand to split any excess pages.

6. Freeing flow

static inline void __free_one_page(struct page *page,
                                   struct zone *zone, unsigned int order) {
    unsigned long page_idx;
    int order_size = 1 << order;
    // ...
    while (order < MAX_ORDER-1) {
        struct page *buddy = __page_find_buddy(page, page_idx, order);
        if (!page_is_buddy(page, buddy, order))
            break;
        list_del(&buddy->lru);
        zone->free_area[order].nr_free--;
        rmv_page_order(buddy);
        // merge logic ...
        order++;
    }
    set_page_order(page, order);
    list_add(&page->lru, &zone->free_area[order].free_list);
    zone->free_area[order].nr_free++;
}

The function repeatedly checks whether the buddy of the freed block is also free; if so, it merges them into a higher‑order block, continuing until no further merge is possible.

7. Advantages and disadvantages

Eliminates external fragmentation by always keeping free blocks in power‑of‑two sizes and merging buddies.

Fast allocation and deallocation using simple bit‑operations and linked‑list manipulations.

Can cause internal fragmentation because allocations are rounded up to the next power of two.

May still leave unusable external fragments when free blocks cannot be merged due to mismatched buddy relationships.

Splitting and merging involve non‑trivial list and bitmap updates, adding some overhead.

Overall, the Linux buddy system provides an effective balance between speed and memory utilization for kernel‑level page management.