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

[Jan Beulich <jbeulich@xxxxxxxx>]

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.

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.

Jan