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

[Jan Beulich <jbeulich@xxxxxxxx>]

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).

For the example in the description, i.e.

PFN compression using PFN lookup table shift 29 and PDX region size 0x10000000
 range 0 [0000000000000, 0x0000807ffff] PFN IDX  0 : 0000000000000
 range 1 [0x00063e80000, 0x0006be7ffff] PFN IDX  3 : 0x00053e80000
 range 2 [0x000c7e80000, 0x000cfe7ffff] PFN IDX  6 : 0x000a7e80000
 range 3 [0x0012be80000, 0x00133e7ffff] PFN IDX  9 : 0x000fbe80000

we'd end up with plimit[] holding

0, 0x10000000, 0x10000000, 0x10000000, 0x20000000, 0x20000000, 0x20000000,
0x30000000, 0x30000000, 0x30000000, 0x40000000, 0x40000000, 0x40000000.

For this example the 2nd of the comparisons could even be omitted afaict, but
I couldn't convince myself that this would hold for the general case.

Jan