vault

Dentry States and Negative Dentries

13 min read

Dentry States and Negative Dentries

A dentry is not simply present or absent in the cache — it occupies one of several states, and the most surprising of them is the negative dentry: a cached record that a name does not exist. A negative dentry has d_inode == NULL; “the inode pointer can be NULL indicating that the name doesn’t exist in the parent” (path-lookup.rst, v6.12). Negative dentries exist to make failed lookups as fast as successful ones: once the kernel has learned that /etc/nonexistent is not there, it caches that failure so the next thousand attempts return ENOENT from memory instead of re-reading the directory. The same mechanism that accelerates repeated ENOENT also creates a memory-pressure hazard, because — unlike positive dentries — there is no natural ceiling on the number of names that don’t exist.

This note covers the dentry lifecycle states (in-use, unused, negative) and the negative-dentry problem specifically. The hash table, lookup short-circuit, refcounting, LRU and shrinker mechanics live in The Dentry Cache; the struct dentry fields and the full dentry_operations table live in VFS Dentry Object. This note picks up where refcounting leaves off — what state a dentry is in once its reference count and inode pointer are considered together.

Mental Model — Three Axes of Dentry State

A dentry’s “state” is really two orthogonal questions answered at once:

  1. Is anyone using it? — given by the reference count d_count (d_lockref.count). d_count > 0 means in-use (held by an open file, the current path walk, or as a parent); d_count == 0 means unused (a candidate for reclaim, parked on the LRU).
  2. Does the name resolve to a file? — given by d_inode. Non-NULL means positive (the name maps to an inode); NULL means negative (the name is known not to exist).

These combine. A positive in-use dentry backs every open file. A positive unused dentry is a cache hit waiting to happen. A negative dentry — almost always unused — is a cached ENOENT.

flowchart LR
  A["allocated<br/>(d_alloc)"] --> NEG["NEGATIVE<br/>d_inode == NULL<br/>(failed lookup cached)"]
  A --> POS["POSITIVE in-use<br/>d_inode != NULL<br/>d_count &gt; 0"]
  NEG -->|"file gets created<br/>d_instantiate"| POS
  POS -->|"last dput,<br/>retain_dentry keeps it"| PU["POSITIVE unused<br/>d_count == 0<br/>on LRU"]
  POS -->|"unlink/rmdir,<br/>d_delete, only user"| NEG
  PU -->|"lookup reuses it"| POS
  NEG -->|"reclaim:<br/>superblock shrinker"| FREE["freed"]
  PU -->|"reclaim or<br/>memory pressure"| FREE

The dentry state machine. What it shows: a freshly allocated dentry is either instantiated positive (the file exists) or left negative (it doesn’t); positive dentries cycle between in-use and unused as references come and go; and d_delete() on the last user of a deleted file flips a positive dentry to negative rather than freeing it. The insight: “negative” is not an error state or a half-built dentry — it is a fully valid, deliberately cached answer (“no such name”), and a positive dentry can become negative when its file is removed.

What a Negative Dentry Records

When a path lookup asks the filesystem for a name and the filesystem reports the name is absent, the VFS does not throw that knowledge away. It keeps the dentry it allocated for the lookup, leaves d_inode as NULL, and inserts it into the hash table. The next lookup of that same (parent, name) finds the negative dentry and can return ENOENT immediately — a “successful negative lookup,” as fs/dcache.c puts it (fs/dcache.c line ~534). This is genuinely valuable: dynamic linkers, shells searching $PATH, and language runtimes probe long lists of candidate paths, most of which don’t exist, and they do so repeatedly. Caching the absence turns those probes into memory hits.

The kernel distinguishes a negative dentry from a positive one not only by d_inode == NULL but by an explicit type encoded in d_flags. Bits 20–22 hold the entry type (include/linux/dcache.h lines 207–214):

#define DCACHE_ENTRY_TYPE      (7 << 20)
#define DCACHE_MISS_TYPE       (0 << 20)  /* Negative dentry */
#define DCACHE_WHITEOUT_TYPE   (1 << 20)  /* Whiteout dentry (stop pathwalk) */
#define DCACHE_DIRECTORY_TYPE  (2 << 20)
#define DCACHE_REGULAR_TYPE    (4 << 20)
#define DCACHE_SYMLINK_TYPE    (6 << 20)

A negative dentry has type DCACHE_MISS_TYPE (the zero value), and d_is_negative() is literally a check that the type field equals DCACHE_MISS_TYPE (include/linux/dcache.h line ~460). The DCACHE_WHITEOUT_TYPE is a special negative used by overlayfs to mark a name as deliberately deleted in an upper layer so the walk stops rather than falling through to the lower layer.

How Negative Dentries Are Created

There are two distinct origins, and they are easy to confuse.

Origin 1 — a lookup that found nothing. During lookup_slow(), the VFS allocates a dentry, calls the filesystem’s ->lookup(), and if the filesystem returns no inode, the dentry is added to the cache as negative. The path-lookup.rst docs are explicit: “A new dentry will be added to the cache regardless of the result.” So even a lookup that fails populates the cache — that is the whole mechanism.

Origin 2 — a positive dentry whose file was deleted. When a file is unlinked, the kernel has a choice, spelled out in the comment at fs/dcache.c line ~2374: “When a file is deleted, we have two options: turn this dentry into a negative dentry, or remove it from the hash queues.” d_delete() implements this:

void d_delete(struct dentry * dentry)
{
	struct inode *inode = dentry->d_inode;
	spin_lock(&inode->i_lock);
	spin_lock(&dentry->d_lock);
	if (dentry->d_lockref.count == 1) {        // we are the only user
		dentry->d_flags &= ~DCACHE_CANT_MOUNT;
		dentry_unlink_inode(dentry);           // -> becomes NEGATIVE
	} else {
		__d_drop(dentry);                      // someone still uses it: just unhash
		spin_unlock(&dentry->d_lock);
		spin_unlock(&inode->i_lock);
	}
}

(fs/dcache.c line 2394.) If the deleted file’s dentry has exactly one user (the deleter), dentry_unlink_inode() is called, which runs __d_clear_type_and_inode(): it clears the entry-type bits and sets dentry->d_inode = NULL under the dentry’s seqcount (fs/dcache.c lines 358–372, 395–415). The dentry is now negative. If instead someone else still has the file open, the dentry cannot be made negative (the open file needs d_inode), so __d_drop() merely removes it from the hash table; the dentry survives, detached, until the last open descriptor closes — this is exactly how “deleting an open file keeps it usable” works.

The reverse transition is d_instantiate(), which “turns negative dentries into productive full members of society” (fs/dcache.c line ~1880) by attaching an inode — this is what create(), mkdir(), etc. do to the negative dentry the lookup left behind.

State Flags Beyond Positive/Negative

A dentry carries other state bits in d_flags that govern where it sits and how it is treated (include/linux/dcache.h):

  • DCACHE_LRU_LIST (bit 19) — the dentry is on its superblock’s LRU list. Set by d_lru_add() when an unused dentry is retained; this is what makes it a reclaimable cache entry rather than a live one.
  • DCACHE_REFERENCED (bit 6) — “recently used, don’t discard.” Implements the second-chance (clock) reclaim policy: a dentry touched again after landing on the LRU gets this bit and survives one extra shrink pass.
  • DCACHE_SHRINK_LIST (bit 10) — the dentry has been isolated onto a private list by the shrinker and is in the process of being killed; it is no longer on the normal LRU.
  • DCACHE_DONTCACHE (bit 7) — “purge from memory on final dput().” When set, retain_dentry() refuses to keep the dentry: as soon as the last reference drops, it is killed rather than cached. Filesystems use d_mark_dontcache() to force this for dentries that should never linger.

The first three describe reclaim position; DCACHE_DONTCACHE is a policy override that opts a dentry out of caching entirely. (The complete flag list and the DCACHE_OP_* operation flags belong to VFS Dentry Object; only the state-relevant ones are covered here.)

The Accounting Subtlety — nr_dentry_negative

The kernel counts negative dentries in a per-CPU counter nr_dentry_negative, surfaced as nr_negative in /proc/sys/fs/dentry-state (fs/dcache.c line 137; fs.rst). But the counter has a precise definition that is easy to overstate: it counts only negative dentries that are on the LRU — i.e. unused ones available for reclaim — not every negative dentry in existence. The code comment is explicit:

/*
 * The negative counter only tracks dentries on the LRU. Don't inc if
 * d_lru is on another list.
 */
if ((flags & (DCACHE_LRU_LIST|DCACHE_SHRINK_LIST)) == DCACHE_LRU_LIST)
	this_cpu_inc(nr_dentry_negative);

(fs/dcache.c lines 367–371.) The condition — DCACHE_LRU_LIST set and DCACHE_SHRINK_LIST clear — means “on the normal LRU, not already being shrunk.” The documentation matches: nr_negative “shows the number of unused dentries that are also negative dentries which do not map to any files” (fs.rst, emphasis added). A negative dentry that is currently held (e.g. mid-lookup) is not counted. So nr_negative is best read as “reclaimable negative dentries,” which is exactly the number that matters for memory-pressure reasoning.

The Bloat Problem — Why Negatives Are Uniquely Dangerous

Positive dentries are self-limiting: you cannot have more positive dentries than you have real files and directories on disk. Negative dentries have no such ceiling. The number of names that don’t exist in a directory is effectively unbounded, so a workload that keeps probing for absent files can manufacture negative dentries without limit. Real cases (LWN, 2020): a single kernel build can generate 52+ million failed lookups, and the glibc name-service-switch code “deliberately attempts 10,000 nonexistent file opens at startup.” Each one leaves a negative dentry behind.

The danger is twofold. First, raw memory consumption: tens of millions of dentries is gigabytes of slab. Second, and worse, is the latency of the reclaim itself — when a single directory accumulates an enormous chain of negative dentries, operations that must walk or invalidate that set can stall, and the kernel has seen “soft lockups” attributed to exactly this (LWN, 2022).

In 6.12 LTS (as of 2026) the only bound on negative dentries is global memory reclaim — the per-superblock dentry shrinker described in The Dentry Cache and Shrinkers and Slab Reclaim. Negative dentries sit on the same LRU as positive unused ones and are freed by the same prune_dcache_sb() path; there is no per-directory negative-dentry limit in the mainline tree. I confirmed this against the v6.12 source: fs/dcache.c contains only the nr_dentry_negative accounting and no clamping logic, and /proc/sys/fs/ exposes only dentry-state (a read-only stat), with no dentry-dir-max or ratio knob (fs/dcache.c; fs.rst).

This is despite a long history of proposals to bound them. Waiman Long proposed a /proc/sys/fs/dentry-dir-max sysctl (minimum 256) capping negatives per directory and trimming back to 7/8 of the limit (LWN, 2020); Stephen Brennan proposed a self-tuning heuristic — “the negative dentries for any given directory should not outnumber the positive dentries by more than a factor of five” — using a cursor to sample ratios (LWN, 2022). Both stalled. Matthew Wilcox objected to the sysctl on principle (“A sysctl is just a way of blaming the sysadmin for us not being very good at programming”), and Dave Chinner argued the real problem is general — “memory reclaim does nothing to manage long term build-up of single-use cached objects when there is no memory pressure” — and should be solved by a generic cache-aging mechanism rather than a dentry-specific cap (LWN, 2022). The problem was first reported around 2002 and, as of the 6.12 era, remains managed only by global reclaim plus memory-cgroup limits.

Uncertain

Verify: that no per-directory or per-superblock negative-dentry limiting mechanism has merged in a release between 6.12 and the current newest LTS 6.18. Reason: I confirmed absence in the v6.12 blob directly, and the LWN discussions (2020/2022) show only stalled proposals, but I did not diff the 6.18 tree. To resolve: grep fs/dcache.c at tag v6.18 for negative/dir_max/clamp logic and re-check /proc/sys/fs/ entries. uncertain

Failure Modes and Diagnosis

Runaway negative-dentry growth. A daemon that repeatedly stat()s or open()s paths that do not exist (a poorly written config-file searcher, a watcher polling for files in a directory, an NSS-heavy boot) inflates nr_negative without bound. Symptom: cat /proc/sys/fs/dentry-state shows a huge nr_negative (the fifth field), slabtop shows dentry dominating with most entries cold, and SReclaimable in /proc/meminfo is large. Because these dentries are negative they pin no inodes, so unlike positive bloat the inode cache stays small — a large nr_negative with a modest inode_cache is the fingerprint of negative-dentry bloat specifically.

It is reclaimable — but only under pressure. The frustrating property, per Chinner’s critique, is that an idle system with plenty of free RAM will not trim negatives, because the shrinker only runs under memory pressure. The cache grows during a burst of failed lookups and then just sits there. Operators sometimes force a trim with echo 2 > /proc/sys/vm/drop_caches (drops dentries and inodes) or by raising vfs_cache_pressure (see The Dentry Cache), but both are blunt — drop_caches discards all reclaimable dentries, not just the negatives.

Cross-cgroup behavior. Because the dentry shrinker is SHRINKER_MEMCG_AWARE (fs/super.c line 378), negative dentries created inside a container are charged to and reclaimed within that container’s memory cgroup. This is partly why Chinner argued existing memcg limits already constrain the problem (LWN, 2022): a container hitting its memory limit will have its negative dentries reclaimed before it OOMs the host. The counter-argument is that a single host-level directory shared across the system has no such natural boundary.

Alternatives and Boundaries

The negative dentry is the dcache’s only mechanism for caching absence. There is no separate “negative cache” data structure — a negative dentry lives in the same hash table and on the same LRU as a positive one, distinguished only by d_inode == NULL and the DCACHE_MISS_TYPE flag. This unification is deliberate and elegant (lookup treats hit-positive, hit-negative, and miss uniformly) but is precisely what makes negatives hard to bound separately — they are not a thing you can cap without special-casing them throughout the cache, which is the engineering objection that has kept every limiting patch out of mainline.

Production Notes

The pragmatic stance through the 6.12 era is: negative dentries are a feature you mostly want, and a problem only for pathological producers (mass failed lookups). Monitor the fifth field of /proc/sys/fs/dentry-state if you suspect bloat; correlate with slabtop. The structural fixes — dentry-dir-max, the 5:1 ratio heuristic, a generic cache-ager — have been debated at the Linux Storage, Filesystem, and Memory-Management Summit repeatedly (LWN, 2022) without a merged outcome, so for now the answer is global reclaim, memory cgroups, and fixing the offending userspace caller. The deeper lesson is the one Dave Chinner keeps making: single-use cached objects with no memory pressure are a kernel-wide gap, and negative dentries are just its most visible instance.

See Also

Graph View

Backlinks