File-System Layout and Free-Space Management
On-disk layout
A typical UNIX file system (e.g., ext4) divides a disk partition into:
| Region | Contents |
|---|---|
| Boot block | Bootloader code (first sector or first few sectors) |
| Superblock | File-system metadata: block size, total blocks, free block count, inode count, mount count, last check timestamp. Replicated at several locations for redundancy. |
| Inode table | A linear array of inodes. Each inode is a fixed-size structure (128–256 bytes). The inode number is its index into this table. |
| Data blocks | The rest of the partition. Allocated to file data and indirect pointer blocks. |
Free-space management
The file system must track which blocks are free (available for allocation) and which are allocated to files. Two common techniques:
Free-block bitmap
Each block is represented by a single bit: 1 = allocated, 0 = free. A 1 TB disk with 4 KB blocks has blocks. The bitmap is bits = 32 MB. This is stored on disk (and cached in memory) and updated atomically.
Advantages: Constant-time allocation of the next free block (scan for the next 0 bit). Simple, robust. Easy to verify consistency (fsck checks the bitmap against actual usage).
Disadvantages: Bitmap size grows with disk size. Finding a contiguous range of free blocks requires scanning the bitmap linearly.
Free-block linked list
Free blocks are chained together: each free block contains a pointer to the next free block. Allocation pops from the head; freeing pushes to the head.
Advantages: Compact — no separate bitmap. Fast allocation (always pop from head).
Disadvantages: Fragile — a single lost pointer corrupts the entire free list. Doesn’t support contiguous allocation well. Not commonly used in modern file systems; the bitmap has won.
Inode allocation
Inode allocation is separate from block allocation. The file system keeps a free-inode bitmap. When creating a new file, the allocator picks a free inode, preferring inodes near the directory’s inode (to keep related files’ metadata close on disk — a heuristic for reducing seek time).
Consistency and journaling
File-system operations often involve multiple on-disk updates (write data block, update inode, update free-block bitmap, update directory entry). A crash in the middle leaves the file system in an inconsistent state.
fsck (file system check) scans the entire file system after a crash, detecting and repairing inconsistencies (e.g., a block marked free in the bitmap but still referenced by an inode). For large disks, fsck can take hours — unacceptable for servers.
Journaling (ext3/ext4, NTFS): before making changes, the file system writes a journal entry (a log record describing the pending changes) to a special journal area on disk. After the changes complete, it writes a commit record. After a crash, the recovery code replays or rolls back journal entries. Only the journal (small, contiguous) needs to be scanned, not the entire file system. Modern file systems use metadata-only journaling (journal inodes and bitmaps; data blocks are written separately).
Summary
- The on-disk layout has the superblock, inode table, and data blocks.
- Free blocks are tracked by a bitmap (common) or linked list (historical).
- Journaling provides fast crash recovery by logging pending changes before applying them.
- fsck scans the whole disk; journal recovery scans only the journal log.