From patchwork Tue Feb 15 14:43:21 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: 12747181 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 35F8BC433F5 for ; Tue, 15 Feb 2022 14:44:22 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 819A46B00A7; Tue, 15 Feb 2022 09:44:06 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id 68A676B00A9; Tue, 15 Feb 2022 09:44:06 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 12E726B00A7; Tue, 15 Feb 2022 09:44:06 -0500 (EST) X-Delivered-To: linux-mm@kvack.org Received: from forelay.hostedemail.com (smtprelay0011.hostedemail.com [216.40.44.11]) by kanga.kvack.org (Postfix) with ESMTP id BD9506B00A5 for ; Tue, 15 Feb 2022 09:44:05 -0500 (EST) Received: from smtpin15.hostedemail.com (10.5.19.251.rfc1918.com [10.5.19.251]) by forelay05.hostedemail.com (Postfix) with ESMTP id 778E3181AC9C6 for ; Tue, 15 Feb 2022 14:44:05 +0000 (UTC) X-FDA: 79145284050.15.DE2B4A5 Received: from mx0a-00069f02.pphosted.com (mx0a-00069f02.pphosted.com [205.220.165.32]) by imf01.hostedemail.com (Postfix) with ESMTP id C99614000F for ; Tue, 15 Feb 2022 14:44:04 +0000 (UTC) Received: from pps.filterd (m0246629.ppops.net [127.0.0.1]) by mx0b-00069f02.pphosted.com (8.16.1.2/8.16.1.2) with SMTP id 21FEi0fY014259; Tue, 15 Feb 2022 14:44:03 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=ELdCh4DE5+UyD+4egtHVt19Pwqv52X7PLvvh+RreRls=; b=qqOh7myiWViMZjEDwIyx5WjxaCxbUw4wVOC6qgh0z3gZfccYdym8RS6Be17E2jTNqpkv xEFmiwWUnA9A3btxKv/mOhpkYBBiy0RgApfdADwePv2R9A/rsZkVQqHJ6aLgqq+UDGBX YlVIpw1iejgpemdSYkd0qeemxuTNlCbUOduVkRK4Ni3iJNYa4oQ8ISCTzHeHFep9Gdce Yfazyvs80aldJaDzVNQXgzYe0NfpcVMIT4KnKAv6REb/HAqRtRHGZLrOef5yKFuICwhR 2CU84+Or/TeL+8y36pB6L32qm34+n91XkZvS1bAG9N19xMhCskpwC7tbqGVIe0e33Wg4 Ww== Received: from aserp3030.oracle.com (aserp3030.oracle.com [141.146.126.71]) by mx0b-00069f02.pphosted.com with ESMTP id 3e8570shtk-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Tue, 15 Feb 2022 14:44:03 +0000 Received: from pps.filterd (aserp3030.oracle.com [127.0.0.1]) by aserp3030.oracle.com (8.16.1.2/8.16.1.2) with SMTP id 21FEeT4R145723; Tue, 15 Feb 2022 14:44:02 GMT Received: from nam04-bn8-obe.outbound.protection.outlook.com (mail-bn8nam08lp2042.outbound.protection.outlook.com [104.47.74.42]) by aserp3030.oracle.com with ESMTP id 3e62xeqfex-16 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Tue, 15 Feb 2022 14:44:02 +0000 ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=K6hY+fwXtR30WHVsoFCymHKKlwoXnnCPuqnuZhDHbOqMWHB+by3HhFzkdZ3DItom8tArWXCFwDjnni78yNU2jMQT2Q4fCCoOVdOPJBzo2j+oma/DT0CUJdDBn8I3M2x7hnslwEbDbcMkQKN+/lIZde0lm+T20Hs0kvafkbslO4I75wmoybtLdw4Fm/ot4fg7jq0ePp/cliI9qKKdT1jk9OwjCGD+xh2vwOc/aZHyKfbPf+P2+cet3TeY03Y0v06mT0iYYqM+RrMx1PzWStJW16larmQm02z3ShHkKO3z8orHrLlcOH3K9K1J0RlqVmPe72qu+NaTlNSk342tvqJ/aw== 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=ELdCh4DE5+UyD+4egtHVt19Pwqv52X7PLvvh+RreRls=; b=KNRdUYepg1T9zjCR0iih1ADfqnXpV3MHwuLx8WQd+a5MYMTQWsYWkhvAwT5ipokDAAc9YG5ZQAUfTrsLji4ZH2tt+Pptq7RQ91hMR66pLZKST60sJ8pHWhsV1xTAYNX9NSqTxUCV1bFW3u5lS0ed1P7G1qXizrXkNK1QaNRyymAW5q8yspL1P06ugsxsDKYxszqk3Wyo1H6eZOK2PMDH5CWvn0U40ydkCCaXegM14BfE9zaZxu9m005TE8DhLt8mRAlnTy+d+ov8eXdymL9nULwePvNcn/IBIYTL5uTFaqeNvK4heWcd2thqopRyOWRh256JuZFoiHbIiRFOiWVVcg== 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=ELdCh4DE5+UyD+4egtHVt19Pwqv52X7PLvvh+RreRls=; b=NPKDHhD2qCWUtNWgZ2nyroLwKqtSSlYA9yC6/fsb3EgEyhaxm3Lb6skxMVVRoS11PmVgHWNoycEzZ43N25lWY+Jz7zI4ZNiDh4CKH7I6e9rzY2kkPMKZiPrZGePOI5WSidvd6Y/4i2T2929FL4oHJAdUWfLSTMG3Vi/FIXD7HDM= Received: from SN6PR10MB3022.namprd10.prod.outlook.com (2603:10b6:805:d8::25) by PH0PR10MB5578.namprd10.prod.outlook.com (2603:10b6:510:f1::16) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.4995.14; Tue, 15 Feb 2022 14:43:58 +0000 Received: from SN6PR10MB3022.namprd10.prod.outlook.com ([fe80::899e:951a:8129:8ef1]) by SN6PR10MB3022.namprd10.prod.outlook.com ([fe80::899e:951a:8129:8ef1%4]) with mapi id 15.20.4975.019; Tue, 15 Feb 2022 14:43:58 +0000 From: Liam Howlett To: "maple-tree@lists.infradead.org" , "linux-mm@kvack.org" , "linux-kernel@vger.kernel.org" , Andrew Morton Subject: [PATCH v6 50/71] sched: Use maple tree iterator to walk VMAs Thread-Topic: [PATCH v6 50/71] sched: Use maple tree iterator to walk VMAs Thread-Index: AQHYInpheXJHm8gPwU6A7JMtz8SqgQ== Date: Tue, 15 Feb 2022 14:43:21 +0000 Message-ID: <20220215144241.3812052-50-Liam.Howlett@oracle.com> References: <20220215143728.3810954-1-Liam.Howlett@oracle.com> <20220215144241.3812052-1-Liam.Howlett@oracle.com> In-Reply-To: <20220215144241.3812052-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.34.1 x-ms-publictraffictype: Email x-ms-office365-filtering-correlation-id: 6bab10ff-cff4-42d9-73e0-08d9f0919957 x-ms-traffictypediagnostic: PH0PR10MB5578:EE_ x-microsoft-antispam-prvs: x-ms-oob-tlc-oobclassifiers: OLM:3044; x-ms-exchange-senderadcheck: 1 x-ms-exchange-antispam-relay: 0 x-microsoft-antispam: BCL:0; x-microsoft-antispam-message-info: p+ZOUA7qg0CX7qzTZ/UU9ArhA4W/ug7KDu8BlSrBA12OzNeAJiTXlPemzP8D4LtOCW/JbmLZHseSxobxdNgnlpJCCqE3miWTUeACAruVAkk00jIt/ieR/R55v96Mjs5le8knqLKRnxX8bZY+buf8X3+O8gsB7JdEDrqAp5WocYFbaQ086cpXAuab9bZBdDwOmvasajM5kRiXvzIDAcJ/I1LIzYMocIcg5n0iMJ/KXdk9GmU8ZlW6nKPkfYXwJ9KM8HrNuaudt2dfIm53UoSbgRzHJjsdpW6YgtYoZYSJeBHFsV7FBROmTwSUfmGKYS10bQDGF1zEwuuNbj1vtNURc5BLgnzhoETh04EQOiVssa2tsooqwGnOVgye81ge9a/j/F7pw6olJ56O2eoJ/7KPiNOGj1QuPU5Bo/NmBXmhE03ht7UOLuO0oJenQiC9qn1vmHkOxsnvIL/vd4CqRB2mOO1KspSwl7Ro9eBkWlTy8sfn2vwDgzMgT7/Mbf9nnM35kuGDQ94Yn0mUtPbKQSzwcb8iXRr81MHGHPOeo18eHGdkUe/iqocgCAxDeRlJZ8F8cV4abn6+ZErpbAo/6ZA7rAr+skfW2DwDJ2evaGfkcmp+nPaPzsSmHURBZMDiHWrM3XJOG9mevJqYPJN4reqs93aj5uWiFlRhFeQsNjojHeq+NJvTD1wjfSLb8iL78B0OIMYhm6CCFNxbCsei+KUulg== 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)(316002)(2906002)(6486002)(83380400001)(38100700002)(110136005)(508600001)(91956017)(64756008)(66556008)(66476007)(66446008)(5660300002)(66946007)(76116006)(8676002)(71200400001)(38070700005)(44832011)(86362001)(2616005)(1076003)(122000001)(6506007)(186003)(6666004)(6512007)(26005)(8936002)(36756003);DIR:OUT;SFP:1101; x-ms-exchange-antispam-messagedata-chunkcount: 1 x-ms-exchange-antispam-messagedata-0: =?iso-8859-1?q?9aQIV33ZjeHwIQSyGuNPGEt?= =?iso-8859-1?q?IFpAIpGinDWLil6uJs6S5i+5A+6F47/+S9Wa1vUQZpJD4QmfosAcRUkNBRhq?= =?iso-8859-1?q?fTenEaWBR87USVQkn+TyuAOrHtbckHlxvndGqPmjh10Gm3LV9jhRsfafGyfh?= =?iso-8859-1?q?BPEJB7BJaDJwKRcUTZbLEq7diKM8UHSCkjRW/0nr2iSZSaDp6Sjnkl524bvJ?= =?iso-8859-1?q?EddfBi58mqFtVu8uQz5Id3S6UHC+0CHywzo2Shb6x0HfX5UVvUw7hvT0UD/e?= =?iso-8859-1?q?hdDZVVHDmmYIxdfUbCIfuZpRPxEp50FBDzo+S04ffbo3EAjmLN4ncBfuPuZ6?= =?iso-8859-1?q?NzOORCKBTdMQS8TMQhvWrSHa/iJ7MWYcemUkcb2mNpbh/EH1ygm7rGao7bz9?= =?iso-8859-1?q?1CVgUvhyQSFwI/ixCJItgZhoZU+3j0uhmoLIFoGDmIzIL6ccYB28m/e7P+eq?= =?iso-8859-1?q?vTOODdSldLHmhvCxu0pr165u6U5ls7+0a640g47GnG5fvOHcVSDoo95dSHFx?= =?iso-8859-1?q?yzkI5H7LD3tqd68DU9jCeSXtWVTx2PUI30gVAdbSYOZAgBj9hjH5TAT5rOSR?= =?iso-8859-1?q?Lv44+wizO3rNdN6tsDCiiqdynfJI6+ivQHiz4WiZ2mWD1NJTYacObfHA1FnJ?= =?iso-8859-1?q?YeQ4bxrg7cXC7ZnxWO6WYZuSUcYwOdOrulfSgRilRjwPLf11zWQDd2iM0+pY?= =?iso-8859-1?q?dQPRbltKzoWY222Wht+Ar8ejynHwU30Qm651cQlqwyAJmhCGnZaA0uBRIegh?= =?iso-8859-1?q?fHGWmXYNN9ZIod+bAE9GRXS01YwMI+q+uH8OT7ot+F37eZXHmIitpFp9ClFU?= =?iso-8859-1?q?DKQ2ZnwAzAoIsFb0YYoggqYdas/9hOsaM+Fn7JlS7v4v1qlN6iGl9J1irePx?= =?iso-8859-1?q?OsHyvdSegnh4CkrPvzb/w0WcHLx7nmw9MXTkdp4Q3czQzSHWHqSuq9WvDiTX?= =?iso-8859-1?q?AB7rKEeu5btaHR0iztGy4ZSGb0zVCqLgMNmkrUJ2q/4S/5qi0W0FwrlIVPug?= =?iso-8859-1?q?7DMsVbZF//B/KGCCz/T9B0zOLEm+0Ko+RrneUkq0d16BgG1zGOPXg5hHHPqw?= =?iso-8859-1?q?uiU1mkWNY3PRMRsJDRh+rqjgTDqcRyoelXMTqC8EvZkqniEQR0f92ysSAh/3?= =?iso-8859-1?q?cGBB9OoMwtw0x/fGZxWhWUbkB00cb+SFOgmcTYGvzLbr/VxFpNB3bbO4LAlU?= =?iso-8859-1?q?fZJzXnRYyoy1m29S7rP664ZM8NgYzL5oV13WMPceM4zlpD9RwJ+uoUN+GL8z?= =?iso-8859-1?q?6pfu6kus+HVDpMiUIjTxY4d0YFR32/MAmQcY3NSo1JA/fKTZF7yFbRZ2bUFU?= =?iso-8859-1?q?2M0E6YrvNtOnaqfRfR9ytMgqkQc1ZLXoArOJJAku22+2zDR+OCwgch9kiuTC?= =?iso-8859-1?q?oJY5G03NBa0r1O6BjmUnmohwILMLkSUH9/D8l8IjsGF7IG8CYHIKizPyJDaY?= =?iso-8859-1?q?zrONgX6Tlnh7gvddgKkXRifttJS6GYgc3ewe2H6HsM/p5aktFoz8xik3HcU9?= =?iso-8859-1?q?kQxt2cPJn4egkWr64AK4C7/Ii8W1voSyQ9V4tkNmLXnGpDyjrE0RmLHQ3O3r?= =?iso-8859-1?q?1kWiBWbA3XYvXy0K0J9k4ZlTqzOZIkZbZem3v0IaK2ag9zGTzdYKSkmU7AR5?= =?iso-8859-1?q?UVq9ildfdKoUUmw2gAHfyr5k8N9lZ71MqFVbbUslDl2s8Up3v6hhcMh9XIxQ?= =?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: 6bab10ff-cff4-42d9-73e0-08d9f0919957 X-MS-Exchange-CrossTenant-originalarrivaltime: 15 Feb 2022 14:43:21.9480 (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: x6Nkm4gOmeEb8CWvoDkSBh1nWt5LNOwwOBjz3jlTNBJM67/sH6D2bFamggc2BjbAUaUbXH418jJ0Eyfy3UYQsg== X-MS-Exchange-Transport-CrossTenantHeadersStamped: PH0PR10MB5578 X-Proofpoint-Virus-Version: vendor=nai engine=6300 definitions=10258 signatures=673431 X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 suspectscore=0 phishscore=0 bulkscore=0 malwarescore=0 adultscore=0 spamscore=0 mlxlogscore=999 mlxscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2201110000 definitions=main-2202150085 X-Proofpoint-ORIG-GUID: QaCTzwAzUjTNItF3E98HdRWGuvG4sUJV X-Proofpoint-GUID: QaCTzwAzUjTNItF3E98HdRWGuvG4sUJV X-Rspamd-Server: rspam12 X-Rspamd-Queue-Id: C99614000F X-Stat-Signature: hgs89tjy1gbpnyxqm9ni87yzyc1kr66u X-Rspam-User: Authentication-Results: imf01.hostedemail.com; dkim=pass header.d=oracle.com header.s=corp-2021-07-09 header.b=qqOh7myi; dkim=pass header.d=oracle.onmicrosoft.com header.s=selector2-oracle-onmicrosoft-com header.b=NPKDHhD2; spf=none (imf01.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-HE-Tag: 1644936244-129719 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" The linked list is slower than walking the VMAs using the maple tree. We can't use the VMA iterator here because it doesn't support moving to an earlier position. Signed-off-by: Matthew Wilcox (Oracle) Signed-off-by: Liam R. Howlett Acked-by: Vlastimil Babka --- kernel/sched/fair.c | 10 +++++++--- 1 file changed, 7 insertions(+), 3 deletions(-) diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c index 5146163bfabb..f0ac5dfe2ab7 100644 --- a/kernel/sched/fair.c +++ b/kernel/sched/fair.c @@ -2671,6 +2671,7 @@ static void task_numa_work(struct callback_head *work) struct task_struct *p = current; struct mm_struct *mm = p->mm; u64 runtime = p->se.sum_exec_runtime; + MA_STATE(mas, &mm->mm_mt, 0, 0); struct vm_area_struct *vma; unsigned long start, end; unsigned long nr_pte_updates = 0; @@ -2727,13 +2728,16 @@ static void task_numa_work(struct callback_head *work) if (!mmap_read_trylock(mm)) return; - vma = find_vma(mm, start); + mas_set(&mas, start); + vma = mas_find(&mas, ULONG_MAX); if (!vma) { reset_ptenuma_scan(p); start = 0; - vma = mm->mmap; + mas_set(&mas, start); + vma = mas_find(&mas, ULONG_MAX); } - for (; vma; vma = vma->vm_next) { + + for (; vma; vma = mas_find(&mas, ULONG_MAX)) { if (!vma_migratable(vma) || !vma_policy_mof(vma) || is_vm_hugetlb_page(vma) || (vma->vm_flags & VM_MIXEDMAP)) { continue;