lkml.org 
[lkml]   [1996]   [Nov]   [27]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    /
    Date
    From
    SubjectRe: Please don't beat me up (was Re: Bugs and wishes in memory management area)

    > IMHO, the problem is that once a pointer is given out, you cannot
    > reogranize your logical->physical memory mappings. With the page table
    > solution you can. It's a CPU hardware feature that is hard to emulate.

    But you don't need to reorganize, you don't need paging and you don't
    need to emulate it.

    Buddy is expensive because it *always* tries to coalesce pages to
    power of two blocks (despite the fact that 99.99% of requests are
    for single blocks anyway) and only ever coalesces neighbouring
    blocks of the same size (which makes it hideously vulnerable to
    fragmentation).

    I use page arrays of arbitrary length (up to a suitably arbitrary
    maximum). I use lazy coalescing to optimise the common, single
    page case - this imposes an extra overhead on the first miss but
    this is not serious for infrequent requests and frequent requests
    tend to keep the queues of larger sizes suitably topped up (so
    requests show the same overhead as the single page case). Being
    able to add a single page to a 4 page array to get 5 is a _lot_
    easier than finding two neighbouring 4s to join. When coalescing
    pages I check to see if neighbouring pages are in the page cache
    but otherwise unused. If so I reclaim them immediately rather
    than waiting for shrink_mmap to clock through memory and get
    round to releasing them (we could do this at interrupt time too
    if I mutex the inode and page cache modifications).

    I do kmalloc in a similar-ish way, treating pages as arrays of
    small (16 byte) "paragraphs" (although the optimum solution appears
    to be not to coalesce them but allocate new page arrays and let
    the current ones fragment away, dropping them when the become
    entirely free - 99.99% of kmalloc action is below 1k).

    These schemes allow good handling of requests for arbitrary
    amounts of memory but the simplicity of the algorithm gives around
    zero cost. My current benchmarking shows the difference in raw
    performance (latency and bandwidth) between this and the old buddy
    code to be down in the noise - if anything I am a small percentage
    faster. I can still trim a few more instructions as well - plus I
    have a fair amount of statistics gathering and the like in there :-).

    Hopefully it will be ready for the harsh light of day in a couple
    of weeks so you lot can break it :-).

    Mike

    --
    .----------------------------------------------------------------------.
    | Mike Jagdis | Internet: mailto:mike@roan.co.uk |
    | Roan Technology Ltd. | |
    | 54A Peach Street, Wokingham | Telephone: +44 118 989 0403 |
    | RG40 1XG, ENGLAND | Fax: +44 118 989 1195 |
    `----------------------------------------------------------------------'


    \
     
     \ /
      Last update: 2005-03-22 13:38    [W:2.444 / U:0.016 seconds]
    ©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site