Negative dentries, 20 years later

Posted Apr 12, 2022 21:42 UTC (Tue) by Wol (subscriber, #4433)
In reply to: Negative dentries, 20 years later by NYKevin
Parent article: Negative dentries, 20 years later

> You have entirely missed the point. We're not trying to figure out whether the bucket is occupied, we're trying to find its nearest occupied neighbors so that we can find an empty range of buckets. That requires a linear scan over neighboring buckets.

Except you completely missed the point I was responding to. cesarb was talking about a hashed directory, and not a cache.

And in that case, there are NO empty buckets (if you want to use that particular variant of hashing). The variant I'm used to sticks multiple entries per bucket, but there's a variant that has exactly as many buckets as entries, and one entry per bucket.

And just as it's very quick and easy to grow the table, it's just as easy to shrink it - the entire bucket you're getting rid of just tags on the end of the bucket the (now invalid) old hash hashes to.

Cheers,
Wol