DragonFly BSD
DragonFly kernel List (threaded) for 2011-03
[Date Prev][Date Next]  [Thread Prev][Thread Next]  [Date Index][Thread Index]

Request for code comments, RB tree for vm_map_findspace()


From: Venkatesh Srinivas <me@xxxxxxxxxxxxxxxxxxx>
Date: Wed, 9 Mar 2011 12:08:44 -0500

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


[Date Prev][Date Next]  [Thread Prev][Thread Next]  [Date Index][Thread Index]