Some mmap observations compared to Linux 2.6/OpenBSD
David Schultz
das at FreeBSD.ORG
Sat Oct 25 22:29:30 PDT 2003
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.
But regardless of the approach, someone has yet to demonstrate
that this is actually a performance problem in the real world. ;-)
[1] http://www.usenix.org/event/usenix01/full_papers/bonwick/
More information about the freebsd-hackers
mailing list