Memory Fragmentation: Internal and External

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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <stdbool.h>
#include <string.h>
#include <math.h>
 
// Block header structure (embedded in each block)
typedef struct BlockHeader {
    size_t size;           // Size of data portion
    size_t allocated_size; // Actual allocated size (includes padding)
    bool is_free;
    struct BlockHeader* next;
    struct BlockHeader* prev;
} BlockHeader;
 
// Fragmentation statistics
typedef struct {
    // Internal fragmentation
    size_t total_requested;    // Sum of user-requested sizes
    size_t total_allocated;    // Sum of actual allocated sizes
    size_t allocation_count;   // Number of active allocations
    
    // External fragmentation
    size_t total_free;         // Total free memory
    size_t largest_hole;       // Largest contiguous free block
    size_t smallest_hole;      // Smallest free block
    size_t hole_count;         // Number of free blocks
    double hole_size_sum_sq;   // For variance calculation
    
    // Derived metrics (computed on demand)
    double internal_frag_ratio;
    double external_frag_ratio;
    double utilization;
    double hole_size_mean;
    double hole_size_variance;
} FragmentationStats;
 
typedef struct {
    BlockHeader* head;
    size_t total_memory;
    size_t header_size;
    FragmentationStats stats;
} InstrumentedAllocator;
 
#define ALIGNMENT 8
#define ALIGN(size) (((size) + (ALIGNMENT-1)) & ~(ALIGNMENT-1))
 
// Initialize allocator with given memory size
InstrumentedAllocator* create_allocator(size_t total_size) {
    InstrumentedAllocator* alloc = malloc(sizeof(InstrumentedAllocator));
    alloc->total_memory = total_size;
    alloc->header_size = ALIGN(sizeof(BlockHeader));
    
    // Create initial free block
    alloc->head = malloc(sizeof(BlockHeader) + total_size);
    alloc->head->size = total_size;
    alloc->head->allocated_size = total_size;
    alloc->head->is_free = true;
    alloc->head->next = NULL;
    alloc->head->prev = NULL;
    
    // Initialize stats
    memset(&alloc->stats, 0, sizeof(FragmentationStats));
    alloc->stats.total_free = total_size;
    alloc->stats.largest_hole = total_size;
    alloc->stats.smallest_hole = total_size;
    alloc->stats.hole_count = 1;
    
    return alloc;
}
 
// Update statistics when allocating
void update_stats_on_alloc(InstrumentedAllocator* alloc, 
                           size_t requested, size_t allocated,
                           BlockHeader* block, BlockHeader* remainder) {
    FragmentationStats* s = &alloc->stats;
    
    // Internal fragmentation tracking
    s->total_requested += requested;
    s->total_allocated += allocated;
    s->allocation_count++;
    
    // External fragmentation: update free memory tracking
    s->total_free -= allocated;
    s->hole_count--;  // This hole is now allocated
    
    if (remainder) {
        // Splitting created a new hole
        s->hole_count++;
    }
    
    // Must rescan for largest/smallest hole (simplified)
    // In production, maintain a sorted structure
}
 
// Update statistics when freeing
void update_stats_on_free(InstrumentedAllocator* alloc,
                          size_t requested, size_t allocated,
                          bool coalesced_prev, bool coalesced_next) {
    FragmentationStats* s = &alloc->stats;
    
    // Internal fragmentation tracking
    s->total_requested -= requested;
    s->total_allocated -= allocated;
    s->allocation_count--;
    
    // External fragmentation
    s->total_free += allocated;
    
    // Hole count changes depend on coalescing
    if (coalesced_prev && coalesced_next) {
        s->hole_count--;  // Two holes merged into one
    } else if (!coalesced_prev && !coalesced_next) {
        s->hole_count++;  // New hole created
    }
    // If exactly one coalesced, hole count unchanged
}
 
// Compute derived fragmentation metrics
void compute_derived_metrics(InstrumentedAllocator* alloc) {
    FragmentationStats* s = &alloc->stats;
    
    // Internal fragmentation ratio
    if (s->total_allocated > 0) {
        s->internal_frag_ratio = 
            (double)(s->total_allocated - s->total_requested) 
            / s->total_allocated;
    } else {
        s->internal_frag_ratio = 0;
    }
    
    // External fragmentation ratio
    if (s->total_free > 0) {
        s->external_frag_ratio = 
            1.0 - ((double)s->largest_hole / s->total_free);
    } else {
        s->external_frag_ratio = 0;
    }
    
    // Utilization
    s->utilization = 
        (double)s->total_requested / alloc->total_memory;
    
    // Hole statistics (require scanning free list)
    if (s->hole_count > 0) {
        s->hole_size_mean = (double)s->total_free / s->hole_count;
    }
}
 
// Full scan to recalculate hole statistics
void scan_hole_statistics(InstrumentedAllocator* alloc) {
    FragmentationStats* s = &alloc->stats;
    
    s->total_free = 0;
    s->largest_hole = 0;
    s->smallest_hole = SIZE_MAX;
    s->hole_count = 0;
    s->hole_size_sum_sq = 0;
    
    BlockHeader* block = alloc->head;
    while (block) {
        if (block->is_free) {
            s->total_free += block->size;
            s->hole_count++;
            
            if (block->size > s->largest_hole) 
                s->largest_hole = block->size;
            if (block->size < s->smallest_hole) 
                s->smallest_hole = block->size;
        }
        block = block->next;
    }
    
    // Compute variance (requires second pass or running sum)
    if (s->hole_count > 0) {
        double mean = (double)s->total_free / s->hole_count;
        s->hole_size_variance = 0;
        
        block = alloc->head;
        while (block) {
            if (block->is_free) {
                double diff = block->size - mean;
                s->hole_size_variance += diff * diff;
            }
            block = block->next;
        }
        s->hole_size_variance /= s->hole_count;
    }
    
    if (s->smallest_hole == SIZE_MAX) s->smallest_hole = 0;
    
    compute_derived_metrics(alloc);
}
 
// Print comprehensive fragmentation report
void print_fragmentation_report(InstrumentedAllocator* alloc) {
    scan_hole_statistics(alloc);
    FragmentationStats* s = &alloc->stats;
    
    printf("
╔══════════════════════════════════════════════════════╗
");
    printf("║         FRAGMENTATION ANALYSIS REPORT                ║
");
    printf("╠══════════════════════════════════════════════════════╣
");
    
    printf("║ MEMORY OVERVIEW                                      ║
");
    printf("║   Total Memory:      %10zu bytes                ║
", 
           alloc->total_memory);
    printf("║   Allocated:         %10zu bytes                ║
", 
           s->total_allocated);
    printf("║   Free:              %10zu bytes                ║
", 
           s->total_free);
    printf("║   Utilization:           %6.2f%%                    ║
", 
           s->utilization * 100);
    
    printf("╠══════════════════════════════════════════════════════╣
");
    printf("║ INTERNAL FRAGMENTATION                               ║
");
    printf("║   Requested:         %10zu bytes                ║
", 
           s->total_requested);
    printf("║   Actually Used:     %10zu bytes                ║
", 
           s->total_allocated);
    printf("║   Wasted (internal): %10zu bytes                ║
", 
           s->total_allocated - s->total_requested);
    printf("║   IF Ratio:              %6.2f%%                    ║
", 
           s->internal_frag_ratio * 100);
    
    printf("╠══════════════════════════════════════════════════════╣
");
    printf("║ EXTERNAL FRAGMENTATION                               ║
");
    printf("║   Number of Holes:   %10zu                      ║
", 
           s->hole_count);
    printf("║   Largest Hole:      %10zu bytes                ║
", 
           s->largest_hole);
    printf("║   Smallest Hole:     %10zu bytes                ║
", 
           s->smallest_hole);
    printf("║   Mean Hole Size:    %10.1f bytes                ║
", 
           s->hole_size_mean);
    printf("║   Hole Size Std Dev: %10.1f bytes                ║
", 
           sqrt(s->hole_size_variance));
    printf("║   EF Ratio:              %6.2f%%                    ║
", 
           s->external_frag_ratio * 100);
    
    printf("╠══════════════════════════════════════════════════════╣
");
    printf("║ HEALTH ASSESSMENT                                    ║
");
    
    // Severity assessment
    const char* severity;
    if (s->external_frag_ratio < 0.2) severity = "HEALTHY";
    else if (s->external_frag_ratio < 0.4) severity = "MILD";
    else if (s->external_frag_ratio < 0.6) severity = "MODERATE";
    else if (s->external_frag_ratio < 0.8) severity = "SEVERE";
    else severity = "CRITICAL";
    
    printf("║   Severity:          %10s                      ║
", severity);
    
    // 50% rule analysis
    if (s->allocation_count > 0) {
        double expected_holes = s->allocation_count / 2.0;
        double deviation = (s->hole_count - expected_holes) / expected_holes;
        printf("║   50%% Rule Deviation:    %+6.1f%%                    ║
", 
               deviation * 100);
    }
    
    printf("╚══════════════════════════════════════════════════════╝
");
}

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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158

#include <stdio.h>
#include <stdlib.h>
 
typedef struct {
    int start;
    int size;
    int is_allocated;
} Block;
 
// ASCII memory map visualization
void visualize_memory_map(Block* blocks, int count, int total_mem) {
    int scale = 80;  // Characters width
    printf("
╔");
    for (int i = 0; i < scale; i++) printf("═");
    printf("╗
║");
    
    for (int b = 0; b < count; b++) {
        int start_pos = (blocks[b].start * scale) / total_mem;
        int end_pos = ((blocks[b].start + blocks[b].size) * scale) / total_mem;
        int width = end_pos - start_pos;
        if (width < 1) width = 1;
        
        char fill = blocks[b].is_allocated ? '█' : '░';
        for (int i = 0; i < width; i++) {
            printf("%c", fill);
        }
    }
    
    printf("║
╚");
    for (int i = 0; i < scale; i++) printf("═");
    printf("╝
");
    printf("Legend: █ = Allocated, ░ = Free
");
}
 
// Hole size histogram
void visualize_hole_histogram(int* hole_sizes, int count, int max_size) {
    int buckets = 10;
    int bucket_size = (max_size + buckets - 1) / buckets;
    int* bucket_counts = calloc(buckets, sizeof(int));
    
    for (int i = 0; i < count; i++) {
        int bucket = hole_sizes[i] / bucket_size;
        if (bucket >= buckets) bucket = buckets - 1;
        bucket_counts[bucket]++;
    }
    
    // Find max count for scaling
    int max_count = 0;
    for (int i = 0; i < buckets; i++) {
        if (bucket_counts[i] > max_count) max_count = bucket_counts[i];
    }
    
    printf("
Hole Size Distribution:
");
    printf("────────────────────────────────
");
    
    int bar_width = 30;
    for (int i = 0; i < buckets; i++) {
        int bar_len = (bucket_counts[i] * bar_width) / (max_count > 0 ? max_count : 1);
        printf("%5d-%5d │", i * bucket_size, (i+1) * bucket_size - 1);
        for (int j = 0; j < bar_len; j++) printf("▓");
        printf(" %d
", bucket_counts[i]);
    }
    
    free(bucket_counts);
}
 
// Time series data structure
typedef struct {
    double* values;
    int count;
    int capacity;
} TimeSeries;
 
void add_sample(TimeSeries* ts, double value) {
    if (ts->count >= ts->capacity) {
        ts->capacity *= 2;
        ts->values = realloc(ts->values, ts->capacity * sizeof(double));
    }
    ts->values[ts->count++] = value;
}
 
// ASCII Sparkline visualization
void visualize_sparkline(double* values, int count, const char* label) {
    if (count == 0) return;
    
    double min_val = values[0], max_val = values[0];
    for (int i = 1; i < count; i++) {
        if (values[i] < min_val) min_val = values[i];
        if (values[i] > max_val) max_val = values[i];
    }
    
    const char* blocks = "▁▂▃▄▅▆▇█";
    int levels = 8;
    double range = max_val - min_val;
    if (range == 0) range = 1;
    
    printf("%12s: ", label);
    
    // Show last 50 values at most
    int start = count > 50 ? count - 50 : 0;
    for (int i = start; i < count; i++) {
        int level = (int)((values[i] - min_val) / range * (levels - 1));
        if (level >= levels) level = levels - 1;
        printf("%c", blocks[level * 3]);  // UTF-8 block chars
    }
    printf(" (%.2f-%.2f)
", min_val, max_val);
}
 
// Generate sample fragmentation report with visualizations
void demo_visualization() {
    printf("
═══════════════════════════════════════════════════════════════
");
    printf("             FRAGMENTATION VISUALIZATION DEMO
");
    printf("═══════════════════════════════════════════════════════════════
");
    
    // Sample blocks
    Block blocks[] = {
        {0, 100, 1}, {100, 50, 0}, {150, 200, 1}, {350, 30, 0},
        {380, 150, 1}, {530, 80, 0}, {610, 90, 1}, {700, 40, 0},
        {740, 120, 1}, {860, 60, 0}, {920, 80, 1}
    };
    int block_count = sizeof(blocks) / sizeof(blocks[0]);
    
    printf("
Memory Layout (1000 units total):");
    visualize_memory_map(blocks, block_count, 1000);
    
    // Sample hole sizes
    int hole_sizes[] = {50, 30, 80, 40, 60, 15, 45, 25, 70, 35, 20, 55, 10, 65};
    int hole_count = sizeof(hole_sizes) / sizeof(hole_sizes[0]);
    visualize_hole_histogram(hole_sizes, hole_count, 100);
    
    // Sample time series
    double ef_history[] = {0.12, 0.15, 0.18, 0.22, 0.19, 0.25, 0.31, 0.28,
                           0.35, 0.42, 0.38, 0.45, 0.52, 0.48, 0.55, 0.51};
    printf("
Fragmentation Over Time:
");
    visualize_sparkline(ef_history, 16, "EF Ratio");
}
 
int main() {
    demo_visualization();
    return 0;
}

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

#!/bin/bash
# Parse buddyinfo and calculate fragmentation metrics
 
echo "=== Linux Memory Fragmentation Analysis ==="
echo
 
# Read buddyinfo
while read line; do
    # Parse zone information
    if [[ $line =~ ^Node ]]; then
        zone=$(echo $line | awk '{print $4}')
        
        # Extract order counts (columns 5 onwards)
        counts=($(echo $line | awk '{for(i=5;i<=NF;i++) print $i}'))
        
        # Calculate total free pages
        total=0
        weighted_sum=0
        for i in "${!counts[@]}"; do
            pages=$((counts[i] * (1 << i)))  # Pages in this order
            total=$((total + pages))
            weighted_sum=$((weighted_sum + pages * (1 << i)))  # Weighted by size
        done
        
        # Calculate fragmentation index
        # High orders available vs total
        high_order_pages=0
        for i in 7 8 9 10; do
            if [ $i -lt ${#counts[@]} ]; then
                high_order_pages=$((high_order_pages + counts[i] * (1 << i)))
            fi
        done
        
        if [ $total -gt 0 ]; then
            frag_pct=$((100 - (high_order_pages * 100 / total)))
        else
            frag_pct=0
        fi
        
        echo "Zone: $zone"
        echo "  Total free pages: $total ($(($total * 4 / 1024)) MB)"
        echo "  High-order pages (order 7+): $high_order_pages"
        echo "  Fragmentation estimate: $frag_pct%"
        echo
    fi
done < /proc/buddyinfo
 
# Additional info from pagetypeinfo if available
if [ -f /proc/pagetypeinfo ]; then
    echo "=== Page Type Distribution ==="
    head -20 /proc/pagetypeinfo
fi

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
102
103
104
105
106
107
108
109
110
111
112
113
114
115

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
 
// glibc malloc analysis functions
void analyze_glibc_malloc() {
    printf("
=== glibc malloc Statistics ===
 
");
    
    // malloc_stats() prints to stderr
    printf("Calling malloc_stats():
");
    malloc_stats();
    
    printf("
");
    
    // malloc_info() provides XML output
    // malloc_info(0, stdout);
    
    // mallinfo() provides structured data (deprecated but simple)
    struct mallinfo mi = mallinfo();
    
    printf("
mallinfo() results:
");
    printf("  arena:    %10d bytes  (total heap from system)
", mi.arena);
    printf("  ordblks:  %10d        (number of free chunks)
", mi.ordblks);
    printf("  smblks:   %10d        (small free blocks)
", mi.smblks);
    printf("  hblks:    %10d        (number of mmapped regions)
", mi.hblks);
    printf("  hblkhd:   %10d bytes  (mmapped bytes)
", mi.hblkhd);
    printf("  uordblks: %10d bytes  (allocated bytes)
", mi.uordblks);
    printf("  fordblks: %10d bytes  (free bytes)
", mi.fordblks);
    printf("  keepcost: %10d bytes  (top-most releasable space)
", mi.keepcost);
    
    // Calculate fragmentation metrics
    if (mi.arena > 0) {
        double utilization = (double)mi.uordblks / mi.arena * 100;
        double internal_waste = (double)(mi.arena - mi.uordblks - mi.fordblks) 
                               / mi.arena * 100;
        
        printf("
Derived Metrics:
");
        printf("  Heap utilization: %.1f%%
", utilization);
        printf("  Internal overhead: %.1f%%
", internal_waste);
        printf("  Free chunk ratio: %.1f%%
", 
               (double)mi.fordblks / mi.arena * 100);
    }
}
 
// Demonstrate with a workload
int main() {
    printf("=== Memory Allocator Fragmentation Analysis ===
");
    
    // Initial state
    printf("
--- Initial State ---");
    analyze_glibc_malloc();
    
    // Allocate many small blocks
    #define NUM_ALLOCS 10000
    void* ptrs[NUM_ALLOCS];
    
    printf("
--- After %d allocations (100-500 bytes each) ---", NUM_ALLOCS);
    for (int i = 0; i < NUM_ALLOCS; i++) {
        ptrs[i] = malloc(100 + rand() % 400);
    }
    analyze_glibc_malloc();
    
    // Free every other block (create fragmentation)
    printf("
--- After freeing every other block ---");
    for (int i = 0; i < NUM_ALLOCS; i += 2) {
        free(ptrs[i]);
        ptrs[i] = NULL;
    }
    analyze_glibc_malloc();
    
    // Attempt large allocation
    printf("
--- Attempting large allocation (1MB) ---");
    void* big = malloc(1024 * 1024);
    if (big) {
        printf("Large allocation succeeded (via mmap likely)
");
        free(big);
    } else {
        printf("Large allocation FAILED
");
    }
    analyze_glibc_malloc();
    
    // Cleanup
    for (int i = 0; i < NUM_ALLOCS; i++) {
        if (ptrs[i]) free(ptrs[i]);
    }
    
    return 0;
}

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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139

#!/usr/bin/env python3
"""
Memory Fragmentation Monitor for Production Systems
 
Periodically samples fragmentation metrics and:
- Logs to file/monitoring system
- Sends alerts when thresholds exceeded
- Triggers compaction when appropriate
"""
 
import subprocess
import time
import json
from datetime import datetime
from dataclasses import dataclass
from typing import List, Optional
 
@dataclass
class FragmentationMetrics:
    timestamp: str
    zone: str
    total_free_pages: int
    high_order_free: int  # Order 7+ pages
    fragmentation_index: float
    largest_contiguous_kb: int
 
@dataclass
class AlertThresholds:
    frag_index_warn: float = 0.6
    frag_index_critical: float = 0.8
    high_order_min: int = 100  # Minimum high-order pages
 
class FragmentationMonitor:
    def __init__(self, log_file: str = "/var/log/fragmentation.json"):
        self.log_file = log_file
        self.thresholds = AlertThresholds()
        self.history: List[FragmentationMetrics] = []
    
    def parse_buddyinfo(self) -> List[FragmentationMetrics]:
        """Parse /proc/buddyinfo and return metrics per zone."""
        metrics = []
        try:
            with open('/proc/buddyinfo', 'r') as f:
                for line in f:
                    if not line.startswith('Node'):
                        continue
                    
                    parts = line.split()
                    zone = parts[3].rstrip(',')
                    counts = [int(x) for x in parts[4:]]
                    
                    # Calculate metrics
                    total_pages = sum(c * (2**i) for i, c in enumerate(counts))
                    high_order = sum(c * (2**i) for i, c in enumerate(counts) if i >= 7)
                    largest = 0
                    for i in range(len(counts)-1, -1, -1):
                        if counts[i] > 0:
                            largest = (2**i) * 4  # KB
                            break
                    
                    # Fragmentation index (0 = no frag, 1 = max frag)
                    frag_idx = 1.0 - (high_order / max(total_pages, 1))
                    
                    metrics.append(FragmentationMetrics(
                        timestamp=datetime.now().isoformat(),
                        zone=zone,
                        total_free_pages=total_pages,
                        high_order_free=high_order,
                        fragmentation_index=round(frag_idx, 3),
                        largest_contiguous_kb=largest
                    ))
        except Exception as e:
            print(f"Error parsing buddyinfo: {e}")
        
        return metrics
    
    def check_alerts(self, metrics: FragmentationMetrics) -> Optional[str]:
        """Check if metrics exceed thresholds."""
        if metrics.fragmentation_index >= self.thresholds.frag_index_critical:
            return f"CRITICAL: Zone {metrics.zone} fragmentation at {metrics.fragmentation_index:.1%}"
        elif metrics.fragmentation_index >= self.thresholds.frag_index_warn:
            return f"WARNING: Zone {metrics.zone} fragmentation at {metrics.fragmentation_index:.1%}"
        elif metrics.high_order_free < self.thresholds.high_order_min:
            return f"WARNING: Zone {metrics.zone} low high-order pages: {metrics.high_order_free}"
        return None
    
    def trigger_compaction(self) -> bool:
        """Request memory compaction from kernel."""
        try:
            with open('/proc/sys/vm/compact_memory', 'w') as f:
                f.write('1')
            return True
        except PermissionError:
            print("Permission denied for compaction (need root)")
            return False
        except Exception as e:
            print(f"Compaction failed: {e}")
            return False
    
    def log_metrics(self, metrics: List[FragmentationMetrics]):
        """Append metrics to log file."""
        try:
            with open(self.log_file, 'a') as f:
                for m in metrics:
                    f.write(json.dumps(m.__dict__) + '
')
        except Exception as e:
            print(f"Logging failed: {e}")
    
    def run(self, interval_seconds: int = 60):
        """Main monitoring loop."""
        print(f"Starting fragmentation monitor (interval: {interval_seconds}s)")
        print(f"Alert thresholds: warn={self.thresholds.frag_index_warn:.0%}, "
              f"critical={self.thresholds.frag_index_critical:.0%}")
        
        while True:
            metrics = self.parse_buddyinfo()
            self.log_metrics(metrics)
            
            for m in metrics:
                alert = self.check_alerts(m)
                if alert:
                    print(f"[{m.timestamp}] {alert}")
                    
                    # Auto-trigger compaction on critical
                    if 'CRITICAL' in alert:
                        print("Triggering memory compaction...")
                        if self.trigger_compaction():
                            print("Compaction triggered successfully")
                else:
                    print(f"[{m.timestamp}] Zone {m.zone}: "
                          f"frag={m.fragmentation_index:.1%}, "
                          f"largest={m.largest_contiguous_kb}KB")
            
            time.sleep(interval_seconds)
 
if __name__ == '__main__':
    monitor = FragmentationMonitor()
    monitor.run(interval_seconds=30)

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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
 
#define MAX_ALLOCS 50000
 
typedef struct {
    void* ptr;
    size_t size;
    int active;
} Allocation;
 
typedef struct {
    const char* name;
    double avg_fragmentation;
    double max_fragmentation;
    size_t peak_memory;
    int failed_allocs;
    double steady_state_frag;
} BenchmarkResult;
 
// Simulated fragmentation measurement (in real code, query allocator)
double measure_fragmentation() {
    struct mallinfo mi = mallinfo();
    if (mi.arena == 0) return 0;
    // Approximate: unused arena space / total arena
    return (double)(mi.arena - mi.uordblks) / mi.arena;
}
 
BenchmarkResult run_benchmark(const char* name, 
                               size_t (*size_gen)(void),
                               int (*free_selector)(Allocation*, int)) {
    printf("Running benchmark: %s
", name);
    
    Allocation allocs[MAX_ALLOCS] = {0};
    int alloc_count = 0;
    
    BenchmarkResult result = {0};
    result.name = name;
    
    double frag_sum = 0;
    int frag_samples = 0;
    
    // Warm-up: fill to ~50% target occupancy
    for (int i = 0; i < MAX_ALLOCS / 2; i++) {
        size_t size = size_gen();
        allocs[i].ptr = malloc(size);
        if (allocs[i].ptr) {
            allocs[i].size = size;
            allocs[i].active = 1;
            alloc_count++;
        } else {
            result.failed_allocs++;
        }
    }
    
    // Steady-state: allocate and free at balanced rate
    for (int iter = 0; iter < 100000; iter++) {
        // Randomly allocate or free
        if (rand() % 2 == 0 && alloc_count < MAX_ALLOCS) {
            // Allocate
            for (int i = 0; i < MAX_ALLOCS; i++) {
                if (!allocs[i].active) {
                    size_t size = size_gen();
                    allocs[i].ptr = malloc(size);
                    if (allocs[i].ptr) {
                        allocs[i].size = size;
                        allocs[i].active = 1;
                        alloc_count++;
                    } else {
                        result.failed_allocs++;
                    }
                    break;
                }
            }
        } else if (alloc_count > 0) {
            // Free based on selector
            int idx = free_selector(allocs, MAX_ALLOCS);
            if (idx >= 0 && allocs[idx].active) {
                free(allocs[idx].ptr);
                allocs[idx].active = 0;
                allocs[idx].ptr = NULL;
                alloc_count--;
            }
        }
        
        // Sample fragmentation periodically
        if (iter % 1000 == 0 && iter >= 10000) {
            double frag = measure_fragmentation();
            frag_sum += frag;
            frag_samples++;
            
            if (frag > result.max_fragmentation) {
                result.max_fragmentation = frag;
            }
        }
    }
    
    result.avg_fragmentation = frag_samples > 0 ? frag_sum / frag_samples : 0;
    result.steady_state_frag = measure_fragmentation();
    
    // Cleanup
    for (int i = 0; i < MAX_ALLOCS; i++) {
        if (allocs[i].active) {
            free(allocs[i].ptr);
        }
    }
    
    return result;
}
 
// Size generators
size_t uniform_size() { return 256; }
size_t bimodal_size() { return (rand() % 100 < 80) ? (32 + rand() % 96) : (1024 + rand() % 3072); }
size_t powerlaw_size() { 
    double u = (double)rand() / RAND_MAX;
    return (size_t)(16 * pow(1.0 / u, 0.5));  // Rough power-law
}
 
// Free selectors  
int random_free(Allocation* a, int n) {
    int active[MAX_ALLOCS];
    int count = 0;
    for (int i = 0; i < n; i++) {
        if (a[i].active) active[count++] = i;
    }
    return count > 0 ? active[rand() % count] : -1;
}
 
int oldest_free(Allocation* a, int n) {
    for (int i = 0; i < n; i++) {
        if (a[i].active) return i;
    }
    return -1;
}
 
int newest_free(Allocation* a, int n) {
    for (int i = n-1; i >= 0; i--) {
        if (a[i].active) return i;
    }
    return -1;
}
 
void print_result(BenchmarkResult* r) {
    printf("  %-25s: avg=%.1f%%, max=%.1f%%, steady=%.1f%%, failed=%d
",
           r->name, 
           r->avg_fragmentation * 100,
           r->max_fragmentation * 100,
           r->steady_state_frag * 100,
           r->failed_allocs);
}
 
int main() {
    srand(time(NULL));
    
    printf("
=== Fragmentation Benchmark Suite ===
 
");
    
    BenchmarkResult results[] = {
        run_benchmark("Uniform/Random", uniform_size, random_free),
        run_benchmark("Uniform/FIFO", uniform_size, oldest_free),
        run_benchmark("Uniform/LIFO", uniform_size, newest_free),
        run_benchmark("Bimodal/Random", bimodal_size, random_free),
        run_benchmark("Bimodal/FIFO", bimodal_size, oldest_free),
        run_benchmark("PowerLaw/Random", powerlaw_size, random_free),
    };
    
    printf("
=== Results ===
");
    for (int i = 0; i < sizeof(results)/sizeof(results[0]); i++) {
        print_result(&results[i]);
    }
    
    return 0;
}