File Systems

A disk is an array of numbered blocks that forgets nothing and understands nothing. A file system is the data structure — literally, a persistent data structure — that turns those blocks into the fiction every program relies on: named files, nested directories, permissions, sizes. This lesson is about the two structures at the core of the Unix design, and the algorithm your exercise implements: resolving a path to the thing it names.

The inode: a file's true identity

Here is the Unix design's sharpest idea: a file's name is not part of the file. The file itself is an inode — a fixed-size record, stored in a known region of the disk, holding:

• the metadata: type (regular / directory / symlink), size, permissions, owner, timestamps
• the link count (how many names point here — hold that thought)
• pointers to the data blocks that hold the actual bytes

Inodes are identified by number, not name. ls -i will show you: every file on your machine is, to the kernel, an integer.

Directories: just tables

So where do names live? In directories — and a directory is nothing exotic: a file whose bytes are a table of name → inode number entries.

inode 2 (directory "/"):        inode 11 (directory "home"):
  "home" → 11                     "alice" → 87
  "etc"  → 12                     "bob"   → 90
  "boot" → 13

Two consequences fall out immediately:

• Hard links: two directory entries can hold the same inode number. Both names are equally "the file"; the inode's link count says how many exist, and the file's storage is reclaimed only when the count hits zero and no process holds it open. (rm doesn't delete files — it deletes names.)
• Symbolic links are the other kind: a tiny file whose content is another path, resolved at lookup time, free to dangle.

Path resolution: the walk

Now the algorithm that makes /home/alice/notes.txt mean something — the one you're about to implement:

1. Start at the root inode (by convention, inode 2 on ext-family filesystems).
2. Take the next path component (home). The current inode must be a directory — if not, fail with ENOTDIR.
3. Look the component up in that directory's table. Missing → ENOENT.
4. The entry's inode number becomes your current inode. Repeat until components run out.
5. Whatever inode you're standing on is the answer.

/home/alice/notes.txt
  inode 2   (dir)  : "home"      → 11
  inode 11  (dir)  : "alice"     → 87
  inode 87  (dir)  : "notes.txt" → 203
  answer: inode 203

Every open() on every Unix machine begins with exactly this loop (plus a per-component permission check, plus symlink detours). It's also a real cost — one lookup per component, potentially one disk read each — which is why kernels keep a dentry cache of recent name→inode resolutions, and why /a/b/c/d/e/f/g is measurably slower to open cold than /tmp/x.

The bigger machine around it

Zoom out and a filesystem has a fixed anatomy on disk: a superblock (filesystem-wide facts: block size, inode count, where things live), the inode table, allocation bitmaps (which blocks/inodes are free — the disk's version of the frame allocator), and the data blocks. Crash midway through an update and these structures disagree with each other — which is why modern filesystems journal: write the intent to a log, then do the update, so recovery replays or discards cleanly.

And one abstraction above it all: the VFS (virtual file system) layer, which defines inode/directory/file interfaces so ext4, tmpfs, network filesystems, and /proc (files that are really kernel data in a costume) all speak one protocol. It's why cat doesn't care what it reads from — and why your path resolver, which works purely on the abstract inode/directory model, is the honest core of all of them.