From owner-freebsd-hackers@FreeBSD.ORG Sat Oct 25 16:04:26 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 6F4D816A4B3 for ; Sat, 25 Oct 2003 16:04:26 -0700 (PDT) Received: from mail.broadpark.no (mail.broadpark.no [217.13.4.2]) by mx1.FreeBSD.org (Postfix) with ESMTP id 28E6643FCB for ; Sat, 25 Oct 2003 16:04:25 -0700 (PDT) (envelope-from des@des.no) Received: from smtp.des.no (37.80-203-228.nextgentel.com [80.203.228.37]) by mail.broadpark.no (Postfix) with ESMTP id E3A61795D4; Sun, 26 Oct 2003 01:04:23 +0200 (MEST) Received: by smtp.des.no (Pony Express, from userid 666) id 55D089C043; Sun, 26 Oct 2003 01:04:23 +0200 (CEST) Received: from dwp.des.no (dwp.des.no [10.0.0.4]) by smtp.des.no (Pony Express) with ESMTP id 18C0B9BFF3; Sun, 26 Oct 2003 01:04:19 +0200 (CEST) Received: by dwp.des.no (Postfix, from userid 2602) id D2BAFB823; Sun, 26 Oct 2003 01:04:18 +0200 (CEST) To: Q 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> From: des@des.no (Dag-Erling =?iso-8859-1?q?Sm=F8rgrav?=) Date: Sun, 26 Oct 2003 01:04:18 +0200 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 +1000") Message-ID: User-Agent: Gnus/5.090024 (Oort Gnus v0.24) Emacs/21.3 (berkeley-unix) MIME-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: quoted-printable X-Spam-Checker-Version: SpamAssassin 2.60 (1.212-2003-09-23-exp) on dsa.des.no X-Spam-Level: X-Spam-Status: No, hits=0.0 required=5.0 tests=none autolearn=no version=2.60 cc: freebsd-hackers@freebsd.org 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: Sat, 25 Oct 2003 23:04:26 -0000 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. DES --=20 Dag-Erling Sm=F8rgrav - des@des.no