From patchwork Wed May 4 01:14:00 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: 12841577 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 487F2C433EF for ; Fri, 6 May 2022 20:28:32 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id CF99C6B0073; Fri, 6 May 2022 16:28:31 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id CA80E6B0074; Fri, 6 May 2022 16:28:31 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id AD47C6B0075; Fri, 6 May 2022 16:28:31 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0012.hostedemail.com [216.40.44.12]) by kanga.kvack.org (Postfix) with ESMTP id 9F85E6B0073 for ; Fri, 6 May 2022 16:28:31 -0400 (EDT) Received: from smtpin19.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay13.hostedemail.com (Postfix) with ESMTP id 6FFC960A9C for ; Fri, 6 May 2022 20:28:31 +0000 (UTC) X-FDA: 79436456022.19.8688D44 Received: from mx0b-00069f02.pphosted.com (mx0b-00069f02.pphosted.com [205.220.177.32]) by imf17.hostedemail.com (Postfix) with ESMTP id B67B74004D for ; Fri, 6 May 2022 20:28:15 +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 243KctF3024988; Wed, 4 May 2022 01:14:38 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=t5HJVMlCrFs371XkVWlg5pWEAxuNjGH/5NiGlW3/6yg=; b=X06xkcvD+GXrjBWKoZxQPWB4Fi/MNkIRKPaXG94VjDpRzAYTXc9Tkwi63K+4fzVy4Er0 u7QtTJhN4NDHAJPn5jXnnUXne68NJ8oGtXvIWTzhV7OzNm5juMcOhnbhkVZM3QxAimTB seNFcRY7Al/ELg8vMHnn+nsyii2G0w3R9O+AbfDDXtsauMW68q1B8E5D3j5Mts0ZLPuU i5WICiOqp3uTdM0Dvrnu7CeWVsRJUy0QOvndZPqfx4j8ZFCZCyFFmeJr3O0zReWMmCgh VYwoiefEkfYpnp+9URzF+UHsB3fa1DzdcCxzUNPw151NfalMrTy61M2VPo5a14ASuxqC Ew== Received: from iadpaimrmta02.imrmtpd1.prodappiadaev1.oraclevcn.com (iadpaimrmta02.appoci.oracle.com [147.154.18.20]) by mx0b-00069f02.pphosted.com (PPS) with ESMTPS id 3fruw2f6c5-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Wed, 04 May 2022 01:14:38 +0000 Received: from pps.filterd (iadpaimrmta02.imrmtpd1.prodappiadaev1.oraclevcn.com [127.0.0.1]) by iadpaimrmta02.imrmtpd1.prodappiadaev1.oraclevcn.com (8.16.1.2/8.16.1.2) with SMTP id 2441AUFa023411; Wed, 4 May 2022 01:14:38 GMT Received: from nam12-mw2-obe.outbound.protection.outlook.com (mail-mw2nam12lp2045.outbound.protection.outlook.com [104.47.66.45]) by iadpaimrmta02.imrmtpd1.prodappiadaev1.oraclevcn.com with ESMTP id 3fruj9g4fp-3 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Wed, 04 May 2022 01:14:37 +0000 ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=PCh6GOQMZc3Prhp8d1qeo0tDGjbJwPIi6J6iipVvbg/ka9Q7l1zWTfAr8yMYxcwWxm5StCK9llyWbkQYa5me7iNnMzlQBtNpQ/JvTY1AtEvvefa0sBConHWsaJwVrAj09aMMzIHUr2U8GDEFntI8BHdTupDJ3WOZhSCvEHdCaOfTY4MYezjljJgNwO4jezkS6Axnlo8mRj17uuXdkfPJB7ZPH6fNIGVgLVzAPezqidFy8y0uQ+Fd7tIBVJHv5z3UdmEZyUeFZ/NMmtvgVh8pXkZYTF72BLrXRFMqejaI8NqM7XnLhi38h7MvaAJ/DxVamzSwyBytQ7cwnTkKuf3/WQ== 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=t5HJVMlCrFs371XkVWlg5pWEAxuNjGH/5NiGlW3/6yg=; b=VXjXQCoyj2VIodRPe+drk8S+qa6Z0QsjtllJV2FJ0xcpceUMaTy6Z3WzvvVMd4TXtKmDh2Q2mYkKWR8I8RD2nAFKShM1wJnsZA0pCmBTTk+QmUYURxIybNGOiwumDwEmP6Qa3SK5dXi+sZDRSt8FYYUBwoPuYRFcSNuxZb6HVRc1kvMoVg/T1J1wlRL9Npv/62CfXweI0+0f4BQ/0HbudKBN7TIA9+nW8iyLvSsys7x2BR/KYuqwVwTnCODdvn7mTFSejIhu+JYZnonAk1k+PjcF22BXfQoL30G5kfZR2OuMqmH1rURiIGKRIcPAb25rYFIGK9HK61IZGRzeLWxAqg== 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=t5HJVMlCrFs371XkVWlg5pWEAxuNjGH/5NiGlW3/6yg=; b=LKuKiVlwAKH/zDD9GaQT9fZ85EyjrA0FhMpKKiBAzKt13vQ3yaQ+Lpz94Kxt5cq3KR3JkYCfSMYzKDZYrwDKY5Jo1reV0pub+pkxCWSOnS/7KBH9qy6diCVkP8j09wx/Jdf4Hu+9jeIOQtbMAfKNgsfQjSnOHn8XK5hXxExN9qk= Received: from SN6PR10MB3022.namprd10.prod.outlook.com (2603:10b6:805:d8::25) by MN2PR10MB3728.namprd10.prod.outlook.com (2603:10b6:208:115::29) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.5186.21; Wed, 4 May 2022 01:14:35 +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:14:35 +0000 From: Liam Howlett To: "maple-tree@lists.infradead.org" , "linux-mm@kvack.org" , "linux-kernel@vger.kernel.org" , Andrew Morton Subject: [PATCH v9 48/69] sched: use maple tree iterator to walk VMAs Thread-Topic: [PATCH v9 48/69] sched: use maple tree iterator to walk VMAs Thread-Index: AQHYX1Q8/nyc3nUnlEWv2xgsS/lGZw== Date: Wed, 4 May 2022 01:14:00 +0000 Message-ID: <20220504011345.662299-33-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: 8d817f9c-2bff-4b0a-c48b-08da2d6b740a x-ms-traffictypediagnostic: MN2PR10MB3728: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: UYAsg+eFUZyuiLjJ+ysq8OuTO5LwybZDuzX2Q9Jgz/QoqQp3ZGvcPNTSvzqBBLaMuolSZlXJsVZq7i4aDvk8ANgGIYCt7nf51t/ATY5yeela1Oh8dbuh0E2WB6iG0OLoL+f+nOPr/lUKPtmOug7cdaHSm4CuwGe7/aXl1YTFakjuwdZ2LIdPgdj+8qOSEAhu4Hg5MkVZ4/0ApvANWTIXrCiW6tPqBMS2i8bbvOC5wEu88RFig6VfIXOjx7jiVfa7Qhyw/msBWokNW9fc4dsg/nTc0FEWmwrVJkjuRBWn3w6cCkJJ5Cx8KOY+trE4UhTypXNAhp5etM7Ww91pwK+mkpHwf5phW6jLc7twGHEEJ9MSLd9x38l/5vbm16uH9xF7N6roEYYwYsxGDqzll2cTTmLyf+UGzRFEWQA3/7JS/O1ArhRODwvW2zWAaw9/tnLbmXwjuSrB8Bg9gAOf/dSch8tmtldDxMGjmmlKeLew2FvE61hBp75DlGLSLDYEq5n0vot6MC2VQQyXTgDGmTVQqe8sUAC9K2QJ2ckBMwNcd773xuvXgz6Qg2/ALIG5oEH+tIv1D2bVSwQSu6z4F8GUkUepc7u07djBHJSPrYWJANNydFi4mbt6p/O0ScvI5hG1ZWD9vGsMVnAxldqNts2fMzbksDgLoA4jdMKFSDNv081KP6vHrGWtg89rKA+a3D9/ZBQOsdNO2/HUsOeAtcx1Iw== 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)(71200400001)(508600001)(5660300002)(8936002)(6486002)(86362001)(26005)(6506007)(2616005)(6512007)(2906002)(83380400001)(44832011)(186003)(6666004)(66946007)(91956017)(76116006)(110136005)(38100700002)(38070700005)(36756003)(316002)(8676002)(66446008)(66556008)(64756008)(66476007)(122000001)(1076003);DIR:OUT;SFP:1101; x-ms-exchange-antispam-messagedata-chunkcount: 1 x-ms-exchange-antispam-messagedata-0: =?iso-8859-1?q?AeTinuEVNljbQhEqiew6zMT?= =?iso-8859-1?q?SmpOjEwDqSCQ+0JHt349165L4HDXVDZhHbUk4X41YtmfCSAGem8j9Kv6sepb?= =?iso-8859-1?q?/zsWDXiAmINpsQdxvVVS6KJ3SvGG0DbFJ0O+yL17+pVQrX2gf2YZx+xbUCUa?= =?iso-8859-1?q?TV+PfhQgqzyZtkflUC5fIBXW6+EK0XK4VkfOIQoiKkzW1/2BZGNlKJ6ZRYM3?= =?iso-8859-1?q?rntw3Zv4sEGOUb3ErM4auPYcgWRtpTMZynW2KdRP7g//QUTVnTcl9MncWKhK?= =?iso-8859-1?q?zUG3k0g1dXvRSDLJlfa11/FW28NnH98SHquOCUQB1QhU6ERsKn9zQ9QDu5as?= =?iso-8859-1?q?7LMThvi/fYHcWCzFVTQUNs22TO431XC9QJBvGfefCxhDCnm3ivVqw0NBaPIR?= =?iso-8859-1?q?Dpg2yOgc3fb0TquqQ4L7CV4k5uNZ74BkvfBPYhXZ0ydb754NZNxX2Sc4jtJ2?= =?iso-8859-1?q?x1rGjC/WeUG2pWcqLjDYn7zQ1vxE78Zi/ygRBOSp9Hbrqf9S8JjsBqg6jNc1?= =?iso-8859-1?q?PZQdz9k3CEiLoYCWQGImXj36OPr+8FNOoew0FWJmtzRsx3+hZ9TCH1bt+e8a?= =?iso-8859-1?q?g2Pv7WEiAr5J0MNzfm0nHYGFBslp3A1dnUrnJf+hPvkzAn8D0uznLAldmN1l?= =?iso-8859-1?q?EQd8BNVTpXEUyXc07urETLvarlZmjgHgxh2afKdM3+PlUakgBJZMoRN5RPxp?= =?iso-8859-1?q?FaRsYH1D0yfdCCOmcHGkjSHyMAiyZlikS9BO49vuUncFORL3IIqa2PMFZw1T?= =?iso-8859-1?q?JDeMDHFLtWpUg78bAkYLs77qjwivaI1DPoPECY+sDEXyefcAo3wPO08/sr5G?= =?iso-8859-1?q?42jdOKhZsFKB8l6tvw1fMEU/yrhyq2q07Gl2FbcKeymeVfAuxtYwBl1e/sd5?= =?iso-8859-1?q?DJrsnJbzxtJ+D27exXw5S7lMHQIifeTE7hmPlKZWcW1iSbl6nj186V/tPvPg?= =?iso-8859-1?q?wWdiWBn2Q6GR4MUV537V3jiewFQZeIO8G6Meur7ZAgMQKXs6YFLmsvIUl0od?= =?iso-8859-1?q?6FEoBTL2FhCh7/IKwHmhj9kCtfVJ8R6CmQFp0rh1xuNnXjioctOCnIYGXSRb?= =?iso-8859-1?q?eYx/vxlY9QSFp15HapgsF7CuII/72pIOSYuPz6UAFgXzcJnshA7WgVPw775O?= =?iso-8859-1?q?6Mt+eFmfHYpAVHuC+fx0fkroFIh6KlbU/eyO7U/VNcWwMDZCG2dZCC6W66wP?= =?iso-8859-1?q?d7vQZkiI8z6ah50jKgVxfRygyqQOgGRK+J+j/CcJXBHm5xv5k9B4iOSkmMOR?= =?iso-8859-1?q?+uicsZjKkhgTi3xyX6/ACXm62oxeNaLRvNrsnPpqULXS4WugZ+2A0doIkxIj?= =?iso-8859-1?q?iIvD96Kcl/KNotDcUG/bJkpfyA0Hju1B3oTbD8Tfl/YBpq2ZneZrn57IuVWa?= =?iso-8859-1?q?FxUczT3lykkZoHm7e0+5mxl80mCK/mfj+3sM+WJDiCXrqgoXVmOwJf0ZWx+3?= =?iso-8859-1?q?z4AdNamGfHH9yY5d+NM1jOX1Cp44yW8zz8FFF8FULHmyK8bd7dJTOhq36TjR?= =?iso-8859-1?q?SrlPwV+2D/ps/YYNYtP+//WLNwYod4ZjqiBoxq23UC6X0p3dmLaQLJVzjlBb?= =?iso-8859-1?q?8XQE1w0dBnRmDSHpHsPkLt0dWDJBtFJKMStjomKDc/K0EaDCiJW5wb6Cgxrm?= =?iso-8859-1?q?8SMVnWjt9GG7XCQC1Cb4bAqvb8mmOu48NCBreJcKluxsbY7JnnlBYY94+Dad?= =?iso-8859-1?q?KDg9HfaHkvvYFWVyRWr0ax80GYY/g7LQ00ic6rjJcLIgaFq2RdNoj6KgUQNK?= =?iso-8859-1?q?kSOU/73KTltf+tticZfy7B2NFG9HRWw1NojE3InqV+isU27lsJiHo/8LO+iV?= =?iso-8859-1?q?sbim2qyQ=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: 8d817f9c-2bff-4b0a-c48b-08da2d6b740a X-MS-Exchange-CrossTenant-originalarrivaltime: 04 May 2022 01:14:00.9389 (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: 4x1tRct4tDe79YfKedIFMomlGjORE2RAwSBmedPZiDqseuxV8gjSyfv2ad/izJZPjhtEhhtVmDJDyv89r3oV8g== X-MS-Exchange-Transport-CrossTenantHeadersStamped: MN2PR10MB3728 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 malwarescore=0 phishscore=0 mlxlogscore=999 mlxscore=0 spamscore=0 suspectscore=0 bulkscore=0 adultscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2202240000 definitions=main-2205040006 X-Proofpoint-GUID: ESyGGmmM-2aOIgCjG35j-1OyGjbFf3g1 X-Proofpoint-ORIG-GUID: ESyGGmmM-2aOIgCjG35j-1OyGjbFf3g1 X-Rspamd-Queue-Id: B67B74004D X-Stat-Signature: dxjx5ftxgbrk67th5s4wiau7d1guq783 X-Rspam-User: Authentication-Results: imf17.hostedemail.com; dkim=pass header.d=oracle.com header.s=corp-2021-07-09 header.b=X06xkcvD; dkim=pass header.d=oracle.onmicrosoft.com header.s=selector2-oracle-onmicrosoft-com header.b=LKuKiVlw; spf=none (imf17.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-Rspamd-Server: rspam09 X-HE-Tag: 1651868895-695372 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: "Matthew Wilcox (Oracle)" 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 a68482d66535..aa18f180ef7d 100644 --- a/kernel/sched/fair.c +++ b/kernel/sched/fair.c @@ -2722,6 +2722,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; @@ -2778,13 +2779,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;