Directories

A directory is a special file whose data is a list of (name, inode) pairs.

ext4 directory entry:

struct dir_entry {
    uint32_t inode;          // 0 = unused slot
    uint16_t rec_len;        // total length of this entry
    uint8_t  name_len;
    uint8_t  file_type;
    char     name[];         // up to 255 bytes
};

Variable-length records, packed contiguously. rec_len lets reader skip past.

Adding entry:

• Find a slot with enough room.
• Either reuse a deleted entry (inode=0) or pack into spare bytes of last entry.
• If no room: allocate a new block.

Removing:

• Mark entry as unused (inode=0) or merge with previous (extend its rec_len).

Listing:

• Walk directory blocks, emit entries.
• Skip entries with inode=0.

Two special entries:

• . → current directory.
• .. → parent directory.

For root: .. points to itself.

Lookup name in directory:

• Linear scan: O(N). Fine for small dirs.
• For large dirs (>>1000 entries), linear is slow.

ext4 indexed directories (htree):

• Like a B-tree keyed by hash(name).
• Logarithmic lookup.
• Optional: enabled via dir_index feature.

Other FS:

• xfs: B-trees by default.
• btrfs: B+ trees.

Opening a directory:

• open() on a path returning a dir.
• getdents() syscall to list entries.

Modifying a directory while iterating: undefined / OS-dependent. Common bug.

Hard links:

• Two directory entries → same inode.
• Inode's link_count incremented.
• Deletion decrements; only frees inode when 0.
• Cannot link directories (cycle prevention).

Symbolic links:

• Inode with mode = SYMLINK.
• Data is target path.
• Following: re-resolve.