Re: Bug: Discontigmem virt_to_page() [Alpha,ARM,Mips64?]

[William Lee Irwin III <wli@holomorphy.com>]

On Thursday 02 May 2002 03:45, William Lee Irwin III wrote:
>> I remember suggesting a sorted array of extents on which binary
>> search could be performed. A B-tree seems unlikely but perhaps if
>> it were contiguously allocated and some other tricks done it might
>> do, maybe I don't remember the special sauce used for the occasion.

On Wed, May 01, 2002 at 04:02:33AM +0200, Daniel Phillips wrote:
> Thanks for the correction.  When you said 'extents' I automatically thought
> 'btree of extents'.  I'd tend to go for the hash table anyway - your binary
> search is going to take quite a few more steps to terminate than the bucket
> search, given some reasonable choice of hash table size.

It's probably motivated more by sheer terror of another huge hash table
sized proportional to memory eating the kernel virtual address space
alive than anything else. I probably should have used reverse psychology
instead. I should note that the size of the array I suggested is not
proportional to memory, only to the number of fragments. It would
probably only have a distinct advantage in a situation where both the
fragment sizes and distributions are irregular; when the number of
fragments is in fact proportional to memory it gains little aside from
a small factor of compactness and/or in-core contiguity. The hashing
techniques that seem obvious to me effectively require some sort of
objects to back a direct mapping, which translates to per-page overhead,
which I'm very very picky about. I also like things to behave gracefully
about space and time when faced with irregular or "hostile" layouts.

Actually, now that I think about it, a contiguously-allocated B-tree of
extents doesn't sound bad at all, even without additional dressing. Do
you think it's worth a try?

Cheers,
Bill