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

[Jan Beulich <jbeulich@xxxxxxxx>]

On 12.06.2025 16:03, Roger Pau Monné wrote:
> 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.

Oh, okay; didn't think of looking at the numbers in the test.

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

Latency and throughput of DIV are quite a bit higher than those of memory
reads, assuming such reads come from a relatively hot cacheline. Then
again comparing such merely from spelled out numbers in some docs usually
doesn't work overly well.

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

In the example above far less than a page should be needed. In general I'd
expect one array slot per (contiguous chunk on a) node.

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

Except that, the fewer entries such an array would have, the hotter the
cacheline(s) can be expected to be anyway. But yes, gaining a clear
picture may be difficult. Then again please recall that my earlier
patching attempt (using BMI2 insns) was also rejected mainly on the
basis that the insns chosen are known to not perform well on some
hardware, without having taken any actual numbers (which again would
have been difficult to obtain in a representable way) into account.

Overall I'm not sure this alternative if worth trying out. I merely
wanted to point out there possibly is such an alternative, given the
concern Andrew had voiced. In the end there may be similar concerns
here ...

Jan