On Fri, May 27, 2022 at 01:17:08PM +0200, Jan Beulich wrote:
> This is a re-usable helper (kind of a template) which gets introduced
> without users so that the individual subsequent patches introducing such
> users can get committed independently of one another.
>
> See the comment at the top of the new file. To demonstrate the effect,
> if a page table had just 16 entries, this would be the set of markers
> for a page table with fully contiguous mappings:
>
> index 0 1 2 3 4 5 6 7 8 9 A B C D E F
> marker 4 0 1 0 2 0 1 0 3 0 1 0 2 0 1 0
>
> "Contiguous" here means not only present entries with successively
> increasing MFNs, each one suitably aligned for its slot, but also a
> respective number of all non-present entries.
>
> Signed-off-by: Jan Beulich <[email protected]>
> Reviewed-by: Roger Pau Monné <[email protected]>
> ---
> @Roger: I've retained your R-b, but I was on the edge of dropping it.
Sure, that's fine.
> ---
> v5: Bail early from step 1 if possible. Arrange for consumers who are
> just after CONTIG_{LEVEL_SHIFT,NR}. Extend comment.
> v3: Rename function and header. Introduce IS_CONTIG().
> v2: New.
>
> --- /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.
Thanks, Roger.
