Source: Operating Systems: Three Easy Pieces (OSTEP) — Chapter 40, Arpaci-Dusseau & Arpaci-Dusseau

File System Implementation

vsfs (Very Simple File System) is a teaching UNIX-style FS: on-disk structures, access paths, and policies you’ll meet in real systems (ext*, XFS, ZFS, …).

Crux: what must live on disk, and how do open / read / write map onto it?

Mental model

(1) Data structures — how is data/metadata laid out? (2) Access methods — which blocks are read/written on each syscall?

Overall organization

Divide the disk into 4 KB blocks. vsfs regions (tiny 64-block example):

Region	Role
Superblock (S)	Size, inode/data starts, magic — read on mount
Inode bitmap (i)	Which inodes are free
Data bitmap (d)	Which data blocks are free
Inode table (I)	Array of inodes (e.g. 256 B → 16/block)
Data region (D)	File and directory contents

i-number → byte address: inodeStart + inumber * sizeof(inode) (then convert to sector).

The inode

Holds type, size, links, mode/owner, times, and where blocks live.

Multi-level index (common): fixed direct pointers, then indirect, double, triple. With 4 KB blocks and 4-byte pointers, 12 directs ≈ 48 KB; +indirect ≈ +4 MB; doubles/triples go multi-GB. Imbalanced because most files are small [A+07].

Extents (ptr + length) are more compact when allocation is contiguous (ext4, XFS). FAT-style linked lists store “next block” in a table — weak for random access without the in-memory FAT.

Directories are special files: rows of (inum, name, …) plus . / ... Deletes leave holes (often inum=0); reclen helps reuse space. Fancy FSes use B-trees for large dirs [S+96].

Free space

Bitmaps (vsfs), free lists, or B-trees of free extents (XFS). Allocation may preallocate a run of blocks for sequential layout (ext2/3 heuristic).

Access paths

open("/foo/bar") — start at well-known root inode (usually 2); for each path component read directory inode → directory data → next i-number; finally load file inode, check perms, allocate fd.

read() — use inode pointers (and cached offset); may update atime. Bitmaps are not consulted on pure reads.

write() that allocates ≈ 5 I/Os: data bitmap R/W, inode R/W, data W. create() is worse (inode bitmap, new inode, directory data, directory inode, …).

Quiz

Rank the sequence

1 / 1

Order the steps of open("/foo/bar") walking the path (top = first).

OrderDrag the handle to rearrange — top should be first.

1Read the directory data of "foo" to find "bar"’s inumber
2Read the root directory’s data to find "foo"’s inumber
3Read the root inode (usually inumber 2)
4Allocate a file descriptor
5Read the inode for "foo" using the inumber just found
6Load the file inode and check permissions

Drag items into the correct order (or use ↑↓), then check.

Caching and buffering

Path walks thrash without a block/page cache. Modern OSes use a unified page cache (dynamic share with VM).

Reads can be filtered entirely by cache. Writes must eventually hit disk for durability, but write buffering (often 5–30 s) batches, schedules, and sometimes avoids I/O (create-then-delete). Trade-off: crash loses buffered updates — apps that care call fsync / direct I/O.

Interactive

Try: on-disk layout · inode pointers · open/read/write I/O · cache trade-offs.

Check your understanding

Quiz