Compaction And Buddy System - Learning Module

Loading content...

0/227

Buddy System Algorithm

An Elegant Solution to Memory Management

The buddy system represents one of the most elegant algorithms in operating systems—a memory allocation technique that transforms the complex problem of managing variable-sized memory blocks into a simple, efficient, and mathematically beautiful system.

Invented by Harry Markowitz (yes, the Nobel Prize-winning economist) in 1963 and refined by Kenneth Knowlton, the buddy system achieves what seems paradoxical: it makes both allocation AND deallocation fast by imposing clever constraints on how memory is divided and merged. The key insight is that limiting flexibility creates efficiency—by restricting block sizes to powers of two, the algorithm enables constant-time partner (buddy) identification and trivial coalescing of adjacent free blocks.

What You Will Learn

By the end of this page, you will understand the buddy system algorithm in complete detail—its mathematical foundation, the splitting and coalescing processes, the data structures that enable O(1) operations, and the trade-offs that make it suitable for specific use cases while limiting its applicability in others.

The Core Concept

The buddy system is built on a fundamental observation: if memory blocks are constrained to powers of two in size and alignment, then every block has exactly one "buddy"—a block of the same size at a predictable, computable address.

The Buddy Relationship:

Two blocks are buddies if and only if:

They are the same size (2^k for some k)
They are adjacent in memory
They were created by splitting a single parent block of size 2^(k+1)
The address of one can be computed from the address of the other by flipping a single bit

The Buddy Address Formula:

For a block of size 2^k at address A, its buddy's address is:

buddy_address = A XOR 2^k

This single formula is the heart of the buddy system's efficiency. No searching, no linked list traversal—just a bitwise XOR to find any block's partner.

The XOR Magic

The XOR operation flips bit k in the address. If the original block starts at an even multiple of 2^(k+1), XOR adds 2^k to get the right buddy. If it starts at an odd multiple, XOR subtracts 2^k to get the left buddy. This works because buddies always straddle a 2^(k+1) boundary.

Visual Intuition:

Consider a 1024-byte memory region managed by the buddy system:

Initial State: One block of 1024 bytes
[                    1024                    ]
 Address 0                               Address 1023

After splitting for a 300-byte request (rounds up to 512):
[         512         ][         512         ]
 Address 0             Address 512          Address 1023
 Left buddy            Right buddy

The two 512-byte blocks are buddies:
  - Same size: 512 = 2^9
  - Adjacent: 0-511 and 512-1023
  - Buddy formula: 0 XOR 512 = 512 ✓
                   512 XOR 512 = 0 ✓

The Splitting Process:

When an allocation request arrives, the buddy system finds the smallest power-of-two block that can satisfy it:

Round up the request to the next power of two
Search for a free block of that size
If found, allocate and return
If not found, split a larger free block:
- Find a free block of size 2^(k+1)
- Divide it into two buddies of size 2^k
- Add one buddy to the free list of size 2^k
- Continue with the other 2^k block
Repeat until a block of the requested size is available

The Coalescing Process:

When a block is freed, the buddy system attempts to merge it with its buddy:

Compute the buddy's address using XOR
Check if the buddy is free and of the same size
If yes, merge both buddies into a 2^(k+1) block
Repeat with the merged block (it has its own buddy at the next level)
Continue until the buddy is not free or the maximum block size is reached

Converting Mermaid diagram...

Data Structures

The buddy system requires specific data structures to track free blocks at each size level efficiently. The most common implementation uses an array of free lists—one list per power-of-two size.

The Free List Array:

free_lists[0]  → blocks of size 2^MIN_ORDER (e.g., 16 bytes)
free_lists[1]  → blocks of size 2^(MIN_ORDER+1) (e.g., 32 bytes)
free_lists[2]  → blocks of size 2^(MIN_ORDER+2) (e.g., 64 bytes)
...
free_lists[k]  → blocks of size 2^(MIN_ORDER+k)
...
free_lists[MAX_ORDER - MIN_ORDER] → largest block (e.g., full memory)

Each free list is typically implemented as a doubly-linked list for O(1) insertion and removal.

buddy_structures.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
// Buddy system data structures
 
#include <stdint.h>
#include <stdbool.h>
 
#define MIN_ORDER 4      // Minimum block: 2^4 = 16 bytes
#define MAX_ORDER 20     // Maximum block: 2^20 = 1 MB
#define NUM_ORDERS (MAX_ORDER - MIN_ORDER + 1)
 
// Free block header (embedded at start of free blocks)
typedef struct FreeBlock {
    struct FreeBlock* next;
    struct FreeBlock* prev;
    uint8_t order;        // log2(size) of this block
    bool is_free;         // For debugging/verification
} FreeBlock;
 
// The free list array
FreeBlock* free_lists[NUM_ORDERS];
 
// Bitmap to track allocated/free status (optional, for fast buddy checks)
// One bit per minimum-sized block
#define BITMAP_SIZE ((1 << MAX_ORDER) / (1 << MIN_ORDER) / 8)
uint8_t allocation_bitmap[BITMAP_SIZE];
 
// Initialization
void buddy_init(void* memory_start, size_t total_size) {
    // Clear all free lists
    for (int i = 0; i < NUM_ORDERS; i++) {
        free_lists[i] = NULL;
    }
    
    // Compute the order of the entire memory region
    int total_order = log2_floor(total_size);
    if (total_order > MAX_ORDER) total_order = MAX_ORDER;
    if (total_order < MIN_ORDER) return;  // Memory too small
    
    // Initialize the entire memory as one free block
    FreeBlock* initial = (FreeBlock*)memory_start;
    initial->order = total_order;
    initial->is_free = true;
    initial->next = NULL;
    initial->prev = NULL;
    
    // Add to the appropriate free list
    int list_index = total_order - MIN_ORDER;
    free_lists[list_index] = initial;
    
    // Clear allocation bitmap
    memset(allocation_bitmap, 0, BITMAP_SIZE);
}

The Allocation Bitmap:

An optional but useful optimization is maintaining a bitmap with one bit per minimum-sized block:

Bit = 0: Block is free
Bit = 1: Block is allocated (or part of an allocated region)

Bitmap Benefits:

O(1) determination of whether a buddy is free
Range queries: "Are blocks X through Y all free?"
Memory debugging: detect use-after-free, double-free

Bitmap Costs:

Memory overhead: 1 bit per minimum block
For MIN_ORDER=4 (16B blocks) and 1MB total: 1MB/16B/8 = 8KB bitmap
Must be kept synchronized with free lists

Free Block Header Placement:

Free blocks store their metadata within the block itself. This is possible because:

Free blocks aren't being used for data
When allocated, the header is overwritten by user data
When freed, the header is reconstructed

This eliminates per-block metadata overhead for allocated blocks—metadata only exists for free blocks.

Alternative: Tree-Based Structure

Some implementations represent the buddy structure as a complete binary tree:

                   [1024] (root)
                   /    \
              [512]      [512]
              /   \      /   \
          [256] [256] [256] [256]
          / \   / \   / \   / \
       [128]....

Tree Representation:

Each node represents a potential block
Leaf nodes are minimum-sized blocks
Internal nodes represent merged blocks
Node state: FULL (has allocation), SPLIT (children in use), FREE

Tree Advantages:

More intuitive visualization
Easy to track partial allocations
Parent-child relationships explicit

Tree Disadvantages:

More memory overhead
Allocation may require tree traversal
Less cache-friendly than array of free lists

Linux Kernel Implementation

The Linux kernel uses a hybrid approach: an array of free lists plus a buddy bitmap. The bitmap has one bit per pair of buddies at each order level, indicating whether they differ in allocation status (one free, one allocated). This enables extremely fast buddy lookups during freeing.

Allocation Algorithm

The allocation algorithm in the buddy system is straightforward once the data structures are understood. The key insight is that we search from the desired size upward, splitting larger blocks as needed.

Algorithm: buddy_alloc(requested_size)

1. Compute required order: order = ceil(log2(requested_size))
   - Clamp to minimum: order = max(order, MIN_ORDER)
   - Reject if too large: if order > MAX_ORDER, return NULL

2. Search for a free block:
   - For k = order to MAX_ORDER:
       - If free_lists[k - MIN_ORDER] is not empty:
           - Remove a block from this list
           - Proceed to step 3 with this block
   - If no block found at any level: return NULL (out of memory)

3. Split if necessary:
   - While block.order > order:
       - Split block into two buddies of order (block.order - 1)
       - Add one buddy to free_lists[block.order - 1 - MIN_ORDER]
       - Continue with the other buddy

4. Mark as allocated and return the block

buddy_alloc.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
// Buddy system allocation implementation
 
void* buddy_alloc(size_t requested_size) {
    // Step 1: Compute required order
    if (requested_size == 0) return NULL;
    
    int order = ceil_log2(requested_size);
    if (order < MIN_ORDER) order = MIN_ORDER;
    if (order > MAX_ORDER) return NULL;
    
    // Step 2: Search for a free block starting at required order
    int current_order;
    FreeBlock* block = NULL;
    
    for (current_order = order; current_order <= MAX_ORDER; current_order++) {
        int list_idx = current_order - MIN_ORDER;
        if (free_lists[list_idx] != NULL) {
            block = free_lists[list_idx];
            // Remove from free list
            remove_from_free_list(block, list_idx);
            break;
        }
    }
    
    if (block == NULL) {
        return NULL;  // Out of memory
    }
    
    // Step 3: Split until we reach the desired order
    while (block->order > order) {
        int new_order = block->order - 1;
        
        // Compute buddy address (second half of current block)
        uintptr_t block_addr = (uintptr_t)block;
        uintptr_t buddy_addr = block_addr + (1UL << new_order);
        FreeBlock* buddy = (FreeBlock*)buddy_addr;
        
        // Initialize buddy as free block
        buddy->order = new_order;
        buddy->is_free = true;
        
        // Add buddy to free list
        add_to_free_list(buddy, new_order - MIN_ORDER);
        
        // Update current block
        block->order = new_order;
    }
    
    // Step 4: Mark as allocated
    block->is_free = false;
    mark_bitmap_allocated((uintptr_t)block, order);
    
    return (void*)block;
}
 
// Helper: Remove block from its free list
void remove_from_free_list(FreeBlock* block, int list_idx) {
    if (block->prev) {
        block->prev->next = block->next;
    } else {
        free_lists[list_idx] = block->next;
    }
    if (block->next) {
        block->next->prev = block->prev;
    }
}
 
// Helper: Add block to front of free list
void add_to_free_list(FreeBlock* block, int list_idx) {
    block->next = free_lists[list_idx];
    block->prev = NULL;
    if (free_lists[list_idx]) {
        free_lists[list_idx]->prev = block;
    }
    free_lists[list_idx] = block;
}

Time Complexity Analysis:

Step 1 (Order Calculation): O(1)

Simple arithmetic and bit operations

Step 2 (Free Block Search): O(log(MAX_SIZE/MIN_SIZE)) = O(MAX_ORDER - MIN_ORDER)

In the worst case, we check each order level once
For typical parameters (MAX_ORDER=20, MIN_ORDER=4), this is O(16)

Step 3 (Splitting): O(log(current_order / requested_order))

At most (MAX_ORDER - MIN_ORDER) splits
Each split is O(1): compute buddy address, initialize, add to list

Step 4 (Marking): O(1)

Update bitmap (if present)

Total: O(log(memory_size / min_block_size))

For practical systems, this is effectively O(1) since the number of orders is typically 15-25, a small constant.

Allocation Example: Request 300 bytes (1KB total memory)
Step	Action	Free Lists State
1	Compute order: ceil(log2(300)) = 9 (512 bytes)
2	Check free_lists[9-4=5]: empty	lists[6] has one 1024B block
2	Check free_lists[10-4=6]: has 1024B block	Remove from lists[6]
3	Split 1024→512+512, add one to lists[5]	lists[5] has one 512B block
4	Return the other 512B block	One 512B block allocated

Deallocation and Coalescing

The real elegance of the buddy system shines during deallocation. The coalescing process—merging adjacent free blocks—is trivial because the buddy's address is always computable and buddies can only be merged with each other (not with arbitrary adjacent blocks).

Algorithm: buddy_free(pointer, size)

1. Compute the order of the block being freed
   - order = ceil(log2(size))
   - Or retrieve from allocation metadata

2. Coalescing loop:
   - While order < MAX_ORDER:
       - Compute buddy address: buddy = pointer XOR (1 << order)
       - If buddy is free AND buddy has the same order:
           - Remove buddy from free_lists[order - MIN_ORDER]
           - pointer = min(pointer, buddy)  // New merged block starts at lower address
           - order = order + 1
       - Else:
           - Break (cannot coalesce further)

3. Add the resulting block to free_lists[order - MIN_ORDER]

buddy_free.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
// Buddy system deallocation with coalescing
 
void buddy_free(void* ptr, size_t size) {
    if (ptr == NULL) return;
    
    // Step 1: Compute block order
    int order = ceil_log2(size);
    if (order < MIN_ORDER) order = MIN_ORDER;
    
    uintptr_t block_addr = (uintptr_t)ptr;
    
    // Step 2: Coalescing loop
    while (order < MAX_ORDER) {
        // Compute buddy address using XOR
        uintptr_t buddy_addr = block_addr ^ (1UL << order);
        
        // Check if buddy is free and same order
        if (!is_buddy_free(buddy_addr, order)) {
            break;  // Buddy is allocated or different size
        }
        
        // Remove buddy from its free list
        FreeBlock* buddy = (FreeBlock*)buddy_addr;
        remove_from_free_list(buddy, order - MIN_ORDER);
        
        // Merge: new block starts at lower address
        if (buddy_addr < block_addr) {
            block_addr = buddy_addr;
        }
        
        // Increase order (merged block is twice as large)
        order++;
    }
    
    // Step 3: Add merged block to appropriate free list
    FreeBlock* block = (FreeBlock*)block_addr;
    block->order = order;
    block->is_free = true;
    add_to_free_list(block, order - MIN_ORDER);
    
    // Update bitmap
    mark_bitmap_free(block_addr, order);
}
 
// Helper: Check if buddy is free and same order
bool is_buddy_free(uintptr_t buddy_addr, int order) {
    // Method 1: Check bitmap
    if (!is_address_free_in_bitmap(buddy_addr, order)) {
        return false;
    }
    
    // Method 2: Verify order matches (optional, for robustness)
    FreeBlock* buddy = (FreeBlock*)buddy_addr;
    return buddy->is_free && buddy->order == order;
}

Why Buddies Must Match:

A subtle but critical point: coalescing is only possible when both conditions are met:

The buddy is free
The buddy is the same size

Why the size constraint? Consider this scenario:

Initial: [   1024 bytes free   ]

Allocate 512: [512 allocated][512 free]
Allocate 256: [512 allocated][256 free][256 allocated]

Memory state:
  [A:512][F:256][B:256]

Now free A (512 bytes):
  [F:512][F:256][B:256]

A's buddy at order 9 is the original second half (addr=512).
But that memory now contains two smaller blocks (one free, one allocated).

The buddy at address 512 is NOT free as a 512-byte block.
It's been split into 256-byte blocks.

We cannot coalesce A with "half a buddy."

This constraint is what makes the buddy system work: blocks can only merge with their exact buddy, not with arbitrary adjacent memory.

Coalescing Example:

Starting state (1024 bytes total):
[A:256][F:256][B:256][C:256]
  0     256    512    768

Free block B (at address 512):

1. order = 8 (256 bytes = 2^8)
2. Coalescing loop:
   - buddy_addr = 512 XOR 256 = 768
   - Check: Is block at 768 free? NO (it's C, allocated)
   - Cannot coalesce, break
3. Add 256-byte block at 512 to free_lists[4]

Result: [A:256][F:256][F:256][C:256]

Now free block A (at address 0):

1. order = 8
2. Coalescing loop:
   - buddy_addr = 0 XOR 256 = 256
   - Check: Is block at 256 free? YES, and same order
   - Remove block at 256 from free_lists[4]
   - block_addr = min(0, 256) = 0
   - order = 9 (now 512 bytes)
   
   - buddy_addr = 0 XOR 512 = 512
   - Check: Is block at 512 free? YES, and same order (256 bytes)
   - Wait! Order doesn't match (we're at order 9, buddy is order 8)
   - Cannot coalesce, break
3. Add 512-byte block at 0 to free_lists[5]

Result: [F:512][F:256][C:256]

The Beauty of Coalescing

Notice that coalescing requires no searching! The buddy address is computed instantly via XOR, and checking if it's free is an O(1) bitmap lookup. This is fundamentally different from other allocators that must scan memory to find mergeable blocks. The buddy system's constraints enable its speed.

Implementation Variations

The basic buddy system described above has several practical variations that address specific use cases or improve performance.

Variation 1: Binary Buddy vs. Fibonacci Buddy

The standard binary buddy uses powers of two. The Fibonacci buddy system uses Fibonacci numbers instead:

Binary sizes:   1, 2, 4, 8, 16, 32, 64, 128, 256...
Fibonacci sizes: 1, 2, 3, 5, 8, 13, 21, 34, 55...

Fibonacci Advantages:

Finer granularity of sizes
Less internal fragmentation on average
Block of size F(n) splits into F(n-1) and F(n-2), both usable

Fibonacci Disadvantages:

Buddy address computation is not a simple XOR
More complex bookkeeping
Less commonly implemented

Variation 2: Weighted Buddy System

Allows splits other than 50-50. For example, a block of size S might split into:

S/4 and 3S/4
S/3 and 2S/3

Weighted Advantages:

Better fit for workloads with biased size distributions
Reduces fragmentation for specific patterns

Weighted Disadvantages:

Buddy identification becomes more complex
Multiple possible buddies per block
Less elegant than binary buddy

Variation 3: Lazy Coalescing

Instead of coalescing immediately on free, defer coalescing until needed:

void lazy_free(void* ptr, size_t size) {
    // Simply add to free list without coalescing
    add_to_free_list(block, order);
}

void* lazy_alloc(size_t size) {
    // If no block found, trigger coalescing pass
    block = try_alloc(size);
    if (block == NULL) {
        coalesce_all();
        block = try_alloc(size);
    }
    return block;
}

Lazy Coalescing Advantages:

Faster frees (no coalescing work)
Batches coalescing work for efficiency
May skip unnecessary coalescing if memory is soon reallocated

Lazy Coalescing Disadvantages:

Allocation may occasionally be slow (when coalescing triggered)
Memory may be more fragmented at any given time

lazy_buddy.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
// Lazy coalescing buddy system variation
 
typedef struct {
    FreeBlock* free_lists[NUM_ORDERS];
    bool needs_coalesce[NUM_ORDERS];  // Track which orders have pending merges
    int uncoalesced_count;
} LazyBuddyAllocator;
 
void lazy_buddy_free(LazyBuddyAllocator* alloc, void* ptr, size_t size) {
    int order = ceil_log2(size);
    FreeBlock* block = (FreeBlock*)ptr;
    
    // Quick check: can we coalesce immediately at low cost?
    uintptr_t buddy_addr = (uintptr_t)ptr ^ (1UL << order);
    if (is_buddy_free_quick_check(buddy_addr, order)) {
        // Buddy is obviously free, coalesce now
        immediate_coalesce(alloc, ptr, order);
    } else {
        // Defer coalescing
        add_to_free_list(&alloc->free_lists[order - MIN_ORDER], block);
        alloc->needs_coalesce[order - MIN_ORDER] = true;
        alloc->uncoalesced_count++;
    }
    
    // Trigger full coalesce if too many pending
    if (alloc->uncoalesced_count > COALESCE_THRESHOLD) {
        full_coalesce_pass(alloc);
    }
}
 
void full_coalesce_pass(LazyBuddyAllocator* alloc) {
    // Coalesce from smallest to largest order
    for (int order = MIN_ORDER; order < MAX_ORDER; order++) {
        int list_idx = order - MIN_ORDER;
        if (!alloc->needs_coalesce[list_idx]) continue;
        
        FreeBlock* block = alloc->free_lists[list_idx];
        while (block != NULL) {
            FreeBlock* next = block->next;
            try_coalesce(alloc, block, order);
            block = next;
        }
        alloc->needs_coalesce[list_idx] = false;
    }
    alloc->uncoalesced_count = 0;
}

Choosing a Variation

•Binary Buddy — Best for general-purpose allocation with predictable performance. Use when simplicity and consistency matter.
•Fibonacci Buddy — Consider when allocation sizes cluster around non-power-of-two values and internal fragmentation is a concern.
•Weighted Buddy — Use when workload analysis shows specific size ratios are common (e.g., many 3:1 size relationships).
•Lazy Coalescing — Prefer for workloads with frequent alloc/free cycles at the same size (common in object pools, network buffers).

Real-World Usage

The buddy system is not just a theoretical construct—it's used in production systems worldwide, particularly in operating system kernels.

Linux Kernel Zone Allocator:

Linux uses a buddy system as the foundation of its physical page allocator:

Linux Buddy Allocator:
- MIN_ORDER = 0 (single page, typically 4 KB)
- MAX_ORDER = 10 (2^10 = 1024 pages = 4 MB typically)
- 11 free lists per memory zone
- Allocates in units of pages (not bytes)
- Used by kmalloc, vmalloc, page cache, etc.

Why Linux Uses Buddy:

O(1) allocation and deallocation (important for high-frequency kernel operations)
Natural fit for page-based memory management
Easy to track which pages are free
Efficient large contiguous allocations for DMA

Buddy + Slab = Complete Solution

Linux combines the buddy allocator with slab allocators. Buddy handles large allocations and provides pages to slab allocators. Slab allocators subdivide pages for small, frequently-allocated objects. This two-tier approach gives both the efficiency of buddy for large allocations and the low fragmentation of slabs for small objects.

FreeBSD UMA (Universal Memory Allocator):

Similar to Linux, FreeBSD uses a buddy-like system for page allocation:

FreeBSD Physical Page Management:
- Page queues organized by "order" (contiguity)
- Buddy-style coalescing on page free
- Integration with VM subsystem

jemalloc (User-Space Allocator):

The jemalloc allocator (used by Firefox, FreeBSD libc, and many others) uses buddy-like techniques internally:

jemalloc's Pages:
- Buddy-based management of large allocations
- Runs (contiguous small objects) managed separately  
- Spans multiple size classes efficiently

Windows Kernel Pool Allocator:

Windows NT kernel uses a variant of buddy allocation for its pool allocator:

Windows Pool:
- NonPaged Pool and Paged Pool
- Buddy-style granularity for large allocations
- Lookaside lists for common sizes

Buddy System Usage in Production Systems
System	Component	Min Unit	Max Unit	Notes
Linux Kernel	Page Allocator	4 KB page	4 MB (1024 pages)	Foundation of memory management
FreeBSD	VM Subsystem	4 KB page	Varies	Integrated with VM
jemalloc	Large Allocs	Page size	Chunk size	Used by Firefox, Rust
Windows NT	Pool Allocator	Variable	Variable	Kernel memory pools
Embedded RTOS	Memory Manager	Block size	Total RAM	Real-time guarantees

When Buddy System Excels:

Kernel Page Allocation: Natural fit for page-granularity memory
DMA Buffers: Need for large contiguous physical memory
Real-Time Systems: Predictable O(log n) worst-case performance
Embedded Systems: Simple implementation, low overhead
Network Drivers: Fast allocation of packet buffers

When to Avoid Buddy System:

Fine-grained allocation: Internal fragmentation too high for small objects
Variable-size strings/arrays: Poor fit for non-power-of-two natural sizes
Memory-constrained systems: If 50% internal fragmentation is unacceptable
Sequential locality needed: Buddy doesn't consider cache/NUMA effects

Summary: Buddy System Algorithm

The buddy system is an elegant algorithm that trades some internal fragmentation for dramatically simplified memory management. Its power-of-two constraints enable O(1) buddy identification and effortless coalescing.

Key Takeaways

•The buddy relationship — Every block has exactly one buddy at a computable address (XOR with block size). This enables instant partner identification.
•Splitting and coalescing — Allocation splits larger blocks; deallocation merges buddies. Both operations are O(log n) and predictable.
•Data structures — An array of free lists (one per size) plus optional bitmaps enables efficient tracking with minimal overhead.
•Variations exist — Fibonacci buddy, weighted buddy, and lazy coalescing address specific use cases and performance requirements.
•Production usage — The Linux kernel, FreeBSD, jemalloc, and Windows all use buddy-based allocation for physical memory management.
•Trade-off clarity — Buddy trades internal fragmentation (up to 50%) for guaranteed O(1) coalescing and simple implementation.

What's Next:

The next page examines Power-of-Two Allocation—the heart of the buddy system's block sizing strategy. We'll explore why powers of two are chosen, how to calculate rounded sizes efficiently, and the mathematical properties that make power-of-two arithmetic so amenable to fast hardware implementations.

Page Complete

You now understand the buddy system algorithm at a deep level—from its elegant mathematical foundation through practical implementation to real-world deployment in major operating systems. This algorithm exemplifies how clever constraints can transform complex problems into simple, efficient solutions.