linux-kernel - Re: [patch][rfc] ddds: "dynamic dynamic data structure" algorithm, for adaptive dcache hash table sizing

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] [day] [month] [year] [list]

Message-ID: <20081008032714.GD6499@wotan.suse.de>
Date:	Wed, 8 Oct 2008 05:27:15 +0200
From:	Nick Piggin <npiggin@...e.de>
To:	"Paul E. McKenney" <paulmck@...ux.vnet.ibm.com>
Cc:	David Miller <davem@...emloft.net>, linux-kernel@...r.kernel.org,
	linux-mm@...ck.org, linux-netdev@...r.kernel.org,
	josh@...edesktop.org
Subject: Re: [patch][rfc] ddds: "dynamic dynamic data structure" algorithm, for adaptive dcache hash table sizing

On Tue, Oct 07, 2008 at 08:12:45PM -0700, Paul E. McKenney wrote:
> On Wed, Oct 08, 2008 at 04:48:13AM +0200, Nick Piggin wrote:
> > On Tue, Oct 07, 2008 at 02:08:25PM -0700, David Miller wrote:
> > > From: Nick Piggin <npiggin@...e.de>
> > > Date: Tue, 7 Oct 2008 08:48:34 +0200
> > > 
> > > > I'm cc'ing netdev because Dave did express some interest in using this for
> > > > some networking hashes, and network guys in general are pretty cluey when it
> > > > comes to hashes and such ;)
> > > 
> > > Interesting stuff.
> > > 
> > > Paul, many months ago, forwarded to me a some work done by Josh
> > > Triplett called "rcuhashbash" which had similar objectives.  He did
> > > post it to linux-kernel, and perhaps even your ideas are inspired by
> > > his work, I don't know. :-)
> > 
> > Hmm yes I did see that. It's not too similar, as it focuses on re-keying
> > an existing element into the same hash table. ddds can't do that kind of
> > thing (the underlying data structure isn't visible to the algorithm, so
> > it can't exactly modify data structures in-place), although in another
> > sense it is more general because the transfer function could transfer
> > items into another hash table and re-key them as it goes (if it did that,
> > it could probably use Josh's "atomic" re-keying algorithm too).
> > 
> > But largely it does seem like they are orthogonal (if I'm reading
> > rcuhashbash correctly).
> 
> IIRC, one of the weaknesses of rcuhashbash was that the elements had
> to be copied in some cases.

Yes, I noticed that.


>  Josh has been working on a variant that
> (hopefully) allows elements to be moved without copying, as is required
> by dcache.

So is it able to actually resize the hash table? If so, I couldn't quite see
how it works; if not, I'd be interested to know what is the application to
dcache. Josh?

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/