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

[Jan Beulich <jbeulich@xxxxxxxx>]

On 01.07.2025 17:49, Roger Pau Monné wrote:
> 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.

Sounds okay to me.

Jan