Re: [PATCH WIP v1 07/20] mm/rmap_id: track if one ore multiple MMs map a partially-mappable folio

[Nadav Amit]

> On Nov 24, 2023, at 3:26 PM, David Hildenbrand <david@xxxxxxxxxx> wrote:
> 
> 5. sub-IDs
> ==========
> 
> To achieve (2), we generate sub-IDs that have the following property,
> assuming that our folio has P=folio_nr_pages() pages.
>  "2 * sub-ID" cannot be represented by the sum of any other *2* sub-IDs
>  "3 * sub-ID" cannot be represented by the sum of any other *3* sub-IDs
>  "4 * sub-ID" cannot be represented by the sum of any other *4* sub-IDs
>  ...
>  "P * sub-ID" cannot be represented by the sum of any other *P* sub-IDs
> 
> The sub-IDs are generated in generations, whereby
> (1) Generation #0 is the number 0
> (2) Generation #N takes all numbers from generations #0..#N-1 and adds
>    (P + 1)^(N - 1), effectively doubling the number of sub-IDs
> 
> Consequently, the smallest number S in gen #N is:
>  S[#N] = (P + 1)^(N - 1)
> 
> The largest number L in gen #N is:
>  L[#N] = (P + 1)^(N - 1) + (P + 1)^(N - 2) + ... (P + 1)^0 + 0.
>  -> [geometric sum with "P + 1 != 1"]
>        = (1 - (P + 1)^N) / (1 - (P + 1))
>        = (1 - (P + 1)^N) / (-P)
>        = ((P + 1)^N - 1) / P

David, as you know it took me a while to understand your impressive work.

I think that part of what made it hard for me is the presentation and the
formulation of sub-IDs in arithmetic means instead of bit manipulations.

Basically, IIUC, you want for order-K pages to add K-1 “0” bits between
each rmap-id bits.

In this case, in x86-64 (with BMI2) there is the PDEP instruction that can
generate these values rather easily with little overhead.

I think that besides the easier generation of sub-ids values in this
manner, discussing the matter without the “generations" also makes it
easier to understand the correctness (at least for me).