Re: [PATCH v5 07/15] x86: introduce helper for recording degree of contiguity in page tables

[Roger Pau Monné <roger.pau@xxxxxxxxxx>]

On Wed, Jun 01, 2022 at 02:11:53PM +0200, Jan Beulich wrote:
> On 01.06.2022 13:29, Roger Pau Monné wrote:
> > On Fri, May 27, 2022 at 01:17:08PM +0200, Jan Beulich wrote:
> >> --- /dev/null
> >> +++ b/xen/arch/x86/include/asm/pt-contig-markers.h
> >> @@ -0,0 +1,110 @@
> >> +#ifndef __ASM_X86_PT_CONTIG_MARKERS_H
> >> +#define __ASM_X86_PT_CONTIG_MARKERS_H
> >> +
> >> +/*
> >> + * Short of having function templates in C, the function defined below is
> >> + * intended to be used by multiple parties interested in recording the
> >> + * degree of contiguity in mappings by a single page table.
> >> + *
> >> + * Scheme: Every entry records the order of contiguous successive entries,
> >> + * up to the maximum order covered by that entry (which is the number of
> >> + * clear low bits in its index, with entry 0 being the exception using
> >> + * the base-2 logarithm of the number of entries in a single page table).
> >> + * While a few entries need touching upon update, knowing whether the
> >> + * table is fully contiguous (and can hence be replaced by a higher level
> >> + * leaf entry) is then possible by simply looking at entry 0's marker.
> >> + *
> >> + * Prereqs:
> >> + * - CONTIG_MASK needs to be #define-d, to a value having at least 4
> >> + *   contiguous bits (ignored by hardware), before including this file (or
> >> + *   else only CONTIG_LEVEL_SHIFT and CONTIG_NR will become available),
> >> + * - page tables to be passed to the helper need to be initialized with
> >> + *   correct markers,
> >> + * - not-present entries need to be entirely clear except for the marker.
> >> + */
> >> +
> >> +/* This is the same for all anticipated users, so doesn't need passing 
> >> in. */
> >> +#define CONTIG_LEVEL_SHIFT 9
> >> +#define CONTIG_NR          (1 << CONTIG_LEVEL_SHIFT)
> >> +
> >> +#ifdef CONTIG_MASK
> >> +
> >> +#include <xen/bitops.h>
> >> +#include <xen/lib.h>
> >> +#include <xen/page-size.h>
> >> +
> >> +#define GET_MARKER(e) MASK_EXTR(e, CONTIG_MASK)
> >> +#define SET_MARKER(e, m) \
> >> +    ((void)((e) = ((e) & ~CONTIG_MASK) | MASK_INSR(m, CONTIG_MASK)))
> >> +
> >> +#define IS_CONTIG(kind, pt, i, idx, shift, b) \
> >> +    ((kind) == PTE_kind_leaf \
> >> +     ? (((pt)[i] ^ (pt)[idx]) & ~CONTIG_MASK) == (1ULL << ((b) + 
> >> (shift))) \
> >> +     : !((pt)[i] & ~CONTIG_MASK))
> >> +
> >> +enum PTE_kind {
> >> +    PTE_kind_null,
> >> +    PTE_kind_leaf,
> >> +    PTE_kind_table,
> >> +};
> >> +
> >> +static bool pt_update_contig_markers(uint64_t *pt, unsigned int idx,
> >> +                                     unsigned int level, enum PTE_kind 
> >> kind)
> >> +{
> >> +    unsigned int b, i = idx;
> >> +    unsigned int shift = (level - 1) * CONTIG_LEVEL_SHIFT + PAGE_SHIFT;
> >> +
> >> +    ASSERT(idx < CONTIG_NR);
> >> +    ASSERT(!(pt[idx] & CONTIG_MASK));
> >> +
> >> +    /* Step 1: Reduce markers in lower numbered entries. */
> >> +    while ( i )
> >> +    {
> >> +        b = find_first_set_bit(i);
> >> +        i &= ~(1U << b);
> >> +        if ( GET_MARKER(pt[i]) <= b )
> >> +            break;
> >> +        SET_MARKER(pt[i], b);
> >> +    }
> >> +
> >> +    /* An intermediate table is never contiguous with anything. */
> >> +    if ( kind == PTE_kind_table )
> >> +        return false;
> >> +
> >> +    /*
> >> +     * Present entries need in-sync index and address to be a candidate
> >> +     * for being contiguous: What we're after is whether ultimately the
> >> +     * intermediate table can be replaced by a superpage.
> >> +     */
> >> +    if ( kind != PTE_kind_null &&
> >> +         idx != ((pt[idx] >> shift) & (CONTIG_NR - 1)) )
> >> +        return false;
> >> +
> >> +    /* Step 2: Check higher numbered entries for contiguity. */
> >> +    for ( b = 0; b < CONTIG_LEVEL_SHIFT && !(idx & (1U << b)); ++b )
> >> +    {
> >> +        i = idx | (1U << b);
> >> +        if ( !IS_CONTIG(kind, pt, i, idx, shift, b) || GET_MARKER(pt[i]) 
> >> != b )
> >> +            break;
> >> +    }
> >> +
> >> +    /* Step 3: Update markers in this and lower numbered entries. */
> >> +    for ( ; SET_MARKER(pt[idx], b), b < CONTIG_LEVEL_SHIFT; ++b )
> >> +    {
> >> +        i = idx ^ (1U << b);
> >> +        if ( !IS_CONTIG(kind, pt, i, idx, shift, b) || GET_MARKER(pt[i]) 
> >> != b )
> >> +            break;
> >> +        idx &= ~(1U << b);
> >> +    }
> >> +
> >> +    return b == CONTIG_LEVEL_SHIFT;
> >> +}
> >> +
> >> +#undef IS_CONTIG
> >> +#undef SET_MARKER
> >> +#undef GET_MARKER
> >> +#undef CONTIG_MASK
> > 
> > Is it fine to undef CONTIG_MASK here, when it was defined outside of
> > this file?  It does seem weird to me.
> 
> I consider it not just fine, but desirable. Use sites of this header #define
> this just for the purpose of this header. And I want to leave name space as
> uncluttered as possible. Should there really arise a need to keep this, we
> can always consider removing the #undef (just like I did for
> CONTIG_LEVEL_SHIFT and CONTIG_NR because of feedback of yours on another
> patch).

OK, I find it kind of unexpected to undef in a file where it's not
defined, but I think that's fine.

Thanks, Roger.