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: <20070224020746.GD2201@wotan.suse.de>
Date:	Sat, 24 Feb 2007 03:07:46 +0100
From:	Nick Piggin <npiggin@...e.de>
To:	Zach Brown <zab@...bo.net>, David Miller <davem@...emloft.net>
Cc:	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 Sat, Feb 24, 2007 at 02:26:02AM +0100, Nick Piggin wrote:
> On Fri, Feb 23, 2007 at 09:25:28AM -0800, Zach Brown wrote:
> > 
> > On Feb 23, 2007, at 7:37 AM, 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.
> > 
> > Can you compare what you've done to the design that Paul and David  
> > talked about a year ago?
> > 
> >   http://lkml.org/lkml/2006/1/30/74
> 
> Thanks for the link, I wasn't aware of Paul's algorithm before.
> 
> I guess most variants are going to have a double pointer scheme,
> so they are similar in that regard.
> 
> I think Paul's is quite complex in moving entries to the new table,
> and it looks like it requires a lot of grace periods. I avoid all
> that by using the seqlock.
> 
> It wasn't clear to me how Paul handled the case where an item is
> present in the not_current table, but the lookup misses it when it
> gets moved between the tables. It is a little tricky to follow
> the find details because it is not in code or pseudo code format.


I guess the other thing is that Paul's seems quite hash specific,
wheras mine does not have to be tied to any particular data strcture.

All you need it to know how to perform a lookup on both your old
and new data structure, and the same algorithm is basically applicable
to switching between any 2 data structures.


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