| Message ID | 1fec512a-8c7b-69b5-40bf-88b42e9ecb7d@suse.com (mailing list archive) |
|---|---|
| State | Superseded |
| Headers | show |
| Series | IOMMU: superpage support when not sharing pagetables | expand |
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 <jbeulich@suse.com> > Reviewed-by: Roger Pau Monné <roger.pau@citrix.com> > --- > @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.
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). Jan
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.
--- /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 + +#endif /* CONTIG_MASK */ + +#endif /* __ASM_X86_PT_CONTIG_MARKERS_H */