Positive to negative ratio [LWN.net]

Positive to negative ratio

Posted Jul 7, 2026 15:29 UTC (Tue) by farnz (subscriber, #17727)
In reply to: Positive to negative ratio by Fowl
Parent article: Limiting negative dentries

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.

to post comments

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.