Directory Implementation

A hash table

Hash the name to a number, and keep the entry in the bucket with that number. The search is then one hash and a short chain instead of a scan.

The weakness is the fixed size of the table. The number of buckets is chosen when the directory is made; as the directory grows, the chains grow with it, and the search becomes linear again. The answer is to rehash into a larger table, which means recomputing every entry's bucket, so it is done rarely and it is expensive when it is.

The same directory, with 64 buckets

About 16 comparisons instead of 500, and usually one block read instead of eight, because a bucket and its chain are small enough to sit together.

Real systems do better again: ext4's directories are hashed B trees, which keep the fast lookup and also grow gracefully. The feature is recorded in the superblock, and it is in the image built in Chapter one hundred five:

$ mkfs.ext4 -q -F -b 1024 -I 128 -O ^has_journal dir.fs 4096 2>&1 | grep -v deprecated
Creating regular file dir.fs
$ dumpe2fs -h dir.fs 2>/dev/null | grep '^Filesystem features' | tr -s ' ' '\n' | grep -c dir_index
1

The 1 is the dir_index feature being present: this file system indexes its directories rather than scanning them.

A directory is a file that grows

The measurement that makes the whole chapter concrete. 120 files are created in the root directory of the image, and the directory's own size is read from its inode before and after.

$ printf 'x\n' > one.txt
$ debugfs -R "stat <2>" dir.fs 2>/dev/null | awk '/^User/ {print "the root directory is", $6, "bytes"}'
the root directory is 1024 bytes
$ { for i in $(seq 1 120); do printf 'write one.txt file-%03d\n' "$i"; done; } > script.debugfs
$ debugfs -w -f script.debugfs dir.fs > /dev/null 2>&1; echo done
done
$ debugfs -R "stat <2>" dir.fs 2>/dev/null | awk '/^User/ {print "after 120 files the root directory is", $6, "bytes"}'
after 120 files the root directory is 2048 bytes
$ debugfs -R "ls /" dir.fs 2>/dev/null | tr -s ' ' '\n' | grep -c '^file-'
120

One block became two. The root directory is inode 2, as Chapter one hundred five showed, and it is an ordinary file: it was 1024 bytes, one block; 120 more names did not fit, so the file system gave it a second block and it is now 2048.

123 entries, counting ., .. and lost+found, in 2,048 bytes: about 17 bytes each, which is a name of a few characters, an inode number, and the lengths that go with them. The arithmetic of the earlier section was not a model of something else: it is this.

Distinctions that carry marks

What it does not mean

A directory is not a special kind of object. It is a file, and it grows in blocks like any other, as the measurement shows.

A hash table does not remove the search. It makes it short.

A linear list is not always wrong. Most directories hold a few dozen entries, where a scan of one block is cheaper than a hash.

Rehashing is not something the user sees. It is the file system's own work, and it is why the fixed table size is tolerable.

The 16 bytes an entry is not a rule. It depends on the length of the names, and the image measured about 17.

Quick revision

• Every path resolution is a directory search, so the structure matters more than any other

choice in the file system.

• A linear list of name and inode number: a search costs n / 2 on average and n when

the name is absent, so creating a file costs a full search.

• Deleted entries are marked unused, filled by the last entry, or kept on a

free list. A sorted list allows a binary search but costs on insertion; real systems use a B tree.

• Worked: 1,000 entries of 16 bytes in 1024 byte blocks is 64 entries a block, about

16 blocks; a search averages 500 comparisons and about 8 block reads.

• A hash table costs one hash and one chain: with 64 buckets, 1000 / 64 = 15.625,

about 16 comparisons. It lists badly in order, and its fixed size means rehashing as it grows.

• ext4 records dir_index in the superblock: its directories are hashed B trees.
• Measured: the root directory was 1024 bytes, and after 120 files it is 2048. With

., .. and lost+found that is 123 entries in two blocks, about 17 bytes each.

Test yourself

1. Why does the directory structure matter so much? Because every path resolution searches

one directory per component, which makes it the most frequent operation in the file system.

1. What does a linear list cost to search, and why is creating a file worse? Half the entries

on average for a successful search; creating a file must prove the name is absent, which means searching all of them.

1. Give the three ways of handling a deleted entry in a linear list. Mark it unused, move the

last entry into the hole, or keep a free list of holes. 4. A directory holds 1,000 entries of about 16 bytes in 1024 byte blocks. How many blocks is it, and what does a search cost? 64 entries a block, so about 16 blocks; a successful search averages 500 comparisons and about 8 block reads.

1. How does a hash table change the cost, with 64 buckets and 1,000 entries? The search is

one hash and one chain of 1000 / 64 = 15.625 entries, about 16 comparisons and usually one block read.

1. Give two disadvantages of a hash table for a directory. Listing the entries in name order

needs a sort, and the table is a fixed size, so the chains lengthen as the directory grows until it is rehashed.

1. What does ext4 do, and how can you tell? Its directories are hashed B trees; the

dir_index feature is recorded in the superblock and printed by dumpe2fs. 8. The root directory of an image was 1024 bytes and became 2048 after 120 files were added. What does that show? That a directory is an ordinary file: the names did not fit in one block, so the file system allocated a second one.