Part 5 of 7 · 2 min read
Directory entries
Think of a phone book on paper. Each line holds a name, a number and a note about the kind of entry. To remove a person, you do not tear out the page: you strike the line. The analogy stops in one place: the line of a phone book stays readable after it is struck, while a freed directory entry may be reused.
In plain words: The data blocks of a directory hold a list of directory entries. Each entry has the inode number, the length of the entry (rec_len), the length of the name, a one-byte type (file, directory, link) and the name itself. Entries are packed one after another. When a name is removed, the entry before it is stretched to cover its space, or the inode number of the entry is set to 0. The inode is not touched by the removal of the entry, except that its link count falls by 1.
A worked example. debugfs -R "ls -l /" on the test image lists the root directory with the inode number, the mode, the link count in brackets, the size and the name:
2 40755 (2) ... 4096 .
2 40755 (2) ... 4096 ..
11 40700 (2) ... 16384 lost+found
12 100644 (1) ... 1 one.txt
13 100644 (1) ... 10000 ten.bin
14 100644 (1) ... 1048576 meg.bin
15 40755 (2) ... 4096 sub
The names are in the directory, and the inode number gives the link to section 3. The directory's own size, 4,096, is one block. lost+found is 16,384 bytes: four blocks that mkfs set aside, so that fsck can have room to put recovered files.
The key lines. To delete one.txt, the file system (1) removes its entry from the root directory's block, (2) lowers the link count of inode 12 to 0, and (3) frees the inode in the inode bitmap and the data block in the block bitmap. That is three separate writes to three places on the disk. If the machine stops between them, the structures disagree. Page 4 shows what happens then and how journaling avoids it.
Directory entry
A directory entry is one record in the data of a directory. It holds an inode number, the length of the record, the name and a type byte. Removing a file's name removes or merges its entry and lowers the inode's link count.
Example: the entry (13, "ten.bin") in the root directory points to inode 13.
Common mistake
The size shown for a directory by ls -l is the size of its entry list in bytes, and not the sum of its files. A directory of 3 files and a directory of 3,000 files can show the same size of 4,096 until the entries no longer fit in one block.
Check yourself:
1. What does one directory entry hold?
2. How many separate places on disk must be changed to delete a file?
3. Why is lost+found larger than an ordinary new directory?