Negative dentries, 20 years later

Posted Apr 11, 2022 18:19 UTC (Mon) by dskoll (subscriber, #1630)
Parent article: Negative dentries, 20 years later

It seems to me that a negative dentry is useful only to the extent that it's hit. So what if the total number of negative dentries was limited to some small number and if that number is exceeded, then either (1) we evict an entry that has never been hit yet (or hit fewer than N times), or (2) we increase the negative dentry cache size by some amount if all negative dentries have been hit at least once (or at least N times).

This means keeping track of how many times a negative dentry is hit.

Caveat: I'm not a kernel programmer and have no idea how this would work in practice with the existing data structures.

Negative dentries, 20 years later

Posted Apr 11, 2022 18:56 UTC (Mon) by willy (subscriber, #9762) [Link] (3 responses)

You're absolutely correct that never-accessed negative dentries have no value. And we even have a single bit that says whether the dentry has been accessed since the last time it got to the end of the LRU list. The problem is, as Dave says, that we don't try to turn the list over to find which ones are and aren't used until were under general memory pressure.

Negative dentries, 20 years later

Posted Apr 11, 2022 19:03 UTC (Mon) by dskoll (subscriber, #1630) [Link] (2 responses)

Right. I guess limiting the size of the dentry cache so we start evicting before we have general memory pressure is the main idea, but allowing it to expand if by some miracle all entries have been hit so that it scales up if memory is available.

Negative dentries, 20 years later

Posted Apr 11, 2022 19:31 UTC (Mon) by willy (subscriber, #9762) [Link] (1 responses)

The idea I'm currently advocating (a little busy with other projects to work on myself) is that after allocating 100 entries, we scan 110 entries at the tail of the list and either return them to the head of the list with their 'referenced' flag cleared, or free them. That allows the cache to both shrink (if <100 have been referenced) and grow (if >100 have been referenced)

Obviously those numbers are a bit magic. Why not 150? Or 200? Needs some experimentation.

Negative dentries, 20 years later

Posted Apr 12, 2022 7:44 UTC (Tue) by geert (subscriber, #98403) [Link]

Why not a power of two? ;-)