Dealing with negative dentries [LWN.net]

Dealing with negative dentries

Posted May 10, 2022 14:22 UTC (Tue) by willy (subscriber, #9762)
In reply to: Dealing with negative dentries by NYKevin
Parent article: Dealing with negative dentries

Yes, there really are. Consider PATH=$HOME/bin:/bin:/usr/bin

Most commands you execute don't exist in your private bin, so you need a negative dentry for each of them.

Similar issues for header files; each invocation of gcc needs to search every directory in the -I directories for the header files.

to post comments

Dealing with negative dentries

Posted May 10, 2022 17:06 UTC (Tue) by NYKevin (subscriber, #129325) [Link]

> Most commands you execute don't exist in your private bin, so you need a negative dentry for each of them.

bash hashes those automatically. It does one lookup and then remembers where the file lives. Try running the command hash to see your lookup table. Ironically, this is a perfect example of negative dentry cache leakage, because the kernel is remembering information which userspace already tracks anyway.

(zsh also does this, and I imagine most other modern shells do as well.)

> Similar issues for header files; each invocation of gcc needs to search every directory in the -I directories for the header files.

I'm not saying that we should get rid of negative dentries altogether, just that you don't need a huge number of them. Just how many header files are you searching for?

Dealing with negative dentries

Posted May 21, 2022 8:57 UTC (Sat) by sammythesnake (guest, #17693) [Link]

Perhaps the fix for this (and similar cases) could be to have an API that allows a file lookup with a set of locations, rather than a single file path.

E.g. a call to look for "ls" in any of ["/home/bob/bin","/usr/bin","/usr/sbin"] - there could then be a single dentry indicating that it's at "/usr/bin/ls", or none of the above for some other binary that isn't installed.

The same logic would work for include files or whatever, too...

Obvious downsides that occur to me:

1. You need to define a neat way to specify the $PATH equivalent in a way that could be canonically hashed as the key in the cache - that API would need careful design.

For positive entries, you could potentially only include path elements up to the one where the file was found, meaning the dentry created by the "ls" example above would also be hit if the $PATH was extended or even if the "sbin" element was omitted.

All of this would be much more complex and locating the correct negative dentries to invalidate when a file is created could be a faff. Given that this code is supposed to be faster than heading to the filesystem, there's a limit to how much cleverness is worth paying for.

2. You also might have lots of different $PATH / $INCLUDE specifications, leading to potentially lots of similar entries (especially the negative ones which wouldn't benefit from the path element pruning idea above) which would reduce the potential wins.