From patchwork Tue Apr 25 14:09:24 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "Liam R. Howlett" X-Patchwork-Id: 13223372 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 227DBC6FD18 for ; Tue, 25 Apr 2023 14:10:38 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 4320D6B0078; Tue, 25 Apr 2023 10:10:35 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 3E0DE6B007B; Tue, 25 Apr 2023 10:10:35 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 1E7D56B007D; Tue, 25 Apr 2023 10:10:35 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0013.hostedemail.com [216.40.44.13]) by kanga.kvack.org (Postfix) with ESMTP id 109006B0078 for ; Tue, 25 Apr 2023 10:10:35 -0400 (EDT) Received: from smtpin08.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay09.hostedemail.com (Postfix) with ESMTP id D98598010D for ; Tue, 25 Apr 2023 14:10:34 +0000 (UTC) X-FDA: 80720098788.08.D970229 Received: from mx0b-00069f02.pphosted.com (mx0b-00069f02.pphosted.com [205.220.177.32]) by imf02.hostedemail.com (Postfix) with ESMTP id 6D6EB80024 for ; Tue, 25 Apr 2023 14:10:30 +0000 (UTC) Authentication-Results: imf02.hostedemail.com; dkim=pass header.d=oracle.com header.s=corp-2023-03-30 header.b=ANGz8p4D; dkim=pass header.d=oracle.onmicrosoft.com header.s=selector2-oracle-onmicrosoft-com header.b=Ya+RUGa3; dmarc=pass (policy=none) header.from=oracle.com; spf=pass (imf02.hostedemail.com: domain of liam.howlett@oracle.com designates 205.220.177.32 as permitted sender) smtp.mailfrom=liam.howlett@oracle.com; arc=pass ("microsoft.com:s=arcselector9901:i=1") ARC-Message-Signature: i=2; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1682431830; h=from:from:sender:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:mime-version: content-type:content-type: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references:dkim-signature; bh=S1JH+3ln71WmML3vmtjGYSigdHsRHRx6Zm7HZXEzXVE=; b=aom86HSJRbxN1VIPr/VzZUHvh06VdfqylZoQG+mS0xeLYAwJW7YeQ+U+tfzCoaEH2cCqjr IbPgWhANZO6RAZma6uF5PcZj2CENCJUU8rWp3OlQn3l7r/JF3QzdX/kNtm1yaBjsI98G9B m+7urypEwVl8tS0KlONFjeE7UoeNy1o= ARC-Authentication-Results: i=2; imf02.hostedemail.com; dkim=pass header.d=oracle.com header.s=corp-2023-03-30 header.b=ANGz8p4D; dkim=pass header.d=oracle.onmicrosoft.com header.s=selector2-oracle-onmicrosoft-com header.b=Ya+RUGa3; dmarc=pass (policy=none) header.from=oracle.com; spf=pass (imf02.hostedemail.com: domain of liam.howlett@oracle.com designates 205.220.177.32 as permitted sender) smtp.mailfrom=liam.howlett@oracle.com; arc=pass ("microsoft.com:s=arcselector9901:i=1") ARC-Seal: i=2; s=arc-20220608; d=hostedemail.com; t=1682431830; a=rsa-sha256; cv=pass; b=IHOSaLq+gp7RNZk1ttP4moP5Q4HPU38/84yP8/e8BXvlxvhBJAcw5CvgCDHXKnoghgf2g1 9j4Rp6nK9W5c3AGEBl2qzklSZfrOKV6tEdkG0Qni9lDf2jX/adxua37RIa6BRXAnaaUuwf raeHOiBMyun9w+FeWouEH3/PXQe98ps= Received: from pps.filterd (m0246631.ppops.net [127.0.0.1]) by mx0b-00069f02.pphosted.com (8.17.1.19/8.17.1.19) with ESMTP id 33PDi75d024299; Tue, 25 Apr 2023 14:10:29 GMT DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=oracle.com; h=from : to : cc : subject : date : message-id : in-reply-to : references : content-transfer-encoding : content-type : mime-version; s=corp-2023-03-30; bh=S1JH+3ln71WmML3vmtjGYSigdHsRHRx6Zm7HZXEzXVE=; b=ANGz8p4DnPINu7jJetT1Bt/GrvETIyOpIGZrZVHQTDsoPDuE9hoA7ICn3MpC8PhdHIxK TZJ1wtnKzwUU5PaPz01bqTkOhecNQlho7D/unhpiIQSIwAb/YTMvEFzJva4rMGvOzbXt pYskYa1US/vjiVEKHgNecV6HkElfS8MDyAQF27qmU/CoVwi54oR+6KfMER2XfkO1N9B9 e3VX3uvTQLedIEfZdEklpHzhWa6ufT/MF+9H18K01SYOxDfrYda69thCjaOX8O1cNNqC E/zy08vA4+ZEQTpgm8tt5tvDX8G65gh/6taUHqKDCzAL82y/pmZ1Orredowt3fOGytga vw== Received: from iadpaimrmta03.imrmtpd1.prodappiadaev1.oraclevcn.com (iadpaimrmta03.appoci.oracle.com [130.35.103.27]) by mx0b-00069f02.pphosted.com (PPS) with ESMTPS id 3q46c45ftn-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Tue, 25 Apr 2023 14:10:29 +0000 Received: from pps.filterd (iadpaimrmta03.imrmtpd1.prodappiadaev1.oraclevcn.com [127.0.0.1]) by iadpaimrmta03.imrmtpd1.prodappiadaev1.oraclevcn.com (8.17.1.19/8.17.1.19) with ESMTP id 33PE6WY3024885; Tue, 25 Apr 2023 14:10:28 GMT Received: from nam11-dm6-obe.outbound.protection.outlook.com (mail-dm6nam11lp2168.outbound.protection.outlook.com [104.47.57.168]) by iadpaimrmta03.imrmtpd1.prodappiadaev1.oraclevcn.com (PPS) with ESMTPS id 3q461crb72-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Tue, 25 Apr 2023 14:10:28 +0000 ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=CXPH+xtRDKSQAcA7yVmH/2IlsHcFFtyhPievjCukigTKvBEG49aXHHsrCTTnPwjr4wbNwIAyBT1Y6YpQL+RfEw5O7hGrOFExCW8HB0ri6fkZ4D4qQE/65t9Rw25FV97S3S0nopq3TF4xo/EOlBEw3Gyiy7YKytEoFXOnmbt7TE6CfyP/1GY4f58y/MCcJtt115+PSKaOEu0hURbgtOTIiPZ5ffBt3cEoYY9lUZrXBHzknUTAP0HaYWxfUEB1umLiyXlj+4NfLsjtM3xcXTTJRb4w8fs51dy5eZ8J+CaBGeXXK7F3UVkImBoIcrnGOWM0aEeMRnrLLJmZSGUF+CeswQ== 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=S1JH+3ln71WmML3vmtjGYSigdHsRHRx6Zm7HZXEzXVE=; b=herTiNqlPbDyiXELaTU0NUQujSgN6+mrv5DsH23+JrQUaHN0vB+i2QUXxteZdaMhedcmw8gqhmL/vlPKRO+lVeTXS2PORZEUoxhs4Q69ToBlQdut6S4vqOEduE4h7cru9cjGhtq/vtfknEBjtX99qL14z2Fg7qFxZiunR8LC+sKMFEXw7Pa3NMleCKsPOxZQVP6Gqwft7PhDwB6e1Rs+FzTXr2J27gw5kufK+C458ONgGZ2Lgy0tb7GfV+ed7+yYQhguREhu+uQ4/fXRQH4z/AYStnc8atFc1OOL8C00KDIDIfo3oktvUhpI7mlXbd21ER0WyqJZcapg2gznigTZrg== 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=S1JH+3ln71WmML3vmtjGYSigdHsRHRx6Zm7HZXEzXVE=; b=Ya+RUGa31znEW6TsQACf4GDXT7YyooXMTM7DCY4/J3poSyKxaJ4P39/5JUmb1tWJmGzt78UH4sY4TQcNMHbo/3Wi033i34Yros47SAoRVKwFzb5gE1OQvB7oznyNZWQgiGH0ermvW6ni6cn20cnf0H0kUS+5oznSvNtYeaWvu60= Received: from SN6PR10MB3022.namprd10.prod.outlook.com (2603:10b6:805:d8::25) by PH7PR10MB6081.namprd10.prod.outlook.com (2603:10b6:510:1fb::19) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.6319.33; Tue, 25 Apr 2023 14:10:27 +0000 Received: from SN6PR10MB3022.namprd10.prod.outlook.com ([fe80::8bb9:2bb7:3930:b5da]) by SN6PR10MB3022.namprd10.prod.outlook.com ([fe80::8bb9:2bb7:3930:b5da%7]) with mapi id 15.20.6319.034; Tue, 25 Apr 2023 14:10:26 +0000 From: "Liam R. Howlett" To: Andrew Morton Cc: linux-kernel@vger.kernel.org, linux-mm@kvack.org, maple-tree@lists.infradead.org, "Liam R. Howlett" Subject: [PATCH 03/34] maple_tree: Avoid unnecessary ascending Date: Tue, 25 Apr 2023 10:09:24 -0400 Message-Id: <20230425140955.3834476-4-Liam.Howlett@oracle.com> X-Mailer: git-send-email 2.39.2 In-Reply-To: <20230425140955.3834476-1-Liam.Howlett@oracle.com> References: <20230425140955.3834476-1-Liam.Howlett@oracle.com> X-ClientProxiedBy: YT3PR01CA0107.CANPRD01.PROD.OUTLOOK.COM (2603:10b6:b01:85::20) To SN6PR10MB3022.namprd10.prod.outlook.com (2603:10b6:805:d8::25) MIME-Version: 1.0 X-MS-PublicTrafficType: Email X-MS-TrafficTypeDiagnostic: SN6PR10MB3022:EE_|PH7PR10MB6081:EE_ X-MS-Office365-Filtering-Correlation-Id: a81f3f01-5c29-4e68-75df-08db4596d19e X-MS-Exchange-SenderADCheck: 1 X-MS-Exchange-AntiSpam-Relay: 0 X-Microsoft-Antispam: BCL:0; X-Microsoft-Antispam-Message-Info: GG4wsptvSoMON9GaSjPnDm+U+ikYoZ3QdAYd/oG9W7GH+rT1gxVoBS2kI6P75i6ZJDGOC6Q9Cy6znpwGiSf5MG6vLlrPaq8dgUBB/pqsqGqidlsyYXEJCOVezwvP7cNX42i0N8cq7t146iwZqbA+kFvwW3wjcztu+FynijfQUNvNkNUUWJKCJoDZvNBrAYDg0G8+0MruRmrU3m/uQGapkWB7KkwnVbRkmhXOJWFg1PX+8TbawENFvz/DWfo4vnPzmI35rxcPT6XJDa37GBSvYM7kmWqf415MPt5v9sGrPUI0/omNOYs/2/A7dhQAbG4Xmx7R8pQo9mZxijulcMbQEMUINh+hLGQBgdH9pLmxJ51zmTELdiyBtdSpkzYp+Wx6w9H28EOakNbqvD3CSrpzgppwpLQDeJeBfLC0VK2RE5P79P/frgMYw3DgCUb4fjVUllrM6G25w/tqjs4LnSraXKU92N92dZK5q0Ranyhp30LOONRdA+sAc5DuoTKU1cUiHPKybTf/hkhrONiQZD4RTENK1ucC7OuloDbWe2LEClrtIXg2hGpJPxPVkkoXPTP9 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:(13230028)(136003)(396003)(39860400002)(366004)(346002)(376002)(451199021)(2906002)(66476007)(66556008)(66946007)(6916009)(4326008)(316002)(5660300002)(8936002)(8676002)(41300700001)(36756003)(86362001)(186003)(26005)(6512007)(1076003)(107886003)(38100700002)(478600001)(6486002)(83380400001)(2616005)(6506007);DIR:OUT;SFP:1101; X-MS-Exchange-AntiSpam-MessageData-ChunkCount: 1 X-MS-Exchange-AntiSpam-MessageData-0: b91YwAQ5UuSY5cCNYnNGJ25TspR5uZP2C70DZrJXyw12r/10Zw5TVplMg8sFB/o+ctZwDAmme9rqBF8pOZaMCdrM2TfaDmcoXFa9YOGubQib/Kuk61l/rciEJvLQV+zybIjqk1Fkpp9LP3pssEkcldL0CPDuFjJpADf/YeWgO4vGkswk/BWktSYzxfG2KibT5Kn3uLIJzvVgbUi1wXd11MrnwrczAXQgxuS7ci8jMhYzeEsGJI2rmQTPntxl0NegDR16/IMNdwivPMxW1q3A4V+YAkGlgktPV8weLG844ruEdDhmap2/DucfnonorgMFtD42U7m4sX7Le74n7TSbwU51j7NtJXlrqaops5/P7gC+TCwf+FIr09dwICoukn/+k1q6dygccPKT3cPSedOMZPTAaMMu0Sv9aihZ40xeG+HPloh+mozKECT2CYKUdH36hrkhUzVzn2WIbECRebWAmfn8VV53YM9zYXX8N9btCThVKw3PgI+8BzX4kl78J5C9iXKgvZraj5Lg4/22aLyZ/PkJEtTPcw2POmn4otwyq2ko7mCJlXliKWhIv97TdArhSyF0vzQEScrfqDBY9x3cwnv8ucKe9M9D1JUVTak5yubJCzecTIznS7oJCp9Jkpg04Kloy9qCcslTUzPTIn1pU2UPibeGeiolIQa9LAAbns+KYiY4/zkJbVQd9q/41psjSSL6KHKyG/wYIOH6LhKoaGFz4vW9tSaGVK8LRjpu9qGxEZsrFSakl+P84DiRKEkP9DqKOE3SK9Z6dOa1CUHh40NykY1dHtOAGV5qqPUGxBcdtnav24BFIMocmfFwX+qGJ868K5JuGeqw+bouW3LxaqTnRsWsv9KGgoICGGUSf3fjidqpJiCypdMemO8222yIz1F4ztuK1rC3bKwS3XkK0h5h83GR0cC2h4oNcwcrALdMhU9o/qsqlGjCpTiVPcnzdrAe+nH4NRdF59NxQZiYjK3AmtYm2QsdF4NqTvRCMCQeKBaa6hpeU/ZrF8Yc41l/14ucSl+tRIpIjS3r8erzgbd6LHXpvoG+La9IsBJPhjz07npXhJs7VwSS0fXrWqoK38dHE3fdTCQsEA3KWAfh9WuelAFrst7yCEI27wiIRaiJ3xemLJ9TlcDryefKqmebMAfiu7yKVxj4/Ty7oO0wsQvNJf6FekQRg9o27xe921SI+Vjz7UStleXITk+ygKP6ugdS3Qclx9wo9Ua7KC2xH68ha3xMxMEBQ9kdt5LIRDnl52j8dpiKNh4UDVofAUgx0BxOYOd80pXi77BJmNJmsPmuWI3ANt0Fkqow3zwMJ3/ggcfxq0JiMuf9fTaKGZowHvQzX4n1aJvxKOy5gXha/uIowCnE9la4j9GKtIpn4xPqQUAzV5QrDjAwWz2hLflxD4njgNaGzljwPyPKBRvuFtvRNqxeVVifPJQMW/NNN02pMrUKr/o7zvY8ByVAWX5KKoeVftB7svCHlHrE7j4MLGJRuFyHLdoPoCOBaOM4om/isHT9g04lLgUi3eFflE722t56wweRCytbEK4GkJH3M31aeMJ1HOQi6IOkx/mDlpcHP8bZHj/sMjlpnfg1JFFdO2smPMn+TPZBxvAGQ7u92Q== X-MS-Exchange-AntiSpam-ExternalHop-MessageData-ChunkCount: 1 X-MS-Exchange-AntiSpam-ExternalHop-MessageData-0: gIHCGXUnHjmKk/Jb2mlDnzO+CheBkKU57YISaWftZv5UaZS84pjgZVydw/WnRtXP6RR9WgQs8IFNme4YodVKCFYDmkc5GoYAmWskuHqjjccdLrBTtrjtRNn/K7Rcpg9DubJRZlM/PfVZhSJ2UorSQY8B3hRliSGGYun6DwWsZba7nIVuM0KN/lFQKzLwcyQrVPWCt1GSLK30W/LRPl9vDeaKNHGrK/pyfffu6A0Yo9JEJUKsxlRNgC2/JO97t2FaZrmAR+T+Z+TQvv6bEua3xY/L8iNRSaflrx3kkpvHcLgs+pod1MDgYOUJP2ct2+dO8QSXXGjv9IqlytzKeSD8nNRgYFOBzxIIX+Go7kPIECq8K9Gc95QnV8+s2joEwW8cCwKpvUVp9aKZTNrBjM/r+8P76YcAxh6T8GnebDO9vKGjL8zASVepCXCxsu4krMkpQ6vDV7gAi4m+fx0sMTVpHuAMYwbdmpn4q0sSQ5HetKVrJnGXa2bWS6hk+l66A84EUrVA/qeKZqzoVy5GytiwzYp0Nt8FPmQmEQ/hmWz/4ziiyRa/z69Tfxe1KgCjwoCRMCXLrEJpGyUxo3mwOOUJfdjZ12ka7l60FcCDzGNjZWGNirdVqkm+Vx+3rRZ2N7GQpf+p+VuFMT5E1jEdPo2nJtHDVPe21SUTrqtN7tylYZgCXtfe0w4mSMmNnCyS9DtXJA3Aos9aOsvvDphBUIoQPpYOUYSB0iPyJwIORDhPx/PVCmFDs36FDTgfn8VLh43HQIr0cmU5KaLxQbtjdqexv2Tty3YMfr76xysc+n1fDMbBYPGLbGZ8PMF3hJImQuSH1CdzwqNCo5JsGszZB7gX0hHboGJVkQY2ZpKltslBLG/fKr3/DUIE2Po8WVIGtE6hgBv83LvIGwCDNKn63n+pNg== X-OriginatorOrg: oracle.com X-MS-Exchange-CrossTenant-Network-Message-Id: a81f3f01-5c29-4e68-75df-08db4596d19e X-MS-Exchange-CrossTenant-AuthSource: SN6PR10MB3022.namprd10.prod.outlook.com X-MS-Exchange-CrossTenant-AuthAs: Internal X-MS-Exchange-CrossTenant-OriginalArrivalTime: 25 Apr 2023 14:10:26.8503 (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: bJRBxFBekFYI57r1Perx/IMNDMbRE4Hwi2hAAN+fufLhyzINPTp4KpDzU1i26itHvQXPN5TGB8+7yZjx0F+bQg== X-MS-Exchange-Transport-CrossTenantHeadersStamped: PH7PR10MB6081 X-Proofpoint-Virus-Version: vendor=baseguard engine=ICAP:2.0.254,Aquarius:18.0.942,Hydra:6.0.573,FMLib:17.11.170.22 definitions=2023-04-25_06,2023-04-25_01,2023-02-09_01 X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 mlxlogscore=999 suspectscore=0 malwarescore=0 mlxscore=0 spamscore=0 adultscore=0 phishscore=0 bulkscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2303200000 definitions=main-2304250128 X-Proofpoint-GUID: V4HQp_Vg_rE5oW5qzKzDHo32QKjSFKXn X-Proofpoint-ORIG-GUID: V4HQp_Vg_rE5oW5qzKzDHo32QKjSFKXn X-Rspam-User: X-Rspamd-Server: rspam02 X-Rspamd-Queue-Id: 6D6EB80024 X-Stat-Signature: i6p4qt153dp1ki3sob19rxkkuopzf57n X-HE-Tag: 1682431830-340822 X-HE-Meta: U2FsdGVkX1+toBFx0dnis0ZbpQ3PH4+RKxeHcNvny4lHwWp6Kr3alax6GXWxFPingf/mUCkFZLo3V+JxR+fR7W9V0Z+DGZvxEWoIDrSXwrCp0TG8T9TaDgxqdu+7DLIkGZC+W2xqPd2yQXipWWgNPcqjXzNYdf2IryQwKnaMTbIDnna5uJFvBPCDzK/ePXtfhoI2tTw0GzGekQxYJIac/kAZmYGYWhyj24Rbh8Fz6e3UcIsfGnejRoQYSpcPlTL/0k/lkJwgxB1vWokbN3Ec1OSjqmGVfK9PJD/sHdIyXVYwu5cOQshYu633nFJtyqa/Oq0H0FJj6oBM4gAcv7iDcU8d6/7nZU1vzUf+UoTOaOGHmvVY1txU5u0hBBU8u/9uPTaEijIk5g0NjNXzKFZbkhffmSiZxtu4hNFgDLzhrKDEb9OTmcilDjPJ1JknDtJmHTtx7lldD7KRi8VLwvugr2rWkyeLX7qusVJ/FLO0iSRI1NLozuMgFMJgL5Y4J/3hfwvgP2EZkvrAeprWPAr+Jx+jl+LQByjXjVd6XdKlWyFqjhUGNbCYcL9RUVveJW0z10xFAO063H1Hw+YDChjlLX4TSPGCLUFtS8LsIUPn2hArD9x2v3i1/GuRculZBIgditvzV1M47/emixURDVk1kzi46JSQU1U0y6d84kKsL6hx2eG/LqsIyNaJkGcQKynhBNqOlgKn/TNVJeEErTFixGCEU+q+x4YbqLmOgj4uq2opziH7TJF9gXkm9wseGfZh4fgGBB5nJ4edRPZvgY+jfEF/cDgF7aNNHXSs39aCmrRh6heUTnZqO8UQUDmMPaxihsPCumLf+PYRg7qRVbUq23Cqy0S0oAsILcmVj1fy5ZyBjKMejZBkTxuRyERrmMmf5wnPgZ1Fw2bb9+WdH8yanBsi7x1ba7hP128Lbm+fJQNIh8+nFGr+pj16YMNdpfBd5kCUWt8i4d3ENSC2pQB 4eBhp+oe uOF7dtDlqMeE6EWOOG1mDI6yxH7Ul3hJB93njllZ6cqw571EnMq3kLAM5S8w19zxMmdjHJoKMqTyCs10h90zL9kiOgh2EJZNmKOp+jqdywf4lgpkqCxnfvWR9L0rgWuC393UPoDSJ35CeLXuta/y4xrfQJA/pUh50zqVUu4v22EEedLgnUW8PyO/wOh3ljw/H1sM2cwyDSElYFtzp0GkE1Tn1L1vaFoO8naU+MQ4g7Vp5uzCRn0yOuJBWZ/1LvzffbE2+k5iPoSpvZHI9WxQOrwE9UdHaLqGnl1ks8VLFSRE4/PmTK3CsE/u0BK8MOBZBinl+GUXNTVcHvNKCS6Y95BeGKNcqEOgIfL2I/I//X4tOOLHOVb/lJUSkCdlSsj0wEgGW/zc/w3599Zp2qobjmLNs5jwbtRXVroLgVeeExdnhJ2I= 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 node limits are implied by the parent. When walking up the tree, the limit may not be known until a slot that does not have implied limits are encountered. However, if the node is the left-most or right-most node, the walking up to find that limit can be skipped. This commit also fixes the debug/testing code that was not setting the limit on walking down the tree as that optimization is not compatible with this change. Signed-off-by: Liam R. Howlett Reviewed-by: Peng Zhang --- lib/maple_tree.c | 6 ++++++ tools/testing/radix-tree/maple.c | 4 ++++ 2 files changed, 10 insertions(+) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index ac0245dd88dad..60bae5be008a6 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -1132,6 +1132,12 @@ static int mas_ascend(struct ma_state *mas) return 0; } + if (!mas->min) + set_min = true; + + if (mas->max == ULONG_MAX) + set_max = true; + min = 0; max = ULONG_MAX; do { diff --git a/tools/testing/radix-tree/maple.c b/tools/testing/radix-tree/maple.c index 9286d3baa12d6..75df543e019c9 100644 --- a/tools/testing/radix-tree/maple.c +++ b/tools/testing/radix-tree/maple.c @@ -35259,6 +35259,7 @@ static void mas_dfs_preorder(struct ma_state *mas) struct maple_enode *prev; unsigned char end, slot = 0; + unsigned long *pivots; if (mas->node == MAS_START) { mas_start(mas); @@ -35291,6 +35292,9 @@ static void mas_dfs_preorder(struct ma_state *mas) mas_ascend(mas); goto walk_up; } + pivots = ma_pivots(mte_to_node(prev), mte_node_type(prev)); + mas->max = mas_safe_pivot(mas, pivots, slot, mte_node_type(prev)); + mas->min = mas_safe_min(mas, pivots, slot); return; done: