vault

The Dentry Cache

16 min read

The Dentry Cache

The dentry cache (the dcache) is the kernel’s in-memory map from path components to filesystem objects. Each entry — a dentry (“directory entry”) — records one name in one directory: a component string, a pointer to its parent dentry, and a pointer to the inode the name resolves to (fs/dcache.c, v6.12). Dentries “live in RAM and are never saved to disc: they exist only for performance” (vfs.rst). The dcache exists so the kernel never has to ask the filesystem to walk the directory tree twice: once a name has been resolved, the binding is hashed into a global table and a later lookup of the same (parent, name) pair becomes a single hash probe instead of a disk read. That short-circuit is the backbone of fast path resolution — it is what makes open("/usr/bin/env") cost a handful of cache hits rather than four directory reads.

Mental Model

Think of the dcache as a giant hash table keyed by (parent dentry, name), sitting in front of every filesystem. The kernel does not store the directory tree as a tree it walks pointer-by-pointer; it stores it as a flat hash table where each dentry knows its parent. To look up bin inside /usr, the kernel computes a hash from the address of the /usr dentry combined with the string "bin", jumps to that bucket, and scans a short chain for a dentry whose parent is /usr and whose name is bin. If it is there (a cache hit), resolution of that component is finished without ever calling the filesystem. If it is not (a cache miss), the kernel falls back to asking the filesystem’s ->lookup() to read the directory and creates a new dentry, which it then inserts into the table so the next lookup hits.

flowchart TB
  subgraph LK["Lookup of name 'bin' in directory '/usr'"]
    H["hash = f(addr-of '/usr' dentry,<br/>name 'bin')"]
    H --> B["dentry_hashtable[hash &gt;&gt; d_hash_shift]<br/>(an hlist_bl bucket)"]
    B --> SCAN["walk the bucket's chain:<br/>match d_name.hash, then<br/>d_parent == /usr and d_same_name"]
    SCAN -->|"found (HIT)"| RET["return cached dentry<br/>refcount++ via lockref"]
    SCAN -->|"not found (MISS)"| SLOW["call fs ->lookup(),<br/>read directory,<br/>d_alloc + d_add into table"]
  end
  RET --> USE["use dentry-&gt;d_inode"]
  SLOW --> USE
  subgraph MEM["When memory is tight"]
    LRU["per-superblock LRU list<br/>(s_dentry_lru)"] --> SHR["superblock shrinker<br/>prune_dcache_sb()"]
    SHR --> FREE["free unused dentries<br/>(d_count == 0)"]
  end
  RET -.->|"on final dput, if unused"| LRU

The dcache as a hash table with an LRU reclaim tail. What it shows: a lookup is a hash probe into dentry_hashtable; a hit returns the cached dentry directly, a miss falls into the filesystem and then populates the cache. Separately, dentries nobody is using sit on a per-superblock LRU list and are freed under memory pressure by the shrinker. The insight: the dcache is two data structures wearing one name — a hash table for fast lookup and an LRU list for reclaim — and a single dentry can be in both at once.

Why a Cache At All

A pathname like /usr/bin/env is, to the kernel, a sequence of component lookups: find usr in /, find bin in usr, find env in bin. Without a cache, each component would require the filesystem to read the directory’s on-disk contents and search them — for ext4 that is a hashed-tree (htree) directory read, for older formats a linear scan. A busy system resolves the same paths thousands of times a second (/etc/passwd, /usr/lib/..., the shell’s $PATH entries), so re-walking the disk every time would be ruinous. The dcache turns the second and subsequent lookups of any path component into pure memory operations. The vfs.rst documentation frames it directly: the dcache “provides a very fast look-up mechanism to translate a pathname (filename) into a specific dentry.”

Crucially, the cache is a partial view: “As most computers cannot fit all dentries in the RAM at the same time, some bits of the cache are missing. In order to resolve your pathname into a dentry, the VFS may have to resort to creating dentries along the way, and then loading the inode” (vfs.rst). So the dcache is never authoritative about absence the way an index would be — a missing dentry means “not cached,” not “does not exist.” (The special case where the dcache does record non-existence is the negative dentry, covered separately.)

The Hash Table — d_hash and dentry_hashtable

The heart of the lookup path is a single global hash table, dentry_hashtable, an array of struct hlist_bl_head buckets (fs/dcache.c line 108). The _bl suffix means bit-locked hlist: each bucket head doubles as a one-bit spinlock stored in the low bit of the head pointer, so locking a single bucket costs no extra memory — important when the table has millions of buckets.

The table is sized at boot relative to physical memory by alloc_large_system_hash("Dentry cache", ...) (fs/dcache.c line ~3193). It is passed scale = 13, and the allocator’s rule is “limit to 1 bucket per 2^scale bytes of low memory” (mm/mm_init.c line ~2375) — i.e. one bucket per 2^13 = 8192 bytes (8 KiB) of RAM as the base ratio.

Uncertain

Verify: the effective bucket-to-RAM ratio on a large 64-bit machine. Reason: alloc_large_system_hash() on 64-bit applies an ADAPT_SCALE loop that increments scale once per ADAPT_SCALE_NPAGES-sized step of memory (mm/mm_init.c line ~2366), so the “1 bucket per 8 KiB” figure is the base and the real ratio gets coarser as RAM grows; the result is also rounded up to a power of two and capped at 1/16 of memory. To resolve: read the exact ADAPT_SCALE_NPAGES/ADAPT_SCALE_SHIFT constants, or just read the actual table size from dmesg | grep "Dentry cache hash table" on a target box. uncertain

The hash itself is computed by d_hash():

static inline struct hlist_bl_head *d_hash(unsigned long hashlen)
{
	return runtime_const_ptr(dentry_hashtable) +
		runtime_const_shift_right_32(hashlen, d_hash_shift);
}

(fs/dcache.c line 110.) The input hashlen is a 32-bit name hash produced by full_name_hash(dir, name, len), which mixes the parent directory pointer (dir) into the hash of the component string — that is what makes bin in /usr land in a different bucket from bin in /sbin. The result is right-shifted by d_hash_shift to index the array. The runtime_const_* wrappers are a 6.x performance trick: the table base pointer and the shift amount are patched directly into the instruction stream at boot by runtime_const_init() (fs/dcache.c lines ~3174–3175), so the hottest function in the kernel avoids two memory loads on every component lookup.

Uncertain

Verify: that the runtime_const machinery in d_hash() is a 6.12-specific form rather than older code. Reason: it is present in the v6.12 blob (so the “in 6.12 it works this way” claim is solid), but I did not check which release introduced it. To resolve: git log the runtime_const_ptr line in fs/dcache.c. uncertain

The Lookup Short-Circuit — __d_lookup

The synchronous, reference-taking lookup is __d_lookup(parent, name) (fs/dcache.c line ~2293). Its body is the canonical short-circuit:

struct dentry *__d_lookup(const struct dentry *parent, const struct qstr *name)
{
	unsigned int hash = name->hash;
	struct hlist_bl_head *b = d_hash(hash);
	...
	rcu_read_lock();
	hlist_bl_for_each_entry_rcu(dentry, node, b, d_hash) {
		if (dentry->d_name.hash != hash)
			continue;                 // cheap reject: hash mismatch
		spin_lock(&dentry->d_lock);
		if (dentry->d_parent != parent)
			goto next;                // wrong directory
		if (d_unhashed(dentry))
			goto next;                // being removed
		if (!d_same_name(dentry, parent, name))
			goto next;                // name mismatch
		dentry->d_lockref.count++;        // HIT: take a reference
		found = dentry;
		spin_unlock(&dentry->d_lock);
		break;
	}
	rcu_read_unlock();
	return found;
}

Reading it line by line: the bucket is found with d_hash(hash); the chain is walked under rcu_read_lock() (so no bucket lock is needed merely to traverse); each candidate is first rejected cheaply on a full 32-bit hash mismatch; a survivor has its per-dentry d_lock taken and is then verified against the real keys — d_parent == parent and d_same_name() (a byte-for-byte name comparison, since two distinct names can collide in the hash). On a match the reference count is bumped and the dentry returned. That returned dentry carries d_inode, so the caller immediately has the file’s metadata with no filesystem call. This is the “fast path resolution” the dcache exists to provide.

There are two siblings worth naming so the relationship is clear. d_lookup() wraps __d_lookup() in a rename_lock seqlock retry, because a concurrent rename can move a dentry to a different bucket mid-scan and cause a false negative; d_lookup() detects that the rename counter changed and simply retries (path-lookup.rst). And __d_lookup_rcu() is the fully lockless variant used by RCU-walk, which does not even take d_lock — the comment in __d_lookup notes the “significant duplication” is deliberate, kept in sync to avoid single-threaded regressions on architectures where the memory barriers in seqcounts are costly. The full two-mode walk is the subject of RCU-Walk and Ref-Walk; here it is enough to see that the hit is a hash probe plus a key check, and the miss (return NULL) is what triggers the slow ->lookup() path and a d_alloc() to populate the cache.

Refcounting — d_lockref and d_count

A dentry must not be freed while anyone is using it, and “anyone” includes open file descriptors, the current path walk, and being someone’s parent. Linux tracks this with a reference count, but with a twist: the count and the per-dentry spinlock are fused into one cacheline-friendly primitive, the lockref.

struct lockref d_lockref;   /* per-dentry lock and refcount */
#define d_lock  d_lockref.lock
static inline unsigned d_count(const struct dentry *dentry)
{
	return dentry->d_lockref.count;
}

(include/linux/dcache.h.) The “special-sauce of this primitive is that the conceptual sequence lock; inc_ref; unlock; can often be performed with a single atomic memory operation” (path-lookup.rst). On the fast path, taking a reference does not actually acquire the spinlock — it uses a cmpxchg that atomically checks “lock not held” and increments the count in one shot. This matters enormously because the root and cwd dentries are referenced by every single path walk on the system; a plain spinlock there would be a global scalability cliff, and lockref is the kernel’s answer to that contention.

dget() increments the count to “clone an existing reference” (calling it on a zero-refcount dentry is a bug); dput() drops a reference and is where the lifecycle decision happens. Holding a reference guarantees the dentry “won’t suddenly be freed and used for something else” and, importantly, that a non-NULL ->d_inode “will never be changed” while the reference is held (path-lookup.rst) — the binding from name to inode is stable as long as you hold the dentry.

From d_count == 0 to the LRU — dput and retain_dentry

When the last reference is dropped, the dentry is unused (d_count == 0) but not necessarily dead. dput() (fs/dcache.c line 845) tries a fast_dput() first; if that cannot decide, it consults retain_dentry() (fs/dcache.c line 690) to answer the question “is this dentry worth keeping?” The logic is the policy core of the cache:

static inline bool retain_dentry(struct dentry *dentry, bool locked)
{
	...
	if (unlikely(d_unhashed(dentry)))        return false; // unreachable, no point
	if (unlikely(d_flags & DCACHE_DISCONNECTED)) return false;
	if (unlikely(d_flags & DCACHE_OP_DELETE)) {            // fs says don't cache
		if (!locked || dentry->d_op->d_delete(dentry)) return false;
	}
	if (unlikely(d_flags & DCACHE_DONTCACHE)) return false; // purge on final put
	// keep it: put on LRU if not already there, else mark referenced
	if (unlikely(!(d_flags & DCACHE_LRU_LIST))) {
		d_lru_add(dentry);
	} else if (unlikely(!(d_flags & DCACHE_REFERENCED))) {
		dentry->d_flags |= DCACHE_REFERENCED;
	}
	return true;
}

If retain_dentry() returns true, the now-unused dentry is kept in the hash table (still findable by a future lookup) and added to its superblock’s LRU list via d_lru_add(), setting DCACHE_LRU_LIST and incrementing the per-CPU nr_dentry_unused counter (fs/dcache.c line 435). This is the whole point: an unused dentry is not freed — it is parked on the LRU as a cache entry, so that if the same path is walked again moments later, the lookup still hits. The DCACHE_REFERENCED flag implements a second-chance (clock) policy: a dentry referenced again after landing on the LRU survives one extra reclaim pass. If retain_dentry() returns false, dput() proceeds into __dentry_kill(), which unhashes the dentry, releases its inode, and frees the slab object (deferred via RCU). The states an unused dentry can be in — and the special unused-and-negative case — are the subject of Dentry States and Negative Dentries; the bridge is exactly this: refcount reaches zero, retain_dentry() decides keep-on-LRU versus kill, and what survives becomes an LRU-resident cache entry.

Reclaim — the Dentry Shrinker and vfs_cache_pressure

Parking every unused dentry forever would let the dcache consume all of RAM, so the kernel registers the dcache (together with the inode cache) as a shrinker — a callback the memory-reclaim core invokes under pressure. This is the general mechanism described in Shrinkers and Slab Reclaim; here is the dentry-specific instance.

Every superblock owns its own dentry LRU (sb->s_dentry_lru) and registers a shrinker whose callbacks are super_cache_count and super_cache_scan (fs/super.c lines 383–384). The shrinker is allocated SHRINKER_NUMA_AWARE | SHRINKER_MEMCG_AWARE (fs/super.c line 378), so reclaim is per-NUMA-node and per-memory-cgroup — a container’s dentries are charged to and reclaimed within its cgroup.

  • Count phase. super_cache_count() reports how many objects could be freed: it sums list_lru_shrink_count(&sb->s_dentry_lru) and the inode LRU, then scales the total through vfs_pressure_ratio() (fs/super.c line 269).
  • Scan phase. When reclaim decides to act, super_cache_scan() proportions the scan between dentries, inodes, and fs-specific caches according to their relative sizes, then calls prune_dcache_sb(sb, sc) (fs/super.c line 221), which walks the LRU and frees the cold dentries it isolates (fs/dcache.c line 1161). It prunes “the dcache first as the icache is pinned by it” — every positive dentry holds a reference to its inode, so you cannot free the inode until the dentry referencing it is gone.

The single tuning knob is /proc/sys/vm/vfs_cache_pressure, and its mechanism is exact and worth understanding:

static inline unsigned long vfs_pressure_ratio(unsigned long val)
{
	return mult_frac(val, sysctl_vfs_cache_pressure, 100);
}

(include/linux/dcache.h line 513.) The default is 100, so vfs_pressure_ratio() is the identity and the count phase reports the true number of reclaimable dentries. The knob simply multiplies that reported count by pressure/100. At vfs_cache_pressure = 100 the kernel reclaims dentries and inodes “at a ‘fair’ rate with respect to pagecache and swapcache reclaim”; decreasing it makes the kernel under-report and therefore retain dentries (good for a fileserver that walks huge trees and wants to keep them cached); increasing it past 100 makes the kernel over-report and reclaim more aggressively; at 0 the kernel “will never reclaim dentries and inodes due to memory pressure and this can easily lead to out-of-memory conditions” (vm.rst). The docs warn that values “significantly beyond 100 may have negative performance impact” because reclaim must take locks to find freeable objects, and at 1000 “it will look for ten times more freeable objects than there are” — pure wasted scanning.

Observability — dentry-state and the slab

Two surfaces let you watch the dcache. /proc/sys/fs/dentry-state exposes struct dentry_stat_t (fs/dcache.c, fs.rst): nr_dentry is the total allocated (active + unused), nr_unused the count parked on LRU lists, and nr_negative the number of unused negative dentries. And the underlying memory is a dedicated slab cache:

dentry_cache = KMEM_CACHE_USERCOPY(dentry,
	SLAB_RECLAIM_ACCOUNT|SLAB_PANIC|SLAB_ACCOUNT, d_iname);

(fs/dcache.c line 3185.) The SLAB_RECLAIM_ACCOUNT flag tells the memory manager this slab is reclaimable (its pages count toward reclaimable memory, since the shrinker can free them); SLAB_ACCOUNT makes the allocations cgroup-accounted. You can watch it live with slabtop or grep dentry /proc/slabinfo. (The slab/SLUB layer itself is The Slab Allocator and SLUB / Kmem Caches and Object Slabs.)

Failure Modes

Dcache bloat starving the page cache. A workload that stat()s or opens millions of distinct paths (a backup walking a huge tree, find /, a build touching every source file) can fill the dcache with cold positive dentries faster than reclaim trims them. Because dentries pin their inodes, this also bloats the inode cache. Symptom: free shows large SReclaimable slab memory, slabtop shows dentry and inode_cache dominating, and the page cache shrinks. The lever is vfs_cache_pressure: raise it to make the kernel discard dentries more eagerly when you would rather keep file data cached.

Reclaim cannot make progress. prune_dcache_sb() “may fail to free any resources if all the dentries are in use” (fs/dcache.c line 1161). If something holds references to a vast set of dentries (e.g. millions of open files, or a leaked reference), the LRU is empty even though nr_dentry is huge, and the shrinker spins finding nothing to free. Diagnose with dentry-state: a large nr_dentry with a tiny nr_unused means the dentries are pinned, not idle.

vfs_cache_pressure = 0 and OOM. Setting the knob to zero to “keep the cache” disables dcache/icache reclaim entirely; under sustained tree-walking the caches grow without bound and the box OOMs (vm.rst). It is almost never the right setting.

Negative-dentry accumulation. The most pernicious bloat comes not from positive dentries but from negative ones — entries recording that a name doesn’t exist. A kernel build can generate 52+ million failed lookups, and the glibc name-service code deliberately tries ~10,000 nonexistent opens at startup (LWN 2020). Unlike positive dentries, negatives are not bounded by the number of real files; their growth and reclaim are the central concern of the companion note.

Alternatives and Boundaries

The dcache is not the page cache. The page cache (see The Page Cache and address_space) holds file data; the dcache holds name-to-inode bindings. A read() consults both: path resolution walks the dcache to reach the inode, then the read pulls bytes from the page cache. Nor is the dcache an authoritative directory index — for filesystems whose contents can change behind the kernel’s back (NFS, 9P, cephfs), the dcache may be stale, and those filesystems set DCACHE_OP_REVALIDATE so the VFS calls ->d_revalidate() on every hit to re-check (path-lookup.rst). Local filesystems (ext4, XFS, Btrfs) leave revalidation NULL because “all their dentries in the dcache are valid” (vfs.rst) — for them the dcache is trusted, which is what lets the VFS answer stat() and even some ENOENTs without ever calling the filesystem.

Production Notes

The dcache’s scalability is one of the most-tuned hot paths in the kernel. The lockref primitive (LWN “Meet the Lockers”) exists specifically because the root and cwd dentries are touched by every walk on the machine, and the runtime_const patching of d_hash() exists to shave loads off the most-called function in the kernel. On the operations side, the practical knobs are vfs_cache_pressure (the only direct policy lever) and observation through /proc/sys/fs/dentry-state, slabtop, and /proc/slabinfo. A common production pattern on metadata-heavy fileservers is to lower vfs_cache_pressure (e.g. to 50) so the kernel keeps directory structure cached across a large tree; the opposite pattern, raising it, is used when a periodic full-tree scan would otherwise evict the page cache the application actually depends on.

See Also

Graph View

Backlinks