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

[Carlo Nonato <carlo.nonato@xxxxxxxxxxxxxxx>]

Hi Jan,

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.

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

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

Obviously fragmentation is inherently higher with coloring because it actually
needs to partition memory, so the third prerequisite actually limits contiguity
a lot.

> Jan