DragonFly kernel List (threaded) for 2010-10
'Change the vm_map lookup algorithm'
-----BEGIN PGP SIGNED MESSAGE-----
I saw a new project on the wiki's Projects page about 'change the VM map
lookup algorithm'. (Thanks sjg and co. for keeping the projects page
(Just a little background)
Every VM map in (D)FBSD is composed of a number of vm_map_entries; each
map entry covers a contiguous range of addresses in the map. Given an
address and a map, there is currently a VM function, vm_map_lookup_entry,
which will find the vm_map entry containing it. In DragonFly, there is
currently a red-black tree, rooted in the vm_map for this mapping. 
FreeBSD uses a splay tree for the same map.
there is a discussion about their splay trees; most of that discussion
applies here. Matt dillon suggested hash tables with array buckets:
A hash table on page addresses, at least, seems like it'd be pretty awful;
a single map entry that was a few pages long would have entries in
multiple buckets. A hash table that dealt in >1page chunks (say 16K) would
only work well on chunk-aligned map entry sections... perhaps I'm not
seeing how this table would be built?
My instinct (without examining either the current RB trees or the map
layouts of usual programs!) would be that a radix tree or a range radix
tree would be suitable; looking at the alpine session writing this email:
[0x08048000 - 0x084e1000)
[0x283d0000 - 0x28b71000)
*(more or less; there're actually a lot of entries in here
and a few page-or-so holes)
[0xbf9c9000 - 0xbfc00000)
*(there's a hole in here too)
are the valid address ranges. I think a wide path-compressed tree would be
very nice; I imagine this would be a very common layout...
- -- vs
is the commit where Dfly switched to an RB tree; it is more or less the
same site where one would patch today.
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.10 (GNU/Linux)
-----END PGP SIGNATURE-----