cvs commit: src/sys/vm vm_phys.c vm_phys.h

[Alan Cox]

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