From owner-cvs-src@FreeBSD.ORG Sun Jun 10 20:02:02 2007 Return-Path: X-Original-To: cvs-src@FreeBSD.org Delivered-To: cvs-src@FreeBSD.org Received: from mx1.freebsd.org (mx1.freebsd.org [69.147.83.52]) by hub.freebsd.org (Postfix) with ESMTP id AB70616A468; Sun, 10 Jun 2007 20:02:02 +0000 (UTC) (envelope-from alc@cs.rice.edu) Received: from mail.cs.rice.edu (mail.cs.rice.edu [128.42.1.31]) by mx1.freebsd.org (Postfix) with ESMTP id 6728413C4C4; Sun, 10 Jun 2007 20:02:02 +0000 (UTC) (envelope-from alc@cs.rice.edu) Received: from mail.cs.rice.edu (localhost.localdomain [127.0.0.1]) by mail.cs.rice.edu (Postfix) with ESMTP id 74E072C2A6C; Sun, 10 Jun 2007 14:30:27 -0500 (CDT) X-Virus-Scanned: by amavis-2.4.0 at mail.cs.rice.edu Received: from mail.cs.rice.edu ([127.0.0.1]) by mail.cs.rice.edu (mail.cs.rice.edu [127.0.0.1]) (amavisd-new, port 10024) with LMTP id ByOwd5F+9LSr; Sun, 10 Jun 2007 14:30:19 -0500 (CDT) Received: from [216.63.78.18] (adsl-216-63-78-18.dsl.hstntx.swbell.net [216.63.78.18]) (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) by mail.cs.rice.edu (Postfix) with ESMTP id 922962C2A8F; Sun, 10 Jun 2007 14:30:19 -0500 (CDT) Message-ID: <466C514B.5060206@cs.rice.edu> Date: Sun, 10 Jun 2007 14:30:19 -0500 From: Alan Cox User-Agent: Mozilla/5.0 (X11; U; FreeBSD i386; en-US; rv:1.7.13) Gecko/20070328 X-Accept-Language: en-us, en MIME-Version: 1.0 To: Jeff Roberson References: <200706100049.l5A0nH16004198@repoman.freebsd.org> <20070609213443.B60816@10.0.0.1> In-Reply-To: <20070609213443.B60816@10.0.0.1> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Cc: Alan Cox , cvs-src@FreeBSD.org, src-committers@FreeBSD.org, cvs-all@FreeBSD.org Subject: Re: cvs commit: src/sys/vm vm_phys.c vm_phys.h X-BeenThere: cvs-src@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: CVS commit messages for the src tree List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sun, 10 Jun 2007 20:02:02 -0000 Jeff Roberson wrote: > On Sun, 10 Jun 2007, Alan Cox wrote: > >> alc 2007-06-10 00:49:16 UTC >> >> FreeBSD src repository >> >> Added files: >> sys/vm vm_phys.c vm_phys.h >> Log: >> Add a new physical memory allocator. However, do not yet connect it >> to the build. > > > Can you tell us about the time complexity of allocating multiple > physically contiguous pages? A parameter in "architecture"/include/vmparam.h determines the number of buddy queues per region of physical memory and per pool within a region. A region might be memory that supports ISA DMA or in the not-so-distant future a particular node's memory in a NUMA architecture. A pool within a region is what allows for the direct-map optimization. The smallest buddy queue always stores individual pages. For example, on amd64, there are 13 buddy queues, and thus the largest queue stores contiguous sets of pages that are 16MB in size. (A comment in vmparam.h explains why it is 16MB.) The time complexity depends on the size of the allocation request. If it is less than or equal to what the largest queue stores, then the time complexity is strictly speaking O(constant). That said, in the worst case on amd64, you might examine a number of queues equal to 2*2*13 to find a free chunk of memory and split that chunk 12 times to complete the allocation. In contrast, the old page coloring allocator might examine 16 queues on amd64. If, however, the allocation size is greater than what the largest queues stores, then the time complexity is O("the length of the 16MB queue" squared). In practice, this is much, much better than the old contigmalloc(9) since the length of the 16MB queue is orders of magnitude smaller than the vm_page_array. Alan