Re: [PATCH v5 09/13] xen: add cache coloring allocator for domains

[Jan Beulich <jbeulich@xxxxxxxx>]

On 02.01.2024 10:51, Carlo Nonato wrote:
> This commit adds a new memory page allocator that implements the cache
> coloring mechanism. The allocation algorithm enforces equal frequency
> distribution of cache partitions, following the coloring configuration of a
> domain. This allows an even utilization of cache sets for every domain.
> 
> Pages are stored in a color-indexed array of lists. Those lists are filled
> by a simple init function which computes the color of each page.
> When a domain requests a page, the allocator extract the page from the list
> with the maximum number of free pages between those that the domain can
> access, given its coloring configuration.
> 
> The allocator can only handle requests of order-0 pages. This allows for
> easier implementation and since cache coloring targets only embedded systems,
> it's assumed not to be a major problem.

I'm curious about the specific properties of embedded systems that makes
the performance implications of deeper page walks less of an issue for
them.

Nothing is said about address-constrained allocations. Are such entirely
of no interest to domains on Arm, not even to Dom0 (e.g. for filling
Linux'es swiotlb)? Certainly alloc_color_heap_page() should at least
fail when it can't satisfy the passed in memflags.

> ---
> v5:
> - Carlo Nonato as the new author
> - the colored allocator balances color usage for each domain and it searches
>   linearly only in the number of colors (FIXME removed)

While this addresses earlier concerns, meanwhile NUMA work has also
been progressing. What's the plan of interaction of coloring with it?

> --- a/xen/arch/Kconfig
> +++ b/xen/arch/Kconfig
> @@ -47,3 +47,15 @@ config NR_LLC_COLORS
>         bound. The runtime value is autocomputed or manually set via cmdline.
>         The default value corresponds to an 8 MiB 16-ways LLC, which should be
>         more than what needed in the general case.
> +
> +config BUDDY_ALLOCATOR_SIZE
> +     int "Buddy allocator reserved memory size (MiB)"
> +     default "64"
> +     depends on LLC_COLORING
> +     help
> +       Amount of memory reserved for the buddy allocator to work alongside
> +       the colored one. The colored allocator is meant as an alternative to
> +       the buddy allocator because its allocation policy is by definition
> +       incompatible with the generic one. Since the Xen heap is not colored
> +       yet, we need to support the coexistence of the two allocators and some
> +       memory must be left for the buddy one.

Imo help text should be about the specific option, not general
documentation. How about

          Amount of memory reserved for the buddy allocator, to serve Xen's
          heap, to work alongside the colored one.

or some such?

> --- a/xen/arch/arm/llc-coloring.c
> +++ b/xen/arch/arm/llc-coloring.c
> @@ -30,6 +30,9 @@ static unsigned int __ro_after_init nr_colors = 
> CONFIG_NR_LLC_COLORS;
>  static unsigned int __ro_after_init dom0_colors[CONFIG_NR_LLC_COLORS];
>  static unsigned int __ro_after_init dom0_num_colors;
>  
> +#define mfn_color_mask              (nr_colors - 1)

This is used solely ...

> +#define mfn_to_color(mfn)           (mfn_x(mfn) & mfn_color_mask)

... here, and this one in turn is used solely ...

> @@ -312,6 +315,16 @@ int domain_set_llc_colors_from_str(struct domain *d, 
> const char *str)
>      return domain_check_colors(d);
>  }
>  
> +unsigned int page_to_llc_color(const struct page_info *pg)
> +{
> +    return mfn_to_color(page_to_mfn(pg));
> +}

... here. What's the point in having those (private) macros?

> @@ -1946,6 +1951,162 @@ static unsigned long avail_heap_pages(
>      return free_pages;
>  }
>  
> +/*************************
> + * COLORED SIDE-ALLOCATOR
> + *
> + * Pages are grouped by LLC color in lists which are globally referred to as 
> the
> + * color heap. Lists are populated in end_boot_allocator().
> + * After initialization there will be N lists where N is the number of
> + * available colors on the platform.
> + */
> +static struct page_list_head *__ro_after_init _color_heap;
> +static unsigned long *__ro_after_init free_colored_pages;

It's "just" two pointers, but still - what use are they when ...

> +/* Memory required for buddy allocator to work with colored one */
> +#ifdef CONFIG_LLC_COLORING

... this isn't defined?

> +static unsigned long __initdata buddy_alloc_size =
> +    MB(CONFIG_BUDDY_ALLOCATOR_SIZE);
> +size_param("buddy-alloc-size", buddy_alloc_size);
> +
> +#define domain_num_llc_colors(d) ((d)->num_llc_colors)
> +#define domain_llc_color(d, i)   ((d)->llc_colors[(i)])

Nit: No need to parenthesize i when used like this.

> +#else
> +static unsigned long __initdata buddy_alloc_size;
> +
> +#define domain_num_llc_colors(d) 0
> +#define domain_llc_color(d, i)   0
> +#define page_to_llc_color(p)     0
> +#define get_nr_llc_colors()      0
> +#endif
> +
> +#define color_heap(color) (&_color_heap[color])
> +
> +void free_color_heap_page(struct page_info *pg, bool need_scrub)

Likely applicable further down as well - this is dead code when
!CONFIG_LLC_COLORING. Besides me, Misra also won't like this. The
function also looks to want to be static, at which point DCE would
apparently take care of removing it (and others, and then hopefully
also the two static variables commented on above).

> +struct page_info *alloc_color_heap_page(unsigned int memflags, struct domain 
> *d)

I don't think d is written through in the function, so it wants to
be pointer-to-const.

> +void __init init_color_heap_pages(struct page_info *pg, unsigned long 
> nr_pages)
> +{
> +    unsigned int i;
> +    bool need_scrub = (system_state < SYS_STATE_active &&

Can this part of the condition be false, seeing we're in an __init
function?

> +                       opt_bootscrub == BOOTSCRUB_IDLE);
> +
> +    if ( buddy_alloc_size )
> +    {
> +        unsigned long buddy_pages = min(PFN_DOWN(buddy_alloc_size), 
> nr_pages);
> +
> +        init_heap_pages(pg, buddy_pages);
> +        nr_pages -= buddy_pages;
> +        buddy_alloc_size -= buddy_pages << PAGE_SHIFT;
> +        pg += buddy_pages;
> +    }

So whatever is passed into this function first is going to fill the
Xen heap, without regard to address. I expect you're sure this won't
cause issues on Arm. On x86 certain constraints exist which would
require lower address ranges to be preferred.

> +void dump_color_heap(void)
> +{
> +    unsigned int color;
> +
> +    printk("Dumping color heap info\n");
> +    for ( color = 0; color < get_nr_llc_colors(); color++ )
> +        if ( free_colored_pages[color] > 0 )
> +            printk("Color heap[%u]: %lu pages\n",
> +                   color, free_colored_pages[color]);
> +}

What's a typical range of number of colors on a system? I expect more
than 9, but I'm not sure about a reasonable upper bound. For the
output to be easy to consume, [%u] may want to become at least [%2u].

Jan