File Systems

A file system turns a flat array of disk blocks into names, directories and files. The key idea is a split: names live in directories, data lives behind inodes. In this lesson your program walks a Unix-style directory tree whose directories are stored as raw bytes in the xv6 on-disk format, and resolves path names to inode numbers exactly as the kernel's namei does.

Inodes and directories

An inode is the file's identity: its type (file or directory), size, link count and the list of disk blocks holding its data. It has a number, but no name. A directory is a special file whose content is a list of directory entries, each pairing a name with an inode number. In xv6 every entry is 16 bytes:

bytes 0-1    inode number, little-endian (0 means "this slot is empty")
bytes 2-15   name, up to 14 characters, padded with NUL bytes

A directory entry for inode 2 named etc is 02 00 65 74 63 00 00 00 00 00 00 00 00 00 00 00. A 14-character name uses the whole field with no terminating NUL, so the reader must stop at 14 bytes as well as at a NUL.

Deleting a name just writes inode number 0 over the entry. The slot is reused by the next file created in that directory, so a directory can contain gaps, and a name may appear in a dead slot that must be skipped.

Every directory contains two special entries stored like any other: . (itself) and .. (its parent). The root's .. points to the root. Because they are real entries, the lookup code needs no special case for them.

A name is attached to an inode by a link. Several entries, in the same or different directories, can name one inode (a hard link); the inode's link count says how many, and the file's data is freed when it reaches zero.

Path resolution

To resolve /etc/passwd:

1. Start at the root inode, number 1 in xv6.
2. Split the path at /. Empty pieces (a leading slash, //) are skipped.
3. For each component, the current inode must be a directory (else ENOTDIR). Scan its entries for a live slot with that name. No match is ENOENT. A match moves the current inode to the entry's inode number.
4. The answer is the final inode number.

Each component costs one directory read and one inode lookup, which is why kernels keep a dentry cache of recent lookups. Two more rules: a component longer than the 14-character limit is ENAMETOOLONG, and a path with a trailing slash (/etc/) insists that the result is a directory.

A worked trace

Root (inode 1) holds .->1, ..->1, etc->2, hello.txt->3. Directory etc (inode 2) holds .->2, ..->1, passwd->4.

Beyond this lesson

A real file system also needs a free-block bitmap, a log or journal so a crash cannot leave it half-updated, permission bits, and symbolic links (an inode whose content is another path, which makes resolution recursive). Mounting joins several file systems into one tree by redirecting a directory to another file system's root. The next lesson looks at how an inode finds its data blocks.

Common mistakes

• Matching a name by prefix, or reading past the NUL.
• Treating inode number 0 as a valid entry.
• Handling . and .. specially instead of finding them in the directory.
• Forgetting that a file in the middle of a path means ENOTDIR, not ENOENT.

Your exercise

The starter parses the disk image lines and handles output. You write the directory lookup and path walk.