vm_map_findspace space search?

[Venkatesh Srinivas]

Hi,

In svn r133636, there was a commit to convert the linear search in
vm_map_findspace() to use the vm_map splay tree. Just curious, were
there any discussions about that particular change? Any measurements
other than the ones noted in the commit log? Any notes on why that
design was used rather than any other?

I've seen the 'Some mmap observations...' thread from about a year
earlier and was wondering about some of the possible designs discussed
there. In particular the Bonwick/Adams vmem allocator was brought up;
I think that something inspired by it (and strangely close to the
QuickFit malloc) would be appropriate:

Here's how I see it working:
* Add a series of power-of-two or logarithmic sized freelists to the
 vm_map structure; they would point to vm_map_entries immediately to the
 left of free space holes of a given size.
* finding free space would just pop an entry off of the free space list
 and split in the usual way; deletion could coalesce in constant time.
* Unlike the vmem allocator, we would not need to allocate external
 boundary tags; the vm_map_entries themselves would be the tags.

At least from looking at the pattern of vm_map_findspace()s on DFly,
the most common requests were for 1 page, 4 page, and 16 page-sized
holes (iirc these combined for 75% of requests there; I imagine the
pattern in FreeBSD would be very similar). The fragmentation concerns
from this would be pretty minor with that pattern...

Seem okay? Thoughts?

Thanks!
-- vs