7a:T4a2,A **bit vector** is a compact data structure that uses exactly one bit to represent the state of each disk block. The concept is beautifully simple: - **Bit = 0**: The corresponding block is **allocated** (in use) - **Bit = 1**: The corresponding block is **free** (available) *Note: Some file systems use the opposite convention (0 = free, 1 = allocated). The choice is arbitrary but must be consistent.* The bits are organized sequentially, with bit position directly corresponding to block number: ``` Bit Vector: [1][0][0][1][1][1][0][0][1][0][1][1]... Block #: 0 1 2 3 4 5 6 7 8 9 10 11 Interpretation: - Block 0: free (bit = 1) - Block 1: allocated (bit = 0) - Block 2: allocated (bit = 0) - Block 3: free (bit = 1) - Blocks 4,5: free - Blocks 6,7: allocated - And so on... ``` **Mathematical Representation**: For a disk with *n* blocks, the bit vector is an array of ⌈n/8⌉ bytes (since each byte contains 8 bits). The mapping from block number to bit position is: ``` byte_index = block_number / 8 (integer division) bit_offset = block_number % 8 (modulo/remainder) ``` To check if block *b* is free: ``` is_free = (bitmap[b / 8] >> (b % 8)) & 1 ```7b:Ta88,#include #include #include #include /** * Bitmap Free Space Manager * * Convention: bit = 1 means FREE, bit = 0 means ALLOCATED * This allows using hardware instructions to find first set bit. */ typedef struct { uint8_t *bitmap; // The actual bit vector uint64_t total_blocks; // Total number of blocks managed uint64_t free_count; // Number of free blocks (cached for O(1) queries) uint64_t bitmap_size; // Size of bitmap in bytes } BitmapManager; /** * Initialize a bitmap manager for a given number of blocks. * All blocks start as FREE. */ BitmapManager* bitmap_create(uint64_t total_blocks) { BitmapManager *bm = malloc(sizeof(BitmapManager)); if (!bm) return NULL; bm->total_blocks = total_blocks; bm->free_count = total_blocks; // Calculate bitmap size: ceiling division to get bytes needed bm->bitmap_size = (total_blocks + 7) / 8; // Allocate and initialize all bits to 1 (all blocks free) bm->bitmap = malloc(bm->bitmap_size); if (!bm->bitmap) { free(bm); return NULL; } memset(bm->bitmap, 0xFF, bm->bitmap_size); // Clear any extra bits in the last byte if total_blocks % 8 != 0 uint64_t extra_bits = (8 - (total_blocks % 8)) % 8; if (extra_bits > 0) { bm->bitmap[bm->bitmap_size - 1] &= (0xFF >> extra_bits); } return bm; } /** * Check if a specific block is free. * Time complexity: O(1) */ bool bitmap_is_free(BitmapManager *bm, uint64_t block_num) { if (block_num >= bm->total_blocks) return false; uint64_t byte_index = block_num / 8; uint8_t bit_offset = block_num % 8; return (bm->bitmap[byte_index] >> bit_offset) & 1; } /** * Mark a block as allocated. * Time complexity: O(1) */ bool bitmap_allocate(BitmapManager *bm, uint64_t block_num) { if (block_num >= bm->total_blocks) return false; if (!bitmap_is_free(bm, block_num)) return false; uint64_t byte_index = block_num / 8; uint8_t bit_offset = block_num % 8; // Clear the bit (set to 0 = allocated) bm->bitmap[byte_index] &= ~(1 << bit_offset); bm->free_count--; return true; } /** * Mark a block as free. * Time complexity: O(1) */ bool bitmap_free(BitmapManager *bm, uint64_t block_num) { if (block_num >= bm->total_blocks) return false; if (bitmap_is_free(bm, block_num)) return false; // Already free uint64_t byte_index = block_num / 8; uint8_t bit_offset = block_num % 8; // Set the bit (set to 1 = free) bm->bitmap[byte_index] |= (1 << bit_offset); bm->free_count++; return true; }7c:T4e8,The most critical operation for a bitmap is **finding free blocks** to satisfy allocation requests. The simplest approach is a **sequential scan** through the bitmap, but this naive implementation can be dramatically optimized. **Basic Algorithm**: 1. Start scanning from position 0 (or a cached position) 2. Check each bit until we find a free block (bit = 1) 3. Return the block number **Naive Implementation Complexity**: O(n) where n is the total number of blocks. For a 1TB drive with 268 million blocks, scanning bit-by-bit in the worst case would require checking 268 million bits—clearly unacceptable for real-time allocation. **Word-at-a-Time Optimization**: Instead of checking individual bits, we can check entire bytes or machine words at once: ``` Optimization 1: Check entire byte - If byte == 0x00, all 8 blocks are allocated → skip to next byte - If byte != 0x00, at least one block is free → find it within the byte Optimization 2: Check entire 64-bit word - If word == 0, all 64 blocks are allocated → skip 64 blocks at once - If word != 0, find first set bit using CPU instruction ``` This transforms worst-case complexity from O(n) bit operations to O(n/64) word operations—a 64× improvement on 64-bit architectures.7d:T9ae,#include #include /** * Find the first free block starting from a given position. * Uses word-at-a-time scanning for efficiency. * * Returns: block number of first free block, or UINT64_MAX if none found. * Time complexity: O(n/64) word operations in worst case */ uint64_t bitmap_find_first_free(BitmapManager *bm, uint64_t start_block) { if (bm->free_count == 0) return UINT64_MAX; // Quick check uint64_t current = start_block; // Phase 1: Align to word boundary (check individual bytes) while (current < bm->total_blocks && (current % 64) != 0) { if (bitmap_is_free(bm, current)) { return current; } current++; } // Phase 2: Scan 64-bit words at a time uint64_t *word_ptr = (uint64_t *)(bm->bitmap + current / 8); uint64_t word_index = current / 64; uint64_t total_words = (bm->total_blocks + 63) / 64; while (word_index < total_words) { uint64_t word = *word_ptr; if (word != 0) { // Found a word with at least one free block // Use built-in to find first set bit (GCC/Clang) int bit_pos = __builtin_ctzll(word); // Count trailing zeros uint64_t block = word_index * 64 + bit_pos; if (block < bm->total_blocks) { return block; } } word_ptr++; word_index++; } // Phase 3: Wrap around to beginning if we started mid-bitmap if (start_block > 0) { return bitmap_find_first_free(bm, 0); // Could also use iteration } return UINT64_MAX; // No free blocks found } /** * Find N contiguous free blocks. * Essential for pre-allocating space for sequential files. * * Returns: starting block number, or UINT64_MAX if not found. */ uint64_t bitmap_find_contiguous(BitmapManager *bm, uint64_t count, uint64_t start) { if (count == 0 || count > bm->free_count) return UINT64_MAX; uint64_t run_start = UINT64_MAX; uint64_t run_length = 0; for (uint64_t i = start; i < bm->total_blocks && run_length < count; i++) { if (bitmap_is_free(bm, i)) { if (run_start == UINT64_MAX) { run_start = i; } run_length++; } else { run_start = UINT64_MAX; run_length = 0; } } return (run_length >= count) ? run_start : UINT64_MAX; }7e:T42b,Simply finding *any* free block is often insufficient. File systems employ sophisticated strategies to choose *which* free blocks to allocate, optimizing for different goals: **First-Fit Allocation**: Allocate the first free block found during a sequential scan. This is simple and reasonably fast, but can lead to fragmentation as small free regions accumulate at the beginning of the disk. **Next-Fit Allocation**: Start scanning from where the last allocation ended rather than from the beginning. This distributes allocations more evenly across the disk and avoids repeatedly scanning allocated regions at the start. **Best-Fit for Contiguous Allocation**: When allocating contiguous extents, find the smallest free region that can satisfy the request. This minimizes fragmentation but requires tracking region sizes—expensive with a simple bitmap. **Locality-Based Allocation**: Allocate blocks physically close to related blocks. For example, when extending a file, prefer blocks near the file's existing blocks to improve sequential read performance.7f:Td1f,/** * Extended Bitmap Manager with allocation strategies */ typedef struct { BitmapManager base; uint64_t next_fit_position; // For next-fit allocation uint64_t recently_freed_hint; // Hint for recently freed regions } ExtendedBitmapManager; /** * Next-Fit allocation: start from last allocation position */ uint64_t bitmap_alloc_next_fit(ExtendedBitmapManager *ebm) { uint64_t block = bitmap_find_first_free(&ebm->base, ebm->next_fit_position); if (block == UINT64_MAX && ebm->next_fit_position > 0) { // Wrap around to beginning block = bitmap_find_first_free(&ebm->base, 0); } if (block != UINT64_MAX) { bitmap_allocate(&ebm->base, block); ebm->next_fit_position = block + 1; } return block; } /** * Locality-aware allocation: prefer blocks near target */ uint64_t bitmap_alloc_near(ExtendedBitmapManager *ebm, uint64_t target, uint64_t radius) { // Search in expanding circles around target for (uint64_t offset = 0; offset <= radius; offset++) { // Check block after target if (target + offset < ebm->base.total_blocks) { if (bitmap_is_free(&ebm->base, target + offset)) { bitmap_allocate(&ebm->base, target + offset); return target + offset; } } // Check block before target if (offset > 0 && target >= offset) { if (bitmap_is_free(&ebm->base, target - offset)) { bitmap_allocate(&ebm->base, target - offset); return target - offset; } } } // Fall back to next-fit if locality search fails return bitmap_alloc_next_fit(ebm); } /** * Bulk allocation for large files * Tries to allocate contiguous blocks for better performance */ typedef struct { uint64_t *blocks; // Array of allocated block numbers uint64_t count; // Number of blocks actually allocated bool contiguous; // True if all blocks are contiguous } AllocationResult; AllocationResult bitmap_alloc_bulk(ExtendedBitmapManager *ebm, uint64_t requested_count) { AllocationResult result = {NULL, 0, false}; if (requested_count > ebm->base.free_count) { return result; // Not enough space } result.blocks = malloc(requested_count * sizeof(uint64_t)); if (!result.blocks) return result; // First, try to find contiguous region uint64_t contig_start = bitmap_find_contiguous(&ebm->base, requested_count, ebm->next_fit_position); if (contig_start != UINT64_MAX) { // Allocate contiguous region for (uint64_t i = 0; i < requested_count; i++) { result.blocks[i] = contig_start + i; bitmap_allocate(&ebm->base, contig_start + i); } result.count = requested_count; result.contiguous = true; ebm->next_fit_position = contig_start + requested_count; } else { // Fall back to scattered allocation for (uint64_t i = 0; i < requested_count; i++) { uint64_t block = bitmap_alloc_next_fit(ebm); if (block == UINT64_MAX) break; result.blocks[i] = block; result.count++; } result.contiguous = false; } return result; }80:Tf1a,Large file systems don't maintain a single monolithic bitmap. Instead, they partition the disk into **block groups** (or *allocation groups*), each with its own bitmap and metadata. This design, pioneered by the ext2 file system and adopted across numerous modern file systems, provides several crucial advantages. **The Block Group Architecture**: ``` ┌─────────────────────────────────────────────────────────────────────┐ │ ENTIRE DISK │ ├─────────────┬─────────────┬─────────────┬─────────────┬─────────────┤ │ Block │ Block │ Block │ Block │ Block │ │ Group 0 │ Group 1 │ Group 2 │ Group 3 │ Group N │ ├─────────────┼─────────────┼─────────────┼─────────────┼─────────────┤ │ ┌─────────┐ │ ┌─────────┐ │ ┌─────────┐ │ ┌─────────┐ │ ┌─────────┐ │ │ │SuperBlk │ │ │Group Dsc│ │ │Group Dsc│ │ │Group Dsc│ │ │Group Dsc│ │ │ ├─────────┤ │ ├─────────┤ │ ├─────────┤ │ ├─────────┤ │ ├─────────┤ │ │ │BlkBitmap│ │ │BlkBitmap│ │ │BlkBitmap│ │ │BlkBitmap│ │ │BlkBitmap│ │ │ ├─────────┤ │ ├─────────┤ │ ├─────────┤ │ ├─────────┤ │ ├─────────┤ │ │ │InodeBmp │ │ │InodeBmp │ │ │InodeBmp │ │ │InodeBmp │ │ │InodeBmp │ │ │ ├─────────┤ │ ├─────────┤ │ ├─────────┤ │ ├─────────┤ │ ├─────────┤ │ │ │InodeTbl │ │ │InodeTbl │ │ │InodeTbl │ │ │InodeTbl │ │ │InodeTbl │ │ │ ├─────────┤ │ ├─────────┤ │ ├─────────┤ │ ├─────────┤ │ ├─────────┤ │ │ │ Data │ │ │ Data │ │ │ Data │ │ │ Data │ │ │ Data │ │ │ │ Blocks │ │ │ Blocks │ │ │ Blocks │ │ │ Blocks │ │ │ Blocks │ │ │ └─────────┘ │ └─────────┘ │ └─────────┘ │ └─────────┘ │ └─────────┘ │ └─────────────┴─────────────┴─────────────┴─────────────┴─────────────┘ ``` **Benefits of Block Groups**: 1. **Parallelism**: Different block groups can be allocated independently, enabling concurrent allocation operations across multiple CPU cores. 2. **Locality**: Files can be allocated within a single block group, keeping all file data and metadata physically close together on disk. 3. **Smaller Bitmaps**: Each bitmap is small enough to fit in a single disk block, reducing I/O for bitmap operations. 4. **Fault Isolation**: Corruption in one block group's bitmap doesn't affect other groups. 5. **Efficient Caching**: Only active block groups' bitmaps need to be cached in memory.81:T621,A bitmap is only as reliable as the file system's ability to maintain it consistently across system crashes and power failures. Without proper crash consistency mechanisms, a crash during allocation could leave blocks marked as allocated but not actually used (leaked space), or worse, marked as free but actually containing data (silent data corruption). **The Crash Consistency Problem**: Consider allocating a new block for a file—this requires multiple updates: 1. Find free block in bitmap 2. Mark block as allocated in bitmap 3. Write data to the block 4. Update file's metadata to reference the block If a crash occurs between steps 2 and 4: - The block is marked allocated in the bitmap - But no file references it - Result: **space leak** (block is "lost" forever) If crash occurs between steps 3 and 2 (if order reversed): - The block contains data - But bitmap still shows it as free - Result: **data corruption** (block may be reallocated and overwritten) **Journaling to the Rescue**: Modern file systems use **journaling** to ensure atomic updates. Before modifying the actual bitmap, the intended changes are written to a **journal** (also called a *log*): ``` 1. Write to journal: "Intent: allocate block 12345 for inode 67" 2. Write journal commit record 3. Modify actual bitmap 4. Modify actual inode 5. Mark journal entry as complete ``` If a crash occurs: - Before step 2: Journal entry incomplete, changes discarded - After step 2, before step 5: Replay journal to complete updates - After step 5: Changes already applied, nothing to do82:Tcee,/** * Journaled bitmap allocation - simplified pseudocode * Demonstrates the transaction-based approach to crash consistency */ typedef struct { uint32_t transaction_id; enum { TXN_ALLOC, TXN_FREE } operation; uint64_t block_num; uint64_t inode_num; // For tracking which file owns the block } JournalEntry; typedef struct { JournalEntry *entries; size_t count; bool committed; } Transaction; /** * Allocate blocks within a transaction (journaled allocation) */ bool bitmap_alloc_journaled(ExtendedBitmapManager *ebm, Journal *journal, uint64_t inode_num, uint64_t *blocks, size_t count) { // Begin transaction Transaction *txn = journal_begin_transaction(journal); // Phase 1: Find and tentatively reserve blocks for (size_t i = 0; i < count; i++) { uint64_t block = bitmap_find_first_free(&ebm->base, ebm->next_fit_position); if (block == UINT64_MAX) { journal_abort_transaction(txn); return false; } blocks[i] = block; // Mark allocated in memory (not yet on disk!) bitmap_allocate(&ebm->base, block); // Record in journal journal_add_entry(txn, (JournalEntry){ .operation = TXN_ALLOC, .block_num = block, .inode_num = inode_num }); } // Phase 2: Commit transaction to journal (write to disk) // After this point, changes are guaranteed to be recoverable if (!journal_commit_transaction(txn)) { // Commit failed - rollback in-memory changes for (size_t i = 0; i < count; i++) { bitmap_free(&ebm->base, blocks[i]); } return false; } // Phase 3: Write actual bitmap blocks to disk // These can be written lazily - journal ensures recoverability bitmap_sync_to_disk(ebm); // Phase 4: Mark transaction as checkpointed (complete) journal_checkpoint_transaction(txn); return true; } /** * Recovery after crash - replay uncommitted journal entries */ void bitmap_recover_from_journal(ExtendedBitmapManager *ebm, Journal *journal) { // Scan journal for committed but not checkpointed transactions Transaction *pending = journal_find_pending(journal); while (pending) { printf("Recovering transaction %u... ", pending->entries[0].transaction_id); for (size_t i = 0; i < pending->count; i++) { JournalEntry *entry = &pending->entries[i]; if (entry->operation == TXN_ALLOC) { // Ensure block is marked allocated if (bitmap_is_free(&ebm->base, entry->block_num)) { bitmap_allocate(&ebm->base, entry->block_num); } } else { // TXN_FREE // Ensure block is marked free if (!bitmap_is_free(&ebm->base, entry->block_num)) { bitmap_free(&ebm->base, entry->block_num); } } } journal_checkpoint_transaction(pending); pending = journal_find_pending(journal); } printf("Journal recovery complete. "); }83:T619,Let's examine how production file systems implement bitmap-based free space management, focusing on the specific optimizations and design decisions they employ. **ext4 (Linux)**: ext4 uses a classic block group structure with one bitmap block per group. Key features: - **Flexible block groups**: Can pack multiple group descriptors in one block for larger file systems - **Uninit block bitmap optimization**: Groups with uninitialized bitmaps are marked specially, allowing lazy initialization - **Preallocation**: Reserves contiguous blocks for files that are expected to grow - **Multi-block allocator (mballoc)**: Sophisticated allocator that delays allocations to batch them for better contiguity **XFS (Linux)**: XFS takes a different approach with *Allocation Groups* (AGs) and *B+ tree* free space indexes: - **Dual B+ trees per AG**: One sorted by block number, one by block count, enabling fast lookup for both location-based and size-based queries - **Free space extent tracking**: Rather than bit-per-block, tracks extents (start, length) of free regions - **Delayed allocation**: Allocates logical extents immediately but defers physical block assignment until writeback **NTFS (Windows)**: NTFS stores its bitmap as a special system file called **$Bitmap**: - **Standard file representation**: Bitmap is a regular file with its own MFT (Master File Table) entry - **Fragmentation allowed**: Unlike ext4's single-block bitmaps, NTFS bitmap can be fragmented - **Cached aggressively**: Windows keeps bitmap in memory and uses lazy writeback72:{"json":{"id":"seed_6e100337a3ea3831e1260a56737b7957","slug":"free-space-management","category":"Operating Systems","topic":"File System Implementation","title":"Free Space Management","description":"Master the fundamental techniques for tracking and allocating free disk space in file systems. Explore bit vectors, linked lists, grouping, counting, and space maps—the core algorithms that enable efficient storage utilization.","difficulty":"INTERMEDIATE","estimatedMinutes":75,"pages":[{"id":"seed_f2dc5e9871ec64f85660aa976f966fff","title":"Bit Vector (Bitmap)","order":0,"content":[{"id":"opening-hook","title":"The Art of Tracking Empty Space","content":[{"data":{"content":"Every file system faces a fundamental bookkeeping challenge: with potentially billions of storage blocks on a modern device, how does the operating system efficiently track which blocks are free and which are allocated? The answer to this question profoundly impacts file system performance, storage efficiency, and the system's ability to recover from failures.\n\n**The bit vector**, also known as a **bit map** or **bitmap**, represents one of computing's most elegant solutions to this problem. By dedicating just one bit per block, a bitmap can represent the allocation status of an entire storage device with remarkable space efficiency and lightning-fast operations.\n\nThis technique is so effective that it forms the backbone of free space management in virtually every major file system, from ext4 and XFS on Linux to NTFS on Windows to APFS on Apple devices. Understanding bitmap-based allocation is essential for anyone seeking to comprehend how modern storage systems actually work at the implementation level."},"type":"text"},{"data":{"icon":"Target","title":"What You Will Learn","content":"By the end of this page, you will understand how bit vectors represent free space, the mathematical foundations of bitmap allocation, the detailed algorithms for finding and allocating free blocks, performance characteristics across different workloads, and the real-world implementation strategies used by production file systems.","variant":"info"},"type":"callout"}]},{"id":"free-space-problem","title":"The Free Space Problem","content":[{"data":{"content":"Before diving into bit vectors specifically, we must understand the broader problem they solve. When a file system formats a storage device, it divides the raw storage capacity into fixed-size units called **blocks** (typically 4KB in modern systems, though sizes can range from 512 bytes to 64KB or more).\n\nConsider a moderately-sized 1TB SSD with 4KB blocks:\n\n```\nTotal capacity: 1,099,511,627,776 bytes (1 TB)\nBlock size: 4,096 bytes (4 KB)\nTotal blocks: 268,435,456 blocks (~268 million blocks)\n```\n\nThe file system must answer two critical questions efficiently:\n\n1. **Allocation query**: When creating or extending a file, which blocks are available?\n2. **Deallocation update**: When deleting a file, how do we mark its blocks as free?\n\nThe challenge is that these operations happen constantly—modern systems may perform thousands of file operations per second—so the free space tracking mechanism must be exceptionally fast while also being recoverable after system crashes."},"type":"text"},{"data":{"icon":"Info","title":"Design Requirements for Free Space Management","content":"An effective free space management system must satisfy multiple requirements: constant-time or near-constant-time operations for common cases, minimal storage overhead, ability to find contiguous free regions for sequential files, crash consistency (recovering correct state after power failure), and scalability to devices with billions of blocks.","variant":"note"},"type":"callout"},{"data":{"rows":[["Bit Vector","1 bit/block","O(n) scan, optimizable","Excellent","Good with journaling"],["Linked List","1 pointer/free block","O(1) head allocation","Poor","Complex"],["Grouping","Variable","O(1) to O(n)","Moderate","Moderate"],["Counting","Variable","O(1) to O(n)","Excellent","Moderate"],["Space Maps (ZFS)","Complex","O(1) amortized","Excellent","Excellent"]],"caption":"Free Space Management Trade-offs","headers":["Approach","Space Overhead","Allocation Speed","Contiguity Support","Crash Recovery"]},"type":"table"}],"titleType":"number","titleNumber":1},{"id":"bit-vector-fundamentals","title":"Bit Vector Fundamentals","content":[{"data":{"content":"$7a"},"type":"text"},{"data":{"fileName":"bitmap_fundamentals.c","languages":[{"code":"$7b","label":"C","value":"c"}]},"type":"code"}],"titleType":"number","titleNumber":2},{"id":"space-efficiency","title":"Space Efficiency Analysis","content":[{"data":{"content":"One of the bitmap's most compelling advantages is its exceptional space efficiency. Let's analyze the overhead for various storage device sizes:\n\n**Overhead Calculation**:\n\nFor a device with *n* blocks, the bitmap requires exactly *n* bits = *n/8* bytes.\n\nThe **overhead ratio** is:\n```\noverhead_ratio = bitmap_size / total_storage\n = (n/8) / (n × block_size)\n = 1 / (8 × block_size)\n```\n\nFor 4KB blocks:\n```\noverhead_ratio = 1 / (8 × 4096) = 1 / 32,768 ≈ 0.003%\n```\n\nThis means **less than 1 byte of overhead for every 32KB of storage**—an incredibly efficient representation."},"type":"text"},{"data":{"rows":[["1 GB","262,144","32 KB","0.003%"],["100 GB","26,214,400","3.125 MB","0.003%"],["1 TB","268,435,456","32 MB","0.003%"],["10 TB","2,684,354,560","320 MB","0.003%"],["100 TB","26,843,545,600","3.125 GB","0.003%"],["1 PB","268,435,456,000","31.25 GB","0.003%"]],"caption":"Bitmap Size for Common Storage Capacities (4KB blocks)","headers":["Storage Size","Total Blocks","Bitmap Size","Overhead %"]},"type":"table"},{"data":{"icon":"Lightbulb","title":"Memory Residency Strategy","content":"For typical server storage (1-10 TB), the entire bitmap is only 32-320 MB. Modern systems can keep this entirely in RAM, enabling constant-time allocation checks without any disk I/O. This is a crucial optimization—even for very large file systems, the bitmap is small enough to cache effectively.","variant":"tip"},"type":"callout"},{"data":{"content":"**Block Size Impact**:\n\nThe block size choice significantly affects both the bitmap size and the minimum allocation granularity:"},"type":"text"},{"data":{"rows":[["512 B","2.2 billion","256 MB","256 B average"],["4 KB","268 million","32 MB","2 KB average"],["64 KB","16.8 million","2 MB","32 KB average"]],"headers":["Block Size","Blocks per TB","Bitmap per TB","Min Allocation Waste"]},"type":"table"},{"data":{"content":"Larger block sizes reduce bitmap overhead but increase *internal fragmentation* (wasted space within allocated blocks for small files). The 4KB block size represents a widely-adopted compromise that balances these concerns."},"type":"text"}],"titleType":"number","titleNumber":3},{"id":"finding-free-blocks","title":"Finding Free Blocks: Sequential Scan","content":[{"data":{"content":"$7c"},"type":"text"},{"data":{"fileName":"bitmap_find_free.c","languages":[{"code":"$7d","label":"C","value":"c"}]},"type":"code"},{"data":{"icon":"Info","title":"Hardware Bit Manipulation Instructions","content":"Modern CPUs provide specialized instructions for bit manipulation: **BSF/BSR** (Bit Scan Forward/Reverse) on x86, **CLZ/CTZ** (Count Leading/Trailing Zeros) operations, and **POPCNT** (Population Count) for counting set bits. These execute in a single CPU cycle, making bitmap operations extremely fast. The GCC/Clang intrinsics __builtin_ctzll, __builtin_ffsll, and __builtin_popcountll map directly to these instructions.","variant":"note"},"type":"callout"}],"titleType":"number","titleNumber":4},{"id":"allocation-strategies","title":"Allocation Strategies","content":[{"data":{"content":"$7e"},"type":"text"},{"data":{"left":[{"data":{"items":["Simple to implement","Consistent starting point aids caching","Works well for uniform allocation patterns","Minimal state to maintain"],"title":{"icon":"CheckCircle","text":"First-Fit Advantages","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"}],"right":[{"data":{"items":["Distributes wear evenly (important for SSDs)","Avoids hotspots in bitmap scanning","Better for mixed workloads","Only requires one pointer to maintain"],"title":{"icon":"CheckCircle","text":"Next-Fit Advantages","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"}]},"type":"two-column"},{"data":{"fileName":"allocation_strategies.c","languages":[{"code":"$7f","label":"C","value":"c"}]},"type":"code"}],"titleType":"number","titleNumber":5},{"id":"block-group-organization","title":"Block Group Organization","content":[{"data":{"content":"$80"},"type":"text"},{"data":{"rows":[["1 KB","8,192","8 MB","1 KB (1 block)"],["2 KB","16,384","32 MB","2 KB (1 block)"],["4 KB","32,768","128 MB","4 KB (1 block)"],["64 KB","524,288","32 GB","64 KB (1 block)"]],"caption":"Block Group Sizing in ext4","headers":["Block Size","Blocks per Group","Group Size","Bitmap Size"]},"type":"table"},{"data":{"icon":"Lightbulb","title":"Why One Block per Bitmap?","content":"Sizing block groups so each bitmap fits in exactly one disk block is deliberate. It means reading or writing a bitmap is always a single I/O operation—no partial block reads or read-modify-write cycles. For 4KB blocks: 1 block × 8 bits/byte × 4096 bytes = 32,768 bits = 32,768 blocks per group × 4KB = 128 MB per group.","variant":"tip"},"type":"callout"}],"titleType":"number","titleNumber":6},{"id":"crash-consistency","title":"Crash Consistency and Journaling","content":[{"data":{"content":"$81"},"type":"text"},{"data":{"fileName":"bitmap_journaled.c","languages":[{"code":"$82","label":"C (Pseudocode)","value":"c"}]},"type":"code"}],"titleType":"number","titleNumber":7},{"id":"real-world-implementations","title":"Real-World Implementations","content":[{"data":{"content":"$83"},"type":"text"},{"data":{"rows":[["Unit","Block groups (128 MB)","Allocation groups (up to 1 TB)","Single bitmap file"],["Bitmap storage","Fixed location per group","AG header area","$$Bitmap system file"],["Free block search","Linear scan with hints","B+ tree lookup","Linear scan with cache"],["Contiguous search","Preallocation window","By-size B+ tree","Best-fit heuristic"],["Journaling","Full metadata journal","Full metadata journal","Logged (USN Journal)"],["Max volume size","1 EB (exabyte)","8 EB","256 TB (practical)"]],"caption":"Bitmap Implementation Comparison","headers":["Aspect","ext4","XFS","NTFS"]},"type":"table"},{"data":{"icon":"Info","title":"Beyond Simple Bitmaps","content":"While XFS uses B+ trees instead of raw bitmaps, conceptually it still tracks which blocks are free vs. allocated. The B+ tree is essentially a compressed representation that eliminates the need to store bits for large contiguous regions. This hybrid approach—conceptually a bitmap, implemented as a tree—represents an evolution of the basic technique.","variant":"note"},"type":"callout"}],"titleType":"number","titleNumber":8},{"id":"summary","title":"Summary: Bitmap Free Space Management","content":[{"data":{"content":"The bit vector is a foundational technique that elegantly balances simplicity, efficiency, and practicality. Despite being one of the oldest approaches to free space management, it remains relevant in modern file systems because its core trade-offs are extremely favorable for typical storage devices."},"type":"text"},{"data":{"type":"ordered","items":["**One bit per block** provides exceptional space efficiency (~0.003% overhead for 4KB blocks)","**Word-at-a-time scanning** with hardware bit instructions enables fast allocation","**Block groups partition** large file systems for parallelism, locality, and fault isolation","**Allocation strategies** (first-fit, next-fit, locality-aware) optimize for different workloads","**Journaling** ensures crash consistency by logging bitmap changes before applying them","**Modern implementations** like ext4, XFS, and NTFS all use variations of the bitmap approach"],"title":{"icon":"CheckCircle","text":"Key Takeaways","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"},{"data":{"content":"**What's Next**:\n\nBitmaps excel at tracking individual block status but have limitations for certain operations—particularly finding the *size* of free regions or efficiently allocating large contiguous extents. The next page explores **Linked List** approaches, which trade space efficiency for different operational characteristics."},"type":"text"},{"data":{"icon":"CheckCircle","title":"Page Complete","content":"You now understand the bit vector approach to free space management—from fundamental concepts through practical implementation details. This technique is essential knowledge for understanding how file systems efficiently track billions of disk blocks while maintaining crash consistency.","variant":"success"},"type":"callout"}],"titleType":"number","titleNumber":9}],"isLocked":false},{"id":"seed_febf0b4a8ddd6cf4955f45b006c561fa","title":"Linked List Free Space Management","order":1,"content":null,"isLocked":true},{"id":"seed_a00b05ed86ebc6178c09c105d519cbfd","title":"Grouping Free Space Management","order":2,"content":null,"isLocked":true},{"id":"seed_0c0c0e080168e275c02dc81be48a705f","title":"Counting Free Space Management","order":3,"content":null,"isLocked":true},{"id":"seed_ec00b890a6ecde1cdfa40bda5e359831","title":"Space Maps","order":4,"content":null,"isLocked":true}]}}