From owner-freebsd-hackers@FreeBSD.ORG Sat Oct 25 22:29:30 2003 Return-Path: Delivered-To: freebsd-hackers@freebsd.org Received: from mx1.FreeBSD.org (mx1.freebsd.org [216.136.204.125]) by hub.freebsd.org (Postfix) with ESMTP id B662A16A4B3 for ; Sat, 25 Oct 2003 22:29:30 -0700 (PDT) Received: from VARK.homeunix.com (adsl-68-123-140-7.dsl.pltn13.pacbell.net [68.123.140.7]) by mx1.FreeBSD.org (Postfix) with ESMTP id A174143FBD for ; Sat, 25 Oct 2003 22:29:29 -0700 (PDT) (envelope-from das@FreeBSD.ORG) Received: from VARK.homeunix.com (localhost [127.0.0.1]) by VARK.homeunix.com (8.12.9/8.12.9) with ESMTP id h9Q5T0en020812; Sat, 25 Oct 2003 22:29:00 -0700 (PDT) (envelope-from das@FreeBSD.ORG) Received: (from das@localhost) by VARK.homeunix.com (8.12.9/8.12.9/Submit) id h9Q5SxOd020811; Sat, 25 Oct 2003 22:28:59 -0700 (PDT) (envelope-from das@FreeBSD.ORG) Date: Sat, 25 Oct 2003 22:28:54 -0700 From: David Schultz To: "Dag-Erling =?us-ascii:iso-8859-1?Q?Sm=F8rgrav?=" Message-ID: <20031026052854.GA20701@VARK.homeunix.com> Mail-Followup-To: "Dag-Erling =?us-ascii:iso-8859-1?Q?Sm=F8rgrav?=" , Q , freebsd-hackers@FreeBSD.ORG, Kris Kennaway 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> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: cc: freebsd-hackers@FreeBSD.ORG cc: Q cc: Kris Kennaway Subject: Re: Some mmap observations compared to Linux 2.6/OpenBSD X-BeenThere: freebsd-hackers@freebsd.org X-Mailman-Version: 2.1.1 Precedence: list List-Id: Technical Discussions relating to FreeBSD List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sun, 26 Oct 2003 05:29:30 -0000 On Sun, Oct 26, 2003, Dag-Erling Smrgrav wrote: > Q 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/