Contiguous Memory Allocation Fundamentals

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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101

// Mathematical analysis of fragmentation in contiguous allocation
 
// ============================================================
// EXTERNAL FRAGMENTATION ANALYSIS (Variable Partitioning)
// ============================================================
 
// Knuth's 50% Rule (proven mathematically)
// At steady state with random allocations/deallocations:
//   Expected number of holes ≈ N / 2
//   where N = number of allocated blocks
 
// Memory efficiency calculation
FUNCTION CalculateExternalFragmentation(memory_state):
    total_memory := 0
    allocated_memory := 0
    largest_hole := 0
    total_holes := 0
    
    FOR EACH block IN memory_state:
        total_memory += block.size
        IF block.is_allocated THEN
            allocated_memory += block.size
        ELSE
            total_holes += block.size
            IF block.size > largest_hole THEN
                largest_hole := block.size
            END IF
        END IF
    END FOR
    
    // Key metrics
    fragmentation_ratio := total_holes / total_memory
    utilization := allocated_memory / total_memory
    
    // Can we allocate a process of size X?
    // Only if largest_hole >= X, NOT if total_holes >= X!
    
    RETURN {
        fragmentation: fragmentation_ratio,
        utilization: utilization,
        largest_allocatable: largest_hole,
        total_free: total_holes
    }
 
// Example scenario:
// Total memory: 1000KB
// Allocated: 600KB across 6 processes
// Free: 400KB across 4 holes of sizes [50KB, 100KB, 80KB, 170KB]
//
// Can we allocate a 300KB process?
// Total free (400KB) > needed (300KB), BUT
// Largest hole (170KB) < needed (300KB)
// ANSWER: NO - external fragmentation prevents allocation!
 
// ============================================================
// INTERNAL FRAGMENTATION ANALYSIS (Fixed Partitioning)
// ============================================================
 
FUNCTION CalculateInternalFragmentation(partitions, processes):
    total_allocated := 0
    total_used := 0
    
    FOR EACH assignment IN AssignProcessesToPartitions(partitions, processes):
        partition := assignment.partition
        process := assignment.process
        
        total_allocated += partition.size
        total_used += process.size
        
        wasted := partition.size - process.size
        PRINT "Process {process.name} in {partition.size}KB partition: {wasted}KB wasted"
    END FOR
    
    internal_fragmentation := (total_allocated - total_used) / total_allocated
    
    RETURN internal_fragmentation
 
// Example:
// Partitions: [32KB, 64KB, 128KB, 256KB, 512KB] = 992KB total
// Processes:  [20KB, 50KB, 100KB, 200KB, 400KB] = 770KB needed
// 
// Best-fit assignment:
//   20KB  -> 32KB  partition (12KB wasted)
//   50KB  -> 64KB  partition (14KB wasted)
//   100KB -> 128KB partition (28KB wasted)
//   200KB -> 256KB partition (56KB wasted)
//   400KB -> 512KB partition (112KB wasted)
//
// Total wasted: 222KB / 992KB = 22.4% internal fragmentation
 
// ============================================================
// COMBINED ANALYSIS
// ============================================================
 
// Neither fixed nor variable partitioning is fragmentation-free:
// - Fixed: Internal fragmentation (wasted space within partitions)
// - Variable: External fragmentation (unusable holes between allocations)
//
// Paging eliminates BOTH by:
// - Fixed-size units (no external fragmentation between units)
// - Any-size allocation (no internal fragmentation beyond last page)

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

// Decision framework: Should you use contiguous allocation?
 
FUNCTION ShouldUseContiguousAllocation(system_requirements):
    // Hard constraints favoring contiguous allocation
    IF system.ram_size < 256KB THEN
        // Page table overhead unacceptable
        RETURN "Contiguous: Minimal memory system"
    END IF
    
    IF system.certification_required AND 
       system.certification_type IN [DO-178C, IEC-62304, ISO-26262] THEN
        // Certification favors simpler, analyzable systems
        RETURN "Contiguous: Safety-critical certification"
    END IF
    
    IF system.requires_hard_realtime AND 
       system.deadline < 1ms THEN
        // Page fault latency could violate deadline
        RETURN "Contiguous: Extreme real-time requirements"
    END IF
    
    IF system.has_mmu = FALSE THEN
        // No hardware support for paging
        RETURN "Contiguous: No MMU available"
    END IF
    
    // Factors favoring paging/virtual memory
    IF system.requires_multiple_large_programs THEN
        RETURN "Paging: Need virtual memory"
    END IF
    
    IF system.requires_shared_libraries THEN
        RETURN "Paging: Need memory sharing"
    END IF
    
    IF system.program_size > system.ram_size THEN
        RETURN "Paging: Programs exceed physical memory"
    END IF
    
    IF system.requires_memory_protection THEN
        // Base/limit provides protection, but paging is more flexible
        IF system.needs_fine_grained_protection THEN
            RETURN "Paging: Need per-page protection"
        END IF
    END IF
    
    // Default: modern systems generally benefit from paging
    RETURN "Paging: General-purpose computing"
 
// Modern hybrid approach: use paging for general allocation,
// but support contiguous allocation for specific needs
// (e.g., Linux's Contiguous Memory Allocator for DMA)

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
77
78
79
80
81
82
83
84
85
86
87
88

/*
 * Linux Contiguous Memory Allocator (CMA) usage example
 * Demonstrates modern contiguous allocation for DMA devices
 */
 
#include <linux/dma-mapping.h>
#include <linux/cma.h>
 
/*
 * Scenario: A video capture device needs a 16MB contiguous buffer
 * for DMA transfers. The page allocator cannot guarantee contiguity
 * for such a large region. CMA provides the solution.
 */
 
struct video_device {
    void *buffer;               /* Virtual address of buffer */
    dma_addr_t dma_handle;      /* Physical/bus address for DMA */
    size_t size;
};
 
int initialize_video_buffer(struct device *dev, struct video_device *vdev) {
    /*
     * dma_alloc_coherent() uses CMA when configured
     * It allocates physically contiguous memory suitable for DMA
     * Returns both virtual address and physical (DMA) address
     */
    vdev->size = 16 * 1024 * 1024;  /* 16 MB */
    
    vdev->buffer = dma_alloc_coherent(
        dev,
        vdev->size,
        &vdev->dma_handle,  /* OUT: Physical address for hardware */
        GFP_KERNEL
    );
    
    if (!vdev->buffer) {
        /* 
         * Allocation failed - might be fragmented
         * This is the classic contiguous allocation problem
         * CMA mitigates but doesn't eliminate it
         */
        dev_err(dev, "Failed to allocate contiguous DMA buffer
");
        return -ENOMEM;
    }
    
    /*
     * vdev->buffer: Virtual address for CPU access
     * vdev->dma_handle: Physical address for DMA controller
     * 
     * The 16MB region is guaranteed to be physically contiguous,
     * enabling efficient scatter-gather-free DMA transfers
     */
    
    dev_info(dev, "Allocated 16MB contiguous buffer at phys 0x%llx
",
             (unsigned long long)vdev->dma_handle);
    
    return 0;
}
 
void cleanup_video_buffer(struct device *dev, struct video_device *vdev) {
    if (vdev->buffer) {
        dma_free_coherent(dev, vdev->size, vdev->buffer, vdev->dma_handle);
        vdev->buffer = NULL;
    }
}
 
/*
 * CMA configuration in kernel (Device Tree or boot param):
 * 
 * reserved-memory {
 *     #address-cells = <2>;
 *     #size-cells = <2>;
 *     ranges;
 * 
 *     linux,cma {
 *         compatible = "shared-dma-pool";
 *         reusable;
 *         size = <0 0x10000000>;  // 256 MB CMA region
 *     };
 * };
 *
 * This reserves 256MB for CMA at boot. The memory can be:
 * - Used for CMA allocations when devices need it
 * - Used as regular pages when CMA isn't needed
 * - Like variable partitioning, but much smarter
 */