LWN: Comments on "Dentry negativity"

Dentry negativity

mgedmin — Wed, 01 Apr 2020 12:19:26 +0000

Debian stopped building locale-archive back in 2011 because it was causing problems for them (https://bugs.debian.org/537743,
https://bugs.debian.org/636694, https://bugs.debian.org/638173).

Dentry negativity

mtmmtm — Tue, 31 Mar 2020 19:03:56 +0000

Yes, for file creation it could work (but it would work even better without it (just one missed hash-lookup)).
There is a hash and rehash-command for updating the hashtable in most shells. I think bash search every directory in PATH if it fails to find the executable in it's hashtable. Sounds like a bad idea to me. Not sure where the hashtable is located, but having ONE hashtable would be most efficient.

Dentry negativity

Hello71 — Sat, 28 Mar 2020 02:29:59 +0000

yeah, seems like corbet's system is misconfigured. /usr/lib64/locale/locale-archive should have all the /usr/lib/locale files already cached, specifically so it is not necessary to go sniffing for them. same with other files, /etc/ld.so.cache caches location of shared libraries. cache invalidation is simple: punt it to the package manager, which must always run ldconfig after changing shared libraries.

I get 21427 ENOENTs for allmodconfig with a fresh O=, and 8161 with an existing one. less with in-tree builds.

Dentry negativity

mathstuf — Thu, 26 Mar 2020 15:38:36 +0000

For file creation, negative entries are turned into positive entries, so they're not completely useless. They're stored in the same tree here in any case.

> Another thing is that lib-c or similar should not look for non-existing files

How would any libc know they don't exist without searching? If you mean for internal things, PATH (and other search mechanisms) are going to be pretty broken if every search "should" hit…

Dentry negativity

mtmmtm — Thu, 26 Mar 2020 15:25:54 +0000

I do not agree that there is a need for a negative cache. Having such a cache would be a waste of memory. Doing a lookup into a tree-structure has an almost constant lookup-time O(log n). Adding another negative-cache would just take more time (now you must search in 2 tree:s). My guess is that the wrong data-structure is used (where a lookup is slow). Another thing is that lib-c or similar should not look for non-existing files (it should know exactly what files to open (in a cache?)).

Dentry negativity

Wol — Sat, 21 Mar 2020 08:25:54 +0000

You've just made the same mistake I did higher up. See Neil Brown's answer to me.

(Over)Simply put, the *path* name is hashed, and use to look up the table. (I guess that's over-simplistic, but the idea is close enough.) The lookup never goes anywhere near the directory itself.

Cheers,
Wol

Dentry negativity

faramir — Thu, 19 Mar 2020 03:08:18 +0000

It seems to me that the number of negative dentries per directory should be in some way based on the actual number of files in the directory (if that is knowable). The whole point of having negative dentries is to avoid having to search an entire directory just to come up empty. The cost of doing that search is likely to be dependent on how a particular filesystem does lookups and the number of files in the directory. In the limit where a directory is empty, I would argue the number of negative dentries allowed should be 0 as doing a full search of an empty directory is likely to be cheap. The time vs. space tradeoffs of doing lots of failed lookups vs. negative dentry memory use isn't clear to me, but might be to people with more experience in this area. This may at least give an upper bound on the number of negative dentries which MIGHT be useful.

Dentry negativity

nix — Tue, 17 Mar 2020 20:25:57 +0000

> The primary difficulty here is deciding how many negative dentries to allow. How to detect thrashing (a signal to increase the number of dentries allowed) and how to detect underutilisation of the cache (an opportunity to shrink the dcache and give the memory back).

Just track the hit rate, hits versus misses versus additions for lookups across the entire cache? If there are many more additions than hits, shrink the cache; if there are many more misses than hits, grow it. (Or something like that.)

(Downside: this sort of global counter is a cache nightmare, but the figures need only be approximate, so the usual trick of having per-CPU counters occasionally spilled into a global counter should work fine.)

Dentry negativity

jezuch — Tue, 17 Mar 2020 15:02:54 +0000

I noticed the clever product placement. Nicely done! ;)

Dentry negativity

luto — Mon, 16 Mar 2020 23:59:56 +0000

This isn’t necessarily a good idea, but: couldn’t a directory have a no-negative-dentry flag that is ignored for file creation? That is, for a lookup that isn’t associated with file creation, no negative dentry would be created.

Dentry negativity

hkario — Mon, 16 Mar 2020 12:21:44 +0000

... and the problem with security issues is that developers need more education.

If only we did find some time in the past 50 years to teach them, we would eliminate them completely! /s

It's not only libc problem, as the article pointed out there are others that do the same, like NSS, and thus Firefox.

Dentry negativity

Wol — Sun, 15 Mar 2020 18:06:45 +0000

I was thinking that if you were doing a lookup for lib.so, it might have a list of directories where you *wouldn't* find it.

Or the dentry list was "per directory". If you've got more entries in the negative dentry list than there are in the directory, then it makes sense to ditch the negative dentry list completely because it costs more to search the negatives than the positives - and the other responses I've had here imply that that's not true ...

Cheers,
Wol

Dentry negativity

viro — Sun, 15 Mar 2020 15:33:07 +0000

Huh? How the hell could they _not_ be path-sensitive and be of any use? After all, the same name in different directories usually refers to different objects. They are hashed by (pointer to parent dentry, name) pairs, and no, we are not doing a hash table per directory, TYVM - _that_ would have a horrible memory footprint for no good reason...

Dentry negativity

NYKevin — Sun, 15 Mar 2020 07:34:22 +0000

Just to clarify, are you saying that the kernel is doing this?

Check for a matching dentry in the cache.
If the dentry is absent from cache, do a "real" lookup of the path in question.
Now the dentry is definitely in cache, either because it was already there or because the previous step caused it to become cached.
If the cached dentry is positive, open it or fail with EEXIST as appropriate for the state of the O_EXCL flag.
If the cached dentry is negative, change it to positive and mark it dirty.
That's it. Eventually, the cached dentry will get written out to disk, but that's not our problem right now.

(Obviously, I have omitted numerous failure modes which we don't need to care about for the purposes of this discussion.)

Dentry negativity

NYKevin — Sun, 15 Mar 2020 07:17:26 +0000

> My understanding is that "the cache invalidation problem" refers to the difficulty of making sure that nobody has a stale entry (eg TLB invalidation) rather than the difficulty of knowing what to cache. Maybe that just reflects my biases as someone who has no control over what the CPU decides to cache.

A cache with a poor invalidation strategy is more succinctly known as a "memory leak."

Dentry negativity

neilbrown — Sat, 14 Mar 2020 20:45:07 +0000

> But does that mean - like someone else suggested - that dentries are path-sensitive?

lwn.net probably has an article describing this in excessive detail, however...
There is a single global hash table for dentry lookup. The lookup key is the memory address of the dentry of the containing directory (the parent) and the name within that directory (which might be treated as case-insensitive). So the actual name lookup process does not notice how many names are currently cached for a particular directory. But that isn't really the issue.

We *cannot* decide to disallow negative dentries for some directories as that would interfere with file creation. To create a new file, we first allocate a dentry and try to populate it via a lookup. If that fails, then we have a negative dentry which acts as a place holder. A lock on that dentry will prevent anyone else from acting on the same name (I don't think we currently use that fact as much as we could).

We do have directories where we *know* that all entries are in the dcache - tmpfs for example and anything else that uses "simple_lookup". We could set a very short time-to-live for negative dentries in those directories (though we would still want the ttl to be an order of magnitude more than that cost of allocating and freeing a dentry), and we might be able to let a filesystem mark a directory as 'fully-cached'. I doubt there are many workloads that would really benefit though.
(Here's a crazy idea. Any directory that hasn't been changed for N seconds gets a 'bloom-filter' attached when a readdir happens. The bloom filter is given the names of all existing objects in the directory. When a negative dentry is added that is *not* in the bloom filter, the dentry goes on a separate LRU with a short lifetime - the justification being that repopulating such negative dentries is cheap, requiring only a re-check of the bloom filter. Would this complexity be worth the benefit.... I doubt it).

Dentry negativity

neilbrown — Sat, 14 Mar 2020 20:23:01 +0000

> ... refers to the difficulty of making sure that nobody has a stale entry .... rather than the difficulty of knowing what to cache.

The fact that these two problems might have the same name is certainly delightful.
I would describe "the cache invalidation problem" as "choosing whether to invalidate something, and what, and when".

> The primary difficulty here is deciding how many negative dentries to allow.

I think that is a narrow formulation. If you look at the email that introduced the recent patches you will see two problems:
1/ speed of cleaning up negative dentries at unmount
2/ speed of freeing up memory used by negative dentries when memory is needed for something else.

i.e. the problem is speed. Reducing the number of negative dentries might help - certainly with 1, probably with 2 - but it is a secondary issue, not a primary one.
Problem 1 could be addressed with some sort of lazy-unmount protocol. We don't *need* to release all cache memory before reporting success for unmounting a filesystem. We just need to be sure it can be released (not currently in use) and that it cannot be accessed again.

Problem 2 could be addressed by optimizing the code (maybe - it's probably quite light weight already ... though I wonder if a negative dentry needs to be linked into the list from its parent - probably not if an alternate way could be provided to invalidate the ->parent pointer when the parent is freed) or by pruning negative dentries earlier (hence my comment about a shrinker with a different 'seeks' value) or by pruning some other cache - because when you need memory, you don't much care exactly what is sacrificed to provide it.

> Do you have any insight into how we might measure the effectiveness of the current cache?

Disable it and try to get some work done.
Any cache provides diminishing returns as it grows beyond the size of the working set, and as the "working set" changes over time, you can only hope for an approximate size. We have that by applying modest vm pressure.
The best heuristic for "should I provide more pressure on caches" is "am I being asked to apply lots of pressure". So the more often we need to find free memory, the more memory we should find each time (do we already do that?)
But that needs to be balanced against the risk of creating unnecessary pressure by pruning things that are needed again soon (thrashing). Maybe there is value in keeping a bloom filter recording identifies of recently pruned objects, and if the hit rate on that suggests we are re-populating objects that were recently removed, we could slow down the pruning. I suspect there are some circumstances were such a filter would help, but I doubt it would really be useful in general.

A really big problem with this stuff is that you cannot improve estimates of need without accounting of some sort, and any accounting has a cost - particularly global accounting on a multi-core multi-cache machine. As the primary problem is speed, you want to make sure that cost is (nearly) invisible.

Dentry negativity

dezgeg — Sat, 14 Mar 2020 15:39:58 +0000

Steps 4. and 5. are just a single step: the existing negative dentry for cowbell is turned into a positive one. All file creations are done this way (regardless of whether the cowbell negative dentry existed in memory due to openat attempt or not).

Dentry negativity

jlayton — Sat, 14 Mar 2020 13:36:21 +0000

> 2) Negative dentries should perhaps be limited to some proportion of the *positive* dentries in a directory, rather than an absolute number.

This idea completely breaks down once you have to deal with (most) network filesystems. NFS (e.g.) won't tell you anything about the number of entries in a directory when you do a LOOKUP, and in any case that info might be invalid the moment the LOOKUP reply leaves the server.

I just don't see how the number of positive dentries is at all connected to how many negative dentries we should cache per directory.

Dentry negativity

jlayton — Sat, 14 Mar 2020 13:13:53 +0000

Doubtful. The names are stored in a hashtable. Representing a range of entries in there would be pretty hard to do. I suppose you could layer on some sort of negative range carveout mechanism on top of the hashtable, but that sounds a bit nasty.

Dentry negativity

pr1268 — Sat, 14 Mar 2020 13:00:48 +0000

How expensive is the management of negative dentries (or dentries in general)?

For example:

openat(AT_FDCWD, "cowbell", O_RDONLY|O_CLOEXEC) = -1
Kernel adds negative dentry
User types at keyboard $ touch cowbell (in FDCWD)
Kernel adds positive dentry
Kernel removes negative dentry

Couldn't this get a little expensive sometime? (I'm unsure what order 4 and 5 would happen.)

And I'm referring to how the kernel does things _now_.

Also, couldn't dentries be set for directory names? (I'm referring to the part about "... the negative dentries were created by deleting a large directory full of files" blurb of the 2002 LWN article linked above.)

Dentry negativity

Wol — Sat, 14 Mar 2020 11:47:25 +0000

Premature optimisation is the root of all evil ... :-)

But does that mean - like someone else suggested - that dentries are path-sensitive? Or are they cached by path-name rather than object-name?

I was thinking rather simplistically, but it sounds like the problem is somewhat horrid :-)

Cheers,
Wol

Dentry negativity

willy — Sat, 14 Mar 2020 11:13:37 +0000

> This is *exactly* the cache invalidation problem and there is no general solution.

My understanding is that "the cache invalidation problem" refers to the difficulty of making sure that nobody has a stale entry (eg TLB invalidation) rather than the difficulty of knowing what to cache. Maybe that just reflects my biases as someone who has no control over what the CPU decides to cache.

The primary difficulty here is deciding how many negative dentries to allow. How to detect thrashing (a signal to increase the number of dentries allowed) and how to detect underutilisation of the cache (an opportunity to shrink the dcache and give the memory back).

Do you have any insight into how we might measure the effectiveness of the current cache?

Dentry negativity

dezgeg — Sat, 14 Mar 2020 10:39:06 +0000

> IME locale data files provide a consistently bad example. Couldn't systemd run something once per bootup and store a "mirror list" e.g. in ~/.cache/.../locale_files.d/ as links to do what positive dentry does (IIUC) and avoid hitting need for negative dentry at all?

Glibc can already do that, by the means of the locale-archive database. But as is apparent from the listing in the article, whichever distro is used has not enabled it.

Dentry negativity

neilbrown — Sat, 14 Mar 2020 10:06:04 +0000

> and thus almost intractable?

not "almost".

> that have proven useful in the past.

Past performance is not indicative of future results.

This is *exactly* the cache invalidation problem and there is no general solution.
Sometimes you can add RAM so your cache becomes bigger than your working set.
Sometimes you can apply behaviour modification so your working set becomes smaller than your cache.
Sometimes you can slip in a heuristic that helps your use case today, and no-one else notices.

But there is very little else that can be done.
The dcache already has a "referenced" flag which results in never-referenced dentries having shorter life expectancy. That sometimes helps, but I suspect it sometimes hurts too.

We have a few interfaces to allow programs to voluntarily be less demanding on the page cache (so we can apply behaviour modification to code). Maybe O_PONIES ... sorry, I mean O_NO_NOCACHE for filename lookup that limits the caching of negative entries created for that lookup.

Dentry negativity

mm7323 — Sat, 14 Mar 2020 07:23:09 +0000

It feels like speeding up path search is a lot of the reason for wanting negative dentries, but at the same time the number of path entries searched before a 'hit' will act as a multiplier for the number of negative dentries needed for an effective cache.

Since adding system calls for specific cases seems popular these days, how about adding something to resolve path search with a positive cache in the kernel e.g. int pathsearch(const char *filename, char *const path[] /* NULL terminated list of paths */); which returns either the index of the first path where filename exists or -ENOENT etc...

The cache structure maybe complex, requiring the path list and filename to be combined to a key, but this could then implement a positive cache with one entry per (successful) lookup, as a single system call from userspace (rather than repeated calls to access(), open() or exec() as is typically done for path search now). Other file system operations would also need to invalidate the cache as needed, possibly in vast swathes depending on how fast vs fine grained invalidation would want to be.

Such a cache could be made in userspace, using inotify() for invalidation and some sort of daemon with IPC to share the cache between processes (e.g. repeated invocations of gcc looking for includes), but it would probably be a bit racy and not give the full performance benefit.

Dentry negativity

marcH — Sat, 14 Mar 2020 06:48:18 +0000

> it’s just that their memory usage is tracked against the limit for that specific control group.

for which "specific" group? A read-only page can be used by any number of groups.

Apparently there was an attempt to "charge" each memory page to only one group: https://lwn.net/Articles/443241/ Did this get merged and again: charged to which group?

Dentry negativity

viro — Sat, 14 Mar 2020 06:26:53 +0000

Lookups are done in hash, not in per-directory lists. And if the length of hash chain is affected by the distribution of dentries among the parents, the hash function is badly fucked. Do you have evidence of such?

Dentry negativity

willy — Fri, 13 Mar 2020 20:52:52 +0000

Since this is a cache of names, it must be a CS-hard problem and thus almost intractable?

I think we need more than a simple LRU list. If I have my cache sized nicely for compiling the kernel and someone else comes along and uses that program that deliberately opens 50k files that don't exist, I don't want it to compete against the negative dentries that have proven useful in the past. Perhaps we need an LFU. I'm not conversant with the latest techniques in preventing cache pollution.

Dentry negativity

neilbrown — Fri, 13 Mar 2020 20:46:37 +0000

> Either way, we have a target number of negative dentries and need to adjust the target up or down, depending on how the workload is behaving.

Is this just a case of having a separate LRU for negative dentries, and then setting a different 'seeks' count for the relevant shrinker?

(I'm reminded that cache invalidation is one of the three hard problems of computer science, along with naming things).

Dentry negativity

NYKevin — Fri, 13 Mar 2020 20:33:19 +0000

Blaming application developers is futile. As the article shows, even a trivial "hello world" program like /usr/bin/echo goes traipsing all over the filesystem looking for locale files, shared libs, and so on. I very much doubt the actual GNU Coreutils source for echo has any of those lookups in its main(). This is a libc problem. Wearing my sysadmin hat for a moment, I do not want to deal with the flag day that will ensue when libc removes all of those lookups in favor of (something else).

Dentry negativity

Sesse — Fri, 13 Mar 2020 20:13:01 +0000

But Tetrinet is the only social contact I have left in these Covid-19 times!

Dentry negativity

iabervon — Fri, 13 Mar 2020 19:44:10 +0000

You'd have to make the cache more elaborate and complicate invalidation rules, but you could potentially cache the fact that every (positive) dentry in the directory is cached. Seems like it would be more trouble than it's worth, but technically possible.

Dentry negativity

bokr — Fri, 13 Mar 2020 19:32:14 +0000

I would agree if it were a "fix," but it is not.
How does that "fix" provide a path to better next versions
of those "thousands upon thousands of apps"? It doesn't.

It lets app developers continue with bad design, perhaps
even unwittingly, because the clever file system implementers
have hidden the worst effects of the bad app (or lib used) design.

It's great to optimize file operations and make bad apps usable, but it
doesn't "fix" them :)

Dentry negativity

nivedita76 — Fri, 13 Mar 2020 16:32:59 +0000

On my gentoo system, it generates only 3 openat calls, all of which are successful.

The only failed lookup is
access("/etc/ld.so.preload", R_OK) = -1 ENOENT (No such file or directory)

Dentry negativity

nybble41 — Fri, 13 Mar 2020 15:07:29 +0000

Borrowing a bit from DNSSEC, could the negative entries be represented as a range rather than specific names? Then the maximum number of negative entries—at least for compatible filesystems—would be limited to one more than the number of entries in each directory. The filesystem would need to report the first and last contiguous missing names around the missing entry on lookup. Smaller approximate ranges (with length=1 being the current behavior) could be used where necessary, e.g. network filesystems that aren't set up to report the necessary information. Adjacent or overlapping ranges would be merged in the cache.

Dentry negativity

willy — Fri, 13 Mar 2020 14:28:38 +0000

A lot of people espouse the opinion that the number of negative dentries should be proportional to the number of positive dentries, and there doesn't seem to be a lot of reason why.

If your search path is /home/josh/lib:/usr/local/lib:/usr/lib:/lib
you're going to want to cache the fact that libiberty.so is not found in the first two, but is in the third. So for this specific lookup case you need twice as many negative as positive dentries.

If your workload involves a lot of looking for libraries, then this ratio will dominate. If your workload is almost anything else, then some other ratio would be better.

Right now, our number of negative dentries is really only constrained by the amount of memory in the machine, which is ridiculous. I want to use that memory for caching useful things, not that Tetris is not present in /home/willy/bin.

This is why I say we need to autotune the number of negative dentries. And once we're autotuning the number of negative dentries, it doesn't matter whether we express that as a fraction of the number of positive dentries, or as an absolute number. Either way, we have a target number of negative dentries and need to adjust the target up or down, depending on how the workload is behaving.

Dentry negativity

willy — Fri, 13 Mar 2020 13:53:19 +0000

It doesn't work. There are three states here -- present, not-present and unknown. Failing to find a positive dentry is not the same thing as finding a negative dentry.

Dentry negativity

Paf — Fri, 13 Mar 2020 13:49:02 +0000

No, just memory tracking for the dentries would be divided; they’re still in the regular cache, it’s just that their memory usage is tracked against the limit for that specific control group.

Dentry negativity

josh — Fri, 13 Mar 2020 11:54:31 +0000

Ah, true! If you have a tiny number of actual files, you can very quickly rule out the existence of an entry without needing negative dentries. So, that heuristic might work after all.