From patchwork Wed Dec 1 14:29:59 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "Liam R. Howlett" X-Patchwork-Id: 12650065 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 5F74CC433F5 for ; Wed, 1 Dec 2021 14:46:10 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 691256B00A1; Wed, 1 Dec 2021 09:31:58 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id 63FEE6B00A2; Wed, 1 Dec 2021 09:31:58 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 46B7A6B00A3; Wed, 1 Dec 2021 09:31:58 -0500 (EST) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (relay025.a.hostedemail.com [64.99.140.25]) by kanga.kvack.org (Postfix) with ESMTP id 3593F6B00A1 for ; Wed, 1 Dec 2021 09:31:58 -0500 (EST) Received: from smtpin01.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay10.hostedemail.com (Postfix) with ESMTP id 9B8F41D29 for ; Wed, 1 Dec 2021 14:31:34 +0000 (UTC) X-FDA: 78869463708.01.44B7341 Received: from mx0a-00069f02.pphosted.com (mx0a-00069f02.pphosted.com [205.220.165.32]) by imf11.hostedemail.com (Postfix) with ESMTP id 679A1F00022C for ; Wed, 1 Dec 2021 14:30:29 +0000 (UTC) Received: from pps.filterd (m0246617.ppops.net [127.0.0.1]) by mx0b-00069f02.pphosted.com (8.16.1.2/8.16.1.2) with SMTP id 1B1Dw8qB002530; Wed, 1 Dec 2021 14:30:20 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-2021-07-09; bh=64Z4ME7fJjPoD5h1H7e+s6g1NWj6gAX3LbvHkPcAr3I=; b=T8dqjoEbWTYSZ4+XWu367elISzLRDaNL7g9Gn/VQNtnTUAjj+TxzsUBcCDBP3bFPBPxV FANgLBI55fgpl5LlQUX7Sdz94SgkIvAOx49mV/J3tG28/XlAfYGMq4Zw5GhCRkMk+7SD 9H8iIMNzYF+IARt5IqK8zAS0uWQ0znw+dVyCbsDVY+YTZHrji+/lkQWihQ/ZJrJJSOSj 0+Ep3q8koTnkgfDdc9PRGTNyRYwyO6ZvOMASC3EP8txjJg/EWLeBk7TePqCzBAymvqlW Ojid70CDDlC3ER3PQHkUs57IrsII0D1yBBuq3V0x8IGQwNo0TIjb44zY52g/PBZllOzF uA== Received: from userp3020.oracle.com (userp3020.oracle.com [156.151.31.79]) by mx0b-00069f02.pphosted.com with ESMTP id 3cmvmx21ts-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Wed, 01 Dec 2021 14:30:18 +0000 Received: from pps.filterd (userp3020.oracle.com [127.0.0.1]) by userp3020.oracle.com (8.16.1.2/8.16.1.2) with SMTP id 1B1EAL58032122; Wed, 1 Dec 2021 14:30:03 GMT Received: from nam11-bn8-obe.outbound.protection.outlook.com (mail-bn8nam11lp2169.outbound.protection.outlook.com [104.47.58.169]) by userp3020.oracle.com with ESMTP id 3cke4rv42p-2 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Wed, 01 Dec 2021 14:30:03 +0000 ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=dlSyG8s+Jny2O2pzppzwrKO+t+Vf0VAgVDIVLglAQTkrS9204kRIAmqi/+vOsGy0DQAeig13hdCMPimTXhibld3OA2Ur/0Ucshfy23XRJyceTiaUhKgoQ1gPmh4tVIvcV7CXSiPbmWPG/BERsN5hUi4GhWT6OaX++zLWyxWkWeeSyBTmkFyYX0qYfej+UGXfZa+ytrl3K3VEvEv4yVlefzcf0C2SUyNXl25HPl/ultCj1TePJZR+QZ+GXo/8UkeuVQNTyyLt7nyA6fDlGONFb6VrK74OjjA5rJDcwkFBndcdkHrY6yz6L/xFBcnHVQbnNhFHGfJcrMKw+6OTqIz6Vg== 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=64Z4ME7fJjPoD5h1H7e+s6g1NWj6gAX3LbvHkPcAr3I=; b=d8VWVC/C9fMvd/3uitTYhF4olkMyJPa0W0N/pG+hfA2Ba+0RlBqpW9Dp0DM91hKnjWZum0E7G8jT+BC73oCjp1XHzVwdRVYi6/dOx8CTw/9sfioZFwZgwDidf/vhrIqUCS/2HShBusNk40YF+Ueney/SKNaR7bdA5t+A4q0/JvybXi0E2e2SrOQpi/B9ka4WMcIELpf0VyjHKm38JlaYK83AKWPChnFr4F+FK9Se9m6XMoiYNNxWDXD3CaPiLtO9eeiEHTqWAfdGUdtb6h5OSMsZHUccBzDIXFx8gwNEw4yILx4ESjtxkghjc4PRJOgeuFmegUrd1uVpV7iKUHjgvw== 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=64Z4ME7fJjPoD5h1H7e+s6g1NWj6gAX3LbvHkPcAr3I=; b=Ln2kz4lQfhSeichIRJclqAAJK07mHLGNg/cWpdy5+QKAZQe5toliCbz9c8XmUACUnpt18sd2FO0tgYHabO5OwNMMbw18Iq8DL8f1huq5ILMIvbK1kku4QCEPAHFYTLeOK+RN3vNVeFHBvs2PQ7fNYr2QPKCf8R5h1wRjeDwtrFY= Received: from SN6PR10MB3022.namprd10.prod.outlook.com (2603:10b6:805:d8::25) by SN6PR10MB3021.namprd10.prod.outlook.com (2603:10b6:805:cc::19) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.4755.11; Wed, 1 Dec 2021 14:29:59 +0000 Received: from SN6PR10MB3022.namprd10.prod.outlook.com ([fe80::c4d0:8291:84d:ac66]) by SN6PR10MB3022.namprd10.prod.outlook.com ([fe80::c4d0:8291:84d:ac66%7]) with mapi id 15.20.4734.027; Wed, 1 Dec 2021 14:29:59 +0000 From: Liam Howlett To: "maple-tree@lists.infradead.org" , "linux-mm@kvack.org" , "linux-kernel@vger.kernel.org" , Andrew Morton CC: Song Liu , Davidlohr Bueso , "Paul E . McKenney" , Matthew Wilcox , Laurent Dufour , David Rientjes , Axel Rasmussen , Suren Baghdasaryan , Vlastimil Babka , Rik van Riel , Peter Zijlstra , Michel Lespinasse , Jerome Glisse , Minchan Kim , Joel Fernandes , Rom Lemarchand , Liam Howlett Subject: [PATCH v4 22/66] mm: Use maple tree operations for find_vma_intersection() and find_vma() Thread-Topic: [PATCH v4 22/66] mm: Use maple tree operations for find_vma_intersection() and find_vma() Thread-Index: AQHX5r/rmzhEuZidmEqFF4ul+BVT5A== Date: Wed, 1 Dec 2021 14:29:59 +0000 Message-ID: <20211201142918.921493-23-Liam.Howlett@oracle.com> References: <20211201142918.921493-1-Liam.Howlett@oracle.com> In-Reply-To: <20211201142918.921493-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.30.2 x-ms-publictraffictype: Email x-ms-office365-filtering-correlation-id: aaf52e87-e80e-4108-b1d3-08d9b4d70e16 x-ms-traffictypediagnostic: SN6PR10MB3021: x-microsoft-antispam-prvs: x-ms-oob-tlc-oobclassifiers: OLM:7219; x-ms-exchange-senderadcheck: 1 x-ms-exchange-antispam-relay: 0 x-microsoft-antispam: BCL:0; x-microsoft-antispam-message-info: nEDA/eO/sO0GS74JzDUPyOoKcFYghOmFwTD+uVFzCIsENRbeUjz1UE5ItxafX4xDo0gKpKj5iVe+uXF0g0RrydwQPPZiri5ycnaDCCASuK/gHENT6RoFjZSyDEonkbYiHQmVrXayOA448tmB5mykrxGmlpg+aI9hx82enGjtkjEuyCJ4/xfNn84rHXcLALjRfAM7e7MNwBr/aCxW8D/UdMO2jsl76mUP1qRnFNQoLg0hPQJB0+k8WalA4L5U1wnzlXkooed/Iuj6poYwnQXNCqIbD4G/nRhxqx0qREwo7fi4hZoEmrWwE+utRPGxPpGd71P5V+1czjSFUo6LQ8HiAsSFw/B7Tv5njWDLiJMCfw5WpFZSj5swYzfFRCjgZoqtJ6hidFYln7jyt/f6ionIGMv2o8ymB/Q1Mzg0dtKwnOcOo8ohVlV3EU6kysrGObTr0uSebp+eflduaxmR5L/61ie8XZRyJ2pqUHSY9EDzLqNLS+QoN0cMhI9XdHMI8jhy5YoJ2FLL0/fbR1U8tLLH84ue8OPKRZjsn+VdYOytgwbfXLzjyEqX3X2DvShMYQbdf8+yqpfRmvIxa97Zl5NorxAIuE1fcVIk9Q+zfMNxy5jisanp61QpSVDYq7QZMWVjB36WkdhiF/m511VnSPMWuEBAb6HYuNbeUrzNH3HB7vBNgYGrzVRxnTvLJKHltZpTab1ZiWwNAl8FImMaWlxdPw== 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:(366004)(66556008)(7416002)(38100700002)(107886003)(38070700005)(316002)(66446008)(76116006)(64756008)(66476007)(2616005)(122000001)(83380400001)(2906002)(6512007)(91956017)(508600001)(66946007)(71200400001)(8936002)(54906003)(186003)(86362001)(44832011)(4326008)(6486002)(6506007)(5660300002)(36756003)(8676002)(110136005)(26005)(1076003);DIR:OUT;SFP:1101; x-ms-exchange-antispam-messagedata-chunkcount: 1 x-ms-exchange-antispam-messagedata-0: =?iso-8859-1?q?vlGr+5hYQGoblLXhFe9gJPi?= =?iso-8859-1?q?WE8IVTsIhbCLvRXfpKDwR0hxw0whxvbyoBuvC2Hz2Ywjf7yqZJSO3iK5cQS0?= =?iso-8859-1?q?Knyvago45GLrxCO4Wt6isxweVpli0dKy2Um67fi8eweBdsMvt9A0RARp+Fv/?= =?iso-8859-1?q?WkQ0tg6CE6nfOQvzfZEcHYWcxku7oYwmlqwkXNckmwuCBy96HguvG/wjEPsF?= =?iso-8859-1?q?Z+/8T6dghooTtrL9OKK9CESrlGMy4CpUyc5OtHlGHqiLE2f119glHfqhGmDL?= =?iso-8859-1?q?Z66HouqF4oMhb+7+4nvD9LAsVndvfHlG4ngSDfJAHTM2cy2aA8mLcA+QT7dC?= =?iso-8859-1?q?+EE0pTWFokvgq6AdPWctFRNgoxwztq0HF9UbpBdhPRsoUM/P/5LEHgN3IuxR?= =?iso-8859-1?q?Vc7EqQedwaSeNai9yzsN9VTISnfyx93CfbG5tz7t6Ipbye6BfQWQWQviEc7G?= =?iso-8859-1?q?zZKxUWiOQhHfhuFw/VIuBij239sCW3dt3zEtmOyGoYtlRxh1nnXlk66fftr0?= =?iso-8859-1?q?OTiKm/URCZHOulpV7bSA8YqtTr5JMG1d0MCrLz8AUJYuhVodYBQDaocfisui?= =?iso-8859-1?q?Xt1Ube7moNFX5g6PM1WqjkKhRlbMwmUmSj1YijYCGeIJn0EZh50HpQ5m9Cww?= =?iso-8859-1?q?BFNaKAZMZ9S3/hepYrt+msG5a1Fglxm5FQqIanQFiWF1hgLKk69yqOq8YX6H?= =?iso-8859-1?q?M4jgh+hu5H5OHjkOC//cbX/ayGUtNMq0ENgI3RStIu44usSrtJtl+/vAv3hM?= =?iso-8859-1?q?ZI5pbZzCuUUlYxi2KE2UQMqe42E/E3sskL2KmpIM8D3TtZ3iTY4JIllgBWrt?= =?iso-8859-1?q?DJsAoHs1sDw8nVndAE7nLjBPr6+lssBpkoRhIDJv9YvLWPjQVpjCFHNRjppc?= =?iso-8859-1?q?2/N3Bp1hInPkHwiXVe6eUYXrk+V9Bp/5VYEZoTC9OeMJitufzvP9JxWab4GW?= =?iso-8859-1?q?ZMki4JEmyqgAyfsbrPeaZQP0VSZlKtoOfaH5v7/S89k+RbCKxYUWlFX57/xz?= =?iso-8859-1?q?x9TRdNYg3BJXPKfLBdtbNLwG+yncs2nC/ySPEA/8DOQCKKtdUAhTsUrYbx8l?= =?iso-8859-1?q?iQ0BBqqtvOvuDOy7FLKFDJlI0mrTCJUBdmW0/6j0KK5YOyB31aTNBnfaoVTa?= =?iso-8859-1?q?i4lh4Ms3afhCubqPOMfTQGehSoIscZmI4dTlzLO6vO29w5n7y7oHsZqxSdBY?= =?iso-8859-1?q?Tf2WE9MhI8jTP7RfiFi7QpwRgpPG8NhBCV4pxuTFsgvmnamWZly0fM7pWTmJ?= =?iso-8859-1?q?7A5eR+h28xpJodUAR3ni0YAJYx84ijmxj5H9BlZft9UutWscB2+mvRE2IXX0?= =?iso-8859-1?q?l++wjVHShoQt0la9Z5wyv4s5cOP+l7fbjF1NjWw1O5A1jCgmXUEjQTDaRcQQ?= =?iso-8859-1?q?2AaWI2rHqhzBblNzwWrQmYDPQZUAxcpBHOvMgxhegYvOnL80WpWhib7kjH3c?= =?iso-8859-1?q?CycevM//Riyei4VHTqrATMG88np4Z44Jefb1s+jZQ/DnNoH6D9ULJJ9AmXu6?= =?iso-8859-1?q?KbY76sjv8pe89EkiXTDkDIHSlLO0dJKwAjhYQ2uK3tcgHu/J2rot5Bjz0ufA?= =?iso-8859-1?q?c+AQX/b8i6cf6vV3+zpZCrKvUUg5wPx+kRVP4wBpuRdAU5Hn5j90LRDfTPLn?= =?iso-8859-1?q?I4PrfVLXfXhWrN4ndfblvDhtY6Lsa3u4yV/tg8kg+5JJsihO/aGPgzqF9Lr0?= =?iso-8859-1?q?=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: aaf52e87-e80e-4108-b1d3-08d9b4d70e16 X-MS-Exchange-CrossTenant-originalarrivaltime: 01 Dec 2021 14:29:59.5943 (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: QHrbjCam8hhMejK7rRljclwuHm0cFYuBq3c98LcKCaeuwRMY09lcRCRQsRCp/8TKRM/N63E/ebNHD92c7bQUtQ== X-MS-Exchange-Transport-CrossTenantHeadersStamped: SN6PR10MB3021 X-Proofpoint-Virus-Version: vendor=nai engine=6300 definitions=10184 signatures=668683 X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 malwarescore=0 mlxlogscore=999 phishscore=0 suspectscore=0 spamscore=0 adultscore=0 mlxscore=0 bulkscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2110150000 definitions=main-2112010081 X-Proofpoint-ORIG-GUID: s2GLre4LqD1X8iaWN1VXoGTiPiRV-Ec8 X-Proofpoint-GUID: s2GLre4LqD1X8iaWN1VXoGTiPiRV-Ec8 X-Rspamd-Server: rspam08 X-Rspamd-Queue-Id: 679A1F00022C X-Stat-Signature: 6ess6i16zirg3uorwizd9ahhna3fnfye Authentication-Results: imf11.hostedemail.com; dkim=pass header.d=oracle.com header.s=corp-2021-07-09 header.b=T8dqjoEb; dkim=pass header.d=oracle.onmicrosoft.com header.s=selector2-oracle-onmicrosoft-com header.b=Ln2kz4lQ; dmarc=pass (policy=none) header.from=oracle.com; spf=none (imf11.hostedemail.com: domain of liam.howlett@oracle.com has no SPF policy when checking 205.220.165.32) smtp.mailfrom=liam.howlett@oracle.com X-HE-Tag: 1638369029-620742 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. This means the find_vma() call changes to a special case of the find_vma_intersection(). Exported for kvm module. Signed-off-by: Liam R. Howlett --- include/linux/mm.h | 25 ++++++------------------- mm/mmap.c | 38 ++++++++++++++++++++++++++++---------- 2 files changed, 34 insertions(+), 29 deletions(-) diff --git a/include/linux/mm.h b/include/linux/mm.h index c08f6d541b8a..39a947f29f6d 100644 --- a/include/linux/mm.h +++ b/include/linux/mm.h @@ -2812,26 +2812,13 @@ 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; -} +extern struct vm_area_struct *find_vma_intersection(struct mm_struct *mm, + 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 e4c8ce377f2c..c06c5b850e1e 100644 --- a/mm/mmap.c +++ b/mm/mmap.c @@ -2003,29 +2003,47 @@ get_unmapped_area(struct file *file, unsigned long addr, unsigned long len, EXPORT_SYMBOL(get_unmapped_area); /** - * find_vma() - Find the VMA for a given address, or the next vma. - * @mm: The mm_struct to check - * @addr: The address + * 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 VMA associated with addr, or the next vma. - * May return %NULL in the case of no vma at addr or above. + * Returns: The first VMA within the provided range, %NULL otherwise. Assumes + * start_addr < end_addr. */ -struct vm_area_struct *find_vma(struct mm_struct *mm, unsigned long 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; - MA_STATE(mas, &mm->mm_mt, addr, addr); + MA_STATE(mas, &mm->mm_mt, start_addr, start_addr); mmap_assert_locked(mm); /* Check the cache first. */ - vma = vmacache_find(mm, addr); + vma = vmacache_find(mm, start_addr); if (likely(vma)) return vma; - vma = mas_find(&mas, -1); + vma = mas_find(&mas, end_addr - 1); if (vma) - vmacache_update(addr, vma); + vmacache_update(mas.index, 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 + * @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. + */ +inline struct vm_area_struct *find_vma(struct mm_struct *mm, unsigned long addr) +{ + // Note find_vma_intersection will decrease 0 to underflow to ULONG_MAX + return find_vma_intersection(mm, addr, 0); +} EXPORT_SYMBOL(find_vma); /**