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

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]

Message-ID: <20081007075309.GA16143@wotan.suse.de>
Date:	Tue, 7 Oct 2008 09:53:09 +0200
From:	Nick Piggin <npiggin@...e.de>
To:	Christoph Hellwig <hch@...radead.org>
Cc:	Linux Kernel Mailing List <linux-kernel@...r.kernel.org>,
	Linux Memory Management List <linux-mm@...ck.org>,
	netdev@...r.kernel.org, Paul McKenney <paulmck@...ibm.com>
Subject: Re: [patch][rfc] ddds: "dynamic dynamic data structure" algorithm, for adaptive dcache hash table sizing (resend)

On Tue, Oct 07, 2008 at 03:18:27AM -0400, Christoph Hellwig wrote:
> > 
> > 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 ;)
> 
> Without even looking at the code I'd say geeting the dcache lookup data
> structure as a hash is the main problem here.  Dcache lookup is
> fundamentally a tree lookup, with some very nice domain splits
> (superblocks or directories).

Dcache lookup is partially a tree lookup, but also how do you look up
entries in a given directory? That is not naturally a tree lookup. Could
be a per directory tree, though, or a hash, or trie.

Anyway, I don't volunteer to change that just yet ;)


>  Mapping these back to a global hash is
> a rather bad idea, not just for scalability purposes.

I don't disagree. But it can be improved by dynamically resizing
until it is replaced. I guess it is also a demonstration of how to
implement the algorithm.

PID hash is probably another good one to convert.

--
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/