Re: [PATCH DO NOT APPLY] docs: Document allocator properties and the rubric for using them

[George Dunlap <George.Dunlap@citrix.com>]

> On Feb 16, 2021, at 10:28 AM, George Dunlap <george.dunlap@citrix.com> wrote:
> 
> Document the properties of the various allocators and lay out a clear
> rubric for when to use each.
> 
> Signed-off-by: George Dunlap <george.dunlap@citrix.com>
> ---
> 
> This doc is my understanding of the properties of the current
> allocators (alloc_xenheap_pages, xmalloc, and vmalloc), and of Jan's
> proposed new wrapper, xvmalloc.
> 
> xmalloc, vmalloc, and xvmalloc were designed more or less to mirror
> similar functions in Linux (kmalloc, vmalloc, and kvmalloc
> respectively).
> 
> CC: Andrew Cooper <andrew.cooper3@citrix.com>
> CC: Jan Beulich <jbeulich@suse.com>
> CC: Roger Pau Monne <roger.pau@citrix.com>
> CC: Stefano Stabellini <sstabellini@kernel.org>
> CC: Julien Grall <julien@xen.org>
> ---
> .../memory-allocation-functions.rst           | 118 ++++++++++++++++++
> 1 file changed, 118 insertions(+)
> create mode 100644 docs/hypervisor-guide/memory-allocation-functions.rst
> 
> diff --git a/docs/hypervisor-guide/memory-allocation-functions.rst b/docs/hypervisor-guide/memory-allocation-functions.rst
> new file mode 100644
> index 0000000000..15aa2a1a65
> --- /dev/null
> +++ b/docs/hypervisor-guide/memory-allocation-functions.rst
> @@ -0,0 +1,118 @@
> +.. SPDX-License-Identifier: CC-BY-4.0
> +
> +Xenheap memory allocation functions
> +===================================
> +
> +In general Xen contains two pools (or "heaps") of memory: the *xen
> +heap* and the *dom heap*.  Please see the comment at the top of
> +``xen/common/page_alloc.c`` for the canonical explanation.
> +
> +This document describes the various functions available to allocate
> +memory from the xen heap: their properties and rules for when they should be
> +used.
> +
> +
> +TLDR guidelines
> +---------------
> +
> +* By default, ``xvmalloc`` (or its helper cognates) should be used
> +  unless you know you have specific properties that need to be met.
> +
> +* If you need memory which needs to be physically contiguous, and may
> +  be larger than ``PAGE_SIZE``...
> +  
> +  - ...and is order 2, use ``alloc_xenheap_pages``.
> +    
> +  - ...and is not order 2, use ``xmalloc`` (or its helper cognates)..
> +
> +* If you don't need memory to be physically contiguous, and know the
> +  allocation will always be larger than ``PAGE_SIZE``, you may use
> +  ``vmalloc`` (or one of its helper cognates).
> +
> +* If you know that allocation will always be less than ``PAGE_SIZE``,
> +  you may use ``xmalloc``.
> +
> +Properties of various allocation functions
> +------------------------------------------
> +
> +Ultimately, the underlying allocator for all of these functions is
> +``alloc_xenheap_pages``.  They differ on several different properties:
> +
> +1. What underlying allocation sizes are.  This in turn has an effect
> +   on:
> +
> +   - How much memory is wasted when requested size doesn't match
> +
> +   - How such allocations are affected by memory fragmentation
> +
> +   - How such allocations affect memory fragmentation
> +
> +2. Whether the underlying pages are physically contiguous
> +
> +3. Whether allocation and deallocation require the cost of mapping and
> +   unmapping
> +
> +``alloc_xenheap_pages`` will allocate a physically contiguous set of
> +pages on orders of 2.  No mapping or unmapping is done.  However, if
> +this is used for sizes not close to ``PAGE_SIZE * (1 << n)``, a lot of
> +space will be wasted.  Such allocations may fail if the memory becomes
> +very fragmented; but such allocations do not tend to contribute to
> +that memory fragmentation much.
> +
> +As such, ``alloc_xenheap_pages`` should be used when you need a size
> +of exactly ``PAGE_SIZE * (1 << n)`` physically contiguous pages.
> +
> +``xmalloc`` is actually two separate allocators.  Allocations of <
> +``PAGE_SIZE`` are handled using ``xmem_pool_alloc()``, and allocations >=
> +``PAGE_SIZE`` are handled using ``xmalloc_whole_pages()``.
> +
> +``xmem_pool_alloc()`` is a pool allocator which allocates xenheap
> +pages on demand as needed.  This is ideal for small, quick
> +allocations: no pages are mapped or unmapped; sub-page allocations are
> +expected, and so a minimum of space is wasted; and because xenheap
> +pages are allocated one-by-one, 1) they are unlikely to fail unless
> +Xen is genuinely out of memory, and 2) it doesn't have a major effect
> +on fragmentation of memory.
> +
> +Allocations of > ``PAGE_SIZE`` are not possible with the pool
> +allocator, so for such sizes, ``xmalloc`` calls
> +``xmalloc_whole_pages()``, which in turn calls ``alloc_xenheap_pages``
> +with an order large enough to satisfy the request, and then frees all
> +the pages which aren't used.
> +
> +Like the other allocator, this incurs no mapping or unmapping
> +overhead.  Allocations will be physically contiguous (like
> +``alloc_xenheap_pages``), but not as much is wasted as a plain
> +``alloc_xenheap_pages`` allocation.  However, such an allocation may
> +fail if memory fragmented to the point that a contiguous allocation of
> +the appropriate size cannot be found; such allocations also tend to
> +fragment memory more.
> +
> +As such, ``xmalloc`` may be called in cases where you know the
> +allocation will be less than ``PAGE_SIZE``; or when you need a
> +physically contiguous allocation which may be more than
> +``PAGE_SIZE``.  
> +
> +``vmalloc`` will allocate pages one-by-one and map them into a virtual
> +memory area designated for the purpose, separated by a guard page.
> +Only full pages are allocated, so using it from less tham
> +``PAGE_SIZE`` allocations is wasteful.  The underlying memory will not
> +be physically contiguous.  As such, it is not adversely affected by
> +excessive system fragmentation, nor does it contribute to it.
> +However, allocating and freeing requires a map and unmap operation
> +respectively, both of which adversely affect system performance.
> +
> +Therefore, ``vmalloc`` should be used for page allocations over a page
> +size in length which don't need to be physically contiguous.
> +
> +``xvmalloc`` is like ``xmalloc``, except that for allocations >
> +``PAGE_SIZE``, it calls ``vmalloc`` instead.  Thus ``xvmalloc`` should
> +always be preferred unless:
> +
> +1. You need physically contiguous memory, and your size may end up
> +   greater than ``PAGE_SIZE``; in which case you should use
> +   ``xmalloc`` or ``alloc_xenheap_pages`` as appropriate
> +
> +2. You are positive that ``xvmalloc`` will choose one specific
> +   underlying implementation; in which case you should simply call
> +   that implementation directly.

Basically, the more I look at this whole thing — particularly the fact that xmalloc already has an `if ( size > PAGE_SIZE)` inside of it — the more I think this last point is just a waste of everyone’s time.

I’m inclined to go with Julien’s suggestion, that we use xmalloc when we need physically contiguous memory (with a comment), and xvmalloc everywhere else.  We can implement xvmalloc such that it’s no slower than xmalloc is currently (i.e., it directly calls `xmem_pool_alloc` when size < PAGE_SIZE, rather than calling xmalloc and having xmalloc do the comparison again).

 -George