File-System Implementation

A hard disk or SSD presents itself to the operating system as one thing: a huge, flat array of fixed-size blocks, each identified by a number from 0 to N. You can read block 5,000,000 or write block 12, and that is the entire vocabulary the device offers. It has no notion of a file, a name, a folder, or where one file ends and the next begins. Everything you think of as "the file system" is software that the OS lays down on top of that dumb array of blocks.

The previous chapter handed us the abstraction we now have to implement. A file is a named stream of bytes with metadata; a directory is a table mapping names to inode numbers; an inode is the record that describes one file. None of those exist on the raw device. The file system’s task is to encode all of them into blocks, and — crucially — to be able to reconstruct them after the machine has been powered off. There is no memory to fall back on; if it is not written into a block, it does not survive.

That reconstruction requirement is why implementation is genuinely hard. When you open /home/ada/report.txt, the file system has to walk the path directory by directory, each lookup reading blocks to find the next inode, until it reaches the inode for report.txt — and that inode must then tell it exactly which data blocks hold the file’s bytes, in order. Every one of those steps is a block read, and every design decision in this chapter is ultimately about making those reads fast, compact, and survivable.

Block (logical block)

The fixed-size unit the file system reads and writes — typically 4 KB — built on top of the device’s 512-byte or 4 KB physical sectors.

Metadata vs data

Data blocks hold file contents; metadata blocks hold the bookkeeping (inodes, directories, free-space maps, the superblock) that describes where everything is.

The three questions

Layout (where does bookkeeping live?), allocation (which blocks does a file get?), and free-space management (which blocks are available?).

When you format a volume, the file system carves the block array into regions with fixed jobs, so that after any reboot it can find itself by reading a few known locations. The exact layout varies between file systems, but the classic Unix-style arrangement — the one ext2/3/4 follow — has a handful of pieces that are worth knowing by name because they show up in every diagnostic tool you will ever run.

Boot block

Block 0, reserved for boot loader code. The file system leaves it alone; it is read by firmware at startup, not by the fs itself.

Superblock

The master record: block size, total number of blocks and inodes, how many are free, and where the other regions live. Lose it and the volume is unreadable — so it is replicated across the disk.

Bitmaps

One bitmap of free/used inodes and one of free/used data blocks. A single bit per object says "taken" or "available".

Inode table

A fixed array of inode slots, allocated at format time. Each slot is a small record (often 128 or 256 bytes) holding one file’s metadata and block pointers.

Data blocks

The large remaining region where file contents and directory contents actually live.

Two consequences of this layout bite in practice. First, because the inode table is a fixed-size array chosen at format time, a volume can run out of inodes while it still has free data blocks — a directory full of millions of tiny files can exhaust the inode table and refuse to create another file even though df says there is plenty of space. Second, the block size is a genuine engineering trade-off. Big blocks mean fewer of them to track and faster sequential transfers, but every file wastes, on average, half a block at its tail — that waste is internal fragmentation.

Make the block too small and the file system spends more space and time on bookkeeping (more pointers, more bitmap bits, more metadata reads per file). Make it too big and a directory of thousands of 100-byte config files might use a hundred times the space of the actual data. The common 4 KB choice is a compromise tuned to typical workloads and, not coincidentally, matches the memory page size so file data caches cleanly in RAM.

$ sudo dumpe2fs /dev/sda1 | grep -iE 'block size|inode size|inode count|block count'
Inode count:              6553600
Block count:              26214400
Block size:               4096
Inode size:               256

# 26,214,400 blocks x 4096 bytes = 100 GiB volume
# 6,553,600 inodes = one inode per ~4 data blocks, fixed at format time

The most obvious way to store a file is to put all its blocks next to each other: file A lives in blocks 4 through 8, and the directory entry only has to remember two numbers — the start block and the length. This is contiguous allocation, and on paper it looks unbeatable. It is trivial to record, and it gives you both kinds of access for free.

Sequential reading is as fast as the device can go, because the blocks are physically adjacent — on a spinning disk the head barely moves, and on an SSD the requests are perfectly predictable. Random access is just arithmetic: to read the i-th block of the file you read start + i, with no lookups at all. For read-only media this is genuinely the right answer, which is why CD-ROM and DVD file systems like ISO 9660 use contiguous allocation — the files never change, so its weaknesses never appear.

But on a writable disk the weaknesses are fatal. To create a file you must find a run of free blocks large enough to hold all of it — this is the same first-fit / best-fit search that plagues contiguous memory allocation, and it is slow. Worse, as files are created and deleted, free space shatters into scattered gaps. You can easily reach a state with plenty of total free space but no single run big enough for a new file — that is external fragmentation, and the only cure is an expensive compaction pass that shuffles every file to close the gaps.

And files grow. A log file or a document that started at three blocks may need a fourth — but the block right after it already belongs to another file. Now the file system must either refuse the write, or copy the entire file to a bigger free run somewhere else. Neither is acceptable for the general-purpose, constantly-changing storage a real OS needs. Contiguous allocation is fast until the moment you write to it, and then it falls apart.

Contiguous allocation

Each file occupies a consecutive run of blocks, recorded as a (start, length) pair.

External fragmentation

Free space broken into scattered chunks too small to satisfy requests, even though the total free space is ample.

Compaction

The costly repair: relocate files to consolidate free space into one big run. Rarely acceptable online.

If contiguity is the problem, throw it away. In linked allocation a file is a linked list of blocks scattered anywhere on the disk: each block stores its data plus a pointer to the next block, and the directory entry only needs to know the first block. To append, grab any free block, and patch the previous block’s pointer to it. Suddenly the hard problems of contiguous allocation vanish.

• ▸No external fragmentation — any free block anywhere can join any file, so free space is never "too scattered to use".
• ▸Files grow trivially — appending is just claiming one more free block and linking it in; no copying, no refusal.
• ▸Creation is cheap — no search for a big enough run, because the file need not be contiguous at all.

The price, however, is steep, and it lands exactly where it hurts. Random access is now terrible: to read the i-th block of the file you must walk the chain from the start, reading every block before it just to find the pointer to the next one. Reading block 1000 means 1000 sequential disk reads. A structure that was meant to store data has turned reading the middle of a file into a linear crawl — the classic weakness of any linked list, made painful because each "next" step is a slow disk seek.

There is a subtler cost too. The "next" pointer has to live somewhere, so it steals a few bytes out of every block. Now your file’s data no longer fits a clean power-of-two boundary — a 4 KB block might hold only 4092 bytes of payload — which quietly complicates every read and misaligns data against memory pages. And the reliability is fragile: corrupt one pointer in the chain and you lose not just that block but the entire rest of the file, with no way to find the orphaned tail.

The insight that rescues linked allocation is simple and powerful: the pointers are the problem, so pull them out of the data blocks and gather them into one table. Keep the "each block points to the next" idea, but store all the pointers together where they can be cached in memory and scanned quickly. That single move turns linked allocation into the FAT file system — the subject of the next section.

The File Allocation Table, FAT, is the file system of MS-DOS and — in its FAT32 form — still the lingua franca of USB sticks and SD cards worldwide, precisely because it is so simple that every device can implement it. Its idea is the refinement we just arrived at: take the "next block" pointers out of the data blocks and put them all into one array, the FAT, with exactly one entry per block on the disk.

The table is the chain. The directory entry records only a file’s first block number, say 9. To follow the file you look at FAT[9], which holds the number of the next block — say 4. Then FAT[4] gives the next, and so on, until you hit a reserved end-of-file marker. A file is a chain threaded through the table, not through the data, so the data blocks stay pure payload with clean, aligned sizes. Special entry values mark blocks that are free, that end a chain, or that are defective and must never be used.

The decisive win is that the whole FAT can be loaded into memory. Walking a chain in RAM is enormously faster than reading each data block just to learn the next pointer, so random access — while still technically a walk — is now a scan of an in-memory array rather than a storm of disk seeks. To find a free block you scan the table for a "free" entry; to grow a file you claim one and patch the chain. Directories are themselves just files whose data blocks hold name-to-start-block entries.

FAT

An on-disk array with one entry per data block; each entry names the next block in the file, or a special marker (free / end-of-file / bad).

Cluster

FAT’s allocation unit — one or more blocks grouped together, so one FAT entry can cover several physical blocks and keep the table small.

FAT12 / 16 / 32

The generations, named for the bit-width of each table entry, which caps how many clusters — and thus how large a volume — the table can address.

But FAT’s simplicity is also its ceiling. The table must be big enough to have one entry per cluster on the entire volume, so a large disk needs either a large table or large clusters — and large clusters bring back internal fragmentation, wasting space on small files. Random access is faster than raw linked allocation but is still a chain walk, not the direct index we really want. And the table is a single point of failure: corrupt it and you lose the map to everything, which is why FAT keeps a second copy — but not a crash-recovery journal. For a robust, high-performance file system we need a structure that reaches any block of a file directly. That is indexed allocation, and the inode.

Indexed allocation gives each file its own index of blocks. Instead of threading a chain, the file’s inode holds an array of pointers straight to its data blocks, so reaching the i-th block is a direct lookup — index into the array, read that block — with no walk at all. This restores the fast random access of contiguous allocation while keeping linked allocation’s freedom from fragmentation and easy growth. The problem is size: a small fixed array of pointers cannot describe a large file, but a huge array wastes space on the tiny files that dominate real systems.

The Unix inode solves this with a beautifully asymmetric, multi-level index. A classic inode holds 15 block pointers. The first 12 are direct pointers — they name data blocks straight away, so a small file (up to 12 blocks) needs no extra indirection at all and is blindingly fast to read. Pointer 13 is a single indirect pointer: it points to a block that contains nothing but more pointers. Pointer 14 is a double indirect pointer (a block of pointers to blocks of pointers), and pointer 15 is a triple indirect pointer, one level deeper still.

This structure is exactly matched to how files are actually distributed: the overwhelming majority are small and are served entirely by the 12 direct pointers with zero overhead, while the rare enormous file can still be addressed by paying for extra indirection blocks only as it grows. You never allocate a triple-indirect tree for a 2 KB file. Let us prove the reach with real numbers — this arithmetic is the heart of the chapter.

block size            = 4 KB          (4096 bytes)
pointers per block    = 4096 / 4     = 1024 pointers

12 direct pointers    = 12 x 4 KB               = 48 KB
single indirect       = 1024 x 4 KB             = 4 MB
double indirect       = 1024 x 1024 x 4 KB      = 4 GB
triple indirect       = 1024 x 1024 x 1024 x 4KB = 4 TB
                                          -------------
max file size ~ 48 KB + 4 MB + 4 GB + 4 TB ~ 4 TB

Read the ladder and the genius is obvious. Twelve pointers reach 48 KB for free. One single-indirect block — 1024 pointers — jumps you to 4 MB. The double-indirect level squares that to 4 GB, and the triple-indirect level cubes it to 4 TB, all from a fixed 15-slot inode of a couple hundred bytes. Cost scales with file size: a small file pays nothing extra, and even a multi-gigabyte file needs at most three extra block reads to locate any given block — a bounded, tiny price for direct access at any offset. This is why the inode has outlived nearly every other design.

Direct pointer

An inode slot that names a data block directly. The first 12 cover small files with no indirection.

Single / double / triple indirect

Slots that point to a block of pointers (one, two, or three levels deep), multiplying reach by the fan-out (1024) at each level.

Index block

A data block used to hold pointers rather than file data — the building block of every indirect level.

Allocation is only half the story. Every time a file grows or is created, the file system has to find blocks that are not already in use — and every time a file shrinks or is deleted, it has to return those blocks to the pool. How it tracks the free pool decides how fast allocation is and how the disk ages. There are two classic schemes.

Bitmap (bit vector)

One bit per block: 1 for used, 0 for free. Finding free space is a scan for zero bits; freeing a block is clearing one bit. Compact — a 100 GB disk of 4 KB blocks needs a bitmap of only a few megabytes — and it makes finding contiguous runs easy, because adjacent free blocks are adjacent zero bits.

Free list

The free blocks themselves form a linked list, each pointing to the next free one. It costs no extra space (the pointers live inside blocks that are free anyway) but you cannot easily ask "is there a run of 8 free blocks here?" — the free blocks are wherever they happen to be, in no particular order.

Most modern file systems favour bitmaps, often grouped so the allocator can quickly find a region with enough contiguous free blocks to keep a file’s data physically close together. That last goal matters more than it first appears: even though the inode lets you place a file’s blocks anywhere, you still want them near each other so sequential reads stay fast. The bitmap makes it cheap to look for clustered free space and to try to keep each file’s blocks in one neighbourhood.

But here is the unavoidable truth: over time, any writable file system fragments. Files are created, extended, and deleted in an unpredictable interleaving, and the free space — and therefore newly written files — gets sprinkled across the disk. On a spinning disk this means the head must seek back and forth to read a single file, and performance quietly degrades. This is why "defragmenting" was a real chore on old Windows/FAT systems. Unix file systems fragment far less, because their allocators deliberately spread files out with room to grow and keep related data in the same block group — prevention rather than cure.

SSDs change the physics but not the principle. There is no head to seek, so fragmentation costs far less, and manually defragmenting an SSD is pointless and even harmful (it burns write cycles). But the allocator still wants large contiguous free regions, now for a different reason: the flash translation layer erases in big blocks, and the TRIM command that tells the SSD which blocks are free is exactly the file system reporting its free-space map to the device. Free-space management never goes away; it just changes what it is optimising for.

Now the hardest problem in the whole chapter, and the one that separates a real file system from a toy. A single logical operation — create one file — is several separate block writes underneath: mark an inode used in the bitmap, write the inode’s contents, mark data blocks used, and add the name-to-inode entry in the directory block. The disk does these one at a time. If the power dies, or the kernel panics, after some of them but before the rest, the on-disk structures are left mutually inconsistent.

Consider the failure concretely. Suppose we mark the inode as allocated and write it, but crash before adding the directory entry. Now there is an inode consuming a slot and blocks that no filename points to — a leaked, orphaned file. The opposite ordering is worse: a directory entry that points at an inode that was never properly initialised, so opening that name reads garbage. Either way the file system is corrupt, and the corruption is silent until something trips over it.

The old cure was fsck — the file-system check — a program that scans the entire volume at boot after an unclean shutdown, cross-checking every inode, directory, and bitmap to find and repair such inconsistencies. It works, but it is agonisingly slow: on a multi-terabyte disk fsck can take hours, and until it finishes the volume is unavailable. As disks grew, "scan everything on every crash" stopped being acceptable. We needed a way to make a group of writes effectively atomic — all or nothing.

The answer is journaling, and it is one of the great ideas in systems. Before touching the real structures, the file system first writes a description of the entire change to a dedicated journal (a log) region, then writes a single small commit record. Only after the change is safely and completely in the journal does it write the changes to their real home locations — and once those are done, the journal entry is discarded. This is write-ahead logging: the intention is durably recorded before the change is applied.

The magic is what happens on crash. Instead of scanning the whole disk, the file system just looks at the journal. If a change has a complete commit record, it is replayed — reapplied to the real structures, harmlessly repeating any writes that already landed. If a change was only half-written to the journal with no commit record, it is discarded entirely, as though it never happened. Either way the file system returns to a consistent state in seconds, not hours, because recovery reads only the small journal, not the entire volume.

Metadata journaling

Log only the metadata changes (inodes, bitmaps, directories), not file data. Fast and the common default (ext4’s ordered mode); it guarantees a consistent structure, though the newest data bytes may still be lost.

Full data journaling

Log the file data too, so both structure and contents survive a crash. Safer but slower — every data write happens twice, once to the journal and once to its home.

fsck vs journal replay

The old way scans the whole volume to find inconsistencies; the journal way replays a tiny log and is consistent in seconds. Journaling does not eliminate fsck — it makes it a rare last resort.

A file system that touched the disk on every operation would be unusably slow, so the kernel leans hard on RAM. The page cache keeps recently used file blocks in memory, so repeated reads never reach the disk at all. Read-ahead notices sequential access and prefetches the blocks you are about to ask for, turning a series of reads into one smooth stream. And writes are buffered too: write() typically just marks a page dirty in memory and returns immediately, with the kernel flushing dirty pages to disk a little later in the background — this is a delayed (or write-behind) write.

Delayed writes are a massive performance win and a genuine danger, and every engineer must understand the gap. Between the moment write() returns "success" and the moment the data actually reaches durable storage, there is a data-loss window — if the power fails in that interval, the write that your program was told succeeded is simply gone. For most files this is a fine trade. For a database committing a transaction, or a mail server accepting a message, it is unacceptable, and the fix is one syscall: fsync(fd), which blocks until that file’s data is truly on disk. This is the same fsync we met in the system-calls chapter, and now you can see precisely what it forces past — the page cache and the delayed-write buffer.

Modern file systems also sharpen the on-disk structures themselves. The inode’s array of individual block pointers is wasteful for large, contiguous files — thousands of pointers to describe one big video. Ext4 replaced them with extents: a single record of "start block + length" describing a whole run at once. It is contiguous allocation’s compact descriptor, brought back safely inside the indexed model — fewer pointers, less metadata, faster large-file I/O.

The most interesting modern shift is copy-on-write. Instead of overwriting a block in place, file systems like ZFS and Btrfs write the modified data to a new free block and only then update the pointers to reference it, leaving the old block untouched. Because the old version is never destroyed until the new one is safely written, the file system is always consistent on disk without a separate journal — a crash simply leaves you at the last complete state. Copy-on-write also makes instant snapshots almost free: keep the old pointers and you have a frozen view of the file system as it was, sharing all unchanged blocks with the present.

• ▸The disk speaks only in numbered blocks; the entire file system is software building files, directories, and inodes on top of that array — and it must survive power loss.
• ▸Allocation evolved from contiguous (fast but fragments) to linked (no fragmentation but slow random access) to FAT (links pulled into one cacheable table) to the indexed inode (direct access with tiny cost for small files, terabytes of reach for large ones).
• ▸Free space is tracked with bitmaps or free lists; every writable disk fragments over time — a real cost on HDDs, a near non-issue on SSDs.
• ▸Journaling / write-ahead logging makes multi-block updates atomic and turns crash recovery from an hours-long fsck into a seconds-long log replay — the same idea as a database’s transaction log.
• ▸Caching, read-ahead, and delayed writes make file systems fast, at the cost of a data-loss window that only fsync closes.

Why should a working software engineer hold all this? Because the file system sits under every service you deploy, and its behaviour leaks into yours. When you wonder why your database insists on fsync at every commit, why an SSD does not need defragmenting, why "the write succeeded but the data was gone after the crash", or why millions of tiny files strangle a build server — the answer is in this chapter. The write-ahead log you just learned is the same mechanism that makes your database durable, and that connection is exactly what the capstone builds on.