Messages in this thread |  | | Date | Wed, 27 Nov 1996 13:38:29 +0000 (GMT/BST) | From | Mike Jagdis <> | Subject | Re: 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 | `----------------------------------------------------------------------'
|  |