Received-SPF: pass (google.com: domain of linux-kernel+bounces-2780-linux.lists.archive=gmail.com@vger.kernel.org designates 2604:1380:45e3:2400::1 as permitted sender) client-ip=2604:1380:45e3:2400::1;
Content-Type: text/plain;
	charset=utf-8
Precedence: bulk
Mime-Version: 1.0 (Mac OS X Mail 16.0 \(3774.300.61.1.2\))
Subject: Re: [PATCH WIP v1 07/20] mm/rmap_id: track if one ore multiple MMs
 map a partially-mappable folio
From: Nadav Amit <nadav.amit@gmail.com>
In-Reply-To: <20231124132626.235350-8-david@redhat.com>
Date: Sun, 17 Dec 2023 21:13:52 +0200
Cc: Linux Kernel Mailing List <linux-kernel@vger.kernel.org>,
 linux-mm <linux-mm@kvack.org>,
 Andrew Morton <akpm@linux-foundation.org>,
 Linus Torvalds <torvalds@linux-foundation.org>,
 Ryan Roberts <ryan.roberts@arm.com>,
 Matthew Wilcox <willy@infradead.org>,
 Hugh Dickins <hughd@google.com>,
 Yin Fengwei <fengwei.yin@intel.com>,
 Yang Shi <shy828301@gmail.com>,
 Ying Huang <ying.huang@intel.com>,
 Zi Yan <ziy@nvidia.com>,
 Peter Zijlstra <peterz@infradead.org>,
 Ingo Molnar <mingo@redhat.com>,
 Will Deacon <will@kernel.org>,
 Waiman Long <longman@redhat.com>,
 "Paul E. McKenney" <paulmck@kernel.org>
Content-Transfer-Encoding: quoted-printable
Message-Id: <F5EF2C8E-2902-447C-BD97-05AF6FF8832D@gmail.com>
References: <20231124132626.235350-1-david@redhat.com>
 <20231124132626.235350-8-david@redhat.com>
To: David Hildenbrand <david@redhat.com>


> On Nov 24, 2023, at 3:26=E2=80=AFPM, David Hildenbrand =
<david@redhat.com> wrote:
>=20
> 5. sub-IDs
> =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D
>=20
> To achieve (2), we generate sub-IDs that have the following property,
> assuming that our folio has P=3Dfolio_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
>=20
> 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
>=20
> Consequently, the smallest number S in gen #N is:
>  S[#N] =3D (P + 1)^(N - 1)
>=20
> The largest number L in gen #N is:
>  L[#N] =3D (P + 1)^(N - 1) + (P + 1)^(N - 2) + ... (P + 1)^0 + 0.
>  -> [geometric sum with "P + 1 !=3D 1"]
>        =3D (1 - (P + 1)^N) / (1 - (P + 1))
>        =3D (1 - (P + 1)^N) / (-P)
>        =3D ((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 =E2=80=9C0=E2=80=9D=
 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 =E2=80=9Cgenerations" also =
makes it
easier to understand the correctness (at least for me).