Directory Entries & Path Resolution

Every time a file is opened, the kernel doesn't just jump straight to the data. It walks.

/home/user/docs/report.txt isn't a single lookup. It's four separate lookups: "home" inside /, then "user" inside home, then "docs" inside user, then "report.txt" inside docs. Each step checks permissions. Each step might cross a mount point into a different filesystem. Each step might follow a symlink into an entirely different part of the tree.

And this walk happens on every open(), stat(), and exec() call. On a busy server, that's millions of walks per second. Without caching, the system would spend all its time reading directories from disk just to find files it already knew about.

What Actually Happens

When a process calls open("/home/user/docs/report.txt", ...), the kernel's namei subsystem takes over:

1. Start at the root dentry (/)
2. Hash ("home", parent=root dentry) and look it up in the dcache hash table
3. Cache hit? Great — grab the inode, no disk I/O
4. Cache miss? Fall back to reading the directory from disk, create a dentry, cache it
5. Check execute permission on the directory (the process needs x to traverse it)
6. Check if this dentry is a mount point — if so, cross into the mounted filesystem
7. Check if this is a symlink — if so, read the target and restart resolution (up to 40 deep)
8. Repeat for "user", "docs", "report.txt"

The kernel carries a struct nameidata through this walk — it tracks the current position (dentry + mount), the remaining path, resolution flags, and a symlink depth counter to catch loops.

Two walk modes. The kernel first tries RCU-walk: lockless path resolution using RCU read-side protection. No atomic operations on dentry reference counts. No locks. This makes hot-path lookups nearly zero-cost. If RCU-walk hits a snag — cache miss, need to sleep for a permission check, concurrent rename happening — it gracefully falls back to ref-walk, which takes proper locks and references. The fast path stays fast; the slow path stays correct.

The openat() family. Traditional path resolution starts from the process's current working directory or from root. But openat(dirfd, "relative/path", ...) resolves from a specific directory fd. This matters for security: once a directory has been opened and validated, openat() guarantees resolution stays within that directory, even if someone renames or replaces the path between the check and the use. This eliminates TOCTOU (time-of-check-to-time-of-use) vulnerabilities. The special value AT_FDCWD means "use the current working directory," making openat(AT_FDCWD, path, flags) equivalent to open(path, flags).

Under the Hood

Directory on-disk formats. Directories are just files whose data blocks contain directory entry records. But the on-disk format matters enormously for lookup speed. ext4 uses the HTree — a hashed B-tree where filenames are hashed (half-MD4) and organized for O(1) amortized lookup. Without it (on ext2, or small ext4 directories), lookups are linear scans: O(n) per lookup. In a Maildir with a million messages, that's the difference between instant and unbearable.

Negative dentries in detail. When a lookup fails (file doesn't exist), the kernel creates a dentry with a NULL inode pointer. This negative dentry sits in the cache and short-circuits future lookups for the same non-existent name — returning ENOENT immediately without touching disk. Negative dentries are evicted under memory pressure via the dcache shrinker. They're especially critical during $PATH search (where the shell tries every directory for a command) and header file resolution in compilers.

The '.' and '..' entries. Every directory contains two special entries: . (self) and .. (parent). These are real on-disk directory entries, not illusions. The . entry is a hard link to the directory's own inode — which is why st_nlink for an empty directory is 2 (the parent's entry for this directory, plus this directory's own .). Each subdirectory adds 1 to the parent's link count via its .. entry. That quirk is why find -type d can optimize tree traversal by counting st_nlink — if a directory has link count 2, it has no subdirectories.

Memory impact. Each dentry is approximately 192 bytes. Walk a million-file directory tree and a million dentries get created — about 192 MB of kernel memory. The dcache grows unboundedly, limited only by available memory. Under pressure, the kernel's dcache shrinker evicts LRU dentries. Forcing eviction with echo 2 > /proc/sys/vm/drop_caches is a sledgehammer that kills performance across the board. Better to monitor /proc/sys/fs/dentry-state and slabtop to understand cache pressure.

Common Questions

What is a TOCTOU vulnerability and how does openat() fix it?

TOCTOU (time-of-check-to-time-of-use) happens when a condition is checked and acted on in separate syscalls. Between access("/safe/dir/file", R_OK) and open("/safe/dir/file", ...), an attacker can replace /safe/dir with a symlink to /etc/shadow. The two calls resolve the same path string to different files. openat() fixes this: once /safe/dir is opened as fd 5, openat(5, "file", ...) resolves within that specific directory instance, regardless of what happens to the path name later. The directory is pinned by the fd — it can be renamed or unlinked, but its contents don't change.

Why does readdir() return files in seemingly random order?

Because directories aren't sorted. ext4 HTree organizes entries by filename hash for fast lookup, so readdir() returns them in hash order — which looks random. Small directories without HTree return entries in creation order. XFS uses B+ trees, returning entries in yet another hash order. If alphabetical output is needed, sort it after reading. ls does exactly this.

What's the deal with the execute bit on directories?

The execute (search) bit on a directory controls whether a process can traverse through it. The x permission is required to reach anything inside. The read bit (r) controls listing — whether the names of entries are visible. A directory can have x without r (traverse but can't list) or r without x (see names but can't access the actual files). This distinction is how directories can require users to know the exact filename to access it — a poor man's access control that's used more often than expected.

How can the dcache consume all system memory?

Every new path resolution that misses the cache creates a new dentry that stays in memory. A process that walks a million-file tree creates a million dentries — 192 MB. Multiply by many processes and many trees, and the dcache can dominate kernel memory usage. The kernel's dcache shrinker, triggered by the slab allocator's reclaim path, evicts LRU dentries when memory gets tight. Writing to /proc/sys/vm/drop_caches forces eviction, but kills performance. The real solution is monitoring: watch /proc/sys/fs/dentry-state and slabtop for creeping growth.