Re: [rfc][patch] dynamic resizing dentry hash using RCU

[Nick Piggin <npiggin@suse.de>]

On Fri, Feb 23, 2007 at 05:31:30PM -0800, Michael K. Edwards wrote:
> On 2/23/07, Zach Brown <zab@zabbo.net> wrote:
> >I'd love to see a generic implementation of RCU hashing that
> >subsystems can then take advantage of.  It's long been on the fun
> >side of my todo list.  The side I never get to :/.
> 
> There's an active thread on netdev about implementing an RCU hash.
> I'd suggest a 2-left (or possibly even k-left) hash for statistical
> reasons discussed briefly there, and in greater depth in a paper by
> Michael Mitzenmacher at
> www.eecs.harvard.edu/~michaelm/NEWWORK/postscripts/iproute.ps.
> Despite his paper's emphasis on hardware parallelism, there's a bigger
> win associated with Poisson statistics and decreasing occupation
> fraction (and therefore collision probability) in successive hashes.

Thanks for the link, I'll take a look.

I'm *pretty* sure that my algorithm will work with any kind of data
structure. It could even change from one to another completely different
data structure.

The important point is that, when a switch is in progress, the data
structure effectively becomes the union of the old and the new. Readers
insert items only into the new structure, but it is implicit that they
have checked for collisions in the union (in the case where collisions are
possible).

And finally, (you probably gathered this, but I'll just make it clear),
I haven't implemented a lockless hash lookup. The dcache already has this.
My algorithm is a lockless dynamic data structure switch, rather than
having anything specifically to do with a specific type of hash, or even
a hash at all. So yes, it should be applicable to resizing a 2-left hash or
whatever.

Thanks,
Nick