vm_map_findspace space search?

[Alan Cox]

On Wed, Dec 15, 2010 at 7:37 PM, Venkatesh Srinivas <
vsrinivas at dragonflybsd.org> wrote:

> 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...
>
>
I'm afraid that the pattern is is not always so simple.  Sometimes external
fragmentation is, in fact, a problem.  For example, search for "ZFS ARC
kmem_map fragmentation".  I recall there being at least one particularly
detailed e-mail that quantified the fragmentation being caused by the ZFS
ARC.  There are also microbenchmarks that simulate an mmap() based web
server, which will show a different pattern than you describe.

If you're interested in working on something in this general area, I can
suggest something.

Alan