Part V · Chapter 15

File Systems

A disk is nothing but a long row of numbered blocks. Yet you see folders, file names, sizes and dates. All of that is an illusion, carefully built and maintained by a file system: a set of tables, stored on the disk itself, that says which blocks belong to which file. In this chapter we build that illusion and see how it survives a power cut.

Ask a disk for "my holiday photos" and it won't understand. All it knows is "give me block 258,015,456". Something has to translate between the two worlds, and keep track of a lot along the way:

Which blocks belong to each file, and in what order.
Each file's name, size, dates and permissions.
How files are grouped into folders, or directories.
Which blocks are still free for new files.

A file system stores all of this on the disk too, in a few special areas, alongside the files themselves. Let's look at two classic designs: the one from the IBM PC, and the one from Unix.

DOS and the FAT

PC DOS 1.0 used a beautifully simple design. The disk is divided into clusters (one or more sectors each), and there are just two tables:

The directory: one 32-byte entry per file, with its name (8 characters plus a 3-letter extension, like LETTER.TXT), its size in bytes, its date and time, and the number of its first cluster.
The file allocation table (FAT): one entry for every cluster on the disk. Each entry holds the number of the next cluster of the same file, or a special "end" mark, or 0 for "free".

To read a file, look up its first cluster in the directory, then follow the chain through the FAT, one link at a time, like a treasure hunt where each clue tells you where the next one is. To create a file, find free entries in the FAT and link them up. The FAT is so important that the disk keeps two copies of it.

Click a file in the directory and press Read selected to follow its chain. Create and delete a few files, grow one, and watch them get scattered. Then defragment.

Notice what deleting does: it only marks the directory entry as unused and sets the file's FAT entries back to 0. The data itself stays on the disk until something overwrites it. That's why "undelete" programs could often bring a file back, and why deleting a file doesn't really erase it.

Fragmentation

As files are created, grown and deleted, the free space gets broken into small holes, and new files have to be split across them. A fragmented file still works perfectly: the chain finds every piece. But on a hard disk, every jump between pieces means a seek, and Chapter 14 showed how expensive those are. A badly fragmented disk could become several times slower.

So in the 1990s, PC users regularly ran a defragmenter, which shuffled every file back into one unbroken run, and watched its colorful block map slowly tidy itself up for an hour or more. Modern file systems try hard to keep files together from the start, and on an SSD, which has no seeks, fragmentation hardly matters at all.

Unix: inodes

Unix took a different approach, which Linux and macOS still follow today. Everything the system knows about a file, except its name, is kept in a small record called an inode (index node): its size, owner, permissions, times, and the list of blocks that hold its data. Every inode has a number, and the file system keeps a big table of them.

The clever part is the list of blocks. An inode has room for just 15 block numbers. The first 12 point straight at data blocks: enough for any file up to 48 KB, which covers most files. For bigger files, the 13th points to a whole block full of further block numbers, the 14th to a block of pointers to pointer blocks, and the 15th adds one more level.

Pick a file size and see how much of the inode's tree it needs. Blocks are 4 KB, and each pointer is 4 bytes, so one block holds 1,024 pointers.

It's a tree again, just like the page tables of Chapter 10: small files are cheap, and huge ones are possible. Modern Linux file systems like ext4 improve on it with extents: instead of listing every block, the inode says "4,000 blocks starting at block 258,015,456". A single extent can cover 128 MB, and four of them fit right inside the inode.

Directories and paths

So where do names live? In directories, which in Unix are just files with a special job: each holds a list of pairs, a name and an inode number. A path like /home/ademar/notes.txt is followed one step at a time:

Start at the root directory /, which is always inode 2.
Read it, and look up home: that gives another inode number.
Read that directory, and look up ademar; then read that one and look up notes.txt.
Finally, read the file's own inode to find its data.

Each step can mean another read from the disk, so operating systems keep recently used directory entries in a cache in RAM. Because names live in directories and not in inodes, one file can even have several names in different directories, each pointing to the same inode: a hard link.

Surviving a crash

Here's a hidden danger. Creating even a tiny file takes several separate writes to different places on the disk: the directory, the inode, the free-block map, and the data itself. The disk may even do them in a different order from the one the operating system asked for, to save seek time (remember the elevator). If the power fails halfway through, some writes have happened and others haven't.

First, without a journal: step through the writes and pull the plug after the first one, then reboot. Try other moments too. Then switch to the journal and try to break it.

For a long time, the only cure was to check the whole file system after every crash, comparing every directory, inode and bitmap with every other. That's what fsck on Unix and CHKDSK or ScanDisk on Windows did, and on a big disk it could take hours.

The modern answer is the journal, borrowed from databases. Before changing anything in place, the file system first writes a description of all the changes into a reserved area of the disk, followed by a final "commit" record. Only then does it make the real changes. After a crash, it just reads the journal: a committed entry is replayed, an unfinished one is thrown away. Either way, the file system is always either completely before or completely after each operation, and recovery takes seconds. NTFS (1993), ext3 (2001) and ext4 all work this way. Newer designs like Apple's APFS, Btrfs and ZFS go further: they never overwrite anything in place at all, writing new versions to free space instead, a trick called copy-on-write, which also gives them instant "snapshots" of the whole disk.

Meanwhile, inside a real CPU

Programs never touch the file system's tables themselves. They ask the operating system with a system call, using the trap mechanism of Chapter 12. Here is how a Linux program reads 512 bytes from an open file:

; x86-64 Linux: read(3, buf, 512)
mov     eax, 0          ; system call 0: read
mov     edi, 3          ; which open file (a "file descriptor")
lea     rsi, [buf]      ; where to put the data
mov     edx, 512        ; how many bytes
syscall                 ; 0f 05: over to the operating system

# RISC-V Linux: the same call
li      a7, 63          # system call 63: read
li      a0, 3
la      a1, buf
li      a2, 512
ecall                   # 73 00 00 00

Behind that one instruction, the kernel follows the path, finds the inode, works out which blocks to read, checks its cache, and if necessary sends an NVMe command and sleeps until the interrupt arrives. Chapter 20 looks at system calls in detail.

On Linux you can see the inode side of things directly. Here's the file for Chapter 14 of this book, on the computer it was written on:

$ stat chapters/14-disks-and-ssds.html
  Size: 15560      Blocks: 32         IO Block: 4096   regular file
Device: 8,17       Inode: 48903791    Links: 1
$ filefrag chapters/14-disks-and-ssds.html
chapters/14-disks-and-ssds.html: 1 extent found          ← blocks 258015456–258015459
$ ls -id / /home /home/ademar
      2 /                                                ← the root is always inode 2
4194305 /home
4198482 /home/ademar
$ df -T / /boot/efi                                      (columns trimmed)
Filesystem                  Type   Mounted on
/dev/mapper/ubuntu--vg-root ext4   /
/dev/sda1                   vfat   /boot/efi             ← FAT, still going strong

The file is 15,560 bytes, stored in four 4 KB blocks, all in one piece. The disk it lives on has room for 122 million inodes. And the small partition the computer starts from (Chapter 18) is formatted with FAT, a direct descendant of the 1981 original, because it's simple enough for the firmware to read.

Try it yourself

The original FAT used 12-bit entries. How many different cluster numbers can a 12-bit entry hold?
Show answer
2¹² = 4,096. A few values are reserved (0 for free, the end mark and so on), so a FAT12 disk can have a little over 4,000 clusters. That's why FAT had to grow to 16 and then 32 bits as disks grew.
To find the 10th cluster of a file in a FAT file system, how many FAT entries must you follow?
Show answer
The directory gives the 1st cluster; each FAT entry gives the next one. So you follow 9 entries. Jumping into the middle of a big file means walking the whole chain up to that point, one weakness of the FAT design.
With 4 KB blocks and 4-byte block numbers, how big can a file be using only the 12 direct pointers? And adding the single indirect block?
Show answer
12 × 4 KB = 48 KB. The single indirect block holds 4,096 / 4 = 1,024 more block numbers: 1,024 × 4 KB = 4 MB more, so about 4.05 MB in total.
How many directories must be read to open /home/ademar/notes.txt?
Show answer
Three: / (to find home), /home (to find ademar) and /home/ademar (to find notes.txt). Plus the inode of each of these and of the file itself. Directory caches make most of these reads unnecessary.
With a journal, the power fails after the commit record was written but before all the real changes were made. What happens at the next boot?
Show answer
The file system finds a committed entry in the journal and simply replays it, writing all the changes again. Writing a change that had already been made does no harm, so afterwards the operation is complete and the disk consistent.

What we learned

A file system turns a row of numbered blocks into named files and folders, using tables stored on the disk itself.
FAT: a directory gives each file's first cluster; the allocation table chains the rest together, one link per cluster.
Files split into scattered pieces are fragmented, which costs seeks on hard disks.
Unix keeps each file's details in an inode with a tree of block pointers (or extents); directories map names to inode numbers.
Creating a file takes several writes; a journal (or copy-on-write) makes each operation all-or-nothing, so a crash can't leave the disk corrupted.

That completes Part V, and with it the machine's memory, devices and storage. Next we turn to what you look at all day. Part VI starts with framebuffers: how a screen full of pixels is just another piece of memory, from the PC's text mode to millions of colors.