Date: Sun, 10 Jun 2007 14:30:19 -0500 From: Alan Cox <alc@cs.rice.edu> To: Jeff Roberson <jroberson@chesapeake.net> Cc: Alan Cox <alc@FreeBSD.org>, 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 Message-ID: <466C514B.5060206@cs.rice.edu> In-Reply-To: <20070609213443.B60816@10.0.0.1> References: <200706100049.l5A0nH16004198@repoman.freebsd.org> <20070609213443.B60816@10.0.0.1>
next in thread | previous in thread | raw e-mail | index | archive | help
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
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?466C514B.5060206>