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

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date:	Sat, 24 Feb 2007 02:52:44 +0100
From:	Nick Piggin <npiggin@...e.de>
To:	"Michael K. Edwards" <medwards.linux@...il.com>
Cc:	Zach Brown <zab@...bo.net>,
	Linux Kernel Mailing List <linux-kernel@...r.kernel.org>,
	Davide Libenzi <davidel@...ilserver.org>,
	"Paul E. McKenney" <paulmck@...ux.vnet.ibm.com>
Subject: Re: [rfc][patch] dynamic resizing dentry hash using RCU

On Fri, Feb 23, 2007 at 05:31:30PM -0800, Michael K. Edwards wrote:
> On 2/23/07, Zach Brown <zab@...bo.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
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/