Chapter 4: Directory Formats

Updated

October 31, 2026

Chapter 4: Directory Formats

In ext4, a directory is simply a special file whose data blocks contain mappings between human-readable filename strings and target inode numbers. However, the efficiency with which a filesystem searches, inserts, and deletes directory entries directly dictates the responsiveness of the entire operating system.

A naïve linear scan through an unindexed directory block works well for folders with twenty files, but degrades to unusable \(O(N)\) latencies when a directory contains hundreds of thousands of entries (such as a mail queue or image cache).

This chapter details the two directory storage formats employed by ext4: classic Linear Directories (ext4_dir_entry_2) and high-performance HTree Hash Trees, examining directory record alignment, hash collision handling, and traversal algorithms.

Linear Directories (ext4_dir_entry_2)

Small directories, or directories formatted without the dir_index feature, store entries as an unsorted, contiguous linked stream of variable-length records:

struct ext4_dir_entry_2 {
    __le32 inode;             /* Target inode number (0 = deleted/unused entry) */
    __le16 rec_len;           /* Total record length in bytes (including padding) */
    __u8   name_len;          /* Exact length of filename string */
    __u8   file_type;         /* File type indicator (e.g. 1=file, 2=dir, 7=symlink) */
    char   name[EXT4_NAME_LEN];/* Filename characters (up to 255 bytes, no null terminator) */
};
┌────────────────────────────────────────────────────────────────────────┐
│                        LINEAR DIRECTORY BLOCK LAYOUT                   │
│                                                                        │
│   Record 0            Record 1             Record 2 (Padded to End)   │
│  ┌──────────────────┐┌───────────────────┐┌───────────────────────────┐│
│  │ inode: 2         ││ inode: 4501       ││ inode: 9812               ││
│  │ rec_len: 12      ││ rec_len: 20       ││ rec_len: 4064             ││
│  │ name_len: 1      ││ name_len: 7       ││ name_len: 8               ││
│  │ file_type: 2     ││ file_type: 1      ││ file_type: 1              ││
│  │ name: "."        ││ name: "app.log"   ││ name: "data.bin"          ││
│  └──────────────────┘└───────────────────┘└───────────────────────────┘│
│  ◄─────────────────────────── 4096 Bytes ─────────────────────────────►│
└────────────────────────────────────────────────────────────────────────┘

Record Length Alignment and Deletion Mechanics

  1. 4-Byte Alignment: Every directory entry’s rec_len is rounded up to the nearest multiple of 4 bytes. The minimum entry size is 12 bytes (inode[4] + rec_len[2] + name_len[1] + file_type[1] + name[4]).
  2. End-of-Block Padding: The final record in a block has its rec_len expanded so that it extends exactly to the final byte of the physical \(4\text{ KiB}\) disk block.
  3. Zero-Cost Deletion: When an entry is deleted, ext4 does not shift memory or compact the block. Instead, it simply adds the deleted record’s rec_len to the rec_len of the preceding entry. The deleted entry’s metadata remains intact in the unused gap until overwritten, which makes ext4 file carving possible in digital forensics.

The HTree Indexing Algorithm

When a directory grows beyond a single block, linear searching becomes a performance bottleneck: finding a file in a directory with 200,000 files would require reading thousands of disk blocks and comparing hundreds of thousands of strings.

To solve this, Daniel Phillips designed HTree (Hash Tree). HTree is a constant-depth, balanced index tree modeled after a B-tree, but indexed by a 32-bit hash of the filename rather than the variable-length filename string itself.

┌────────────────────────────────────────────────────────────────────────┐
│                        HTREE DIRECTORY ARCHITECTURE                    │
│                                                                        │
│   Block 0: Root Node (dx_root)                                         │
│   ├─ Fake dir entries (. and ..)                                       │
│   ├─ dx_root_info: hash_version, depth (1 or 2)                        │
│   └─ Keys and Child Block Pointers:                                    │
│      [Hash: 0x00000000 -> Block 1] [Hash: 0x4A1F8900 -> Block 2]...   │
│                                           │                            │
│                                           ▼                            │
│   Block 2: Leaf Directory Block (ext4_dir_entry_2 stream)              │
│   ├─ Entry: hash("charlie.png") == 0x4A201100 -> Inode 5401           │
│   └─ Entry: hash("config.yaml") == 0x7E01A4F0 -> Inode 8920           │
└────────────────────────────────────────────────────────────────────────┘

Key Design Constraints of HTree

  1. Backward Compatibility: To ensure older ext2/3 drivers do not crash if they encounter an HTree directory, the root node of an HTree directory (Block 0) begins with fake . and .. directory entries that consume the entire block according to legacy parsers. Older kernels treat the block as an ordinary directory containing only . and .., while HTree-aware kernels parse the indexing structures stored inside.
  2. Constant Depth (1 or 2 Levels): HTree trees have a maximum depth of 2 index levels. With a fan-out of over 500 index entries per block, a 2-level HTree indexes over 100 million files while guaranteeing that resolving any filename requires at most two or three block reads.

Hash Algorithms: legacy, half_md4, tea and siphash

The HTree index relies on a uniform cryptographic hash to distribute filenames evenly across leaf blocks, preventing pathological index imbalances:

  • Legacy (0): Unsalted, simplistic polynomial hash inherited from early Unix tools. Prone to hash collisions; deprecated.
  • Half-MD4 (1): Truncated variant of the MD4 message digest. Fast, highly uniform, and historically the ext4 default.
  • Tea (2): Tiny Encryption Algorithm. Designed for low CPU architectures.
  • SipHash (5): Modern keyed cryptographic pseudo-random function. Introduced to protect against algorithmic complexity denial-of-service (HashDoS) attacks, where an attacker intentionally generates millions of colliding filenames to force leaf block splits.

Hash Seeds

To prevent cross-system hash collision exploitation, every ext4 superblock contains a random 128-bit hash seed (s_hash_seed). Two identical filenames hashed on different ext4 filesystems produce completely different 32-bit hash values.

Traversing and Searching Directories

When the kernel searches for filename "report.pdf" within an indexed directory:

  1. Hash Generation: The kernel computes H = ext4_dirhash("report.pdf", seed).
  2. Root Inspection: The kernel reads Block 0 (dx_root), verifies the dx_root_info header, and performs a binary search across the dx_entry array to find the child block whose hash key range encompasses H.
  3. Interior Node Traversal (if depth == 2): The kernel reads the intermediate dx_node block and performs another binary search.
  4. Leaf Block Scan: The kernel fetches the target leaf directory block and scans its linear ext4_dir_entry_2 records, comparing the exact string "report.pdf" to verify identity and retrieve the target inode number.
  5. Hash Collisions: If multiple filenames produce identical 32-bit hashes, HTree sets the lowest bit (hash | 1) to indicate a collision group, prompting the kernel to inspect the adjacent leaf block if the target file is not found in the first.