Re: [BK PATCH 2.5] Introduce 64-bit versions of PAGE_{CACHE_,}{MASK,ALIGN}

[Andrea Arcangeli]

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).

> Then again, Andi says that sizeof(struct page) is a problem for
> x86-64.

not true.

> No recursion needed, no allocations needed.

the 28 bytes if they're on the stack they're like recursion, just using
an interactive algorithm.

you're done with 28 bytes with a max 7/8 level tree, so 7*4 = 28 (4 size
of pointer/long). On a 32bit arch the max index supported is
2^32, on a 64bit arch the max index supported is
2^(64-PAGE_CACHE_SHFIT), plus each pointer is 8 bytes. You may want to
do the math to verify if you've enough stack to walk the tree in order,
it's not obvious.

> But I don't see any showstoppers here.

on a 32bit arch with 32bit index it seems ok to me too, on 64bit
somebody has to do the math and it's not really obvious to me that's
feasible.

Andrea