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