From owner-cvs-all@FreeBSD.ORG Sun Jun 10 22:09:48 2007 Return-Path: X-Original-To: cvs-all@FreeBSD.org Delivered-To: cvs-all@FreeBSD.org Received: from mx1.freebsd.org (mx1.freebsd.org [69.147.83.52]) by hub.freebsd.org (Postfix) with ESMTP id D205B16A400; Sun, 10 Jun 2007 22:09:48 +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 8C1E413C45E; Sun, 10 Jun 2007 22:09:48 +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 DA3F52C2AAE; Sun, 10 Jun 2007 17:09:47 -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 gEx8vjwgUOU7; Sun, 10 Jun 2007 17:09:40 -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 059FA2C2A92; Sun, 10 Jun 2007 17:09:39 -0500 (CDT) Message-ID: <466C76A3.8050308@cs.rice.edu> Date: Sun, 10 Jun 2007 17:09:39 -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> <466C514B.5060206@cs.rice.edu> In-Reply-To: <466C514B.5060206@cs.rice.edu> 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, Alan Cox , cvs-all@FreeBSD.org Subject: Re: cvs commit: src/sys/vm vm_phys.c vm_phys.h X-BeenThere: cvs-all@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: CVS commit messages for the entire tree List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sun, 10 Jun 2007 22:09:48 -0000 Alan Cox wrote: > 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. I should add that placing constraints, such as a high or low physical address, on an allocation request of less than or equal to 16MB changes the worst case time complexity to O("the length of all of the buddy queues containing chunks of size greater than or equal to the requested size"). Alan