Directory Implementation

When you type ls /home/user/documents/report.pdf, something has to figure out where that file actually lives on disk. That something is the directory implementation. The directory is the mapping between human-readable names and the underlying inodes that point to file data. How that mapping is structured determines how fast you can find files, how many files a directory can hold, and how the file system behaves under heavy load.

Most people think directories are simple folders. Under the hood, they’re sophisticated data structures that make the difference between a file system that screams and one that crawls.

Introduction

When to Use / When Not to Use

Understanding directory implementation helps with system design and troubleshooting.

When directory implementation matters:

• Systems with millions of files in single directories
• High-throughput workloads that create/delete files frequently
• Backup systems that must scan directory structures
• Troubleshooting slow file system operations

When you can ignore it:

• Normal desktop/server use with moderate file counts
• Cloud storage abstracted behind network file systems
• Applications using higher-level APIs (databases, etc.)

Architecture or Flow Diagram

graph TD
    A[Path: /home/user/docs/file.txt] --> B[Root Directory]
    B --> C[Look up "home"]
    C --> D[User Directory]
    D --> E[Look up "docs"]
    E --> F[Docs Directory]
    F --> G[Look up "file.txt"]
    G --> H[Return Inode Number]

    style A stroke:#ff00ff,stroke-width:2px
    style H stroke:#ff00ff,stroke-width:2px

Path resolution walks through each component. The efficiency of each lookup step determines overall performance.

Core Concepts

Directory Entry Structure

At the basic level, a directory contains entries. Each entry maps a name to an inode:

// Classic Unix directory entry (simplified)
struct old_dirent {
    unsigned long d_ino;      // Inode number
    unsigned short d_reclen; // Record length
    unsigned char d_type;    // File type
    char d_name[256];        // File name (variable length)
};

// Modern directory entry with type
struct linux_dirent64 {
    unsigned long d_ino;      // Inode number
    unsigned long d_off;      // Offset to next entry
    unsigned short d_reclen;  // Record length
    unsigned char d_type;    // File type
    char d_name[];            // File name (null-terminated)
};

The d_reclen field enables entries of variable length. Older systems used fixed-size entries (often 16 or 32 bytes), which limited file names and wasted space.

Linear Search (Simple List)

The most basic directory implementation: entries stored as a simple list, searched sequentially.

graph TD
    A[Directory Entry Array] --> B[.]
    A --> C[..]
    A --> D[file1.txt]
    A --> E[file2.txt]
    A --> F[file3.txt]
    A --> G[fileN.txt]

    H[Search for "file3.txt"] --> I[Compare with file1.txt: NO]
    I --> J[Compare with file2.txt: NO]
    J --> K[Compare with file3.txt: YES - Return inode]

    style H stroke:#00fff9

Characteristics:

• O(n) lookup time where n is number of entries
• No memory overhead for indexing
• Simple implementation
• Performance degrades linearly with directory size

def linear_search(directory, target_name):
    """Simulate linear directory search."""
    for entry in directory.entries:
        if entry.name == target_name:
            return entry.inode
    return None  # Not found

# Complexity: O(n) where n = number of entries
# For 1 million files in a directory: up to 1 million comparisons

Hash Table Directories

Hash tables provide O(1) average lookup by computing a hash of the filename:

graph TD
    A[Filename: "document.txt"] --> B[Hash Function]
    B --> C[Bucket Index: 7]
    C --> D[Bucket 7]
    D --> E[Entry: document.txt -> inode 1234]

    F[Filename: "report.pdf"] --> G[Hash Function]
    G --> H[Bucket Index: 3]
    H --> I[Bucket 3]
    I --> J[Entry: report.pdf -> inode 5678]

    style A stroke:#ff00ff
    style F stroke:#ff00ff

Advantages:

• O(1) average lookup regardless of directory size
• Handles collisions through chaining or open addressing
• Good for large directories

Disadvantages:

• Hash computation overhead
• Collisions require additional handling
• Memory overhead for hash table structure
• Cannot efficiently list entries in sorted order

// Hash table directory implementation (conceptual)
typedef struct dir_entry {
    char *name;
    unsigned long inode;
    struct dir_entry *next;  // Collision chain
} DirEntry;

typedef struct {
    DirEntry *buckets[TABLE_SIZE];
    unsigned int (*hash_fn)(const char *name, int len);
} HashDirectory;

// Insert operation
int hash_insert(HashDirectory *dir, const char *name, unsigned long inode) {
    unsigned int index = dir->hash_fn(name, strlen(name));
    DirEntry *new_entry = malloc(sizeof(DirEntry));
    new_entry->name = strdup(name);
    new_entry->inode = inode;
    new_entry->next = dir->buckets[index];
    dir->buckets[index] = new_entry;
    return 0;
}

B-Tree and B+ Tree Directories

Modern file systems (ext4, NTFS, XFS) use B-trees for directories to maintain sorted order and handle millions of entries:

graph TD
    A[Root Node] --> B[Intermediate Node]
    A --> C[Intermediate Node]

    B --> D[Leaf: A-M]
    B --> E[Leaf: N-Z]
    C --> F[Leaf: A-G]
    C --> G[Leaf: H-N]

    style A stroke:#ff00ff,stroke-width:3px
    style D stroke:#00fff9
    style E stroke:#00fff9
    style F stroke:#00fff9
    style G stroke:#00fff9

B-Tree characteristics:

• O(log n) lookup time
• Maintains sorted order (range queries efficient)
• Handles insertions/deletions without complete restructuring
• Efficient for both small and large directories

ext4 HTree (Indexed Directory): ext4 uses a special B-tree called HTree (a hybrid tree) for directory indexing. It supports:

• O(log n) lookups via two-level indexing
• Linear directory entries as fallback for small directories
• Automatic upgrade to HTree when directory grows large

graph TD
    A[Hash Index Root] --> B[Index Node 0]
    A --> C[Index Node 1]
    B --> D[Leaf: files 0-999]
    B --> E[Leaf: files 1000-1999]
    C --> F[Leaf: files 2000-2999]
    C --> G[Leaf: files 3000-3999]

    style A stroke:#ff00ff,stroke-width:3px

Path Resolution

Path resolution walks the directory tree, looking up each component:

// Simplified path resolution algorithm
inode_t resolve_path(const char *path) {
    if (path[0] == '/') {
        // Absolute path - start at root
        current = root_inode;
        path = path + 1;
    } else {
        // Relative path - start at current directory
        current = cwd_inode;
    }

    while (*path) {
        // Find next path component
        component = next_component(&path);

        // Skip empty components (e.g., "a//b")
        if (strlen(component) == 0) continue;

        // Look up component in current directory
        inode = lookup_entry(current, component);
        if (!inode) return -ENOENT;  // Component doesn't exist

        // Handle ".." and "."
        if (strcmp(component, "..") == 0) {
            current = get_parent(current);
        } else if (strcmp(component, ".") == 0) {
            // Stay at current
        } else {
            current = inode;
        }
    }
    return current;
}

Directory Caching

The kernel caches directory lookups to avoid repeated I/O:

# Check dentry cache statistics
cat /proc/sys/fs/dentry-state

# View cached entries
ls -la /proc/slabinfo | grep dentry

# Clear dentry cache (requires root)
echo 3 > /proc/sys/vm/drop_caches

Production Failure Scenarios

Scenario 1: Million-File Directory Meltdown

What happened: A continuous integration system stored build artifacts in a single directory that grew to over 3 million files. Operations like ls and find became unusable. Creating new files took 10+ seconds. The file system was ext3 with linear directory search.

Why it happened: ext3 uses linear directory search by default. With 3 million files, finding any file required scanning millions of entries. The system spent all its time searching directories instead of doing useful work.

Detection:

# Count files in a directory
ls -la /path/to/directory | wc -l

# Or faster
find /path/to/directory -maxdepth 1 | wc -l

# Check directory entry type
debugfs -R "dir /path/to/directory" /dev/sda1

Mitigation:

• Upgrade to ext4 which enables HTree indexing automatically

• Use e2fsck to convert directory to indexed format:

  sudo tune2fs -O dir_index /dev/sda1
  sudo e2fsck -fD /dev/sda1  # Convert directories

• Restructure storage to spread files across multiple directories

• Implement automatic directory sharding (e.g., using first letters)

Scenario 2: Directory Entry Corruption

What happened: A server crashed mid-write to a directory. On reboot, the directory contained entries pointing to non-existent inodes. Some file names were garbled. The kernel marked the file system dirty.

Why it happened: Without journaling (ext3), directory modifications weren’t atomic. A partial write left the directory in an inconsistent state.

Detection:

# Run file system check in read-only mode
sudo fsck.ext4 -n /dev/sda1

# Use debugfs to examine directory structure
sudo debugfs -w /dev/sda1
debugfs: dirstat /path/to/directory

Mitigation:

• Use journaling file systems (ext4, XFS)
• Convert ext3 to ext4: tune2fs -O extents,uninit_bg /dev/sda1
• Run periodic consistency checks
• Monitor kernel logs for file system errors

Scenario 3: Case-Insensitive Lookup Failure

What happened: A developer created a file named Config.php and pushed to a case-insensitive Windows file share mounted on Linux. Another developer on Linux couldn’t find config.php. The share appeared to lose the file.

Why it happened: Different file systems have different case sensitivity rules:

File System	Case Sensitive?
ext2/3/4	Yes
XFS	Yes
NTFS	No
FAT32	No
CIFS/SMB default	Often no

Detection:

# Check mount options for case sensitivity
mount | grep cifs

# Test case sensitivity
touch TESTFILE
ls testfile 2>/dev/null && echo "Case insensitive" || echo "Case sensitive"

Mitigation:

• Use consistent naming conventions (all lowercase)

• Specify case sensitivity mount option for CIFS:

  mount -o case insensitive //server/share /mnt
  # Or
  mount -o case sensitive //server/share /mnt

• Document case sensitivity rules for cross-platform projects

Trade-off Table

Method	Lookup Time	Insert Time	Memory	Use Case
Linear List	O(n)	O(1) at end	Minimal	Small directories (<1000 files)
Hash Table	O(1) avg	O(1) avg	Medium	Large directories, random access
B-Tree	O(log n)	O(log n)	Higher	Very large, sorted access needed
ext4 HTree	O(log n)	O(log n)	Medium	Modern Linux default

Implementation Snippet

Directory Entry Parser

#!/usr/bin/env python3
"""Parse Linux ext4 directory entries."""

import struct

def parse_ext4_directory(data, block_size=4096):
    """Parse directory entries from an ext4 directory block."""
    entries = []
    offset = 0

    while offset < block_size:
        # Directory entry header (8 bytes)
        header = struct.unpack('<IHHHHH', data[offset:offset+struct.calcsize('<IHHHHH')])

        inode = header[0]
        rec_len = header[1]
        name_len = header[3]

        if inode == 0:
            # Entry not in use
            offset += rec_len
            continue

        # Extract filename
        name_start = offset + struct.calcsize('<IHHHHH')
        name = data[name_start:name_start + name_len].decode('utf-8', errors='replace')

        # File type (stored in record length high bits in ext4)
        file_type = (rec_len >> 12) if rec_len > 255 else 1

        entries.append({
            'inode': inode,
            'name': name,
            'rec_len': rec_len & 0xFFF,  # Lower 12 bits
            'type': ['unknown', 'regular', 'directory', 'char', 'block',
                     'fifo', 'sock', 'symlink'][file_type]
        })

        offset += rec_len

    return entries

def list_directory(device, inode_num):
    """List entries in a directory given its inode."""
    import subprocess

    result = subprocess.run([
        'debugfs', '-R', f'rdump / {inode_num}',
        device
    ], capture_output=True, text=True)
    return result.stdout

Simulating Directory Search

#!/usr/bin/env python3
"""Compare different directory search strategies."""

import time
import random
import string

class DirectoryEntry:
    def __init__(self, name, inode):
        self.name = name
        self.inode = inode

class LinearDirectory:
    """Simple list-based directory."""
    def __init__(self):
        self.entries = []

    def insert(self, name, inode):
        self.entries.append(DirectoryEntry(name, inode))

    def lookup(self, name):
        for entry in self.entries:
            if entry.name == name:
                return entry.inode
        return None

    def list_all(self):
        return [e.name for e in self.entries]

class HashDirectory:
    """Hash table based directory."""
    def __init__(self, size=256):
        self.buckets = [[] for _ in range(size)]
        self.size = size

    def _hash(self, name):
        h = 0
        for c in name:
            h = (h * 31 + ord(c)) % self.size
        return h

    def insert(self, name, inode):
        bucket = self._hash(name)
        for entry in self.buckets[bucket]:
            if entry.name == name:
                entry.inode = inode
                return
        self.buckets[bucket].append(DirectoryEntry(name, inode))

    def lookup(self, name):
        bucket = self._hash(name)
        for entry in self.buckets[bucket]:
            if entry.name == name:
                return entry.inode
        return None

def benchmark(directory, names, iterations=1000):
    """Benchmark directory lookup performance."""
    # Insert all names
    for name in names:
        directory.insert(name, random.randint(1, 1000000))

    # Benchmark lookups
    start = time.time()
    for _ in range(iterations):
        for name in random.sample(names, min(100, len(names))):
            directory.lookup(name)
    elapsed = time.time() - start

    return elapsed

if __name__ == "__main__":
    # Generate test names
    names = [''.join(random.choices(string.ascii_lowercase, k=10))
             for _ in range(10000)]

    linear = LinearDirectory()
    hash_dir = HashDirectory()

    linear_time = benchmark(linear, names)
    hash_time = benchmark(hash_dir, names)

    print(f"Linear search: {linear_time:.4f}s")
    print(f"Hash table:    {hash_time:.4f}s")
    print(f"Speedup:       {linear_time/hash_time:.2f}x")

Observability Checklist

Monitoring directory performance:

• ls -la /path: Check entry count and modification
• getfattr -d file: Check extended attributes
• debugfs -R “dirstat /path” /dev/sdX: Directory statistics on ext4
• xfs_info /mount: Show XFS directory block configuration

# Monitor directory operation times
strace -c ls /path/to/directory

# Check for problematic directories
for dir in /var /home /tmp; do
    count=$(find "$dir" -maxdepth 1 -type f | wc -l)
    if [ $count -gt 10000 ]; then
        echo "WARNING: $dir has $count files"
    fi
done

# Check ext4 directory indexing
sudo tune2fs -l /dev/sda1 | grep -E "Directory"
# Should show: "Directory ACLs", "Directory Indexed"

Common Pitfalls / Anti-Patterns

Directory Permissions

Directory permissions work differently than file permissions:

• Read (r): List directory contents (use ls)
• Write (w): Create, rename, or delete files within directory
• Execute (x): Access directory contents (traverse, use cd)

# r--: Can see file names but not metadata or content
ls /directory      # Yes
ls -l /directory   # No
cat /file          # No

# -w-: Can create/delete files but can't read them
touch /directory/newfile  # Yes
rm /directory/file        # Yes
ls /directory             # No

# --x: Can access known files but not list directory
cd /directory     # Yes
ls /directory     # No
cat /file         # Yes (if you know exact path)

Sticky Bit on Shared Directories

# Prevents users from deleting others' files in shared directories
chmod +t /shared/directory

# View sticky bit
ls -la /shared
# drwxrwxrwt  2 root root 4096 May 19 10:00 /shared
#                                                         ^ sticky bit

Directory Access Control Lists (ACLs)

# Set default ACL for new files in directory
setfacl -d -m u:alice:rw /shared/directory

# Set ACL for specific user
setfacl -m u:bob:r /shared/directory

# View ACLs
getfacl /shared/directory

# Remove specific ACL entry
setfacl -x u:alice /shared/directory

Common Pitfalls / Anti-patterns

1. Millions of Files in One Directory

# BAD: Storing millions of files in single directory
# This kills performance on most file systems
find /logs -name "*.log" | head -1000000 > /tmp/all_logs

# GOOD: Use subdirectories sharded by date/hash
find /logs -type d | head
# /logs/2024/01/01
# /logs/2024/01/02
# ...

# GOOD: Use hierarchical sharding
for i in $(seq 0 99); do
    mkdir -p /data/$i
done
mv file_0001.dat /data/$(($RANDOM % 100))/

2. Long File Names

# Path length limits (older systems):
# - Maximum component: 255 bytes
# - Maximum total path: 4096 bytes

# BAD: Extremely long file names
touch "this_is_a_very_very_long_file_name_that_might_cause_problems.txt"

# GOOD: Use reasonable naming conventions
touch "config_v2_final_REVISED.txt"

3. Special Characters in File Names

# BAD: Special characters that break scripts
touch "file with spaces.txt"
touch "file;with;semicolons.txt"
touch "file*with*asterisks.txt"

# GOOD: Alphanumeric and underscores
touch "config_settings.txt"
touch "user_data_backup.txt"

Quick Recap Checklist

• Directories map file names to inode numbers
• Linear search is O(n), good for small directories (<1000 entries)
• Hash tables provide O(1) average lookup but no sorted iteration
• B-trees give O(log n) and maintain sorted order
• ext4 uses HTree for large directories; convert with e2fsck -D
• Path resolution walks through each component, looking up each name
• Directory caching (dentry cache) dramatically speeds repeated lookups
• Different file systems have different case sensitivity rules
• Watch for inode exhaustion (not just space) when many small files exist

Interview Questions

Further Reading

Topic-Specific Deep Dives:

• HTree Implementation: The ext4 HTree is a specialized B-tree variant optimized for directory lookups. Studying the index node format, hash function used for bucket selection, and how leaf nodes compress filename entries reveals why it handles millions of entries efficiently.

• Distributed Directory Systems: Ceph’s CRUSH algorithm and GlusterFS’s elastic hash algorithm distribute directory metadata across cluster nodes. Understanding how these scale beyond single-machine limits helps design large-scale storage systems.

• Unicode Normalization: Case-insensitive file systems face Unicode challenges. How does NTFS handle case insensitivity across different locales? Study how normalization forms (NFC, NFD) affect file system behavior.

• Directory Entry Caching: The dentry cache isn’t just a performance optimization—it maintains consistency. Explore how d_lookup(), d_invalidate(), and namespace semaphores ensure cache coherence across threads.

• FUSE Directory Implementations: Implementing a FUSE directory index reveals the full complexity. Handling readdir() with offset, implementing mkdir() with proper error codes, and ensuring atomic rename operations are all non-trivial.

Conclusion

Directory implementations transform flat name spaces into the hierarchical structures we navigate daily. The evolution from linear search through hash tables to B-trees reflects the industry learning to handle millions of files per directory without sacrificing performance. ext4’s HTree index makes million-file directories practical — a task that would bring ext3 to its knees.

Path resolution leverages the dentry cache to avoid repeated disk I/O for frequently accessed paths. Each lookup checks the cache before triggering disk reads, making repeated file access dramatically faster than initial access. This caching strategy applies not just to file content but to the directory structure itself.

For deeper study, explore how distributed file systems like Ceph and GlusterFS implement directory metadata at scale, how case-insensitive file systems handle Unicode normalization, and how the trade-offs between directory implementation strategies affect benchmark results. The principles learned here apply broadly to any system that needs to map keys to values at scale.