Directory Hash Trees: Indexing Names Without Breaking Enumeration

A directory in the traditional layout is a file whose data blocks hold a sequence of variable-length entries, each with a name and an inode number. Lookup is a linear scan of every entry, which is fine for a directory of twenty files and pathological for one of two hundred thousand. Adding an index is not as simple as adding a hash table, because readdir must continue to return every entry exactly once and the format has always allowed a directory to be read block by block, in order, with no index at all.

The compatibility trick that makes an index possible

The htree design keeps the directory’s data blocks exactly as they were: a linear sequence of dirents. The index is built out of those same blocks, by reinterpreting the first block’s contents as a tree node. The . and .. entries stay at the front of that block; .. is given a rec_len of one block minus twelve bytes, so it covers everything after it, and the index header and index entries live inside that covered region. The block’s remaining dirents move into leaf blocks. Nothing about the block’s size or position changes, so a driver with no htree support reads the block, returns the two dot entries, and skips to the end of it without ever seeing the index.

The trick is only available because the directory format has no separate type marker. A directory is a file whose data blocks happen to be dirents, so a format can rearrange the interior of those blocks as long as the outer shape still parses. The extent tree cannot use the same trick for the inode’s pointer area: the two layouts are distinguished by a magic number, and a driver that does not recognize it must refuse the volume rather than skip over it.

struct ext4_dir_entry_2 {
    __le32 inode;      /* 0 means this slot is unused */
    __le16 rec_len;    /* bytes to the next entry */
    __u8   name_len;
    __u8   file_type;
    char   name[];     /* not NUL-terminated */
};

The rec_len field is what makes the reinterpretation safe. A reader that does not understand the block follows .. to the end of the block in one step. A reader that does understand the block reads the bytes just past the dot entries as a node header, where they carry a hash algorithm identifier, an information length, and an indirect level, followed by the index entries themselves. Interior nodes are hidden the same way: each begins with an eight-byte dirent header whose inode is zero and whose record length spans the whole block, so a reader that does not descend sees one unused entry where the hash map lives.

What the index stores, and why a leaf stores nothing

The index is a tree whose root sits in the directory’s first block, holding entries of the form (hash, block number) sorted by hash. An index entry is eight bytes: a 32-bit hash and a 32-bit block number counted within the directory file, not within the filesystem. Each leaf is an ordinary directory block containing real dirents, and the leaf’s entries are ordered by hash rather than by name, with every hash at or above the value recorded for the leaf in its parent.

The hash of a name is 31 bits wide, and the low bit of the field that holds it is zero. It may be set to one in an interior entry when two names whose hashes collide do not fit in one leaf and must be spread across several blocks, so that two index entries carrying the same hash remain distinguishable during the descent. Nothing in a leaf stores a hash: the dirents there carry only an inode number, a record length, and a name, so a split must rehash the names it redistributes. Directories that are both encrypted and casefolded are the exception, because their names cannot be compared in plaintext; those carry an extended dirent with a stored hash and minor hash, which is what lets a lookup order entries without decrypting them.

The hash algorithm is recorded per directory in the node header, and the defined versions are a legacy variant, a half-MD4 variant, a TEA variant, unsigned forms of each, and SipHash. The version matters because a directory indexed with one algorithm cannot be searched correctly with another: the hash of the same name differs, so the leaf selected differs. A driver that does not implement the recorded version must fall back to reading every block of the directory, which the layout permits precisely because the index blocks look like empty dirents to a reader that does not descend into them.

Lookup, and what the index does not store

Lookup hashes the name, descends the root to the leaf whose hash range contains it, and scans that leaf’s dirents for a name match. The scan is short because a leaf is one block and holds on the order of a few hundred entries at most, so a lookup is one or two block reads regardless of directory size.

The index stores no names. That is a deliberate space decision: a hash entry is eight bytes, while storing the name would make the index as large as the directory it indexes. The cost is that a hash collision sends lookup into a leaf that contains the colliding name but not the target, and the scan must then continue to the next leaf. Collisions are rare but not impossible, and the format’s correctness does not depend on their absence: the scan-and-continue rule makes any collision a slowdown rather than a wrong answer.

/* Pick the leaf by hash, then scan it. The root's entries are
 * sorted by hash, so the last one not greater than the target wins. */
uint64_t leaf_for(struct node *root, uint32_t target)
{
        uint64_t block = root->entry[0].block;
        for (int i = 0; i < root->count; i++)
                if (root->entry[i].hash <= target)
                        block = root->entry[i].block;
        return block;
}
/* The caller then scans that leaf's dirents for an exact name match. */

Insertion is where the tree earns its keep. A new entry goes into the leaf whose hash range contains its hash, placed at the position its hash implies within that leaf. If the leaf has no room, it splits: a new block is allocated from the same group, following the placement rules described in Block Groups and the Cost of Metadata Locality, the entries are divided between the two blocks at a hash boundary, and a root entry is added for the new block. The root holds a bounded number of index entries, and when it is full the tree gains a level: at most two levels of interior nodes, or three on a filesystem with the large-directory feature. A directory with millions of entries still resolves in a handful of block reads.

Enumeration ignores the index entirely

readdir must return every entry exactly once and must not require the caller to hold state beyond a position. The position the interface carries is a byte offset into the directory, which is why the index is built to leave the linear structure intact.

Enumeration walks the directory’s blocks in offset order and returns the dirents it finds, exactly as it would for an unindexed directory. The root block yields . and .. and then an apparently unused region, because the index entries that occupy the rest of it have an inode number of zero and a name length of zero. Each leaf block yields its real entries. The result is a complete traversal with no tree descent, no hash computation, and no dependence on where the leaves sit relative to one another.

That is also why the index entries are laid out as dirents at all. A reader that knows about the tree can find them by position, but a reader that does not is not required to recognize them: they are valid empty entries, and skipping them is correct. The layout serves both readers from the same bytes.

The ordering consequence is that enumeration follows block allocation order, not name order and not hash order. POSIX does not promise alphabetical order, only that a sequence of calls from the start visits each entry once, so any order satisfies the contract. Programs that assumed alphabetical order were relying on an implementation detail of the filesystems they were tested against, and on an indexed directory they will see names grouped by the hash of their prefixes.

Where the design leaks

Deleting an entry does not shrink the tree. The dirent is marked unused, or its space is merged into the preceding entry’s rec_len, and the leaf stays. A directory that once held a hundred thousand files and now holds ten still carries the index blocks and the leaf blocks allocated for the peak. There is no rebalancing pass that merges half-empty leaves, so the space cost of a directory tracks its historical maximum rather than its current size.

The hash also makes the leaf assignment dependent on a per-filesystem seed stored in the superblock. Two filesystems with identical contents therefore place the same names in different leaves and enumerate them in different orders. Tools that compare directory listings across volumes must sort, and any tool that recorded a position in one directory and expected to resume at the same logical point in another has no basis for that expectation.

The final leak is the one shared with every format that layers an index over a linear structure: a damaged root block leaves the leaves intact but unreachable through the index. Repair can rebuild the index by scanning every block in the directory and reinserting the entries, which is exactly the linear cost the index was meant to avoid, paid once. The scan-and-rebuild approach, and its place in the repair sequence, belongs with the other consistency passes described in fsck and the Ordering of Repairs.