Message ID | 20220720021727.17018-13-Liam.Howlett@oracle.com (mailing list archive) |
---|---|
State | New |
Headers | show
Return-Path: <owner-linux-mm@kvack.org> 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 C8958CCA487 for <linux-mm@archiver.kernel.org>; Wed, 20 Jul 2022 02:18:05 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 57E12940008; Tue, 19 Jul 2022 22:17:56 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 4432794000B; Tue, 19 Jul 2022 22:17:56 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 0981F940008; Tue, 19 Jul 2022 22:17:55 -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 D90F4940008 for <linux-mm@kvack.org>; Tue, 19 Jul 2022 22:17:55 -0400 (EDT) Received: from smtpin17.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay10.hostedemail.com (Postfix) with ESMTP id B4005C036A for <linux-mm@kvack.org>; Wed, 20 Jul 2022 02:17:55 +0000 (UTC) X-FDA: 79705867710.17.B833C3D Received: from mx0b-00069f02.pphosted.com (mx0b-00069f02.pphosted.com [205.220.177.32]) by imf19.hostedemail.com (Postfix) with ESMTP id 435051A008C for <linux-mm@kvack.org>; Wed, 20 Jul 2022 02:17:55 +0000 (UTC) Received: from pps.filterd (m0246631.ppops.net [127.0.0.1]) by mx0b-00069f02.pphosted.com (8.17.1.5/8.17.1.5) with ESMTP id 26K1FaEH015096; Wed, 20 Jul 2022 02:17:53 GMT DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=oracle.com; h=from : to : cc : subject : date : message-id : references : in-reply-to : content-type : content-transfer-encoding : mime-version; s=corp-2022-7-12; bh=Inai7+Xsx308VsWeAtBqzeGr8bnOosAz9uaDpcaMZDw=; b=I+9l9BDow4GelXVY7VbnOgc3NYVtLXOptYN8rOY1AuSt3zXD1EgIwT1v7zM1T2+ojpLY zcm3jWVAMvH4HEY3fGa23OK9N22ke3QqE0jGuYYebWsIyLH8m0z4g8Ysslg/EhzKnM0h sAP72Gt1x24gTQWS2nKFT3WXyNBuRcuWSmKpawKQEp/INIGMYZZpzIdHYGqwBYq+pcnN 7QmarSLxpTY4Zid7NiUY4W71fBHBb0Uci7705QMopLK9ymkdBIUtuVEc3vMNzZnvrPlU nGPwQeolZk/dKdOKrNoEC+7g639wTEmsNyYsUKPqr1EdRty2BKB4RXv36IbycQacbM4c Jw== Received: from iadpaimrmta03.imrmtpd1.prodappiadaev1.oraclevcn.com (iadpaimrmta03.appoci.oracle.com [130.35.103.27]) by mx0b-00069f02.pphosted.com (PPS) with ESMTPS id 3hbm42g542-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Wed, 20 Jul 2022 02:17:53 +0000 Received: from pps.filterd (iadpaimrmta03.imrmtpd1.prodappiadaev1.oraclevcn.com [127.0.0.1]) by iadpaimrmta03.imrmtpd1.prodappiadaev1.oraclevcn.com (8.17.1.5/8.17.1.5) with ESMTP id 26JNHLKx022321; Wed, 20 Jul 2022 02:17:52 GMT Received: from nam10-mw2-obe.outbound.protection.outlook.com (mail-mw2nam10lp2109.outbound.protection.outlook.com [104.47.55.109]) by iadpaimrmta03.imrmtpd1.prodappiadaev1.oraclevcn.com (PPS) with ESMTPS id 3hc1hseann-5 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Wed, 20 Jul 2022 02:17:52 +0000 ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=N9jN5POusYlE3+uoKevdKIjRCUA5W+tmkiiS9BCDmNy669o9+pp3cpcHdHAkQnFWezxAuj6BNaLCpN4v20KwIN5P+qqhgFPk2zqNEH1jj9Gx+PMu8kaAxwjuxfGfFiAdHvGxFYvk8u+KXqCTSPEMcO/h7spc7R4+hRjkt8Gdt45z/ul5D0G5ABKf7Vz74lpO61ouqCrrhEATmf+NAoRvzbLTHnGKK+GROE2Dmu0VleBYt5TSL31Ee7OGvnQ8IgTiCoInk2onGCOwSAytjD0bHvZe6EK2ZhQra3r1HEfC/1aZlRT39oq7CGusczuF4mwvHprYW0iEt0bwqFvJqew3jw== 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=Inai7+Xsx308VsWeAtBqzeGr8bnOosAz9uaDpcaMZDw=; b=hEvG/B5dge+EkqGJd4jOOw1tb8J7D6AOA6uYetP50TDIIqJXYMyszULdVK7A6RDwQSS7yzcozVR8q7WYIiL1QkBSNdmfDPRUc4+Abky5t/1oW9SonQI/o6zHe24O+MXJ5BGjOlboIRttq3x/u6a+knqHjZBMjXMhAtAfK2Zo5SQuXvgrgX8j4HMR/OEMLT7gRVlw5WMZuw8zkq/OWR6Q6T0rdHtwOW9tKyqNI1HomboKTOleqJhh8il4BrcPoqWSzE9sTwGh2eT4JsY1NkGGpvjVagdIgJuN2aUKOJELkntJXa2kE9feViCn3kmVM1HJVd+P4FT/j69QDH9eAOFSMg== 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=Inai7+Xsx308VsWeAtBqzeGr8bnOosAz9uaDpcaMZDw=; b=yPCF7/sS7/Mh6BLFOpKLuaKAfTlgMFcZqjTIRcIMBygqCoVIKK/IYarDkU82+cFWCN/pWgZKwfNajtjkXgXNXh13NN18IMsQtgkFywrJ1hGCQmGXkgjiJ/mvpcUXN+rwBSAa9szGUMjGryeCyQsLl15i//G6M4gzkBUwHBDbnkY= Received: from SN6PR10MB3022.namprd10.prod.outlook.com (2603:10b6:805:d8::25) by IA1PR10MB6243.namprd10.prod.outlook.com (2603:10b6:208:3a1::15) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.5417.26; Wed, 20 Jul 2022 02:17:49 +0000 Received: from SN6PR10MB3022.namprd10.prod.outlook.com ([fe80::c4d1:edc3:7d21:7c68]) by SN6PR10MB3022.namprd10.prod.outlook.com ([fe80::c4d1:edc3:7d21:7c68%6]) with mapi id 15.20.5438.024; Wed, 20 Jul 2022 02:17:49 +0000 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>, Hugh Dickins <hughd@google.com> CC: Yu Zhao <yuzhao@google.com> Subject: [PATCH v12 12/69] mm/mmap: use the maple tree for find_vma_prev() instead of the rbtree Thread-Topic: [PATCH v12 12/69] mm/mmap: use the maple tree for find_vma_prev() instead of the rbtree Thread-Index: AQHYm97nwWeYiLIcvUWN7RbY5HprLA== Date: Wed, 20 Jul 2022 02:17:47 +0000 Message-ID: <20220720021727.17018-13-Liam.Howlett@oracle.com> References: <20220720021727.17018-1-Liam.Howlett@oracle.com> In-Reply-To: <20220720021727.17018-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: 1312f08e-784d-476c-b1b1-08da69f60b0a x-ms-traffictypediagnostic: IA1PR10MB6243:EE_ x-ms-exchange-senderadcheck: 1 x-ms-exchange-antispam-relay: 0 x-microsoft-antispam: BCL:0; x-microsoft-antispam-message-info: bwSguN6pWztarzx7OrOIlI3RqInH3HeaSXeymDIW6wKpSaSyR/P2hNr+7lJ7VtYDBlLlW65fimsbEbbkvGiCj8OrcaOF8IofauYLMfyk7eG0l0Np0bvIx4AXBrXwkkjXxUqt40Mk1D2FpkLs076dpVDfn8phPsmdN28KSewFtyaMQHl6lOENCPwabj9BMKpI7SMK3Yh/1hE75ld5xUEHNeobTbz9fs5nAdP2/xJHQoYFK/iN4S++qRsNFU/FrHkuk4nROZnt9yFMJZxRy0QVeseTBNLRx7l6ps4Ydl5h940Lb8S7QlXvNtPt6LebZAov3X4E51/8ROmL6xnZyHISruVsjvaOQ+pwxntdrrn6FCPrZUZwkjyGIbYt8GG64K1cv7AED4QPztJeQ6Pgx65D1JnAEN4oh57/UO8qIfZZnTh0Cae5s4rU27dYd4JYLxdxWEiMGi5AoPAX9l5msbsGwqod9Mz3uo+ei9EAmso99v7EEXiEeh2a7Gc9H+z/vcL0GpYFnVrLA+eoP4/hmSlfaeLnkqbxMf9tRIYjR2PiIKIbYpPra5ItZWb0xPbQZp+FIWWaloCD+Bh5Qb8J8RgasD13CnmFWU4AT+vbK+ge40klvFkzQeOE4DT9UYS8lRYO6fgP59fF/7yoS6fPHqhgeyPGqbDmqJ/8oLtwtWKpGLsKNlBIGUsZMSA+mV8RGnOIPKdUcCc/xnHf3xACvwRqxVoIHsqFTfM2Reep3OX1iOzOyL3BiKaZi6yPpJVQt+Y51aW0fdjlp5aN0A2S6V6zXD+ceEI9eIDfqqLOkclWXUHN+D10GDjWRo1fw7DlFo64DFhCKdJ9uXuHqO7esYjnwinB3sIb3xA+7ieJU5pX6rlQcHCqA1vO2r5vq2bhY0FZ 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:(13230016)(396003)(376002)(39860400002)(366004)(136003)(346002)(2906002)(26005)(1076003)(6486002)(91956017)(8676002)(71200400001)(86362001)(8936002)(5660300002)(38100700002)(83380400001)(66476007)(6512007)(36756003)(122000001)(966005)(38070700005)(316002)(478600001)(44832011)(4326008)(64756008)(66946007)(76116006)(186003)(66556008)(110136005)(66446008)(6506007)(41300700001)(2616005);DIR:OUT;SFP:1101; x-ms-exchange-antispam-messagedata-chunkcount: 1 x-ms-exchange-antispam-messagedata-0: =?iso-8859-1?q?69ONXJf0hncrpvBblUZDsWB?= =?iso-8859-1?q?HsRwhLnnkRYdsHRApywVqB4zthFG21wjMjzqhkeycK8zIx3Gn0gwf4bT7ed5?= =?iso-8859-1?q?A5ybkkCEGwMwBlPZ/GyGRYxkSTudNN7/bFXrGHsaOt9wabtKYe8zKY/r3pFB?= =?iso-8859-1?q?9cNU29T7WQFnCir9mT9IsFcto+Z9227akV31g5LH+VugvHlacZn9iQ9S9fAY?= =?iso-8859-1?q?lek4OSCzYSwx3Caby0EA7rLXR64mS2uVVJw6lFs3HlpJlhSXrkEiUwbktHMh?= =?iso-8859-1?q?WBpOj9f6DsyDmq0rRdIwpHj8gJaC6eP2WsG4ThS5LZwM/h8H4kbDn46PdepZ?= =?iso-8859-1?q?XO3s22En2tVTPmev/AzcOeoAgNvWsd2QxDSRHJvby41r4Y66SlhxlwH4Bcid?= =?iso-8859-1?q?fcgo9W63oAorG9a+JZyqcWTDYvM38zpPnAq4sClORwAoBU50jz9UmXy9tEZQ?= =?iso-8859-1?q?hojazpG4SHr3aDOpMTDd/0nRrlueDf1wECZsyFWk5Zmjq9K2dqTBvEvealBd?= =?iso-8859-1?q?3OH2BgrokyG8FVjWXfAZ+cW81aM1o7OvebUB8XS4P8LyfuFciqdZUrfA1KCu?= =?iso-8859-1?q?EhpNUCTUEKcacBjLiTYQEhEVw18AqKNVqLPRIthCavv0X6N4Hx9TaqtEotRF?= =?iso-8859-1?q?hnxlHpSdh/WULwZgJhbHSQnYJ/hKapklO5+D1KVTjCJpb4Ho/l+kAlzHjSmI?= =?iso-8859-1?q?CS3y1H0HH2f2oNJJJPxV/9FsP7ewCdX1rsG3c4k8ADJau1Bo+DrmSpEaYdiy?= =?iso-8859-1?q?ieoCRfQr0QRH5g2LKgPrXf+9xcIhDxBBYAibA3+pl9zJEe1OBBZdhV0s4UjI?= =?iso-8859-1?q?pJOXXwvM5hXyzuKWE3yicrF3qBAdZiPpSbZ0Ca6wch6b3ONVb9SrFMNqoBKK?= =?iso-8859-1?q?YT/PL9zkterrQZ/c9HOVBT9cD+jWSJcd3cYAUBMma4NjE/w4Z8GsnnR4b3cp?= =?iso-8859-1?q?obH488rfpyjj6JtZN0ZCeii3z/Zg4VLk7Wp6CHpTOFZCoyQYHUWMKOm+eVJR?= =?iso-8859-1?q?VpkWrKtgnJhueQz7+NgtV5eZRpJlX2A2GYAFsQ42xd6bIzCWrW2WouPVKyVG?= =?iso-8859-1?q?m46eAr7guvddN9DSwWGMsw/VPCpojhzQVz20bhyE6ShQGaP4Rd2J/Gq0sOOX?= =?iso-8859-1?q?tZpN/xjZfo5ODmQr0pVYYYWEd0NHS3UbcNFyP2NIevo5EOyriTBQtrac9m+E?= =?iso-8859-1?q?L9DMRQtiaMw+5kq7DGRyQPsdSOxplkxwiawnx/7z2nlFKAjwC/JOVVqltJ9E?= =?iso-8859-1?q?CEpvdZkMvnw46XbzgE4RBHMwKphv7GMD3rljOm3RIoyGmFiFyhbV8SfjonOD?= =?iso-8859-1?q?qL/yehUFyZyVPfakQAVq8PX3THqKyX66TI2NWEVt4SHMpjzDUd8exYv14FqU?= =?iso-8859-1?q?dWjXyw2gvfHXEMRQmh+gT0FwwUBf9J38dr0M+k6RBvL2uJMH/DEIkml2MXFR?= =?iso-8859-1?q?od+oK5DZvccGoRWcKdDBd2oBIb15cb1e0sb93YDyDkjz4t9DbL+RPUJWxzUw?= =?iso-8859-1?q?fbXym1M05PBBIdGyEjia5+kzrGOwFOdsT1dHHDYX3jg42KTtvZYBhjEad4dl?= =?iso-8859-1?q?DdZXlh36azeyDBOoPwmCD2QBMQAzSq6qkheUhB6/SoytfrTD2qfo/JAB0MOy?= =?iso-8859-1?q?VppV56wzYgvjR6k7+9Nvk3n91dUpRNe0N8nuUDg=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: 1312f08e-784d-476c-b1b1-08da69f60b0a X-MS-Exchange-CrossTenant-originalarrivaltime: 20 Jul 2022 02:17:47.3532 (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: +AHqaM9E01zJITA71gvRR5aNBJxa+NRf5pPgaypa9wxADsf/dC3jp5bueX/dAOGGnbiewN3/hfFwy3ea7mU7ZQ== X-MS-Exchange-Transport-CrossTenantHeadersStamped: IA1PR10MB6243 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-19_10,2022-07-19_01,2022-06-22_01 X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 spamscore=0 bulkscore=0 malwarescore=0 mlxscore=0 phishscore=0 mlxlogscore=999 suspectscore=0 adultscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2206140000 definitions=main-2207200008 X-Proofpoint-ORIG-GUID: vcbu30n8HXPE-xJefaKhGabVlPIXEGYm X-Proofpoint-GUID: vcbu30n8HXPE-xJefaKhGabVlPIXEGYm ARC-Seal: i=2; s=arc-20220608; d=hostedemail.com; t=1658283475; a=rsa-sha256; cv=pass; b=Mw2X29UgBaEoMDaMBIhRqrI8DHfjClQ8UGFodjAMohFQtM0K4z8+X8DvBpx+N7UDBP3W6L NHMB7HusDiRTLIJCuLHffH9nX84I/tFhNhBIjyLwn7NBKEhYDPJ9MMlN+UkzY9c23TrNAs 02drOq0odUXND36yOD4dJ06BNN2nIgU= ARC-Authentication-Results: i=2; imf19.hostedemail.com; dkim=pass header.d=oracle.com header.s=corp-2022-7-12 header.b=I+9l9BDo; dkim=pass header.d=oracle.onmicrosoft.com header.s=selector2-oracle-onmicrosoft-com header.b="yPCF7/sS"; spf=none (imf19.hostedemail.com: domain of liam.howlett@oracle.com has no SPF policy when checking 205.220.177.32) smtp.mailfrom=liam.howlett@oracle.com; arc=pass ("microsoft.com:s=arcselector9901:i=1"); dmarc=pass (policy=none) header.from=oracle.com ARC-Message-Signature: i=2; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1658283475; 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=Inai7+Xsx308VsWeAtBqzeGr8bnOosAz9uaDpcaMZDw=; b=u+puApISJTbxLj/E769w4YAf+93qCuZrUPL26PXkEB1JKeDfuAB7hcGWRH/Owh4NaagkrB 6mc/u9oe8ebTqtijSz16qnRt5H8mdQlFCcWBKrGEzPRlPMC9yrouYZoE44ScqR/xFZakr/ M6xSplreqejTp7Dmlibr64vggLu3Heo= X-Rspamd-Queue-Id: 435051A008C Authentication-Results: imf19.hostedemail.com; dkim=pass header.d=oracle.com header.s=corp-2022-7-12 header.b=I+9l9BDo; dkim=pass header.d=oracle.onmicrosoft.com header.s=selector2-oracle-onmicrosoft-com header.b="yPCF7/sS"; spf=none (imf19.hostedemail.com: domain of liam.howlett@oracle.com has no SPF policy when checking 205.220.177.32) smtp.mailfrom=liam.howlett@oracle.com; arc=pass ("microsoft.com:s=arcselector9901:i=1"); dmarc=pass (policy=none) header.from=oracle.com X-Rspam-User: X-Rspamd-Server: rspam06 X-Stat-Signature: f56jhe7o3orca6mt4ktjer7bbyxcy4na X-HE-Tag: 1658283475-297527 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: <linux-mm.kvack.org> |
Series |
Introducing the Maple Tree
|
expand
|
diff --git a/mm/mmap.c b/mm/mmap.c index 208deb8f55a9..12abf6a75690 100644 --- a/mm/mmap.c +++ b/mm/mmap.c @@ -2517,23 +2517,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; }