Buddy Allocator

#internals#mm#buddy_allocator#page_struct#pcp

Physical RAM is basically one big array of page frames. The kernel needs some way to hand those pages out to different users . For instance, SLUB needs pages to build slabs, alloc_pages() needs them for larger allocations, page tables need them, and so on.

Linux’s answer is the buddy allocator (mm/page_alloc.c). It manages memory as blocks of size 2^order pages , order 0 is a single page, order 1 is 2 pages, order 2 is 4 pages, and so on up to MAX_ORDER. The interesting part is how the allocator keeps track of these blocks without having to search the entire memory space.

  • Every block has exactly one buddy of the same size — the other half of the larger block it could be merged into.
  • The address of that buddy can be calculated directly with an XOR, so the allocator doesn’t have to search for it.

The rest of this note builds up both of those properties from scratch.

1. Blocks, splitting, and the buddy relationship

Imagine a toy machine with only 8 pages of RAM:

+----+----+----+----+----+----+----+----+
| P0 | P1 | P2 | P3 | P4 | P5 | P6 | P7 |
+----+----+----+----+----+----+----+----+

Initially all 8 pages are free, and the allocator sees them as one block of order 3 (2^3 = 8 pages):

+-------------------------------------------+
| P0 P1 P2 P3 P4 P5 P6 P7                   |
+-------------------------------------------+

If a caller needs less than 8 pages, the allocator splits the block exactly in half:

+-------------------+-------------------+
| P0 P1 P2 P3       | P4 P5 P6 P7       |
+-------------------+-------------------+

The two halves came from the same split, so they are called buddies:

P0-P3  <------->  P4-P7

Split the left half again:

+---------+---------+
| P0 P1   | P2 P3   |
+---------+---------+

P0-P1 and P2-P3 are now buddies of each other. Note that P0-P1 is not the buddy of P4-P5 , they were never created by the same split, even though they’re both 2-page blocks. Buddy-ness is defined by shared parentage, not by size or adjacency alone.

Split once more:

+----+----+
| P0 | P1 |
+----+----+

P0 and P1 are buddies. The full family tree for this 8-page region looks like this:

                    P0-P7
                  /       \
          P0-P3             P4-P7
         /     \           /     \
     P0-P1   P2-P3     P4-P5   P6-P7
      /  \     /  \      /  \     /  \
     P0 P1   P2 P3     P4 P5   P6 P7

Every split creates exactly two children, and those two children are each other’s buddy. This tree is the key structure the entire allocator is built around — splitting walks down it, merging walks back up it.

2. Merging — how freed memory coalesces back up

Suppose all 8 pages are currently allocated:

+----+----+----+----+----+----+----+----+
| X  | X  | X  | X  | X  | X  | X  | X  |
+----+----+----+----+----+----+----+----+

Free P0.

+----+----+----+----+----+----+----+----+
| F  | X  | X  | X  | X  | X  | X  | X  |
+----+----+----+----+----+----+----+----+

No merge happens. P0’s buddy is P1, and P1 is still allocated:

P0 (free)  +  P1 (allocated)  ->  cannot merge

Now free P1 as well:

+----+----+----+----+----+----+----+----+
| F  | F  | X  | X  | X  | X  | X  | X  |
+----+----+----+----+----+----+----+----+

The allocator asks: is P0’s buddy also free? Yes — so P0 and P1 merge into a single order-1 (2-page) block:

P0  +  P1   ->   P0-P1   (a 2-page block)

The allocator then re-asks the same question one level up: does this new P0-P1 block have a free buddy? From the family tree, the buddy of P0-P1 is P2-P3. If P2 and P3 are still allocated:

P0-P1 (free)  +  P2-P3 (allocated)  ->  no merge, stop

Later, P2 and P3 are freed too:

+----+----+----+----+----+----+----+----+
| F  | F  | F  | F  | X  | X  | X  | X  |
+----+----+----+----+----+----+----+----+

P2 and P3 merge into P2-P3, and the allocator checks again: can P0-P1 merge with P2-P3? Yes — they’re buddies.

+---------+---------+          +-------------------+
| P0-P1   | P2-P3   |    ->    | P0 P1 P2 P3       |
+---------+---------+          +-------------------+

That produces one order-2 (4-page) block. The buddy of P0-P3 is P4-P7; if those are still allocated, merging stops there. Once P4-P7 also become fully free:

+-------------------+-------------------+
| P0 P1 P2 P3       | P4 P5 P6 P7       |
+-------------------+-------------------+

both halves merge one final time back into the original order-3 block:

+---------------------------------------+
| P0 P1 P2 P3 P4 P5 P6 P7               |
+---------------------------------------+

Why only buddies can merge

For example, imagine:

P0 P1 | P2 P3 | P4 P5 | P6 P7

Now suppose P2-P3 and P6-P7 are both free. They’re both 2-page blocks, so why not combine them into a larger block?

The problem is that they aren’t physically adjacent:

P2 P3       P4 P5       P6 P7
└─ free ─┘   allocated   └─ free ─┘

There are still two allocated pages sitting between them. Combining P2-P3 and P6-P7 would give us something that isn’t actually one contiguous physical region.

And that’s a fundamental rule of the buddy allocator:

Every block represents one contiguous range of physical pages.

The buddy system solves this by only allowing two blocks to merge when they are buddies. A pair of buddies is guaranteed to be adjacent because they are simply the two halves of the same larger block.

So the would ask something like: “Is my buddy free?” If it is, they can merge. If it isn’t, the block stays as it is.

3. Finding the buddy without searching — the XOR trick

The allocator needs to find a block’s buddy when freeing memory. It could search the free list, but that would be slow. Instead, the buddy allocator calculates the buddy’s PFN directly using XOR.

Order Block size Bit that differs
0 1 page bit 0
1 2 pages bit 1
2 4 pages bit 2
3 8 pages bit 3

For example, for order 1:

P0-P1  starts at 000
P2-P3  starts at 010
          ↑
        bit 1

The two buddy blocks differ only in bit order. So the kernel can find the buddy with:

buddy_pfn = pfn ^ (1 << order);

Here:

  • pfn is the starting page frame number.
  • order determines the block size and therefore which bit to flip.

    Example

  • For P2-P3 (order 1): 
    pfn       = 2  =  010
1 << 1    =       010
               -----
                000 = 0

  • So its buddy is P0-P1.

  • For P4-P7 (order 2):
pfn       = 4  = 100
1 << 2    =      100
                 -----
                  000 = 0
  • So its buddy is P0-P3.

The reason this works is that every split divides a block into two equal halves. The two halves differ in exactly one bit , the bit corresponding to their order. Flipping that bit jumps directly from one buddy to the other, with no searching required.

4. Concurrency: zone->lock

The buddy allocator’s free lists are shared between CPUs, so they need synchronization.

Why a lock is needed ? Imagine two CPUs allocating from the same free list:

Free list: [page100, page101, page102]

CPU0 → sees page100
CPU1 → sees page100

Without locking, both CPUs could receive the same page, causing memory corruption. The same problem can happen while freeing pages: two CPUs could try to modify the same free list or merge the same buddy pair at the same time.

4.1 zone->lock

Linux protects each zone’s buddy lists with a spinlock:

spin_lock_irqsave(&zone->lock, ...);

Each struct zone has its own lock:

struct zone {
    ...
    spinlock_t lock;
    ...
};

So allocations in different zones can happen concurrently:

CPU0 → ZONE_DMA    → zone->lock
CPU1 → ZONE_NORMAL → zone->lock

But operations within the same zone still serialize on that zone’s lock.

4.3 The scaling problem

On a many-core system, constantly doing: lock -> free -> unlock, creates lock contention. CPUs spend time waiting for zone->lock instead of doing useful work.

This is one reason Linux uses a per-CPU page cache (PCP) in front of the buddy allocator: most order-0 allocations and frees can be handled locally without taking zone->lock.

5. The per-CPU page cache (PCP)

Linux’s fix is to give every CPU its own small, lock-free stash of pages.

                Buddy Allocator
                (large warehouse)
                       │
        ┌──────────────┼──────────────┐
        ▼               ▼               ▼
   CPU0 shelf       CPU1 shelf       CPU2 shelf
   (PCP list)       (PCP list)       (PCP list)

5.1 Fast-path allocation

When CPU0 wants a page, it checks its own shelf first:

CPU0 PCP: [page20, page35, page41]

It just pops page20 off that local list. No trip to the buddy allocator, no zone->lock.

5.2 Fast-path freeing

Freeing works the same way in reverse: instead of immediately handing the page back to the buddy allocator, Linux just appends it to the local PCP list:

CPU0 PCP before: [page20, page35]
CPU0 frees page100
CPU0 PCP after:  [page20, page35, page100]

  • Draining: PCP → buddy allocator

    The local list can’t grow forever. Once it crosses the hard-coded limit, Linux drains a batch of it back into the real buddy allocator. This is where free_one_page() (the actual coalescing routine) finally runs, taking zone->lock once for the whole batch instead of once per freed page.

  • Refilling: buddy allocator → PCP

    Similarly, when CPU0’s PCP is empty and it needs a page, Linux doesn’t ask the buddy allocator for one page, it asks for several at once. This bulk refill is what rmqueue_bulk() does.

6. From a PFN to a struct page and back

The kernel represents every physical page with a struct page, and needs to convert between “page frame number” and “pointer to that page’s metadata” constantly. For that, there is one big array:

struct page mem_map[10000];

mem_map
+-----------+
| page[0]   |  address 0x1000
+-----------+
| page[1]   |  address 0x1040
+-----------+
| page[2]   |  address 0x1080
+-----------+
| page[3]   |  address 0x10c0
+-----------+

(assume sizeof(struct page) == 64).

6.1 struct page * → PFN is pointer subtraction

struct page *p = &mem_map[3];   // p == 0x10c0

p only holds an address , it does not carry “index 3” anywhere inside it. To recover the index, Linux uses the fact that it knows exactly where mem_map starts:

index = (address_of(p) - address_of(mem_map)) / sizeof(struct page)
      = (0x10c0 - 0x1000) / 64
      = 0xc0 / 0x40
      = 3

So PFN = 3.

6.2 PFN → struct page * is array indexing

Going the other way, given PFN = 500:

struct page *page = &mem_map[500];   // pfn_to_page(500)
// conceptually: return mem_map + 500;

6.3 Real Linux: the sparse memory model

The mental model

PFN → mem_map[PFN] → struct page

This is useful for understanding the concept, but modern Linux doesn’t always have one giant mem_map[] array containing every possible physical page.

The reason is that physical memory isn’t necessarily one continuous range. There can be holes in the physical address space. Linux solves this with the sparse memory model. Instead of one huge array, the struct page objects are divided into memory sections:

Memory section 0
    └── struct page array for PFNs 0 – 131071

Memory section 1
    └── struct page array for PFNs 131072 – 262143

Memory section 2
    └── struct page array for PFNs 262144 – 393215
  • It doesn’t search through all sections. The section number and the offset within the section can be calculated directly, so pfn_to_page() is still effectively O(1).