Space Allocation
Part of Data Storage
How operating systems and filesystems manage storage space — tracking which blocks are used and which are free, and strategies for efficient allocation.
Why This Matters
When a program creates a file, the operating system must find free space on the storage medium and assign it to that file. When the file grows, more space must be found and linked. When the file is deleted, its space must be reclaimed and made available again. Space allocation is the bookkeeping system that makes all of this work.
Poor allocation strategies lead to fragmentation — a file’s data scattered across non-contiguous regions of the disk, increasing seek time. Good strategies minimize fragmentation, maximize space utilization, and make allocation fast.
Understanding storage allocation is essential for designing filesystem software, for understanding performance characteristics of different filesystems, and for implementing storage systems from scratch when rebuilding computing infrastructure.
Block-Based Allocation
Modern storage systems divide the medium into fixed-size blocks (also called sectors or clusters). A file’s data occupies one or more blocks. Even a 1-byte file uses at least one full block.
Common block sizes:
- Hard disk sectors: 512 bytes (traditional) or 4096 bytes (Advanced Format)
- Filesystem clusters: 4 KB (typical for small volumes), up to 64 KB (for large volumes)
- Flash pages: 4 KB typical
Larger blocks reduce overhead (fewer metadata entries) but waste space on small files (internal fragmentation: unused space within an allocated block). A filesystem cluster of 64 KB holding a 100-byte file wastes 64 KB - 100 bytes = ~64 KB.
Smaller blocks reduce waste but increase overhead (more blocks to track) and add seek overhead for files spread across many blocks.
The choice of block size is a tradeoff based on the typical file size distribution and storage capacity.
Free Space Tracking: Bitmap
A block bitmap is the simplest free-space tracking method. One bit per block: 0 = free, 1 = used. A 1 GB filesystem with 4 KB blocks has 262,144 blocks, requiring 262,144 bits = 32 KB for the bitmap.
To allocate one block: scan the bitmap for the first 0, set it to 1, return the block number. O(N) worst case but typically fast with efficient scanning.
To free a block: clear the corresponding bit to 0. O(1) operation.
The bitmap must be persistent (stored on disk) and updated atomically with the file data to prevent inconsistency after crashes. Many filesystems use journaling to ensure bitmap updates are crash-safe.
Bitmaps are used by ext2/ext3/ext4 (Linux), FAT32 (FAT uses a linked allocation table instead), and most custom filesystems.
Free Space Tracking: Free List
A free list (or free block list) maintains a linked list of free blocks. Each free block stores the number of the next free block in the list.
Allocation: remove the head of the list, return the block. O(1). Freeing: prepend the block to the list head. O(1).
Free lists are fast but have poor spatial locality — allocating multiple blocks for one file may give blocks scattered across the disk, immediately causing fragmentation.
Some implementations group free blocks: the head of the list points to a block that contains a list of N free block numbers. Allocating N blocks at once retrieves the entire group, then follows the pointer to the next group.
File Allocation Strategies
Contiguous allocation: allocate consecutive blocks for each file. Maximum sequential read performance, no fragmentation within a file. Severe external fragmentation over time (files deleted leave holes of various sizes). Requires knowing the file’s maximum size at creation time. Used by simple filesystems and early mainframe systems.
Linked allocation (FAT): each block contains a pointer to the next block in the file. The file is a linked list of blocks. No fragmentation limit on file growth. Poor random access (must follow chain from start). The FAT (File Allocation Table) stores these links in a centralized table rather than in the data blocks themselves, allowing the chain to be traversed without reading all data blocks.
Indexed allocation (inode): each file has an inode — a metadata block containing direct pointers to data blocks, plus indirect pointers (a block containing more pointers) and double-indirect pointers (a block of blocks of pointers). Efficient for both small files (use direct pointers) and large files (use multi-level indirection). ext2/ext3/ext4 use inode-based allocation.
Fragmentation and Defragmentation
Internal fragmentation: wasted space within allocated blocks. A 1-byte file in a 4 KB block wastes 4095 bytes. Unavoidable with block-based allocation; minimized by choosing appropriate block sizes.
External fragmentation: free space is split into many small, non-contiguous pieces. Even if total free space is sufficient for a large allocation, no single contiguous region is large enough. Occurs with variable-size allocation; less of an issue with fixed-size block allocation.
File fragmentation: a single file’s blocks are scattered non-contiguously across the medium. Increases seek time for HDDs significantly; has no effect on SSDs (random access is same speed as sequential). Defragmentation reorganizes file blocks to be contiguous.
Defragmentation algorithms:
- Identify fragmented files (files with non-contiguous blocks).
- Find contiguous free space large enough for the file.
- Copy file to the new contiguous location.
- Update the filesystem metadata (inode, directory entry).
- Free the old blocks.
On SSDs, defragmentation reduces SSD lifespan by causing unnecessary write amplification and provides no performance benefit. Never defragment an SSD.
Allocation for Flash Storage
Flash memory complicates allocation because of the erase-before-write requirement: flash cells must be erased in large blocks (128 KB or more) before individual pages can be written. Random writes cause write amplification — small data changes trigger large erase-write cycles.
Flash filesystems (JFFS2, YAFFS, F2FS, or the internal FTL in an SSD) implement log-structured writes: always write sequentially, marking old data as invalid rather than overwriting in place. Periodically, a garbage collection process compacts valid data and erases freed blocks.
This approach converts random writes to sequential writes, dramatically extending flash lifespan and maintaining consistent performance. Understanding log-structured allocation is essential for any system incorporating flash storage.