From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by smtp.lore.kernel.org (Postfix) with ESMTP id 6BFDFC3DA6E for ; Sun, 17 Dec 2023 19:14:06 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id A3C726B0078; Sun, 17 Dec 2023 14:14:05 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id 9ED956B007B; Sun, 17 Dec 2023 14:14:05 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 88C976B007D; Sun, 17 Dec 2023 14:14:05 -0500 (EST) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0015.hostedemail.com [216.40.44.15]) by kanga.kvack.org (Postfix) with ESMTP id 74AD76B0078 for ; Sun, 17 Dec 2023 14:14:05 -0500 (EST) Received: from smtpin04.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay07.hostedemail.com (Postfix) with ESMTP id 442151602F6 for ; Sun, 17 Dec 2023 19:14:05 +0000 (UTC) X-FDA: 81577260450.04.F2CAFE6 Received: from mail-ed1-f52.google.com (mail-ed1-f52.google.com [209.85.208.52]) by imf22.hostedemail.com (Postfix) with ESMTP id 61D0FC0006 for ; Sun, 17 Dec 2023 19:14:03 +0000 (UTC) Authentication-Results: imf22.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=Fx0SZolg; dmarc=pass (policy=none) header.from=gmail.com; spf=pass (imf22.hostedemail.com: domain of nadav.amit@gmail.com designates 209.85.208.52 as permitted sender) smtp.mailfrom=nadav.amit@gmail.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1702840443; a=rsa-sha256; cv=none; b=D8DdVINVSNWvIu8zzVGUYZZZDbz9glnJ+M9+DP5l4bMQLxCH45V3JcuPhqHEZGleTarf7y H4QOKj/lRRqephziImUapqpVZ5qJtPA/HV+h8N8a1kXahuvm//Ibv5lKna2J7vdfZJexkp PIvjtqkb2dKnmI39Vg42FG3g74o+SI0= ARC-Authentication-Results: i=1; imf22.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=Fx0SZolg; dmarc=pass (policy=none) header.from=gmail.com; spf=pass (imf22.hostedemail.com: domain of nadav.amit@gmail.com designates 209.85.208.52 as permitted sender) smtp.mailfrom=nadav.amit@gmail.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1702840443; h=from:from:sender:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:mime-version: content-type:content-type: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references:dkim-signature; bh=qAlIATYK6g6ASaeNglWYD7dTnzBHWW3q/ZKCMEGpKSw=; b=pexQwVAxA6ZvOFFzhnH/TIHh+fFUbrZrxGfJsVMcEUiEKPVNAepQPi23GJy8hn3s8MdTKq jOLoynVNQXPlonmxyoT4B/hM1HY5Gb0HN2+SzKXfMceNwb4ZhPTSranxv6a8Lnyt+m6Z8k EZEKFCkkU/2CCrQ+B5nl5vN8gRalmys= Received: by mail-ed1-f52.google.com with SMTP id 4fb4d7f45d1cf-54dcfca54e0so3100514a12.1 for ; Sun, 17 Dec 2023 11:14:03 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1702840442; x=1703445242; darn=kvack.org; h=to:references:message-id:content-transfer-encoding:cc:date :in-reply-to:from:subject:mime-version:from:to:cc:subject:date :message-id:reply-to; bh=qAlIATYK6g6ASaeNglWYD7dTnzBHWW3q/ZKCMEGpKSw=; b=Fx0SZolghAoTd9OvlTO/kLGHvAaZ8O2SVq2EQaKlrf5YH9Wa8yTXcfodFrvj/DmAGL 1clp4KnIVGhUoOiBQsknz7iZf823EY9W+FUvahqPNJQr3OBUhpN8hGQb9XAnL1V6rwKv 3ZZDxuAdqJdS4qns8ZHDE904ghIEWF+zjc8CkAtvVVTDvYC2+I7+ReNl8Z67ZoJfyz9I BOeFvRybPzC1W1oKS4kUCuvRJMgQcaSpQPFvXLCCdkjZfhqhm1q9XOMLS3eNg/5TDuyH n767+tAjeIRjrAxlsNJdnGzsRkig2sapjh5Z3nE+LIhPLAcro1qQELt+oe8RwD5xITKO vJHw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1702840442; x=1703445242; h=to:references:message-id:content-transfer-encoding:cc:date :in-reply-to:from:subject:mime-version:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=qAlIATYK6g6ASaeNglWYD7dTnzBHWW3q/ZKCMEGpKSw=; b=AsLoH0wofl4hqPiKjx6RhGcZbC+kxWk4tC66diJBCLUPGmggFoEGVhKRFwzeRDP063 waOFR3ogtobIGlwKOU7bbclHyqm5yfjA0TdPPFOXAj74i5iR7PeN8SMd0tZn7cR85R51 S6RZlUCRR0mShFdV2FqZpYDqGmKdMmMkHjUsGdxhiml0uyvgHwi3scvTi86DOFQx7e/U g22Ncg5Jj9B1iLqdULOYn+RmybYHfxrr8zWRa/CLxDV9aFcCn4uY2He43Nn9W/oEu6Pr u1uwU1pF/OxtcZreBWvDasEpXGzJsHDhNJG+/pEN4uptYaQoFE+uDlKl1NmpYMZQrNbY Wz7Q== X-Gm-Message-State: AOJu0YxeKRsdDfwc5KOEKHbCsFtoklviRwKyGHLeSf75d/Q9smIppu7t E3ZwoRdnaVaMnM3hiz8xHgM= X-Google-Smtp-Source: AGHT+IEN3tIZdbpdVnFfl95tahRpNjWbRQOVznLJZHfiRY6lrr6de7Vw2kGd+7/mTy1LnW405nG+0Q== X-Received: by 2002:a17:906:116:b0:a1b:7df6:11dd with SMTP id 22-20020a170906011600b00a1b7df611ddmr8445806eje.80.1702840441526; Sun, 17 Dec 2023 11:14:01 -0800 (PST) Received: from smtpclient.apple ([31.154.57.136]) by smtp.gmail.com with ESMTPSA id ts4-20020a170907c5c400b00a1cc1be1158sm13295978ejc.165.2023.12.17.11.13.59 (version=TLS1_2 cipher=ECDHE-ECDSA-AES128-GCM-SHA256 bits=128/128); Sun, 17 Dec 2023 11:14:01 -0800 (PST) Content-Type: text/plain; charset=utf-8 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 In-Reply-To: <20231124132626.235350-8-david@redhat.com> Date: Sun, 17 Dec 2023 21:13:52 +0200 Cc: Linux Kernel Mailing List , linux-mm , Andrew Morton , Linus Torvalds , Ryan Roberts , Matthew Wilcox , Hugh Dickins , Yin Fengwei , Yang Shi , Ying Huang , Zi Yan , Peter Zijlstra , Ingo Molnar , Will Deacon , Waiman Long , "Paul E. McKenney" Content-Transfer-Encoding: quoted-printable Message-Id: References: <20231124132626.235350-1-david@redhat.com> <20231124132626.235350-8-david@redhat.com> To: David Hildenbrand X-Mailer: Apple Mail (2.3774.300.61.1.2) X-Rspam-User: X-Rspamd-Server: rspam06 X-Rspamd-Queue-Id: 61D0FC0006 X-Stat-Signature: 51s1hmq8pjxriys6cy3qipmumn5tcuup X-HE-Tag: 1702840443-81736 X-HE-Meta: U2FsdGVkX1/7CCmqa//oTaSDDProMl10ozm3SzATbGgK2rakzLtyJQ7+RZ/DZ8Gl68zvUSal2QBf+KR2FstuXfhvo9skpWGJLN4fKwMRWLCXwpvt4bWflgHxB2mXdCdpYpOlrpRdCA25/NohNdUehtPMa8OPSLfX0xsr1WcThBWlpEEz+Y4zgFDx6sSf9MoynwjMHTmfSW+3hz7Qf7k3D9MTz67XGI0XrhCEvj+kPYqM8DcQhjMuNcssE9HHEpIgBM+muIIedgC5V4aqIzttE61qqdqsKs6+OmL8LMfZ4cagDjcjX/d4aY+6PZQpUpc0F+OcReR944lXrVvUi8m5pMD0g5gbJF7XC4SROIVCofl4RT5bxz9ECyYBp4X620z4/jbgNrgPz2UoowbTMxGv5LtcLnoQ43Q2qGi1BznP280JEl/sduAxR48oM6grIpmnaEHDS7RcU0lBncfgyaGM1F/RH1lxb9PdK5lHPUlYmTL73N6fI51dxeUqoyZe9gkZC9e/Kkx82oiitVG+j7FayU1QhVbt5yMhGYxgUSIBD+gnomY0FB/2uLbDojxlL9b79rwm6qb6qxMp/3Lt97JZduYPXhQWvZPRdslIBPGc8eW4HZKAcrs2q/bFItM+vsM73kEdtHbXF61XZCCQn6Pn0C+NTxOH+kdg5HUpZv6cCpmSev+dCd+BPpNA/RnDlcYxurBXA2nQEmcY2lMIZC09nNIbHAcElXk691Zim++scWfCg8BscVVuz+AjEKU2yX2Dj31jjc/+F6eG3m0/hTxnXwLx7SeKDg/Lrr0jHydCemoRaU/w8t2Lrflce6quQmKxhmZCS1tHBsSiWp3qCJgVEoFiK5NqvK8yYYigh7um/fQWdTUOO5h/bVNM5M3/NE/sMDPFrsmSHNAtAzS8xopQMNmBnoimZ6zUS6tiYGd0RrsgQ48snRhXhq4u+QUtVt1CX3Mn/q3f9rQBonwGJgK isE34Fz+ AMi34JXI7oB5ab70X4bgWnTbR3NaT/a8uChf7dLmp9NRo3YDEqHrSU7vgjdpiG2UgIj3F7FLnK0zyt4K+YyR+JQgeP0/vZEGrijVNqvPKAW/VqVLsi0SAfWNmtCZV2hWQHanh3W3DOEHV7gNP3D4COGHc6sKbn3g8OmHadQuFRJEuimuWSdjeQmXAnWkikKnLM3VtgndoEdLWCCz/rxrQMbB8Shf6GSznieSYFCHB7OMuEzIhiTxpSb8MGFgjgPymffa0xRSs/4lHwjv2AOKFtwIKUEoYBhEXLKOYEKe0bs0qUtc3JjVpLxzpN6VJmDGrjgUfa29RzFL3wzUUM6R1ZC2XLdRlJ2GsfyQPDdPU81pjYQfKroGOJK9z1cBSwXbEqHQegJU6YHH4rgbiy6D0knuOajJtv0C4ucdclOlPGcY5JNUXIGsWg7PZYDjI6vb77sdbKgyWmWXhl7Inkm8Du77dWjvtm98Vdmwj6gnHYHnBCcnsgdW2UAFhN4kk3YIiYxpeh2Q9ARCG+lwB0Bo1DM94gsysliOQdCQrninffhd5EZSguRK6oMT2NQ== X-Bogosity: Ham, tests=bogofilter, spamicity=0.000000, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: List-Subscribe: List-Unsubscribe: > On Nov 24, 2023, at 3:26=E2=80=AFPM, David Hildenbrand = 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).