Compaction And Buddy System - Learning Module

Loading content...

0/227

Buddy System Fragmentation

The Fragmentation Paradox

The buddy system is often praised for its efficient coalescing of free blocks—a property that combats external fragmentation. Yet the reality is more nuanced. While the buddy system eliminates certain classes of fragmentation problems, it introduces others. Understanding these fragmentation characteristics is essential for knowing when buddy allocation is appropriate and when alternatives should be considered.

This page provides a rigorous analysis of fragmentation in buddy systems: the internal fragmentation inherent in power-of-two sizing, the external fragmentation that can still occur despite coalescing, the mathematical bounds on memory utilization, and strategies for mitigating fragmentation issues in practice.

What You Will Learn

By the end of this page, you will understand the quantitative characteristics of buddy system fragmentation, including worst-case and average-case internal fragmentation, the conditions under which external fragmentation occurs, mathematical utilization bounds, and practical mitigation strategies.

Internal Fragmentation Analysis

Internal fragmentation occurs when allocated blocks are larger than the requested size. In the buddy system, this is a direct consequence of power-of-two sizing—every request is rounded up to the next power of two.

Formal Definition:

For a request of size R bytes allocated in a block of size B bytes:

Internal_Fragmentation = B - R
Fragmentation_Ratio = (B - R) / B = 1 - R/B

Where B = 2^⌈log₂(R)⌉ (the smallest power of two ≥ R)

Worst-Case Internal Fragmentation:

The worst case occurs when R is just slightly larger than a power of two:

R = 2^k + 1  →  B = 2^(k+1)

Internal_Fragmentation = 2^(k+1) - (2^k + 1)
                       = 2^k - 1

Fragmentation_Ratio = (2^k - 1) / 2^(k+1)
                    = (2^k - 1) / (2 × 2^k)
                    ≈ 0.5 - ε  (approaches 50%)

Worst-case approaches but never quite reaches 50% fragmentation.

Internal Fragmentation Examples
Request (R)	Allocated (B)	Wasted	Fragmentation %
1 byte	16 bytes (MIN)	15 bytes	93.75% (edge case)
17 bytes	32 bytes	15 bytes	46.88%
33 bytes	64 bytes	31 bytes	48.44%
65 bytes	128 bytes	63 bytes	49.22%
129 bytes	256 bytes	127 bytes	49.61%
257 bytes	512 bytes	255 bytes	49.80%
513 bytes	1024 bytes	511 bytes	49.90%

Best-Case Internal Fragmentation:

The best case occurs when R is exactly a power of two:

R = 2^k  →  B = 2^k

Internal_Fragmentation = 2^k - 2^k = 0
Fragmentation_Ratio = 0%

Average-Case Analysis:

Assuming requests are uniformly distributed across size ranges, what's the expected fragmentation?

For requests uniformly distributed in range [2^k + 1, 2^(k+1)]:

All requests in this range are allocated blocks of size 2^(k+1).

E[Fragmentation] = E[2^(k+1) - R]
                 = 2^(k+1) - E[R]
                 = 2^(k+1) - (2^k + 1 + 2^(k+1))/2
                 = 2^(k+1) - (3 × 2^k + 1)/2
                 = 2^(k+1) - 3 × 2^(k-1) - 0.5
                 = 2^k - 0.5
                 ≈ 2^(k-1)  (approximately half the lower bound)

E[Fragmentation_Ratio] ≈ (2^(k-1)) / 2^(k+1)
                       = 1/4 = 25%

With uniform random requests, average internal fragmentation is approximately 25%.

The 25% Rule

For randomly distributed allocation sizes, the buddy system wastes approximately 25% of allocated memory to internal fragmentation. This is significantly better than the 50% worst case, but still substantial. For workloads with specific size patterns, actual fragmentation may be higher or lower.

Impact of Minimum Block Size:

The minimum block size significantly affects fragmentation for small allocations:

With MIN_ORDER = 4 (16 bytes):
  Request for 1 byte → 16 bytes → 93.75% fragmentation
  Request for 8 bytes → 16 bytes → 50% fragmentation
  Request for 15 bytes → 16 bytes → 6.25% fragmentation

With MIN_ORDER = 5 (32 bytes):
  Request for 1 byte → 32 bytes → 96.88% fragmentation
  Request for 17 bytes → 32 bytes → 46.88% fragmentation
  Request for 31 bytes → 32 bytes → 3.13% fragmentation

Key Insight: Larger minimum block sizes increase fragmentation for small allocations. If your workload has many small allocations (1-16 bytes), a larger MIN_ORDER is costly.

Cumulative Waste Calculation:

For a workload with n allocations of sizes R₁, R₂, ..., Rₙ:

Total_Requested = ΣRᵢ
Total_Allocated = Σ(2^⌈log₂(Rᵢ)⌉)
Total_Waste = Total_Allocated - Total_Requested
Overall_Fragmentation = Total_Waste / Total_Allocated

External Fragmentation in Buddy Systems

A common misconception is that buddy systems eliminate external fragmentation entirely. This is not true. While buddy systems Excel at coalescing free blocks, external fragmentation can still occur under specific conditions.

When External Fragmentation Occurs:

External fragmentation in a buddy system happens when free blocks cannot be coalesced because their buddies are allocated:

Scenario: 1024-byte memory, allocations at various sizes

Initial:    [           1024 bytes free           ]

Alloc A(128): [A:128][F:128][    F:256    ][  F:512  ]
              Split from 1024→512+512→256+256→128+128

Alloc B(256): [A:128][F:128][B:256][  F:512  ]

Alloc C(128): [A:128][C:128][B:256][  F:512  ]

Now free A:   [F:128][C:128][B:256][  F:512  ]

Can we allocate 256 bytes?
  - F:512 can satisfy it (will be split to 256+256)
  ✓ Yes!

Can we allocate 640 bytes (rounds to 1024)?
  - Need 1024 contiguous bytes
  - F:128 + F:512 = 640 bytes free, but not contiguous
  - F:128 buddy (at 128) is C, allocated → cannot coalesce
  - F:512 buddy (at 0) contains A's ex-location + C, partially allocated
  ✗ No! External fragmentation!

The Buddy Blocking Problem:

External fragmentation in buddy systems is caused by buddy blocking—a free block cannot coalesce to a larger size because its buddy (or its buddy's buddy, recursively) is allocated.

Visualization:

Memory divided into 8 minimum blocks (order-0):

  Block:  0   1   2   3   4   5   6   7
         [F] [A] [F] [F] [A] [F] [F] [F]
          L   L   R   R   L   L   R   R
              ↑       ↑       ↑       ↑
              │       │       │       │
         Buddy pairs at order-0

Coalescing analysis:
  - Block 0's buddy is Block 1 (allocated) → cannot coalesce
  - Blocks 2-3 can coalesce to order-1
  - Block 4's buddy is Block 5 (free) → can coalesce to order-1
  - Wait, Block 4 is allocated! Cannot coalesce.
  - Blocks 5-7: 5's buddy is 4 (allocated) → 5 cannot coalesce
  - Blocks 6-7 can coalesce to order-1

After maximum coalescing:
  Block:  0   1   2-3   4   5   6-7
         [F] [A] [FF]  [A] [F] [FF]
          ↑       ↑         ↑   ↑
          order-0 order-1   0   order-1

We have 5 free minimum blocks but maximum contiguous is order-1 (2 blocks).
External fragmentation exists!

External Fragmentation is Real

Despite efficient coalescing, buddy systems can still exhibit external fragmentation. The key limitation is that coalescing only works when BOTH buddies are free AND the same size. A single allocated block can prevent large coalesced regions from forming.

Pathological Allocation Patterns:

Certain allocation patterns maximize external fragmentation:

Pattern 1: Alternating Allocations

Allocate every other minimum-sized block:
[A][F][A][F][A][F][A][F]

No coalescing possible!
Free memory = 50%, but max allocatable = MIN_SIZE

Pattern 2: Persistent Small Allocations

Long-lived small allocations scattered throughout memory:

[F:256][A:64][F:64][F:128][A:128][F:256][A:64][F:64]...

Small persistent allocations prevent buddy coalescing,
making large allocations impossible despite free space.

Pattern 3: Size Mismatch

Allocate at order k, free, then request order k+2:

Initial: [1024 free]
Alloc A(128): [A:128][free:128][free:256][free:512]
Alloc B(256): [A:128][free:128][B:256][free:512]
Free A: [free:128][free:128][B:256][free:512]

128+128 can coalesce to 256
[free:256][B:256][free:512]

256+B? No, B is allocated.
512 buddy? Contains B, cannot coalesce.

Request for 1024 fails despite 768 bytes free.

Memory Utilization Bounds

What's the theoretical and practical limit on memory utilization in a buddy system? Several factors contribute to waste.

Utilization Decomposition:

Total_Memory = Useful_Data + Internal_Frag + External_Frag + Metadata

Utilization = Useful_Data / Total_Memory

Where:
  Useful_Data = Σ(actual request sizes)
  Internal_Frag = Σ(allocated block size - request size)
  External_Frag = unallocatable free memory
  Metadata = free list pointers, bitmaps, etc.

Theoretical Bounds:

Internal Fragmentation Bound:

Best case: 0% (all requests are exact powers of two)
Worst case: ~50% (all requests are 2^k + 1)
Average case: ~25% (uniform distribution)

External Fragmentation Bound:

Best case: 0% (no fragmentation, full coalescing)
Worst case: Approaches 100% in pathological patterns
Practical case: Depends heavily on allocation pattern

The Buddy System Utilization Theorem:

There exists a theoretical result on buddy system utilization:

Theorem: For a buddy system with orders from k_min to k_max,
and allocations following certain distributions, the expected
utilization U satisfies:

U ≥ 1 / (1 + α)

Where α depends on the allocation size distribution and
allocation/deallocation patterns.

For "well-behaved" workloads:
  α ≈ 0.5, giving U ≥ 67%

For adversarial workloads:
  α can be arbitrarily large, U → 0

Practical Utilization:

Real-world measurements from production systems show:

Workload Type	Typical Utilization	Limiting Factor
Kernel page allocation	85-95%	External frag with long-lived allocs
General malloc	65-80%	Internal frag + size variance
Object pools (same size)	90-99%	Minimal frag for exact sizes
Mixed sizes, random	60-75%	Combined internal + external
Adversarial patterns	10-50%	External frag dominates

utilization_analysis.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
// Buddy system utilization analysis
 
typedef struct {
    size_t total_memory;
    size_t allocated_bytes;       // Sum of block sizes
    size_t requested_bytes;       // Sum of request sizes
    size_t free_bytes;            // Total free (may be fragmented)
    size_t largest_free_block;    // For external frag detection
    size_t metadata_bytes;        // Overhead
} BuddyStats;
 
typedef struct {
    float internal_fragmentation;   // allocated - requested
    float external_fragmentation;   // free - largest_allocatable
    float utilization;              // requested / total
    float efficiency;               // requested / allocated
} FragmentationMetrics;
 
FragmentationMetrics analyze_buddy_system(BuddyStats* stats) {
    FragmentationMetrics m;
    
    // Internal fragmentation: wasted space within allocated blocks
    m.internal_fragmentation = 
        (float)(stats->allocated_bytes - stats->requested_bytes) /
        (float)stats->total_memory;
    
    // External fragmentation: free memory that can't satisfy
    // the largest possible request due to being non-contiguous
    size_t max_possible_request = stats->free_bytes;  // Theoretical
    size_t max_satisfiable = stats->largest_free_block;
    m.external_fragmentation = 
        (float)(max_possible_request - max_satisfiable) /
        (float)stats->total_memory;
    
    // Utilization: how much memory is actually used
    m.utilization = 
        (float)stats->requested_bytes / (float)stats->total_memory;
    
    // Efficiency: how well allocated memory matches requests
    m.efficiency = 
        (float)stats->requested_bytes / (float)stats->allocated_bytes;
    
    return m;
}
 
// Calculate largest allocatable block (max order with free block)
size_t find_largest_allocatable(FreeBlock** free_lists, int num_orders, int min_order) {
    for (int i = num_orders - 1; i >= 0; i--) {
        if (free_lists[i] != NULL) {
            return 1UL << (min_order + i);
        }
    }
    return 0;  // No free memory
}

Monitoring Matters

Production systems should monitor fragmentation metrics continuously. A gradual decline in largest_free_block while total_free remains stable indicates growing external fragmentation. This early warning enables proactive intervention before allocation failures occur.

Comparison with Other Allocators

How does buddy system fragmentation compare to other allocation strategies? Each approach makes different trade-offs.

First Fit / Best Fit / Worst Fit:

Variable-size allocation without power-of-two constraint:

Internal Fragmentation: Minimal (exact-fit possible)
External Fragmentation: Can be severe (scattered holes)
Coalescing: Complex (must scan for adjacent blocks)
Allocation Speed: O(n) for first/best fit

Slab Allocation:

Fixed-size object pools:

Internal Fragmentation: Zero for exact-size objects
External Fragmentation: Per-slab (unused objects within slab)
Coalescing: Not applicable (fixed-size slots)
Allocation Speed: O(1) for free list pop

Paging:

Fixed-size page allocation:

Internal Fragmentation: Up to (PAGE_SIZE - 1) per allocation
External Fragmentation: None (by design)
Coalescing: Not needed
Allocation Speed: O(1) with free page list

Fragmentation Comparison Across Allocators
Allocator	Internal Frag	External Frag	Coalescing	Best For
Buddy System	~25% average	Possible	O(log n), automatic	Kernel pages, contiguous needs
First Fit	Minimal	Moderate-High	O(n), complex	Simple implementations
Best Fit	Minimal	Many small holes	O(n), complex	Minimizing waste
Slab	None (exact)	Per-slab waste	N/A	Same-size objects
Paging	Per-page	None	N/A	General virtual memory
jemalloc	Low (size classes)	Managed	Varies	General purpose

Buddy vs. Slab Trade-off:

The Linux kernel combines both approaches:

Buddy handles:
  - Page-level allocation (4KB+)
  - Contiguous multi-page requests
  - DMA buffers
  
Slab handles:
  - Sub-page allocations (kmalloc)
  - Kernel object caches (struct inode, struct dentry, etc.)
  - Small frequently-allocated structures

This hybrid eliminates buddy's internal fragmentation for
small allocations while preserving buddy's efficient
coalescing for page-level memory.

When Buddy Fragmentation is Acceptable:

Allocation sizes cluster around powers of two — Page sizes, network buffers (MTU boundaries), disk blocks
Contiguous memory is required — DMA buffers, memory-mapped I/O
Fast coalescing is critical — High-churn allocation patterns
Predictable performance matters — Real-time systems (O(log n) bounded)

When Buddy Fragmentation is Problematic:

Many small, varied-size allocations — String handling, dynamic records
Memory is severely constrained — Embedded systems where 25% waste is unacceptable
Allocation sizes are typically 2^k + small — Consistently hitting worst case
Long-lived scattered allocations — External fragmentation accumulates

Mitigation Strategies

Understanding fragmentation leads naturally to strategies for mitigation. Several approaches can reduce fragmentation in buddy systems.

Strategy 1: Size Class Subdivision

Add intermediate size classes to reduce internal fragmentation:

Instead of: 64, 128, 256, 512
Use: 64, 80, 96, 128, 160, 192, 256, 320, 384, 512

For request of 65 bytes:
  Pure buddy: 128 bytes (49% waste)
  With intermediates: 80 bytes (19% waste)

Implementation: Manage each size class separately, with buddy-style coalescing only within aligned power-of-two boundaries.

Fragmentation Mitigation Approaches

•Segregated Lifetime Allocation — Reserve regions for short-lived vs. long-lived allocations. Long-lived allocations at one end prevent fragmentation of the short-lived region.
•Movable vs. Non-Movable Pages — Linux distinguishes between movable (can relocate), reclaimable (can discard), and unmovable pages. Grouping by type prevents unmovable pages from blocking compaction.
•Deferred Coalescing — Batch coalescing operations. For rapid alloc/free of same size, immediate coalescing is wasteful—the coalesced block is immediately re-split.
•Memory Pools — Pre-allocate pools for common sizes. Pool allocation has zero fragmentation; buddy handles only unusual sizes.
•Compaction — Periodically relocate allocations to consolidate free space. More feasible for movable userspace allocations than kernel memory.

anti_fragmentation.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
// Linux-style anti-fragmentation zone classification
 
typedef enum {
    MIGRATE_UNMOVABLE,    // Kernel structures, DMA buffers
    MIGRATE_MOVABLE,      // User pages (can be migrated/compacted)
    MIGRATE_RECLAIMABLE,  // Page cache, slab caches (can be freed)
    MIGRATE_PCPTYPE,      // Per-CPU pages
    MIGRATE_TYPES         // Number of types
} MigrateType;
 
// Separate free lists per migrate type
typedef struct {
    FreeBlock* free_lists[NUM_ORDERS];
} FreeArea;
 
FreeArea free_areas[MIGRATE_TYPES];
 
// Allocation specifies mobility
void* buddy_alloc_typed(size_t size, MigrateType type) {
    int order = size_to_order(size);
    
    // Try exact type first
    void* block = alloc_from_type(order, type);
    if (block) return block;
    
    // Fallback hierarchy depends on type
    if (type == MIGRATE_UNMOVABLE) {
        // Unmovable can steal from reclaimable (after reclaim)
        // but should NEVER steal from movable (would prevent compaction)
        block = try_reclaim_pages(order);
        if (block) return block;
        
        block = alloc_from_type(order, MIGRATE_RECLAIMABLE);
        if (block) return block;
    } else if (type == MIGRATE_MOVABLE) {
        // Movable can take from anywhere (we can move it later)
        for (int t = 0; t < MIGRATE_TYPES; t++) {
            block = alloc_from_type(order, t);
            if (block) return block;
        }
    }
    
    return NULL;  // Out of memory
}
 
// Policy: Return freed pages to their original type
void buddy_free_typed(void* block, size_t size, MigrateType type) {
    int order = size_to_order(size);
    add_to_typed_free_list(block, order, type);
    coalesce_typed(block, order, type);
}

Strategy 2: Memory Compaction for Buddy Systems

Unlike pure compaction discussed earlier, buddy-aware compaction considers order constraints:

Buddy Compaction Algorithm:

1. Identify fragmented regions:
   - Areas where small allocated blocks block coalescing
   
2. For each blocking allocation:
   - If movable: relocate to a different region
   - If reclaimable: try to reclaim (page cache, slab)
   - If unmovable: skip (cannot help)
   
3. After relocation:
   - Coalesce the freed region with buddies
   - Propagate coalescing upward
   
4. Repeat until target order is achievable or no progress

Linux CMA (Contiguous Memory Allocator):

For systems needing large contiguous regions (video buffers, etc.), Linux reserves a CMA region:

CMA Region:
[       Reserved for CMA allocations         ]

- Normally used for movable pages (file cache, etc.)
- When CMA allocation needed, movable pages are migrated out
- CMA allocation gets contiguous physical memory
- After CMA free, region returns to general movable pool

Benefit: Contiguous memory available without permanent reservation

The Fragmentation Arms Race

Anti-fragmentation in modern kernels is a constant battle. As systems grow more complex, new sources of fragmentation emerge. The Linux kernel's anti-fragmentation work spans over a decade of patches, and improvements continue. Understanding the fundamental trade-offs—buddy's efficient coalescing vs. its power-of-two constraints—enables appreciation of why this remains an active area of development.

Summary: Buddy System Fragmentation

Buddy system fragmentation is a nuanced topic with both internal and external components. Understanding these characteristics enables informed decisions about when buddy allocation is appropriate and how to mitigate its limitations.

Key Takeaways

•Internal fragmentation is inherent in power-of-two sizing—worst case ~50%, average case ~25% for uniform distributions.
•External fragmentation can occur in buddy systems when allocated blocks prevent buddy coalescing, despite overall free memory.
•Memory utilization depends heavily on workload—well-behaved patterns achieve 70-85%, adversarial patterns can fall below 50%.
•Buddy's advantage is efficient coalescing (O(1) per level) at the cost of size flexibility—a deliberate trade-off.
•Mitigation strategies include size class subdivision, lifetime segregation, migrate type classification, and buddy-aware compaction.
•Hybrid approaches (Buddy + Slab) combine the best of both worlds—slab handles small allocations efficiently, buddy manages pages.

Module Summary:

This module has provided comprehensive coverage of memory compaction and the buddy system—two fundamental approaches to managing memory fragmentation in operating systems:

Memory Compaction — Relocating allocations to consolidate free space, with significant performance costs
Compaction Cost — CPU, bandwidth, cache, and latency impacts of compaction operations
Buddy System Algorithm — Power-of-two allocation with efficient O(1) buddy identification and coalescing
Power-of-Two Allocation — Mathematical properties that enable efficient sizing operations
Buddy System Fragmentation — Characteristics, bounds, and mitigation of both internal and external fragmentation

Together, these topics provide the foundation for understanding memory management in modern operating systems, from the Linux kernel to embedded real-time systems.

Module Complete

Congratulations! You've completed the Compaction and Buddy System module. You now possess deep knowledge of these foundational memory management techniques—knowledge that forms the basis of how operating systems like Linux, Windows, and FreeBSD manage physical memory to this day.