357 | Memory Management: Buddy System

Key Insight: Cut memory into neat power-of-2-sized blocks, merge when freed, merge when freed, merge when freed. This “divide and merge” algorithm is the starting point of Linux physical memory management.

1. What Problem Does the Buddy System Solve?

The core problem in physical memory allocation is fragmentation.

Assume we have 512KB of physical memory, and at a certain moment it’s allocated as follows:

Allocated:  [ 64KB ][ 128KB ][ 32KB ]
Free:       [  96KB         ][ 192KB ]

Now a program comes along requesting 128KB: the largest remaining contiguous blocks are 96KB + 192KB = 288KB, but they are not contiguous, so the 128KB contiguous allocation cannot be satisfied.

This is external fragmentation: the total memory is sufficient, but contiguous space is not.

Buddy System solves this with a simple rule: Always allocate blocks in powers of 2; when freeing, always try to merge adjacent same-size buddies.

2. Basic Idea: Divide and Conquer

Assume we have 8MB of physical memory, starting from 8MB:

Initial state (order=23, meaning 2^23 * PAGE_SIZE = 8MB):
┌─────────────────────────────────────┐
│              8MB                    │  ← One large block
└─────────────────────────────────────┘

Need to allocate 1MB = 2^20?

First split (8MB → two 4MB blocks):
┌───────────────┬───────────────┐
│     4MB       │     4MB       │
│   (Free)      │   (Free)      │
└───────────────┴───────────────┘

Second split (4MB → two 2MB blocks):
┌───────┬───────┬───────────────┐
│  2MB  │  2MB  │    4MB       │
└───────┴───────┴───────────────┘

Third split (2MB → two 1MB blocks):
┌─────┬─────┬───────┬───────────┐
│ 1MB │ 1MB │  2MB  │   4MB     │
└─────┴─────┴───────┴───────────┘

Allocate the first 1MB block:
┌─────┬ [1MB] ────────┬──────────┐
│ 1MB │ (Allocated)  │   4MB    │
└─────┴───────────────┴──────────┘

The two blocks produced by each split are each other’s Buddies: their physical addresses are contiguous and they are the same size.

3. Definition of a Buddy

Two blocks are buddies if and only if:

1. Same size (both are 2^k)
2. Physically contiguous
3. Address relationship: The start address of one block is start address of the other block + size

Example (1MB blocks):
Block A start address 0x00000000, size 1MB
Block B start address 0x00100000, size 1MB
Block A and Block B are buddies

Block C start address 0x00080000, size 1MB
Block C and Block A are NOT buddies (not contiguous)

When freeing, the kernel checks if the buddy is also free. If so, they are merged into a larger block.

4. Data Structure: free_area Array

Linux uses the free_area array to manage the free block list for each order:

#define MAX_ORDER 11    // Max 2^11 * 4KB = 8MB

struct zone {
    struct free_area    free_area[MAX_ORDER];
    unsigned long       start_pfn, end_pfn;
    ...
};

struct free_area {
    struct list_head    free_list[MIGRATE_TYPES];
    unsigned long       nr_free;
};

free_area[0] manages… [truncated]