Date: Mon, 27 Oct 2003 09:08:59 -0800 From: David Schultz <das@FreeBSD.ORG> To: Lowell Gilbert <lowell@world.std.com> Cc: freebsd-hackers@FreeBSD.ORG Subject: Re: Some mmap observations compared to Linux 2.6/OpenBSD Message-ID: <20031027170859.GA30164@VARK.homeunix.com> In-Reply-To: <44he1wi2yy.fsf@be-well.ilk.org> References: <1066789354.21430.39.camel@boxster.onthenet.com.au> <20031022082953.GA69506@rot13.obsecurity.org> <1066816287.25609.34.camel@boxster.onthenet.com.au> <20031022095754.GA70026@rot13.obsecurity.org> <1066820436.25609.93.camel@boxster.onthenet.com.au> <xzpk76sc425.fsf@dwp.des.no> <20031026052854.GA20701@VARK.homeunix.com> <44he1wi2yy.fsf@be-well.ilk.org>
next in thread | previous in thread | raw e-mail | index | archive | help
On Sun, Oct 26, 2003, Lowell Gilbert wrote: > David Schultz <das@FreeBSD.ORG> writes: > > > On Sun, Oct 26, 2003, Dag-Erling Smrgrav wrote: > > > Q <q_dolan@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.] Erm, did you read the paper I referred to? If you have, say, 32 power-of-two buckets, you can use a bitmask representing which buckets are non-empty to locate spcae in constant time. The caveat (also in the paper) is that the price of the constant time operation is that your allocation may be up to twice as large as necessary. A tree lacks this disadvantage, but also carries with it some additional overhead.
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20031027170859.GA30164>