[lkml]   [2002]   [May]   [1]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
Messages in this thread
    SubjectRe: Bug: Discontigmem virt_to_page() [Alpha,ARM,Mips64?]
    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?

    To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
    the body of a message to
    More majordomo info at
    Please read the FAQ at

     \ /
      Last update: 2005-03-22 13:25    [W:0.024 / U:0.616 seconds]
    ©2003-2016 Jasper Spaans. hosted at Digital OceanAdvertise on this site