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

[Nick Piggin <npiggin@suse.de>]

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.