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]

Message-ID: <20070224050937.GA16601@wotan.suse.de>
Date:	Sat, 24 Feb 2007 06:09:37 +0100
From:	Nick Piggin <npiggin@...e.de>
To:	William Lee Irwin III <wli@...omorphy.com>
Cc:	Linux Kernel Mailing List <linux-kernel@...r.kernel.org>
Subject: Re: [rfc][patch] dynamic resizing dentry hash using RCU

On Fri, Feb 23, 2007 at 08:24:44PM -0800, William Lee Irwin III wrote:
> On Fri, Feb 23, 2007 at 04:37:43PM +0100, Nick Piggin wrote:
> > The dentry hash uses up 8MB for 1 million entries on my 4GB system is
> > one of the biggest wasters of memory for me. Because I rarely have
> > more than one or two hundred thousand dentries. And that's with
> > several kernel trees worth of entries. Most desktop and probably even
> > many types of servers will only use a fraction of that.
> > So I introduce a new method for resizing hash tables with RCU, and apply
> > that to the dentry hash.
> > The primitive heuristic is that the hash size is doubled when the number of
> > entries reaches 150% the hash size, and halved when the number is 50%.
> > It should also be able to shrink under memory pressure, and scale up as
> > large as we go.
> 
> You would be better served by a data structure different from a hashtable.

Possibly. Note that I wasn't intending to rewrite the dcache hash
specifically, but just demonstrate my lockless dynamic data structure
switch, and the dentry hash was the most obvious candidate.

But considering that it is lockless, and basically free in the fastpath
(ie. a single easily-predicted branch), then I'm better served by an
dynamically sized dynamic hash table than an inappropriately sized one.

Well, almost. The vmalloc issue is the downside, of course. But if I'm
on a NUMA that is doing vmalloc hashes anyway, then there is little
downside.

Out of curiosity, what better data structure do you have in mind for
the dentry hash?
-
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/