Date: Sun, 26 Oct 2003 01:04:18 +0200 From: des@des.no (Dag-Erling =?iso-8859-1?q?Sm=F8rgrav?=) To: Q <q_dolan@yahoo.com.au> Cc: Kris Kennaway <kris@obsecurity.org> Subject: Re: Some mmap observations compared to Linux 2.6/OpenBSD Message-ID: <xzpk76sc425.fsf@dwp.des.no> In-Reply-To: <1066820436.25609.93.camel@boxster.onthenet.com.au> (q_dolan@yahoo.com.au's message of "Wed, 22 Oct 2003 21:00:36 %2B1000") 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>
next in thread | previous in thread | raw e-mail | index | archive | help
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. DES --=20 Dag-Erling Sm=F8rgrav - des@des.no
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?xzpk76sc425.fsf>