Request for code comments, RB tree for vm_map_findspace()
--20cf303f6d60348c7f049e0fc94f
Content-Type: text/plain; charset=UTF-8
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
--20cf303f6d60348c7f049e0fc94f
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
Hi,<br><br><a href=3D"ht=" rel="nofollow">http://m-net.arbornet.org/~sv5679/vm_map_simple.c">ht=
tp://m-net.arbornet.org/~sv5679/vm_map_simple.c</a> is a bit of code that r=
eworks 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 unl=
ike the existing RB tree connecting maps and map entries, this one is keyed=
by length of free address space holes. <br>
<br>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 searchi=
ng for KVA holes.<br><br>I do not implement the start and align arguments t=
o 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 sc=
an back upwards to the nearest parent. Does that sound better?<br>
<br>Thanks!<br clear=3D"all">-- vs<br>
--20cf303f6d60348c7f049e0fc94f--