'Change the vm_map lookup algorithm'

[Venkatesh Srinivas]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
Hi,

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 
active!)

(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. [1]
FreeBSD uses a splay tree for the same map.
- ----------

On FBSD-current 
(http://lists.freebsd.org/pipermail/freebsd-current/2010-September/020250.html), 
there is a discussion about their splay trees; most of that discussion 
applies here. Matt dillon suggested hash tables with array buckets:
http://lists.freebsd.org/pipermail/freebsd-current/2010-October/020280.html

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...

Thanks,
- -- vs
[1]: 
http://gitweb.dragonflybsd.org/dragonfly.git/commit/686dbf64f84094293330ee527217876838e7b04a
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)
iEYEARECAAYFAkymI+4ACgkQ+zApffxCWtB+TgCbBzXK2O9jaZwFEMfwszm2Nran
wvcAoNiITIhVPtX8xdYc/Poy8QJJUuTR
=EJt9
-----END PGP SIGNATURE-----