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 | `----------------------------------------------------------------------'