The name is not in the file

Two structures, and the gap between them

A UNIX file is stored as two separate things, and almost every surprising behaviour in the rest of this course comes from the gap between them.

A directory is a file whose bytes are a table. Each row — a directory entry — has exactly two useful fields: an inode number and a filename. That is all. A directory entry does not record the file's size, its owner, its permissions or where its data lives; it records a number and a name.

An inode is a fixed-size record in a table on the disk called the i-list, and the inode number is simply its index into that table. The inode holds everything the directory entry does not:

• the file's type (ordinary, directory, symbolic link, device, …) and its access permissions
• the owner's user ID and the group ID
• the link count — how many directory entries name this inode
• the size in bytes, and the timestamps
• the addresses of the data blocks: a handful of direct pointers, plus one or more indirect pointers to blocks that hold nothing but more pointers, which is how a small fixed-size record can describe a very large file

And here is the fact the whole module rests on. The filename is not in the inode. Search an inode for the string a.c and you will not find it, because a name is something a directory says about a file, not something the file knows about itself. A file with no name at all is perfectly well formed; so is a file with three equally valid names. Once you have accepted that, hard links, symbolic links, what rm does and what mv does all stop being rules to memorise and become consequences.

Worked example — resolving /home/ada/a.c by hand

When you name a file, the kernel does not look the string up in an index. It walks the tree one component at a time, alternating between directory entries and inodes:

1. The pathname begins with /, so start at the root inode, whose number the kernel knows without being told (it is fixed for a mounted file system).
2. Read that inode. It says: type d, and the data lives in these blocks. Read those blocks; they are the root directory's table of entries.
3. Search the table for the string home. Found: inode 2 (say). The name stops mattering now — from here on the kernel carries a number.
4. Read inode 2. Type d, here are its blocks. Read them; search for ada. Found: inode 1841.
5. Read inode 1841. Type d, here are its blocks. Read them; search for a.c. Found: inode 4271.
6. Read inode 4271. Type -, permissions rw-r--r--, size 8192, link count 1, and these are the data blocks. The walk is over; the data is reachable.

Count what happened: one directory entry lookup and one inode read per component. Notice step 3 in particular — the moment a component is resolved, the name is discarded and only the inode number travels onward. That is why two different names can lead to the same step 6, and why a name can be removed without touching anything the file is made of.

You can watch the last step of this happen:

$ ls -i a.c b.c
4271 a.c   5008 b.c
$ stat -c '%i %h %s %U %n' a.c
4271 1 8192 ada a.c

ls -i prints the inode number in front of each name — the number from step 5. stat reads the inode itself and prints fields out of it: %i the inode number, %h the link count, %s the size, %U the owner. Every one of those came from the inode. The only thing on either line that came from the directory is the name.

What the link count is counting

The third column of an ls -l line, the one nobody explains, is the inode's link count: the number of directory entries that name this inode. A newly created ordinary file has a count of 1 — one name. Give it a second name and the count becomes 2. Remove a name and it drops. When it reaches 0, and only then, the kernel frees the inode and the data blocks.

Directories are counted the same way, which is why a brand-new empty directory has a link count of 2 rather than 1: its own . entry names it, and so does the entry its parent holds for it. Each subdirectory you create inside it adds a third, a fourth, and so on, because every subdirectory's .. is one more entry naming the parent.

Inode numbers are local

An inode number is an index into one file system's i-list. It has no meaning outside that file system, and two files on two different mounted file systems routinely carry the same inode number without being related in any way. This one fact is why a hard link cannot cross a file system, why mv behaves differently across a mount point, and why find / -inum 4271 may print several unrelated files. Everything in the next four lessons follows from it.