From owner-freebsd-hackers@FreeBSD.ORG Thu Dec 16 01:38:13 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 DF60E1065670 for ; Thu, 16 Dec 2010 01:38:13 +0000 (UTC) (envelope-from extrudedaluminiu@gmail.com) Received: from mail-gx0-f172.google.com (mail-gx0-f172.google.com [209.85.161.172]) by mx1.freebsd.org (Postfix) with ESMTP id 9B4C38FC12 for ; Thu, 16 Dec 2010 01:38:13 +0000 (UTC) Received: by gxk28 with SMTP id 28so2082092gxk.17 for ; Wed, 15 Dec 2010 17:38:12 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:received:mime-version:sender:reply-to:received :from:date:x-google-sender-auth:message-id:subject:to:content-type; bh=V8sNR9fIPdgn60NcaW9Oxssh/+FHaBVqUpmy7okMo+U=; b=CgSN6i8gLVGd1XcDWMUJ/8XdasrDNfOmGI7+lBqjq6dzmYkRQqrgwY2lvy5IeG8Zxx E3w7ujVdEqMm0zEgmfb7nvn6A9GQ6hLNXg+eFzZFoo85HQ11/BIMocvhQlQyCPIcoZ/G p2DJvMlPqLC7yVhOGaDh5ffUwqsh+PLaEqfHg= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=mime-version:sender:reply-to:from:date:x-google-sender-auth :message-id:subject:to:content-type; b=RuAjJxPlBH1brvnzAgOIZef3BuBctBFrkc52EHLst2+xp8RNppKEcNfXKPJn24sxp6 5rJxLXgugXUHd3KCNQ70sEXBXl8hf5Kx2QW1zlDXwjwh6NSyl6/aMWUKpAe6gvCNgg4A +/Eu0TbO2hDUV5bpUxU347SH9yOyGA+ZHnblM= Received: by 10.236.109.12 with SMTP id r12mr10211333yhg.32.1292463492803; Wed, 15 Dec 2010 17:38:12 -0800 (PST) MIME-Version: 1.0 Sender: extrudedaluminiu@gmail.com Received: by 10.236.110.172 with HTTP; Wed, 15 Dec 2010 17:37:52 -0800 (PST) From: Venkatesh Srinivas Date: Wed, 15 Dec 2010 20:37:52 -0500 X-Google-Sender-Auth: xzv3mVOlykhvRLM_UNk0mz3dy20 Message-ID: To: freebsd-hackers@freebsd.org Content-Type: text/plain; charset=UTF-8 X-Mailman-Approved-At: Thu, 16 Dec 2010 04:41:50 +0000 Subject: vm_map_findspace space search? X-BeenThere: freebsd-hackers@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list Reply-To: me@endeavour.zapto.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 01:38:14 -0000 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... Seem okay? Thoughts? Thanks! -- vs