Positive to negative ratio [LWN.net]

Positive to negative ratio

Posted Jul 7, 2026 10:40 UTC (Tue) by Fowl (subscriber, #65667)
Parent article: Limiting negative dentries

I’m imaging the implementation is probably not simple, but would setting a limit at some ratio of positive entires work? Surely finding the negative entry gets harder than not finding the actual file at some point? Does a directory with 10 files need them at all?

Keeping counts might be difficult, but it doesn’t need to be precise - even just a few buckets maybe.

I guess there’d a potential for a “cliff” (instead of gradual performance degradation) at reaching any limit at all if there’s not been one before.

Positive to negative ratio

Posted Jul 7, 2026 13:48 UTC (Tue) by paulj (subscriber, #341) [Link] (1 responses)

I have the same question. Why is the answer not a limit on the -dentry cache list, given there exists some number of entries beyond which the -dentry cache list apparently has a /greater/ cost than just doing the lookup?

Positive to negative ratio

Posted Jul 10, 2026 10:36 UTC (Fri) by neilbrown (subscriber, #359) [Link]

The number of negative dentries is not the problem. The problems are:
- iterating over positive children can be slow
- refcount on parent from negative children can exceed 32bits
- freeing a large number of (negative) dentries may not free much memory due to fragmentation, and may cause excessive memory bus traffic (if I've understood that one properly)

Reducing the number of negative dentries is a large and inappropriate hammer.

Negative dentries can be on a separate list. They can have an indirect ref on the parent. They can, on second reference, be moved to a separate pool of pages of negative dentries (negative dentries do not have ling term references so ate relatively easy to move). These pages can be freed whole, reducing fragmentation.

So we can address each actual problem rather addressing something that loosely correlates with the problems.

Positive to negative ratio

Posted Jul 7, 2026 15:29 UTC (Tue) by farnz (subscriber, #17727) [Link] (4 responses)

The motivating use case for negative dentries is something like the C include path; you write #include <stdio.h> in your source code, and your compiler searches multiple directories for stdio.h. In the case of a default Fedora 44 gcc, there's three before you add any library search paths, in the following order:

Your cwd for "" includes, but not <> includes.
/usr/lib/gcc/x86_64-redhat-linux/16/include - 141 files on my system
/usr/local/include - empty
/usr/include - 270 files.

Most header files are going to be found in /usr/include - /usr/lib/gcc/x86_64-redhat-linux/16/include is only for headers whose content is machine-specific, and /usr/local/include is for cases where you installed a package outside the system package manager's control.. On top of that, you have additional directories added by -I and similar options (including those added by things like pkg-config).

This gets worse for C++, which changes to the following list:

Your cwd for "" includes, but not <> includes.
/usr/lib/gcc/x86_64-redhat-linux/16/../../../../include/c++/16 - 137 files.
/usr/lib/gcc/x86_64-redhat-linux/16/../../../../include/c++/16/x86_64-redhat-linux - 3 files
/usr/lib/gcc/x86_64-redhat-linux/16/../../../../include/c++/16/backward - 8 files
/usr/lib/gcc/x86_64-redhat-linux/16/include
/usr/local/include
/usr/include

So, we need something that's going to quickly return "not present" for all the directories that are earlier in the search path than /usr/include when we search for (say) stdio.h or zlib.h, or the directory vulkan, but that's not going to consume a lot of resources. Negative dentries are supposed to be that thing - so the question is how many negative dentries are reasonable to record before it'd be cheaper to just do a full lookup.

In turn, that means that the "right" number of negative dentries for directories in the search path for the C compiler before /usr/include is a function of the number of files in /usr/include, and not any function of the number of files in those directories. If you have a lot of libraries installing headers in there, then the right number can be quite large.

And related to that is cache management policy; while positive dentries are limited to the number of directory entries by definition, which dentries we should remove once we have too many dentries is itself a question that needs considering - are you better off removing the negative dentry that tells you that zlib.h is not found in /usr/lib/gcc/x86_64-redhat-linux/16/include, or the positive dentry that tells you that omp.h is found there? The right answer depends on whether you're compiling code that uses GOMP heavily, or code that uses Zlib heavily.

Positive to negative ratio

Posted Jul 7, 2026 16:01 UTC (Tue) by kleptog (subscriber, #1183) [Link] (3 responses)

ISTM what is relevant is the amount of time a dentry is in the cache. Deleting a negative dentry means the next lookup will take longer. So that's the time being saved that needs to be weighed against the extra memory usage and CPU cost of keeping the entry.

I would think that if a negative dentry hasn't been hit in the last minute you can probably toss it. The example posted above where the negative dentries are using up 1GB of memory per minute while never being referenced for me feels like the memory costs far outweighs the benefits.

Positive to negative ratio

Posted Jul 7, 2026 17:15 UTC (Tue) by farnz (subscriber, #17727) [Link]

The same applies to positive dentries, too - while they don't have the cache size explosion potential of negative dentries (being bounded by the number of entries in the directory), it seems wasteful to keep a positive dentry for omp.h that's never referenced again, when you could use the cache space for a negative dentry for limits.h that's being referenced every 90 seconds.

It does feel like the necessary change is to have a size limit on the dentry cache (so that it can't be multiple gigabytes in size), and to have a cache replacement policy that accounts for many dentries never being reused - a split LRU (like the active/inactive lists for page cache), or a LFUDA type policy.

Positive to negative ratio

Posted Jul 7, 2026 18:28 UTC (Tue) by jmgao (subscriber, #104246) [Link] (1 responses)

> I would think that if a negative dentry hasn't been hit in the last minute you can probably toss it.

The compiler include use case is going to be pretty disconnected from any wall-clock time, since the iteration time of an edit-compile-test loop is going to be highly variable.

Positive to negative ratio

Posted Jul 7, 2026 19:10 UTC (Tue) by rgmoore (✭ supporter ✭, #75) [Link]

The issue with compiling is when you have to compile many individual .c files, each of which has the same set of includes. It makes sense to cache that information so you don't have to perform the same expensive file checks again for each .c file. When you get into the test and edit steps of the loop, you can safely flush the cache. It's going to be a really long time before you need to look that information up again, and the cache will repopulate as soon as you compile one file.