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

Andrea Arcangeli (andrea@suse.de)
Mon, 29 Jul 2002 22:52:11 +0200


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
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/