From patchwork Wed May 4 01:13:51 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: 12836634 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 827B5C433FE for ; Wed, 4 May 2022 01:14:01 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 4EDD56B0078; Tue, 3 May 2022 21:13:58 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 3AD998D0003; Tue, 3 May 2022 21:13:58 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 08A368D0005; Tue, 3 May 2022 21:13:57 -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 D31256B0078 for ; Tue, 3 May 2022 21:13:57 -0400 (EDT) Received: from smtpin10.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay10.hostedemail.com (Postfix) with ESMTP id B83C03CE for ; Wed, 4 May 2022 01:13:57 +0000 (UTC) X-FDA: 79426288914.10.09E5538 Received: from mx0a-00069f02.pphosted.com (mx0a-00069f02.pphosted.com [205.220.165.32]) by imf25.hostedemail.com (Postfix) with ESMTP id 80B78A008B for ; Wed, 4 May 2022 01:13:44 +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 243Kx7ff030616; Wed, 4 May 2022 01:13:56 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=yl9Gax7ZI4n0/oVxjNW4LW5//V5Da7Al5qqXAKDIc9Q=; b=o4yLX3MksYpO9TkgWb6oEbW9JLO6Y4GsS9KgC/CdW418VKff28dbtw1Q4GJHi21fpTdI Smj1eg4uMs7wEIHKd914hrHXzLWK7r6qM3btAjWRK0VzKTFmN7Y03kOq4D6rd59ZDKxo yzNCyc0jn1kkCdGQdgv/c0RoJD4gDt3e6shR0wqcXyLEXJIzW8tUIqNQVOixBoaWty2n CrH3Owa+0BwYpyb/XFKValcTovmrNmHWNHG22IZCrSYqycRkkB/Nr1E581T5Myl9st+e GS9Hhbh3nhsOtBhXIYIaLX7aH/NNKFIIzsqFFivvWPf7lfUPc82wdL6d1vweL5BZ+4wc zg== Received: from iadpaimrmta03.imrmtpd1.prodappiadaev1.oraclevcn.com (iadpaimrmta03.appoci.oracle.com [130.35.103.27]) by mx0b-00069f02.pphosted.com (PPS) with ESMTPS id 3fruq0f60r-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Wed, 04 May 2022 01:13:55 +0000 Received: from pps.filterd (iadpaimrmta03.imrmtpd1.prodappiadaev1.oraclevcn.com [127.0.0.1]) by iadpaimrmta03.imrmtpd1.prodappiadaev1.oraclevcn.com (8.16.1.2/8.16.1.2) with SMTP id 2441BRJW013094; Wed, 4 May 2022 01:13:54 GMT Received: from nam10-dm6-obe.outbound.protection.outlook.com (mail-dm6nam10lp2105.outbound.protection.outlook.com [104.47.58.105]) by iadpaimrmta03.imrmtpd1.prodappiadaev1.oraclevcn.com with ESMTP id 3fsvbmv3ke-8 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Wed, 04 May 2022 01:13:54 +0000 ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=Ue/8q1IwT7oN2cVF7LdGrZHapSjNV34eB/JfVbUi0Vtwc4hcS3G/sPFBD/GvNjoIomRX88X2FnMlVOOod7UOjWt+rKPR2vhDPF73bna68zZHNlY7l2XxB15Th9gtL5SQsG5HlAQdqkvp/sK8DvZH+dExbgU/KIRjTZtFmMIiQkJnWVu3NcB/O0aGeYWyulnIlDfqPkAeQEHLwOzxqFI9SxeiAorejG20lNNHVpvbpocrvAHAVdg2T20w4X1g9NEgrukvzkOohnih9zHvrcKCwvBOEkqBKJH5Bu6GjCrCwkANTaLpiy7JILvTgyJkIAABHwL5GzYGQ3MQXcZC4oc01g== 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=yl9Gax7ZI4n0/oVxjNW4LW5//V5Da7Al5qqXAKDIc9Q=; b=IZf7CGpF3Asb1oWidGJF7HbMtD44K1FMP7Mmrs6/1fiJWp+CVz2Hi7iTP0His9RVbndx4AP5pcyCsSollcFFol6QliSeV/86U6lC84jrXVImWoh3vb6rK3n2eh/zG9DPP+WWADEelY3TA2LlkwHl5qjhuoiMSQiwQPH9KSPbsZHBSnOxQ67+4yj2EiCwxlcq+FGjiz3lcvbSRCm3BHrxeh9OyQ5It7UBSxn+fri/grbQmEETY6mXgh3DwPGTqhVFIF3HDY1+wuYG1xeBsROHC4HExSGhAxPYQ7Ih3me/T82rhdbqfKLEN8d3BTGQfNxpBy1ob86wS1UqxMQx24PYiw== 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=yl9Gax7ZI4n0/oVxjNW4LW5//V5Da7Al5qqXAKDIc9Q=; b=miR72fq+HufaJ1EoTZh4kPoDdIsj2M/oxWcRkILveN3B1VTIi9lz75f1VDZKsYu4aJurpyHR3zYGN4StmRj7nKab/jgUC7S2+EEmJWqkj4cMxbiH1QidzdGzD8mWm1vvOOjOXDV+Bh0nwOmUP8ZEHVe+4G9MXx+MI9B1qsxD3NU= Received: from SN6PR10MB3022.namprd10.prod.outlook.com (2603:10b6:805:d8::25) by PH7PR10MB5830.namprd10.prod.outlook.com (2603:10b6:510:127::10) 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:13:52 +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:13:52 +0000 From: Liam Howlett To: "maple-tree@lists.infradead.org" , "linux-mm@kvack.org" , "linux-kernel@vger.kernel.org" , Andrew Morton Subject: [PATCH v9 23/69] mm: use maple tree operations for find_vma_intersection() Thread-Topic: [PATCH v9 23/69] mm: use maple tree operations for find_vma_intersection() Thread-Index: AQHYX1Q3mlFRYcoQUEaWWiN5amr27g== Date: Wed, 4 May 2022 01:13:51 +0000 Message-ID: <20220504011345.662299-8-Liam.Howlett@oracle.com> References: <20220504002554.654642-1-Liam.Howlett@oracle.com> <20220504011345.662299-1-Liam.Howlett@oracle.com> In-Reply-To: <20220504011345.662299-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: 4a1516bf-5e6e-491e-198f-08da2d6b5a14 x-ms-traffictypediagnostic: PH7PR10MB5830: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: VunZu37gr6U4MW2ZoaeJIUVxFfMWNBLy+R788xz+w0tBQeKhBclH71YPFs2Zi+/YkZrJjf7fhBcQ9dCSxVbG7kENJu47y4eEaMLghvgywrcnGxU6CY8z2sRK8tissmZxIBxfqUyJGbgTFLF1hHjd8nfRAn4uu4xDs+aM/i8N3UQsCMBl+VbM9ALfK/zuf1yO3JC218kfgyI4souUECB1Yxi86Lg7ZfiLlyxb7tTU4jN0N+dqKdqbhBvIXeUuvx5K2pS1m/Gki+0PGIgDjbB97mA8F82cQgvsttuYTJdp8EqQtWr8k7Ky9woDdi75PfGmgjTzM5+NsB4QWotQOiXPKFM5a695eXyWHUNT3OJJe617TWXvuEdLPSJJKLSmDNEFRzRq8iuE29QUTGm3Gv7VvGiyuaRtx6jW/4tNpuixQPvEMzAea+pBmlCU93TsF1CIFEYIAsMk1Ujf8somMWWnjoeKShqC6SPfwnv/UUpDRqJNbYr1PfvDEamvzgYb2pFEJFL3LFlk8RIt+NiLCrj/y1GtbJsBFujipNBG5ZiJ33RC4OBKZoacg4Kwo2rRieHbllbSaXMhNLH52uyikC0+wJUC7/vrWM5WWUztiJu7LB8FnjV7nNwRz7Y8SdGhx0XT9v6XQayJOAgEDYZ4EYI7tu3RcCzJKAg02rEqFhwuj4IwxdAOAsli0j5L7BHQHNQtO1FC4JRoI4tnTMUDtYw2KQ== 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)(86362001)(71200400001)(83380400001)(38100700002)(38070700005)(122000001)(316002)(110136005)(44832011)(2906002)(8676002)(5660300002)(64756008)(66476007)(36756003)(8936002)(91956017)(66556008)(2616005)(66446008)(66946007)(76116006)(1076003)(186003)(6512007)(6486002)(508600001)(26005)(6506007);DIR:OUT;SFP:1101; x-ms-exchange-antispam-messagedata-chunkcount: 1 x-ms-exchange-antispam-messagedata-0: =?iso-8859-1?q?Db+hNN1bm1PN6NAuNhZsXFc?= =?iso-8859-1?q?J2ktCHLdxN8QmvCkotta0NoPSG6qH00d49VFPfOVWZam6vo6nxDRGfl4w/o9?= =?iso-8859-1?q?QE0Tgkvdr+tw6MCJut+owdiTcg9uwWjRUcZZkLDqGq2s25+yY0KZdIuoFJ5/?= =?iso-8859-1?q?NCsnJ+6RbQ37k/FDw5B79ItuCgAcVgBOBIqmuodJFRDcxnypz5hm4nPcJZL8?= =?iso-8859-1?q?ssHWeDkXr2aQv4/fylgL7swS7EB5yO3redzejFm+I4LNH+HlVL3DWmZd8bBO?= =?iso-8859-1?q?xpr6/cXUOsInQEkRckXNyCgOZxHxgjOWae2Q5AW131xQ3SzGDCCD9R+QZTl2?= =?iso-8859-1?q?SFyrJJrhm9FcE/4vPAOt4V0a+Q97gSSuVC+Prj8HmeoH9y4vNxBVZEyBgoeC?= =?iso-8859-1?q?fikwoU2rfLcuq0bFlecGC/4SRhG501Ah9PfUPddynO4ScmYUuWzbI/rB0Xzs?= =?iso-8859-1?q?ULSdzIrZGZ5cHt+p0LOIH7m0CTb89vH4IDnGPGG5G0Iy3R0gqgAzFcmqrk4r?= =?iso-8859-1?q?bmB1fFodhs9dwMLI+EIcXV7PzeQBxFG1+GNmcwIsxzGdcE5Q8YkgPZ5sTbE2?= =?iso-8859-1?q?6Mlrs1eecSy/m2YWzFnEY+YeedVP9996K5zGw11GgCF8JovgPXhZd04mJNPu?= =?iso-8859-1?q?s5d6xly1iA5prcMI1xXz7C2RLpxT+h/8j/1i7WyRpXyontnNBNmqrjnR3Y3h?= =?iso-8859-1?q?IaJiCRSkbplptOZppmrUHfbErz4aAtx+tuIuBl+hOBBUMbq5yhCsWQ2aiobT?= =?iso-8859-1?q?AvXVJVm4hOF19V1vT9Ht04dfdAYmiMYg1pR7C/lAuUO1OVPcKGTJiJW7rK61?= =?iso-8859-1?q?HibmSAut5B55TA8FVky79+k8s5R3I90XvpzLRh5n33SMntlQmRlHWvxaS5Ea?= =?iso-8859-1?q?0IQ5iHh3oTE6gHnR8vYWU9eCCsivsnddqwadSzGg7g3H9hGhJJBcDoJNQyZb?= =?iso-8859-1?q?wOSAL2ju830O15qhvKnnlcnMZQO1Silno+8lZq2JesboBe0aX2efCGauy4il?= =?iso-8859-1?q?iheim61w53Nch3nesNyMLVrrqOUXirN0kN4NfWRJoxD7OTmgq3HimZ+fURa8?= =?iso-8859-1?q?WwtNsIOoFjzWmYDfE38grHSAeW8R18MTECmSkuRGUlSTZW73NTqICslr/uIQ?= =?iso-8859-1?q?oqZrkQDuTyIVPftI5EZd4sWprbczOmOfaFiAkAsg3HKoNKaQSyQPfKtRUpb4?= =?iso-8859-1?q?jJFkPaTGec9h4YKyNQG6Bf9jdyVeMU+QUg7Erbw4CYfjTOfLdmrZekf5ymf5?= =?iso-8859-1?q?DLL5PA4xlADl+NKFSCRVwovJGWBuia3ROH8oH/mO3mE9J2h7UhhWh27YONqp?= =?iso-8859-1?q?z1s2+3wTH3+cEMVL8kpa7PncIT4eTl1zfqswUuyEq3RIY8l+FrD0/79d+V1u?= =?iso-8859-1?q?qYmC5leqOLBI+6R8R4/pJLbCQBW6qVJ9Ru6snYoMSsVu3oOAYjhbzpec32cF?= =?iso-8859-1?q?wMAyce5trQSq9PisTE/2qEur1USK1DEkpOP+plyc7qxzHneeDO1v5FB2HguC?= =?iso-8859-1?q?buQSQMVugvji4OKhypZGkoKK+IcF0PKO6JmAJAZyc+84xW+FBkb9AYXLUmYd?= =?iso-8859-1?q?4zFyO8a55A3GIPfqMS44sl3LuZii32PFGh7oD3xq4gst+HzZ4pKMoI2W+4Al?= =?iso-8859-1?q?klMEkJlmykxm30IGHrOpvo9ASyeo8TdBOuta8LMzov83BYItVrUWTuPxBDvL?= =?iso-8859-1?q?L/EiSZsH2NoFZiFyc0sKMv+Y0u5oFUtnjNkVeQjL29M8WGyjVJBFs66Kpq8G?= =?iso-8859-1?q?QijMqGv4r2XfvcwKZvb75m1qaeV/xTa+xWUW5VfHrc0FUXFgE+zTvkJtGRfN?= =?iso-8859-1?q?Tp0nqbDU=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: 4a1516bf-5e6e-491e-198f-08da2d6b5a14 X-MS-Exchange-CrossTenant-originalarrivaltime: 04 May 2022 01:13:51.9707 (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: ke4Z9OwFQdhkQgd6M0JR74akFIwVBBdqfPCL9XWsR5gUpnoKrOL3Rr87Idu6nxf4yswPwJV2pS/Xr5t7IWitAg== X-MS-Exchange-Transport-CrossTenantHeadersStamped: PH7PR10MB5830 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 phishscore=0 bulkscore=0 spamscore=0 malwarescore=0 adultscore=0 suspectscore=0 mlxscore=0 mlxlogscore=999 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2202240000 definitions=main-2205040006 X-Proofpoint-ORIG-GUID: VWO3OS50xBdTFgbPBkDwaA1kWGmsqBcO X-Proofpoint-GUID: VWO3OS50xBdTFgbPBkDwaA1kWGmsqBcO X-Rspamd-Server: rspam10 X-Rspamd-Queue-Id: 80B78A008B Authentication-Results: imf25.hostedemail.com; dkim=pass header.d=oracle.com header.s=corp-2021-07-09 header.b=o4yLX3Mk; dkim=pass header.d=oracle.onmicrosoft.com header.s=selector2-oracle-onmicrosoft-com header.b=miR72fq+; spf=none (imf25.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-Stat-Signature: jrhhbz7cdtstfo9r7373zdfn9y9isx81 X-HE-Tag: 1651626824-861933 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" Move find_vma_intersection() to mmap.c and change implementation to maple tree. When searching for a vma within a range, it is easier to use the maple tree interface. Exported find_vma_intersection() for kvm module. Signed-off-by: Liam R. Howlett --- include/linux/mm.h | 22 ++++------------------ mm/mmap.c | 29 +++++++++++++++++++++++++++++ mm/nommu.c | 11 +++++++++++ 3 files changed, 44 insertions(+), 18 deletions(-) diff --git a/include/linux/mm.h b/include/linux/mm.h index 0fdb19d1b48b..6db9face6f84 100644 --- a/include/linux/mm.h +++ b/include/linux/mm.h @@ -2780,26 +2780,12 @@ extern struct vm_area_struct * find_vma(struct mm_struct * mm, unsigned long add extern struct vm_area_struct * find_vma_prev(struct mm_struct * mm, unsigned long addr, struct vm_area_struct **pprev); -/** - * find_vma_intersection() - Look up the first VMA which intersects the interval - * @mm: The process address space. - * @start_addr: The inclusive start user address. - * @end_addr: The exclusive end user address. - * - * Returns: The first VMA within the provided range, %NULL otherwise. Assumes - * start_addr < end_addr. +/* + * Look up the first VMA which intersects the interval [start_addr, end_addr) + * NULL if none. Assume start_addr < end_addr. */ -static inline struct vm_area_struct *find_vma_intersection(struct mm_struct *mm, - unsigned long start_addr, - unsigned long end_addr) -{ - struct vm_area_struct *vma = find_vma(mm, start_addr); - - if (vma && end_addr <= vma->vm_start) - vma = NULL; - return vma; -} + unsigned long start_addr, unsigned long end_addr); /** * vma_lookup() - Find a VMA at a specific address diff --git a/mm/mmap.c b/mm/mmap.c index ec4ce76f02dc..5f948f353376 100644 --- a/mm/mmap.c +++ b/mm/mmap.c @@ -2069,6 +2069,35 @@ get_unmapped_area(struct file *file, unsigned long addr, unsigned long len, EXPORT_SYMBOL(get_unmapped_area); +/** + * find_vma_intersection() - Look up the first VMA which intersects the interval + * @mm: The process address space. + * @start_addr: The inclusive start user address. + * @end_addr: The exclusive end user address. + * + * Returns: The first VMA within the provided range, %NULL otherwise. Assumes + * start_addr < end_addr. + */ +struct vm_area_struct *find_vma_intersection(struct mm_struct *mm, + unsigned long start_addr, + unsigned long end_addr) +{ + struct vm_area_struct *vma; + unsigned long index = start_addr; + + mmap_assert_locked(mm); + /* Check the cache first. */ + vma = vmacache_find(mm, start_addr); + if (likely(vma)) + return vma; + + vma = mt_find(&mm->mm_mt, &index, end_addr - 1); + if (vma) + vmacache_update(start_addr, vma); + return vma; +} +EXPORT_SYMBOL(find_vma_intersection); + /** * find_vma() - Find the VMA for a given address, or the next vma. * @mm: The mm_struct to check diff --git a/mm/nommu.c b/mm/nommu.c index 81408d20024f..2870edfad8ed 100644 --- a/mm/nommu.c +++ b/mm/nommu.c @@ -629,6 +629,17 @@ static void delete_vma(struct mm_struct *mm, struct vm_area_struct *vma) vm_area_free(vma); } +struct vm_area_struct *find_vma_intersection(struct mm_struct *mm, + unsigned long start_addr, + unsigned long end_addr) +{ + unsigned long index = start_addr; + + mmap_assert_locked(mm); + return mt_find(&mm->mm_mt, &index, end_addr - 1); +} +EXPORT_SYMBOL(find_vma_intersection); + /* * look up the first VMA in which addr resides, NULL if none * - should be called with mm->mmap_lock at least held readlocked