From patchwork Tue Oct 5 01:30:25 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: 12535245 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 mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 2C71FC433EF for ; Tue, 5 Oct 2021 01:31:08 +0000 (UTC) Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by mail.kernel.org (Postfix) with ESMTP id 3E0FF6121F for ; Tue, 5 Oct 2021 01:31:07 +0000 (UTC) DMARC-Filter: OpenDMARC Filter v1.4.1 mail.kernel.org 3E0FF6121F Authentication-Results: mail.kernel.org; dmarc=fail (p=none dis=none) header.from=oracle.com Authentication-Results: mail.kernel.org; spf=pass smtp.mailfrom=kvack.org Received: by kanga.kvack.org (Postfix) id 3FA2F94000B; Mon, 4 Oct 2021 21:31:03 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 3AAA294000A; Mon, 4 Oct 2021 21:31:03 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 1AF0194000B; Mon, 4 Oct 2021 21:31:03 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from forelay.hostedemail.com (smtprelay0086.hostedemail.com [216.40.44.86]) by kanga.kvack.org (Postfix) with ESMTP id 0549E940007 for ; Mon, 4 Oct 2021 21:31:03 -0400 (EDT) Received: from smtpin24.hostedemail.com (10.5.19.251.rfc1918.com [10.5.19.251]) by forelay05.hostedemail.com (Postfix) with ESMTP id B1B10181E726D for ; Tue, 5 Oct 2021 01:31:02 +0000 (UTC) X-FDA: 78660655164.24.0D39CC7 Received: from mx0a-00069f02.pphosted.com (mx0a-00069f02.pphosted.com [205.220.165.32]) by imf21.hostedemail.com (Postfix) with ESMTP id 29599D03C70A for ; Tue, 5 Oct 2021 01:31:01 +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 1951OdX7010252; Tue, 5 Oct 2021 01:30:53 GMT DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=oracle.com; h=from : to : cc : subject : date : message-id : content-type : content-transfer-encoding : mime-version; s=corp-2021-07-09; bh=3dh2fyeFStJ0eoL6s+os+346cUUPoHSm+i7flt4yF3w=; b=PFoR3/p9y4rFyQmPFSSNJqxD7PRfsL7Olp+3H7itZuc6Z1FPXD3KQT/tAi/FQIlh8sAw eCVxW2TxDKZwe6IMshZkXxBDZyn2F9DKJ5MCEa4sN1muCDUZcIizbfpPSLN2yT9mlIOw 2I21t5S/rI21DG45ZMv1KnNq0Q8+UVO3vhmnIMbmP9nwBo37OTnm9u7rjB3f/bIbcxFa t+nVuxvktxVu1NDv06wtA9sRd2gm31Mv6bYmaK2QZ4cwSqRZIv9+pQsFaJGQdQQW8eVP 2DvQ5xdzvKexsHUYMmlvjevcUO62SQ73ysJzCmgMBjvhP2Mtiq/dfczLBl2g5ci6ecx1 +A== Received: from aserp3020.oracle.com (aserp3020.oracle.com [141.146.126.70]) by mx0b-00069f02.pphosted.com with ESMTP id 3bg3upv32m-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Tue, 05 Oct 2021 01:30:52 +0000 Received: from pps.filterd (aserp3020.oracle.com [127.0.0.1]) by aserp3020.oracle.com (8.16.1.2/8.16.1.2) with SMTP id 1951UHf0178354; Tue, 5 Oct 2021 01:30:27 GMT Received: from nam11-bn8-obe.outbound.protection.outlook.com (mail-bn8nam11lp2168.outbound.protection.outlook.com [104.47.58.168]) by aserp3020.oracle.com with ESMTP id 3bev8w02af-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Tue, 05 Oct 2021 01:30:27 +0000 ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=T0iWjp93hYpuJX+8v0As3LJCx36vwdAjob4GmNP8hOsTVyVba60bEaYBCErM0qUL6CBcIn7sORyDfhb5XI6r1lj/zKYDZfTmHO1rPlE4xZq0RqPWw4jEimfPANq8FrgJfEpusS9CqyOGMPEyLGg+Fkf7N2z9fBpA8hXeRvLnT3pE7mzGVjM1SigUUGeZYEeTAlsyw1hfF1TGOx2jfzCpSxr3NxnTXTRn33eVhILidw3A5wNnN2gaU1rpcWdva1gb7HWIeXl6+2v8UDNd0vaA/DGqGvnGamp6PVJyixlCkaub8xyZdeUWT4bEf20lgILc7VFXHbRBipFvP6pphJzfGw== 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=3dh2fyeFStJ0eoL6s+os+346cUUPoHSm+i7flt4yF3w=; b=ehPM7YKDWbFdXbvwVNZ8zlv6DG53K9j5b1I1BlcjI4e8ly8Dm+WxemDEzT/CemTZ6oj3Hip8f3QLQqenShNNeQk7JRaX47ySHdwgLenHyGbpRONreGHkoWEgmHfu3iFu6N8sWdNr2z4hGXMZZ6jmv2VrOfrhRK8pYqTkfeqLT7QzL4D/H2vuqBLQkxowkPmEi1hj6JiX/xEnrO8ta+KxtoLACf8ZrecTZROXG8oSJsMyyY2qwz3GwoRgoo4bQtYb0wG4M3C5PjCsQt9vcWPjoqXWdfVxyCy63IaUeN77YQ9X3B5O/vU6l9Qeo696u6gGYJCIjfRCCSCxUfbCExwYug== 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=3dh2fyeFStJ0eoL6s+os+346cUUPoHSm+i7flt4yF3w=; b=Jy/t32PBzLL1SmEoifY8RMn6n9wmlxxYfVmK0bGVQW38TsRU7hh4q1JAEAjtLyLg04rWFOKdfK/H1M/RedapsVnLnefXwqsaZEUt0RIgwcZW3Gg4YiZOO0tooG8v6PqCPQ9IIm06l10rAna+riHV17wFmaYQSY+JR4R+ekVNW18= Received: from BL0PR10MB3011.namprd10.prod.outlook.com (2603:10b6:208:7e::29) by BLAPR10MB5218.namprd10.prod.outlook.com (2603:10b6:208:306::23) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.4566.15; Tue, 5 Oct 2021 01:30:25 +0000 Received: from BL0PR10MB3011.namprd10.prod.outlook.com ([fe80::6d61:54c2:40f0:93a]) by BL0PR10MB3011.namprd10.prod.outlook.com ([fe80::6d61:54c2:40f0:93a%5]) with mapi id 15.20.4566.017; Tue, 5 Oct 2021 01:30:25 +0000 From: Liam Howlett To: "maple-tree@lists.infradead.org" , "linux-mm@kvack.org" , "linux-kernel@vger.kernel.org" , Andrew Morton , David Hildenbrand , Douglas Gilbert CC: Song Liu , Davidlohr Bueso , "Paul E . McKenney" , Matthew Wilcox , David Rientjes , Axel Rasmussen , Suren Baghdasaryan , Vlastimil Babka , Rik van Riel , Peter Zijlstra Subject: [PATCH v3 00/66] Introducing the Maple Tree Thread-Topic: [PATCH v3 00/66] Introducing the Maple Tree Thread-Index: AQHXuYiS9Xv5SJOepEyoMjh6+6izPg== Date: Tue, 5 Oct 2021 01:30:25 +0000 Message-ID: <20211005012959.1110504-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: 137a54db-0233-462e-d3df-08d9879fb4e8 x-ms-traffictypediagnostic: BLAPR10MB5218: x-microsoft-antispam-prvs: x-ms-oob-tlc-oobclassifiers: OLM:8882; x-ms-exchange-senderadcheck: 1 x-ms-exchange-antispam-relay: 0 x-microsoft-antispam: BCL:0; x-microsoft-antispam-message-info: o1pYLHhYJH2T44yHoH5YKiKQzVVFmkvJxMU3MQaW9E29DVb7TGSygsZ6YTYFFwO4rOcvayZidjo2vQvRnhzE7zqcfpruYZVQHQgJeitLmXLvrYwwFkrYcVJxS9sFe+gVBeXmNDBkuMG1CWS3vlpUUHG2WxgpQw1RWXZywxDvGsSSN35ivJoME2KTs1jSQE9d3dnaozFVOKgo/y50trVPw24e8RrUScLnUbPqjtAfRqvAx5RtF220WZukE96e2asMnRs9vz9KeNHTKO5ygCDqoFK/Tx407QRhpmjdEQY51eONhTwCDZAbzA5qT/0S7y0ivGCjXwQT9EgOGWL97EBq1TH+tUJaqpvS18SUm8YlXdWsB+gmvRkgrnBoY/dYovkf/WNZd5RNwBwFcC3bq9wnbG92ehWiclTX3Dugg+67nLK7Y+rwJ69/IDAopLUvsKQERp32TClVl/k0q/TJIARUm8hySI6jrCKgKpscV5UYwAEXar7eBVOrTl741bUfIAjUvnwVntuRVlX5sDku8mXH+AuJTMxzdHh9rxnT2/PBwEW7WZ5oJO0N7jZTHoLKfB/q8DoCoXpGXBv9yS00YLl+8QH2PbO44cpzkGXMB2sKnb80rpV0PT7HjN2DHiH5Dsf/Hif/S5qOqpqqRRW3Glee8BSXhKGJRNpzcExqilqQwkeNNhQN6/SlQLemVPleA1bwK/R8S87KMG4rwzrI/1rWeGcbFXklDPAVCwveiGz9x5OJ3AmjV53VO1G5NRB8jU3bl4d4h3SKaIP4hlcPpbxuykeAC3ikYNtb0GHjHCFW7R6AiraUdms95tWSSjPDVowT37IslfLjklgyp+qtZB3IFw== x-forefront-antispam-report: CIP:255.255.255.255;CTRY:;LANG:en;SCL:1;SRV:;IPV:NLI;SFV:NSPM;H:BL0PR10MB3011.namprd10.prod.outlook.com;PTR:;CAT:NONE;SFS:(366004)(26005)(5660300002)(6486002)(186003)(6506007)(86362001)(6512007)(1076003)(36756003)(38100700002)(508600001)(30864003)(8936002)(71200400001)(966005)(8676002)(122000001)(316002)(110136005)(76116006)(91956017)(2616005)(44832011)(7416002)(38070700005)(54906003)(4326008)(66556008)(2906002)(64756008)(83380400001)(66476007)(66946007)(66446008);DIR:OUT;SFP:1101; x-ms-exchange-antispam-messagedata-chunkcount: 1 x-ms-exchange-antispam-messagedata-0: =?iso-8859-1?q?dgLIFrqY88gkdbaAAX6jUAr?= =?iso-8859-1?q?q2uLddvciPwTeJsPvyyXq/CBo+IdENolvguZgio+3WI4vLJQwA0gTTL9C/YD?= =?iso-8859-1?q?CxUFldt/vrN7FGx4EdWx32FlPsy9cvXELuG+7ktTzF8ERyO489jyvkPREe0v?= =?iso-8859-1?q?UAXaIwVs7Z8yIwAHH+M9G4BboyjOT+ZdaLanCr9iyE34jB8BtzuLxvzj+lMD?= =?iso-8859-1?q?fDHoNh4opPfqt0/8eWP63SL9gNYbDt+cMOQmcUi445F4j3eDEO2am3w1gzRI?= =?iso-8859-1?q?k7lCb3XRSjazHhGuP/q+/1mRVuJGUOFm4zPlqu0+3Wsa/P43tKroypPWHDFd?= =?iso-8859-1?q?pXENB8z5xf+WUtfdQTWQLDek1ZBbWhdnuF5MGFmDcbqnIJb9d2j2EaLaIHmp?= =?iso-8859-1?q?g5OINi09m+tQ6S9kmhmljUrSE9cOWGfTmNZwjnOHtJG6WSE4L4zfzT9jj6hr?= =?iso-8859-1?q?/qZUiEzFfoAQhKrgeA2GWHmLRG2f/bwfG8+6WOncOPchi0cEilBwsHkVMclu?= =?iso-8859-1?q?5JZT7jLUZZdqgQgEPR7+vrQrVx0acES+7OM7ijgJYXXjKUC8UxEbykfFP01g?= =?iso-8859-1?q?G4zor6tKxtq3m/2cPY+FKB92Nd1S4RA6gQ8D+Q+rZ4k9rupocJDliGIaWo0U?= =?iso-8859-1?q?78NBmIWorPtleyFBTtTSuBA6du16ZOrOUNa/ryQ8C3FMNRBywB3y7/o+coXK?= =?iso-8859-1?q?WA9Iz2Oa9zqhvU7IKiPk5ZMIfgQpHE08ducFZxZ5ziopu1fr7n0tDBpzViZj?= =?iso-8859-1?q?L1gJ8phakUM553PTW8aid0zihLUhzLzZw1vp1U7CaVq2PgU1EL+4mv0wpWll?= =?iso-8859-1?q?YtBa2qTBHgMZzlx2rw6G+h4b7oEoJI5Ffrd7tpaeQ9MxTMQAA1cdzbzkHWrM?= =?iso-8859-1?q?iSPRR4h+/BlxygwkAmAMPuEPqwa9oHg8Vgr3hJuQwW+kOIqFTW092sh7LfvZ?= =?iso-8859-1?q?YzteuFholWrlQsA0A+oy6yN821lFpznoFXOxjh+JAvAhIbhNXSa5l0uhlxFD?= =?iso-8859-1?q?/6b5H50k1qCM0HXEz8yVUw3458TACNhI9YyAKKiYXpbjn5zBKRPjiSg3YpJT?= =?iso-8859-1?q?uw8DrkakQNAAdY/lURYUjKiv8Y98CB9wL6iDajI+3nXhfH3MbQ7I6hpNnCn+?= =?iso-8859-1?q?qmym86HjjHR+fohJNAbI0uFusmDwXkjju50SJDk3MYKojuMC6OJTZ5DstM37?= =?iso-8859-1?q?BVDxduwF+FUkgbXJPWCsLR/Z2eZnV4wqJ6DRdBQYkmPOraonaMo3TR5WpiJ/?= =?iso-8859-1?q?cIStNM3xFZ08jvcrFhApntJqWmiDAfuUzUYjSWzaKYSMlp7ic+NK0O6dJoGl?= =?iso-8859-1?q?II0L95avoG8QVn069JMvcygKluQcf3RUDacQOFl+YtnBQJwQqPACTs+88iF3?= =?iso-8859-1?q?U?= x-ms-exchange-transport-forked: True MIME-Version: 1.0 X-OriginatorOrg: oracle.com X-MS-Exchange-CrossTenant-AuthAs: Internal X-MS-Exchange-CrossTenant-AuthSource: BL0PR10MB3011.namprd10.prod.outlook.com X-MS-Exchange-CrossTenant-Network-Message-Id: 137a54db-0233-462e-d3df-08d9879fb4e8 X-MS-Exchange-CrossTenant-originalarrivaltime: 05 Oct 2021 01:30:25.2474 (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: szDx47vjPojteSzUq8LEhiBn0q3yCIlfN+UU4da5Mcg4Q1g2SkKi/jnsIGro7Qe+3gAWR8HQyAT4s1d1xCByuA== X-MS-Exchange-Transport-CrossTenantHeadersStamped: BLAPR10MB5218 X-Proofpoint-Virus-Version: vendor=nai engine=6300 definitions=10127 signatures=668683 X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 bulkscore=0 adultscore=0 phishscore=0 spamscore=0 mlxscore=0 mlxlogscore=999 suspectscore=0 malwarescore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2109230001 definitions=main-2110050007 X-Proofpoint-ORIG-GUID: 0FNiRpI7kUshPnHzPdCAw0QhO9zEF-NK X-Proofpoint-GUID: 0FNiRpI7kUshPnHzPdCAw0QhO9zEF-NK X-Rspamd-Server: rspam01 X-Rspamd-Queue-Id: 29599D03C70A X-Stat-Signature: 4o5edz1u4i8jq9uenafcxdpz7fujyf58 Authentication-Results: imf21.hostedemail.com; dkim=pass header.d=oracle.com header.s=corp-2021-07-09 header.b="PFoR3/p9"; dkim=pass header.d=oracle.onmicrosoft.com header.s=selector2-oracle-onmicrosoft-com header.b="Jy/t32PB"; dmarc=pass (policy=none) header.from=oracle.com; spf=none (imf21.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: 1633397461-953117 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: The maple tree is an RCU-safe range based B-tree designed to use modern processor cache efficiently. There are a number of places in the kernel that a non-overlapping range-based tree would be beneficial, especially one with a simple interface. The first user that is covered in this patch set is the vm_area_struct, where three data structures are replaced by the maple tree: the augmented rbtree, the vma cache, and the linked list of VMAs in the mm_struct. The long term goal is to reduce or remove the mmap_sem contention. The tree has a branching factor of 10 for non-leaf nodes and 16 for leaf nodes. With the increased branching factor, it is significantly shorter than the rbtree so it has fewer cache misses. The removal of the linked list between subsequent entries also reduces the cache misses and the need to pull in the previous and next VMA during many tree alterations. This patch is based on v5.15-rc3 git: https://github.com/oracle/linux-uek/tree/howlett/maple/20211004 v3 changes: - Reverted unnecessary change to mm headers - Thanks David Hildenbrand - Fixed 8 typos in the documentation - Thanks Douglas Gilbert - Reduced the number of walks in do_mas_align_munmap() - Remove unnecessary resets of the maple state - Reworked mas_node_store() and mas_slot_store() so _mas_store has a more shallow code path - Added support for metadata node end markers to leaves and non-alloc nodes - Fixed lockdep complain on detaching VMAs, mainly cosmetic - Added maple iterator for powerpc, damon, i915, and s390 VDSO - Changed zeroing of maple tree in _vma_adjust(). Just overwrite the area. v2: https://lore.kernel.org/linux-mm/20210817154651.1570984-1-Liam.Howlett@oracle.com/ v1: https://lore.kernel.org/linux-mm/20210428153542.2814175-1-Liam.Howlett@Oracle.com/ Performance on a 144 core x86: It is important to note that the code is still using the mmap_sem, the performance seems fairly similar on real-world workloads, while there are variations in micro-benchmarks. kernbench, increased system time, less user time: Amean user-2 881.41 ( 0.00%) 879.51 * 0.22%* Amean syst-2 147.52 ( 0.00%) 151.16 * -2.47%* Amean elsp-2 520.65 ( 0.00%) 521.30 * -0.13%* Amean user-4 904.92 ( 0.00%) 905.51 * -0.07%* Amean syst-4 154.76 ( 0.00%) 159.14 * -2.83%* Amean elsp-4 271.53 ( 0.00%) 272.52 * -0.36%* Amean user-8 957.37 ( 0.00%) 957.04 * 0.03%* Amean syst-8 162.09 ( 0.00%) 168.37 * -3.88%* Amean elsp-8 148.01 ( 0.00%) 149.64 * -1.10%* Amean user-16 1037.05 ( 0.00%) 1034.01 * 0.29%* Amean syst-16 171.22 ( 0.00%) 178.27 * -4.12%* Amean elsp-16 85.17 ( 0.00%) 84.98 * 0.23%* Amean user-32 1202.17 ( 0.00%) 1164.72 * 3.11%* Amean syst-32 189.54 ( 0.00%) 195.18 * -2.98%* Amean elsp-32 52.93 ( 0.00%) 52.41 * 0.98%* Amean user-64 1236.16 ( 0.00%) 1244.45 * -0.67%* Amean syst-64 192.87 ( 0.00%) 203.73 * -5.63%* Amean elsp-64 32.53 ( 0.00%) 32.81 * -0.84%* Amean user-128 1609.20 ( 0.00%) 1608.73 * 0.03%* Amean syst-128 237.86 ( 0.00%) 250.98 * -5.52%* Amean elsp-128 25.55 ( 0.00%) 25.89 * -1.30%* Increase in performance in the following micro-benchmarks in Hmean: - wis brk1-threads: Disregard, this is useless. - wis malloc1-threads: Increase of 13% to 992% - wis page_fault1-threads: Increase of up to 15% - wis signal1-processes: 0% to +10% Decrease in performance in the following micro-benchmarks in Hmean: - wis brk1-processes: -42% to -49% due to RCU required allocations - wis signal1-threads: 0% to -5% Mixed: - wis malloc1-processes: +4% to -19% - wis pthread_mutex1-threads: +21% to -8% - wis page_fault3-threads: +10% to -28% Patch organization: Patches 1 to 4 are radix tree test suite additions for maple tree support. Patch 5 adds the maple tree. The bulk of which is test code. Patches 6-11 are the removal of the rbtree from the mm_struct. Patch 12 optimizes __vma_adjust() for the maple tree. Patches 13-19 are the removal of the vmacache from the kernel. Patches 20-24 make necessary changes for the removal of the vma linked list. Patches 25-65 are the removal of the vma linked list from the mm_struct. Patch 66 is a small cleanup from the removal of the vma linked list. Liam R. Howlett (66): radix tree test suite: Add pr_err define radix tree test suite: Add kmem_cache_set_non_kernel() radix tree test suite: Add allocation counts and size to kmem_cache radix tree test suite: Add support for slab bulk APIs Maple Tree: Add new data structure mm: Start tracking VMAs with maple tree mm/mmap: Use the maple tree in find_vma() instead of the rbtree. mm/mmap: Use the maple tree for find_vma_prev() instead of the rbtree mm/mmap: Use maple tree for unmapped_area{_topdown} kernel/fork: Use maple tree for dup_mmap() during forking mm: Remove rb tree. mmap: Change zeroing of maple tree in __vma_adjust xen/privcmd: Optimized privcmd_ioctl_mmap() by using vma_lookup() mm: Optimize find_exact_vma() to use vma_lookup() mm/khugepaged: Optimize collapse_pte_mapped_thp() by using vma_lookup() mm/mmap: Change do_brk_flags() to expand existing VMA and add do_brk_munmap() mm: Use maple tree operations for find_vma_intersection() and find_vma() mm/mmap: Use advanced maple tree API for mmap_region() mm: Remove vmacache mm/mmap: Move mmap_region() below do_munmap() mm/mmap: Convert count_vma_pages_range() to use ma_state mm/mmap: Reorganize munmap to use maple states mm/mmap: Change do_brk_munmap() to use do_mas_align_munmap() mm: Introduce vma_next() and vma_prev() arch/arm64: Remove mmap linked list from vdso. arch/parisc: Remove mmap linked list from kernel/cache arch/powerpc: Remove mmap linked list from mm/book3s32/tlb arch/powerpc: Remove mmap linked list from mm/book3s64/subpage_prot arch/s390: Use maple tree iterators instead of linked list. arch/x86: Use maple tree iterators for vdso/vma arch/xtensa: Use maple tree iterators for unmapped area drivers/misc/cxl: Use maple tree iterators for cxl_prefault_vma() drivers/tee/optee: Use maple tree iterators for __check_mem_type() fs/binfmt_elf: Use maple tree iterators for fill_files_note() fs/coredump: Use maple tree iterators in place of linked list fs/exec: Use vma_next() instead of linked list fs/proc/base: Use maple tree iterators in place of linked list fs/proc/task_mmu: Stop using linked list and highest_vm_end fs/userfaultfd: Stop using vma linked list. ipc/shm: Stop using the vma linked list kernel/acct: Use maple tree iterators instead of linked list kernel/events/core: Use maple tree iterators instead of linked list kernel/events/uprobes: Use maple tree iterators instead of linked list kernel/sched/fair: Use maple tree iterators instead of linked list kernel/fork: Use maple tree iterators instead of linked list arch/um/kernel/tlb: Stop using linked list bpf: Remove VMA linked list mm/gup: Use maple tree navigation instead of linked list mm/khugepaged: Use maple tree iterators instead of vma linked list mm/ksm: Use maple tree iterators instead of vma linked list mm/madvise: Use vma_next instead of vma linked list mm/memcontrol: Stop using mm->highest_vm_end mm/mempolicy: Use maple tree iterators instead of vma linked list mm/mlock: Use maple tree iterators instead of vma linked list mm/mprotect: Use maple tree navigation instead of vma linked list mm/mremap: Use vma_next() instead of vma linked list mm/msync: Use vma_next() instead of vma linked list mm/oom_kill: Use maple tree iterators instead of vma linked list mm/pagewalk: Use vma_next() instead of vma linked list mm/swapfile: Use maple tree iterator instead of vma linked list damon: Change vma iterator to mas_for_each powerpc: Use maple tree iterator for vdso. s390: Use the maple tree iterator for vdso i915: Use the maple tree iterator for vdso mm: Remove the vma linked list mm/mmap: Drop range_has_overlap() function Documentation/core-api/index.rst | 1 + Documentation/core-api/maple-tree.rst | 508 + MAINTAINERS | 12 + arch/arm64/kernel/vdso.c | 5 +- arch/parisc/kernel/cache.c | 15 +- arch/powerpc/kernel/vdso.c | 4 +- arch/powerpc/mm/book3s32/tlb.c | 5 +- arch/powerpc/mm/book3s64/subpage_prot.c | 15 +- arch/s390/configs/debug_defconfig | 1 - arch/s390/kernel/vdso.c | 3 +- arch/s390/mm/gmap.c | 8 +- arch/um/kernel/tlb.c | 16 +- arch/x86/entry/vdso/vma.c | 12 +- arch/x86/kernel/tboot.c | 2 +- arch/xtensa/kernel/syscall.c | 4 +- drivers/firmware/efi/efi.c | 2 +- drivers/gpu/drm/i915/gem/i915_gem_userptr.c | 3 +- drivers/misc/cxl/fault.c | 6 +- drivers/tee/optee/call.c | 15 +- drivers/xen/privcmd.c | 2 +- fs/binfmt_elf.c | 5 +- fs/coredump.c | 13 +- fs/exec.c | 9 +- fs/proc/base.c | 7 +- fs/proc/task_mmu.c | 48 +- fs/proc/task_nommu.c | 55 +- fs/userfaultfd.c | 34 +- include/linux/maple_tree.h | 485 + include/linux/mm.h | 54 +- include/linux/mm_types.h | 28 +- include/linux/mm_types_task.h | 5 - include/linux/sched.h | 1 - include/linux/sched/mm.h | 9 + include/linux/vm_event_item.h | 4 - include/linux/vmacache.h | 28 - include/linux/vmstat.h | 6 - include/trace/events/maple_tree.h | 123 + include/trace/events/mmap.h | 71 + init/main.c | 2 + ipc/shm.c | 13 +- kernel/acct.c | 8 +- kernel/bpf/task_iter.c | 10 +- kernel/debug/debug_core.c | 12 - kernel/events/core.c | 7 +- kernel/events/uprobes.c | 25 +- kernel/fork.c | 70 +- kernel/sched/fair.c | 14 +- lib/Kconfig.debug | 15 +- lib/Makefile | 3 +- lib/maple_tree.c | 6811 +++ lib/test_maple_tree.c | 36996 ++++++++++++++++ mm/Makefile | 2 +- mm/damon/vaddr.c | 3 +- mm/debug.c | 14 +- mm/gup.c | 7 +- mm/huge_memory.c | 4 +- mm/init-mm.c | 4 +- mm/internal.h | 81 +- mm/khugepaged.c | 11 +- mm/ksm.c | 26 +- mm/madvise.c | 2 +- mm/memcontrol.c | 6 +- mm/memory.c | 33 +- mm/mempolicy.c | 41 +- mm/mlock.c | 21 +- mm/mmap.c | 2094 +- mm/mprotect.c | 13 +- mm/mremap.c | 27 +- mm/msync.c | 2 +- mm/nommu.c | 120 +- mm/oom_kill.c | 5 +- mm/pagewalk.c | 2 +- mm/swapfile.c | 9 +- mm/util.c | 32 - mm/vmacache.c | 117 - mm/vmstat.c | 4 - tools/testing/radix-tree/.gitignore | 2 + tools/testing/radix-tree/Makefile | 13 +- tools/testing/radix-tree/generated/autoconf.h | 1 + tools/testing/radix-tree/linux.c | 160 +- tools/testing/radix-tree/linux/kernel.h | 1 + tools/testing/radix-tree/linux/maple_tree.h | 7 + tools/testing/radix-tree/linux/slab.h | 4 + tools/testing/radix-tree/maple.c | 59 + .../radix-tree/trace/events/maple_tree.h | 3 + 85 files changed, 46908 insertions(+), 1632 deletions(-) create mode 100644 Documentation/core-api/maple-tree.rst create mode 100644 include/linux/maple_tree.h delete mode 100644 include/linux/vmacache.h create mode 100644 include/trace/events/maple_tree.h create mode 100644 lib/maple_tree.c create mode 100644 lib/test_maple_tree.c delete mode 100644 mm/vmacache.c create mode 100644 tools/testing/radix-tree/linux/maple_tree.h create mode 100644 tools/testing/radix-tree/maple.c create mode 100644 tools/testing/radix-tree/trace/events/maple_tree.h