From owner-freebsd-hackers@FreeBSD.ORG Sun Oct 26 15:09:40 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 4F98416A4B3; Sun, 26 Oct 2003 15:09:40 -0800 (PST) Received: from cs.rice.edu (cs.rice.edu [128.42.1.30]) by mx1.FreeBSD.org (Postfix) with ESMTP id 616CB43FBD; Sun, 26 Oct 2003 15:09:39 -0800 (PST) (envelope-from alc@cs.rice.edu) Received: from localhost (localhost [127.0.0.1]) by cs.rice.edu (Postfix) with ESMTP id 141144AA01; Sun, 26 Oct 2003 17:09:39 -0600 (CST) Received: from cs.rice.edu ([127.0.0.1]) by localhost (cs.rice.edu [127.0.0.1]) (amavisd-new, port 10024) with LMTP id 14580-01-6; Sun, 26 Oct 2003 17:09:37 -0600 (CST) Received: by cs.rice.edu (Postfix, from userid 19572) id 957904A9C3; Sun, 26 Oct 2003 17:09:37 -0600 (CST) Date: Sun, 26 Oct 2003 17:09:37 -0600 From: Alan Cox To: Q , hackers@freebsd.org Message-ID: <20031026230937.GF20658@cs.rice.edu> References: <1066793641.22245.12.camel@boxster.onthenet.com.au> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <1066793641.22245.12.camel@boxster.onthenet.com.au> User-Agent: Mutt/1.3.28i X-Virus-Scanned: by amavis-20030616-p5 at rice.edu cc: alc@freebsd.org cc: dillon@apollo.backplane.com Subject: Re: [Fwd: 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 23:09:40 -0000 On Wed, Oct 22, 2003 at 01:34:01PM +1000, Q wrote: > It has been suggested that I should direct this question to the VM > system guru's. Your comments on this would be appreciated. > An address space is represented by a data structure that we call a vm_map. A vm_map is, in the abstact, an ordered collection of in-use address ranges. FreeBSD 4.x implements the vm_map as a doubly-linked list of address ranges with a hint pointing to the last accessed entry. Thus, if the hint fails, the expected time to lookup an in-use address is O(n). FreeBSD 5.x overlays a balanced binary search tree over this structure. This accelerates the lookup to an (amortized) O(log n). In fact, for the kind of balanced binary search tree that we use, the last accessed entry is at the root of the tree. Thus, any locality in the pattern of lookups will produce even better results. Linux and OpenBSD are similar to FreeBSD 5.x. The differences lie in the details, like the kind of balanced binary tree that is used. That said, having a balanced binary tree to represent the address space does NOT inherently make finding unallocated space any faster. Instead, OpenBSD augments an address space entry with extra information to speed up this process: struct vm_map_entry { ... vaddr_t ownspace; /* free space after */ vaddr_t space; /* space in subtree */ ... The same could be done in FreeBSD, and you don't need a red-black tree in order to do it. If someone, especially a junior kernel hacker with a commit bit, is serious about trying this, I'll gladly mentor them. Recognize, however, that this approach may produce great results for a microbenchmark, but pessimize other more interesting workloads, like say, "buildworld", making it a poor choice. Nonetheless, I think we should strive to get better results in this area. Regards, Alan > > -----Forwarded Message----- > From: Q > To: freebsd-hackers@freebsd.org > Subject: Some mmap observations compared to Linux 2.6/OpenBSD > Date: Wed, 22 Oct 2003 12:22:35 +1000 > > As an effort to get more acquainted with the FreeBSD kernel, I have been > looking through how mmap works. I don't yet understand how it all fits > together, or of the exact implications things may have in the wild, but > I have noticed under some synthetic conditions, ie. mmaping small > non-contiguous pages of a file, mmap allocation scales much more poorly > on FreeBSD than on OpenBSD and Linux 2.6. > > After investigating this further I have observed that vm_map_findspace() > traverses a linked list to find the next region (O(n) cost), whereas > OpenBSD and Linux 2.6 both use Red-Black trees for the same purpose > (O(log n) cost). Profiling the FreeBSD kernel appears to confirm this. > > Can someone comment on whether this is something that has been done > intentionally, or avoided in favour of some other yet to be implemented > solution? Or is it still on someones todo list. > > -- > Seeya...Q > > -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- > > _____ / Quinton Dolan - q@OntheNet.com.au > __ __/ / / __/ / / > / __ / _/ / / Gold Coast, QLD, Australia > __/ __/ __/ ____/ / - / Ph: +61 419 729 806 > _______ / > _\ >