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 72A76C433F5 for ; Tue, 26 Apr 2022 15:07:20 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 3DE306B009C; Tue, 26 Apr 2022 11:06:47 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 139BD6B009F; Tue, 26 Apr 2022 11:06:47 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id D79796B009B; Tue, 26 Apr 2022 11:06:46 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (relay.hostedemail.com [64.99.140.26]) by kanga.kvack.org (Postfix) with ESMTP id 73DDE6B00A0 for ; Tue, 26 Apr 2022 11:06:46 -0400 (EDT) Received: from smtpin25.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay13.hostedemail.com (Postfix) with ESMTP id 580AE608D0 for ; Tue, 26 Apr 2022 15:06:46 +0000 (UTC) X-FDA: 79399357212.25.323AC3B Received: from mx0a-00069f02.pphosted.com (mx0a-00069f02.pphosted.com [205.220.165.32]) by imf24.hostedemail.com (Postfix) with ESMTP id 39F6D180062 for ; Tue, 26 Apr 2022 15:06:42 +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 23QDT0fg015405; Tue, 26 Apr 2022 15:06:42 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=Ogt+c3oWhWfK2AtETrybCdUXg5TkjjhP8U5EGNjpxXw=; b=U+/S5lDzvpuoToKyKjLoug3tZK1tt5lIAWcfue3hRV5TVHmf0prQQ9R8jNHWlC53cZjq 4lDpAHJUOoF0bHCH1mavawzZvAJIA0GIfGFoPwU62dOBQRvx96aYLpQWK4Lv3aONcuCv NotNOMpG5cfEaPaAMjqnDLvUB1yU9NKGH53TBK1e9Fj85WzpSSEEZ7xWKftGY64bhcij egn2TEw7x1w0bZMYn88uisFhuLdrk/WOaI8Ikz8boLFeSlmincFAYApMqz48Fw+98/G6 WFmawVz7o61krpgRVVfdEETJlY+sbZzW+wsCcvoPGPi4mhUEFawRuN702WjnJLXp0fWD Hg== Received: from iadpaimrmta01.imrmtpd1.prodappiadaev1.oraclevcn.com (iadpaimrmta01.appoci.oracle.com [130.35.100.223]) by mx0b-00069f02.pphosted.com (PPS) with ESMTPS id 3fmb9apbj9-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Tue, 26 Apr 2022 15:06:41 +0000 Received: from pps.filterd (iadpaimrmta01.imrmtpd1.prodappiadaev1.oraclevcn.com [127.0.0.1]) by iadpaimrmta01.imrmtpd1.prodappiadaev1.oraclevcn.com (8.16.1.2/8.16.1.2) with SMTP id 23QF6Us4037859; Tue, 26 Apr 2022 15:06:40 GMT Received: from nam12-dm6-obe.outbound.protection.outlook.com (mail-dm6nam12lp2176.outbound.protection.outlook.com [104.47.59.176]) by iadpaimrmta01.imrmtpd1.prodappiadaev1.oraclevcn.com with ESMTP id 3fp5yjktje-14 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Tue, 26 Apr 2022 15:06:40 +0000 ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=hC7sEo0zKj2CnfpRheawOVEYrQHyDhrODeqc3+tAyEuOWPCOtHzu4uuGe/f465b0J4+mSrbCVkdvSfs90Sv2PjjrFBoZSvOWXbV66+wlreYP6Prvwiq0T4+SjsveqlkvHaasxkwPKP8U6E/g6Qr0DUAwYdUdSrTBphogLpqk4wFBVcgd2B72CwsuyqV5lDm/CVwUwfo2ahvRokKLGFK1cpm2C0mK6hIQuprdvutb3SbgazmXyyr0VaHdw2CfG14YJH7wst5VCfTaPw++oiiC7aUwPlOwuI9xjeeMWYhpjfQWxFSKn6erAOpqwRD3pd/0sH4wzuajFuMg7Auch4axNw== 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=Ogt+c3oWhWfK2AtETrybCdUXg5TkjjhP8U5EGNjpxXw=; b=BCd+lMXQ02qORZzd3nXzmOlGhNHweXihKjGUzbudEmvE8cb9NxH1RLkbTumaReoGOu8FFFOzMgZzmu2rBbTRSwm/VmUKuexVC+aSfhnpSoCMpd/wB0YjYZsB3+DUQEhg8V7+1Vu6dXZNMTVUTsXXdVwfB5EqeWKvKfXe6ujfTX+6IwnUEVXPbBqw1PZ/57kWdFAz46LrSXeAVb/CdK8/Y39l6iGW1FJ/bzl3di27qMbnIF256XNCYwJ5VwOtPP27k2oY9ZVffIvlEv56Lz6GlguJHX+Di7thqlu+NEAyBhohmKMhyyejkcMiXSQiWrCa69bF7N/F2ESibAu4UT8Dng== 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=Ogt+c3oWhWfK2AtETrybCdUXg5TkjjhP8U5EGNjpxXw=; b=Bs2NMo9BBffF2GEw+pkfqXFC0STJPu13jfOuOjDdYIu7YrzIsvX8SU5WkSK+UYUM2XK3tizRSl/uIanyPvpqEUMSATLsdnUjWngpZNQYi5BDDWd9rzFuJbVitFxI4Z5P10hEUoNzDy+ruz76P4yLgD51JNPzCHVF9VH+7j8QPaY= Received: from SN6PR10MB3022.namprd10.prod.outlook.com (2603:10b6:805:d8::25) by PH0PR10MB4679.namprd10.prod.outlook.com (2603:10b6:510:3c::15) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.5186.14; Tue, 26 Apr 2022 15:06:36 +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.5186.021; Tue, 26 Apr 2022 15:06:36 +0000 From: Liam Howlett To: "maple-tree@lists.infradead.org" , "linux-mm@kvack.org" , "linux-kernel@vger.kernel.org" , Andrew Morton , Yu Zhao Subject: [PATCH v8 24/70] mm: use maple tree operations for find_vma_intersection() Thread-Topic: [PATCH v8 24/70] mm: use maple tree operations for find_vma_intersection() Thread-Index: AQHYWX85+liBUYsmTEWbnS7c8IL3+w== Date: Tue, 26 Apr 2022 15:06:36 +0000 Message-ID: <20220426150616.3937571-25-Liam.Howlett@oracle.com> References: <20220426150616.3937571-1-Liam.Howlett@oracle.com> In-Reply-To: <20220426150616.3937571-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: f8cf3af6-fbde-42ba-c961-08da27965be6 x-ms-traffictypediagnostic: PH0PR10MB4679: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: 6hkxYRLF4he/9BJGr3w/gpUeGbngBWmBexn8lWrGU2STAt85j8Q34W68zATZg3hItyrk4Mm7vhO3O/hZIYWg5k3JY7FX8fSmD0DBdjM4ErrIAYg9ryzw6VB5u9Cifn0s2UCic8/djerjlxG/Lq83ZyAjXk9X0IUGFoQCDKLQwAsmlrC4prglowFx6VxCO2DHkOWVDh5BqWcbEQG+LjwxutuETXDEITwFneuZDpUJe8mNGwdw7B3VCJc5AvGmnR46J3xDZjFaB6xgzH4X8yYKy0rP7l/v1n96eUjD+irshRKu3hiwmw6mv/NzUU/nYF+joeBFbxnLHbPm/U75Vt/X0BzTPX0N2j2rsCASxAc/ayV12fgR4hFMnLso/1EE95EOX4L/yz2litKbYtkHYgmUftzxk8gF+COeg6nq1ubJJJAaEwVPBP85j/ejF0Z3vFtwnKkB5mOyM5SXtpNYWocFTxzQBykTT4Mi/svzpAkmpXzXrCxnsi8wk2cvKoaU4CQeLnk0GRmOpV0vK7ayPZ3oxfiGVmywIMI6/lZLXNlCC2hwCqClXg4xmyXukKAuFz9W0PMkCI3mKOgq6pnP1oBw2eoRuPcqqUURVvGC6QqIPu6X6hhfsyNt3gOK0deehV+wyKuCwCDuhmYcz5d7mtnU9DyrytIDH8NsTe9vktf4OHl53IXBNUOCeK1txa+BRxgZQptJglu7H/QvaTTKWfZWXA== 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)(5660300002)(66476007)(38070700005)(316002)(2616005)(122000001)(38100700002)(83380400001)(2906002)(66556008)(76116006)(66946007)(66446008)(64756008)(91956017)(8936002)(44832011)(6512007)(186003)(26005)(1076003)(71200400001)(110136005)(6506007)(6486002)(508600001)(36756003)(8676002);DIR:OUT;SFP:1101; x-ms-exchange-antispam-messagedata-chunkcount: 1 x-ms-exchange-antispam-messagedata-0: =?iso-8859-1?Q?DUMpvqmAAvHHFaql8uGLq8lqdmi31+o6vKA462phPuIPjaDWVhYWk6toDO?= =?iso-8859-1?Q?cLqTiZKeTugiR90Als561RzluteRS77H3rS++HsPNLMTXZfpxXvF426pJc?= =?iso-8859-1?Q?I4BXlkqb1XvZMnSBYbWKZupkG9YSAmh2CyFjNLFUKc9yDD9atmE2krW+PJ?= =?iso-8859-1?Q?jY4pjcKHXAQ9pysqBRj3D9QWAHfn9qcAygH/RBiJuEpkZ2rV3HUS+9XG25?= =?iso-8859-1?Q?hwHBDx4VD3iqncY15M32AqojDzDl20vvqqccumLUV/Qop12Dt/+SpQFNlL?= =?iso-8859-1?Q?JAD5jJbR6ZUIqm+Cfw8SHNRAnP5ubG/EMZs/NPPiPuHDEuvnj0sBbcwwtk?= =?iso-8859-1?Q?6IJyMWJBlv+K5Bsy76HBYgfQRIWgEFH8lEBgH4LTggpulnX0d4023ho8bl?= =?iso-8859-1?Q?DWZI5fxT8nUKRn7uiY08Ug5yjaPoIvSegtyJ3ttj8M5zHDqL8gCnCXTSXH?= =?iso-8859-1?Q?37TL8DONhPjMuHHyzZ3iXe/FjjBvCa5/jHbLxfPw6STuGb7GdQhyy6BxKQ?= =?iso-8859-1?Q?2Zc0SXEPL8FSTpa8o4KFtU5j7Dm5ml97sKYjqxWbKqfNJsu/4EmU8fpykF?= =?iso-8859-1?Q?wwCGWis3myajrAIs6w0G5LkA8i3pAWkb3Bj3b8G0Bxd51bSO4jCiGJq4V+?= =?iso-8859-1?Q?F9/wmrrqovzRtb4ywVTu4jbIz1HjRb/xBkYRGyDkha6QvHbwkrk2XrNllG?= =?iso-8859-1?Q?PXbVf0re/quceUwobnQv3SOakTD7SiKBSpP1s+XnDruyKbP2LP606HiOsl?= =?iso-8859-1?Q?kGsrTytC++l5+XxCKb1Vixq3v/OV1fA7EW4DxHZiNV2TTT0tIS4WFsF9Ti?= =?iso-8859-1?Q?kQSJNm+2rrJ2QXqfO5rWSlX0+neoT3UE67aBS9rF/4HwyTnsX2io/uA/7l?= =?iso-8859-1?Q?OAPGgtiCuDZAT/6o6v/3IQglUx1DrZKG1EIsU3l1xQkkBMGhPMe05LEWas?= =?iso-8859-1?Q?XAmzJSPz0JaSH62SxTX31h59n5fZ+P7g5Xw9IplvcJMiuG6qyrlaGzIuOL?= =?iso-8859-1?Q?2Yk4/ipNHY6/eqpuUJsTMyEbjb57DT/b2eJu9QyekCXIWLr9sbWDDS5E9q?= =?iso-8859-1?Q?quNClxUsn6ceBBcSDnht7Bch1tici/FwKtcfQHpNnlqKaYyO2oRrkmEkli?= =?iso-8859-1?Q?zk8gfysmYBpNNTY7br/mmU5mWNyP4IOJ2bx5GlmBlUn4rSn7xBNPf5wNgk?= =?iso-8859-1?Q?laCZWByMP5/cqeTyHWpIJqf7Eu8vPvLqwMs0BWvojZad4xGWmgtXYBEGay?= =?iso-8859-1?Q?BojPc/+ur/xhpMbQ4KmNsonz5+c1BLYMOpViHJLywuiYTBxgIth3qx5yLO?= =?iso-8859-1?Q?V4jcMGffHw5zaOKtGUEpIGFtSNKa7x0DgJOmQ+EvNCgD9dIohUUyqsXPP/?= =?iso-8859-1?Q?ewV2cCMuh+SPCvFJymy5RAjuaVVc+hCDNs5EF2FPM8s/3XCvrfdrPHamnR?= =?iso-8859-1?Q?M5ZVxve2KsEDAmg+ELNYmLMQz835nRLLQGjxiQdOGe62S4O5SjovXHw8yt?= =?iso-8859-1?Q?CF8cvH0opyHJ0/uHqdElrzMXQpCaYdXfByClJ4plvBAr+8qK85CH24Fb1k?= =?iso-8859-1?Q?24D3pLv/YYcdRr88jf1eG0kizIpAi9LyH5gYDIin212ee4buPTvKawUxBc?= =?iso-8859-1?Q?8C54N1JD7AgLCC5PfbtYXWdDvXQrFd2lzXJ8gsEorCjbSKgq9gRICVvnDG?= =?iso-8859-1?Q?3fQ12UpWIROhtQNjh+EBpigtpN3PH+u9A0bNvH6iXfBLi1uxdlE3oDHcYR?= =?iso-8859-1?Q?nI48boC7L5YEG2GaX60u/64gAfLI+EbA5MmDRaf5SauBgbkcqCRcy1oXIm?= =?iso-8859-1?Q?rPiH2u24Kgg2eiP5lu9gvNgHttCwMVI=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: f8cf3af6-fbde-42ba-c961-08da27965be6 X-MS-Exchange-CrossTenant-originalarrivaltime: 26 Apr 2022 15:06:36.0994 (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: HmnDjVvixEodmKBTwpMXPfod5F7M+eNtkwnQqN1B/yMn3JZLIQ3+P4pMnOsv8h/MBzhi2+JKMvlSfZ2sJ9jTEg== X-MS-Exchange-Transport-CrossTenantHeadersStamped: PH0PR10MB4679 X-Proofpoint-Virus-Version: vendor=fsecure engine=2.50.10434:6.0.486,18.0.858 definitions=2022-04-26_04:2022-04-26,2022-04-26 signatures=0 X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 phishscore=0 mlxlogscore=999 mlxscore=0 suspectscore=0 malwarescore=0 spamscore=0 adultscore=0 bulkscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2202240000 definitions=main-2204260096 X-Proofpoint-ORIG-GUID: 6_feak1aBjSnylnxGHYG4k3CpoDDt4l7 X-Proofpoint-GUID: 6_feak1aBjSnylnxGHYG4k3CpoDDt4l7 X-Rspamd-Server: rspam10 X-Rspamd-Queue-Id: 39F6D180062 Authentication-Results: imf24.hostedemail.com; dkim=pass header.d=oracle.com header.s=corp-2021-07-09 header.b="U+/S5lDz"; dkim=pass header.d=oracle.onmicrosoft.com header.s=selector2-oracle-onmicrosoft-com header.b=Bs2NMo9B; spf=none (imf24.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: snw3a11upyfkkx88a9hnjrjz1dkt8nr8 X-HE-Tag: 1650985602-770721 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 02bd4390ca7b..9d0d76c410e7 100644 --- a/include/linux/mm.h +++ b/include/linux/mm.h @@ -2785,26 +2785,12 @@ extern struct vm_area_struct * find_vma(struct mm_s= truct * mm, unsigned long add extern struct vm_area_struct * find_vma_prev(struct mm_struct * mm, unsign= ed long addr, struct vm_area_struct **pprev); =20 -/** - * find_vma_intersection() - Look up the first VMA which intersects the in= terval - * @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. Ass= umes - * start_addr < end_addr. +/* + * Look up the first VMA which intersects the interval [start_addr, end_ad= dr) + * 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 =3D find_vma(mm, start_addr); - - if (vma && end_addr <=3D vma->vm_start) - vma =3D NULL; - return vma; -} + unsigned long start_addr, unsigned long end_addr); =20 /** * vma_lookup() - Find a VMA at a specific address diff --git a/mm/mmap.c b/mm/mmap.c index aeefa2c7962f..843fddce316f 100644 --- a/mm/mmap.c +++ b/mm/mmap.c @@ -2061,6 +2061,35 @@ get_unmapped_area(struct file *file, unsigned long a= ddr, unsigned long len, =20 EXPORT_SYMBOL(get_unmapped_area); =20 +/** + * find_vma_intersection() - Look up the first VMA which intersects the in= terval + * @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. Ass= umes + * 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 =3D start_addr; + + mmap_assert_locked(mm); + /* Check the cache first. */ + vma =3D vmacache_find(mm, start_addr); + if (likely(vma)) + return vma; + + vma =3D 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 9b8c033ef997..7d8f756f13f3 100644 --- a/mm/nommu.c +++ b/mm/nommu.c @@ -627,6 +627,17 @@ static void delete_vma(struct mm_struct *mm, struct vm= _area_struct *vma) vm_area_free(vma); } =20 +struct vm_area_struct *find_vma_intersection(struct mm_struct *mm, + unsigned long start_addr, + unsigned long end_addr) +{ + unsigned long index =3D 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 --=20 2.35.1