File Systems

A file system is the layer that turns a path like /home/user/notes.txt into bytes on a disk. It keeps a file's contents in data blocks, keeps its metadata in a small record called an inode, and keeps its name somewhere else entirely: in the data of the directory above it. The name is not part of the file.

Picture a coat check. Your coat hangs in the back on hanger 7. The attendant's book at the counter has one line in it: notes.txt → 7. The coat itself carries no label with your name on it, and it never will. Everything you can ask about the coat — how heavy it is, how many tickets have been issued for it, which hooks it occupies — is written on a tag attached to the hanger. The name lives at the counter, and only at the counter. That one split explains nearly everything a file system does, including several things that look like bugs until you know it.

How File Systems Work

This page animates a scale model of vsfs, the teaching file system from OSTEP: thirteen blocks of 4 KB. Block 0 is the superblock, the header that says how the rest is laid out. Blocks 1 and 2 are two bitmaps, one bit per inode and one bit per data block, recording what is in use. Blocks 3 and 4 are the inode table, eight inodes with four packed into each block. Blocks 5 through 12 are the data region, D0 through D7, where actual bytes live.

An inode is the file. It holds the type (file or directory), the size in bytes, the link count, and the numbers of the blocks holding the contents. On a real system it also holds permissions, ownership and three timestamps. What it does not hold, on this model or on yours, is a name.

So where does the name live? In a directory. And a directory is not a special kind of object: it is an ordinary file whose data blocks happen to contain a table of name → inode number pairs. Root's inode is i0, its data sits in D0, and reading D0 gets you two rows: home → i3 and readme.txt → i2. That is the entire mechanism. Directories are files that hold the phone book.

Which means opening a path is a loop, and the loop has a price. The kernel starts from the one number it knows without looking anything up — the root inode number, fixed by the file system's format. Then, for each component of the path, it does exactly two reads: one to fetch that directory's inode (which says where its data lives), and one to fetch that data (which says what number the next name maps to). Matching the name inside that block is free, because you already paid to bring the block into memory. After the last component, one more read fetches the file's own inode.

Two reads per component, plus one. 2 × depth + 1, on a cold cache — which is how this page models every lookup, and the reason the numbers here are higher than the ones you would measure on a warm machine. Nothing in that formula mentions the size of the file, and that is the first thing worth noticing: opening a 4 GB video costs exactly what opening an empty file at the same depth costs.

A File System Walk, Step by Step

The default run is a three-line program against the disk shown on screen — open("/home/user/notes.txt"), then read, then unlink. The disk is deliberately scattered: root's data is in D0, home's is in D1, user's is in D3, and the file's two blocks are D4 and D5. A path is contiguous. A disk is not.

Reads 1 and 2 — resolving home. Read inode 0: a directory, pointing at D0. Read D0: two rows. The row home → i3 is the answer, and the lookup itself costs nothing. Note what has been read so far: two blocks, neither of which is your file.

Reads 3 and 4 — resolving user. Identical shape one level down. Read inode 3, which points at D1. Read D1, which holds user → i5.

Reads 5 and 6 — resolving notes.txt. Same climb again, and the animation compresses it to a single fast beat because the rule is established: read inode 5, read D3, find notes.txt → i7.

Read 7 — the file itself. Inode 7: a file, 8,192 bytes, link count 1, blocks D4 and D5. This card is the file. Read the fields and notice the absence — there is no name anywhere in it. open returns file descriptor 3, which is a handle on inode 7.

Seven disk reads, and you have received zero bytes of notes.txt. The header counter says so the whole way down: your data: 0 B.

Reads 8 and 9 — the bytes. read(fd 3) needs no path and no walk; the descriptor already holds the inode. Its two pointers say D4 and D5, so two reads bring back 8,192 bytes. Nine reads in, two of them were about your data.

The delete. unlink("/home/user/notes.txt") walks the whole path again — reads 10 through 15 — because nothing here caches a lookup. The walk ends at user's table in D3, not at the file: the thing unlink edits is the parent directory. Then four writes in a specific order:

1. Write D3, removing the row notes.txt → i7. At this instant the file is gone from ls, and nothing whatsoever has happened to inode 7 or its blocks.
2. Read inode 7 (read 16): to change a counter you must first fetch it.
3. Write inode 7, dropping the link count from 1 to 0. In this model, which omits open-file references, that number decides what happens next. A real open descriptor would keep the unlinked file alive.
4. Because it reached 0, write both bitmaps: clear the D4 and D5 bits, clear the i7 bit. The bitmaps are held in memory from mount, so this costs no reads.

The run ends at 16 reads and 4 writes. Twenty disk I/Os, of which exactly two carried bytes you asked for. The rest was the file system finding a name and then unfinding it.

Now look at what the last beat leaves on screen. D4 and D5 are marked free, and they still contain the file's text. Freeing a block clears a bit in a bitmap; it does not touch the block. The bytes sit there until something else is allocated over them, which is why undelete tools work at all, and why "delete" and "erase" are different words on every file system that respects your time.

What rm Actually Removes

Load the Two names scenario and watch the same disk take a hard link. link("/home/user/notes.txt", "backup.txt") performs the usual seven-read walk to find inode 7, then does two writes: it adds the row backup.txt → i7 to D3, and it bumps inode 7's link count from 1 to 2. No data block is read, copied, or written. Nothing is duplicated, because there is nothing to duplicate — the second name adds a directory entry pointing at the existing inode; it does not add another copy of the file contents.

Then the same unlink as before runs on notes.txt. The row comes out of D3, the count drops from 2 to 1, and the free branch does not execute. No bitmap is touched. Open the file through backup.txt and the walk lands on inode 7 again, reads D4 and D5, and hands back the identical 8,192 bytes. Both names always were the same file, which is why the animation gives them the same colour: the colour belongs to the inode, not to the name.

Back at the coat check: two tickets, one coat. Tearing up one ticket does not destroy the coat. The attendant throws it out when the last ticket is gone, and never before.

That counter has a sibling this model does not draw, and it is the answer to a question that bites people in production: why deleting a huge log file frees no space at all while a process still has it open. There, the link count really has hit zero and the directory entry really is gone — ls and du cannot see the file. What holds the blocks is a second count, of open descriptors on the inode, kept in memory rather than on disk. The kernel frees the blocks when both counts are zero, which is when the last process exits or closes the descriptor. rm removes a name. Whether it removes a file is a question about arithmetic.

Edge Cases

• A path that misses costs money. Run the ENOENT scenario. open("/home/guest/diary.txt") resolves home normally, reads home's directory block, and finds no guest. The walk dies there, four reads already spent and not refunded. open reports only ENOENT; it does not say which component was missing — the red chip on the canvas is the model marking where the walk stopped. Failed opens are not free, which is why a program that stats fifty candidate paths to find a config file is doing fifty walks.
• Opening a directory is opening a file. Type /home/user into the custom path box. The walk resolves it, open returns a descriptor on inode 5, and its data block is a table of names. Then read fails with EISDIR. Neither half is a trick of the model: on Linux you can open a directory and inspect metadata with fstat, and read refuses it because the kernel hands out directory entries through readdir, parsed, rather than as raw block bytes.
• A file in the middle of a path. Type /readme.txt/x. The walk reads inode 2, finds a file where it needed a directory, and fails with ENOTDIR, three reads already paid.
• One write is three writes. The Append one block scenario adds 4 KB to the file. That means marking a block allocated in the data bitmap (write one), putting your bytes in it (write two), and updating the inode's pointer list and size (write three). Two thirds of that traffic is bookkeeping, and it has to happen in an order that survives a crash, which is exactly what journaling exists to guarantee.
• The walk is repeated in full, every time. Path-based operations in these scenarios re-walk from root; read(fd) uses the already resolved inode, and the read counter climbs accordingly. Real kernels do not work this way: a dentry cache holds recently resolved path components in memory, so the second open of a hot path usually touches no disk at all. The model pays full fare so the price stays visible, and so you can see what the cache is actually buying.
• Depth is the cost, not size. The Shallow path scenario opens /readme.txt: three reads instead of seven, for a file whose size the walk never consulted. The difference between them is two directory levels. This is why deeply nested node_modules trees are slow to traverse and why a build tool that stats every file in a deep tree spends its life in path resolution.

Common Mistakes

• Thinking a file has a name. It has an inode number. Names are rows in directories, and a file can have several or, briefly, none at all. Once you hold this, renaming a 4 GB file for free stops being surprising: a same-filesystem rename usually changes namespace metadata without copying the file data; its exact metadata writes depend on directories, replacement targets, and filesystem design.
• Thinking rm erases data. It removes a directory entry and decrements a counter. Even when the count hits zero, the bytes stay on the medium until they are overwritten. Secure deletion is a separate operation, and on an SSD it is not even reliably possible from the file-system layer, because wear levelling means the drive decides where your data physically lives.
• Confusing hard links with copies, or with symbolic links. A hard link is a second name for the same inode: same size, same blocks, same permissions, and no way to tell which name came first. A symbolic link is its own tiny file whose contents are a path string, so it can point across file systems and can dangle when its target disappears. A hard link can do neither, which is the price of not being a copy.
• Assuming a directory listing tells you what is on disk. ls shows names. The disk stores inodes and blocks. A file that is still held open by a process, or reachable through another name, is on the disk without being in the listing you are looking at.
• Forgetting that inodes run out separately from space. This model and some filesystems use a fixed inode allocation determined at creation; others allocate inode-like records dynamically. Fill it with millions of tiny files and you get "no space left on device" with a df that shows plenty of free bytes. df -i is the command that tells you what actually happened.
• Treating path length as free. Every component is two reads on a cold cache. That cost is invisible on a warm machine and painfully visible when you are walking a network file system, or opening a million paths in a cold container image.

A Note on Simplification

This is a teaching model, not a simulator. Thirteen blocks and eight inodes stand in for structures with billions of each. The inode here has four direct pointers, which caps a file at four blocks; real inodes reach large files through indirect blocks (ext2/ext3) or extents (ext4, XFS, APFS), and that indirection is its own lookup mechanism with its own costs. Root is inode 0 here for readability; the ext family uses inode 2.

Directory lookup is drawn as a linear scan through a table, which is what small directories really do. Large directories are not: ext4 uses hashed B-trees (dir_index), and other file systems use their own trees, so a lookup in a directory with a million entries is not a million comparisons.

Nothing here caches except the two bitmaps, which stay in memory from mount. Real systems cache aggressively at several layers — the dentry cache for path components, the inode cache, the page cache for data — and those caches are the reason the numbers on this page are not the numbers you measure. There are also no permissions, no timestamps, no ownership, and no journaling, and no in-memory open-file table: the on-disk link count is the only reference this model counts. The order of the four writes in unlink matters enormously for what happens if the machine loses power halfway through, and crash consistency is a subject large enough to deserve its own page.

Measuring it on your own machine

Every claim here has a command behind it:

stat notes.txt          # inode number, size, link count, block count
ls -i                   # the name → inode mapping, straight from the directory
ln notes.txt backup.txt # watch the link count go to 2, with no data copied
df -i                   # inodes used and free, separately from bytes

On Linux, strace -e trace=openat,read ./your-program shows path-based and descriptor-based system calls; it does not expose every internal lookup or physical disk read, and filefrag -v shows the extents behind a large file. On macOS, stat -f '%i %l %z' gives the inode number, link count and size, and fs_usage -f filesys shows the file-system calls a running process makes. The link count moving from 1 to 2 when you create a hard link, with du reporting no additional space used, is the whole lesson in two commands.