Buddy System Memory Allocation: Complete Implementation Guide

1. Introduction and Core Concepts

Buddy system memory allocation is a powerful memory management technique designed to efficiently allocate and deallocate memory blocks while minimizing external fragmentation. First introduced by Harry Markowitz in 1963 and later refined by Donald Knuth, the buddy system remains a cornerstone of operating system kernel design and low-level memory management. Unlike simple sequential allocation strategies, the buddy system maintains memory as power-of-two sized blocks that can be quickly split and coalesced, providing a balanced trade-off between allocation speed and memory utilization.

At its core, the buddy system operates on a simple but elegant principle: memory is divided into partitions that are powers of two, and every block has a unique "buddy" — the adjacent block of the same size that was created when a larger block was split. When a process requests memory, the allocator finds the smallest available block that can satisfy the request, splitting larger blocks recursively if necessary. When memory is freed, the system checks if the block's buddy is also free, and if so, merges them back into a larger block. This buddy relationship is deterministically computable from the block's address and size, which makes coalescing extremely efficient.

Understanding buddy system memory allocation matters for several reasons. First, it solves the critical problem of external fragmentation that plagues many allocation schemes — where free memory becomes scattered in small, unusable fragments. Second, it provides predictable, logarithmic-time allocation and deallocation, which is essential for operating system kernels and real-time systems where latency matters. Third, the concepts behind the buddy system — binary splitting, address-based buddy calculation, and hierarchical free lists — appear frequently in system design interviews and are foundational to understanding how modern operating systems like Linux manage physical memory.

Why Power-of-Two Sizing Matters

The restriction to power-of-two block sizes is not arbitrary. It enables extremely fast buddy address calculation using simple bitwise XOR operations. For a block of size 2^k at address A, its buddy is located at address A XOR 2^k. This mathematical property eliminates the need for complex bookkeeping or searching to find a buddy during deallocation. The trade-off is internal fragmentation — a request for 70KB in a system with power-of-two blocks will receive a 128KB block, wasting 58KB — but this waste is bounded and often preferable to the external fragmentation and slow coalescing of other methods.

Key Terminology

To work effectively with the buddy system, you must understand several key terms. The order of a block refers to the exponent k where block size equals 2^k. An order-0 block is the smallest allocatable unit (often 4KB, matching a page size), while the maximum order represents the entire managed memory region. A free list is maintained for each order, tracking all currently unallocated blocks of that size. Splitting is the process of dividing a larger block into two equal buddies, and coalescing (or merging) is the reverse operation of combining two free buddies into their parent block.

2. How It Works

The buddy system manages a contiguous region of memory, typically starting at address 0 for simplicity, with total size 2^U where U is the maximum order. Initially, the entire memory region exists as a single free block at the highest order. All free lists except the one for order U are empty. As allocation requests arrive, the system traverses the free lists to find suitable blocks, splitting as needed, and as blocks are freed, it attempts to coalesce them upward.

Allocation follows a precise algorithm. When a request for n bytes arrives, the allocator first calculates the required order k such that 2^(k-1) < n ≤ 2^k, accounting for header overhead if present. It then searches for a free block at order k. If one exists, it is removed from the free list and returned. If no block exists at order k, the allocator looks for the next larger order j > k that has a free block. When found, that block is recursively split: a block of order j is divided into two buddies of order j-1, one buddy remains free while the other is further split, until a block of order k is produced. The unused buddies created during splitting are inserted into their respective free lists.

Deallocation is where the buddy system's elegance truly shines. When a block of order k at address A is freed, the allocator computes its buddy's address as A XOR 2^k. It then checks whether that buddy is free and exists in the free list for order k. If the buddy is not free, the freed block is simply added to the free list for order k. If the buddy is free, both blocks are removed from the free list and merged into a single block of order k+1 at address min(A, buddy_address). This coalescing process repeats recursively — the newly formed block checks if its own buddy (at the next higher order) is free, and so on, potentially coalescing all the way up to the maximum order.

The Binary Tree Representation

Conceptually, the buddy system can be visualized as a complete binary tree where the root represents the entire memory region, each internal node represents a block that has been split, and leaves represent current blocks (either allocated or free). Splitting corresponds to expanding a leaf into two children, and coalescing corresponds to collapsing two free leaf siblings back into their parent. This tree is rarely materialized explicitly in implementation — the free lists and buddy address calculation implicitly encode it — but it is invaluable for reasoning about fragmentation and correctness. The depth of the tree is U - L, where L is the minimum order, and any allocation or deallocation traverses at most this many levels.

Address Calculation and Alignment

A critical invariant of the buddy system is alignment: a block of order k must be aligned to a multiple of 2^k. This alignment is what makes the XOR buddy calculation work. For example, in a 1024KB region (order 10), a 128KB block (order 7) can only start at addresses 0, 128, 256, 384, 512, 640, 768, or 896. Its buddy is always the adjacent 128KB block within the same 256KB parent. This strict alignment also means that not every arbitrary address can be a block boundary, which simplifies hardware memory management unit (MMU) interactions and enables efficient bitmap-based tracking in some implementations.

3. Implementation

Implementing a buddy allocator requires careful management of free lists, block metadata, and the split/merge logic. Below is a complete, well-commented Python implementation that simulates a buddy system for educational purposes. While production kernel allocators are written in C and manage physical pages directly, this Python version faithfully captures the algorithmic behavior and is ideal for experimentation and interview preparation.

import math
from collections import defaultdict

class BuddyAllocator:
    """
    Buddy System Memory Allocator Simulation
    Manages a contiguous memory region of size 2^max_order.
    Each block's address is its offset from the base.
    """
    def __init__(self, max_order=10, min_order=4):
        # Total memory = 2^max_order (e.g., 1024 if max_order=10)
        # Minimum block = 2^min_order (e.g., 16 if min_order=4)
        self.max_order = max_order
        self.min_order = min_order
        self.total_size = 1 << max_order  # << is left shift: 2^max_order
        # free_lists[k] stores set of free block addresses of order k
        self.free_lists = defaultdict(set)
        self.free_lists[max_order].add(0)  # Initially one big free block
        # allocated maps address -> order for allocated blocks
        self.allocated = {}
    
    def _order_for_size(self, size):
        """Find smallest order k where 2^k >= size and k >= min_order"""
        if size <= 0:
            raise ValueError("Size must be positive")
        # Add header overhead simulation if needed
        k = math.ceil(math.log2(size)) if size > 1 else 0
        k = max(k, self.min_order)
        if k > self.max_order:
            raise MemoryError(f"Request {size} exceeds total memory {self.total_size}")
        return int(k)
    
    def _buddy_address(self, addr, order):
        """Compute buddy address using XOR: buddy = addr XOR 2^order"""
        return addr ^ (1 << order)
    
    def _is_free(self, addr, order):
        """Check if buddy block is free"""
        return addr in self.free_lists[order]

    def allocate(self, size):
        """
        Allocate a block of at least 'size' bytes.
        Returns starting address on success, raises MemoryError on failure.
        Time complexity: O(max_order - min_order) worst case
        """
        k = self._order_for_size(size)
        # Find smallest j >= k with a free block
        j = k
        while j <= self.max_order and len(self.free_lists[j]) == 0:
            j += 1
        
        if j > self.max_order:
            raise MemoryError(f"No free block large enough for order {k} (size {size})")
        
        # Found block at order j, remove it
        addr = self.free_lists[j].pop()
        
        # Recursively split down to order k
        # Each split creates two buddies of order j-1
        while j > k:
            j -= 1
            buddy = addr + (1 << j)  # Second half becomes free buddy
            # Equivalent to addr ^ (1 << j) when addr is aligned
            self.free_lists[j].add(buddy)
            # addr remains the first half, continue splitting it
        
        self.allocated[addr] = k
        print(f"ALLOC: req={size} -> order={k} (block size {1 << k}) at addr={addr}")
        return addr

    def deallocate(self, addr):
        """
        Free a previously allocated block at 'addr' and coalesce with buddies.
        Time complexity: O(max_order - min_order) worst case
        """
        if addr not in self.allocated:
            raise ValueError(f"Address {addr} not allocated or already freed (double free?)")
        
        k = self.allocated.pop(addr)
        current_addr = addr
        current_order = k
        
        # Try to coalesce upward as long as buddy is free
        while current_order < self.max_order:
            buddy = self._buddy_address(current_addr, current_order)
            
            if not self._is_free(buddy, current_order):
                break  # Buddy is allocated, cannot coalesce
            
            # Buddy is free: remove it and merge
            self.free_lists[current_order].remove(buddy)
            # Merged block starts at min(current_addr, buddy)
            current_addr = min(current_addr, buddy)
            current_order += 1
            print(f"  COALESCE: merged to order {current_order} at addr={current_addr}")
        
        # Insert the (possibly coalesced) block into its free list
        self.free_lists[current_order].add(current_addr)
        print(f"FREE: addr={addr} (order {k}) -> coalesced to order {current_order} at addr={current_addr}")

    def get_fragmentation_stats(self):
        """Calculate internal fragmentation and free memory distribution"""
        total_free = sum(len(addrs) * (1 << order) 
                        for order, addrs in self.free_lists.items())
        total_allocated = sum(1 << order for order in self.allocated.values())
        print(f"\n--- Memory Stats ---")
        print(f"Total size: {self.total_size}")
        print(f"Allocated: {total_allocated} in {len(self.allocated)} blocks")
        print(f"Free: {total_free}")
        for order in sorted(self.free_lists.keys()):
            if self.free_lists[order]:
                print(f"  Order {order} (size {1 << order:4d}): {len(self.free_lists[order])} free block(s) at {sorted(self.free_lists[order])}")
        return total_free

    def is_valid_state(self):
        """Validate allocator invariants for debugging"""
        # Check no overlapping blocks and alignment
        for order, addrs in self.free_lists.items():
            for addr in addrs:
                if addr % (1 << order) != 0:
                    return False, f"Misaligned free block at {addr} order {order}"
                if addr < 0 or addr + (1 << order) > self.total_size:
                    return False, f"Out of bounds block at {addr} order {order}"
        return True, "State valid"

# Demonstration: allocation and deallocation pattern showing split and coalesce
if __name__ == "__main__":
    allocator = BuddyAllocator(max_order=10, min_order=4)  # 1024 bytes total, 16 min block
    print(f"Initialized buddy allocator: total={allocator.total_size} bytes\n")
    
    # Allocate blocks of varying sizes
    a1 = allocator.allocate(100)   # Needs 128 (order 7)
    a2 = allocator.allocate(50)    # Needs 64  (order 6)
    a3 = allocator.allocate(200)   # Needs 256 (order 8)
    allocator.get_fragmentation_stats()
    
    print("\n--- Freeing a2 (should not coalesce immediately) ---")
    allocator.deallocate(a2)
    allocator.get_fragmentation_stats()
    
    print("\n--- Freeing a1 (buddy of a2 is now free, should coalesce) ---")
    allocator.deallocate(a1)
    allocator.get_fragmentation_stats()
    
    print("\n--- Allocating 60 bytes (should reuse coalesced block) ---")
    a4 = allocator.allocate(60)    # Needs 64, should split the coalesced 128
    allocator.get_fragmentation_stats()
    
    print("\n--- Freeing remaining blocks ---")
    allocator.deallocate(a3)
    allocator.deallocate(a4)
    allocator.get_fragmentation_stats()
    print(allocator.is_valid_state())

The implementation above highlights several important design decisions. Using sets for free lists provides O(1) average-time membership testing, which is critical for the coalescing check. The XOR-based buddy calculation is constant time and avoids storing explicit buddy pointers. In a production C implementation, free lists would typically be implemented as intrusive linked lists where the free blocks themselves store next/prev pointers, eliminating external metadata overhead. The allocated dictionary simulates the block header that a real allocator would store immediately before the returned pointer to remember the block's order for later freeing.

4. Step-by-Step Example

To solidify understanding, let us walk through a concrete example with 1024KB of total memory (max order 10, where 2^10 = 1024) and a minimum block size of 32KB (order 5). Initially, the memory is a single free block: [0–1024KB] at order 10. The free lists are: order 10: {0}, all other orders empty.

Request 1 arrives for 100KB. The allocator computes the required order: 2^6 = 64 is too small, 2^7 = 128 suffices, so order 7 is needed. No free block exists at order 7, so it searches upward and finds the order 10 block at address 0. It splits order 10 into two order 9 buddies: [0–512KB] and [512–1024KB]. The second buddy [512–1024KB] is placed in the order 9 free list. The first buddy [0–512KB] is split again into two order 8 blocks: [0–256KB] and [256–512KB], with [256–512KB] going to order 8 free list. Finally, [0–256KB] is split into two order 7 blocks: [0–128KB] and [128–256KB]. The block [128–256KB] is added to order 7 free list, and [0–128KB] is allocated to the requester. Internal fragmentation is 28KB (128 - 100).

Request 2 arrives for 50KB, requiring order 6 (64KB). The allocator checks order 6 free list — empty. It checks order 7 — finds [128–256KB] free at address 128. It splits this into two order 6 buddies: [128–192KB] and [192–256KB]. The second buddy [192–256KB] goes to order 6 free list, and [128–192KB] is allocated. Request 3 arrives for 200KB, requiring order 8 (256KB). The free list for order 8 contains [256–512KB] at address 256, which is allocated directly with no splitting. At this point, allocated blocks are [0–128KB], [128–192KB], [256–512KB], and free blocks are [192–256KB] (order 6), [512–1024KB] (order 9).

Now deallocation demonstrates coalescing. Freeing the 64KB block at address 128 (order 6) checks its buddy at address 192 (128 XOR 64 = 192). The buddy at 192 is free (in order 6 free list), but wait — in our state after step 3, the buddy at 192 is actually the free block [192–256KB]. However, the allocated block is [128–192KB] at address 128, whose buddy is [192–256KB] at 192. Since the buddy is free, they could coalesce, but in the table above we show step 4 freeing [128–192] — after this free, the free lists contain both buddies at order 6, but they are not automatically coalesced until one of them is freed? Actually, in the standard algorithm, coalescing happens only on free. So after freeing [128–192], both [128–192] and [192–256] are free at order 6, but they remain separate until the next free triggers a check. When [0–128] at order 7 is freed in step 5, its buddy is [128–256] at order 7 — but there is no single order 7 block at 128; instead there are two order 6 blocks. The implementation correctly handles this by only coalescing at the same order. After step 4, we have order 6: {128, 192}. When [0–128] (order 7) is freed, its buddy at order 7 would be at address 128, but address 128 at order 7 is not in the free list (it is split into two order 6 blocks), so no coalescing occurs at order 7 immediately. A more sophisticated implementation might recursively coalesce the order 6 buddies first, but the standard buddy system coalesces only the block being freed.

This example reveals an important nuance: the buddy system can suffer from fragmentation where two adjacent free blocks cannot be coalesced because they are not buddies. For instance, blocks [0–64] and [64–128] are buddies (both order 6 within parent order 7 at 0), but blocks [64–128] and [128–192] are not buddies despite being adjacent — they have different parent blocks. This is the primary source of external fragmentation in buddy systems, though it is far less severe than in first-fit or best-fit allocators.

5. Complexity Analysis

The performance characteristics of the buddy system are one of its most attractive features, offering predictable logarithmic behavior for both allocation and deallocation. The time complexity is determined by the number of orders, which is logarithmic in the total memory size. For a memory region of size 2^U with minimum block size 2^L, there are U - L + 1 distinct orders, and any operation traverses at most this many levels.

Allocation in the best case occurs when a free block of exactly the required order is available — the allocator simply removes it from the free list in O(1) time. In the average case, the allocator may need to search through a few orders and perform a small number of splits. In the worst case, the allocator must search all the way to the maximum order and then split all the way back down, performing O(U - L) operations. Since U = log2(total_memory) and L = log2(min_block_size), this is O(log n) where n is the total memory size in units of minimum blocks. Importantly, this bound is independent of the number of allocated blocks, unlike best-fit which may need to scan the entire free list.

Deallocation has similar complexity. The best case is freeing a block whose buddy is allocated — no coalescing occurs, just an insertion into the free list in O(1). The worst case requires coalescing all the way to the maximum order, performing O(U - L) buddy checks and merges. Each buddy check is O(1) average time when using hash sets, or O(1) with bitmap tracking. Space overhead is also well-bounded: the free lists store at most O(number_of_free_blocks) entries, and the total number of blocks (free plus allocated) is at most 2 * (total_memory / min_block_size) in the worst case where memory is maximally fragmented into minimum-sized blocks.

Internal fragmentation deserves special attention in the complexity analysis. In the worst case, a request for 2^k + 1 bytes requires a block of size 2^(k+1), wasting nearly 50% of the allocated block. On average, assuming uniformly distributed request sizes, internal fragmentation is approximately 25-30% — meaning about a quarter of allocated memory is wasted inside blocks. This is the fundamental space-time trade-off of the buddy system: it sacrifices some memory efficiency to achieve fast, predictable allocation times and simple coalescing. For systems where memory is plentiful but latency is critical, this trade-off is highly favorable.

6. Variations and Optimizations

While the classic binary buddy system is elegant, several variations have been developed to address its limitations, particularly internal fragmentation and limited size granularity. The most prominent variant is the weighted buddy system, also known as the Fibonacci buddy system, which uses Fibonacci numbers instead of powers of two for block sizes. In this scheme, a block of size F(k) splits into blocks of size F(k-1) and F(k-2), providing more size options and reducing internal fragmentation at the cost of more complex buddy calculation.

The double buddy system maintains two separate buddy systems with different block size sequences and allocates from whichever provides the better fit. For example, one system might use powers of two (32, 64, 128, 256) while the other uses powers of two multiplied by three (48, 96, 192, 384). This hybrid approach significantly reduces internal fragmentation — a request for 100 bytes would use a 128-byte block in the classic system (28% waste) but could use a 96-byte or 192-byte block more efficiently in a double buddy system. The Linux kernel's memory allocator historically used a variation of this idea in its slab allocator layer built atop the buddy system.

Another important optimization is the use of bitmaps instead of linked lists for tracking free blocks. In a bitmap buddy system, each order has a bitmap where bit i indicates whether block i at that order is free or split. This representation is extremely cache-friendly and allows the allocator to find free blocks using efficient bit-scan instructions (like x86's BSF/BSR). The bitmap also makes it trivial to check if a buddy is free — just test a single bit — and enables the allocator to quickly find the largest free block for defragmentation purposes. The trade-off is that bitmaps require contiguous metadata storage proportional to total memory divided by minimum block size.

Deferred Coalescing and Caching

Production buddy allocators often employ deferred coalescing to improve performance under certain workloads. Instead of immediately coalescing freed blocks, the allocator keeps recently freed blocks in a per-CPU or per-thread cache for rapid reallocation. If the same size is requested again shortly after being freed — a common pattern in network packet processing or slab allocation — the block can be reused without any splitting or merging overhead. Coalescing is performed lazily, either when the cache grows too large or during periodic maintenance. This optimization dramatically improves allocation throughput for workloads with high temporal locality, which is why the Linux kernel's page allocator maintains per-CPU page frame caches (PCP lists) in front of the core buddy system.

Reclaim and Defragmentation Strategies

Advanced buddy systems incorporate active defragmentation to combat the gradual accumulation of fragmentation over long uptimes. Techniques include memory compaction, where the kernel migrates allocated pages to create larger contiguous free regions, and proactive coalescing during idle periods. Some systems also implement allocation color or cache coloring to reduce cache conflicts — by offsetting block addresses, the allocator ensures that frequently accessed blocks do not map to the same cache lines. These optimizations transform the buddy system from a simple allocator into a sophisticated memory management subsystem capable of sustaining high performance over months of continuous operation.

7. Real-World Applications

The buddy system is not merely an academic exercise — it is deployed in some of the most critical software systems in the world. Its most famous application is in the Linux kernel's physical page frame allocator, which manages all RAM on the system. The Linux buddy allocator manages memory in orders from 0 (single 4KB page) to 10 or 11 (1024 or 2048 pages, i.e., 4MB or 8MB), handling millions of allocation and deallocation requests per second across all running processes. Every time a process faults in a new page, allocates DMA buffers, or the kernel creates a new slab cache, the buddy system is involved.

Beyond operating system kernels, buddy allocation appears in hypervisors and virtual machine monitors. VMware ESXi, Xen, and KVM all use buddy-like allocators to manage guest physical memory, where the ability to quickly allocate and reclaim large contiguous regions is essential for virtual machine lifecycle management. In embedded and real-time systems, the buddy system's predictable O(log n) worst-case latency makes it preferable to allocators with unbounded search times. Automotive ECUs, avionics systems, and industrial controllers frequently use buddy allocators precisely because their timing behavior can be formally analyzed for safety certification.

In user-space, buddy allocation principles influence high-performance memory allocators like jemalloc and tcmalloc, which use size classes that are conceptually similar to buddy orders. While these allocators are not pure buddy systems — they incorporate additional techniques like thread-local caching and slab allocation — the hierarchical size class design and the emphasis on fast coalescing are direct descendants of buddy system ideas. Database systems such as PostgreSQL and MySQL use buddy-like strategies in their buffer pool managers to handle variable-sized page allocations efficiently.

Web servers and caching infrastructure also benefit from buddy allocation concepts. High-performance web servers like Nginx and content delivery networks use custom allocators for connection buffers and cache entries where allocation sizes vary but tend to cluster around powers of two (e.g., 4KB, 8KB, 16KB for HTTP buffers). By aligning allocation sizes to buddy-like size classes, these systems minimize fragmentation while maintaining the high allocation rates required to handle thousands of concurrent connections. Similarly, in-memory databases like Redis and Memcached, which must manage millions of small objects with varying lifetimes, use slab-based allocators that are conceptually layered on top of buddy system principles to balance speed and memory efficiency.

8. Comparison with Alternatives

Choosing a memory allocation strategy requires understanding the trade-offs between competing approaches. The buddy system occupies a middle ground between simple sequential allocators and more complex segregated storage schemes, offering a compelling balance of speed, fragmentation resistance, and implementation simplicity. To make an informed decision, it is essential to compare it against the most common alternatives: first-fit, best-fit, slab allocation, and segregated free lists.

First-fit and best-fit allocators maintain a single free list of variable-sized blocks and scan linearly to find a suitable block. First-fit returns the first block large enough to satisfy the request, while best-fit searches for the smallest sufficient block. Both suffer from external fragmentation that worsens over time and have O(n) worst-case allocation time where n is the number of free blocks. The buddy system's O(log n) guarantee and automatic coalescing give it a significant advantage in long-running systems, though first-fit can be faster for small heaps where linear scanning is cheap.

Slab allocation, pioneered by Sun Microsystems for the Solaris kernel and later adopted by Linux, is optimized for allocating many objects of the same size — such as process control blocks, file descriptors, or network packet headers. A slab allocator pre-allocates contiguous memory regions (slabs) and carves them into fixed-size objects, eliminating fragmentation entirely for that size class. Slab allocators are typically built on top of a buddy system that provides the underlying large pages. Segregated free lists maintain separate free lists for different size classes without the buddy constraint, offering more flexible sizing at the cost of more complex coalescing logic.

The choice ultimately depends on workload characteristics. If allocation sizes are highly variable and unpredictable, the buddy system's power-of-two rounding may waste significant memory, and a segregated list with finer size granularity may be preferable. If allocations are predominantly of a few fixed sizes — as in kernel object caches — slab allocation is superior. For general-purpose kernel memory management where both small and large allocations coexist and long-term fragmentation resistance is paramount, the buddy system remains the gold standard, often complemented by a slab layer on top for small object efficiency. This layered architecture — buddy system for page-level management, slab allocator for object-level management — is exactly what the Linux kernel employs, demonstrating how these approaches complement rather than compete with each other.

9. Common Mistakes and Best Practices

Implementing and using the buddy system correctly requires attention to several subtle pitfalls that can lead to memory corruption, leaks, or performance degradation. One of the most common mistakes is incorrect buddy address calculation, particularly when the managed memory region does not start at address zero or when block headers are not accounted for in alignment. The XOR formula buddy = addr XOR 2^order assumes that the base address is zero and that all blocks are properly aligned. If the allocator manages memory starting at a non-zero base, the calculation must be adjusted to buddy = base + ((addr - base) XOR 2^order). Failing to do so results in coalescing the wrong blocks and corrupting the free lists.

Double-free and invalid-free errors are particularly dangerous in buddy systems because they can silently corrupt the allocator's internal state. Freeing the same block twice will cause the allocator to treat an already-free block as newly freed, potentially merging it with its buddy and creating overlapping free blocks that lead to the same memory being allocated to two different requesters. Similarly, freeing an address that was never allocated or freeing with the wrong size can desynchronize the free lists. Production allocators defend against this by storing magic numbers or checksums in block headers, maintaining allocation bitmaps, and adding assertions that validate free list invariants in debug builds. Always validate that the address being freed was previously allocated and has not already been freed.

Another frequent pitfall is choosing an inappropriate minimum block size. Setting the minimum too small (e.g., 8 bytes when the typical allocation is 1KB) creates an excessive number of orders, increasing the depth of splitting and coalescing and bloating metadata. Setting it too large (e.g., 1KB when many allocations are 16 bytes) wastes enormous amounts of memory to internal fragmentation. The minimum block size should be chosen based on the distribution of expected allocation sizes and the page size of the underlying system. A good rule of thumb is to set the minimum to the most common small allocation size or to the hardware page size, whichever is larger. Profiling allocation patterns before tuning this parameter is essential.

Best Practices for Robust Implementation

To build a production-quality buddy allocator, follow several established best practices. First, always maintain and validate invariants: after every allocation and deallocation, the sum of free memory plus allocated memory should equal total memory, no two free blocks should be buddies (otherwise they should have been coalesced), and all blocks should be properly aligned. Implement a debug mode that performs these checks after every operation — the overhead is acceptable during testing and catches bugs early. Second, use iterative rather than recursive splitting and coalescing to avoid stack overflow when the number of orders is large. Third, consider adding per-CPU or per-thread caches in front of the global buddy system to reduce lock contention in multi-threaded environments; the global buddy system should be protected by appropriate synchronization, but the fast path should avoid locking entirely.

Finally, instrument your allocator with comprehensive statistics: track allocation count, free count, fragmentation ratio, split count, coalesce count, and allocation latency histograms. These metrics are invaluable for diagnosing performance issues and tuning the allocator for specific workloads. When integrating the buddy system into a larger system, clearly document the alignment guarantees, maximum allocation size, and thread-safety properties so that callers can use it correctly. Remember that the buddy system is often not used in isolation — it is typically the bottom layer of a memory management hierarchy, and its interface should be designed to efficiently serve the layer above it, whether that is a slab allocator, a heap manager, or a virtual memory subsystem.

10. Interview Questions

Buddy system memory allocation is a favorite topic in systems design and operating system interviews at top technology companies. Interviewers use it to assess understanding of memory management fundamentals, algorithmic thinking, and the ability to reason about trade-offs. Below are common interview questions with guidance on how to approach them effectively.

Question 1: How do you find the buddy of a block in O(1) time? Explain the XOR trick.

This question tests whether you understand the mathematical foundation of the buddy system. The answer is that for a block of order k (size 2^k) at address A, its buddy is at address A XOR 2^k. Explain why this works: because buddy blocks are always aligned to 2^(k+1) boundaries, they differ only in the k-th bit of their address. For example, with order 3 (block size 8), blocks at addresses 0 (binary 0000) and 8 (binary 1000) are buddies — they differ only in bit 3. The XOR operation flips exactly that bit, yielding the buddy's address. Mention the prerequisite that the base address must be zero (or the calculation must be base-relative) and that blocks must be properly aligned for this to hold. A strong answer also discusses what happens if alignment is violated and how to handle non-zero base addresses.

Question 2: What is the worst-case internal fragmentation of the buddy system, and how would you reduce it?

The worst-case internal fragmentation is just under 50% — a request for 2^k + 1 bytes requires a block of size 2^(k+1), wasting nearly half the block. On average, internal fragmentation is about 25-30% for uniformly distributed requests. To reduce it, discuss several strategies: using a weighted or Fibonacci buddy system that provides more size granularity, implementing a double buddy system with interleaved size classes, adding a slab allocator layer on top that subdivides buddy blocks into smaller fixed-size objects for common allocation sizes, or using a hybrid approach where small allocations are handled by a separate segregated list while large allocations use the buddy system. Quantify the trade-off: finer granularity reduces internal fragmentation but increases the number of free lists and may slow down buddy calculation.

Question 3: Walk through what happens when you allocate 70KB and then free it in a buddy system with 1MB total memory and 32KB minimum block size.

This is a hands-on simulation question that tests your ability to trace the algorithm step by step. Start by computing the required order: 70KB needs order 7 (128KB, since 64KB is too small). With 1MB = 1024KB = 2^10 and minimum 32KB = 2^5, orders range from 5 to 10. Initially, one free block at order 10 (address 0). To allocate 128KB, split order 10 → two order 9 blocks (0 and 512KB), split order 9 block at 0 → two order 8 blocks (0 and 256KB), split order 8 block at 0 → two order 7 blocks (0 and 128KB). Allocate block at 0, leaving free lists: order 7: {128KB}, order 8: {256KB}, order 9: {512KB}. When freeing the 128KB block at address 0, compute its buddy at 0 XOR 128KB = 128KB. Check if buddy at 128KB is free — yes, it is in order 7 free list. Merge them into a 256KB block at address 0 (order 8). Now check if this new block's buddy at 0 XOR 256KB = 256KB is free — yes, order 8 has {256KB} free. Merge into 512KB at address 0 (order 9). Check buddy at 0 XOR 512KB = 512KB — yes, order 9 has {512KB} free. Merge into 1MB at address 0 (order 10). The entire memory is coalesced back to the initial state.

Question 4: Compare the buddy system with a slab allocator. When would you use each?

A strong answer explains that the buddy system is a general-purpose allocator for variable-sized, power-of-two blocks with O(log n) allocation and automatic coalescing, while the slab allocator is optimized for many allocations of the same fixed size with O(1) allocation and zero internal fragmentation for that size. Use the buddy system when allocation sizes vary widely and unpredictably, when you need to allocate large contiguous regions (like page frames for processes), and when long-term fragmentation resistance is critical. Use the slab allocator when you repeatedly allocate and free objects of identical size (like task_struct, inode, or sk_buff in the kernel), when per-object construction/destruction overhead matters (slabs cache initialized objects), and when you want to minimize fragmentation for hot allocation paths. In practice, the two are complementary — Linux uses the buddy system to allocate pages and then uses slab caches (SLAB/SLUB) built on top of those pages to efficiently manage kernel objects. This layered design gives the best of both worlds.

Question 5: How does the buddy system handle external fragmentation compared to first-fit? Can the buddy system still suffer from external fragmentation?

Explain that the buddy system dramatically reduces external fragmentation compared to first-fit because its coalescing is fast, deterministic, and always merges buddies when possible, whereas first-fit requires scanning and boundary tag checks that may miss coalescing opportunities or be too slow to perform eagerly. However, the buddy system can still suffer from external fragmentation in a specific form: two adjacent free blocks that are not buddies cannot be coalesced. For example, if blocks [0–64KB] and [64–128KB] are free and are buddies (same parent 128KB block), they will coalesce. But if blocks [64–128KB] and [128–192KB] are free, they are not buddies (different parents) and remain separate, even though together they form a contiguous 128KB region. This means a request for 128KB could fail even though 128KB of contiguous free memory exists — it is just not buddy-aligned. Discuss mitigation strategies like memory compaction (migrating allocated blocks to create buddy-aligned free regions) and the use of larger minimum block sizes to reduce the probability of this checkerboard fragmentation pattern.