Re: [BK PATCH 2.5] Introduce 64-bit versions of

[Andrew Morton]

Andrea Arcangeli wrote:
> 
> On Mon, Jul 29, 2002 at 02:01:15PM -0700, Andrew Morton wrote:
> > Andrea Arcangeli wrote:
> > >
> > > On Sun, Jul 28, 2002 at 07:05:19PM -0700, Andrew Morton wrote:
> > > > But yes, all of this is a straight speed/space tradeoff.  Probably
> > > > some of it should be ifdeffed.
> > >
> > > I would say so. recalculating page_address in cpu core with no cacheline
> > > access is one thing, deriving the index is a different thing.
> > >
> > > > The cost of the tree walk doesn't worry me much - generally we
> > > > walk the tree with good locality of reference, so most everything is
> > > > in cache anyway.
> > >
> > > well, the rbtree showedup heavily when it started growing more than a
> > > few steps, it has less locality of reference though.
> > >
> > > >    Good luck setting up a testcase which does this ;)
> > >
> > > a gigabit will trigger it in a millisecond. of course nobody tested it
> > > either I guess (I guess not many people tested the 800Gbyte offset
> > > either in the first place).
> >
> > There's still the mempool.
> 
> that's hiding the problem at the moment, it's global, it doesn't provide
> any real guarantee.

Sizing the mempool to max_cpus * max tree depth provides a guarantee,
provided you take care of context switches, which is pretty easy.

> ...
> 
> so it's not too bad in terms of stack because there's not going to be
> more than one walk at time, thanks for doing the math btw. You'd
> basically need a second radix tree for the dirty pages (using the same
> radix tree is not an option because it would increase pdflush complexity
> too much with terabytes of clean pages in the tree).

Not sure.  If each ratnode has a 64-bit bitmap which represents
dirty pages if it's a leaf node, or nodes which have dirty pages
if it's a higher node then the "find the next 16 dirty pages above index
N" is a pretty efficient thing.

Tricky to code though.