CSE Roadmap

Core tier · about 3 hours · 7 parts

Part 3 of 7 · 2 min read

Directories

Think of the index at the back of a book. It lists a word and a page number. Looking up a word gives the place, and the same page can appear under many words. The analogy stops in one place: the index of a book is printed once, while a directory changes whenever files are created or removed.

In plain words: A directory is a special file whose contents are a table of entries. Each entry has a name and an inode number. Every directory has two entries that the system makes itself: . (the directory itself) and .. (its parent). The tree of a whole file system starts at the root directory, which has a fixed inode number (2 on ext4). Looking for a name in a directory means scanning or searching its table for that name.

A worked example. On the test file system the root directory has inode 2. lost+found has inode 11 and a link count of 2. After mkdir d, the new directory got inode 12 and link count 2: its entry in the root, and its own . entry. The root's link count rose from 3 to 4, because d/.. points to it. When d/e was added, the count of d rose to 3. A tree with t/a/b and t/c gave counts of 4 for t (its name, its ., and the .. of a and c), 3 for a and 2 for b and c.

The key lines. The rule for a directory is: link count = 2 + the number of its subdirectories. It follows from the entries above. A file that is not a directory has one link for each name.

Directory

A directory is a file whose data is a list of entries, each pairing a name with an inode number. It lets the OS turn a name into the file that the name refers to. Every directory also contains the entries . for itself and .. for its parent.

Example: the root directory of the test file system holds the entries ., .. and lost+found (inode 11).

Check yourself: 1. What does a directory entry hold? 2. Why does a new empty directory have a link count of 2? 3. A directory has 5 subdirectories. What is its link count?