The idea: a disk is an array of blocks

To a file system, a disk is a row of numbered blocks of the same size (4 KB here). Files, directories and names do not exist on the disk by themselves. The file system builds them by giving each block a job. The simple layout on this page has five parts.

A row of 24 blocks. Block 0 is the superblock, block 1 the inode bitmap, block 2 the data bitmap, blocks 3 and 4 the inode table with inodes 0 to 7, and blocks 5 to 23 are data blocks. Block 5 holds the root directory, block 6 the directory foo, blocks 7 and 8 the file bar.
The 24-block disk of the page: three blocks of bookkeeping, two blocks of inodes, nineteen data blocks.
  • The superblock (block 0) describes the file system: how many blocks and inodes it has, where the inode table starts, and that the root directory is inode 2. It is read once, at mount.
  • The inode bitmap (block 1) has one bit per inode: 1 = in use, 0 = free.
  • The data bitmap (block 2) has one bit per data block.
  • The inode table (blocks 3 and 4) holds the inodes, four per block. An inode is the record of one file: type, size, times, and the numbers of its data blocks. It does not hold the file's name.
  • The data blocks (blocks 5 to 23) hold file contents. A directory is a file too: its data block is a list of entries name → inode number.

Part 1 of the canvas is this disk. A grey head box moves to every block that is read or written, and a counter adds them up. Nothing is cached on this page, so you see every access a cold file system would make.

Reading /foo/bar

The file system starts with one fact: the root directory is inode 2. Everything else it must read. open("/foo/bar") goes:

  1. Read inode 2 (it is in block 3). It says: directory, data in block 5.
  2. Read block 5. The entry foo says inode 3.
  3. Read inode 3. It says: directory, data in block 6.
  4. Read block 6. The entry bar says inode 4.
  5. Read inode 4. It says: regular file, 8 KB, blocks 7 and 8.

That is 5 reads before one byte of the file is seen: two per directory in the path, plus one for the file's own inode. Then each read() of one block reads the inode, reads the data block, and writes the inode back with a new access time. So cat /foo/bar costs 9 reads and 2 writes for a 2-block file (Demo 1: read /foo/bar block by block).

Creating and writing a file

Creating /foo/baz walks to /foo with 4 reads, then changes four different places (Demo 2: create /foo/baz):

StepBlockWhy
Read, then write the inode bitmap1Find a free inode (5) and mark it used
Write the data of /foo6Add the entry baz → 5
Read, then write inode 54Fill in the new inode: file, size 0
Write inode 33The directory /foo changed

In total 6 reads and 4 writes, and still no data block: the file is empty. Appending one block (Demo 3: write the first block of a new file) reads the inode, reads and writes the data bitmap, writes the data block and writes the inode with the new pointer and size: 2 reads and 3 writes for 4 KB of data.

These writes go to different blocks, one after another. If the power fails between them, the bitmap, the inode and the directory no longer agree. How a file system survives that is the topic of How a File System Survives a Crash.

Direct and indirect pointers

An inode has a fixed size, so it has room for only a few block numbers. These are the direct pointers: 3 in this page's inode, 12 in ext2. A bigger file uses an indirect pointer: it names a data block that holds no file data, only more block numbers. With 4 KB blocks and 4-byte block numbers, one indirect block holds 1024 pointers.

In Demo 4: grow past the direct pointers the file baz gets blocks 9, 10 and 11 through its direct pointers. The fourth block needs two free blocks: block 12 becomes the indirect block and block 13 holds the data. From then on every access beyond the direct pointers costs one extra read, of the indirect block.

An ext2 inode with 12 direct pointers reaching 48 KB, a single indirect pointer to a block of 1024 pointers reaching 4 MB more, a double indirect pointer reaching 4 GB more through two levels, and a triple indirect pointer reaching 4 TB more through three levels.
Each level of indirection multiplies the reach by 1024; small files need only the direct pointers.

The pointer layout fixes the largest file. For 4 KB blocks:

PointersBlocks reachedBytes
12 direct1248 KB
1 single indirect10244 MB
1 double indirect1024 × 10244 GB
1 triple indirect1024 × 1024 × 10244 TB

The toy inode on the canvas, with 3 direct pointers and one single indirect pointer, reaches 3 + 1024 = 1027 blocks, which is 4108 KB. The design is lopsided on purpose: most files are small, and a small file is found with no extra read at all.

Four allocation methods

The inode with its pointers is one answer to a general question: how does the file system record which blocks belong to a file? Part 2 of the canvas stores the same files, A, B and C with 4 blocks each, in the four classic ways.

The same file of four blocks stored four ways. Contiguous: blocks 8 to 11 in a row, the directory holds start 8 and length 4. Linked: each block ends with the number of the next. FAT: the next numbers are in a separate table in memory. Indexed: index block 10 lists the data blocks 11 to 14.
The four methods differ only in where the list of a file's blocks is kept.
  • Contiguous: a file is one run of blocks. The directory holds the start and the length. Block i is simply start + i.
  • Linked: the directory holds the first block. Each block ends with the number of the next one, so the blocks can be anywhere.
  • FAT (file allocation table): the same chain, but the "next" numbers are taken out of the blocks and put in one table, which is kept in memory. This is the MS-DOS and USB-stick format.
  • Indexed: each file has an index block that lists its data blocks. The Unix inode is this method, with the first pointers kept inside the inode.

Demo 5: sequential read vs random access reads file C in order, then only its last block. Demo 6: fragmentation deletes A and creates D with 5 blocks. Contiguous has 8 free blocks but no hole larger than 4, so the create fails: that is external fragmentation. The other three put D in blocks that are far apart, and reading D then needs a jump of the disk head.

ContiguousLinkedFATIndexed
Read C in order (disk reads)4445
Read the last block of C1412
Create D after deleting AFails0 1 2 3 120 1 2 3 12Index 0, data 1 2 3 4 15
External fragmentationYesNoNoNo
A file can grow in placeOnly if the next block is freeYesYesYes, until the index is full
Extra spaceNoneA pointer in every blockThe tableAn index block per file

See also How a File System Survives a Crash for the journal that keeps bitmaps, inodes and directories in step, What open() Does: Linux VFS Path Lookup for the kernel's cached path walk, Hard Link vs Symbolic Link for two names on one inode, The Page Cache: read() vs mmap() for why most of these reads never reach the disk, and Disk Scheduling for what a jump of the head costs.

What the page leaves out

Caching: a real kernel keeps inodes, directory entries and blocks in memory, so a warm open() reads nothing from disk. Block groups, which keep a file's inode near its data. Extents (ext4, XFS, NTFS), which replace long pointer lists by a few (start, length) pairs, a mix of contiguous and indexed. Double and triple indirect blocks on the canvas, permissions, link counts, deleting files in part 1, directories larger than one block, the journal, and internal fragmentation (the unused tail of a file's last block).

On the mind map

Open the Operating Systems mind mapOperatingSystemsBoot and program start: from power on to main()Boot and program startProcesses and the kernel: how user code talks to the kernelProcesses and the kernelInterrupts and devices: hardware interrupts the CPUInterrupts and devicesScheduling and deadlock: who runs next, who gets whatScheduling and deadlockVirtual memory: every address is translatedVirtual memoryPhysical memory: who gets which bytes of RAMPhysical memoryFiles and storage: from open() down to the diskFiles and storageDisks and RAID: blocks down to platter or flashDisks and RAIDIsolation and security: limit what a process can doIsolation and securityVFS path lookupVFS path lookupwalk the path one dentry at a timeFile system and crashesFile system and crashesthe journal makes metadata crash safeOn-disk layoutopen /foo/bar = 5 block readsPage cache: read vs mmapPage cache: read vs mmapread copies, mmap maps the cache pageHard link vs symlinkHard link vs symlinkhard: same inode; sym: a path to itCopy-on-write file systemsCopy-on-write file systemsnever overwrite: new blocks, then new rootOpen the Operating Systems mind mapOperating Systemsfrom open() down to the diskFiles and storageVFS path lookupVFS path lookupwalk the path one dentry at a timeFile system and crashesFile system and crashesthe journal makes metadata crash safeOn-disk layoutopen /foo/bar = 5 block readsPage cache: read vs mmapPage cache: read vs mmapread copies, mmap maps the cache pageHard link vs symlinkHard link vs symlinkhard: same inode; sym: a path to itCopy-on-write file systemsCopy-on-write file systemsnever overwrite: new blocks, then new root
This page on the Operating Systems mind map · 57 pages in 9 branches · open it to see the whole map and test yourself in recall mode.