Re: [PATCH v4 07/11] xen: add cache coloring allocator for domains

[Jan Beulich <jbeulich@xxxxxxxx>]

On 26.01.2023 12:00, Carlo Nonato wrote:
> On Tue, Jan 24, 2023 at 5:50 PM Jan Beulich <jbeulich@xxxxxxxx> wrote:
>> On 23.01.2023 16:47, Carlo Nonato wrote:
>>> From: Luca Miccio <lucmiccio@xxxxxxxxx>
>>>
>>> This commit adds a new memory page allocator that implements the cache
>>> coloring mechanism. The allocation algorithm follows the given domain color
>>> configuration and maximizes contiguity in the page selection of multiple
>>> subsequent requests.
>>>
>>> Pages are stored in a color-indexed array of lists, each one sorted by
>>> machine address, that is referred to as "colored heap". Those lists are
>>> filled by a simple init function which computes the color of each page.
>>> When a domain requests a page, the allocator takes one from those lists
>>> whose colors equals the domain configuration. It chooses the page with the
>>> lowest machine address such that contiguous pages are sequentially
>>> allocated if this is made possible by a color assignment which includes
>>> adjacent colors.
>>
>> What use is this with ...
>>
>>> The allocator can handle only requests with order equal to 0 since the
>>> single color granularity is represented in memory by one page.
>>
>> ... this restriction? Plus aiui there's no guarantee of contiguous pages
>> coming back in any event (because things depend on what may have been
>> allocated / freed earlier on), so why even give the impression of there
>> being a way to obtain contiguous pages?
> 
> I really need us to be on the same "page" (no pun intended) here cause we
> discussed the subject multiple times and I'm probably missing important
> details.
> 
> First, is physical memory contiguity important? I'm assuming this is good
> because then some hardware optimization can occur when accessing memory.
> I'm taking it for granted because it's what the original author of the series
> thought, but I don't have an objective view of this.

I'd need to have a reference to a concrete description of such hardware
behavior to believe it. On x86 I certainly know of an "adjacent cacheline
prefetch" optimization in hardware, but that won't cross page boundaries
afair.

Contiguous memory can be advantageous for I/O (allowing bigger chunks in
individual requests or s/g list elements), and it is certainly a prereq
to using large page mappings (which earlier on you already said isn't of
interest in your use case).

> Then, let's state what contiguity means with coloring:
> *if* there are contiguous free pages and *if* subsequent requests are made
> and *if* the coloring configuration allows it, the allocator guarantees
> contiguity because it serves pages *in order*.

I don't think it can, simply because ...

> From the fragmentation perspective (first prerequisite), this is somewhat
> similar to the buddy case where only if contiguous pages are freed they can
> be allocated after. So order of operation is always important for
> fragmentation in dynamic allocation. The main difference is speed
> (I'm not comparing them on this aspect).
> 
> The second prerequisite requires that users of the allocator have exclusive
> access to it until the request is carried out. If interleaved requests happen,
> contiguity is practically impossible. How often does this happen? I view
> allocation as something that happens mainly at domain creation time, one
> domain at a time which results in a lot of subsequent requests, and then
> contiguity (if other prerequisites hold) isn't an impression.

... the "exclusive access" here is a fiction: Domain memory is populated
by the tool stack. Such tool stack allocations (even if properly serialized
in the control domain) will necessarily compete with anything done
internally in the hypervisor. Specifically the hypervisor may, at any time,
allocate a page (perhaps just for transient use), and then free that page
again, or free another one which was allocated before the tool stack
started populating domain memory.

Jan