Long Article 102: Memory Management – Physical: In-Depth Buddy System Analysis — From Theory to Industrial Implementation

Long Article 102: Memory Management – Physical: In-Depth Buddy System Analysis — From Theory to Industrial Implementation

“The Buddy allocator is far more than just ‘split and merge.’ This article dives into Linux kernel source-level implementation, systematically analyzing watermark management, migration types, per-CPU page frame caches, compound pages, and other core mechanisms, providing a runnable industrial-grade implementation framework.”

Introduction

In an OS memory management subsystem, the Physical Memory Allocator bears the most fundamental and critical role: efficiently managing physical page frames. Since Knuth proposed the Buddy system in the 1960s, this algorithm has become the standard choice for virtually all modern operating systems due to its simplicity and effective fragmentation control.

Linux’s Buddy allocator has evolved over 20+ years from a simple implementation into a complex system featuring watermark management, migration types, per-CPU caching, compound page support, and NUMA awareness.

These features address real production challenges:

• Memory exhaustion deadlock: kernel critical paths need emergency memory
• External fragmentation: non-movable pages prevent large block allocation
• Multi-core performance bottleneck: severe global lock contention
• TLB pressure: 4KB small pages deplete TLB entries quickly
• NUMA latency: cross-node memory access performance degradation

Theoretical Foundation: Address Arithmetic

The Buddy system’s core idea stems from binary address symmetry. For a memory block of size 2^n pages, its buddy’s address can be obtained via a simple XOR operation:

buddy_addr = addr ⊕ 2^n × PAGE_SIZE

In PFN (Page Frame Number) space, the formula simplifies to:
buddy_pfn = pfn ⊕ 2^n

This address arithmetic gives O(1) time complexity — no traversal or search needed.

Free Block Management: Bitmap vs Free List

Bitmap approach: each block has 1 bit (1=free, 0=allocated). Minimal memory (1 bit/block), but merging requires traversal.
Free List approach: each order maintains a free block list with embedded list pointers. Split/merge is O(1). Linux uses this approach.