Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20;
From:   Liam Howlett <liam.howlett@oracle.com>
To:     "maple-tree@lists.infradead.org" <maple-tree@lists.infradead.org>,
        "linux-mm@kvack.org" <linux-mm@kvack.org>,
        "linux-kernel@vger.kernel.org" <linux-kernel@vger.kernel.org>,
        Andrew Morton <akpm@linux-foundation.org>,
        Yu Zhao <yuzhao@google.com>, Hugh Dickins <hughd@google.com>
Subject: [PATCH v11 11/69] mm/mmap: use the maple tree in find_vma() instead
 of the rbtree.
Thread-Topic: [PATCH v11 11/69] mm/mmap: use the maple tree in find_vma()
 instead of the rbtree.
Thread-Index: AQHYmYdwvhT9MF1FsUWZ8qcH7jZeHw==
Date:   Sun, 17 Jul 2022 02:46:40 +0000
Message-ID: <20220717024615.2106835-12-Liam.Howlett@oracle.com>
References: <20220717024615.2106835-1-Liam.Howlett@oracle.com>
In-Reply-To: <20220717024615.2106835-1-Liam.Howlett@oracle.com>
Accept-Language: en-US
Content-Language: en-US
x-ms-exchange-antispam-messagedata-chunkcount: 1
x-ms-exchange-antispam-messagedata-0: =?iso-8859-1?Q?tWXq5TpsHKIpVZSzTWtVNvW2gnI43sGHCGTrXmPR2f2RMDNq6TNXytPJ7s?=
 =?iso-8859-1?Q?+zJo49GcE6R3k9Q9CWrLq3HwwAK/bq+HrZMuKmaMiMkivdHRJRh3buwOZ0?=
 =?iso-8859-1?Q?u8SJN5+KqkQc3RuubqSLi9HA5FN45Z4qz9umzVzKY/6jTev2XAlipDPGT0?=
 =?iso-8859-1?Q?0tPcc8U/q2MhXDb3k9LrddIpiX+9V7uxDoEUYXalRT3dakiA0BkopPv50n?=
 =?iso-8859-1?Q?gPIwQ8IxNAYJotPWJ9m91sn6U0x9r8eP0hET3sCJ3R2a2KnaOocY4UVTl4?=
 =?iso-8859-1?Q?AoAgrVl/TsN6OX39FmJYdIjulDlEfabMMpjOdueGpheFlroN2WxkZbTD5E?=
 =?iso-8859-1?Q?k+3c6xa6pnnrfgL57ftksncp7N0LtStZmcEGU3X8iuHlBob+oD/w3jyn1Q?=
 =?iso-8859-1?Q?cPr1HYueTQV1vz/QKT+8V0EllK60qp//o9hKfJWKtDkPqKtJeNbUe95Tml?=
 =?iso-8859-1?Q?JtUiuL0xHy95wn3jkJNoeeMqKxJ7So5rSCbv62HohQZ2E4x0VmY0anI56o?=
 =?iso-8859-1?Q?gO2QHDRRowyYiYX1uNZzf19tUwwIROUmlnvFzwvSroGtrhRwfisBfHPC3O?=
 =?iso-8859-1?Q?abkRpV7qTR/VA2fD79AIdmOql7fC8ULr0+7oIzuDAwL3VE+LNSp1wlzn44?=
 =?iso-8859-1?Q?JfxRXZeiims8PxL7TogLcrsakjmnt2shECtet15bFPdyiVrTxhWopKkwr7?=
 =?iso-8859-1?Q?Qtp6jE2TqBeFkcxAO2bOUabRLfiZNt8scGFehx0rUrv6uXHfGma6ptpHQ9?=
 =?iso-8859-1?Q?jLULB3lM8Y8Qqv/ycb/7DkDVsIUd8aj5XAKfbwCZ0c40munLI9qyzMmzeZ?=
 =?iso-8859-1?Q?F1b1IvVrfXFG2VisRhcKe7+BEyShYzGqi5B1/d4ZIck6i/XgNEct4hY/MD?=
 =?iso-8859-1?Q?ZKQDWfTRi/cMaMjgs+0VH/VgRvfY3tGiMd/dqdlAdVIgEtAwo6+GcEraQV?=
 =?iso-8859-1?Q?/ScTLxJEuTBg/WIBuS3gQiibwnQYljSRiypT+KJHL5doQ2F5pHkWz6ug+1?=
 =?iso-8859-1?Q?Y/fEswXL4uWRpRBIm1Ofb1GSChnqtIdF9vKEM+x8Ga7pkMlBx04IVIrdm0?=
 =?iso-8859-1?Q?owPaNDUQtZrDz/ZvnKy2g4WmfcNGmd/PtnQqcjgnWB7bGANUCoVEwE0O7f?=
 =?iso-8859-1?Q?eP+2tGwMOqibqRBsEqoCn1GOrQdWuBxqlUyuiddTzVlbySDjwmz8OthDq2?=
 =?iso-8859-1?Q?s0zmxauwh4/q1V0ZwTME+GlK00GFfRVCb8pnZybyn0Hdsam0tqar3wLDRM?=
 =?iso-8859-1?Q?GhQCqu3umZvFH3QnoFQUh9wASOtiR2pYwaw64chH3yCV2m6xwWJH7klZgT?=
 =?iso-8859-1?Q?hQfVNaODl7PO4xGfDKsz+H+A3LchVxiSdCyTXKvEgmx5ZU0w/8NWYox72N?=
 =?iso-8859-1?Q?2L8/oSPu+ufhznN4jd359eNOCHanP3CRP1fe6L5+D0cxQLnrcRmA3BNuNH?=
 =?iso-8859-1?Q?4pQ4ttRmFn+yPdIO0gQlRyTnsNph9NvM/7+U3J26u7e4OQ8a61eucr5SeY?=
 =?iso-8859-1?Q?06HdgZ/dhOTeBx36W6Y4wXR72ip8vbm3/E3V9hLF3YxEPSpNkYPu3iKxie?=
 =?iso-8859-1?Q?jCpO5whXK8IC8+dCzv2/1iXglZda/AC3VbT/ZnplfRKvq8mY4cTm5944wp?=
 =?iso-8859-1?Q?pXqc/k2ByZYpcVOuIhCosFN/inCst4hLrURgbCl5yKRS6KEXsn3BYQUw?=
 =?iso-8859-1?Q?=3D=3D?=
Content-Type: text/plain; charset="iso-8859-1"
Content-Transfer-Encoding: quoted-printable
MIME-Version: 1.0
X-OriginatorOrg: oracle.com
X-MS-Exchange-CrossTenant-AuthAs: Internal
X-MS-Exchange-CrossTenant-AuthSource: SN6PR10MB3022.namprd10.prod.outlook.com
X-MS-Exchange-CrossTenant-Network-Message-Id: 5d951392-9c2d-493d-68af-08da679e94bd
X-MS-Exchange-CrossTenant-originalarrivaltime: 17 Jul 2022 02:46:40.2720
 (UTC)
X-MS-Exchange-CrossTenant-fromentityheader: Hosted
X-MS-Exchange-CrossTenant-id: 4e2c6054-71cb-48f1-bd6c-3a9705aca71b
X-MS-Exchange-CrossTenant-mailboxtype: HOSTED
X-MS-Exchange-CrossTenant-userprincipalname: WoeFvqi8zKTP970W8eF7RrTAsTZxDDWL/qECUecSNr6cN13oomiPu7RCPU4Yy4P/cp17BChpE3j/znTtEOtaMQ==
X-MS-Exchange-Transport-CrossTenantHeadersStamped: DM6PR10MB2908
X-Proofpoint-Virus-Version: vendor=baseguard
 engine=ICAP:2.0.205,Aquarius:18.0.883,Hydra:6.0.517,FMLib:17.11.122.1
 definitions=2022-07-17_01,2022-07-15_01,2022-06-22_01
X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 bulkscore=0 mlxscore=0 mlxlogscore=876
 suspectscore=0 phishscore=0 adultscore=0 spamscore=0 malwarescore=0
 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2206140000
 definitions=main-2207170010
X-Proofpoint-GUID: KH427pTFsIXuFq3FZb3T8oPylWgvmXQc
X-Proofpoint-ORIG-GUID: KH427pTFsIXuFq3FZb3T8oPylWgvmXQc
X-Spam-Status: No, score=-2.8 required=5.0 tests=BAYES_00,DKIM_SIGNED,
        DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,RCVD_IN_DNSWL_LOW,
        RCVD_IN_MSPIKE_H2,SPF_HELO_NONE,SPF_NONE autolearn=ham
        autolearn_force=no version=3.4.6
X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on
        lindbergh.monkeyblade.net
Precedence: bulk
List-ID: <linux-kernel.vger.kernel.org>
X-Mailing-List: linux-kernel@vger.kernel.org

From: "Liam R. Howlett" <Liam.Howlett@Oracle.com>

Using the maple tree interface mt_find() will handle the RCU locking and
will start searching at the address up to the limit, ULONG_MAX in this
case.

Add kernel documentation to this API.

Link: https://lkml.kernel.org/r/20220504010716.661115-13-Liam.Howlett@oracl=
e.com
Link: https://lkml.kernel.org/r/20220621204632.3370049-12-Liam.Howlett@orac=
le.com
Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>
Acked-by: Vlastimil Babka <vbabka@suse.cz>
Reviewed-by: David Hildenbrand <david@redhat.com>
Cc: Catalin Marinas <catalin.marinas@arm.com>
Cc: David Howells <dhowells@redhat.com>
Cc: "Matthew Wilcox (Oracle)" <willy@infradead.org>
Cc: SeongJae Park <sj@kernel.org>
Cc: Will Deacon <will@kernel.org>
Cc: Davidlohr Bueso <dave@stgolabs.net>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
---
 mm/mmap.c | 28 ++++++++++------------------
 1 file changed, 10 insertions(+), 18 deletions(-)

diff --git a/mm/mmap.c b/mm/mmap.c
index 1ba4074c75cf..96ff32ff97cd 100644
--- a/mm/mmap.c
+++ b/mm/mmap.c
@@ -2494,11 +2494,18 @@ get_unmapped_area(struct file *file, unsigned long =
addr, unsigned long len,
=20
 EXPORT_SYMBOL(get_unmapped_area);
=20
-/* Look up the first VMA which satisfies  addr < vm_end,  NULL if none. */
+/**
+ * find_vma() - Find the VMA for a given address, or the next VMA.
+ * @mm: The mm_struct to check
+ * @addr: The address
+ *
+ * Returns: The VMA associated with addr, or the next VMA.
+ * May return %NULL in the case of no VMA at addr or above.
+ */
 struct vm_area_struct *find_vma(struct mm_struct *mm, unsigned long addr)
 {
-	struct rb_node *rb_node;
 	struct vm_area_struct *vma;
+	unsigned long index =3D addr;
=20
 	mmap_assert_locked(mm);
 	/* Check the cache first. */
@@ -2506,22 +2513,7 @@ struct vm_area_struct *find_vma(struct mm_struct *mm=
, unsigned long addr)
 	if (likely(vma))
 		return vma;
=20
-	rb_node =3D mm->mm_rb.rb_node;
-
-	while (rb_node) {
-		struct vm_area_struct *tmp;
-
-		tmp =3D rb_entry(rb_node, struct vm_area_struct, vm_rb);
-
-		if (tmp->vm_end > addr) {
-			vma =3D tmp;
-			if (tmp->vm_start <=3D addr)
-				break;
-			rb_node =3D rb_node->rb_left;
-		} else
-			rb_node =3D rb_node->rb_right;
-	}
-
+	vma =3D mt_find(&mm->mm_mt, &index, ULONG_MAX);
 	if (vma)
 		vmacache_update(addr, vma);
 	return vma;
--=20
2.35.1