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

[Jan Beulich <jbeulich@xxxxxxxx>]

On 13.10.2022 11:47, Carlo Nonato wrote:
> On Mon, Sep 19, 2022 at 8:26 AM Jan Beulich <jbeulich@xxxxxxxx> wrote:
>> On 16.09.2022 18:05, Carlo Nonato wrote:
>>> On Thu, Sep 15, 2022 at 3:13 PM Jan Beulich <jbeulich@xxxxxxxx> 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.

Ah yes, that's a good reason to keep the function out-of-line.

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

I could live with this as long as it's stated prominently enough, but ...

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

... this sounds even more promising, not the least because it also eliminates
yet another shortcoming we've talked about already. In fact I would expect
that log2(max_colors) doesn't need to be the limit either, as you'd cycle
back to the first color anyway once you've reached the last one.

Jan