Understanding the Linux Kernel Buddy Memory Allocation Algorithm

Introduction

Memory in a computer system functions like blood in a body, continuously delivering data and instructions to programs and processes; efficient memory management is crucial for system performance, especially when running multiple applications, large games, or complex data processing.

In Linux, the kernel's memory management is the foundation of system stability, and the buddy algorithm is a powerful technique that allocates memory efficiently while minimizing fragmentation.

1. Buddy Algorithm Overview

The buddy algorithm is a dynamic storage management method that treats memory as a series of fixed‑size page blocks. Free blocks are organized into 11 lists, each representing a size of 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, or 1024 contiguous pages, acting like a set of resource warehouses.

By repeatedly splitting larger blocks into equal‑sized buddies, the algorithm can satisfy allocation requests and later merge free buddies to reduce external fragmentation.

2. Core Principles of the Buddy System

2.1 The Concept of a Buddy

A buddy pair consists of two blocks of the same size that are contiguous in physical memory and originate from the same larger block. For example, an 8‑page block split into two 4‑page blocks creates a buddy relationship.

During allocation, if an exact‑size block is unavailable, the algorithm splits a larger block, allocating one half and returning the other as a free buddy. During reclamation, if a freed block’s buddy is also free, the two are merged into a larger block.

2.2 Allocation Process

When a process requests memory, the algorithm determines the smallest order k such that 2^k ≥ requested pages. It then searches the free list for that order. If the list is empty, it looks for a larger order, splits the block, allocates one half, and inserts the other half into the appropriate free list. If no suitable block exists up to the maximum order, allocation fails.

Example: To allocate 8 pages, the algorithm looks for an order‑3 block. If none exists, it finds a 16‑page block (order‑4), splits it into two 8‑page buddies, allocates one, and places the other into the order‑3 list.

2.3 Reclamation Process

When a block is freed, it is inserted into its order’s free list. The algorithm then checks whether its buddy is also free; if so, the two are merged into the next higher order. This merging repeats until the buddy is not free or the maximum order is reached.

3. Implementation and Data Structures

3.1 Key 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 represents a memory zone (e.g., ZONE_DMA, ZONE_NORMAL, ZONE_HIGHMEM). Each free_area holds a linked list of free blocks of a specific order, and nr_free tracks how many blocks are available.

Each physical page is described by a struct page object; its lru field links it into the appropriate free list, and the private field stores the block’s order.

3.2 System Initialization

During early kernel boot, memory is managed by the bootmem allocator. When mem_init runs, bootmem’s free pages are transferred to the buddy system via __free_all_bootmem , which calls free_page for each page, populating the free_area lists.

3.3 Allocation Code

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--;

zone->free_pages -= 1UL << order;

return expand(zone, page, order, current_order, area);

}

3.4 Reclamation Code

free_pages_bulk iterates over the pages to be freed, removes each from its list, and then attempts to merge with its buddy:

while (order < MAX_ORDER-1) {

buddy_idx = (page_idx ^ (1 << order));

buddy = base + buddy_idx;

if (!page_is_buddy(buddy, order))

break;

list_del(&buddy->lru);

zone->free_area[order].nr_free--;

rmv_page_order(buddy);

page_idx &= buddy_idx;

order++;

}

After merging, the resulting block is inserted into the appropriate free list.

4. Advantages and Disadvantages

Advantages

Reduces external fragmentation by keeping free blocks in powers‑of‑two sizes.

Improves memory utilization through efficient merging of buddies.

Provides fast allocation and reclamation via simple list operations.

Disadvantages

Can cause internal fragmentation when request sizes are not powers of two.

Allocation granularity is limited to powers of two, reducing flexibility for small or irregular requests.

Merging only occurs when both buddies are free; otherwise fragmentation may remain.

5. Application Scenarios and Optimizations

The buddy system is used for process memory allocation, device driver buffers, and memory‑mapped file systems. Optimizations include adaptive allocation strategies, hash‑table‑assisted free‑block lookup, and hybrid schemes that combine the buddy allocator with slab allocators for small objects.

6. Evolution Across Linux Versions

From early kernels to Linux 2.6, the buddy allocator gained hot‑plug support and improved allocation heuristics. Linux 3.x introduced migration‑type aware allocation, enhancing flexibility. Later kernels (4.x and beyond) refined locking for high concurrency and added auxiliary data structures such as hash tables to speed up searches.