← Previous Lecture

Next Lecture →

What You Will Learn

Prerequisites

Why Memory Is Allocated in Pages

The CPU’s Memory Management Unit (MMU) does not understand “bytes” the way user-space programmers think about malloc(). The MMU works with fixed-size chunks called pages, almost always 4 KB on most architectures (some platforms support larger base page sizes). Because of this hardware reality, the Linux kernel’s lowest level allocator — the buddy system page allocator (often called the Buddy System Allocator or BSA) — only ever hands out memory in whole pages, and more specifically, in power-of-2 groups of pages.

This single design decision drives everything else in this lecture: how free lists are organized, how splitting and merging happen, and why certain allocation sizes are wasteful.

Node, Zone, and the Concept of an “Order”

On any real system, physical memory is logically divided into nodes (each node usually maps to a physical memory bank, especially important on NUMA systems with multiple CPU sockets) and within each node, into zones (such as ZONE_DMA, ZONE_NORMAL, ZONE_HIGHMEM on 32-bit systems, or ZONE_MOVABLE on modern kernels). Every distinct node:zone combination on the system maintains its own independent set of free lists.

Each free list is indexed by what the kernel calls an order. An order simply tells you how many contiguous pages are grouped together as one chunk:

The highest usable order is bounded by a kernel constant. It is worth noting that this constant’s meaning changed in kernel 6.5: previously MAX_ORDER was the highest valid order itself, but from 6.5 onward it represents an exclusive upper bound (the highest valid order is now MAX_ORDER - 1). If you are reading older training material or an older textbook, keep this version detail in mind so your math doesn’t end up off by one order.

How an Allocation Request Actually Flows

Picture a driver asking the kernel for some pages. Conceptually, here is the order-search logic the allocator follows:

In plain language: the allocator picks the smallest order list that satisfies the request. If that exact list is empty, it borrows from the next bigger list and splits that chunk into two equal “buddy” halves — one half goes to the requester, the other half is queued back onto the lower order list for future use. If even the bigger lists are empty, the kernel may trigger memory reclaim or compaction before failing the request.

The Power of Merging (Coalescing)

The real elegance of this algorithm shows up at free time, not allocation time. When a chunk is freed, the kernel checks whether the chunk’s “buddy” (its size-matched, address-adjacent neighbour) is also free. If it is, the two are merged back into one larger chunk and pushed up to the next order’s list. This process can repeat several times, naturally healing fragmentation without any separate defragmentation pass — a property that makes the buddy system genuinely elegant compared to a flat free-list allocator.

Internal Fragmentation: The Honest Downside

Because the allocator only deals in power-of-2 sized chunks, an odd-sized request gets rounded up. A request for slightly more than 128 KB, for example, is satisfied from the 256 KB order list, wasting close to half the allocated memory. This waste is called internal fragmentation, and it is the well-known weak point of any binary buddy allocator.

Modern Kernel APIs You Should Actually Call

You will rarely call the buddy allocator directly. Instead, modern kernel code uses well-defined wrapper APIs:

struct page *alloc_pages(gfp_t gfp_mask, unsigned int order);
void        *page_address(struct page *page);
unsigned long get_free_page(gfp_t gfp_mask);
void         __free_pages(struct page *page, unsigned int order);

For odd-sized requests where you want the kernel to round up internally but free exactly what you used (avoiding the fragmentation problem described above), use:

void *alloc_pages_exact(size_t size, gfp_t gfp_mask);
void  free_pages_exact(void *virt, size_t size);

In day-to-day driver work, you usually won’t touch the page allocator at all — instead you reach for kmalloc() for small physically contiguous allocations (which itself is built on top of the slab/slub allocator, which in turn gets its backing pages from the buddy allocator) or vmalloc() for large virtually-contiguous allocations. This layered design — buddy allocator at the bottom, slab/slub in the middle, kmalloc/vmalloc as the driver-facing API — is one of the most important architectural facts to internalize in this free Linux kernel development course.

NUMA Awareness

On multi-socket servers, accessing memory attached to a remote CPU socket is slower than accessing local memory. Because every node maintains its own zone free lists, the buddy allocator naturally prefers the free list belonging to the node the requesting thread is currently running on. Only if that node is exhausted does the kernel fall back to other nodes, following a per-node fallback order maintained internally by the memory management subsystem.

Real-World Use Cases

Common Mistakes and Troubleshooting

Best Practices

Performance and Security Considerations

Performance: Splitting and merging are O(log n) operations relative to the order, making the buddy allocator predictable even under load — a major reason it has remained the kernel’s core allocator for decades. Security: Improperly sized or unchecked allocations can lead to heap-adjacent memory disclosure or corruption in driver code; always validate sizes coming from user space before passing them into any allocation path.

Summary / Key Takeaways

Conclusion

The buddy system page allocator is the silent foundation underneath every memory allocation in the Linux kernel. As part of this free Linux kernel development course and free Linux device drivers course, mastering its order-based free lists, the split/merge dance, and where it fits relative to slab/slub and vmalloc will make every future memory management lecture in this series click into place much faster.

FAQ

← Previous Lecture
Next Lecture →