Contiguous Allocation

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

/*
 * Directory Entry Structure for Contiguous Allocation
 * 
 * This structure represents how a file system using contiguous
 * allocation stores file metadata in directory entries.
 */
 
#include <stdint.h>
#include <time.h>
 
#define MAX_FILENAME_LENGTH 255
#define BLOCK_SIZE 4096  /* 4 KB blocks - typical modern size */
 
/* File type enumeration */
typedef enum {
    FILE_TYPE_REGULAR   = 0x01,
    FILE_TYPE_DIRECTORY = 0x02,
    FILE_TYPE_SYMLINK   = 0x03,
    FILE_TYPE_DEVICE    = 0x04
} file_type_t;
 
/* Permission bits (Unix-style) */
typedef struct {
    uint16_t owner_read   : 1;
    uint16_t owner_write  : 1;
    uint16_t owner_exec   : 1;
    uint16_t group_read   : 1;
    uint16_t group_write  : 1;
    uint16_t group_exec   : 1;
    uint16_t other_read   : 1;
    uint16_t other_write  : 1;
    uint16_t other_exec   : 1;
    uint16_t reserved     : 7;
} file_permissions_t;
 
/*
 * Contiguous Allocation Directory Entry
 * 
 * Note how simple this is compared to linked or indexed allocation:
 * - Only TWO fields needed to locate ALL file data: start_block + length
 * - No pointers, no index blocks, no FAT entries to follow
 */
typedef struct {
    /* File identification */
    char filename[MAX_FILENAME_LENGTH + 1];  /* Null-terminated filename */
    
    /* ====== THE KEY FIELDS FOR CONTIGUOUS ALLOCATION ====== */
    uint64_t start_block;    /* Starting block number on disk */
    uint32_t block_count;    /* Number of contiguous blocks */
    /* ======================================================= */
    
    /* File metadata */
    uint64_t file_size;      /* Actual file size in bytes */
    file_type_t file_type;   /* Type of file */
    file_permissions_t perms; /* Permission bits */
    
    /* Ownership */
    uint32_t owner_uid;      /* User ID of owner */
    uint32_t owner_gid;      /* Group ID of owner */
    
    /* Timestamps */
    time_t created_time;     /* File creation time */
    time_t modified_time;    /* Last modification time */
    time_t accessed_time;    /* Last access time */
    
} contiguous_dir_entry_t;
 
/*
 * Example: Calculating disk address from file position
 * 
 * Given: file starts at block 1000, position = 10,500 bytes
 * Block size = 4096 bytes
 * 
 * Block offset = position / BLOCK_SIZE = 10500 / 4096 = 2
 * Byte offset within block = position % BLOCK_SIZE = 10500 % 4096 = 2308
 * 
 * Disk block = start_block + block_offset = 1000 + 2 = 1002
 * Disk address = (disk_block * BLOCK_SIZE) + byte_offset
 *              = (1002 * 4096) + 2308 = 4,106,500
 */
static inline uint64_t calculate_disk_address(
    const contiguous_dir_entry_t *entry,
    uint64_t file_position
) {
    /* Calculate which block within the file */
    uint32_t block_offset = file_position / BLOCK_SIZE;
    
    /* Calculate offset within that block */
    uint32_t byte_offset = file_position % BLOCK_SIZE;
    
    /* Bounds check: ensure we're within the file's allocated blocks */
    if (block_offset >= entry->block_count) {
        return (uint64_t)-1;  /* Error: position beyond file */
    }
    
    /* Calculate absolute disk block number */
    uint64_t disk_block = entry->start_block + block_offset;
    
    /* Return absolute disk byte address */
    return (disk_block * BLOCK_SIZE) + byte_offset;
}
 
/*
 * Example usage:
 * 
 * contiguous_dir_entry_t myfile = {
 *     .filename = "data.bin",
 *     .start_block = 1000,
 *     .block_count = 100,    // 100 blocks = 400 KB
 *     .file_size = 409600,
 *     ...
 * };
 * 
 * // To read byte 50,000 of the file:
 * uint64_t disk_addr = calculate_disk_address(&myfile, 50000);
 * // disk_addr = block 1000 + (50000/4096) = block 1012, offset 688
 * // Absolute address = 1012 * 4096 + 688 = 4,145,840
 */

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

/*
 * Complete Address Translation Implementation
 * 
 * Demonstrates the mathematical elegance of contiguous allocation:
 * - O(1) address calculation for any file position
 * - No disk I/O required to compute addresses
 * - Trivial bounds checking
 */
 
#include <stdio.h>
#include <stdint.h>
#include <stdbool.h>
 
#define BLOCK_SIZE_BYTES    4096
#define SECTOR_SIZE_BYTES   512
#define SECTORS_PER_BLOCK   (BLOCK_SIZE_BYTES / SECTOR_SIZE_BYTES)
 
typedef struct {
    uint64_t block_number;      /* Logical block number */
    uint32_t block_offset;      /* Byte offset within the block */
    uint64_t absolute_address;  /* Absolute byte address on disk */
    uint64_t sector_number;     /* Physical sector (for disk driver) */
    uint32_t sector_offset;     /* Offset within sector */
} disk_location_t;
 
typedef struct {
    uint64_t start_block;       /* First block of the file */
    uint32_t block_count;       /* Total blocks allocated */
    uint64_t file_size_bytes;   /* Actual file size */
} file_allocation_t;
 
/**
 * Translates a logical file position to physical disk location.
 * 
 * This function demonstrates WHY contiguous allocation enables
 * such fast random access: the entire calculation is pure arithmetic
 * with no disk I/O, no pointer chasing, no indirection.
 * 
 * @param file      File allocation information
 * @param position  Byte position within the file (0-indexed)
 * @param location  Output: physical disk location
 * @return          true if position is valid, false otherwise
 */
bool translate_position(
    const file_allocation_t *file,
    uint64_t position,
    disk_location_t *location
) {
    /* Step 1: Bounds check - is this position within the file? */
    if (position >= file->file_size_bytes) {
        return false;  /* Position beyond end of file */
    }
    
    /* Step 2: Calculate which block within the file contains this position */
    uint64_t block_index = position / BLOCK_SIZE_BYTES;
    
    /* Step 3: Verify block is within allocated range */
    if (block_index >= file->block_count) {
        return false;  /* Position in unallocated region */
    }
    
    /* Step 4: Calculate the absolute disk block number */
    location->block_number = file->start_block + block_index;
    
    /* Step 5: Calculate offset within the block */
    location->block_offset = position % BLOCK_SIZE_BYTES;
    
    /* Step 6: Calculate absolute disk address (byte-addressable) */
    location->absolute_address = 
        (location->block_number * BLOCK_SIZE_BYTES) + location->block_offset;
    
    /* Step 7: Calculate sector-level addressing (for disk driver) */
    location->sector_number = 
        (location->block_number * SECTORS_PER_BLOCK) + 
        (location->block_offset / SECTOR_SIZE_BYTES);
    location->sector_offset = location->block_offset % SECTOR_SIZE_BYTES;
    
    return true;
}
 
/**
 * Example: Reading a range of bytes from a file
 * 
 * This shows how contiguous allocation enables efficient planning
 * of read operations - we know exactly which blocks to read before
 * issuing any I/O.
 */
typedef struct {
    uint64_t first_block;
    uint64_t last_block;
    uint32_t first_block_offset;
    uint32_t last_block_offset;
    uint32_t total_blocks;
} read_plan_t;
 
bool plan_read_operation(
    const file_allocation_t *file,
    uint64_t start_position,
    uint64_t byte_count,
    read_plan_t *plan
) {
    /* Validate range */
    uint64_t end_position = start_position + byte_count - 1;
    if (end_position >= file->file_size_bytes) {
        return false;
    }
    
    /* Calculate block range */
    plan->first_block = file->start_block + (start_position / BLOCK_SIZE_BYTES);
    plan->last_block = file->start_block + (end_position / BLOCK_SIZE_BYTES);
    
    plan->first_block_offset = start_position % BLOCK_SIZE_BYTES;
    plan->last_block_offset = end_position % BLOCK_SIZE_BYTES;
    
    plan->total_blocks = plan->last_block - plan->first_block + 1;
    
    return true;
}
 
/* Demonstration */
void demonstrate_address_calculation(void) {
    file_allocation_t example_file = {
        .start_block = 1000,
        .block_count = 500,          /* 500 blocks = 2 MB */
        .file_size_bytes = 2000000   /* ~1.9 MB actual data */
    };
    
    printf("File: starts at block 1000, 500 blocks, 2MB size
");
    printf("Block size: 4096 bytes
 
");
    
    /* Test various positions */
    uint64_t test_positions[] = {0, 100, 4096, 4097, 100000, 1000000};
    int num_tests = sizeof(test_positions) / sizeof(test_positions[0]);
    
    for (int i = 0; i < num_tests; i++) {
        disk_location_t loc;
        uint64_t pos = test_positions[i];
        
        if (translate_position(&example_file, pos, &loc)) {
            printf("Position %8lu -> Block %6lu, Offset %4u
",
                   pos, loc.block_number, loc.block_offset);
        }
    }
    
    /* Plan a read operation */
    printf("
Planning read of 10,000 bytes starting at position 50,000:
");
    read_plan_t plan;
    if (plan_read_operation(&example_file, 50000, 10000, &plan)) {
        printf("  Read blocks %lu through %lu (%u blocks)
",
               plan.first_block, plan.last_block, plan.total_blocks);
        printf("  First block offset: %u, Last block offset: %u
",
               plan.first_block_offset, plan.last_block_offset);
    }
}

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

/*
 * Contiguous Block Allocation Algorithms
 * 
 * Implementation of the four classic allocation strategies.
 * These are used when creating new files or extending existing ones.
 */
 
#include <stdio.h>
#include <stdint.h>
#include <stdbool.h>
#include <limits.h>
 
#define TOTAL_BLOCKS 10000
#define INVALID_BLOCK UINT64_MAX
 
/* Free space entry in the free list */
typedef struct free_extent {
    uint64_t start_block;
    uint32_t block_count;
    struct free_extent *next;
} free_extent_t;
 
/* Free space manager state */
typedef struct {
    free_extent_t *free_list;
    uint64_t next_fit_position;  /* For Next Fit algorithm */
    uint64_t total_free_blocks;
    uint32_t free_extent_count;
} free_space_manager_t;
 
/**
 * First Fit Allocation
 * 
 * Time Complexity: O(n) where n = number of free extents
 * Behavior: Allocates from the first hole that fits
 * Pros: Fast (stops at first match)
 * Cons: Fragments the beginning of the disk
 */
uint64_t allocate_first_fit(free_space_manager_t *mgr, uint32_t blocks_needed) {
    free_extent_t *current = mgr->free_list;
    free_extent_t *prev = NULL;
    
    while (current != NULL) {
        if (current->block_count >= blocks_needed) {
            /* Found a suitable hole */
            uint64_t allocated_start = current->start_block;
            
            if (current->block_count == blocks_needed) {
                /* Exact fit: remove this extent entirely */
                if (prev == NULL) {
                    mgr->free_list = current->next;
                } else {
                    prev->next = current->next;
                }
                mgr->free_extent_count--;
                /* free(current); -- Memory management */
            } else {
                /* Partial allocation: shrink this extent */
                current->start_block += blocks_needed;
                current->block_count -= blocks_needed;
            }
            
            mgr->total_free_blocks -= blocks_needed;
            return allocated_start;
        }
        
        prev = current;
        current = current->next;
    }
    
    return INVALID_BLOCK;  /* No suitable hole found */
}
 
/**
 * Best Fit Allocation
 * 
 * Time Complexity: O(n) - must scan entire list
 * Behavior: Finds the smallest hole that fits
 * Pros: Minimizes wasted space per allocation
 * Cons: Creates many tiny, useless fragments
 */
uint64_t allocate_best_fit(free_space_manager_t *mgr, uint32_t blocks_needed) {
    free_extent_t *current = mgr->free_list;
    free_extent_t *best = NULL;
    free_extent_t *best_prev = NULL;
    free_extent_t *prev = NULL;
    uint32_t best_size = UINT32_MAX;
    
    /* Scan entire list to find smallest sufficient hole */
    while (current != NULL) {
        if (current->block_count >= blocks_needed && 
            current->block_count < best_size) {
            best = current;
            best_prev = prev;
            best_size = current->block_count;
            
            /* Optimization: exact fit is optimal, stop early */
            if (best_size == blocks_needed) {
                break;
            }
        }
        
        prev = current;
        current = current->next;
    }
    
    if (best == NULL) {
        return INVALID_BLOCK;
    }
    
    uint64_t allocated_start = best->start_block;
    
    if (best->block_count == blocks_needed) {
        if (best_prev == NULL) {
            mgr->free_list = best->next;
        } else {
            best_prev->next = best->next;
        }
        mgr->free_extent_count--;
    } else {
        best->start_block += blocks_needed;
        best->block_count -= blocks_needed;
    }
    
    mgr->total_free_blocks -= blocks_needed;
    return allocated_start;
}
 
/**
 * Worst Fit Allocation
 * 
 * Time Complexity: O(n) - must scan entire list
 * Behavior: Finds the largest hole and allocates from it
 * Pros: Leaves larger remaining fragments
 * Cons: Quickly consumes large holes that might be needed
 */
uint64_t allocate_worst_fit(free_space_manager_t *mgr, uint32_t blocks_needed) {
    free_extent_t *current = mgr->free_list;
    free_extent_t *worst = NULL;
    free_extent_t *worst_prev = NULL;
    free_extent_t *prev = NULL;
    uint32_t worst_size = 0;
    
    while (current != NULL) {
        if (current->block_count >= blocks_needed && 
            current->block_count > worst_size) {
            worst = current;
            worst_prev = prev;
            worst_size = current->block_count;
        }
        
        prev = current;
        current = current->next;
    }
    
    if (worst == NULL) {
        return INVALID_BLOCK;
    }
    
    uint64_t allocated_start = worst->start_block;
    
    if (worst->block_count == blocks_needed) {
        if (worst_prev == NULL) {
            mgr->free_list = worst->next;
        } else {
            worst_prev->next = worst->next;
        }
        mgr->free_extent_count--;
    } else {
        worst->start_block += blocks_needed;
        worst->block_count -= blocks_needed;
    }
    
    mgr->total_free_blocks -= blocks_needed;
    return allocated_start;
}
 
/**
 * Next Fit Allocation
 * 
 * Time Complexity: O(n) worst case, but often faster in practice
 * Behavior: Like First Fit, but resumes from last allocation position
 * Pros: Distributes fragmentation evenly, often faster than First Fit
 * Cons: May miss good holes at the beginning of the list
 */
uint64_t allocate_next_fit(free_space_manager_t *mgr, uint32_t blocks_needed) {
    free_extent_t *current = mgr->free_list;
    free_extent_t *prev = NULL;
    bool wrapped = false;
    
    /* Skip to the next-fit starting position */
    while (current != NULL && 
           current->start_block < mgr->next_fit_position) {
        prev = current;
        current = current->next;
    }
    
    /* If we've gone past the list, wrap to beginning */
    if (current == NULL) {
        current = mgr->free_list;
        prev = NULL;
        wrapped = true;
    }
    
    free_extent_t *start = current;
    
    while (true) {
        if (current != NULL && current->block_count >= blocks_needed) {
            uint64_t allocated_start = current->start_block;
            
            /* Update next-fit position for future allocations */
            mgr->next_fit_position = allocated_start + blocks_needed;
            
            if (current->block_count == blocks_needed) {
                if (prev == NULL) {
                    mgr->free_list = current->next;
                } else {
                    prev->next = current->next;
                }
                mgr->free_extent_count--;
            } else {
                current->start_block += blocks_needed;
                current->block_count -= blocks_needed;
            }
            
            mgr->total_free_blocks -= blocks_needed;
            return allocated_start;
        }
        
        prev = current;
        current = (current != NULL) ? current->next : NULL;
        
        /* Wrap around to beginning */
        if (current == NULL && !wrapped) {
            current = mgr->free_list;
            prev = NULL;
            wrapped = true;
        }
        
        /* We've checked everything */
        if (current == start || (current == NULL && wrapped)) {
            break;
        }
    }
    
    return INVALID_BLOCK;
}

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

/*
 * Bitmap-Based Free Space Management
 * 
 * A bitmap is simple and efficient for contiguous allocation:
 * - Each bit represents one block
 * - Fast block status check: O(1)
 * - Finding contiguous space: O(n) scan
 */
 
#include <stdio.h>
#include <stdint.h>
#include <stdbool.h>
#include <string.h>
 
#define TOTAL_BLOCKS 1000000        /* 1 million blocks */
#define BITS_PER_WORD 64
#define BITMAP_SIZE ((TOTAL_BLOCKS + BITS_PER_WORD - 1) / BITS_PER_WORD)
 
typedef struct {
    uint64_t bitmap[BITMAP_SIZE];
    uint64_t total_blocks;
    uint64_t free_blocks;
} bitmap_allocator_t;
 
/* Initialize bitmap with all blocks free */
void bitmap_init(bitmap_allocator_t *alloc) {
    memset(alloc->bitmap, 0, sizeof(alloc->bitmap));
    alloc->total_blocks = TOTAL_BLOCKS;
    alloc->free_blocks = TOTAL_BLOCKS;
}
 
/* Check if a specific block is free */
static inline bool is_block_free(bitmap_allocator_t *alloc, uint64_t block) {
    uint64_t word_index = block / BITS_PER_WORD;
    uint64_t bit_index = block % BITS_PER_WORD;
    return (alloc->bitmap[word_index] & (1ULL << bit_index)) == 0;
}
 
/* Mark a block as allocated */
static inline void mark_allocated(bitmap_allocator_t *alloc, uint64_t block) {
    uint64_t word_index = block / BITS_PER_WORD;
    uint64_t bit_index = block % BITS_PER_WORD;
    alloc->bitmap[word_index] |= (1ULL << bit_index);
    alloc->free_blocks--;
}
 
/* Mark a block as free */
static inline void mark_free(bitmap_allocator_t *alloc, uint64_t block) {
    uint64_t word_index = block / BITS_PER_WORD;
    uint64_t bit_index = block % BITS_PER_WORD;
    alloc->bitmap[word_index] &= ~(1ULL << bit_index);
    alloc->free_blocks++;
}
 
/**
 * Find a contiguous region of free blocks using word-level optimization.
 * 
 * Key insight: If a bitmap word is all 1s (0xFFFFFFFFFFFFFFFF),
 * we know all 64 blocks in that word are allocated, so skip it entirely.
 */
uint64_t find_contiguous_blocks(
    bitmap_allocator_t *alloc, 
    uint32_t blocks_needed
) {
    uint64_t consecutive = 0;
    uint64_t start_block = 0;
    
    for (uint64_t block = 0; block < alloc->total_blocks; block++) {
        /* Word-level optimization: skip fully allocated words */
        if (block % BITS_PER_WORD == 0) {
            uint64_t word_idx = block / BITS_PER_WORD;
            if (alloc->bitmap[word_idx] == UINT64_MAX) {
                /* All 64 bits set = all allocated, skip entire word */
                consecutive = 0;
                continue;
            }
        }
        
        if (is_block_free(alloc, block)) {
            if (consecutive == 0) {
                start_block = block;
            }
            consecutive++;
            
            if (consecutive >= blocks_needed) {
                /* Found sufficient contiguous space! */
                /* Mark all blocks as allocated */
                for (uint64_t i = 0; i < blocks_needed; i++) {
                    mark_allocated(alloc, start_block + i);
                }
                return start_block;
            }
        } else {
            consecutive = 0;
        }
    }
    
    return UINT64_MAX;  /* Failed: no contiguous region found */
}
 
/**
 * Free a contiguous region (when file is deleted)
 */
void free_contiguous_blocks(
    bitmap_allocator_t *alloc,
    uint64_t start_block,
    uint32_t block_count
) {
    for (uint32_t i = 0; i < block_count; i++) {
        mark_free(alloc, start_block + i);
    }
}
 
/**
 * Fragmentation statistics
 */
typedef struct {
    uint32_t free_extent_count;     /* Number of free regions */
    uint64_t largest_extent;        /* Size of largest free region */
    uint64_t total_free_blocks;     /* Total free space */
    double fragmentation_ratio;     /* 1 - (largest / total) */
} fragmentation_stats_t;
 
void calculate_fragmentation(
    bitmap_allocator_t *alloc,
    fragmentation_stats_t *stats
) {
    stats->free_extent_count = 0;
    stats->largest_extent = 0;
    stats->total_free_blocks = 0;
    
    uint64_t current_extent = 0;
    
    for (uint64_t block = 0; block < alloc->total_blocks; block++) {
        if (is_block_free(alloc, block)) {
            current_extent++;
            stats->total_free_blocks++;
        } else {
            if (current_extent > 0) {
                stats->free_extent_count++;
                if (current_extent > stats->largest_extent) {
                    stats->largest_extent = current_extent;
                }
                current_extent = 0;
            }
        }
    }
    
    /* Handle trailing free extent */
    if (current_extent > 0) {
        stats->free_extent_count++;
        if (current_extent > stats->largest_extent) {
            stats->largest_extent = current_extent;
        }
    }
    
    /* Calculate fragmentation ratio */
    if (stats->total_free_blocks > 0) {
        stats->fragmentation_ratio = 
            1.0 - ((double)stats->largest_extent / stats->total_free_blocks);
    } else {
        stats->fragmentation_ratio = 0.0;
    }
}