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

'Change the vm_map lookup algorithm'

From: Venkatesh Srinivas <me@xxxxxxxxxxxxxxxxxxx>
Date: Fri, 1 Oct 2010 14:09:49 -0400 (EDT)

Hash: SHA1


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:

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

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

Version: GnuPG v1.4.10 (GNU/Linux)


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