Some mmap observations compared to Linux 2.6/OpenBSD

[Lowell Gilbert]

David Schultz <das at FreeBSD.ORG> writes:

> On Sun, Oct 26, 2003, Dag-Erling Smrgrav wrote:
> > Q <q_dolan at yahoo.com.au> writes:
> > > Yes, it would appear this is a legacy thing that existed in the original
> > > 1994 import of the BSD 4.4 Lite source. Both FreeBSD and NetBSD still
> > > use this technique, but OpenBSD changed to using Red-Black trees back in
> > > Feb 2002.
> > > [...]
> > > I am wondering if there is a compelling reason why the technique used by
> > > OpenBSD could not be adapted to FreeBSD's VM system.
> > 
> > Adapting OpenBSD's red-balck patches would require quite a bit of work
> > as FreeBSD and OpenBSD have diverged quite a bit in this area.  Though
> > it is a good idea to change the list into a tree, I think you'd get
> > more mileage by addressing the fundamental problem, which is the lack
> > of a free list.  The current code (in both FreeBSD and OpenBSD)
> > searches a list or tree of allocated extents, sorted by location,
> > looking for a pair that have sufficient space between them for the
> > extent you want to create.  We should instead keep track of free
> > extents in a structure that makes it easy to locate one of the correct
> > size.  We probably need a dual structure, though, because we need to
> > keep the free extents sorted both by size (to quickly find what we
> > need) and by location (to facilitate aggregation of adjacent extents,
> > without which we'd suffer horribly from address space fragmentation).
> > 
> > I have no idea how much this means for real-life workloads though.
> 
> Your idea of using a size-hashed freelist as well as a
> location-sorted list is appealing in its simplicity.  Though it
> can cause a bit of fragmentation, it gives you constant time
> lookup.  Bonwick's vmem allocator ([1], section 4.4.2 and
> following), apparently works quite well using this principle.

A hash probably isn't the right data structure for either dimension
(DES didn't say it was, I notice).  Finding the next-largest available
entry is a useful operation, here, so a list would be better than a
hash.  [Or a tree; the point is that exact-match isn't the only kind
of search you need.]

> But regardless of the approach, someone has yet to demonstrate
> that this is actually a performance problem in the real world. ;-)

Yes.  Wouldn't be easy to test even if you wanted to, either...