Re: [PATCH v2 8/8] pdx: introduce a new compression algorithm based on region offsets

["Roger Pau Monné" <roger.pau@citrix.com>]

On Mon, Jun 30, 2025 at 08:34:52AM +0200, Jan Beulich wrote:
> On 20.06.2025 13:11, Roger Pau Monne wrote:
> > @@ -40,6 +41,8 @@ bool __mfn_valid(unsigned long mfn)
> >  
> >  #ifdef CONFIG_PDX_MASK_COMPRESSION
> >      invalid |= mfn & pfn_hole_mask;
> > +#elif defined(CONFIG_PDX_OFFSET_COMPRESSION)
> > +    invalid |= mfn ^ pdx_to_pfn(pfn_to_pdx(mfn));
> >  #endif
> >  
> >      if ( unlikely(evaluate_nospec(invalid)) )
> 
> In the chat you mentioned that you would add a check against max_pdx here. While
> that feels sufficient, I couldn't quite convince myself of this formally. Hence
> an alternative proposal for consideration, which imo is more clearly achieving
> the effect of allowing for no false-positive results. In particular, how about
> adding another array holding the PDX upper bounds for the respective region.
> When naming the existing two arrays moffs[] and poffs[] for brevity, the new
> one would be plimit[], but indexed by the MFN index. Then we'd end up with
> 
> 	p = mfn - moffs[midx]; /* Open-coded pfn_to_pdx() */
> 	invalid |= p >= plimit[midx] || p < plimit[midx - 1];
> 
> Of course this would need massaging to deal with the midx == 0 case, perhaps by
> making the array one slot larger and incrementing the indexes by 1. The
> downside compared to the max_pdx variant is that while it's the same number of
> memory accesses (and the same number of comparisons [or replacements thereof,
> like the ^ in context above), cache locality is worse (simply because of the
> fact that it's another array).

I've got an alternative proposal, that also uses an extra array but is
IMO simpler.  Introduce an array to hold the PFN bases for the
different ranges that are covered by the translation.  Following the
same example, this would be:

PFN compression using lookup table shift 29 and region size 0x10000000
 range 0 [0000000000000, 000000807ffff] PFN IDX   0 : 0000000000000
 range 1 [0000063e80000, 000006be7ffff] PFN IDX   3 : 0000053e80000
 range 2 [00000c7e80000, 00000cfe7ffff] PFN IDX   6 : 00000a7e80000
 range 3 [000012be80000, 0000133e7ffff] PFN IDX   9 : 00000fbe80000

pfn_bases[] = { [0] =          0, [3] =  0x63e80000,
                [6] = 0xc7e80000, [9] = 0x12be80000 };

With the rest of the entries poisoned to ~0UL.

The checking would then be:

base = pfn_bases[PFN_TBL_IDX(mfn)];
invalid |= mfn < base || mfn >= base + (1UL << pdx_index_shift);

I think the above is clearer and avoids the weirdness of using IDX +
1 for the array indexes.  This relies on the fact that we can obtain
the PDX region size from the PDX shift itself.

Thanks, Roger.