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

[Alan Cox]

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