Allocation Methods for File Storage

Allocation is the strategy a file system uses to assign disk blocks to a file and to record that assignment so the blocks can be found again. Disks are divided into fixed-size blocks (or clusters), typically 4 KB, the smallest unit the file system manages. A file of logical size $L$ bytes needs $\lceil L / B \rceil$ blocks, where $B$ is the block size; the file system must choose which physical blocks these are and store a mapping from logical block number (0, 1, 2, … within the file) to physical block number on disk. Three classical strategies solve this mapping problem. Contiguous allocation stores a file as one run of consecutive blocks, recording only a starting block and a length. Linked allocation stores a file as a chain of blocks, each holding a pointer to the next, so metadata is just a head pointer. Indexed allocation gathers all of a file's block pointers into one or more dedicated index blocks, so the mapping is an explicit array rather than an implicit run or chain. Real systems (ext4, NTFS) use hybrids — extent-based indexing — that combine the compactness of contiguous runs with the flexibility of indexed pointers. Orthogonal to allocation is free-space management: the file system must always know which blocks are unused so it can satisfy allocation requests. The two dominant structures are the bitmap (one bit per block, 1 = allocated) and the free list (a linked list threading through unused blocks, sometimes cached as a stack of free block numbers in memory). Both must support fast allocation, fast deallocation, and — ideally — fast discovery of runs of contiguous free blocks, since contiguity is what makes sequential I/O fast regardless of which allocation method is layered on top.

Contiguous allocation

The directory entry (or inode) stores only `(start_block, length)`. To access logical block $i$ of the file, compute physical block `start_block + i` directly — no traversal needed. ``` function CONTIG_READ(file, logical_block_i): if i >= file.length: error "out of range" physical = file.start_block + i return DISK_READ(physical) function CONTIG_ALLOCATE(size_in_blocks): // Requires finding a contiguous free run of the right size. run = FIND_FREE_RUN(size_in_blocks) // best-fit / first-fit / worst-fit if run == NONE: error "no contiguous space (may need compaction)" MARK_ALLOCATED(run.start, size_in_blocks) return run.start ``` `FIND_FREE_RUN` is the crux: as files are created and deleted, free space fragments into many small runs separated by allocated blocks — external fragmentation. Eventually a request for $k$ blocks may fail even though the disk has far more than $k$ free blocks in total, because no single run is long enough. The classic remedy is compaction (copy all files to squeeze free space together), which is correct but expensive — $O(n)$ in total data moved, and it typically requires taking the file system offline or doing it incrementally. A refinement, extent-based allocation, stores a list of `(start, length)` pairs instead of one — a file is a small number of contiguous runs (extents) rather than one giant run. This keeps most of the sequential-access benefit while tolerating fragmentation gracefully; ext4 and NTFS both use extents.

Linked allocation

Each block contains data plus a pointer to the next block in the file; the last block's pointer is a sentinel (e.g., $-1$ or null). The directory/inode stores only the address of the first block (and often the last, to support fast appends). ``` function LINKED_READ(file, logical_block_i): ptr = file.head for k = 0 to i - 1: (data, ptr) = DISK_READ(ptr) // follow the chain if ptr == NULL: error "out of range" (data, next) = DISK_READ(ptr) return data function LINKED_APPEND(file, new_data): new_block = FIND_ONE_FREE_BLOCK() WRITE(new_block, new_data, next = NULL) if file.tail != NULL: UPDATE_NEXT_POINTER(file.tail, new_block) else: file.head = new_block file.tail = new_block ``` Free-space management is trivial for allocation itself: any single free block will do, since there is no contiguity requirement — this eliminates external fragmentation entirely (aside from unavoidable internal fragmentation in the last block). But random access to logical block $i$ costs $O(i)$ disk reads because every prior block must be traversed to find the next pointer. Reliability is also fragile: a single corrupted pointer breaks the chain for every subsequent block. A well-known optimization, the File Allocation Table (FAT), pulls all the "next" pointers out of the data blocks and into one contiguous table cached in memory, turning traversal into fast in-memory array lookups while keeping data blocks pointer-free. ``` // FAT variant: table[i] = index of block following block i, or EOF function FAT_READ(file, logical_block_i): block = file.first_block for k = 0 to i - 1: block = FAT[block] // in-memory table, O(1) per step if block == EOF: error "out of range" return DISK_READ(block) ``` The FAT table itself, however, must be scanned linearly to find a free entry unless a separate free list or bitmap tracks free blocks — and the whole table typically must reside in memory to be useful, which does not scale to very large volumes.

Indexed allocation

Each file gets one index block holding an array of pointers, one per logical block. The inode stores only the address of the index block. ``` function INDEXED_READ(file, logical_block_i): index_block = DISK_READ(file.index_block_addr) if i >= LENGTH(index_block.pointers): error "out of range" physical = index_block.pointers[i] return DISK_READ(physical) function INDEXED_ALLOCATE_BLOCK(file, logical_block_i, data): p = FIND_ONE_FREE_BLOCK() WRITE(p, data) index_block = DISK_READ(file.index_block_addr) index_block.pointers[i] = p DISK_WRITE(file.index_block_addr, index_block) ``` Random access now costs one indirection (read the index block, typically cached in memory after the first access) plus one data read — $O(1)$ disk accesses in the worst case, versus $O(i)$ for pure linked allocation. External fragmentation on data blocks is gone (any free block works), but a single index block has a fixed capacity: with block size $B$ and pointer size $p$ bytes, it can address only $B/p$ blocks. For a 4 KB block and 4-byte pointers, that is 1024 blocks — only 4 MB per file, unacceptable for large files. The standard fix is multilevel indexing, exactly as used for Inodes and File Metadata in Unix-style inodes: direct pointers for small files, a single indirect block for medium files, a double indirect block (an index block of index blocks) for large files, and a triple indirect block for very large files. ``` function MULTILEVEL_TRANSLATE(inode, logical_block_i): N = POINTERS_PER_BLOCK // e.g., 1024 if i < NUM_DIRECT: return inode.direct[i] i -= NUM_DIRECT if i < N: // single indirect L1 = DISK_READ(inode.single_indirect) return L1.pointers[i] i -= N if i < N N: // double indirect L1 = DISK_READ(inode.double_indirect) L2 = DISK_READ(L1.pointers[i / N]) return L2.pointers[i % N] i -= N N if i < N N N: // triple indirect L1 = DISK_READ(inode.triple_indirect) L2 = DISK_READ(L1.pointers[i / (N*N)]) L3 = DISK_READ(L2.pointers[(i / N) % N]) return L3.pointers[i % N] error "file exceeds maximum addressable size" ``` Access time is bounded by the number of indirection levels touched — a small constant (at most 4 disk reads for the triple-indirect case, often fewer with caching), independent of file size, so it remains $O(1)$ in the number of blocks the file occupies.

Free-space management

Bitmap. One bit per block: `bit[i] = 1` means block $i$ is allocated. Finding a free block is a linear scan for a 0 bit; finding $k$ contiguous free blocks is a scan for $k$ consecutive 0 bits, which the bitmap supports naturally because adjacency in the bitmap mirrors adjacency on disk. ``` function BITMAP_FIND_FREE_RUN(bitmap, k): run_start = -1 run_len = 0 for i = 0 to LENGTH(bitmap) - 1: if bitmap[i] == 0: if run_len == 0: run_start = i run_len += 1 if run_len == k: return run_start else: run_len = 0 return NONE ``` A bitmap for a 1 TB disk with 4 KB blocks needs $2^{30}$ bits $\approx$ 128 MB — small enough to hold largely in memory, and word-at-a-time scanning (checking 64 bits per comparison) makes the common case fast in practice despite the $O(n)$ worst case.

Free list. Each free block stores a pointer to the next free block, forming a linked list threaded through unused space; the file system keeps only a head pointer (and sometimes a count). Allocating one block is $O(1)$: pop the head. But finding $k$ contiguous free blocks is not naturally supported — the list order need not reflect physical adjacency — so contiguous allocation on top of a pure free list typically requires an auxiliary structure (e.g., grouping the list by extent, or falling back to a bitmap-like scan). A common optimization caches a large array of free block numbers in memory (a "free list cache" or the FAT itself doubles as one) to avoid disk I/O for every allocation. ``` function FREELIST_ALLOCATE_ONE(): if free_list.head == NULL: error "disk full" b = free_list.head free_list.head = DISK_READ(b).next_free // O(1) return b function FREELIST_DEALLOCATE(b): DISK_WRITE(b, next_free = free_list.head) // O(1) free_list.head = b ```

Contiguous allocation. Sequential read of the whole file: $O(n)$ blocks with no seek overhead between blocks (best possible for sequential I/O). Random access to block $i$: $O(1)$ — direct arithmetic on `start + i`. Allocation of a new file: $O(D)$ in the worst case, where $D$ is the number of free-space fragments, since the allocator must scan for a run of the requested size using strategies like first-fit or best-fit. Correctness relies on the invariant that `(start, length)` always denotes a set of blocks currently marked allocated in the free-space structure and owned by exactly one file; any allocator that maintains this invariant (never returns overlapping runs) is correct by construction. The persistent weakness is space efficiency: even with $\Theta(n)$ live data, the disk can become unusable because free space is not "usable" free space — this is the textbook definition of external fragmentation, and no local fix removes it without global compaction.

Linked allocation. Sequential read: $O(n)$ blocks, but each block may be scattered anywhere on disk, so real wall-clock time picks up a seek between almost every block on a rotating disk — asymptotically $O(n)$ but with a much worse constant than contiguous. Random access to block $i$: $O(i)$, since the chain must be walked from the head; worst case $O(n)$ for the last block. Space overhead: one pointer per block (small, e.g., 4–8 bytes out of 4096), giving negligible internal fragmentation from the pointer itself. Correctness invariant: following `next` pointers from `head` visits exactly the blocks of the file, in logical order, terminating at a sentinel — true as long as no pointer is corrupted and no block is shared between two chains, which the allocator must guarantee by only ever allocating from the free set.

Indexed allocation (single index block). Random access: $O(1)$ disk operations (one index-block read, cached after first touch, plus one data read). Space overhead: one pointer per file block, held in the index block(s) rather than inline, so data blocks carry zero overhead, but a whole block is spent per file just for the index even for a 1-block file — a form of internal fragmentation for small files. Maximum file size with one index block of $B/p$ pointers is $B \cdot (B/p)$ bytes. Multilevel indexing extends the addressable range multiplicatively at each level while keeping access time bounded: with $L$ levels beyond direct pointers, worst-case disk accesses to reach a data block is $L + 1$ — a small constant independent of $n$, because the branching factor $N = B/p$ (commonly 512–1024) makes even two levels of indirection address gigabytes of data, and three levels reach terabytes. This is the same complexity argument used to justify $B$-tree-like fan-out elsewhere: constant depth for enormous capacity because depth grows as $\log_N(\text{size})$, and with $N \approx 1000$, that log is effectively bounded by 3–4 for any realistic file size.

Free-space bitmap. Space: $n/8$ bytes for $n$ blocks (1 bit each) — for a 1 TB disk at 4 KB blocks, about 128 MB, feasible to cache in RAM. Finding one free block: $O(n)$ worst case (all allocated blocks scanned before a 0 bit is found), but with word-parallel scanning (test 64 bits at once) the practical constant shrinks by roughly 64×, and maintaining a "next free hint" pointer makes the amortized case close to $O(1)$ under typical allocation/deallocation patterns. Finding a contiguous run of $k$ blocks: $O(n)$ worst case, unavoidable in the worst case since contiguity is a global property, but bitmaps are the natural structure for this because bit adjacency mirrors block adjacency.

Free list. Space: one pointer per free block, stored in the free blocks themselves — effectively zero extra space beyond the head pointer, better asymptotically than a bitmap for space when free space is small, though bitmaps win when free space is large (a free list of $m$ free blocks needs $m$ pointer-writes; a bitmap is always $n/8$ regardless of how many blocks are free). Allocate/deallocate one block: $O(1)$ — pop/push the head. Finding contiguous runs: not supported without auxiliary structure, since list order is not tied to physical order; this is the chief reason many systems prefer bitmaps or grouped/extent-based free lists despite the free list's simplicity.

Consider a small file system with 16 blocks (0–15), block size 4 KB, and a file `report.txt` that needs 4 blocks. Suppose blocks 2, 4, 7, and 9 are currently free among otherwise allocated blocks 0, 1, 3, 5, 6, 8, 10–15.

This trace makes the trade-off concrete: contiguous allocation fails outright here despite 4 free blocks existing in total, because none of the strategies can conjure contiguity that does not exist — the request must wait for deletions to coalesce free space, or the system must compact. Linked allocation succeeds immediately but costs 3 extra disk reads to reach the last block (block 9) versus indexed allocation's fixed 2 reads regardless of which block is requested. Indexed allocation pays a one-block metadata tax (block 11) that neither of the other schemes pays directly, though contiguous allocation pays an implicit tax in its `(start, length)` inode fields and linked allocation pays it in per-block pointer overhead spread across all four data blocks. Now suppose the file grows to 1200 blocks with a 4-byte pointer and 4 KB blocks ($N = 1024$ pointers per index block), and the inode has 12 direct pointers. Using the multilevel scheme:

Since $1188 < 1024$, a single indirect block is not enough (it only reaches $12 + 1024 = 1036$ blocks); block 1200 falls into the double indirect range, which starts at logical block $1036$ and can address up to $12 + 1024 + 1024^2 \approx 1{,}049{,}612$ blocks. Reaching logical block 1199 (0-indexed 1188th indirect block) costs: 1 read for the double-indirect block, 1 read for the appropriate first-level index block within it, 1 read for the data block — 3 disk operations total, regardless of whether the target were block 1199 or block 1,000,000. That constancy is exactly the $O(1)$-in-file-size claim made above.

Every mainstream file system is a variant or hybrid of these three ideas. FAT12/16/32 and exFAT use table-based linked allocation, still found on USB drives, SD cards, and camera storage because of its simplicity and universal compatibility. ext2/ext3 used classic Unix indexed allocation with direct/indirect/double-indirect/triple-indirect pointers; ext4 and XFS moved to extent-based allocation, representing large contiguous runs compactly to reduce both metadata size and fragmentation for large files (video, databases, virtual machine disk images). NTFS stores file layout as a run list of extents inside the Master File Table, blending contiguous runs with indexed flexibility. Database systems and virtual machine hypervisors often bypass the general-purpose file system entirely and manage raw block allocation themselves, using the same bitmap/free-list trade-offs to control fragmentation for performance-critical workloads. SSD-aware file systems and log-structured file systems (e.g., F2FS) lean toward append-only, sequential allocation patterns precisely because random writes interact badly with flash translation layers, echoing the sequential-access advantage of contiguous allocation. The layout decisions made here directly determine what must be logged or checksummed to survive a crash, which is the subject of Journaling and Crash Consistency, and how blocks are striped or mirrored across disks for durability and throughput, the subject of RAID and Redundant Storage.

Ask the tutor: How does extent-based allocation in ext4 combine the benefits of contiguous and indexed allocation while avoiding their respective weaknesses?