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

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-Id: <F5EF2C8E-2902-447C-BD97-05AF6FF8832D@gmail.com>
Date: Sun, 17 Dec 2023 21:13:52 +0200
From: Nadav Amit <nadav.amit@...il.com>
To: David Hildenbrand <david@...hat.com>
Cc: Linux Kernel Mailing List <linux-kernel@...r.kernel.org>,
 linux-mm <linux-mm@...ck.org>,
 Andrew Morton <akpm@...ux-foundation.org>,
 Linus Torvalds <torvalds@...ux-foundation.org>,
 Ryan Roberts <ryan.roberts@....com>,
 Matthew Wilcox <willy@...radead.org>,
 Hugh Dickins <hughd@...gle.com>,
 Yin Fengwei <fengwei.yin@...el.com>,
 Yang Shi <shy828301@...il.com>,
 Ying Huang <ying.huang@...el.com>,
 Zi Yan <ziy@...dia.com>,
 Peter Zijlstra <peterz@...radead.org>,
 Ingo Molnar <mingo@...hat.com>,
 Will Deacon <will@...nel.org>,
 Waiman Long <longman@...hat.com>,
 "Paul E. McKenney" <paulmck@...nel.org>
Subject: Re: [PATCH WIP v1 07/20] mm/rmap_id: track if one ore multiple MMs
 map a partially-mappable folio

> On Nov 24, 2023, at 3:26 PM, David Hildenbrand <david@...hat.com> 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).