Dentry negativity
Dentry negativity
Posted Mar 14, 2020 10:06 UTC (Sat) by neilbrown (subscriber, #359)In reply to: Dentry negativity by willy
Parent article: Dentry negativity
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.
Posted Mar 14, 2020 11:13 UTC (Sat)
by willy (subscriber, #9762)
[Link] (3 responses)
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?
Posted Mar 14, 2020 20:23 UTC (Sat)
by neilbrown (subscriber, #359)
[Link]
The fact that these two problems might have the same name is certainly delightful.
> 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:
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 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.
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.
Posted Mar 15, 2020 7:17 UTC (Sun)
by NYKevin (subscriber, #129325)
[Link]
A cache with a poor invalidation strategy is more succinctly known as a "memory leak."
Posted Mar 17, 2020 20:25 UTC (Tue)
by nix (subscriber, #2304)
[Link]
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
Dentry negativity
I would describe "the cache invalidation problem" as "choosing whether to invalidate something, and what, and when".
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.
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.
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.
Dentry negativity
Dentry negativity