File-System Implementation and Layout

A file-system implementation is the concrete mapping between an abstract hierarchy of files and directories and the raw sequence of blocks a disk or SSD actually exposes. The disk itself has no notion of "files" — it is addressed by logical block number (LBA), a flat array of fixed-size sectors (traditionally 512 bytes, now often 4096-byte blocks). Every file system must therefore reserve, at formatting time (`mkfs`), specific regions of this address space for specific purposes, and this reservation scheme is called the on-disk layout. Four layout regions recur across nearly every classical file system. The boot block (or boot sector) occupies the first few blocks of a partition and holds a small bootstrap program executed by firmware at power-on; a volume need not be bootable, but the block's location is standardized. The superblock is a small, densely packed structure holding the file system's vital statistics: block size, total block count, free block count, count of inodes, and a pointer to the root of the directory tree. The free-space region tracks which blocks are currently unallocated, using a bitmap, a free list, or a variant. The inode table (or its equivalent, an MFT in NTFS) is a region holding fixed-size metadata records — one per file — that describe ownership, permissions, size, timestamps, and pointers to the file's data blocks; this leads directly into Inodes and File Metadata and Allocation Methods for File Storage. Parallel to this static, on-disk structure, the operating system maintains in-memory data structures that exist only while the system is running. The mount table records which device is attached at which pathname in the global namespace, enabling a single tree to span multiple physical or virtual volumes. The in-memory superblock is a cached, often augmented copy of the on-disk superblock, avoiding a disk read on every metadata query. The buffer cache (block-level) or page cache (unified with virtual memory) holds recently accessed disk blocks, since real workloads exhibit strong temporal and spatial locality — the same blocks, or their neighbors, are re-read and re-written far more often than a uniform-random access pattern would suggest.

Formatting (`mkfs`) is the process that writes the initial, empty layout onto a raw partition. Conceptually it performs the following steps. ``` FORMAT(partition, block_size): n_blocks := size(partition) / block_size

# 1. Reserve boot block(s) write_zero_or_bootstub(partition, block 0)

# 2. Reserve and initialize superblock sb.magic := FS_MAGIC sb.block_size := block_size sb.total_blocks := n_blocks sb.inode_count := choose_inode_count(n_blocks) sb.free_block_count := n_blocks - reserved_blocks(sb) sb.free_inode_count := sb.inode_count - 1 # root uses one sb.root_inode := ROOT_INODE_NUMBER sb.state := CLEAN write(partition, SUPERBLOCK_OFFSET, sb) write_backup_superblock_copies(partition, sb) # crash resilience

# 3. Initialize free-space structure (bitmap example) for b in range(n_blocks): bitmap[b] := (b in reserved_regions(sb)) ? USED : FREE write(partition, sb.bitmap_offset, bitmap)

# 4. Initialize inode table for i in range(sb.inode_count): inode_table[i] := EMPTY_INODE inode_table[ROOT_INODE_NUMBER] := make_root_directory_inode() write(partition, sb.inode_table_offset, inode_table)

# 5. Write root directory's data block (".", "..") root_block := new_directory_block(ROOT_INODE_NUMBER, ROOT_INODE_NUMBER) write(partition, allocate_from(bitmap), root_block) ```

Mounting links a formatted volume into the live directory tree so ordinary path lookups can cross into it transparently. ``` MOUNT(device, mount_point_path): sb := read_superblock(device) assert sb.magic == FS_MAGIC # sanity check if sb.state != CLEAN: run_consistency_check(device) # e.g. fsck / journal replay in_memory_sb := load_into_memory(sb) # cached superblock mp_inode := resolve_path(mount_point_path) # must be an existing directory assert is_directory(mp_inode) assert not already_a_mount_point(mp_inode) entry := { device, root_inode: sb.root_inode, mount_point: mp_inode } mount_table.add(entry) mp_inode.mark_as_mount_point(device) # lookups here now redirect ``` Once mounted, every pathname lookup consults the mount table at each directory boundary: ``` RESOLVE_PATH(path): cur := current_root_or_cwd_inode() for component in split(path): if cur.is_mount_point(): device := mount_table.lookup(cur) cur := read_inode(device, device.root_inode) # cross into new FS cur := lookup_entry_in_directory(cur, component) if cur is null: error("no such file or directory") return cur ``` Finally, the buffer/page cache intercepts every block read and write, turning most I/O into memory operations: ``` READ_BLOCK(device, block_number): if cache.contains(device, block_number): cache.mark_recently_used(device, block_number) return cache.get(device, block_number) else: data := disk_read(device, block_number) # goes through I/O scheduler if cache.is_full(): victim := cache.evict_lru() if victim.dirty: disk_write(victim.device, victim.block_number, victim.data) cache.insert(device, block_number, data) return data WRITE_BLOCK(device, block_number, data): cache.insert_or_update(device, block_number, data, dirty=True)

# deferred write-back, or immediate flush for metadata in journaled FS ```

Time complexity of the core operations. Reading the superblock at mount time is `O(1)` — it lives at a fixed, known offset, so no search is required. Path resolution costs `O(d)` disk/cache accesses, where `d` is the path depth, since each directory component requires one lookup (and, at mount boundaries, one redirect through the mount table, itself `O(1)` with a hash-based implementation). Checking or updating free-space status for one block is `O(1)` with a bitmap, since block number `b` maps directly to bit `b` of the bitmap — no traversal needed. Finding a free block among `n` total blocks is `O(n)` in the worst case with a naive bitmap scan, though real systems maintain per-group free counts or a free list so an actual free block is found in `O(1)` amortized time. Buffer cache lookup is `O(1)` with a hash table keyed by (device, block number); LRU eviction is `O(1)` with a doubly linked list plus hash map, or `O(log n)` if implemented with a heap-based clock approximation.

Space complexity. The superblock is a small, fixed-size structure independent of volume size — typically under a few kilobytes, so `O(1)` relative to disk size. The free-space bitmap requires 1 bit per block, so `O(n / 8)` bytes for `n` blocks — for a 1 TB disk with 4 KB blocks, `n ≈ 2.68×10^8` blocks, giving roughly 32 MB of bitmap, a small fraction of total capacity. The inode table's size is fixed at format time as a design tradeoff: too few inodes and the file system runs out of "file slots" even with free disk space remaining; too many wastes space permanently, since the region cannot easily shrink later, foreshadowing the deeper inode-design tradeoffs in Inodes and File Metadata.

Correctness argument for the buffer cache. The cache must maintain the invariant that any read returns the most recently written value for that block, from the perspective of processes using the file system (read-your-writes consistency), even though the on-disk copy may be stale. This holds because every `READ_BLOCK` and `WRITE_BLOCK` funnels through the same cache lookup keyed by `(device, block_number)`; a write always updates (or inserts) the cached entry before any subsequent read can observe it, and there is no code path that reads directly from disk while bypassing an existing cache entry. The invariant that matters for crash correctness is different and weaker: after an uncontrolled power loss, the on-disk state must be recoverable to some consistent file-system state, not necessarily the most recent one. This is why metadata writes (superblock, bitmap, inodes) are typically write-ordered or journaled — the system enforces that a transaction's intent record hits disk before the data it describes is considered committed, so a crash mid-write leaves the log inconsistent (detectable and replayable) rather than the file system silently corrupted.

Tradeoffs. A fixed-size inode table (classic UFS/ext2 style) gives `O(1)` inode lookup by number but caps the maximum file count at format time. A dynamic metadata structure (NTFS's Master File Table, ext4's flexible inode allocation) trades a small lookup overhead for elastic capacity. Write-back caching (deferring disk writes) dramatically improves throughput but risks losing recent writes on crash; write-through caching sacrifices throughput for durability. Bitmaps are compact and support `O(1)` status checks, but a naive linear scan for a free block degrades under fragmentation — production systems mitigate this with grouped allocation and cached "hint" pointers, which is exactly the subject of Allocation Methods for File Storage.

Trace mounting a small ext2-like volume with 128 blocks (block size 1 KB) at `/mnt/data`, then opening the file `/mnt/data/notes.txt`.

Step 0 — layout on disk (fixed at format time).

Step 1 — `MOUNT("/dev/sdb1", "/mnt/data")`.

Step 2 — `RESOLVE_PATH("/mnt/data/notes.txt")`.

Step 3 — reading the file's first block through the cache.

This trace shows the three costs in practice: mounting is a handful of fixed reads independent of volume size, path resolution costs one step per component plus a redirect at each mount boundary, and repeated access to the same block after the first miss becomes free until eviction forces a flush.

The layout conventions described here trace back to early Unix file systems, whose designers had to solve superblock placement, free-list management, and crash recovery with far less memory and far slower disks than modern systems provide, motivating decisions — such as small fixed metadata regions and replicated superblocks — that persist in file systems today.

Every general-purpose operating system relies on exactly this layered layout-plus-cache design. Linux's ext4, XFS, and Btrfs each define their own superblock format and free-space structure (a bitmap for ext4, B-trees for XFS and Btrfs) but share the mount-table and page-cache abstractions in the kernel's Virtual File System (VFS) layer. Windows' NTFS replaces the fixed inode table with an extensible Master File Table but still reserves a boot sector and a fixed-offset "file system descriptor" analogous to a superblock. Database systems and container runtimes rely on the mount table's flexibility to overlay union file systems (as in Docker's overlay2) and bind-mount volumes without duplicating data. Embedded and mobile systems tune buffer/page cache sizes aggressively because RAM is scarce, while cloud block-storage systems (Amazon EBS-backed volumes, network file systems) replicate the superblock across nodes to survive single-machine failure — a direct descendant of the "backup superblock" idea from 1970s Unix. Solid-state drives complicate the classic layout further, since the flash translation layer beneath an SSD (see Solid-State Drives (SSDs)) remaps logical block numbers to physical flash pages, meaning the file system's tidy on-disk layout is itself an abstraction over another layer of indirection and wear-leveling below it.

Ask the tutor: How does journaling change the write-ordering rules for the superblock, bitmap, and inode table during a single file-creation transaction?