Re: [PATCH 06/12] xen/common: add cache coloring allocator for domains

[Carlo Nonato <carlo.nonato@minervasys.tech>]

Hi Jan


On Mon, Sep 19, 2022 at 8:26 AM Jan Beulich <jbeulich@suse.com> wrote:
>
> On 16.09.2022 18:05, Carlo Nonato wrote:
> > On Thu, Sep 15, 2022 at 3:13 PM Jan Beulich <jbeulich@suse.com> wrote:
> >> On 26.08.2022 14:51, Carlo Nonato wrote:
> >>> --- a/xen/arch/arm/coloring.c
> >>> +++ b/xen/arch/arm/coloring.c
> >>> @@ -300,6 +300,16 @@ void prepare_color_domain_config(struct xen_arch_domainconfig *config,
> >>>      config->num_colors = (uint16_t)num;
> >>>  }
> >>>
> >>> +unsigned int page_to_color(struct page_info *pg)
> >>
> >> The parameter will want to be pointer-to-const and I wonder whether ...
> >>
> >>> +{
> >>> +    return addr_to_color(page_to_maddr(pg));
> >>> +}
> >>
> >> ... the function as a whole wouldn't be a good candidate for being an
> >> inline one (requiring addr_to_color() to be available in outside of
> >> this file, of course).
> >
> > You mean defining it as static inline in the coloring.h header?
>
> That would seem preferable for a simple function like this one.
>

I didn't want to expose that function since I would also have to expose
the addr_col_mask global variable.
Same goes for get_max_colors(): it exist only for the purpose to restrict
the max_colors variable visibility.

> >>> +    page_list_for_each( pos, head )
> >>> +    {
> >>> +        if ( page_to_maddr(pos) < page_to_maddr(pg) )
> >>> +        {
> >>> +            head = &pos->list;
> >>> +            break;
> >>> +        }
> >>> +    }
> >>
> >> Wait - a linear search for every single page insertion? How well
> >> is that going to perform on a multi-terabyte system?
> >
> > For our test cases (embedded systems) the linear search is good enough.
> > I agree with you that in the general case this is bad (even though the main
> > targets are indeed embedded systems).
> > Are there any already available data structures that we can exploit to get
> > better performances?
>
> I'm afraid there aren't any that I would see as a good fit here.
>

Regarding this I can see three options:
1) We leave it as it is and we warn the user in the docs that cache coloring
   is embedded system specific for the moment since it has, probably, bad
   performances with bigger systems.
2) We use some priority queue implementation to replace the actual lists.
   Red/black trees are available in Xen codebase, but I think I would have
   to change the page_info struct to use them.
   Maybe just a binary heap implemented as an array could be viable, but that
   would require me to implement somewhere the logic for insertion,
   extract-min and other operations.
3) I have a working prototype of a buddy allocator that also makes use of
   coloring information. It isn't an extension of the main one, but rather a
   simpler version. This means that nodes, zones, scrubbing, aren't
   supported, but this is true also for the already submitted colored
   allocator. With this, order > 0 pages can be served (up until
   log2(max_colors)) and insertion is no more linear, but constant instead.

>
> Jan

Thanks

- Carlo Nonato