What You Will Learn

• Why the page allocator organizes free memory into power-of-two-sized lists
• How a block is split into two “buddies” when the exact size you need isn’t free
• How two free buddies merge back into a larger block when memory is released
• Why large allocations can fail purely due to fragmentation, even with free RAM available
• How to read /proc/buddyinfo to see the buddy allocator’s real state
• Why the SLAB/SLUB allocator exists on top of the buddy system

Prerequisites

• The previous lecture on the linux page allocator API (alloc_pages, order, GFP flags)
• Basic familiarity with linked lists and binary powers of two
• A Linux system with kernel headers for the demo driver

The Core Idea: Free Lists Per Order

The buddy allocator keeps one free list per order — one list for single free pages (order 0), one for free 2-page blocks (order 1), one for 4-page blocks (order 2), and so on up to the maximum order. Every block on every list is, by construction, a power-of-two number of pages, and every block’s starting address is aligned to its own size.

Splitting: What Happens on Allocation

When a request for order N arrives and the order-N list is empty, the allocator does not give up — it looks at order N+1. If that list has a block, the allocator splits it in half: one half satisfies the request, and the other half — the “buddy” — is placed on the order-N free list for someone else to use later. If order N+1 is also empty, the search continues upward, recursively, until a non-empty list is found or the top order is reached with nothing free.

Merging: What Happens on Free

Freeing works in reverse. When a block is released, the allocator computes the address of its buddy (the block of the same size it would have been split from) and checks whether that buddy is also free. If it is, the two merge into one block of the next order up, and the allocator immediately repeats the check one level higher. This continues until either the buddy at the next level isn’t free, or the maximum order is reached. This is what keeps memory from staying permanently fragmented into tiny pieces.

Splitting and Merging Compared

Event	Direction	Effect on free lists
Allocation, exact order available	—	Block removed from its own order’s list
Allocation, exact order unavailable	Split (downward)	Larger block splits; buddy added to a lower-order list
Free, buddy busy	—	Block simply added back to its own order’s list
Free, buddy also free	Merge (upward)	Both removed, combined block added to next order up, repeat check

Why Large Allocations Can Fail

Because a block can only merge with its specific buddy — not with any nearby free memory — a system can have gigabytes of free RAM scattered as order-0 and order-1 blocks and still fail an order-6 request. This is external fragmentation, and it is the buddy algorithm’s central trade-off: fast, simple splitting and merging, in exchange for the possibility that high-order allocations fail even when total free memory looks generous. This is exactly why the page allocator lecture recommended keeping driver allocations at low orders wherever possible.

Original Driver: ep_buddy_probe_demo

This driver deliberately requests several orders in a row and reports which ones fail, so you can watch fragmentation behaviour directly.

#include <linux/module.h>
#include <linux/init.h>
#include <linux/gfp.h>
#include <linux/mm.h>

#define EP_MAX_ORDER_TEST 6
static struct page *ep_pages[EP_MAX_ORDER_TEST + 1];

static int __init ep_buddy_probe_init(void)
{
    int order;

    for (order = 0; order <= EP_MAX_ORDER_TEST; order++) {
        ep_pages[order] = alloc_pages(GFP_KERNEL, order);
        if (ep_pages[order])
            pr_info("ep_buddy_probe_demo: order %d (%lu KB) OK\n",
                    order, (PAGE_SIZE >> 10) << order);
        else
            pr_warn("ep_buddy_probe_demo: order %d FAILED\n", order);
    }
    return 0;
}

static void __exit ep_buddy_probe_exit(void)
{
    int order;

    for (order = 0; order <= EP_MAX_ORDER_TEST; order++)
        if (ep_pages[order])
            __free_pages(ep_pages[order], order);

    pr_info("ep_buddy_probe_demo: all test allocations freed\n");
}

module_init(ep_buddy_probe_init);
module_exit(ep_buddy_probe_exit);
MODULE_LICENSE("GPL");
MODULE_DESCRIPTION("EmbeddedPathashala buddy allocator probe demo");

Build and Run

make -C /lib/modules/$(uname -r)/build M=$PWD modules
sudo insmod ep_buddy_probe_demo.ko
dmesg | tail -8
cat /proc/buddyinfo
sudo rmmod ep_buddy_probe_demo

Expected Output

[ 1203.114221] ep_buddy_probe_demo: order 0 (4 KB) OK
[ 1203.114230] ep_buddy_probe_demo: order 1 (8 KB) OK
[ 1203.114235] ep_buddy_probe_demo: order 2 (16 KB) OK
[ 1203.114239] ep_buddy_probe_demo: order 3 (32 KB) OK
[ 1203.114243] ep_buddy_probe_demo: order 4 (64 KB) OK
[ 1203.114247] ep_buddy_probe_demo: order 5 (128 KB) OK
[ 1203.114251] ep_buddy_probe_demo: order 6 (256 KB) OK
[ 1203.115501] ep_buddy_probe_demo: all test allocations freed

The /proc/buddyinfo output shows the free-list counts per order, per zone, directly from the running kernel — the same lists this lecture just described:

$ cat /proc/buddyinfo
Node 0, zone   Normal   312  198  102   54   23   11    5    2    1    0    0

Why the Slab Allocator Exists

The buddy allocator is efficient for page-sized and multi-page requests, but the kernel constantly needs much smaller, fixed-size objects — task_struct instances, inode caches, small driver buffers measured in tens or hundreds of bytes. Asking the buddy allocator for a whole 4 KB page every time you need a 64-byte object would waste huge amounts of memory and cause needless fragmentation. The slab allocator (SLUB on current kernels — the classic SLAB implementation was replaced as the default years ago) solves this: it requests pages from the buddy allocator in bulk, then carves them into same-sized “slabs” of objects that can be allocated and freed cheaply, without going back to the buddy system every time. This is exactly the layer kmalloc() sits on, and it is the subject of our next lecture.

Real-World Use Cases

• Memory-pressure debugging: reading /proc/buddyinfo to diagnose why large driver allocations intermittently fail on a long-running system
• Driver design: deciding whether to request pages directly (low order, DMA buffers) or rely on kmalloc/vmalloc for everything else
• Kernel compaction tuning: understanding why /proc/sys/vm/compact_memory exists and when it helps

Common Mistakes

Mistake	Consequence	Fix
Assuming “enough free RAM” guarantees a high-order allocation will succeed	Allocation failure despite free memory	Design for lower orders, or use vmalloc() for large non-contiguous-OK buffers
Ignoring /proc/buddyinfo during driver debugging	Missed fragmentation as the real root cause	Check buddyinfo before assuming a leak
Requesting page-allocator memory for many tiny objects	Wasted memory, driver-induced fragmentation	Use kmalloc()/kmem_cache for small fixed-size objects

Best Practices

• Reserve any critical high-order DMA buffers early at boot, before the system has had time to fragment
• Prefer kmalloc() for anything well under a page in size — let the slab layer do the bulk work
• Use __GFP_RETRY_MAYFAIL when a higher-order allocation is genuinely worth retrying instead of failing immediately

Performance Considerations

Splitting and merging are both O(log(max_order)) in the worst case — cheap operations — which is why the buddy allocator remains fast even under load. The real performance cost appears when fragmentation forces the kernel into reclaim or compaction to satisfy a high-order request, which can add significant latency compared to a simple free-list pop.

Security Considerations

Because buddies merge automatically, freed memory can be re-split and handed to a completely different, unrelated caller almost immediately. Never assume freed kernel memory is inert — always zero sensitive data before freeing it if it must not leak to the next consumer of that page.

Summary / Key Takeaways

• The buddy allocator keeps one free list per order, from 0 up to the maximum order
• Allocation splits a larger block when the exact size isn’t available; the leftover half becomes the “buddy”
• Freeing checks whether a block’s buddy is also free and merges upward, repeatedly, if so
• External fragmentation can fail high-order requests even with plenty of total free memory
• /proc/buddyinfo shows the real, live state of every free list
• The slab allocator (SLUB) is built on top of the buddy allocator to serve small, fixed-size objects efficiently

Conclusion

The buddy algorithm is a small, elegant idea — power-of-two blocks, split on demand, merge on release — but it explains a huge amount of real-world kernel behaviour, from why /proc/buddyinfo looks the way it does to why large DMA allocations should happen early at boot. With the page allocator and buddy system now covered, the next lecture in this free linux kernel development course moves up a layer to the SLUB allocator and kmalloc() internals — how the kernel serves millions of small allocations per second without going back to the buddy system every time.

FAQ

What is the linux buddy algorithm?

It’s the internal mechanism the Linux page allocator uses to manage free memory in power-of-two blocks, splitting larger blocks to satisfy smaller requests and merging freed blocks with their “buddy” to reduce fragmentation.

What is a “buddy” in the buddy system?

The buddy of a block is the other equal-sized block it would have been split from (or would merge with) — its address is computed from the block’s own address using its order.

Why do large memory allocations sometimes fail even with free RAM?

Because the buddy allocator can only merge a block with its specific buddy, free memory can be scattered as many small blocks (external fragmentation) that can’t combine into one large contiguous block.

How do I see the buddy allocator’s live state?

Read /proc/buddyinfo — it lists the free block count for every order, per memory zone, per NUMA node.

What’s the difference between the buddy allocator and the slab allocator?

The buddy allocator manages whole pages in power-of-two blocks. The slab allocator (SLUB) requests pages from the buddy allocator and slices them into small, fixed-size objects that kmalloc() serves efficiently.

Is SLAB still used in current Linux kernels?

No — the classic SLAB implementation has been replaced by SLUB as the default kmalloc backend in current mainline kernels; SLUB is what this course covers going forward.

What is this course?

This lecture is part of EmbeddedPathashala’s free linux kernel development course, a free embedded systems course covering kernel internals and device drivers on current 6.x kernels.