Free Space Management

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

#include <stdint.h>
#include <stdbool.h>
 
/**
 * Linked List Free Space Manager
 * 
 * The free list is threaded through the free blocks themselves.
 * Each free block contains the block number of the next free block.
 */
 
#define NULL_BLOCK UINT64_MAX  // Sentinel for end of list
 
typedef struct {
    uint64_t head;          // First free block (NULL_BLOCK if empty)
    uint64_t free_count;    // Number of free blocks
    uint64_t block_size;    // Size of each block in bytes
    
    // Disk I/O functions (abstracted)
    void *disk_handle;
} LinkedListManager;
 
/**
 * Read the "next" pointer from a free block.
 * The pointer is stored at the start of the block.
 */
uint64_t read_next_pointer(LinkedListManager *llm, uint64_t block_num) {
    uint64_t next;
    // disk_read(llm->disk_handle, block_num * llm->block_size, &next, sizeof(next));
    return next;
}
 
/**
 * Write the "next" pointer into a free block.
 */
void write_next_pointer(LinkedListManager *llm, uint64_t block_num, uint64_t next) {
    // disk_write(llm->disk_handle, block_num * llm->block_size, &next, sizeof(next));
}
 
/**
 * Allocate a single block from the free list.
 * Time complexity: O(1) - just take from head
 * I/O operations: 1 read, 1 write (to persist new head)
 */
uint64_t ll_allocate(LinkedListManager *llm) {
    if (llm->head == NULL_BLOCK) {
        return NULL_BLOCK;  // No free blocks
    }
    
    // Remove from head of list
    uint64_t allocated_block = llm->head;
    
    // Read next pointer from the block we're allocating
    uint64_t next = read_next_pointer(llm, allocated_block);
    
    // Update head to next block
    llm->head = next;
    llm->free_count--;
    
    // Note: Must persist new head to superblock for crash consistency
    // persist_superblock(llm);
    
    return allocated_block;
}
 
/**
 * Free a block by adding it to the free list.
 * Time complexity: O(1) - just add to head
 */
bool ll_free(LinkedListManager *llm, uint64_t block_num) {
    // Write current head as this block's next
    write_next_pointer(llm, block_num, llm->head);
    
    // Update head to this block
    llm->head = block_num;
    llm->free_count++;
    
    // persist_superblock(llm);
    
    return true;
}
 
/**
 * Check if list is empty.
 * Time complexity: O(1)
 */
bool ll_is_empty(LinkedListManager *llm) {
    return llm->head == NULL_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

/**
 * Enhanced Linked List Free Space Manager
 * 
 * Stores additional metadata in free blocks:
 * - Next pointer
 * - Previous pointer (for doubly-linked)  
 * - Adjacent count (rudimentary extent tracking)
 * - Magic number (for crash recovery verification)
 */
 
#define FREE_BLOCK_MAGIC 0xDEADBEEFCAFEBABE
 
typedef struct __attribute__((packed)) {
    uint64_t magic;           // Verification that this is indeed a free block
    uint64_t next;            // Next free block
    uint64_t prev;            // Previous free block (for doubly-linked)
    uint32_t adjacent_count;  // Number of contiguous free blocks starting here
    uint32_t checksum;        // CRC32 of this header
} FreeBlockHeader;
 
typedef struct {
    uint64_t head;
    uint64_t tail;            // For O(1) append operations
    uint64_t free_count;
    uint64_t block_size;
    void *disk_handle;
} EnhancedLLManager;
 
/**
 * Read free block header
 */
FreeBlockHeader read_free_header(EnhancedLLManager *ellm, uint64_t block) {
    FreeBlockHeader hdr;
    // disk_read(ellm->disk_handle, block * ellm->block_size, &hdr, sizeof(hdr));
    return hdr;
}
 
/**
 * Write free block header
 */
void write_free_header(EnhancedLLManager *ellm, uint64_t block, FreeBlockHeader *hdr) {
    hdr->magic = FREE_BLOCK_MAGIC;
    hdr->checksum = compute_crc32(hdr, sizeof(*hdr) - sizeof(hdr->checksum));
    // disk_write(ellm->disk_handle, block * ellm->block_size, hdr, sizeof(*hdr));
}
 
/**
 * Verify block is actually free (crash recovery)
 */
bool verify_free_block(EnhancedLLManager *ellm, uint64_t block) {
    FreeBlockHeader hdr = read_free_header(ellm, block);
    
    if (hdr.magic != FREE_BLOCK_MAGIC) {
        return false;  // Not a free block (or corrupted)
    }
    
    uint32_t expected = compute_crc32(&hdr, sizeof(hdr) - sizeof(hdr.checksum));
    if (hdr.checksum != expected) {
        return false;  // Corrupted header
    }
    
    return true;
}
 
/**
 * Find contiguous blocks using adjacent_count optimization
 */
uint64_t find_contiguous(EnhancedLLManager *ellm, uint32_t needed) {
    uint64_t current = ellm->head;
    
    while (current != NULL_BLOCK) {
        FreeBlockHeader hdr = read_free_header(ellm, current);
        
        if (!verify_free_block(ellm, current)) {
            // Corrupted block - skip and potentially repair
            current = hdr.next;  // Hope next pointer is still valid
            continue;
        }
        
        if (hdr.adjacent_count >= needed) {
            // Found a run of sufficient size
            return current;
        }
        
        current = hdr.next;
    }
    
    return NULL_BLOCK;  // No contiguous region found
}
 
/**
 * Remove block from middle of doubly-linked list
 * Time complexity: O(1) assuming we have the block number
 */
void remove_from_list(EnhancedLLManager *ellm, uint64_t block) {
    FreeBlockHeader hdr = read_free_header(ellm, block);
    
    // Update previous block's next pointer
    if (hdr.prev != NULL_BLOCK) {
        FreeBlockHeader prev_hdr = read_free_header(ellm, hdr.prev);
        prev_hdr.next = hdr.next;
        write_free_header(ellm, hdr.prev, &prev_hdr);
    } else {
        ellm->head = hdr.next;
    }
    
    // Update next block's previous pointer
    if (hdr.next != NULL_BLOCK) {
        FreeBlockHeader next_hdr = read_free_header(ellm, hdr.next);
        next_hdr.prev = hdr.prev;
        write_free_header(ellm, hdr.next, &next_hdr);
    } else {
        ellm->tail = hdr.prev;
    }
    
    ellm->free_count--;
}

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

/**
 * Cached Free List Manager
 * 
 * Maintains an in-memory cache of free block numbers to minimize I/O.
 * Cache is periodically synchronized with on-disk linked list.
 */
 
#define CACHE_SIZE 1024
 
typedef struct {
    LinkedListManager *ll;     // Underlying linked list
    
    uint64_t cache[CACHE_SIZE]; // In-memory cache of free blocks
    size_t cache_count;         // Number of cached blocks
    size_t cache_low_water;     // Refill when below this
    size_t cache_high_water;    // Flush when above this
    
    bool dirty;                 // True if cache has unflushed changes
} CachedFreeList;
 
/**
 * Initialize cached free list
 */
CachedFreeList* cached_init(LinkedListManager *ll) {
    CachedFreeList *cfl = malloc(sizeof(CachedFreeList));
    cfl->ll = ll;
    cfl->cache_count = 0;
    cfl->cache_low_water = CACHE_SIZE / 4;
    cfl->cache_high_water = CACHE_SIZE * 3 / 4;
    cfl->dirty = false;
    
    // Pre-fill cache
    cached_refill(cfl);
    
    return cfl;
}
 
/**
 * Refill cache from linked list
 */
void cached_refill(CachedFreeList *cfl) {
    while (cfl->cache_count < CACHE_SIZE && !ll_is_empty(cfl->ll)) {
        uint64_t block = ll_allocate(cfl->ll);
        if (block != NULL_BLOCK) {
            cfl->cache[cfl->cache_count++] = block;
        }
    }
}
 
/**
 * Flush cache to linked list
 */
void cached_flush_some(CachedFreeList *cfl, size_t count) {
    while (count > 0 && cfl->cache_count > 0) {
        cfl->cache_count--;
        ll_free(cfl->ll, cfl->cache[cfl->cache_count]);
        count--;
    }
    cfl->dirty = (cfl->cache_count > 0);
}
 
/**
 * Allocate from cache (fast path)
 * Amortized O(1), minimal I/O
 */
uint64_t cached_allocate(CachedFreeList *cfl) {
    // Check if we need to refill
    if (cfl->cache_count <= cfl->cache_low_water) {
        cached_refill(cfl);
    }
    
    if (cfl->cache_count == 0) {
        return NULL_BLOCK;  // Truly out of space
    }
    
    // Pop from cache (LIFO - last one added is first out)
    cfl->cache_count--;
    cfl->dirty = true;
    return cfl->cache[cfl->cache_count];
}
 
/**
 * Free to cache (fast path)
 * O(1), no I/O unless cache is full
 */
bool cached_free(CachedFreeList *cfl, uint64_t block) {
    // Check if we need to flush
    if (cfl->cache_count >= cfl->cache_high_water) {
        cached_flush_some(cfl, CACHE_SIZE / 4);
    }
    
    // Add to cache
    cfl->cache[cfl->cache_count++] = block;
    cfl->dirty = true;
    
    return true;
}
 
/**
 * Sync all cached state to disk
 * Called on unmount and periodically for safety
 */
void cached_sync(CachedFreeList *cfl) {
    if (!cfl->dirty) return;
    
    // Flush all cached blocks back to linked list
    cached_flush_some(cfl, cfl->cache_count);
    
    // Persist superblock with updated head
    // persist_superblock(cfl->ll);
    
    cfl->dirty = false;
}

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

/**
 * FAT File System Simulation
 * 
 * Demonstrates how FAT uses a centralized table for both
 * file block chains and free space tracking.
 */
 
#define FAT_FREE        0x00000000
#define FAT_BAD         0x0FFFFFF7
#define FAT_EOF         0x0FFFFFF8
#define FAT_RESERVED    0x0FFFFFF0
 
typedef struct {
    uint32_t *fat;           // The File Allocation Table
    uint32_t total_clusters; // Total data clusters
    uint32_t free_count;     // Cached free count
    uint32_t next_free_hint; // Hint for faster allocation
} FATManager;
 
/**
 * Initialize FAT - mark all clusters as free
 */
FATManager* fat_create(uint32_t cluster_count) {
    FATManager *fm = malloc(sizeof(FATManager));
    fm->total_clusters = cluster_count;
    fm->fat = malloc(cluster_count * sizeof(uint32_t));
    
    // First two entries are reserved
    fm->fat[0] = FAT_RESERVED;
    fm->fat[1] = FAT_RESERVED;
    
    // Rest start as free
    for (uint32_t i = 2; i < cluster_count; i++) {
        fm->fat[i] = FAT_FREE;
    }
    
    fm->free_count = cluster_count - 2;
    fm->next_free_hint = 2;
    
    return fm;
}
 
/**
 * Find a free cluster using next-fit strategy
 */
uint32_t fat_find_free(FATManager *fm) {
    if (fm->free_count == 0) return 0;  // 0 indicates failure
    
    uint32_t start = fm->next_free_hint;
    uint32_t current = start;
    
    do {
        if (fm->fat[current] == FAT_FREE) {
            fm->next_free_hint = current + 1;
            return current;
        }
        current++;
        if (current >= fm->total_clusters) current = 2;  // Wrap
    } while (current != start);
    
    return 0;  // No free cluster found
}
 
/**
 * Allocate a chain of clusters for a new file
 */
uint32_t fat_allocate_chain(FATManager *fm, uint32_t count) {
    if (count == 0 || count > fm->free_count) return 0;
    
    uint32_t first = 0;
    uint32_t prev = 0;
    
    for (uint32_t i = 0; i < count; i++) {
        uint32_t cluster = fat_find_free(fm);
        if (cluster == 0) {
            // Out of space - free what we allocated
            if (first != 0) fat_free_chain(fm, first);
            return 0;
        }
        
        if (first == 0) {
            first = cluster;
        } else {
            // Link previous cluster to this one
            fm->fat[prev] = cluster;
        }
        
        fm->fat[cluster] = FAT_EOF;  // Mark as end (for now)
        fm->free_count--;
        prev = cluster;
    }
    
    return first;  // Return first cluster of chain
}
 
/**
 * Free an entire cluster chain
 */
void fat_free_chain(FATManager *fm, uint32_t start) {
    uint32_t current = start;
    
    while (current >= 2 && current < fm->total_clusters) {
        uint32_t next = fm->fat[current];
        
        fm->fat[current] = FAT_FREE;
        fm->free_count++;
        
        if (next >= FAT_EOF) {
            break;  // End of chain
        }
        current = next;
    }
}
 
/**
 * Extend an existing chain by adding more clusters
 */
bool fat_extend_chain(FATManager *fm, uint32_t end_cluster, uint32_t add_count) {
    // Verify end_cluster is actually end of a chain
    if (fm->fat[end_cluster] < FAT_EOF) {
        return false;  // Not end of chain
    }
    
    for (uint32_t i = 0; i < add_count; i++) {
        uint32_t new_cluster = fat_find_free(fm);
        if (new_cluster == 0) return false;
        
        fm->fat[end_cluster] = new_cluster;
        fm->fat[new_cluster] = FAT_EOF;
        fm->free_count--;
        end_cluster = new_cluster;
    }
    
    return true;
}
 
/**
 * Walk a cluster chain (for reading a file)
 */
void fat_walk_chain(FATManager *fm, uint32_t start, 
                    void (*callback)(uint32_t cluster, void *ctx), 
                    void *ctx) {
    uint32_t current = start;
    
    while (current >= 2 && current < FAT_RESERVED) {
        callback(current, ctx);
        current = fm->fat[current];
    }
}

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

/**
 * Ordered Free List with Coalescing
 * 
 * Maintains blocks in sorted order by block number.
 * Automatically merges adjacent free blocks.
 */
 
typedef struct FreeNode {
    uint64_t start_block;   // First block in this extent
    uint64_t block_count;   // Number of contiguous blocks
    struct FreeNode *next;  // Next extent in sorted order
} FreeNode;
 
typedef struct {
    FreeNode *head;
    uint64_t total_free;
} OrderedFreeList;
 
/**
 * Free a block with automatic coalescing
 */
void ordered_free(OrderedFreeList *ofl, uint64_t block) {
    FreeNode *prev = NULL;
    FreeNode *current = ofl->head;
    
    // Find insertion point (sorted by start_block)
    while (current && current->start_block < block) {
        prev = current;
        current = current->next;
    }
    
    // Check if we can coalesce with previous extent
    bool merged_prev = false;
    if (prev && prev->start_block + prev->block_count == block) {
        prev->block_count++;
        merged_prev = true;
        ofl->total_free++;
    }
    
    // Check if we can coalesce with next extent
    if (current && block + 1 == current->start_block) {
        if (merged_prev) {
            // Merge all three: prev absorbs block and current
            prev->block_count += current->block_count;
            prev->next = current->next;
            free(current);
        } else {
            // Extend current backward
            current->start_block = block;
            current->block_count++;
            ofl->total_free++;
        }
        return;
    }
    
    // If merged with prev, we're done
    if (merged_prev) return;
    
    // Create new node for this single block
    FreeNode *new_node = malloc(sizeof(FreeNode));
    new_node->start_block = block;
    new_node->block_count = 1;
    new_node->next = current;
    
    if (prev) {
        prev->next = new_node;
    } else {
        ofl->head = new_node;
    }
    
    ofl->total_free++;
}
 
/**
 * Allocate contiguous blocks - efficient due to extent tracking
 */
uint64_t ordered_alloc_contiguous(OrderedFreeList *ofl, uint64_t count) {
    FreeNode *prev = NULL;
    FreeNode *current = ofl->head;
    
    // First-fit search for extent of sufficient size
    while (current) {
        if (current->block_count >= count) {
            uint64_t result = current->start_block;
            
            if (current->block_count == count) {
                // Exact fit - remove node entirely
                if (prev) {
                    prev->next = current->next;
                } else {
                    ofl->head = current->next;
                }
                free(current);
            } else {
                // Partial allocation - shrink extent
                current->start_block += count;
                current->block_count -= count;
            }
            
            ofl->total_free -= count;
            return result;
        }
        
        prev = current;
        current = current->next;
    }
    
    return NULL_BLOCK;  // No sufficient contiguous region
}