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

[Carlo Nonato <carlo.nonato@xxxxxxxxxxxxxxx>]

Hi Jan,

On Tue, Jan 9, 2024 at 11:28 AM Jan Beulich <jbeulich@xxxxxxxx> wrote:
>
> 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?

They will be used in later patches (#13).

> > @@ -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?

Nope. I'll drop it.

> > +                       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].

16 or 32 colors are pretty typical. In the past we set an upper bound at
128 colors.

Thanks.

> Jan