Hi, http://m-net.arbornet.org/~sv5679/vm_map_simple.c is a bit of code that reworks vm_map_findspace to use a Red-black tree to find free sections of VA. The RB tree is rooted at each vm_map and contains vm_map_entries, but unlike the existing RB tree connecting maps and map entries, this one is keyed by length of free address space holes.
The compare function first keys based on free span length and second on start address of the map entry. This favors low addresses first in searching for KVA holes. I do not implement the start and align arguments to vm_map_findspace(). Advice on how to implement them would be appreciated! Also, I suspect that my _findspace() is not great. It should probably scan down the tree till it finds and exact fit. If it doesn't, it should scan back upwards to the nearest parent. Does that sound better? Thanks! -- vs
