On Mon, Apr 04, 2011 at 03:00:43PM +0200, Ariane van der Steldt wrote: > Please test this diff to uvm_map on as many architectures as possible. > Contains a number of fixes and a better algorithm.
It makes sure random address space allocations happen (and enables it in the kernel) without causing the fragmented mess that the current implementation does. It works by keeping lists of allocatable space in a tree, sorted by size. Whenever an allocation is made, the first entry in the tree and up to 8 entries after it are considered, one of them is randomly chosen. From the chosen area, a random offset is chosen (any address, unless the size tree contains too many segments, in which case only the lowest and highest offsets are chosen). Differences: - The current allocator may fail when memory is available (because it searches forward only), while my implementation won't fail until we really run out of memory. - It keeps a target for fragmentation: if fragmentation is more than the target, allocations happen randomly without creating more fragmentation. - It uses a best-fit algorithm, so is better able to use available space. - It has a proper implementation of guard pages in the kernel. - vm_maps that are vmspaces now have a bit set, in which case the allocator will update the vmspace data (instead of the caller needing to do that). - uvm_map no longer needs a hint address (address is ignored unless MAP_FIXED). Ciao, -- Ariane
