Part 6 of 7 · 3 min read
Walking a path
Walking a path
Think of finding a flat in a big building with a note that says "block C, floor 3, door 7". You go to block C, then to floor 3, then to door 7, and each step uses the sign of the step before. The analogy stops in one place: in a building every sign is already printed, while the OS must read each directory from the disk or the cache.
In plain words: To open /home/ann/notes.txt the OS starts at the root inode (a fixed, known number). It reads the root directory's data, looks for home, and gets the inode of home. It reads that directory and finds ann, then reads ann and finds notes.txt, and gets the inode of the file. A symlink on the way restarts the walk with the stored path. Each step needs the permission to search the directory (Level 10). The result is an inode, which is the thing that open gives to the process as a file descriptor.
A worked example (made up to show the idea). With nothing cached, the lookup of /home/ann/notes.txt reads: the inode of /, the data of /, the inode of home, the data of home, the inode of ann, the data of ann, and the inode of notes.txt. That is 7 reads from the disk, and 6 more would be needed for a path that is two levels deeper. The page cache of Level 8 (page 5) keeps the recent ones, so a second lookup of the same path usually reads none.
The key lines. A deep path costs more lookups, and a long directory takes longer to search. Modern file systems index large directories with a tree or a hash, so a lookup does not scan every entry. The OS also keeps a dentry cache, a cache of recent name-to-inode answers, to skip the walk.
Path resolution
Path resolution is the process in which the OS turns a path name into an inode. It starts at the root or at the current directory and, for each name, looks up the entry in the directory reached so far and continues with the inode found, following symbolic links on the way.
Example: resolving /home/ann/notes.txt finds home in the root, ann in home, and notes.txt in ann.
Interview angle
A common question is "What is the difference between a hard link and a soft link?" A good answer says that a hard link is another directory entry for the same inode, so the data lives until the last name goes, and that a soft link is a separate file that stores a path and can dangle or cross file systems.
Check yourself:
1. Where does the walk of an absolute path start?
2. How many disk reads does a cold lookup of /a/b/c need, if each directory takes two and the file one?
3. What does the dentry cache save?
Words you will meet
| Word | Meaning |
|---|---|
| Inode number | The number that identifies a file inside one file system. |
| Link count | Number of directory entries that point to an inode. |
| Directory entry | A pair of a name and an inode number. |
| Dangling link | A symlink whose target does not exist. |
| Dentry cache | Cache of name-to-inode lookups. |
Quick notes
- A file is bytes plus metadata under an inode number. Names live in directories.
- A directory maps names to inode numbers. It has
.and..entries. - A directory's link count is 2 + its subdirectories.
- A hard link is another name for an inode. Data is freed when the count is 0 and no one has it open.
- A symbolic link is a file that holds a path. It can dangle and can cross file systems.
- A path is resolved one name at a time, from the root or the current directory.