Re: [PATCH 6/8] pdx: introduce a new compression algorithm based on offsets between regions

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

On Thu, Jun 12, 2025 at 10:27:03AM +0200, Jan Beulich wrote:
> On 11.06.2025 19:16, Roger Pau Monne wrote:
> > With the appearance of Intel Sierra Forest and Granite Rapids it's not
> > possible to get a production x86 host wit the following memory map:
> > 
> > SRAT: Node 0 PXM 0 [0000000000000000, 000000007fffffff]
> > SRAT: Node 0 PXM 0 [0000000100000000, 000000407fffffff]
> > SRAT: Node 1 PXM 1 [0000061e80000000, 0000065e7fffffff]
> > SRAT: Node 2 PXM 2 [00000c3e80000000, 00000c7e7fffffff]
> > SRAT: Node 3 PXM 3 [0000125e80000000, 0000129e7fffffff]
> > 
> > This is from a four socket system, with each node having 256GB of memory.
> > The total amount of RAM on the system is 1TB, but without enabling
> > CONFIG_BIGMEM the last range is not accessible, as it's above the 16TB
> > boundary covered by the frame table.
> > 
> > Note that while the memory map is very sparse, it won't be compressible
> > using the current algorithm that relies on all ranges having a shared
> > zeroed region of bits that can be removed.
> > 
> > The memory map presented above has the property of all regions being
> > similarly spaced between each other, and all having also a similar size.
> > This allows to compress them using the following formula:
> > 
> >  pdx = (pfn % offset) + ((pfn / offset) * size)
> > 
> > Where offset and size are two static coefficients calculated at
> > initialization.
> 
> What I would find useful here in addition would be offset and size values
> resulting from the example memory map above. In particular, without looking
> at the code in detail, it doesn't become quite clear how the two ranges on
> node 0 are being dealt with. For what follows I'll assume they'd be folded
> into a single range covering all of node 0.

Indeed, they are folded into a single range, that's why the function
to register ranges takes an ID, so that for this algorithm ranges with
the same ID are folded together.

For the above example the offset (pfn based) is 0x63e80000 and the
size 0x8300000.  You can see those (and for all the other examples) on
the test-pdx-offset.c file.

> Along the lines of Andrew's concern regarding the division (and modulo)
> involved, I wonder whether there might be an alternative with a lookup
> array, holding bias values (e.g.) for each node. Main question there would
> be how to quickly determine the array index to use, both from an incoming
> MFN and an incoming PDX. If such an array wouldn't have too many entries,
> such a lookup may end up being faster (on average) than a division.
> 
> Taking the example above, such an array could be:
> 
> [0x00] = 0,
> [0x06] = 0x061e80000 - 1 * 0x5000000,
> [0x0c] = 0x0c3e80000 - 2 * 0x5000000,
> [0x12] = 0x125e80000 - 3 * 0x5000000,
> 
> indexed by the top-so-many bits of the MFN. For the reverse array some
> gap would need to be left between ranges (i.e. the 0x5000000 above would
> perhaps need doubling; maybe a little less than that would suffice), such
> that the array slot to use could be determined easily there as well.

I've assumed that any kind of lookups like this would end up being
slower than arithmetic transformations.  I had the (maybe wrong)
impression that having to fetch the adjustment from an array based on
a calculated index would result in slower code that using constant
coefficients.

I was also worried about the extra memory consumption of this
approach, but overall we can use a full page for the lookup table,
which would allow up to 512 entries and that should be more than
enough.

I can try to code this suggestion.  However it's hard to benchmark
those algorithms, as the cost of rdtsc shadows the cost of the
operation.  Then running the translation in a tight loop and averaging
the result also doesn't seem very realistic, as the cache is hot in
that case.

Thanks, Roger.