Bit Vector (Bitmap) - Free Space Management | OneNoughtOne

0/236

Operating SystemsFile System Implementation

Free Space Management

LevelIntermediate

Duration75 mins

TopicFile System Implementation

1 / 5

Bit Vector (Bitmap)

The Art of Tracking Empty Space

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.

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.

This 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.

What You Will Learn

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.

The Free Space Problem

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).

Consider a moderately-sized 1TB SSD with 4KB blocks:

Total capacity: 1,099,511,627,776 bytes (1 TB)
Block size: 4,096 bytes (4 KB)
Total blocks: 268,435,456 blocks (~268 million blocks)

The file system must answer two critical questions efficiently:

Allocation query: When creating or extending a file, which blocks are available?
Deallocation update: When deleting a file, how do we mark its blocks as free?

The 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.

Design Requirements for Free Space Management

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.

Free Space Management Trade-offs
Approach	Space Overhead	Allocation Speed	Contiguity Support	Crash Recovery
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

Bit Vector Fundamentals

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

bitmap_fundamentals.c
C
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
#include <stdint.h>
#include <stdbool.h>
#include <string.h>
#include <stdlib.h>
 
/**
 * 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;
}

Space Efficiency Analysis

One of the bitmap's most compelling advantages is its exceptional space efficiency. Let's analyze the overhead for various storage device sizes:

Overhead Calculation:

For a device with n blocks, the bitmap requires exactly n bits = n/8 bytes.

The overhead ratio is:

overhead_ratio = bitmap_size / total_storage
                = (n/8) / (n × block_size)
                = 1 / (8 × block_size)

For 4KB blocks:

overhead_ratio = 1 / (8 × 4096) = 1 / 32,768 ≈ 0.003%

This means less than 1 byte of overhead for every 32KB of storage—an incredibly efficient representation.

Bitmap Size for Common Storage Capacities (4KB blocks)
Storage Size	Total Blocks	Bitmap Size	Overhead %
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%

Memory Residency Strategy

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.

Block Size Impact:

The block size choice significantly affects both the bitmap size and the minimum allocation granularity:

Block Size	Blocks per TB	Bitmap per TB	Min Allocation Waste
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

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.

Finding Free Blocks: Sequential Scan

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:

Start scanning from position 0 (or a cached position)
Check each bit until we find a free block (bit = 1)
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.

bitmap_find_free.c
C
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
#include <stdint.h>
#include <limits.h>
 
/**
 * 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;
}

Hardware Bit Manipulation Instructions

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.

Allocation Strategies

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.

First-Fit Advantages

•Simple to implement
•Consistent starting point aids caching
•Works well for uniform allocation patterns
•Minimal state to maintain

Next-Fit Advantages

•Distributes wear evenly (important for SSDs)
•Avoids hotspots in bitmap scanning
•Better for mixed workloads
•Only requires one pointer to maintain

allocation_strategies.c
C
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
/**
 * 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;
}

Block Group Organization

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:

Parallelism: Different block groups can be allocated independently, enabling concurrent allocation operations across multiple CPU cores.
Locality: Files can be allocated within a single block group, keeping all file data and metadata physically close together on disk.
Smaller Bitmaps: Each bitmap is small enough to fit in a single disk block, reducing I/O for bitmap operations.
Fault Isolation: Corruption in one block group's bitmap doesn't affect other groups.
Efficient Caching: Only active block groups' bitmaps need to be cached in memory.

Block Group Sizing in ext4
Block Size	Blocks per Group	Group Size	Bitmap Size
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)

Why One Block per Bitmap?

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.

Crash Consistency and Journaling

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:

Find free block in bitmap
Mark block as allocated in bitmap
Write data to the block
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 do

bitmap_journaled.c
C (Pseudocode)
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
/**
 * 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.
");
}

Real-World Implementations

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 writeback

Bitmap Implementation Comparison
Aspect	ext4	XFS	NTFS
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)

Beyond Simple Bitmaps

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.

Summary: Bitmap Free Space Management

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.

Key Takeaways

•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

What's Next:

Bitmaps 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.

Page Complete

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.