From patchwork Wed May 4 01:07:53 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "Liam R. Howlett" X-Patchwork-Id: 12836625 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 609C4C4332F for ; Wed, 4 May 2022 01:08:07 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 514888D0008; Tue, 3 May 2022 21:08:01 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 49F7C8D0006; Tue, 3 May 2022 21:08:01 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 27D338D0009; Tue, 3 May 2022 21:08:01 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0011.hostedemail.com [216.40.44.11]) by kanga.kvack.org (Postfix) with ESMTP id 1081C8D0008 for ; Tue, 3 May 2022 21:08:01 -0400 (EDT) Received: from smtpin12.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay08.hostedemail.com (Postfix) with ESMTP id DAD9720751 for ; Wed, 4 May 2022 01:08:00 +0000 (UTC) X-FDA: 79426273920.12.D90FC33 Received: from mx0a-00069f02.pphosted.com (mx0a-00069f02.pphosted.com [205.220.165.32]) by imf22.hostedemail.com (Postfix) with ESMTP id E9635C0088 for ; Wed, 4 May 2022 01:07:58 +0000 (UTC) Received: from pps.filterd (m0246627.ppops.net [127.0.0.1]) by mx0b-00069f02.pphosted.com (8.17.1.5/8.17.1.5) with ESMTP id 243KnGuM029440; Wed, 4 May 2022 01:07:59 GMT DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=oracle.com; h=from : to : subject : date : message-id : references : in-reply-to : content-type : content-transfer-encoding : mime-version; s=corp-2021-07-09; bh=Cv8myIjZOfvIlULL8qjTGQaN76z/ZSIoLC0i+L+fVgQ=; b=TEfS1rFM160152Oqoc6Iow8VnJ3p8CREsS89ONSdDoktb+0ezL13nzDgJ8k/VQ7+7HZS UG4bS/nYgrPHyDKps1FcUxOTei+zZDRKMz1AMSD+HJ9EE/A6Y+vo3rIF95W3mWuXqARD OTnWitA8JhuaUyf+wDvFbo+DzKuGRm1oRC6bmndDYVULr32j7UMSDM2mtfecB2jeyvGA YLbU8bJuXCvyiW0vjrX5P8aNslFpd0F71XM2Z0+Px2+S0DODRk37XvpvDsQL3UuOzZsT cGXKBpqPE8/+G8tl3u6yAuVUOI6kg0ol66QM+FEhduxT1j/uiWFU8VKybQkF7DGFr5dX 9Q== Received: from phxpaimrmta03.imrmtpd1.prodappphxaev1.oraclevcn.com (phxpaimrmta03.appoci.oracle.com [138.1.37.129]) by mx0b-00069f02.pphosted.com (PPS) with ESMTPS id 3fruq0f5uh-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Wed, 04 May 2022 01:07:58 +0000 Received: from pps.filterd (phxpaimrmta03.imrmtpd1.prodappphxaev1.oraclevcn.com [127.0.0.1]) by phxpaimrmta03.imrmtpd1.prodappphxaev1.oraclevcn.com (8.16.1.2/8.16.1.2) with SMTP id 24416SvM039119; Wed, 4 May 2022 01:07:58 GMT Received: from nam12-bn8-obe.outbound.protection.outlook.com (mail-bn8nam12lp2176.outbound.protection.outlook.com [104.47.55.176]) by phxpaimrmta03.imrmtpd1.prodappphxaev1.oraclevcn.com with ESMTP id 3fruj2wdr3-5 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Wed, 04 May 2022 01:07:58 +0000 ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=naDeg44kvXw1yO/goamRQbUvW+4z/floTpmTw8QUNoIX5SrcfVeDlaXZNU4MUgGrA6t1ICJWvB+anjEzhZFJ2jiYVIt6z0KcBKHonVkUxceOHTmDHs+He0xVq1XW/XnlK4Z6B8MezksBCHZi8Z6dhwKGGgtOwJEXHgqlaVWtHrUvwu7BYVkeAvSFUGyv84ELlSDxODv47Nt6SnSjRo2oDML70pI3Q2RFLCRDa23UMnJrMP24DyiFCifO0GhUEE06jTisvGpMEGaFGUurSp/i/I0Wkfl6OTpjwpYZRJrjX8wK836ZTD7lk//lkrLTETLOiet2gAlV99ryh+vA4biz8g== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=microsoft.com; s=arcselector9901; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-AntiSpam-MessageData-ChunkCount:X-MS-Exchange-AntiSpam-MessageData-0:X-MS-Exchange-AntiSpam-MessageData-1; bh=Cv8myIjZOfvIlULL8qjTGQaN76z/ZSIoLC0i+L+fVgQ=; b=USwBCrqXvhHzUWN3HlQ8GZXJIrHz1qDCyG6OCCLimwQZpcztY0NxGvqji5sVDd8VdXmyHS3rjbLvyKTAXTxTcrZf20wO1JX70wTcgRG9o5SIPeHPSRN++QhVLcUzZQhpTsGfuojRXWo7ylSJB2+1sguUDV0zyZ5rbAqX1nmcPfmaNzge8UdZyCEekb17QiUk2xAoMZD2KdWgRsH57oidxRlqklhx/859wxdPZ/+NtGwBNKMUotcuRZ6fih98gOqmaUkfOic6S64g6L9OIl44k4RzT7m/2RhfpbqiByHjRS5xxAdbtEp2mGoePl3kErRRCKctpNZHg4EP/yUBRjTJXg== ARC-Authentication-Results: i=1; mx.microsoft.com 1; spf=pass smtp.mailfrom=oracle.com; dmarc=pass action=none header.from=oracle.com; dkim=pass header.d=oracle.com; arc=none DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=oracle.onmicrosoft.com; s=selector2-oracle-onmicrosoft-com; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=Cv8myIjZOfvIlULL8qjTGQaN76z/ZSIoLC0i+L+fVgQ=; b=FAht91GN3vglIt7FXqLo1xekZ4zqxMIp6VQ3UqcHstZiwWHp+mJ1bopvQ31IH/DfIG+ZjWBdloemKbYxNPY0Lk9qIulXM9CZx+Wzxoc5K7LzXy2JcF/86ycZEFjvGCwGoC6/10YIn+edzN4aEyvjl4Sy4pGrXfpS0YaXT0AaH3k= Received: from SN6PR10MB3022.namprd10.prod.outlook.com (2603:10b6:805:d8::25) by CH2PR10MB4214.namprd10.prod.outlook.com (2603:10b6:610:a6::21) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.5206.24; Wed, 4 May 2022 01:07:55 +0000 Received: from SN6PR10MB3022.namprd10.prod.outlook.com ([fe80::318c:d02:2280:c2c]) by SN6PR10MB3022.namprd10.prod.outlook.com ([fe80::318c:d02:2280:c2c%7]) with mapi id 15.20.5206.024; Wed, 4 May 2022 01:07:55 +0000 From: Liam Howlett To: "maple-tree@lists.infradead.org" , "linux-mm@kvack.org" , "linux-kernel@vger.kernel.org" , Andrew Morton Subject: [PATCH v9 12/69] mm/mmap: use the maple tree for find_vma_prev() instead of the rbtree Thread-Topic: [PATCH v9 12/69] mm/mmap: use the maple tree for find_vma_prev() instead of the rbtree Thread-Index: AQHYX1Nh/LTdV4mXI0WB2ARQgN7clw== Date: Wed, 4 May 2022 01:07:53 +0000 Message-ID: <20220504010716.661115-14-Liam.Howlett@oracle.com> References: <20220504010716.661115-1-Liam.Howlett@oracle.com> In-Reply-To: <20220504010716.661115-1-Liam.Howlett@oracle.com> Accept-Language: en-US Content-Language: en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: x-mailer: git-send-email 2.35.1 x-ms-publictraffictype: Email x-ms-office365-filtering-correlation-id: 7515d7c8-2cec-4e84-1454-08da2d6a855c x-ms-traffictypediagnostic: CH2PR10MB4214:EE_ x-microsoft-antispam-prvs: x-ms-exchange-senderadcheck: 1 x-ms-exchange-antispam-relay: 0 x-microsoft-antispam: BCL:0; x-microsoft-antispam-message-info: ip+1tdmIs3tBhPSPTVL9IrA1xIrKXql/7srkRZL0s0VXiuIyMYajTh5xJvzo2KIb7EI9RNnIA1dNgnq93K5d7jK5hXIPa/BOUc9w4kwg8A2LgE+YaAenLhPU6I3uNS6fC9r8qga9gMi4jAV0XA1xoPcwt+GczRxNPs9i+GSRBoOIBl8EJ87w2wO+Y/WfDEL38wxYRztYeRAo/1QmHfJL0+xKcWDFXZoYFDo0Y+w13TMzFwtZgSuRQHSAp9IaocM1E2SoD9APZ8p9Op8uGWZ9ILwX0CIAo/62usQMG3RjCJycklhCLWGW7/1+nKwJizASCxCYH5jOv71AQp/uGZoeYGqm7K5k5ExQ8031YcbSYfqMYUMGtJKvOfCVkRG7oWcC2TI9WZn3Elz2CJxKqbBAQYrp4tXQaWccaaQpKT9g03qSvN/zV4nCruPrKmQ95VdZWCNR98DZ57Wv2RmGjdTurSBGGOTW4eSP3TeHM8pGe4FJOGFzbm23TaxEIDq8zOehbrbgSb8zmEMERuz2b4GJa4D44V+Vtqi6Pq+Q79aFAKFcP61YmcSOc1kSf6Zwyw2g4p0fqfbcVBtvUs8X5gNfJt5Orf3S36tn+7Nqt5zEZXOaB64OyxshFNXrxx9JhBj6pjFr7R7Yfa44iU5nAZdRhduXj+47E9gcYGKsbJmKcHhYYlMXK7ltORMsEZCiGu05tFfFCQVTuuXSpgoqnWDbpA== x-forefront-antispam-report: CIP:255.255.255.255;CTRY:;LANG:en;SCL:1;SRV:;IPV:NLI;SFV:NSPM;H:SN6PR10MB3022.namprd10.prod.outlook.com;PTR:;CAT:NONE;SFS:(13230001)(366004)(66446008)(64756008)(66946007)(66556008)(66476007)(8676002)(76116006)(83380400001)(2616005)(110136005)(186003)(1076003)(316002)(6512007)(86362001)(26005)(2906002)(6506007)(71200400001)(36756003)(5660300002)(44832011)(38100700002)(508600001)(8936002)(38070700005)(122000001)(6486002);DIR:OUT;SFP:1101; x-ms-exchange-antispam-messagedata-chunkcount: 1 x-ms-exchange-antispam-messagedata-0: =?iso-8859-1?q?qljiFkzKMU8JO0nxDjv5KE9?= =?iso-8859-1?q?L8cKdq6kpMAgCnbGTodHX28mnx3lTxoQVrb8ODUrn96RJUroeMh8Tn6JZkCR?= =?iso-8859-1?q?K3tM3DBqpspS9uQ/z+KMaK5Rb8Fd7F6E7PPBKpKa0blfhwJP95NCHC41JAZs?= =?iso-8859-1?q?3Mer8pdBLePZZKeYVjeAks3S8V8+oqLJ+HKMS56mzw2KZ+53mpeq3/k/8doV?= =?iso-8859-1?q?Slku0zsRGW1TEJCnb4pGtFnvcuncCjNF9THa89m31/idlPSEqrPHRQX+G/UD?= =?iso-8859-1?q?tUAzIYDXxyEiY05BMBRwGqSxVHI6x3DQLhMGvacnkyUsWQnOMKfE16o674i2?= =?iso-8859-1?q?LOOAFTteQSzFdzwULFU29jKarNDTqpe43i3L76rtXRjG8gj9oCYb/SbNlgdO?= =?iso-8859-1?q?fTgEJtnCPMAhZ6SODYeLQsM/FKXPtrXOHAe0qVeX8tLVyzABat5ymeMskqQQ?= =?iso-8859-1?q?E1zizJDSdrGQA++yYCJSqEZwCNZCaOXQoAjPd+dg5xp8532gbgE3Eg42Y4LW?= =?iso-8859-1?q?PvoTF1It/A0EjdNNXJxloxXZ61CD/l06cZ2s7Gdd1BC96DpKufkmlpa8ygUZ?= =?iso-8859-1?q?7zcaJ1HSE+nlCoUQElcOupQewyXmDtErLwKYJCqRvyydf42epOcrZAwpOL4x?= =?iso-8859-1?q?pCAkOOEOmjvEGbEwI7hbqlLsj6l3IizSsw4X2zkkh1wXhYFr4EaE+AFwL5GQ?= =?iso-8859-1?q?Gk+pfTDoAohR6VetVPdAKrTyBocVpEJx4pGyuBKHjJT5YmWFyXZLQfhanAM2?= =?iso-8859-1?q?7NP8YlCawCzszGD6w+l35FH+nVxs8kFSuYUZt2wi+mRrvE13obYm6RaJQvJB?= =?iso-8859-1?q?uJsljdSDtV0Z+BL/FTBOoTD0ETnqhh82w9Ls4r90I6fr1Qkf13FHjqsvWt6W?= =?iso-8859-1?q?LwcHh6CA3/JOwd0RHY3WCzvPwySV5c0edHMnbf14c7MQAAE8htAByAl6mmJx?= =?iso-8859-1?q?iJYI9UjWQcvQufeKrRgEJWbBTXdNtMh8aomeiDosZabQvcd/UVnXqOmK4Oax?= =?iso-8859-1?q?+31tSmUg7NEUbSXIhAXlbFewJuoxRezSFAotyGcakafL/pgmd7UrQ1J5QorO?= =?iso-8859-1?q?2og/+88pQKjpm1HrSOjJVt0va29DFFaNSiVLctGLY30r1l8SYfZewxNOW7Z+?= =?iso-8859-1?q?FGN+XP994pivhTx6BNtplCxq44ZrcNb41pSVcwzSJeC4opDRkuN1UWwZEYSU?= =?iso-8859-1?q?AwdvswrqxgD5FhD1V890kTKeK70l9DEvrqACL52tZP1CgJSDTptlexbvcoOi?= =?iso-8859-1?q?t7iUciExPspDiAUMcuOvWsvzXv3IvK+T6DnDzlRAlGOeE03b3cJOedPYStqE?= =?iso-8859-1?q?ISp6XabBxQYLVBZlC+sonbM/lqzmwvSdOdqKBNVMWOuAYZTl9roAJd6y1XrD?= =?iso-8859-1?q?fXH6VG9Vf+MWMkCnfvoFZV3M6HSiar21lNYkhZfy7rVrxV9GnnrbkSjOMgyo?= =?iso-8859-1?q?GPNX7q3nJwu+wUBs+GxeRQ+pfVVdTMHUeJKSUl3n/l9fapkoOPUj45X584Ie?= =?iso-8859-1?q?Dt/ROEgjKrHcHcdvkvNyoQldK9x2F7kz8dPEjXuoYsz4IeP7o5IUgj0pxgW2?= =?iso-8859-1?q?kIyMaWVZ3SvZ+cLpXiT9Jljs70VT1G5r9oAbN5pTJil9fKa12eFXQCAjjkyf?= =?iso-8859-1?q?m2SGkS+UnOeE1paUVkVUTFvF6uP+MaOceiatA8lKWY8ekSVeEbUo1ycZ9uso?= =?iso-8859-1?q?HgM3nhR0r6PKUwyre3/MhG2k90TI/PgcBd2QqzP/vBgIMVcFzkNcK7jwMeS7?= =?iso-8859-1?q?ERlGR3pl4V61yfucBKi4mR/XwPQ/OoB2v5+cfc0bDjemCj4gs0Z/ijFlSGtr?= =?iso-8859-1?q?vp1nq8dU=3D?= 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: 7515d7c8-2cec-4e84-1454-08da2d6a855c X-MS-Exchange-CrossTenant-originalarrivaltime: 04 May 2022 01:07:53.6191 (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: uT0LEq32qW1rHcEZoxqXANgD1P3Y5yhVRgqfV/n75vEWcQIA09XHbOLkyhuNEgljtKhm5sG5/riSWd7YVs1Ypg== X-MS-Exchange-Transport-CrossTenantHeadersStamped: CH2PR10MB4214 X-Proofpoint-Virus-Version: vendor=fsecure engine=2.50.10434:6.0.486,18.0.858 definitions=2022-05-03_10:2022-05-02,2022-05-03 signatures=0 X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 adultscore=0 suspectscore=0 mlxlogscore=999 spamscore=0 bulkscore=0 mlxscore=0 phishscore=0 malwarescore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2202240000 definitions=main-2205040005 X-Proofpoint-ORIG-GUID: oP8_B7MkCzTDu6qOyH7sGP7ZIEqjpTEQ X-Proofpoint-GUID: oP8_B7MkCzTDu6qOyH7sGP7ZIEqjpTEQ X-Stat-Signature: ntoioxj6acaj7y8ikjky3aczt8dn9m6r X-Rspamd-Server: rspam12 X-Rspamd-Queue-Id: E9635C0088 Authentication-Results: imf22.hostedemail.com; dkim=pass header.d=oracle.com header.s=corp-2021-07-09 header.b=TEfS1rFM; dkim=pass header.d=oracle.onmicrosoft.com header.s=selector2-oracle-onmicrosoft-com header.b=FAht91GN; spf=none (imf22.hostedemail.com: domain of liam.howlett@oracle.com has no SPF policy when checking 205.220.165.32) smtp.mailfrom=liam.howlett@oracle.com; dmarc=pass (policy=none) header.from=oracle.com X-Rspam-User: X-HE-Tag: 1651626478-259904 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: From: "Liam R. Howlett" Use the maple tree's advanced API and a maple state to walk the tree for the entry at the address of the next vma, then use the maple state to walk back one entry to find the previous entry. Add kernel documentation comments for this API. Signed-off-by: Liam R. Howlett Signed-off-by: Matthew Wilcox (Oracle) Acked-by: Vlastimil Babka --- mm/mmap.c | 27 +++++++++++++++++---------- 1 file changed, 17 insertions(+), 10 deletions(-) diff --git a/mm/mmap.c b/mm/mmap.c index f582478c83b1..7ab07c67da71 100644 --- a/mm/mmap.c +++ b/mm/mmap.c @@ -2489,23 +2489,30 @@ struct vm_area_struct *find_vma(struct mm_struct *mm, unsigned long addr) } EXPORT_SYMBOL(find_vma); -/* - * Same as find_vma, but also return a pointer to the previous VMA in *pprev. +/** + * find_vma_prev() - Find the VMA for a given address, or the next vma and + * set %pprev to the previous VMA, if any. + * @mm: The mm_struct to check + * @addr: The address + * @pprev: The pointer to set to the previous VMA + * + * Note that RCU lock is missing here since the external mmap_lock() is used + * instead. + * + * 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_prev(struct mm_struct *mm, unsigned long addr, struct vm_area_struct **pprev) { struct vm_area_struct *vma; + MA_STATE(mas, &mm->mm_mt, addr, addr); - vma = find_vma(mm, addr); - if (vma) { - *pprev = vma->vm_prev; - } else { - struct rb_node *rb_node = rb_last(&mm->mm_rb); - - *pprev = rb_node ? rb_entry(rb_node, struct vm_area_struct, vm_rb) : NULL; - } + vma = mas_walk(&mas); + *pprev = mas_prev(&mas, 0); + if (!vma) + vma = mas_next(&mas, ULONG_MAX); return vma; }