Re: [PATCH v4 14/21] x86: introduce helper for recording degree of contiguity in page tables

[Jan Beulich <jbeulich@xxxxxxxx>]

On 06.05.2022 15:25, Roger Pau Monné wrote:
> On Mon, Apr 25, 2022 at 10:41:23AM +0200, Jan Beulich wrote:
>> --- /dev/null
>> +++ b/xen/arch/x86/include/asm/pt-contig-markers.h
>> @@ -0,0 +1,105 @@
>> +#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,
>> + * - page tables to be passed here need to be initialized with correct
>> + *   markers.
> 
> Not sure it's very relevant, but might we worth adding that:
> 
> - Null entries must have the PTE zeroed except for the CONTIG_MASK
>   region in order to be considered as inactive.

NP, I've added an item along these lines.

>> +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 )
>> +            SET_MARKER(pt[i], b);
> 
> Can't you exit early when you find an entry that already has the
> to-be-set contiguous marker <= b, as lower numbered entries will then
> also be <= b'?
> 
> Ie:
> 
> if ( GET_MARKER(pt[i]) <= b )
>     break;
> else
>     SET_MARKER(pt[i], b);

Almost - I think it would need to be 

        if ( GET_MARKER(pt[i]) < b )
            break;
        if ( GET_MARKER(pt[i]) > b )
            SET_MARKER(pt[i], b);

or, accepting redundant updates, 

        if ( GET_MARKER(pt[i]) < b )
            break;
        SET_MARKER(pt[i], b);

. Neither the redundant updates nor the extra (easily mis-predicted)
conditional looked very appealing to me, but I guess I could change
this if you are convinced that's better than continuing a loop with
at most 9 (typically less) iterations.

Jan