From patchwork Wed May 4 01:12:26 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: 12836629 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 E84DFC433EF for ; Wed, 4 May 2022 01:12:35 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 50F3A6B0071; Tue, 3 May 2022 21:12:35 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 4BE506B0075; Tue, 3 May 2022 21:12:35 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 2E9CF6B0078; Tue, 3 May 2022 21:12:35 -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 1F36C6B0071 for ; Tue, 3 May 2022 21:12:35 -0400 (EDT) Received: from smtpin31.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay07.hostedemail.com (Postfix) with ESMTP id DB2F020499 for ; Wed, 4 May 2022 01:12:33 +0000 (UTC) X-FDA: 79426285386.31.19EDDF9 Received: from mx0b-00069f02.pphosted.com (mx0b-00069f02.pphosted.com [205.220.177.32]) by imf20.hostedemail.com (Postfix) with ESMTP id 8B0681C0094 for ; Wed, 4 May 2022 01:12:26 +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 243KctEm024988; Wed, 4 May 2022 01:12:28 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=wMnXYZ6ilXCCmNJwmRifegQ+iz/dSmHFhbRUOQ2lNXg=; b=BFSRW9wEgqnVVu/t0IDQWGUBa0GmdZTfO7Ev0j0ng+bdcJiAyQX7seAv1zlIPxzW1aVn Vt5SogMtCFrrP3nvfzZszBDynIipblkxtXYyx4Z7O7PhuDxzLv0R4+eu4lBYFHkLUFi9 +978JFc+Q9RIaDvszeExWSrVVbTBZE0uHtbSZZV5TP4pvP1UgUHTc4o+oH5yyhje1A0l txMQMUjnXFOOZ8jM02o3W6S0AQ/DmvNubi6Ctm/8kCtUf4oKm5Bgev01cz16ahxZFLuT LsR+CNLGDetUgSEXsb3SMc53EHQWOp/0nSinHgnxlhHGhGJFVlcTZ4x/QFSmrbOff2OC Uw== Received: from iadpaimrmta01.imrmtpd1.prodappiadaev1.oraclevcn.com (iadpaimrmta01.appoci.oracle.com [130.35.100.223]) by mx0b-00069f02.pphosted.com (PPS) with ESMTPS id 3fruw2f6a9-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Wed, 04 May 2022 01:12:28 +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 2441As5n020085; Wed, 4 May 2022 01:12:28 GMT Received: from nam10-bn7-obe.outbound.protection.outlook.com (mail-bn7nam10lp2107.outbound.protection.outlook.com [104.47.70.107]) by iadpaimrmta01.imrmtpd1.prodappiadaev1.oraclevcn.com with ESMTP id 3fruj9223a-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Wed, 04 May 2022 01:12:27 +0000 ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=FV02A98bHCXj/GCk331MgxzerwEX9mltNwHxyEC1XOP+wZbbq1l86KRBHmEivjqAKyRWElv2sNsrb0lDNHcwtPny7h3CecKjEoufZE3LH0CHo5WdQbI741/aKYu/65PEJAU0zhXBOmaqjvVSXDPtYgAC+X1yqyHTUyhGpIYcyKAGTCpwMWHSC8RL4E8v6c0ey9p5HfEYbQgMHrbRJgLUqFXg0GOWE5Q6V2DUh379MNGLA33O6mBHOgwiCpq3UhhA9DTqfq1b9TFXGyeZQXhQM4yn14CK5jrkneabUdZL5Wcsq4Csb1UhNZkap/Ry5xmcLeLcgtK/sClZWgBPo8/bfQ== 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=wMnXYZ6ilXCCmNJwmRifegQ+iz/dSmHFhbRUOQ2lNXg=; b=bc5j457y4jYDmSG7XhdCPHjEU9h5Zb02+4ADjJXVIhDhfS0h4FjmIYM5gvHpJ8v7duMMS+7Mnx7aphtfC/2ktCw3Z3EW2jZMFTbBYbrwsDitA+gJhTYkvvIcKIyy55P2/aStFLt6jX/zpugOO0tTXNeUeJ5ZIpXHHuPrSHlDCzUn9v5M8UOjQMkEcXPAo9TeFb+sqeOYpm1QqtyJbpHHeHHm0jUshBtg3tW3WrbUDB863lrzVaKEuT+C7POsmS9SLCXbYkQDW/u9Jm/6wCxxKJbs4DyNZELQziKaAATRSqmQCdvWbTiINuzS9DwwnOPmwVxqdQsPtFSuIr6RnHTPYA== 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=wMnXYZ6ilXCCmNJwmRifegQ+iz/dSmHFhbRUOQ2lNXg=; b=MVEMXXHaCjw9iayVJ5TTtXfCOPya5DiJTjs7Q3DBagG3Xl5EoSWIa4kEs36KNskcTabJeJ1hXzv3AZFWCfJX//JT/2ue/v1vzYWQeYT87XGO5qxdUG4ZSDXDGxLPT1+Wigw5O6C83EJaHV87FbTvSl4DzX49/mTpaeQq9SJLLkA= 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:12:26 +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:12:26 +0000 From: Liam Howlett To: "maple-tree@lists.infradead.org" , "linux-mm@kvack.org" , "linux-kernel@vger.kernel.org" , Andrew Morton , "damon@lists.linux.dev" , SeongJae Park Subject: [PATCH v9 15/69] damon: Convert __damon_va_three_regions to use the VMA iterator Thread-Topic: [PATCH v9 15/69] damon: Convert __damon_va_three_regions to use the VMA iterator Thread-Index: AQHYX1QE+HvcVvuhWk2ltHXx1nzXSg== Date: Wed, 4 May 2022 01:12:26 +0000 Message-ID: <20220504011215.661968-1-Liam.Howlett@oracle.com> References: <20220504002554.654642-1-Liam.Howlett@oracle.com> In-Reply-To: <20220504002554.654642-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: 3a9024bf-e8a2-4fa4-a46c-08da2d6b26cd 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: pgg1b/Sag2KxliTD+rmYG0L/GONovo2z9V7yZCz8ngyoORAO7UHktGsxA8g7J4pglnDLCyZpG4V1WWvdDSzZrv1tA+4l9PNyu7z82de9dCR9qigBc9ha6y7EAIdtHAHJoeu/QliJO3RlGU+ad+S1UJyehN4qtJMBovklcE1xttw2j8ymWhc0Xh4HU5k8lNk11oJ801RZ1Z4W/ucbbIXFM+UAvJMbMsf9HgPO5qLF1VIrSwjz87zJOpyn9oeIhLglYdm0LsV7hBS+QQaLzbgPTT2ck5GLCYTojXjoBU0NRj/IKmS3Lez1yOau3QK3xM1SAeZGJUDQEtGBg+E7IVr148dvsGFV43ff4B5LoPAYMoDGsG0KAwdoTOS6fEJgwJJNt8S4U/7clRbJJRion0yQqoXomOeWmaC6RobJU7m7bbVh3d6k3L4WgHoYNSwljXzffsMxi8NEaDWBaRg3MBQs6rSytmlC1pBTQlut4WQ+vwJ1AauQ6n9vP4HHbiP4RxMWMAu+hqx7lRKHs3c6eCYPcst6KMM8J38Dqa2U+m6q09/8kCql9L3wPt21FNTT+IPuzQOtrSNdCnn16xABqJLS53Qek2XLCzKtkFh2e6IptWgeS+YO1HVGGhTtP9XVjb1XWCxiabQ0DiCX1HFKcO7wN4TlrEnBSR4bpXZc1SlbnyOxFh/eWogsQy8uOWGszJfwZ0u9XDBoyMQ18OOxOgncSw== 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?/mD2xn3N0kFKerH7RPBlVX6?= =?iso-8859-1?q?XtmIn7IRqpXB3JPP/P8s0w0A+D8/73mHZlSZ+L9oE9jERdAXMRmQ12jbZjTK?= =?iso-8859-1?q?H8ma92Ac9J7cMpU/bLaQIbSi0tyubuMxj+QFJ2PH0xgamKHy/IGEGT3mY6a5?= =?iso-8859-1?q?aGi1M6kPixM5mFtGG6Wu9+TuTBXImOMG3h9DINdqreh8SZRHV8jeByprd8+h?= =?iso-8859-1?q?cdSo9pScqUieWZvIAafAmR3Ykxjo7iSHCLINYppkr4kwhGz2TRVgdUk/ESL4?= =?iso-8859-1?q?4HX0eqcRm6Fah+9OwDkO6sw93BYFm94UORdOOZvKruRvibYrCcJMODVZoExa?= =?iso-8859-1?q?fgd5dyOARPx+OBJGskKu1Gvk9zrVMkMUcUFUM/c0cqQF3jSVlaXYcOTEzkmY?= =?iso-8859-1?q?Dr1DW6+q/h+4XZwa4kDkMEHkx5h53QvzXFdUpFLtUNPdas4ToDGw8z+GhxzF?= =?iso-8859-1?q?U50+JmhL9ngRDEEQsfYzRuJDk71oxqBQm7XseLfQn9Vh0CVjIH4ieWkW7UoH?= =?iso-8859-1?q?jNzHBkLMxWRp4RkyQF5EfrQGyoVCrTyNoLHTPezw+wX9pTqvkMnEKgok6iGQ?= =?iso-8859-1?q?4UDUPCMbere3LQazD8QCbzoMof4OOsKF5xwsE+b1CB+cECLORP/vzqu7O0lG?= =?iso-8859-1?q?Mg0bzxZ+tTcHKTWgv0AKbHLz7dajRugoFoNX3+eehuZAMlDftAMQJkBT6vUg?= =?iso-8859-1?q?HyfDDBnXuMYWzdSV3kzPZ2ike9z88yTqsxf4g0992INBEmCNCrHQ9rW8GVE7?= =?iso-8859-1?q?QtZDgTzuo629FRuoU9JL9A0NmzAEuPE/6n7gJ6d/TdzNtNrzHmLegPbfVEm4?= =?iso-8859-1?q?RPTgu+fCZeYjSAZd70HZtJhyaHwcO3fmxzsxND+B87t9glzMVIGwjfZ+trX3?= =?iso-8859-1?q?3GfDq9f7JuX5qb41RxuwXnitmQyiCoKIrnMme/EQFEURQL06a7ru3COCLd7N?= =?iso-8859-1?q?iHG4vF3iHFtUHd88Offksb6HBsiTraGPJiD7Y4QbA43n1GRfZs3QOvgAMQW+?= =?iso-8859-1?q?+KIVuZF1kkM76GztRVAQKm99Ku3TrAPik/gGAizC360+i1EemioN1l36WASg?= =?iso-8859-1?q?Ps4BJNZEqAdZVZyQQW8edLC8SDjipWob2UpOSKEMYzlnIwoNAIfQ9VIZ0dbX?= =?iso-8859-1?q?5crqMEAB6QnelOzv8Z/r9jm/GO6d/HrnBaUhZpjoaWb11rPjEa9kaBoL4bqm?= =?iso-8859-1?q?aPSAAYzPsJ/VfT3ykLFAG2bNHFzbFLyGjNP8D39rcc+kcDPkTvDIKOJyNM9k?= =?iso-8859-1?q?tAw3417JPFuakXjKSAiiPtAFexS4q9+/GzYkOV8Jl7NxVO13NOvpTgKZzKUC?= =?iso-8859-1?q?JXor8se73KriKn8YxirrIIjDfhhWItfgL0qkDRHp9wtBXFBQhsQpZf6pb0t6?= =?iso-8859-1?q?keAj2Aa7tX5aX/pJOdvrMqn8S07RZaBWQfzpkit+42kZal1mDFQTfOfB59Pw?= =?iso-8859-1?q?XO6j09XxzVehqrPwfRHE2ZX61e7hN1DqpQ9SR+ny1Rb6a4NGM/C/BMUixJPw?= =?iso-8859-1?q?Pz53psPmpGeP6aYkk1rBghUVaP2a4zI/TFWryCL2rir2ikpHHeSkSd3cTfEH?= =?iso-8859-1?q?fk9pHnOeRUyMQIY6ZHCvjgJjZt5dySnuNHG/QnHkl/A6NcmCt3Bt7ev1IECw?= =?iso-8859-1?q?eUUotSxK6214hK10KfQsF6dSFdW4fjBUfTgYxrze08smGFyUvIiRsr1y9ZMK?= =?iso-8859-1?q?0XuCoMtGWtWa1XGaSovguokV/nrKqh9gOn8DQVKE/JVtxKN6MINILJg9caU9?= =?iso-8859-1?q?qWV6zQ7bWP+oR/UQN9MOQfP4557QsluwoJM2L362Ppq+belpvFqKcfIB1iU+?= =?iso-8859-1?q?I7SxtWUQ=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: 3a9024bf-e8a2-4fa4-a46c-08da2d6b26cd X-MS-Exchange-CrossTenant-originalarrivaltime: 04 May 2022 01:12:26.1795 (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: mdjtnHRLR4OkPoHsMzDNz5DqKLmeJKxAOL7mlWlx3LQKCW69MfthjJoOCrjt+TJI+QxOnJVHfSrSOZmSuh7+sw== 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 spamscore=0 mlxscore=0 adultscore=0 bulkscore=0 suspectscore=0 mlxlogscore=798 malwarescore=0 phishscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2202240000 definitions=main-2205040006 X-Proofpoint-GUID: xM11dKXUrMJiEHMfD0cRDmHNUGg5mIge X-Proofpoint-ORIG-GUID: xM11dKXUrMJiEHMfD0cRDmHNUGg5mIge X-Rspamd-Server: rspam10 X-Rspamd-Queue-Id: 8B0681C0094 Authentication-Results: imf20.hostedemail.com; dkim=pass header.d=oracle.com header.s=corp-2021-07-09 header.b=BFSRW9wE; dkim=pass header.d=oracle.onmicrosoft.com header.s=selector2-oracle-onmicrosoft-com header.b=MVEMXXHa; spf=none (imf20.hostedemail.com: domain of liam.howlett@oracle.com has no SPF policy when checking 205.220.177.32) smtp.mailfrom=liam.howlett@oracle.com; dmarc=pass (policy=none) header.from=oracle.com X-Rspam-User: X-Stat-Signature: rkyjdkuzeh6t4wet1r9hhhrcaoz3be5f X-HE-Tag: 1651626746-816235 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" This rather specialised walk can use the VMA iterator. If this proves to be too slow, we can write a custom routine to find the two largest gaps, but it will be somewhat complicated, so let's see if we need it first. Update the kunit test case to use the maple tree. This also fixes an issue with the kunit testcase not adding the last VMA to the list. Fixes: 17ccae8bb5c9 (mm/damon: add kunit tests) Signed-off-by: Liam R. Howlett Signed-off-by: Matthew Wilcox (Oracle) Reviewed-by: SeongJae Park --- mm/damon/vaddr-test.h | 37 +++++++++++------------------- mm/damon/vaddr.c | 53 ++++++++++++++++++++++--------------------- 2 files changed, 40 insertions(+), 50 deletions(-) diff --git a/mm/damon/vaddr-test.h b/mm/damon/vaddr-test.h index 5431da4fe9d4..dbf2b8759607 100644 --- a/mm/damon/vaddr-test.h +++ b/mm/damon/vaddr-test.h @@ -13,34 +13,21 @@ #define _DAMON_VADDR_TEST_H #include +#include "../../mm/internal.h" -static void __link_vmas(struct vm_area_struct *vmas, ssize_t nr_vmas) +static void __link_vmas(struct maple_tree *mt, struct vm_area_struct *vmas, + ssize_t nr_vmas) { - int i, j; - unsigned long largest_gap, gap; + int i; + MA_STATE(mas, mt, 0, 0); if (!nr_vmas) return; - for (i = 0; i < nr_vmas - 1; i++) { - vmas[i].vm_next = &vmas[i + 1]; - - vmas[i].vm_rb.rb_left = NULL; - vmas[i].vm_rb.rb_right = &vmas[i + 1].vm_rb; - - largest_gap = 0; - for (j = i; j < nr_vmas; j++) { - if (j == 0) - continue; - gap = vmas[j].vm_start - vmas[j - 1].vm_end; - if (gap > largest_gap) - largest_gap = gap; - } - vmas[i].rb_subtree_gap = largest_gap; - } - vmas[i].vm_next = NULL; - vmas[i].vm_rb.rb_right = NULL; - vmas[i].rb_subtree_gap = 0; + mas_lock(&mas); + for (i = 0; i < nr_vmas; i++) + vma_mas_store(&vmas[i], &mas); + mas_unlock(&mas); } /* @@ -72,6 +59,7 @@ static void __link_vmas(struct vm_area_struct *vmas, ssize_t nr_vmas) */ static void damon_test_three_regions_in_vmas(struct kunit *test) { + static struct mm_struct mm; struct damon_addr_range regions[3] = {0,}; /* 10-20-25, 200-210-220, 300-305, 307-330 */ struct vm_area_struct vmas[] = { @@ -83,9 +71,10 @@ static void damon_test_three_regions_in_vmas(struct kunit *test) (struct vm_area_struct) {.vm_start = 307, .vm_end = 330}, }; - __link_vmas(vmas, 6); + mt_init_flags(&mm.mm_mt, MM_MT_FLAGS); + __link_vmas(&mm.mm_mt, vmas, ARRAY_SIZE(vmas)); - __damon_va_three_regions(&vmas[0], regions); + __damon_va_three_regions(&mm, regions); KUNIT_EXPECT_EQ(test, 10ul, regions[0].start); KUNIT_EXPECT_EQ(test, 25ul, regions[0].end); diff --git a/mm/damon/vaddr.c b/mm/damon/vaddr.c index b2ec0aa1ff45..9a7c52982c35 100644 --- a/mm/damon/vaddr.c +++ b/mm/damon/vaddr.c @@ -113,37 +113,38 @@ static unsigned long sz_range(struct damon_addr_range *r) * * Returns 0 if success, or negative error code otherwise. */ -static int __damon_va_three_regions(struct vm_area_struct *vma, +static int __damon_va_three_regions(struct mm_struct *mm, struct damon_addr_range regions[3]) { - struct damon_addr_range gap = {0}, first_gap = {0}, second_gap = {0}; - struct vm_area_struct *last_vma = NULL; - unsigned long start = 0; - struct rb_root rbroot; - - /* Find two biggest gaps so that first_gap > second_gap > others */ - for (; vma; vma = vma->vm_next) { - if (!last_vma) { - start = vma->vm_start; - goto next; - } + struct damon_addr_range first_gap = {0}, second_gap = {0}; + VMA_ITERATOR(vmi, mm, 0); + struct vm_area_struct *vma, *prev = NULL; + unsigned long start; - if (vma->rb_subtree_gap <= sz_range(&second_gap)) { - rbroot.rb_node = &vma->vm_rb; - vma = rb_entry(rb_last(&rbroot), - struct vm_area_struct, vm_rb); + /* + * Find the two biggest gaps so that first_gap > second_gap > others. + * If this is too slow, it can be optimised to examine the maple + * tree gaps. + */ + for_each_vma(vmi, vma) { + unsigned long gap; + + if (!prev) { + start = vma->vm_start; goto next; } - - gap.start = last_vma->vm_end; - gap.end = vma->vm_start; - if (sz_range(&gap) > sz_range(&second_gap)) { - swap(gap, second_gap); - if (sz_range(&second_gap) > sz_range(&first_gap)) - swap(second_gap, first_gap); + gap = vma->vm_start - prev->vm_end; + + if (gap > sz_range(&first_gap)) { + second_gap = first_gap; + first_gap.start = prev->vm_end; + first_gap.end = vma->vm_start; + } else if (gap > sz_range(&second_gap)) { + second_gap.start = prev->vm_end; + second_gap.end = vma->vm_start; } next: - last_vma = vma; + prev = vma; } if (!sz_range(&second_gap) || !sz_range(&first_gap)) @@ -159,7 +160,7 @@ static int __damon_va_three_regions(struct vm_area_struct *vma, regions[1].start = ALIGN(first_gap.end, DAMON_MIN_REGION); regions[1].end = ALIGN(second_gap.start, DAMON_MIN_REGION); regions[2].start = ALIGN(second_gap.end, DAMON_MIN_REGION); - regions[2].end = ALIGN(last_vma->vm_end, DAMON_MIN_REGION); + regions[2].end = ALIGN(prev->vm_end, DAMON_MIN_REGION); return 0; } @@ -180,7 +181,7 @@ static int damon_va_three_regions(struct damon_target *t, return -EINVAL; mmap_read_lock(mm); - rc = __damon_va_three_regions(mm->mmap, regions); + rc = __damon_va_three_regions(mm, regions); mmap_read_unlock(mm); mmput(mm);