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
_______________________________________________
[email protected] mailing list
http://lists.freebsd.org/mailman/listinfo/cvs-all
To unsubscribe, send any mail to "[EMAIL PROTECTED]"
