From owner-freebsd-hackers@FreeBSD.ORG Thu Dec 16 18:43:45 2010 Return-Path: Delivered-To: freebsd-hackers@freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:4f8:fff6::34]) by hub.freebsd.org (Postfix) with ESMTP id 1F233106564A for ; Thu, 16 Dec 2010 18:43:45 +0000 (UTC) (envelope-from alan.l.cox@gmail.com) Received: from mail-fx0-f49.google.com (mail-fx0-f49.google.com [209.85.161.49]) by mx1.freebsd.org (Postfix) with ESMTP id A508C8FC0A for ; Thu, 16 Dec 2010 18:43:44 +0000 (UTC) Received: by fxm19 with SMTP id 19so3576845fxm.36 for ; Thu, 16 Dec 2010 10:43:43 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:mime-version:received:received:reply-to :in-reply-to:references:date:message-id:subject:from:to:cc :content-type; bh=ZTry7633MBlZ01rA85atSXFUWg2LhGhJgfaKGUWpb4k=; b=WvqOUObodde9CfftLDhxapO0hLjixrmzzKMnnaeo+VbNIRht13mFLiRtt8XuQzJLZ+ Uxhzvn2vCijsPMG+gAOPtuti2u53D58nQJuG5MWGg3e//gTpCJAdbxcjB4aXn+U7xTrg o1ZUzoH4Y1M8vHrZujkdwm4ydnVh/cjPEddzw= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=mime-version:reply-to:in-reply-to:references:date:message-id :subject:from:to:cc:content-type; b=L5Bg+VXPj4U+3APj+Q7306M4ARQukhvvDLxEQO7sWz/i6j9ljTBYCT34A7ufRtQWcX P9iijJ+TIqvShHdML1/UsQLIq2/8AEIuu1sOo7udN6xHqo4NYBAsZM0bC84z1LRk8dTa X3gttK0tZPkM8+6S4+YZCSf8puJU2PHkTQ3BU= MIME-Version: 1.0 Received: by 10.223.96.194 with SMTP id i2mr142610fan.25.1292525023550; Thu, 16 Dec 2010 10:43:43 -0800 (PST) Received: by 10.223.116.205 with HTTP; Thu, 16 Dec 2010 10:43:43 -0800 (PST) In-Reply-To: References: Date: Thu, 16 Dec 2010 12:43:43 -0600 Message-ID: From: Alan Cox To: me@endeavour.zapto.org Content-Type: text/plain; charset=ISO-8859-1 X-Content-Filtered-By: Mailman/MimeDel 2.1.5 Cc: freebsd-hackers@freebsd.org Subject: Re: vm_map_findspace space search? X-BeenThere: freebsd-hackers@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list Reply-To: alc@freebsd.org List-Id: Technical Discussions relating to FreeBSD List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 16 Dec 2010 18:43:45 -0000 On Wed, Dec 15, 2010 at 7:37 PM, Venkatesh Srinivas < vsrinivas@dragonflybsd.org> wrote: > Hi, > > In svn r133636, there was a commit to convert the linear search in > vm_map_findspace() to use the vm_map splay tree. Just curious, were > there any discussions about that particular change? Any measurements > other than the ones noted in the commit log? Any notes on why that > design was used rather than any other? > > I've seen the 'Some mmap observations...' thread from about a year > earlier and was wondering about some of the possible designs discussed > there. In particular the Bonwick/Adams vmem allocator was brought up; > I think that something inspired by it (and strangely close to the > QuickFit malloc) would be appropriate: > > Here's how I see it working: > * Add a series of power-of-two or logarithmic sized freelists to the > vm_map structure; they would point to vm_map_entries immediately to the > left of free space holes of a given size. > * finding free space would just pop an entry off of the free space list > and split in the usual way; deletion could coalesce in constant time. > * Unlike the vmem allocator, we would not need to allocate external > boundary tags; the vm_map_entries themselves would be the tags. > > At least from looking at the pattern of vm_map_findspace()s on DFly, > the most common requests were for 1 page, 4 page, and 16 page-sized > holes (iirc these combined for 75% of requests there; I imagine the > pattern in FreeBSD would be very similar). The fragmentation concerns > from this would be pretty minor with that pattern... > > I'm afraid that the pattern is is not always so simple. Sometimes external fragmentation is, in fact, a problem. For example, search for "ZFS ARC kmem_map fragmentation". I recall there being at least one particularly detailed e-mail that quantified the fragmentation being caused by the ZFS ARC. There are also microbenchmarks that simulate an mmap() based web server, which will show a different pattern than you describe. If you're interested in working on something in this general area, I can suggest something. Alan