From nobody Thu Sep 11 15:26:07 2025 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 vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id 979FBC001DE for ; Fri, 4 Aug 2023 17:00:35 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S231419AbjHDRAe (ORCPT ); Fri, 4 Aug 2023 13:00:34 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:36166 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S229762AbjHDRAb (ORCPT ); Fri, 4 Aug 2023 13:00:31 -0400 Received: from mx0a-00069f02.pphosted.com (mx0a-00069f02.pphosted.com [205.220.165.32]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 0767D1994 for ; Fri, 4 Aug 2023 10:00:30 -0700 (PDT) Received: from pps.filterd (m0333521.ppops.net [127.0.0.1]) by mx0b-00069f02.pphosted.com (8.17.1.19/8.17.1.19) with ESMTP id 374EiEkq002988; Fri, 4 Aug 2023 17:00:17 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=FX3AVzelaw6ITZi6EysUWnMmnKX/hf4MQkplrvHqWt8=; b=2YijfXjTiAbI8pZDFTkVBwIhoeuSdoPw2zUyJ6SngNzto+6LCsvOvv5KwOujCfpIC5Rx Bkwlzz9F4VvmEm45brMT8CPWr0WvGDVE+HOPR1H8lj2bOii1i3gxIWM52mNkbAUbhA3h rScIpQwlgRvxExsoYhr8WDMQNnKHpHrHo7CK42pnMgkr9wQvIMntsn2kvJr0Pwq9NTrc dzfWCfdLnBmnPUcB4n79P+S4N9ClT0PnmZIQr3caSYugua5Xcu/cmhRsOKjgg8/IfOUi Bm3CA1rdyzmZnSown8wX55UMvCLrTslGhq1oX4g+ygl2OP8H6T/k7VX5Bk7Zm1MRZMAp Gw== Received: from phxpaimrmta03.imrmtpd1.prodappphxaev1.oraclevcn.com (phxpaimrmta03.appoci.oracle.com [138.1.37.129]) by mx0b-00069f02.pphosted.com (PPS) with ESMTPS id 3s4spcc9v4-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Fri, 04 Aug 2023 17:00:17 +0000 Received: from pps.filterd (phxpaimrmta03.imrmtpd1.prodappphxaev1.oraclevcn.com [127.0.0.1]) by phxpaimrmta03.imrmtpd1.prodappphxaev1.oraclevcn.com (8.17.1.19/8.17.1.19) with ESMTP id 374Gt8Y0029324; Fri, 4 Aug 2023 17:00:17 GMT Received: from nam04-mw2-obe.outbound.protection.outlook.com (mail-mw2nam04lp2175.outbound.protection.outlook.com [104.47.73.175]) by phxpaimrmta03.imrmtpd1.prodappphxaev1.oraclevcn.com (PPS) with ESMTPS id 3s8m29bmms-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Fri, 04 Aug 2023 17:00:16 +0000 ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=TOZt6J+fR95OXDTDPq8mSe1+yIc414rz89GFy2D9Z95sXjUqlOBsGiNVTz4vTcUyew5ebVi9TE5OyAFWKMWPWKA5zauT7pbQ5zmYY6e29x8gdTOyEZjprYENdEY5I8wTAs46gDaxE0iIzpbZz9d7BEm9PhIn10eB70mZWXS4lnVNOxo3PIi6XmNxMuyh5WCH1F8YhShaH7pM4wqp90sUaKdPjceFI/mPtv+dvXn1cnGlT7FK+BmZk3oRkuzS51ayLUkb9vvY1Efn7vUNa5uti6c5EAq1Fqsgy7VK60RHLc3zjSCBVIx9zBh3B94P2/5d7ux3AQEK0mnFmSmJ09aMGg== 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=FX3AVzelaw6ITZi6EysUWnMmnKX/hf4MQkplrvHqWt8=; b=cximcLXJsO6Vtj6EykUo3Jp/LwVoxsfzTd+qkHFvGDVmFVAENpcD6B7sLSBFeU2bLYIOwzAGcOUYzKYBkOBk/4V0x5LVQw86aXqusy/5oA45m7NVcLlhwpeRFRzrMYtCQHnpqidGTiA5vxDDYJKv2ZfBmR9qflg+rxBUQrBylcJF3vSxja4gp/Z5CWvcas3S8XhRDsq3s2ItRCaTB1Vu0v8jX+EdhCoOyizzXN8FJyA0RImnOJ1g2m/ZVjGj4YrLRbr8/8W1ClbnYZfn/nt6t+zr8T92KfflgXHMm30CyYTosWbcVBRvEhWqG0eovrkDXTCvnaBI+l1/vC7kDKTN7g== 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=FX3AVzelaw6ITZi6EysUWnMmnKX/hf4MQkplrvHqWt8=; b=v7f5DHXDp4ghxTE+tb3rPGDm2IDu4iG4/CswdFtSWaem5kA3AYqWLg2XQuIuPnfiCUB6ZCsN5pYZGqY+cm0KdwsZoflaDEUn7n0O9CpxTfIkiEgLFII+XNWEf1mWdLEyxPDjnokBtnP8imU+/owHEudpzTcALkoYFEp8Xy0UiAI= Received: from SN6PR10MB3022.namprd10.prod.outlook.com (2603:10b6:805:d8::25) by CH0PR10MB4939.namprd10.prod.outlook.com (2603:10b6:610:c0::14) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.6652.21; Fri, 4 Aug 2023 17:00:14 +0000 Received: from SN6PR10MB3022.namprd10.prod.outlook.com ([fe80::26d3:6f41:6415:8c35]) by SN6PR10MB3022.namprd10.prod.outlook.com ([fe80::26d3:6f41:6415:8c35%3]) with mapi id 15.20.6631.046; Fri, 4 Aug 2023 17:00:14 +0000 From: "Liam R. Howlett" To: Andrew Morton Cc: maple-tree@lists.infradead.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, "Paul E . McKenney" , Suren Baghdasaryan , Matthew Wilcox , "Liam R. Howlett" Subject: [PATCH 1/6] maple_tree: Add hex output to maple_arange64 dump Date: Fri, 4 Aug 2023 12:59:46 -0400 Message-Id: <20230804165951.2661157-2-Liam.Howlett@oracle.com> X-Mailer: git-send-email 2.39.2 In-Reply-To: <20230804165951.2661157-1-Liam.Howlett@oracle.com> References: <20230804165951.2661157-1-Liam.Howlett@oracle.com> Content-Transfer-Encoding: quoted-printable X-ClientProxiedBy: YT4PR01CA0175.CANPRD01.PROD.OUTLOOK.COM (2603:10b6:b01:110::9) To SN6PR10MB3022.namprd10.prod.outlook.com (2603:10b6:805:d8::25) MIME-Version: 1.0 X-MS-PublicTrafficType: Email X-MS-TrafficTypeDiagnostic: SN6PR10MB3022:EE_|CH0PR10MB4939:EE_ X-MS-Office365-Filtering-Correlation-Id: 6b912ad6-9581-4633-6c86-08db950c4560 X-MS-Exchange-SenderADCheck: 1 X-MS-Exchange-AntiSpam-Relay: 0 X-Microsoft-Antispam: BCL:0; X-Microsoft-Antispam-Message-Info: d7Zktq7fjjhwSy+rvEgLak+wzE911BkqwjT30JR+5NLBLvX6PmGllI39s2KRGh0e353e7LWh33uV0fmtoNFtY+X0uXvBCc7H5UivO8h3qE8+mCXUNMrufOsa/2bDifO52EdJKcMp4o+aZzzCB24JXsPrdbTSznkA8CB2ux8MFzwKc0UohREz12U49U1DvdOjOUla2pVyPHruQuQMN5fdPnPa4syRHitCwm90NgATQvjBCFWkviWfFJFVYLWsm6f0MHf62weicQsq0XzxR+CRFppo7Zfxm3qOWL6knbOX1jCk0RoNDSSO5fFuu1rPKBVJzcZge44rg0A8SouZZM7RsBrlknlfEIW6QS7G3Ezd/JzCFv/YVWQNQwY5gimTuzZIsq5p0Lt7qrv6aIlcQebKQDPCCoKfb8djKTzSJzmVtliFdl/nIvZFBYI+kYUJz0RRzlQbZ4TM6nhjK9PR+HQRvi8Px7geqYafzAMUktTfzukq++/tjfCfggkvbu7zQIiAcn3EQNrHs2XnBu2C2NaKoB6zTSEfjS+nJN93u/805HiybdJ4nsxe2RBoo6YlL4EB 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)(366004)(396003)(39860400002)(346002)(376002)(136003)(186006)(451199021)(1800799003)(6666004)(6486002)(6512007)(86362001)(6506007)(26005)(1076003)(107886003)(36756003)(2616005)(83380400001)(38100700002)(5660300002)(41300700001)(8936002)(8676002)(4326008)(6916009)(66476007)(2906002)(66556008)(66946007)(316002)(478600001)(54906003);DIR:OUT;SFP:1101; X-MS-Exchange-AntiSpam-MessageData-ChunkCount: 1 X-MS-Exchange-AntiSpam-MessageData-0: =?us-ascii?Q?k6IQPoLcAFBnjWZNwS7UXw79/aOqt5nL0+9vwRb3qL1Bfipzab1E30JBr9rG?= =?us-ascii?Q?n90qnp5HvNSOyfQTUXASLn454GSXkXZuDRRW/mrJUVkPAV8MprUcAKxucadu?= =?us-ascii?Q?y1+KxuHgpELUZvtzV/YoIahlpLUhajbVVIEauyfF6BgiRNU6qenbGwFtpyc2?= =?us-ascii?Q?p+8M3F5BMUYc40sMuHfOnIzqkwmh53+LMNrvGRF7/8GPbUgqzKCPjEPvlluE?= =?us-ascii?Q?/76v9fzDx3yUL1kXtccovBQlnG6XVofovEdCECikpQ/nHZBQFThqayd1XpMR?= =?us-ascii?Q?nfVO3PEDMUZpVVPJCNBOlldL6Vcl+IJ/RnA7tnCnDeXu433D3NfuQxYaPyhe?= =?us-ascii?Q?fcPfS0nrPLhzVmrvXZ17YYkS9/Yn6zsQ2pudnoBOtAKNQmFE+E3EuBHj7kdL?= =?us-ascii?Q?fsQJFyUs2klkjJtsOYHjxQgJCx+JV3iYVX0yp6PM8v7yvSgfc8eS+fkwts1e?= =?us-ascii?Q?oiIYQrpfXb/lQ6PuXvjihwVfU+orJoE8ihLAIgq0/dL3Qg9DPfA5UxHiS6is?= =?us-ascii?Q?ey+FKfP/awmqisMSJc7nJNcKCErS4yU4Ah012BGcJ4OU5CNWLIO5m97jtBPv?= =?us-ascii?Q?ryrjH0lFAgz/w/a7uy9NUMgLYPtnJaO1Gjq1mjj8c8L8ApwfWx7DyDKWp4Hk?= =?us-ascii?Q?UCAvUb8LliT10IeKGasPRF68xVDwkYROMQbTYAWgKuxawcJ5rK5xwrFG5LN9?= =?us-ascii?Q?6Q+LGufhZ+/LtOBbIZ2I+Wn7aj8dBEAxCS8bf4YEn7JBi5rvjxZHj8Bzqp1T?= =?us-ascii?Q?TCUWZBn1sYE/y0u4qINAt2bYYpUdunnyTO1hCzOPvVc5IdTrvRcRQSOseAEP?= =?us-ascii?Q?7KAuMI0fhbJBdlUlI/hvM/5Qlb9VZwPjsjGyuZ4dPMYaldGswWCm74AW112i?= =?us-ascii?Q?6OCOsSpAJJOFyXRzniLRqX0lcgCLpSBI1JpZDkeayqfKLuA775QmI9X1tJVz?= =?us-ascii?Q?JOc0y8ffn6EMlHqHV8mktSNanN9bV5r0mv2G1tkrye1PNh8K8Id3o4HBgr0+?= =?us-ascii?Q?eS9apu5wGP5cRMYnmKwn4Pj1I0BIcqIcjddBvzBHH8paT583wY15UU5El3qz?= =?us-ascii?Q?Dm8RsW0OJ94ZNy0DKzTHb6+gZcnvkcCEf16OrUtVsZCd9OnJ7LzK67YrkdaX?= =?us-ascii?Q?r0lblatu9hHIwoRbyGMkbU7JyFVc4b1HfAKlRLIWPFPQDTKBxNqxDp41bQuJ?= =?us-ascii?Q?vFcQJ8gf0ipGCt17HZT6Wz1XI1aLdej27k5OJIekb6IZXN4bnz/831l5ip/G?= =?us-ascii?Q?u1dzkJxfepAmIIcQbA/C+vnae7DBu/L5ukdFZhLcu4nWyCMCyohPb5mPE/0E?= =?us-ascii?Q?Uj245v1LRljdJaymDvoUo0o5pPvDEFFpHUlKt5YcH5c3kkLhuW0K5jDiLw9Y?= =?us-ascii?Q?8WuaKAhqMLCbDRlMIQ21W4HxxYZdI0V5YyGwZ8CNnVNiVYBcoyvrfvZqis0Z?= =?us-ascii?Q?cyWJdV2oMuz3lrU5azQS/Nzous4qhMDPejdIwV/P0U1Oz6UmzqvGt8HI3tua?= =?us-ascii?Q?WcCYT8qMXdcDQFY1/L02o/fe//38BfN6l/S0fDTYxKmE78f9QQiS0L+Ee2Yj?= =?us-ascii?Q?UgtHwZMlGQJPhmwf80b2U82GEU7QxAHDLQopml1vpHzzRznniz8twW/ip6UQ?= =?us-ascii?Q?4Q=3D=3D?= X-MS-Exchange-AntiSpam-ExternalHop-MessageData-ChunkCount: 1 X-MS-Exchange-AntiSpam-ExternalHop-MessageData-0: =?us-ascii?Q?Dw1Gb1g6ISuF8arsAOWKcyJQS/uE9wsm1W5QnowOz0WwtmDSWPCt7dAO8NEX?= =?us-ascii?Q?3vP7zxBqbWhEy4pww2G1Yov2+s+7V5eBz2HVuedUdxNYqBQoBdYj3a8Iugzn?= =?us-ascii?Q?8HcAAWH4yAgY0rLnCOEgO3jzSoFAQOswQ1pVbgZUp1ZZMrJB8HBf6EFaWnRw?= =?us-ascii?Q?RKU+5HxocBorfS7UhB0FJbQvJIpJr7sTbIjxt1Bq4g12UYY2JyA5NfJDUYnm?= =?us-ascii?Q?nigX1aILltdJyS8nvCrKJ3E/PN/4S0cDQqqhYrTtpIQ9qFEPWUfuYxeYcTNK?= =?us-ascii?Q?yi3XIdLVeXzyj9nqpjiSRM9mgIz0pp4VOoANz7qKg0s2syelg612VY798/ts?= =?us-ascii?Q?Mi7y7PLv3MqMjH/mGn1m0L4vg9Zdp0840TdBFh52evBILcd/quGiCdlz1suA?= =?us-ascii?Q?MUUqQdmxqfWBdQu77YFNUqVcP1fIU1M0HA+fLtqmepAP5efa8DFbXOFuV6oT?= =?us-ascii?Q?OgfG7NHCMHnsG7o4zxez1iZCZEb3VnL3khyPD5xSaZp/vy6BQ2Wdun4HiRxP?= =?us-ascii?Q?y7lZxjGWrZ2aScDd0QHvk+w4G80QZf0+QMQWJRpSB7x5xDKcAQUNG9BMu9vz?= =?us-ascii?Q?em/R//rZn6T+oyd0Cr0N6yvaQfL106Mf8UYPE0P/Ucpz6xDwuZIK4agMr2E2?= =?us-ascii?Q?QfealzrGqwvNipYLMpWV1PVG+yt4vuBSelfzFUYmfSE9ohUX8IuMa8uezmKM?= =?us-ascii?Q?PIik6TDL6o68LeURzXcw+de7dVgy1kWqcnX3Tcf6k8tLMnqJFH7TsKDYPyaY?= =?us-ascii?Q?k1yaqnWDMQdBzGEyuFRh82PBghTU3pu0DTHzxqid+B1P88utmSqFFO1rScET?= =?us-ascii?Q?ooxDQheDjipuKffOyH+w3Xlb2jLOlNob7lOuVeXmYFajUFYCGTNKNnUBRCGB?= =?us-ascii?Q?zahhJqOGEeTTzkSNCR0uEjcsouG8wkPVZI/GOUm+EAHaETnG5orPC9VIJP9D?= =?us-ascii?Q?gM0DWG4KwovWgzn+yUoqkE8QLuYsffAD+EfGi2OOQYs=3D?= X-OriginatorOrg: oracle.com X-MS-Exchange-CrossTenant-Network-Message-Id: 6b912ad6-9581-4633-6c86-08db950c4560 X-MS-Exchange-CrossTenant-AuthSource: SN6PR10MB3022.namprd10.prod.outlook.com X-MS-Exchange-CrossTenant-AuthAs: Internal X-MS-Exchange-CrossTenant-OriginalArrivalTime: 04 Aug 2023 17:00:14.0317 (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: ZwStVAYx/5TY+2sIIgw5sl1Pzvjdrd7oNXb0hgzkM4eMRBuiTQQXqaYNwZPRh20CO8y6DRSgo2pLCCPeSjM4Rw== X-MS-Exchange-Transport-CrossTenantHeadersStamped: CH0PR10MB4939 X-Proofpoint-Virus-Version: vendor=baseguard engine=ICAP:2.0.267,Aquarius:18.0.957,Hydra:6.0.591,FMLib:17.11.176.26 definitions=2023-08-04_17,2023-08-03_01,2023-05-22_02 X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 suspectscore=0 spamscore=0 phishscore=0 bulkscore=0 mlxscore=0 adultscore=0 mlxlogscore=999 malwarescore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2306200000 definitions=main-2308040151 X-Proofpoint-ORIG-GUID: T-VwZFYPxZ1PUH_Y7Vj4TK1BF2Xb-T4a X-Proofpoint-GUID: T-VwZFYPxZ1PUH_Y7Vj4TK1BF2Xb-T4a Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Type: text/plain; charset="utf-8" When dumping the tree, honour formatting request to output hex for the maple node type arange64. Signed-off-by: Liam R. Howlett --- lib/maple_tree.c | 24 ++++++++++++++++++++---- 1 file changed, 20 insertions(+), 4 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index a3d602cfd030..880ce0fcdcac 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -6833,11 +6833,27 @@ static void mt_dump_arange64(const struct maple_tre= e *mt, void *entry, int i; =20 pr_cont(" contents: "); - for (i =3D 0; i < MAPLE_ARANGE64_SLOTS; i++) - pr_cont("%lu ", node->gap[i]); + for (i =3D 0; i < MAPLE_ARANGE64_SLOTS; i++) { + switch (format) { + case mt_dump_hex: + pr_cont("%lx ", node->gap[i]); + break; + default: + case mt_dump_dec: + pr_cont("%lu ", node->gap[i]); + } + } pr_cont("| %02X %02X| ", node->meta.end, node->meta.gap); - for (i =3D 0; i < MAPLE_ARANGE64_SLOTS - 1; i++) - pr_cont("%p %lu ", node->slot[i], node->pivot[i]); + for (i =3D 0; i < MAPLE_ARANGE64_SLOTS - 1; i++) { + switch (format) { + case mt_dump_hex: + pr_cont("%p %lX ", node->slot[i], node->pivot[i]); + break; + default: + case mt_dump_dec: + pr_cont("%p %lu ", node->slot[i], node->pivot[i]); + } + } pr_cont("%p\n", node->slot[i]); for (i =3D 0; i < MAPLE_ARANGE64_SLOTS; i++) { unsigned long last =3D max; --=20 2.39.2 From nobody Thu Sep 11 15:26:07 2025 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 vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id 76E0FC001DE for ; Fri, 4 Aug 2023 17:00:47 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S231535AbjHDRAq (ORCPT ); Fri, 4 Aug 2023 13:00:46 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:36232 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S231477AbjHDRAj (ORCPT ); Fri, 4 Aug 2023 13:00:39 -0400 Received: from mx0a-00069f02.pphosted.com (mx0a-00069f02.pphosted.com [205.220.165.32]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id D2B861994 for ; Fri, 4 Aug 2023 10:00:34 -0700 (PDT) Received: from pps.filterd (m0333521.ppops.net [127.0.0.1]) by mx0b-00069f02.pphosted.com (8.17.1.19/8.17.1.19) with ESMTP id 374EiDF3002950; Fri, 4 Aug 2023 17:00:20 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=u4CFjppFxp9l2MaITKNmsStPN7oSuRkt18qYVROXvto=; b=eYdumrFqyYhH4qPEX/i+0YDHILjZdjdwZj3bHwLlv32izcpXTLGhilcy2fF5Co/3iCiw aVkeL6r3J0RATkpgBR0bujYMoDSYRUaeWlwQqjeH/W630tev1HsNVkZhkvld2/R8KaGW wWe/APJEzeAj8ZQcyRwbzs3UK1fc3F0/0focCN7gQoa20jptC2HQo7PrcAODHBoyRYme fo/cn44Esn8384iYmK6PL8/0fPJJaG4uVJX3je+ht4KavMzGkdXpslBlPw20L2peoDvC KeCuDrWGwDVX3m3RqyI57CAORTrHYFdi3Jzt/v1KqgCmx8XuB/LZpGKoGFQ8U1XxyuUG iw== Received: from phxpaimrmta03.imrmtpd1.prodappphxaev1.oraclevcn.com (phxpaimrmta03.appoci.oracle.com [138.1.37.129]) by mx0b-00069f02.pphosted.com (PPS) with ESMTPS id 3s4spcc9v7-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Fri, 04 Aug 2023 17:00:20 +0000 Received: from pps.filterd (phxpaimrmta03.imrmtpd1.prodappphxaev1.oraclevcn.com [127.0.0.1]) by phxpaimrmta03.imrmtpd1.prodappphxaev1.oraclevcn.com (8.17.1.19/8.17.1.19) with ESMTP id 374FJgoG029618; Fri, 4 Aug 2023 17:00:19 GMT Received: from nam10-bn7-obe.outbound.protection.outlook.com (mail-bn7nam10lp2108.outbound.protection.outlook.com [104.47.70.108]) by phxpaimrmta03.imrmtpd1.prodappphxaev1.oraclevcn.com (PPS) with ESMTPS id 3s8m29bmtm-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Fri, 04 Aug 2023 17:00:19 +0000 ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=WrVIitj3IUCky6F5fD9u7X31poirUjinnNhoJVR6qh7boNn4gHkKYGtr3oldmApl9+QtXGkfBR1GpplbaNCf55ECuR1O8FaSRmv1c3gd2vo2oSivfqlP2gwBYs2Q/bj5NyAt/gtNcXfMY7aieIw5s6bojik+acYP1wDN+w0euQHheE91o5SCefMaFfAR58PwK7vV1yIDnpMyxmDrSfYm21mnyBQXAPg3MmH5PrLseergrOtcj7EeOFqE1L01gbWn84j15w9plfop9Q0NDCpQPSca/UKIc0mj5S6WLYpeXJiq4lfu4kdah8fZP5JEJNowhANGs3odCEqH1t9XMOLy6w== 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=u4CFjppFxp9l2MaITKNmsStPN7oSuRkt18qYVROXvto=; b=g+qWeLZo7usR/KWrSY8m7wNw/O8PO32pRdPAb3IQ+BLjWEtr0PBRvNTMiNEULDjobaGBy3UeUGrGser5pcdQWcP1ZSJVwOWBWKnNYAGqjjhfq9v+oeYI1ULSZaDGr+B2LValyRV5QdLClJx/epFkdDSlrDOcxI7NvjuoJmN3+TveQ09OAY8utD9BA2c/ieReLlxQ+/0MW/LU5ykwwhs3ZiqbSGEYHHIWy6j/Rg80oCTN4afS7B+4RVUv6jANxfN6UFhif5w0hHPSAkGu63J8MMHGLZiJzJvl5Jx37dhKmGC+QAGA94OIY+JHYgffaHyrht75kIBWD+TbWTF1FxmTeA== 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=u4CFjppFxp9l2MaITKNmsStPN7oSuRkt18qYVROXvto=; b=QXSeBrbrKegpOXrUs3h8PJt131fnQ//0JVG3wkyVS1+2FZevwMwGek/RUUHw8/0yJNpyXtuEY/SFD6MiOXya7/9ltPCsSqExsycdS57/tygpK0ALX75A5c+QH3TpQ4m1UZBv5mMCDWdmQXEIWteq9DtsK5uQxK2v0jF+IJyEsJM= Received: from SN6PR10MB3022.namprd10.prod.outlook.com (2603:10b6:805:d8::25) by CH0PR10MB4939.namprd10.prod.outlook.com (2603:10b6:610:c0::14) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.6652.21; Fri, 4 Aug 2023 17:00:17 +0000 Received: from SN6PR10MB3022.namprd10.prod.outlook.com ([fe80::26d3:6f41:6415:8c35]) by SN6PR10MB3022.namprd10.prod.outlook.com ([fe80::26d3:6f41:6415:8c35%3]) with mapi id 15.20.6631.046; Fri, 4 Aug 2023 17:00:17 +0000 From: "Liam R. Howlett" To: Andrew Morton Cc: maple-tree@lists.infradead.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, "Paul E . McKenney" , Suren Baghdasaryan , Matthew Wilcox , "Liam R. Howlett" Subject: [PATCH 2/6] maple_tree: Reorder replacement of nodes to avoid live lock Date: Fri, 4 Aug 2023 12:59:47 -0400 Message-Id: <20230804165951.2661157-3-Liam.Howlett@oracle.com> X-Mailer: git-send-email 2.39.2 In-Reply-To: <20230804165951.2661157-1-Liam.Howlett@oracle.com> References: <20230804165951.2661157-1-Liam.Howlett@oracle.com> Content-Transfer-Encoding: quoted-printable X-ClientProxiedBy: YT4PR01CA0456.CANPRD01.PROD.OUTLOOK.COM (2603:10b6:b01:10d::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_|CH0PR10MB4939:EE_ X-MS-Office365-Filtering-Correlation-Id: 7868e07f-7abd-4d31-c7b8-08db950c4708 X-MS-Exchange-SenderADCheck: 1 X-MS-Exchange-AntiSpam-Relay: 0 X-Microsoft-Antispam: BCL:0; X-Microsoft-Antispam-Message-Info: pVgEEq0a7N5gMOXBNiGz/MvTEkOsQAjuthf3BC/2wAOiVnKwxuj12rBGIdT/iJRG7o0wJGif8PxMf/SENfbpHdStJ0Anx9ivwtF0lAyieyxLi0RoikmQas/JFlpg85708E5+RM/WU/CP3a9+pHjenecAHs2erzqcxEukTo4uIME62phS9gPAeL+oAAi1Tx6b747eQ8RswOqy8j4kOhDncCU1duQ3GEWX1HEUQ2wDVERLrDkK6OQFm/EgVE803EPNtPUSntQRmE9Z8EzqXOgZBTveJBf+4OmqtOkWSW3Y7hyB0RYy2XYcvGW+ypjtVv7FsPsod+Y10QabgJUVla75xNydicKyPewigOU1VeaLWmiuCvVBowW2FN7mBvt5F1qismXeOpARm6hjIXzSqhNjzLZiXdG5eRAvai/i5lKi0xCjxNnuI0ZNTkyzM1e53LdUD2aLidfqbEotIuZp4po2aqTM1JhenlwZOQk3PoW0dKd+AdxLd2xK4WRfBvtkBjp25Zh5USlLFx85ut3U5L04xBuEST/e2qzBlwO4esd+UpeGIuqTaWg/+dgcBtmvfQcp 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)(366004)(396003)(39860400002)(346002)(376002)(136003)(186006)(451199021)(1800799003)(6666004)(6486002)(6512007)(86362001)(6506007)(26005)(1076003)(107886003)(36756003)(2616005)(83380400001)(38100700002)(5660300002)(41300700001)(8936002)(8676002)(4326008)(6916009)(66476007)(2906002)(66556008)(66946007)(316002)(478600001)(54906003);DIR:OUT;SFP:1101; X-MS-Exchange-AntiSpam-MessageData-ChunkCount: 1 X-MS-Exchange-AntiSpam-MessageData-0: =?us-ascii?Q?9M437dGkuFLrkEsKZm60ZHDhqnZ4k1Ek39n/DcMvvfmmhHqen9lgsQkBznUh?= =?us-ascii?Q?WQPN0ssUPggLJY65NJc9bRao6a6+aR+fLgEyQ5DVRAqaTVpsPvylYgt3UoAX?= =?us-ascii?Q?TF3kza6/A8PRXoE3JchOFBsE22pbM1aokDzdaQ399rHJ6piIo4SN4Jro5pzf?= =?us-ascii?Q?L2iW4JOqif7TDtPU11I9WYRFn1ZmGSw7LUV4zPtxCzpxSx/FbRuFUK3C6zTZ?= =?us-ascii?Q?h4EXl4tgk9Ux59mrTc93i+Gt9t0bDHHpXXNCh0isX2wKKZmCIQmhPOwUx0ei?= =?us-ascii?Q?uzBdtGI6tUliuRdX+Nufg/7vZYJpCyhpY+6xCDW55TsVHFKaHf41DZ8t6SA9?= =?us-ascii?Q?kSYQI2ISP+IbFJAfYK8vMF5VaWp5HxukVGRklxL37sPVkTthIhwkLcHRq6TX?= =?us-ascii?Q?o0C7BJGPyuQBkzie6ZbPoJanqwaOqU1b2iDbuyMtcjCXl+Qmil4+FQBBhZPf?= =?us-ascii?Q?nvl7Rf+suq4SyXCZE7u7DjsXFFuiZ28UHRWnv1AcX6Eo5CVoUWFbQ97/kOr/?= =?us-ascii?Q?eAfCeCKeQWEskUfjKkrxbQ4HK22hh9SMtP4NAMe7mXogjBQ57xjPwBJA3VkY?= =?us-ascii?Q?ZtjFWwRqn9LhKLimTTDQlBtnhkn+/FjBc/QDXfBERfrjoBx5rr8LBMk3Lfzw?= =?us-ascii?Q?6+yk/4hi2cjnkf9ZMRSvtyB6dcPaS5jSiAoPXMJgyT+giKvhcyYBnQ/lfkp5?= =?us-ascii?Q?F2kJH7unYj6DTjCrD/YQJotgq8mOgbT2jl2RiEQ0NXepnWVe6oJEHZiAxhCW?= =?us-ascii?Q?NB3XfPRwBCYOkJVjVs2kJmVgN/1dPeELJwLpzEE6wuz8jOEVa13DYxWyYeqO?= =?us-ascii?Q?lr64KOUI2oEWWijoT/+MBbf9ZpeTEveBiptRVhnHArZyg6fJonHOPgR3OkrH?= =?us-ascii?Q?Ka27VfMhfg58bv8WjoalVZd2l2fPDgSkOt/N/PtJp5CV8ptYzDer05A37WoY?= =?us-ascii?Q?XVSTK7ZumK1r7VspSeFXPfWqH8HMpN32cXq+3f6dW5t+ifpOu2VCL34Zqt+L?= =?us-ascii?Q?ODvNLN95i6fkUZBChD4XF7FKAWQ9PPcbg5PHXZCBKbbLXudF4zvSRuBYs8AC?= =?us-ascii?Q?J4T+YR3gj2hkblizjBmUHXd/7lHmPtxXNh0HEAcrgkrH2J0i67CC2zMvTsB6?= =?us-ascii?Q?yefYIHhNJpTME6xzLBRWO9JLK4ulKz9G+FyF6yXoA/UGeaGTISJVxGfkE7ZE?= =?us-ascii?Q?gf4Bb/s/0wI2ZKRLQvF70BIW8sbAGJ4JRRPm84CklbejC0MDre7vJ+ERKEra?= =?us-ascii?Q?Om6Mxt+WW9ini8IeO10+r/AsUBlYyFgEdOQQfi69Vk+yPnjzS+yrTbXG9XKr?= =?us-ascii?Q?j9uN03JZ4PjBgRRqy1da0my9uSP7BMC2Y/Q/M63dCb5BDOtDNxS4xcP3L+3J?= =?us-ascii?Q?VkbRnhx/WpwY8raBpra3tXbVdC2mzvYM1WZCTXSQSKQYSCdKwYgJcywC5L4v?= =?us-ascii?Q?A4NdV0jpge46ObT+A+gxUz2wPb2NSaK7o83q6v/mmK6tDl7sWogvdKyeMcFX?= =?us-ascii?Q?5vbvFFEZqkCa8igcghpwfhyl0ICoz7vlMvDTw2ajoQaO6jmUwb7ppw78MwTl?= =?us-ascii?Q?YHq//iGUIbNop3rliQVq/ElF+HOvq2AcPTQ4Ndtk4jRC0uXBKQD8Ey6exvI7?= =?us-ascii?Q?XQ=3D=3D?= X-MS-Exchange-AntiSpam-ExternalHop-MessageData-ChunkCount: 1 X-MS-Exchange-AntiSpam-ExternalHop-MessageData-0: =?us-ascii?Q?CjbESMqePxQ4FdHqzZwDtl2MTFv/o2ikj/vHXfTRhmDFQMrjf4LRzbxsGNXn?= =?us-ascii?Q?6oOqHee1Vv0HdMhJGCwq4Dp5+wePmhm75n0EfZWwCCKRRAW/5a3+Uuf+jQ4x?= =?us-ascii?Q?pDZKRo83vgBQW8u9RpYKSl0NaRKRpt9Fxv6gBlxNn6lbPFtZx+/bs5OMESZx?= =?us-ascii?Q?sVMAHm7U8FcDLgm/rNNaDFxFPi2UlP+ilg24ktEY09hVsKHIhe80ruNDzAKm?= =?us-ascii?Q?jSUwM4E+HHcEHYI9yenF3yNd7F/DhUZDSoKdyZ7T9xMjl1LJE2aidXip3Kz/?= =?us-ascii?Q?E77pOh8cVvMUL72oiYrJKrKAeD3/eGxS0dm7K9511GOiJ2XsB4ZtzFDwW9e1?= =?us-ascii?Q?ERJV55rpZRjC3+szofg3jCA731H6g1cv0aSrfxmFQP05n9wW7wSqrI99koFB?= =?us-ascii?Q?Gi6CuzOsb5GYq+9tsmM0d+7uwWe4BWhBwUHL1nCr0MvXYVC3kBSxfoqKsU16?= =?us-ascii?Q?n40peWpFwsbHh+0FAfPTQDXWmfKhLCntrskeIeeiWpQwqGe0ZQzWFwBWQl6o?= =?us-ascii?Q?E9k7l+CqNLxBoiHyOPFRQ69ZPir4bL3K9RH7FROdeodfTOZxjm7aTRPWLNvg?= =?us-ascii?Q?3wwIXnnswmAkPhAYXWSfmU/Jax0hf13X9EBoSXG7zujXQVO+l4cc63sjY9R5?= =?us-ascii?Q?+kgsWJancw8YnsQuXeLCRiS6QfAoOJ0ZaHh4VW5BGXIeuAjKOWS44OWP4Nu3?= =?us-ascii?Q?OEOp9xwavfdoj3cmcRnhpA2wDPjZI4FhhJ4ylquiIAdxSYjuY0ybTntAgLKA?= =?us-ascii?Q?MbUIq2nOQvr5tfAGMr6X2B5bpV0SVGVFxQyUZR+G31uTNfJQOG/z7GMJ3Dz5?= =?us-ascii?Q?qApTs8KpdHJcdjskXLfwj+b7+0S9e6ENw0bZYnG0768jhnTXkC5DtMwu+d1F?= =?us-ascii?Q?3ThYpBGl6swLo9oKdceFP4h5VIVrO6Qpv0t643KpnFmCM6GsHMeVlYXOfeQo?= =?us-ascii?Q?gwZT6nxuse3258ASp9VSzpizAi3a0PY7Lfo465+LeBU=3D?= X-OriginatorOrg: oracle.com X-MS-Exchange-CrossTenant-Network-Message-Id: 7868e07f-7abd-4d31-c7b8-08db950c4708 X-MS-Exchange-CrossTenant-AuthSource: SN6PR10MB3022.namprd10.prod.outlook.com X-MS-Exchange-CrossTenant-AuthAs: Internal X-MS-Exchange-CrossTenant-OriginalArrivalTime: 04 Aug 2023 17:00:16.8120 (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: yM3cU92b+h4k4v1Mw/dw1AEpX6lRMpISHE79cxFSFCWGY01YDO3IciwNy+9BK7jXeS1Zfot69NcufnbUcmpocA== X-MS-Exchange-Transport-CrossTenantHeadersStamped: CH0PR10MB4939 X-Proofpoint-Virus-Version: vendor=baseguard engine=ICAP:2.0.267,Aquarius:18.0.957,Hydra:6.0.591,FMLib:17.11.176.26 definitions=2023-08-04_17,2023-08-03_01,2023-05-22_02 X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 suspectscore=0 spamscore=0 phishscore=0 bulkscore=0 mlxscore=0 adultscore=0 mlxlogscore=999 malwarescore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2306200000 definitions=main-2308040151 X-Proofpoint-ORIG-GUID: JL9Ja1WvvKDzbuFLUnp6brBA8IABs5-C X-Proofpoint-GUID: JL9Ja1WvvKDzbuFLUnp6brBA8IABs5-C Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Type: text/plain; charset="utf-8" Replacing nodes may cause a live lock-up if CPU resources are saturated by write operations on the tree by continuously retrying on dead nodes. To avoid the continuous retry scenario, ensure the new node is inserted into the tree prior to marking the old data as dead. This will define a window where old and new data is swapped. When reusing lower level nodes, ensure the parent pointer is updated after the parent is marked dead. This ensures that the child is still reachable from the top of the tree, but walking up to a dead node will result in a single retry that will start a fresh walk from the top down through the new node. Signed-off-by: Liam R. Howlett --- lib/maple_tree.c | 56 +++++++++++++++++++++++++++++++++++++++--------- 1 file changed, 46 insertions(+), 10 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 880ce0fcdcac..0d4573a8d134 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -1756,6 +1756,36 @@ static inline void mas_replace(struct ma_state *mas,= bool advanced) } } =20 +/* + * mas_replace_node() - Replace a node by putting it in the tree, marking = it + * dead, and freeing it. + * the parent encoding to locate the maple node in the tree. + * @mas - the ma_state with @mas->node pointing to the new node. + * @old_enode - The old maple encoded node. + */ +static inline void mas_replace_node(struct ma_state *mas, + struct maple_enode *old_enode) + __must_hold(mas->tree->ma_lock) +{ + if (mte_is_root(mas->node)) { + mas_mn(mas)->parent =3D ma_parent_ptr( + ((unsigned long)mas->tree | MA_ROOT_PARENT)); + rcu_assign_pointer(mas->tree->ma_root, mte_mk_root(mas->node)); + mas_set_height(mas); + } else { + unsigned char offset =3D 0; + void __rcu **slots =3D NULL; + + offset =3D mte_parent_slot(mas->node); + slots =3D ma_slots(mte_parent(mas->node), + mas_parent_type(mas, mas->node)); + rcu_assign_pointer(slots[offset], mas->node); + } + + mte_set_node_dead(old_enode); + mas_free(mas, old_enode); +} + /* * mas_new_child() - Find the new child of a node. * @mas: the maple state @@ -3176,7 +3206,7 @@ static inline void mas_destroy_rebalance(struct ma_st= ate *mas, unsigned char end { enum maple_type mt =3D mte_node_type(mas->node); struct maple_node reuse, *newnode, *parent, *new_left, *left, *node; - struct maple_enode *eparent; + struct maple_enode *eparent, *old_eparent; unsigned char offset, tmp, split =3D mt_slots[mt] / 2; void __rcu **l_slots, **slots; unsigned long *l_pivs, *pivs, gap; @@ -3218,7 +3248,7 @@ static inline void mas_destroy_rebalance(struct ma_st= ate *mas, unsigned char end =20 l_mas.max =3D l_pivs[split]; mas->min =3D l_mas.max + 1; - eparent =3D mt_mk_node(mte_parent(l_mas.node), + old_eparent =3D mt_mk_node(mte_parent(l_mas.node), mas_parent_type(&l_mas, l_mas.node)); tmp +=3D end; if (!in_rcu) { @@ -3234,7 +3264,7 @@ static inline void mas_destroy_rebalance(struct ma_st= ate *mas, unsigned char end =20 memcpy(node, newnode, sizeof(struct maple_node)); ma_set_meta(node, mt, 0, tmp - 1); - mte_set_pivot(eparent, mte_parent_slot(l_mas.node), + mte_set_pivot(old_eparent, mte_parent_slot(l_mas.node), l_pivs[split]); =20 /* Remove data from l_pivs. */ @@ -3242,6 +3272,7 @@ static inline void mas_destroy_rebalance(struct ma_st= ate *mas, unsigned char end memset(l_pivs + tmp, 0, sizeof(unsigned long) * (max_p - tmp)); memset(l_slots + tmp, 0, sizeof(void *) * (max_s - tmp)); ma_set_meta(left, mt, 0, split); + eparent =3D old_eparent; =20 goto done; } @@ -3266,7 +3297,7 @@ static inline void mas_destroy_rebalance(struct ma_st= ate *mas, unsigned char end parent =3D mas_pop_node(mas); slots =3D ma_slots(parent, mt); pivs =3D ma_pivots(parent, mt); - memcpy(parent, mte_to_node(eparent), sizeof(struct maple_node)); + memcpy(parent, mte_to_node(old_eparent), sizeof(struct maple_node)); rcu_assign_pointer(slots[offset], mas->node); rcu_assign_pointer(slots[offset - 1], l_mas.node); pivs[offset - 1] =3D l_mas.max; @@ -3278,8 +3309,10 @@ static inline void mas_destroy_rebalance(struct ma_s= tate *mas, unsigned char end mte_set_gap(eparent, mte_parent_slot(l_mas.node), gap); mas_ascend(mas); =20 - if (in_rcu) - mas_replace(mas, false); + if (in_rcu) { + mas_replace_node(mas, old_eparent); + mas_adopt_children(mas, mas->node); + } =20 mas_update_gap(mas); } @@ -3596,11 +3629,13 @@ static noinline_for_kasan int mas_commit_b_node(str= uct ma_wr_state *wr_mas, struct maple_big_node *b_node, unsigned char end) { struct maple_node *node; + struct maple_enode *old_enode; unsigned char b_end =3D b_node->b_end; enum maple_type b_type =3D b_node->type; =20 + old_enode =3D wr_mas->mas->node; if ((b_end < mt_min_slots[b_type]) && - (!mte_is_root(wr_mas->mas->node)) && + (!mte_is_root(old_enode)) && (mas_mt_height(wr_mas->mas) > 1)) return mas_rebalance(wr_mas->mas, b_node); =20 @@ -3618,7 +3653,7 @@ static noinline_for_kasan int mas_commit_b_node(struc= t ma_wr_state *wr_mas, node->parent =3D mas_mn(wr_mas->mas)->parent; wr_mas->mas->node =3D mt_mk_node(node, b_type); mab_mas_cp(b_node, 0, b_end, wr_mas->mas, false); - mas_replace(wr_mas->mas, false); + mas_replace_node(wr_mas->mas, old_enode); reuse_node: mas_update_gap(wr_mas->mas); return 1; @@ -4117,9 +4152,10 @@ static inline bool mas_wr_node_store(struct ma_wr_st= ate *wr_mas, done: mas_leaf_set_meta(mas, newnode, dst_pivots, maple_leaf_64, new_end); if (in_rcu) { - mte_set_node_dead(mas->node); + struct maple_enode *old_enode =3D mas->node; + mas->node =3D mt_mk_node(newnode, wr_mas->type); - mas_replace(mas, false); + mas_replace_node(mas, old_enode); } else { memcpy(wr_mas->node, newnode, sizeof(struct maple_node)); } --=20 2.39.2 From nobody Thu Sep 11 15:26:07 2025 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 vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id 46E27C001DE for ; Fri, 4 Aug 2023 17:00:55 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S231611AbjHDRAw (ORCPT ); Fri, 4 Aug 2023 13:00:52 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:36280 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S231555AbjHDRAp (ORCPT ); Fri, 4 Aug 2023 13:00:45 -0400 Received: from mx0b-00069f02.pphosted.com (mx0b-00069f02.pphosted.com [205.220.177.32]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id AF8BA4C0C for ; Fri, 4 Aug 2023 10:00:41 -0700 (PDT) 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 374Ei6wF032152; Fri, 4 Aug 2023 17:00:23 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=Z7Gj5S0j9aJuMmiu8QbGEoIFKbCYb02+sSjKCP66TtU=; b=eSOhx8TgRZwZc3YlZY6Ir19XNkq2l/W3HO5GD8fM4Fp1qpuqZ9HvlEUF1Q3xEbsudyl5 YSzxtdqZvL/V65dpOxu3yMhXQi1rGa8ub/sOrfUit++S0XxBoSNBupS5xfLP4VvqjtXk Xv5htHm3FJGBmZF+4nonpbcYPN/zEJrAQw3+eIVAZrFuAJ8T8f6KoxnW7XnpWafWfo4W 6X7AXzk537jAaUpQ7MMqv+nM439wZsbiaKP8enoy+26VSdbrQBiqVeR1ZwLlMbB+aPES y9l/ZfjNmvj8TpBU+CSXFNCpgiJeILXluhPbt1LQtAHWtSSBzDKLB8d5QgUhlB+v6JNu rA== Received: from phxpaimrmta03.imrmtpd1.prodappphxaev1.oraclevcn.com (phxpaimrmta03.appoci.oracle.com [138.1.37.129]) by mx0b-00069f02.pphosted.com (PPS) with ESMTPS id 3s79vbx9eq-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Fri, 04 Aug 2023 17:00:23 +0000 Received: from pps.filterd (phxpaimrmta03.imrmtpd1.prodappphxaev1.oraclevcn.com [127.0.0.1]) by phxpaimrmta03.imrmtpd1.prodappphxaev1.oraclevcn.com (8.17.1.19/8.17.1.19) with ESMTP id 374FBTWQ029325; Fri, 4 Aug 2023 17:00:22 GMT Received: from nam10-bn7-obe.outbound.protection.outlook.com (mail-bn7nam10lp2102.outbound.protection.outlook.com [104.47.70.102]) by phxpaimrmta03.imrmtpd1.prodappphxaev1.oraclevcn.com (PPS) with ESMTPS id 3s8m29bn0g-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Fri, 04 Aug 2023 17:00:22 +0000 ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=KyqsAiCRKCZuWfF9Ah7S2aYj0Sva/MFw0cOqYhL5cRXjd+V1j/GL84nDQ7gjK1eSwrSUff3B4l8O+Y3qoIWyDFc2aBEyLWG0WP7Ujl8EsrCa1kG9I5KJDYLyWkTdszUddFeqLCTJ8DLEKcS92P6liH50xEjm/YJmjH1sSeNM/CF2rpUeOTib157mLHC+p6vaUO52IKJzzL4fTXVrFWoexN2gVw+vc8pOEhshW4k7BWf4D8xLmAmvgSmklK1zNrN9V5eYI0OVBjxhLHgqQqufobZp83SI5l+/FMYuKdm1CGxYUJ71fymrgX+ivLAc58Jdqv6OvN8FvcVnQCWJADzNGw== 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=Z7Gj5S0j9aJuMmiu8QbGEoIFKbCYb02+sSjKCP66TtU=; b=SZx+r65ZhWHNFAMAeri3p+YUdv4AC/SgVO1S6zA2lFFVT3mEPiFEcLEpTCJj9a6hHVfdOtmBXFNgI71AYjDK0FtdvGn+5ORVWVnO5+QvO6+Hipw9UES0ctL+3pvxzpmQGsyh2q40g4uPmtCUndl3D9ARC8Vyuz7DUHDc6sdssCu1QyDuak0BkC6CBfsD2KNHzWBNs4J0XKN6CSQV/Ph2Y0tB/u2mwS7WveSkgPJRJiPfpwQZbya1aGpstOYpFIBJjN9p137bUIOYfatYVVb/dhQ+xkD9qBBoeI8jlBa+qneyKcPDipQsqR+9nw0vkf1fkN/K7Ys7qp2W90VQxjoVEQ== 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=Z7Gj5S0j9aJuMmiu8QbGEoIFKbCYb02+sSjKCP66TtU=; b=dgnDjNtibR7qwsGr4ZK1RxfsyJNSplNaSrr3VFp9O/Mc94MqIyBo8OYnge2PqIF+qUT/YqrcTFSru4mVqRm16r5Y9b+k6dOV2/cBcDZdTg1MGPLyPlKF084jMMH5o1uXyGkEkV/luvNRDM/3mnMPI1ogP0VoEaEEi6CDnjvD3wE= Received: from SN6PR10MB3022.namprd10.prod.outlook.com (2603:10b6:805:d8::25) by CH0PR10MB4939.namprd10.prod.outlook.com (2603:10b6:610:c0::14) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.6652.21; Fri, 4 Aug 2023 17:00:19 +0000 Received: from SN6PR10MB3022.namprd10.prod.outlook.com ([fe80::26d3:6f41:6415:8c35]) by SN6PR10MB3022.namprd10.prod.outlook.com ([fe80::26d3:6f41:6415:8c35%3]) with mapi id 15.20.6631.046; Fri, 4 Aug 2023 17:00:19 +0000 From: "Liam R. Howlett" To: Andrew Morton Cc: maple-tree@lists.infradead.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, "Paul E . McKenney" , Suren Baghdasaryan , Matthew Wilcox , "Liam R. Howlett" Subject: [PATCH 3/6] maple_tree: introduce mas_put_in_tree() Date: Fri, 4 Aug 2023 12:59:48 -0400 Message-Id: <20230804165951.2661157-4-Liam.Howlett@oracle.com> X-Mailer: git-send-email 2.39.2 In-Reply-To: <20230804165951.2661157-1-Liam.Howlett@oracle.com> References: <20230804165951.2661157-1-Liam.Howlett@oracle.com> Content-Transfer-Encoding: quoted-printable X-ClientProxiedBy: YT4PR01CA0277.CANPRD01.PROD.OUTLOOK.COM (2603:10b6:b01:109::10) To SN6PR10MB3022.namprd10.prod.outlook.com (2603:10b6:805:d8::25) MIME-Version: 1.0 X-MS-PublicTrafficType: Email X-MS-TrafficTypeDiagnostic: SN6PR10MB3022:EE_|CH0PR10MB4939:EE_ X-MS-Office365-Filtering-Correlation-Id: dc592ef8-9cd4-4fdd-8541-08db950c48b3 X-MS-Exchange-SenderADCheck: 1 X-MS-Exchange-AntiSpam-Relay: 0 X-Microsoft-Antispam: BCL:0; X-Microsoft-Antispam-Message-Info: H+0tr6yQAUTv9uVDHF4xH4n91gbWXUUC35WD4lLSv/D3QFyIWDEIEzAYjMX8SIEQBE2a9HiK/YuHCoZzRsKUzkVB/IJyUUgoY0KmiGuXdlyecfcmovWdBMDvrldVKm+VBezW3wfTCnFStd+xaBECNjGCtYvU6qwedV69+mjVfnIFH7SN+UlivD9NeL4RISxSo4EL9CPM3nN8bSitCtaeuqqhNAA1IIXNPBz9OBLmd9p+UL2zZsUsxqT8G0D3kN+se8EDBFVzlbBvOACQxBUJUAx8/ZHOzGmq6RumyAP1xs62T7mpxkR7x7Eku6rS+NsE0cKnQfo5JBEkD+bSzaLzONb0SNlhcesVelJbsYYAToJb96mJj3hmtOpeYHN324fAPBdhLbD/a4F2IgKGlpRVTlfthf3oti/dcVBVvvh7bQQ0NuvPJeXKUsywzGopO6gogObf2Y+XU8Bfd/wP9GW0X+cBq6HWjeSLzNdCNIy0MqE1cSgHjeueAY0EsYBxj2n6YhCQ7W/Dv0FbEuIKK5byFvwKCaiiWb9U3WvDD9b+eWv85JJyMGQa1KBgAyYvEHZs 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)(366004)(396003)(39860400002)(346002)(376002)(136003)(186006)(451199021)(1800799003)(6666004)(6486002)(6512007)(86362001)(6506007)(26005)(1076003)(107886003)(36756003)(2616005)(83380400001)(38100700002)(5660300002)(41300700001)(8936002)(8676002)(4326008)(6916009)(66476007)(2906002)(66556008)(66946007)(316002)(478600001)(54906003);DIR:OUT;SFP:1101; X-MS-Exchange-AntiSpam-MessageData-ChunkCount: 1 X-MS-Exchange-AntiSpam-MessageData-0: =?us-ascii?Q?eLVDOabtYvh96iaW28fjFiN0BI6+XPBKey+dLuuiNE2yEBH8rsoNmQXmqFb+?= =?us-ascii?Q?1B0Z6N3bMijFj3LvvBmorYeKduZ+jYWlE5MNfIC7XmgB/2IqyRNnuYrcfLnq?= =?us-ascii?Q?kzLk+hrCZPnaL9Pw/fpd2AgnPzTlXxhCOdUQILuX8WwbXO2yBFbeuWNBvIyf?= =?us-ascii?Q?U8HPn5AoTZ012PYMVmV/AX5urhVzGu1NvsM8zJ/wszmp+3a9Heyx2VhvoZjZ?= =?us-ascii?Q?xsP+MTbi+oUrIgLHpzvbFRwqYbiTMmqWzDQZWE2nHV21L3khJB3gESAAZnEK?= =?us-ascii?Q?0aHN3WctbB0+P3C96bmD2Nzv4aY9chUquxYZIR1I5LaT8ZlgW9flHEsC2lQa?= =?us-ascii?Q?bV3qvjHLMoCSVJ8UI2osXIj2tLA7EZy2vYDD8ss1Jd4BzjRT4w+R9LU1jlAq?= =?us-ascii?Q?XWCJXFPxAUkzTBd92FC+p0Aq0wewsBuFrQ7CjZebmWVr1kizK0a3JXPfHB4y?= =?us-ascii?Q?aYoCHYnPmg+iG8ecltJXWgAVFzJe5GsJD6xxDXWPaOVwEaZ+PfOqdqtDsIc4?= =?us-ascii?Q?nFj76sWd+Sa+rk1eLhWwJ1ie2TwXAFEea68fXeXsDkL67w5F4TdVdhirvwtc?= =?us-ascii?Q?Q46NUQjn+qAU2cV64jpso4rtjB+WznolKmmTUTTZvBdjziEI4iBqSMZz0PgM?= =?us-ascii?Q?V6k3VyZpfr6sYP9lVBWIkTA2WF/+/FSwNnjYkCY/dkxp0NRpDi87VyqsaJjD?= =?us-ascii?Q?q3HarU1NlxgNMfcd82psf0y7PD6Yh9pCltItdYGsSZs6AF0XtLZoZf+OtKPo?= =?us-ascii?Q?p61bjRR4wk8DdaFcw7xVRzWUA3z6lM2UeZ/m4khWJQ7nb90tBnxAkfFS3Mnu?= =?us-ascii?Q?w9xu8RTpLgKFD8WDbkjSvJZ4pgTQ0RDaewIkXn7bsYlXwFOEi819jjd5RXWB?= =?us-ascii?Q?UFekgNd4iIfHc6g//DVDtQiCbkViE9Scqpqbg1aJnQUy7C6uPmuZ5VfsRxYo?= =?us-ascii?Q?36j7WKhOABuicPzCkW1AHLfVX/dl1LW0M0k691tvl4foUDVK6HM1QTU7FgSq?= =?us-ascii?Q?IpBWCKpf9qJF54V5IWkSTyy2Jzd2DcXvpfk4xOcW7dMJChxDOPfumGiZv3sr?= =?us-ascii?Q?QcTqhdaM066JSeSHxuYe4sEXylfnXndUsnm/7V03DYgUxXUBMuZ5C4SAAuFz?= =?us-ascii?Q?NqRfQSfQrPdSo+syHbOJSttUsoAtzRwZ3SES3TnWRGwqbVEfFhkrF601WRGy?= =?us-ascii?Q?fC0A66dlax8ekCyFAtNIltvxKe8WRky+9JXJWDVhSt36DmrZJKYIPnOce8xm?= =?us-ascii?Q?N9Ua5HT+ahMUdvRTPQc3gzJHHxm/dXcmafLviTfWwNrSJVMZHMIWy2MgLPzD?= =?us-ascii?Q?wN6tGzVrffvFC8X3AyPB9ZjYvqo/rQdrZFQCjtCxiqJd+usbp2AhHqeZzyBt?= =?us-ascii?Q?lhjFQDOSls2TCDuBkN9Iflq3bcUOxF20QgcEl0+LB6GzQFtwd8ElI8IBDet5?= =?us-ascii?Q?zkT2d2mjLLqd4kfwl7d+PgtGgB25THXo9FtK+5ZwGUlAnRpcRpuPOv7EoNzE?= =?us-ascii?Q?XvO55rg3IYy3RU8ioTw1o2F9AqpHX8+9op6s439d5KANPmpyESBEsKuyMgM/?= =?us-ascii?Q?9RmwkSfTUGfgr+ZUHvmofswl5M1AHHSHPQw7r07HbZi/sd3aFhQBcA84lrAP?= =?us-ascii?Q?7w=3D=3D?= X-MS-Exchange-AntiSpam-ExternalHop-MessageData-ChunkCount: 1 X-MS-Exchange-AntiSpam-ExternalHop-MessageData-0: =?us-ascii?Q?sWdmtV3O5dJ13qSJd3K3X+oSEtJ3YkLmeZKYG4K3svViO6a9CCWOtCcyO5Ag?= =?us-ascii?Q?paKRUh26Aw7ayJDHgsg47mz4jQ8ucFr9E/26vv3/0mP1suMYcAyLNlC4BjGn?= =?us-ascii?Q?gfpaEsrwqxS+BXBX7tov6blYlOxDNyOYglyMkQHm6hmptbapZxydKNgn/4Du?= =?us-ascii?Q?BGQwfw5HMkD5tzOXamRKPUm6UHiMMEpinbZd8JxtXKSywJ7LJBuJyp3Dy/nO?= =?us-ascii?Q?f2vWvhSLXEwumi5WqBkFSlhnEdSQxOZUExlj70JpJr7AS/buBYdVQB529PXT?= =?us-ascii?Q?pCybFDrrKKN9qC9xxIbWWoy8aUrIQzemfFakBfAAYFH5jCxSVumEh7nclnTi?= =?us-ascii?Q?uzrj+XFW8LXnRZtTgcOY+rMN4Z+cd7vYgPqgHuM+uI9o6Cw2HWog+LqKuPpM?= =?us-ascii?Q?Hol5iiLzyon+4juFF9M0IOqCGk8CZKJ/Fh0ziw1Qk8NCvoh7rgaZ9vzoJhaZ?= =?us-ascii?Q?xuWAbpLJX6dW28T8gXYfGQrTTzaP0BwWHk3S9ZfNx9Q8qUybSmpPwVXDIKp3?= =?us-ascii?Q?OqUd1smcRk0sDJ8sYBKSIHR8QeFc6XkcFfmCyzxWNQiA5xVuXUx318mST/Tq?= =?us-ascii?Q?cYzFUsV6OYhrW+aSlPAr4u7lXqAE6+z0u0hzGIKYw0IYP4Leb/DxtfCeyfDd?= =?us-ascii?Q?Qo54pPtOX209AfwqN7pQVW5D9sAOXz466DWsuF8FU7AjdmWC7BwVDpet/7MN?= =?us-ascii?Q?sPxt/Koxc0Zroor6cRWD3uf+93pYRug+LJJBRh7AQv8dhD0YwSR+4D9J8pyI?= =?us-ascii?Q?MEnCV0vCseHhiU4fZcx0vrU20TlgT9iQgXEHC5DpG6YCPbQzdu8lIiRuJQau?= =?us-ascii?Q?42xkg8/M4rP5PEmd2MPQwbpDiM0TBZdgDoFVvzyOBL0cdZlutPwUd9QLIXiy?= =?us-ascii?Q?wLaXxjdRaZKPj9Nvc/0UGF5iLg2eDnhd9IW5GptMohjKizyaJEcISR0zlF30?= =?us-ascii?Q?rhcsn7HWhuuclaof5+Lq3HfUSXwvZPTagxnLx237kds=3D?= X-OriginatorOrg: oracle.com X-MS-Exchange-CrossTenant-Network-Message-Id: dc592ef8-9cd4-4fdd-8541-08db950c48b3 X-MS-Exchange-CrossTenant-AuthSource: SN6PR10MB3022.namprd10.prod.outlook.com X-MS-Exchange-CrossTenant-AuthAs: Internal X-MS-Exchange-CrossTenant-OriginalArrivalTime: 04 Aug 2023 17:00:19.8035 (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: WlWdKj4W1aijM1nMtEpg1WrbNxT0sRcU+m3Q9v/Xou/BcYtwW/wYVtUobhg72QAxSuzjRdV+6NBKX7+BpMdsVw== X-MS-Exchange-Transport-CrossTenantHeadersStamped: CH0PR10MB4939 X-Proofpoint-Virus-Version: vendor=baseguard engine=ICAP:2.0.267,Aquarius:18.0.957,Hydra:6.0.591,FMLib:17.11.176.26 definitions=2023-08-04_17,2023-08-03_01,2023-05-22_02 X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 suspectscore=0 spamscore=0 phishscore=0 bulkscore=0 mlxscore=0 adultscore=0 mlxlogscore=999 malwarescore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2306200000 definitions=main-2308040151 X-Proofpoint-GUID: jESdJAkz7tnNYuATUmTO2uzn7cRKzltb X-Proofpoint-ORIG-GUID: jESdJAkz7tnNYuATUmTO2uzn7cRKzltb Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Type: text/plain; charset="utf-8" mas_replace() has a single user that takes a flag which is now always true. Replace this function with mas_put_in_tree() to better align with mas_replace_node(). Inline the remaining logic into the only caller; mas_wmb_replace(). Signed-off-by: Liam R. Howlett --- lib/maple_tree.c | 73 ++++++++++++++++++------------------------------ 1 file changed, 27 insertions(+), 46 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 0d4573a8d134..c01b1be1480c 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -1715,45 +1715,32 @@ static inline void mas_adopt_children(struct ma_sta= te *mas, } =20 /* - * mas_replace() - Replace a maple node in the tree with mas->node. Uses = the - * parent encoding to locate the maple node in the tree. - * @mas - the ma_state to use for operations. - * @advanced - boolean to adopt the child nodes and free the old node (fal= se) or - * leave the node (true) and handle the adoption and free elsewhere. + * mas_put_in_tree() - Put a new node in the tree, smp_wmb(), and mark the= old + * node as dead. + * @mas - the maple state with the new node + * @old_enode - The old maple encoded node to replace. */ -static inline void mas_replace(struct ma_state *mas, bool advanced) +static inline void mas_put_in_tree(struct ma_state *mas, + struct maple_enode *old_enode) __must_hold(mas->tree->ma_lock) { - struct maple_node *mn =3D mas_mn(mas); - struct maple_enode *old_enode; - unsigned char offset =3D 0; - void __rcu **slots =3D NULL; - - if (ma_is_root(mn)) { - old_enode =3D mas_root_locked(mas); - } else { - offset =3D mte_parent_slot(mas->node); - slots =3D ma_slots(mte_parent(mas->node), - mas_parent_type(mas, mas->node)); - old_enode =3D mas_slot_locked(mas, slots, offset); - } - - if (!advanced && !mte_is_leaf(mas->node)) - mas_adopt_children(mas, mas->node); + unsigned char offset; + void __rcu **slots; =20 if (mte_is_root(mas->node)) { - mn->parent =3D ma_parent_ptr( + mas_mn(mas)->parent =3D ma_parent_ptr( ((unsigned long)mas->tree | MA_ROOT_PARENT)); rcu_assign_pointer(mas->tree->ma_root, mte_mk_root(mas->node)); mas_set_height(mas); } else { + + offset =3D mte_parent_slot(mas->node); + slots =3D ma_slots(mte_parent(mas->node), + mas_parent_type(mas, mas->node)); rcu_assign_pointer(slots[offset], mas->node); } =20 - if (!advanced) { - mte_set_node_dead(old_enode); - mas_free(mas, old_enode); - } + mte_set_node_dead(old_enode); } =20 /* @@ -1767,22 +1754,7 @@ static inline void mas_replace_node(struct ma_state = *mas, struct maple_enode *old_enode) __must_hold(mas->tree->ma_lock) { - if (mte_is_root(mas->node)) { - mas_mn(mas)->parent =3D ma_parent_ptr( - ((unsigned long)mas->tree | MA_ROOT_PARENT)); - rcu_assign_pointer(mas->tree->ma_root, mte_mk_root(mas->node)); - mas_set_height(mas); - } else { - unsigned char offset =3D 0; - void __rcu **slots =3D NULL; - - offset =3D mte_parent_slot(mas->node); - slots =3D ma_slots(mte_parent(mas->node), - mas_parent_type(mas, mas->node)); - rcu_assign_pointer(slots[offset], mas->node); - } - - mte_set_node_dead(old_enode); + mas_put_in_tree(mas, old_enode); mas_free(mas, old_enode); } =20 @@ -2789,11 +2761,20 @@ static inline void mas_wmb_replace(struct ma_state = *mas, struct ma_topiary *free, struct ma_topiary *destroy) { - /* All nodes must see old data as dead prior to replacing that data */ - smp_wmb(); /* Needed for RCU */ + struct maple_enode *old_enode; + + if (mte_is_root(mas->node)) { + old_enode =3D mas_root_locked(mas); + } else { + unsigned char offset =3D mte_parent_slot(mas->node); + void __rcu **slots =3D ma_slots(mte_parent(mas->node), + mas_parent_type(mas, mas->node)); + + old_enode =3D mas_slot_locked(mas, slots, offset); + } =20 /* Insert the new data in the tree */ - mas_replace(mas, true); + mas_put_in_tree(mas, old_enode); =20 if (!mte_is_leaf(mas->node)) mas_descend_adopt(mas); --=20 2.39.2 From nobody Thu Sep 11 15:26:07 2025 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 vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id 82D51C04A6A for ; Fri, 4 Aug 2023 17:00:50 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S231527AbjHDRAs (ORCPT ); Fri, 4 Aug 2023 13:00:48 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:36278 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S231493AbjHDRAl (ORCPT ); Fri, 4 Aug 2023 13:00:41 -0400 Received: from mx0a-00069f02.pphosted.com (mx0a-00069f02.pphosted.com [205.220.165.32]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id EA61A46B3 for ; Fri, 4 Aug 2023 10:00:38 -0700 (PDT) Received: from pps.filterd (m0246627.ppops.net [127.0.0.1]) by mx0b-00069f02.pphosted.com (8.17.1.19/8.17.1.19) with ESMTP id 374EiPjS019904; Fri, 4 Aug 2023 17:00:27 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=CSBRiN3QDXn+UdttUmnB30Ar+vyLKFI9e7V3W37fdL0=; b=vL/f7lN9E7+9n+zVgvdsuH3Nc6hULuQrWyNPN9219tI5gQFHBFNfaCqlc3WkGVVOlH1q OHWpjLRONSNTpeFcu7P+1ec0WlGQHeF6LzAR3bviB4Y7c70m+PfGLH46j2z2ofbJvGP5 FOZDl4ICM219iijRHQHKjbhGyZtm8f6ueXyineIFUHQFtq7Ea47vLAeVpej+ctWNYjr0 5rsr0dIffxERRCJY/RAzJCx6rWW5UXo1eu9Yt42zMRMHf1qgR4vA9K9JmKvKtmGZjTuY XNiVswn+cZbqRTBzEhXMaEyqY77vohhgYXJOLpqOZmeIvm5p1smXdluyNAqplNPNDOf+ vw== Received: from iadpaimrmta01.imrmtpd1.prodappiadaev1.oraclevcn.com (iadpaimrmta01.appoci.oracle.com [130.35.100.223]) by mx0b-00069f02.pphosted.com (PPS) with ESMTPS id 3s4sc2m942-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Fri, 04 Aug 2023 17:00:26 +0000 Received: from pps.filterd (iadpaimrmta01.imrmtpd1.prodappiadaev1.oraclevcn.com [127.0.0.1]) by iadpaimrmta01.imrmtpd1.prodappiadaev1.oraclevcn.com (8.17.1.19/8.17.1.19) with ESMTP id 374Gghws040734; Fri, 4 Aug 2023 17:00:25 GMT Received: from nam04-mw2-obe.outbound.protection.outlook.com (mail-mw2nam04lp2177.outbound.protection.outlook.com [104.47.73.177]) by iadpaimrmta01.imrmtpd1.prodappiadaev1.oraclevcn.com (PPS) with ESMTPS id 3s8kpkmhy4-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Fri, 04 Aug 2023 17:00:25 +0000 ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=OUptpqReCMyNwnLvcLGqM9CslKvJYSUWsA5F0BaZdk6QEgr1ofPAtFDg5Vg0lF1lCmjV5Kw1ZKnY2cCtuyHIagpUvhBwUv3/evSHkGqGz4MGamjgOciBUH7DgBv9vNhLlJrlIsjJFyI6iN1rJUZRTdzN0lrDauG56vn8e66IZR/lUraiUdgu6OIJdejHUp71yKQvN8bD2dQt2wJ0BBwoyOgxFmQt2PMFjC8s8H6xg7DxoExyvHQuIIxFzwqJBwl5FsO0HUS79kvohvzcQW4L72Rl6Yk/qMOgerCqxEsA1vR0+ClI8uZEm99ZoP55jUSvLcy597uVqz5brMDONYZ0RA== 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=CSBRiN3QDXn+UdttUmnB30Ar+vyLKFI9e7V3W37fdL0=; b=AnruR5XiAgajrB8ECVilyiq8dVqrcyoMu+/Y4HDq/6mUvIP9iTx6jyUc1nAN3H/MiURB2Ba+r3n/4k1Ir1S2R+pxPu+Yw/YmlwnC2qPb2/hzn2etim9OFtaBQ6W25PQ3YOAxX+Xwyz95ZFHGZ7hGBNzPygESbyzmIX9qCvHKVBScDiV3cy8fJge75neE4mrJg+2RoM0xRnee8dx+50rnkSsbEhaJ8GBoZ0UBkskYGx9AZYQ9Q+BYrTk6a1kkFGJUknK9mN1Y7hY9TcM0i1zESjQEGeoAP1Shxg1yhXOwAN4X3T3WLbYm+fs7xPoRIjMdMNupP8hZWbpkidw+kDG4pQ== 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=CSBRiN3QDXn+UdttUmnB30Ar+vyLKFI9e7V3W37fdL0=; b=fkb/JbfH+7ggYfasiZ4JOJlBaUirZCYcq6OcnHCPzrK8cfpgpxaK1S3vkN9fwC9bkjhFu4ynx/xAIoNcDOSe3LEsc1iPbDm1A/Pv50GiwrkrjGlqWqRDHN2JQ973UjdVaEp3dxpixH7qgcMs4Tt3IUxrvFNvSsGrEa7itCs1bNI= Received: from SN6PR10MB3022.namprd10.prod.outlook.com (2603:10b6:805:d8::25) by CH0PR10MB4939.namprd10.prod.outlook.com (2603:10b6:610:c0::14) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.6652.21; Fri, 4 Aug 2023 17:00:22 +0000 Received: from SN6PR10MB3022.namprd10.prod.outlook.com ([fe80::26d3:6f41:6415:8c35]) by SN6PR10MB3022.namprd10.prod.outlook.com ([fe80::26d3:6f41:6415:8c35%3]) with mapi id 15.20.6631.046; Fri, 4 Aug 2023 17:00:22 +0000 From: "Liam R. Howlett" To: Andrew Morton Cc: maple-tree@lists.infradead.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, "Paul E . McKenney" , Suren Baghdasaryan , Matthew Wilcox , "Liam R. Howlett" Subject: [PATCH 4/6] maple_tree: Introduce mas_tree_parent() definition Date: Fri, 4 Aug 2023 12:59:49 -0400 Message-Id: <20230804165951.2661157-5-Liam.Howlett@oracle.com> X-Mailer: git-send-email 2.39.2 In-Reply-To: <20230804165951.2661157-1-Liam.Howlett@oracle.com> References: <20230804165951.2661157-1-Liam.Howlett@oracle.com> Content-Transfer-Encoding: quoted-printable X-ClientProxiedBy: YT4PR01CA0286.CANPRD01.PROD.OUTLOOK.COM (2603:10b6:b01:109::6) To SN6PR10MB3022.namprd10.prod.outlook.com (2603:10b6:805:d8::25) MIME-Version: 1.0 X-MS-PublicTrafficType: Email X-MS-TrafficTypeDiagnostic: SN6PR10MB3022:EE_|CH0PR10MB4939:EE_ X-MS-Office365-Filtering-Correlation-Id: 80cf2793-7ba3-4480-2e65-08db950c4a6a X-MS-Exchange-SenderADCheck: 1 X-MS-Exchange-AntiSpam-Relay: 0 X-Microsoft-Antispam: BCL:0; X-Microsoft-Antispam-Message-Info: kABZ5l4rOAILR0fqwkZ7OGNhs24/hRUJRyJvRpTZfMAtqwBTRdFO3RmUqM+jhN1shqqB8ccw/PHv2z3wnZYkQszTTHEGBNzOvibVMiob1iQzg5U6rVvE0X+QHn8IJ6GAJWBOEbt70/Q81w4FVU5ecY5ao9JRLkcvkiVMQht0u+frtCIJDtO8dNIdE/F8YXEcX+3Ch6aZqWhWjP1S0V+5ZmJBUPYAI3xbdT3DK5Ysi7dDXR7W5MSONnx1DR4nVg6OobUNDhj3u0EuhSUpnrvCO1ijDa2LHFAtMgdc8geOw1dkDFLde4QkyfxSVC7SRRSrRL/zILeNXBhbd4gjr1yacLJUCPztkqINrnkOOGrqJU+hiUvO/kSu342+1g2c4zlosHbwXqQDIIpgi/yY0KrESv+KuzCFXwIuVRyhB53gma1wz2y5fieN3E50AkfjMM9nEG04D+fxAV17Lr5zuoVp7UviPbVQMmmzjLLcjkJIO5Nv5wGYa2qqikFo5guEeR0CM0z6zw0YZGlFP9LknnBgu+OCpnA8U6tk0Al9a+oSseRNQoFPSR1wFFnz369MQlw6 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)(366004)(396003)(39860400002)(346002)(376002)(136003)(186006)(451199021)(1800799003)(6666004)(6486002)(6512007)(86362001)(6506007)(26005)(1076003)(107886003)(36756003)(2616005)(83380400001)(38100700002)(5660300002)(41300700001)(8936002)(8676002)(4326008)(6916009)(66476007)(2906002)(66556008)(66946007)(316002)(478600001)(54906003);DIR:OUT;SFP:1101; X-MS-Exchange-AntiSpam-MessageData-ChunkCount: 1 X-MS-Exchange-AntiSpam-MessageData-0: =?us-ascii?Q?pKpNAdwRhUUrAvdRLMeaQtL+1d7Yxs3ttZs1YrIsKP4Ed6HncUAu3izdlRUv?= =?us-ascii?Q?vmrUJaXEbQqnrZaPQIDHUemAYHYfBF+QhXCxtYw8ddcLIDmuhLcWvP2Ak75V?= =?us-ascii?Q?do6nDQIE2Qbd7bDxaKTj0OmgPkxdv/I1KBVWv8G8eDp/Y9IHpuAHT72YIZer?= =?us-ascii?Q?Kelxnd15VIBFpdD9DErblwQ4ubG2QDZIaAD45ih6q1AhJpSxzE+lbt7mmF+k?= =?us-ascii?Q?3Rbj9qQXcxEOG347NPXdJQWC8A8+7mvYi3fsQ3itYOeCmiic6S4/A/+7+R0Z?= =?us-ascii?Q?lEQVq2K3WG1juG/+vKavtPWZWSwWSAl1XOTCEoX+Eo4ecnMl0tnOBwwDOh6+?= =?us-ascii?Q?Ev90wSxex1IRN8vT9H9XyAKSJtga4ZnJ1vcbtZk6GNdKBYWKcjdbhxRcwMrN?= =?us-ascii?Q?FSlYAFUyk9KMsFkdAilFuIAx7yC1QFjvUPKLcR/AxnFI9vFbRDYFn2ZbrZzg?= =?us-ascii?Q?+ik38KhwtbfgWFIgeL3ffpdsbs50n+Qp/04uL1ipTBQyVkRV7UqxMfONQPr6?= =?us-ascii?Q?jGdahJ/KmPQ8pcZnl0hqfU9plsMfb0zSi03H4Ar0geQum7jfvS4SPLWmFIuG?= =?us-ascii?Q?zLr9NGhydTUzeSLX1s380UtEkkFSAXiplVULoCrRmSgAaOj/vbtbu0US6B/U?= =?us-ascii?Q?rIymX0KD/GzO8ida5oijQQxJRQSNJlyB6pYkoiJ8q7xmgF0I9N858Y3GqDCj?= =?us-ascii?Q?bJKPww3RcMcJ+l+K1w3skEBPxZCdCo+L14URz4C0jhL0IoqmZn9ET6Lk3ZXq?= =?us-ascii?Q?cDlJvTShlm5aVLt4sx29GisinYcjvq/hIBKuY1tSmi/ErKHDD9tOBqFyfhMo?= =?us-ascii?Q?w5GeC5YA3pe/YyiW+T/yRLRQ73f7IyiFsCW4GJveq1BPcjZbtHxW3Iy7gfP+?= =?us-ascii?Q?qdHBDloZAcMKP5W0AN5mwEgkchs1QZM0RZg8RjsgZeRxgcmYWIevkMB8gzXw?= =?us-ascii?Q?I1Is+VHso+CEA+3BMVd0t70fn4up4WnlksjWsUwGnI7toXQP6fdgzhg04eO5?= =?us-ascii?Q?4D5unb+na7JSOju2NnyzcK4MwUStJerg8+NunsN8SVumrRLeCBr2URyTwA97?= =?us-ascii?Q?g2nmOJiJ8D3HzGI2R6o8+T0Ummw0yOYTf/s4FcdeIT3VQ1jQrfGOkSV4cwYk?= =?us-ascii?Q?26uEJf/NZGCU9fzBWxJ8Cdh7csNIVY2IvodQLhBDhbHdMoYQwu0PvnhBn43T?= =?us-ascii?Q?tXlfKcUWGmAWnpPgV5ymdYhulvRV5q+P0VvPsv2TVDrOs944oNyR/ouquK9a?= =?us-ascii?Q?9jgadsonWlibGk3YuO3Xm5qkIRl/Sx5fRqLzmVcbv5Yc8jlEzA1UDmciE/EI?= =?us-ascii?Q?9Ed1BZoEyua6CbiVkGckbN3zVc6NnoZF2w8kFtuGGM9NOOA50dOrwyTGwBAq?= =?us-ascii?Q?FKiGNDw02YMiq8C8Aw/OIFyVdPBlbSDHXSvDhwKXcMISt54xrtCYv0JJI30Z?= =?us-ascii?Q?JSMK0RIGA0guYyt0axzCw2s31xgmzAf9YyLEIasSNY/l8lwr+szlL1v9vRtN?= =?us-ascii?Q?zDlaU9ieNywBOAy4P11zJBlciHx+mcrUaR5qZt1b0Y46hC83nEjteHGig9SP?= =?us-ascii?Q?xCK9GyZjoSu7NYifvPig5ZuhcyFGQmC6sQ2RRX3X5CdAjQqNUukDDFDgmY2r?= =?us-ascii?Q?pA=3D=3D?= X-MS-Exchange-AntiSpam-ExternalHop-MessageData-ChunkCount: 1 X-MS-Exchange-AntiSpam-ExternalHop-MessageData-0: =?us-ascii?Q?ckoAJr2ULvhjkE4Jd261i8V7kjLEeVp+2V32gx9spiO9E2rpQujf90DITUcj?= =?us-ascii?Q?N7fUMApJPpZFFEbK4NNqGOOCDXCk46P5CJSasEkrWht1Z4fCIUJlh4hpIht0?= =?us-ascii?Q?tTV21rwYUiE8isfY8rqCINslRhiori2X3oYjFA2zklko/oQEEcEBARici6s6?= =?us-ascii?Q?tADCuLdnqZn1Cx6fKChKjvDXCs434PzveBLTxt69gaqgVGZxcd5Uxzk5ZcJz?= =?us-ascii?Q?M/kuRXFhfbdJ5b9XGFZzkpItzWixvDlLbhia8vROBFbJzC4vweEWlgUDrdEY?= =?us-ascii?Q?sx0XNIxiesTXQywhwqvq1uIjb2heuyglV9IjCSqKYMvMMoQRroRzx1htr4mi?= =?us-ascii?Q?nwzrOxGEEpQzgqS7iUIt/3TT44OCvRzLti5ibXweHZThcy+L4yHBlPEhPQ3A?= =?us-ascii?Q?jTAYg1WoGPM/Mm/qO7t1weBPmfy11V9mPvfxQWf67xxUb64d76gOvG1Pmj3R?= =?us-ascii?Q?wQZvnhrT5mFoMr+BsQSGSNmpd3EWkt8ovPj3RnxG3eOreq4rSHDd5qUYjAJz?= =?us-ascii?Q?QcGdFn5dhQqE23QOKqabmt50ozlI/5laARMGNl6mjt2zEJ3eAkAits3udl9w?= =?us-ascii?Q?Re2RoVLN7XhXTCZlsLIUIPhGFy6VhxhEM/VTSBv9Ei4ZQIK3xtCl7q+AZ6VN?= =?us-ascii?Q?yQKCXq16kN1flbgeRiUeaOd1ECjUGm7ZDnG5Pznc34jizflHrtLA2EPi7jZU?= =?us-ascii?Q?qdmCQr9bfr+s5tVZbxzkNqv0jEQnEBA5Bh8KVVCL/QtXO2Uts6xd/ew6zY0s?= =?us-ascii?Q?Qwjk6P21ukMBeixk044t3unTN8GsthvFmi/iJ/FP8VKcZZhjYyThIxdIK4Xa?= =?us-ascii?Q?sz+/lrJ4aEhtrkrbOedM9x/M9txTCKq3m/F2RDB2NTEYdaAhm/dYvPjHxFFE?= =?us-ascii?Q?qAHRib+QlbvTkwoBdMzlGafPZAuB+6bZq9WPVvTq7X+1XDxL6EkundSFBE0y?= =?us-ascii?Q?cX+49j4JMFWZJAZNcIDRvm8hc+HNeG+eKCnnDLNew5s=3D?= X-OriginatorOrg: oracle.com X-MS-Exchange-CrossTenant-Network-Message-Id: 80cf2793-7ba3-4480-2e65-08db950c4a6a X-MS-Exchange-CrossTenant-AuthSource: SN6PR10MB3022.namprd10.prod.outlook.com X-MS-Exchange-CrossTenant-AuthAs: Internal X-MS-Exchange-CrossTenant-OriginalArrivalTime: 04 Aug 2023 17:00:22.5366 (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: fS5pV1J8KCqHxjkdlzikOOeI9QLIsGsy+g7qCNkgRDzceDGemusCnFA5mfu8rmUkJ/jwdq0CXGzFuAlJ/opK2A== X-MS-Exchange-Transport-CrossTenantHeadersStamped: CH0PR10MB4939 X-Proofpoint-Virus-Version: vendor=baseguard engine=ICAP:2.0.267,Aquarius:18.0.957,Hydra:6.0.591,FMLib:17.11.176.26 definitions=2023-08-04_17,2023-08-03_01,2023-05-22_02 X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 mlxlogscore=999 spamscore=0 bulkscore=0 adultscore=0 phishscore=0 mlxscore=0 suspectscore=0 malwarescore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2306200000 definitions=main-2308040151 X-Proofpoint-ORIG-GUID: SYYsx-cerzgYfAgzjKl_eg0581WQsUrB X-Proofpoint-GUID: SYYsx-cerzgYfAgzjKl_eg0581WQsUrB Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Type: text/plain; charset="utf-8" Add a definition to shorten long code lines and clarify what the code is doing. Use the new definition to get the maple tree parent pointer from the maple state where possible. Signed-off-by: Liam R. Howlett --- lib/maple_tree.c | 13 +++++-------- 1 file changed, 5 insertions(+), 8 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index c01b1be1480c..cf41e0dbb87b 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -75,6 +75,7 @@ #define MA_STATE_PREALLOC 4 =20 #define ma_parent_ptr(x) ((struct maple_pnode *)(x)) +#define mas_tree_parent(x) ((unsigned long)(x->tree) | MA_ROOT_PARENT) #define ma_mnode_ptr(x) ((struct maple_node *)(x)) #define ma_enode_ptr(x) ((struct maple_enode *)(x)) static struct kmem_cache *maple_node_cache; @@ -1728,8 +1729,7 @@ static inline void mas_put_in_tree(struct ma_state *m= as, void __rcu **slots; =20 if (mte_is_root(mas->node)) { - mas_mn(mas)->parent =3D ma_parent_ptr( - ((unsigned long)mas->tree | MA_ROOT_PARENT)); + mas_mn(mas)->parent =3D ma_parent_ptr(mas_tree_parent(mas)); rcu_assign_pointer(mas->tree->ma_root, mte_mk_root(mas->node)); mas_set_height(mas); } else { @@ -2798,8 +2798,7 @@ static inline void mas_wmb_replace(struct ma_state *m= as, static inline void mast_new_root(struct maple_subtree_state *mast, struct ma_state *mas) { - mas_mn(mast->l)->parent =3D - ma_parent_ptr(((unsigned long)mas->tree | MA_ROOT_PARENT)); + mas_mn(mast->l)->parent =3D ma_parent_ptr(mas_tree_parent(mas)); if (!mte_dead_node(mast->orig_l->node) && !mte_is_root(mast->orig_l->node)) { do { @@ -3661,8 +3660,7 @@ static inline int mas_root_expand(struct ma_state *ma= s, void *entry) node =3D mas_pop_node(mas); pivots =3D ma_pivots(node, type); slots =3D ma_slots(node, type); - node->parent =3D ma_parent_ptr( - ((unsigned long)mas->tree | MA_ROOT_PARENT)); + node->parent =3D ma_parent_ptr(mas_tree_parent(mas)); mas->node =3D mt_mk_node(node, type); =20 if (mas->index) { @@ -3938,8 +3936,7 @@ static inline int mas_new_root(struct ma_state *mas, = void *entry) node =3D mas_pop_node(mas); pivots =3D ma_pivots(node, type); slots =3D ma_slots(node, type); - node->parent =3D ma_parent_ptr( - ((unsigned long)mas->tree | MA_ROOT_PARENT)); + node->parent =3D ma_parent_ptr(mas_tree_parent(mas)); mas->node =3D mt_mk_node(node, type); rcu_assign_pointer(slots[0], entry); pivots[0] =3D mas->last; --=20 2.39.2 From nobody Thu Sep 11 15:26:07 2025 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 vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id 5C674C001DE for ; Fri, 4 Aug 2023 17:01:07 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S229607AbjHDRBG (ORCPT ); Fri, 4 Aug 2023 13:01:06 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:36716 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S231530AbjHDRA5 (ORCPT ); Fri, 4 Aug 2023 13:00:57 -0400 Received: from mx0b-00069f02.pphosted.com (mx0b-00069f02.pphosted.com [205.220.177.32]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id BA2C749F0 for ; Fri, 4 Aug 2023 10:00:45 -0700 (PDT) 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 374Ei3U8031787; Fri, 4 Aug 2023 17:00:32 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=+FX2dSTi4gdLWV9WMkxLANUNbJ9NL7dPJboXF2A/Zbo=; b=xn6DBMafeB1x+lfRrzT7+/6MT0H2fl1f27DhyInof7u9t8E0krZZTurCAFrJrDM/eWfO uPtm3FY3j42agfF5gptNChFCnkZyulZZ6QCxbTx5N2h/MgiikvEcmtwkkyUvDbwKCWT4 TCY/nRjUSV3Xa1SBn26HsacmZ1bwiNsuDZ4LiLL3lEiS9+ymHuRATW77qhoSoU1LV/aF Lh06klQo4Hc8exh5ISwEkYHN6davLuY03Tn1bghlXwx13SzRRdxo18Bs3/CBEEpDkRbb xVdnuJU5Hp2rUZyRXyABoe4MMo159zFbLTszMOne7TmLkLQ7eFge/nZkYCZkD4YUyKy/ eA== Received: from phxpaimrmta03.imrmtpd1.prodappphxaev1.oraclevcn.com (phxpaimrmta03.appoci.oracle.com [138.1.37.129]) by mx0b-00069f02.pphosted.com (PPS) with ESMTPS id 3s79vbx9et-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Fri, 04 Aug 2023 17:00:32 +0000 Received: from pps.filterd (phxpaimrmta03.imrmtpd1.prodappphxaev1.oraclevcn.com [127.0.0.1]) by phxpaimrmta03.imrmtpd1.prodappphxaev1.oraclevcn.com (8.17.1.19/8.17.1.19) with ESMTP id 374FJgoX029618; Fri, 4 Aug 2023 17:00:31 GMT Received: from nam10-bn7-obe.outbound.protection.outlook.com (mail-bn7nam10lp2101.outbound.protection.outlook.com [104.47.70.101]) by phxpaimrmta03.imrmtpd1.prodappphxaev1.oraclevcn.com (PPS) with ESMTPS id 3s8m29bngp-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Fri, 04 Aug 2023 17:00:31 +0000 ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=iV11Fx5Mx3I7s5MhB0JJZrs3TM8iRA2sq/BabKICYxx0pq8LeszxoPuVOk9JtLr+n9MciKy+pKVun9XCaKhRU1bzvwQzdvl14bdOLM1Zfw11/1X3Ob+rORTZ9UntULXEMa3PMssYAuVmeoSCnuO5Vg3/ie7Xlf2VGM+8cLPSnAfdk0JbQ4JP+DJ2yTvTuQSsrViUCBO11dqDVsSbTgF7KbG03eanWERUwgV2WyDi6QCYVyD1NtNUM2vV0aMw6xw5BoDx+y212jvjGHODhDFJEGcBkt4r7T0VKxHgDkBH9B335ffMpR8IM58l4a0L6s4kkKKdKS37PsemXdshaXqpaw== 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=+FX2dSTi4gdLWV9WMkxLANUNbJ9NL7dPJboXF2A/Zbo=; b=aldS8nkp/efxtZ5Und2PzaNbRnHGJ4MiuY7wPN7TMxzYD5C8f/+SWohCCL7Plh+BOxagZAT12KCal9GlA3IUPx59k9I2qRWTERs2rOQ1OWBuVMXlO9jqyPyrFB0nab4zepH5eYLgIaIGV2TOzgrbRjy8QYQkYpWZ3BMvm+UnSi9B0pKNFJyyWIKsrFj5Hx47IsZFnLAbuOBMaerDTKOOEl06i/3Pw8W88pSdRUJu71hxld8LozdoByMumeCi06zPC87dGCG1osyjVRbUAyRe4b3pBoeAa9xJ0s+c1OL/lazFdS8gbLcQdJ4AITCnEjTwT2ycEZHlW9R8fu1vcFVMRg== 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=+FX2dSTi4gdLWV9WMkxLANUNbJ9NL7dPJboXF2A/Zbo=; b=XdI4kVBTxIkvEc1SWjy3RNJ1RETCKfL0WB2JkP8RiGyqFzBO6PZ2i6s92REY+Nu7XGOsCUUA0ZHSSq1piJeBjxF1oRtwls9PpI7+jCYE78vJDWcSr3zAJbYY2/Xr3LK9L6JwNli26DD/S22AvoNPNCCXh8ww/9vx60MFD0zCz/s= Received: from SN6PR10MB3022.namprd10.prod.outlook.com (2603:10b6:805:d8::25) by CH0PR10MB4939.namprd10.prod.outlook.com (2603:10b6:610:c0::14) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.6652.21; Fri, 4 Aug 2023 17:00:28 +0000 Received: from SN6PR10MB3022.namprd10.prod.outlook.com ([fe80::26d3:6f41:6415:8c35]) by SN6PR10MB3022.namprd10.prod.outlook.com ([fe80::26d3:6f41:6415:8c35%3]) with mapi id 15.20.6631.046; Fri, 4 Aug 2023 17:00:28 +0000 From: "Liam R. Howlett" To: Andrew Morton Cc: maple-tree@lists.infradead.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, "Paul E . McKenney" , Suren Baghdasaryan , Matthew Wilcox , "Liam R. Howlett" Subject: [PATCH 5/6] maple_tree: Change mas_adopt_children() parent usage Date: Fri, 4 Aug 2023 12:59:50 -0400 Message-Id: <20230804165951.2661157-6-Liam.Howlett@oracle.com> X-Mailer: git-send-email 2.39.2 In-Reply-To: <20230804165951.2661157-1-Liam.Howlett@oracle.com> References: <20230804165951.2661157-1-Liam.Howlett@oracle.com> Content-Transfer-Encoding: quoted-printable X-ClientProxiedBy: YT4PR01CA0414.CANPRD01.PROD.OUTLOOK.COM (2603:10b6:b01:10b::22) To SN6PR10MB3022.namprd10.prod.outlook.com (2603:10b6:805:d8::25) MIME-Version: 1.0 X-MS-PublicTrafficType: Email X-MS-TrafficTypeDiagnostic: SN6PR10MB3022:EE_|CH0PR10MB4939:EE_ X-MS-Office365-Filtering-Correlation-Id: 6127e6f2-a361-449d-471f-08db950c4dbd X-MS-Exchange-SenderADCheck: 1 X-MS-Exchange-AntiSpam-Relay: 0 X-Microsoft-Antispam: BCL:0; X-Microsoft-Antispam-Message-Info: kdbRdliBhZuprvvy/Bg/p+D/lK2ECMsIgcXW5EghNkhprQFJoPwMdaXDKw8d+dVSBr7Gsq0lJFmf+fHuFp9AC9PUavamTZrseDuRKlgdZVnXhUyNODTFiNtLJL9DdegchhmwhWXXddtDzrP1wwHy+0ESlJ8QMIohH1e13WtXU2/7529/rUQRanXs++BaiYY/1quLqaSjC9Fjzfdxn0xH8NmQdY0WUaQMC/cpzvBAHT76mmRGwR6/uDMCzAaTGDwl20dSX8JvlHmFn3Jfohiv1ftiRocb7hlFiiLvKjjMvLD5r8Rlpfj+T4Ae28y/El+JuFjtPsMxMt3GHZWxshsHx8jevRmvS8vStC9yO45Fpe4XSpXjywd6NMWETsFF3fMFCf3tcr0Cyci8uLR+hfId13vN6dWcuWx0GY0k9Vfz+rSluwslsO6lsRuhrL1npwPxH1JtCDk/dF3vF8OljrjNTLxDgkPhIY0WI+nctMJfsZo2Yv9kqDK+vfWLKVBqjIjM6F98d0QGN53SwhJNRbIeP5zglN0DJ0Y1JgGdtNIanZDWQ/jTrGffiMNFaj/2c7i4 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)(366004)(396003)(39860400002)(346002)(376002)(136003)(186006)(451199021)(1800799003)(6666004)(6486002)(6512007)(86362001)(6506007)(26005)(1076003)(107886003)(36756003)(2616005)(83380400001)(38100700002)(5660300002)(41300700001)(8936002)(8676002)(4326008)(6916009)(66476007)(2906002)(66556008)(66946007)(4744005)(316002)(478600001)(54906003);DIR:OUT;SFP:1101; X-MS-Exchange-AntiSpam-MessageData-ChunkCount: 1 X-MS-Exchange-AntiSpam-MessageData-0: =?us-ascii?Q?PLIrrkQQqcwypLoGVzPMoQDqCLXIncDCchem/Her+9352AQ1miIPhxn8ezpL?= =?us-ascii?Q?33QOLN6pqOAdRVuS/rZOrnvn2CZZBPIQ37ElhCgbbMSSotp1aTZVthLAYROH?= =?us-ascii?Q?m9MYUXmTi/v6RKPUeM29EdZmD/S9lNwBs1Js4Ayksuy/s1EwPaGe0DbuXXQ4?= =?us-ascii?Q?v57Oa+bopTduuRLtctcCqfmngGqohOXHM3PCu4CQ4TOJllK9csTkn7xC9eEk?= =?us-ascii?Q?FL0hIKJDEad24JlNInQUqd1+Ni+4G6+Aez7m5pbY/bXy4TGuJ/Uzzyv4oLSr?= =?us-ascii?Q?hGv8BmD2dyyt2pmtrOSRch7Istdsk5TJiDn96wwS8e0zMRTLHIM4q5Mnzf5g?= =?us-ascii?Q?xEVUMGCn+XlfMjCZM6xfh0YYVrOBnQfgDXrjTYqjvzF3L+YQhjydWTBlhUUm?= =?us-ascii?Q?zzmy2OgLWBB59w0WQIa7i5TYgXhO8X4oJgQJU1RqusTEAbVrzgP+LheLE6sE?= =?us-ascii?Q?QMdKWJmmIxR801UibdtyDk8O0XQjj8FxbAw695fvAvEux74vE3aApEVvQIlA?= =?us-ascii?Q?/hUliiXFtjZ8yXuOdM2NEeaKdwND4l0Yv1DBGdkA0HpqdEvOdCADgk2zCj0Q?= =?us-ascii?Q?F7DMEKdWRcMuW8PALBqW9RDX8pv8MgqpKb7WyVkJnJ1+oAzZluihY4s9bq4Q?= =?us-ascii?Q?1uKJ9cTH2+s2iWAHLTcGD+6jlbJfUmIplw4msblY+tdt/+Itv6y8FBd0xQD6?= =?us-ascii?Q?bNUBvIVJ7Dk39HvwmdVuz1PKWkrqMFEGMLRHY0gX/bI7Jbz5JGo7AF6r8/nF?= =?us-ascii?Q?WROzyCVs9VlmlRzTxSvrKAcK2hNDIAwyEcce4pU+wL8P1u3XwcIUg48UL7RT?= =?us-ascii?Q?UU18pw0RLTTZthKfHCTltkdZatdbJMtcjwC301nBPO8B3B68gf25I2Zwj608?= =?us-ascii?Q?OMQ3SVd9YQCFK1YRwtlkbvDjNCQ8blLfG+Iae+NbfDM01/iDtxwMrYea9I73?= =?us-ascii?Q?0SiTKtS6u/nXsmBZjQUfp+jt1Qjka4ws1iuR+w2oxDRBkXDf14b79WI+QzQH?= =?us-ascii?Q?T2kPjOjaCHveOtidQOqaBKSTRf5D2H85K4JRADq1GSJUeWqam5vRL19RXUit?= =?us-ascii?Q?dk3ZSFghRnFHSApnjjWt7PXELgw3YiSIzdunJ7H/2IgiNWEvWoBQeoI1ntOS?= =?us-ascii?Q?Q1xHcJOCac0nyhEVpVv6XEvrKJ6qwNrvFi6iASG9TBo2xcWhu1UD0AYOrer4?= =?us-ascii?Q?u6YcAiJK4ONDzaPNVMiu0HdkPgklC43h88EfbSSQMU4Sx9Asqtkv6WbKkfO+?= =?us-ascii?Q?JShs1hRBJKmOOozb9/qyTEkBblINYJueQ9pMkUOn9f5rsWirV+uf3PHRECMU?= =?us-ascii?Q?LyEK68dUStctyndOsIuuibBSl5YvEN8xQel/UvZdxFbNIhPtIffP7evTsXct?= =?us-ascii?Q?p0abnQEYmJpBdEuvYkDBJTOVknshAbVgWodp23z1sYrWBvekqCl5Hf17PwCf?= =?us-ascii?Q?DkPLGBoz8IYogDmVH0btX6uUY4+yziUBbOvbfDdeAnkyK/kzeeH0bCHlllow?= =?us-ascii?Q?Niv6cZz5mqfLzO3rf3AUPDY6rjhTA5mleLGaYO2ABWgkMfcLrMJSEerY+4QF?= =?us-ascii?Q?9HPHNzhpLdA749KfSP62P7jWBf2GygQZASJUMIw1vysVcB2QB49I3fHEtcoY?= =?us-ascii?Q?Og=3D=3D?= X-MS-Exchange-AntiSpam-ExternalHop-MessageData-ChunkCount: 1 X-MS-Exchange-AntiSpam-ExternalHop-MessageData-0: =?us-ascii?Q?auEpgGJ5aUqJhWt2U0/Mkn7BrbYAZF+RHNg9UkWaiA5ZXwGg48F5r9r51QTc?= =?us-ascii?Q?Mg71W0i+rxWXnXDB/JrWxAdji/pcS6gYdviFSLRZoj5r/09fjg3ozk9qQTk5?= =?us-ascii?Q?LwSJJ8X01cNDJEtX0QFEIQfNa3IUhGoWwAjCXvCmxvtd8Ai6zBZeuRUZPndM?= =?us-ascii?Q?+6I0BaGxlYffDA2Pq9PXQMIuBDbUPcFJvAsJ/my5q1Zjf/d/xUQYC8MfjAUv?= =?us-ascii?Q?E/MALrqUcBbf1G6iks8G7Q2ULPQBD4Sr0AjwuIZE2SXNqfLT+M6xPROoJaZL?= =?us-ascii?Q?lJJXC7s4ebV7xJIjOtq/V1DP9E8VV5r7sL/pfJ60aAiA0vGbfEKzoKbRqZs2?= =?us-ascii?Q?0LI8+mUIcNivSqNWpU+H3HmIo7s9ZkVSqw2I9GNHgB59L/CWdZgDFDE0vpKN?= =?us-ascii?Q?OviFLm9WCReaPoEqJj7c1OvDNctUoRfOOfK0yq4Gg/YakdmRfF2fvhk8qLvR?= =?us-ascii?Q?xHtAz3JQhEIsgw6IqTEa0w7gBT+7pHojflf+n1iWzDpJbFr3qE4jqes+NWEF?= =?us-ascii?Q?TSUBy0WixSTndHw0qj7Sm2jERuWBJEUq+GVRsMvuZEBZtvy/ojOKmtybcyid?= =?us-ascii?Q?VJDvNRqA3DNsyFN+PO6Da27rLmQzsr9F1eMwK1WODBexkpJwT6cNTzEyUdZt?= =?us-ascii?Q?0w6aIHyuM+AiaBo8J7dU50clXX6WWNZ2nObTV7iJXW1uqyLU8/j+XdEKAqk5?= =?us-ascii?Q?99mDrZKXntSQyrgbSzGFdA5PyYlUQSxpedFO/bXQ6txvW3ozDzBmVArzAlRM?= =?us-ascii?Q?6GcBS6orLhRbVXkLUjZVekvpy+0Y0tKESfXbxX2Z1MiOt0aZWios9hshWjHU?= =?us-ascii?Q?l3m40KlDym6BQH/BljJEVBwAeWFUWXMjhjwa1Zw5SU5K6EN22eE4RbhbSGsO?= =?us-ascii?Q?hMF3Yy523OjgiZTeGfkTpUjH/ayeINhlVOmdDf8R+hlULPTgHZtTI043lh0H?= =?us-ascii?Q?v5/9T65wz/T/rcSJ3CLjQeWzop7TN4E7Uk1ZUVzd5fE=3D?= X-OriginatorOrg: oracle.com X-MS-Exchange-CrossTenant-Network-Message-Id: 6127e6f2-a361-449d-471f-08db950c4dbd X-MS-Exchange-CrossTenant-AuthSource: SN6PR10MB3022.namprd10.prod.outlook.com X-MS-Exchange-CrossTenant-AuthAs: Internal X-MS-Exchange-CrossTenant-OriginalArrivalTime: 04 Aug 2023 17:00:28.5940 (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: 3LWLMoZ0eeUWD5WnsyOgJ/QYUBMFaZ2XUzE/oN8ZuJE5HoDmr7Q2u06AUglyw9/dOXaqahkcPM/8JYrdkAMhXg== X-MS-Exchange-Transport-CrossTenantHeadersStamped: CH0PR10MB4939 X-Proofpoint-Virus-Version: vendor=baseguard engine=ICAP:2.0.267,Aquarius:18.0.957,Hydra:6.0.591,FMLib:17.11.176.26 definitions=2023-08-04_17,2023-08-03_01,2023-05-22_02 X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 suspectscore=0 spamscore=0 phishscore=0 bulkscore=0 mlxscore=0 adultscore=0 mlxlogscore=999 malwarescore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2306200000 definitions=main-2308040151 X-Proofpoint-GUID: xS_U-pDC2ZxjaOzu5KYktNiTOmdHJga7 X-Proofpoint-ORIG-GUID: xS_U-pDC2ZxjaOzu5KYktNiTOmdHJga7 Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Type: text/plain; charset="utf-8" All calls to mas_adopt_children() currently pass the parent as the node in the maple state. Allow for the parent pointer that is passed in to be used instead. Signed-off-by: Liam R. Howlett --- lib/maple_tree.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index cf41e0dbb87b..8e94f5495a97 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -1702,7 +1702,7 @@ static inline void mas_adopt_children(struct ma_state= *mas, struct maple_enode *parent) { enum maple_type type =3D mte_node_type(parent); - struct maple_node *node =3D mas_mn(mas); + struct maple_node *node =3D mte_to_node(parent); void __rcu **slots =3D ma_slots(node, type); unsigned long *pivots =3D ma_pivots(node, type); struct maple_enode *child; --=20 2.39.2 From nobody Thu Sep 11 15:26:07 2025 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 vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id 02C7BC001DE for ; Fri, 4 Aug 2023 17:01:22 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S229839AbjHDRBV (ORCPT ); Fri, 4 Aug 2023 13:01:21 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:36560 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S231558AbjHDRBQ (ORCPT ); Fri, 4 Aug 2023 13:01:16 -0400 Received: from mx0a-00069f02.pphosted.com (mx0a-00069f02.pphosted.com [205.220.165.32]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 8DB8D4EFB for ; Fri, 4 Aug 2023 10:00:55 -0700 (PDT) Received: from pps.filterd (m0333521.ppops.net [127.0.0.1]) by mx0b-00069f02.pphosted.com (8.17.1.19/8.17.1.19) with ESMTP id 374EiDn7002929; Fri, 4 Aug 2023 17:00:37 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=m65lrO2qFmAh9M4Ry8wuMUS7xfZox23yZiJJhAn8EW0=; b=siBp/O0fpVZ2ngoPKQvky8N6TfJNdNd0d0bNRxBMTMpcqha367GYghbNyg62RooCDG+k y1WN2uYBCm1gqmRZ1R/MGpSD0Ddei0tGySv9EjM98KJOsB/LaZ59O7b6AbUT60KYc6Vq eu2TsbclXyh+RclgYSPckfG2WBpyZbpPfQ0MDKwqtq9/orJX1CP3fpRVqwQ+9zf84NGc w/TX4D139fFYTxUX5RzeTvmRPBm1JQ5G9Bgjku7eumHcBKHjz0eeCt37WX0GPMv9ncEz UfgQxqNGcXJ6eJTTpc5LBQqPXZh16Dm9+zt1PVbQndJqWH/FiKnSfn5DR8DpeeMR6tHe OQ== Received: from phxpaimrmta01.imrmtpd1.prodappphxaev1.oraclevcn.com (phxpaimrmta01.appoci.oracle.com [138.1.114.2]) by mx0b-00069f02.pphosted.com (PPS) with ESMTPS id 3s4spcc9w7-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Fri, 04 Aug 2023 17:00:36 +0000 Received: from pps.filterd (phxpaimrmta01.imrmtpd1.prodappphxaev1.oraclevcn.com [127.0.0.1]) by phxpaimrmta01.imrmtpd1.prodappphxaev1.oraclevcn.com (8.17.1.19/8.17.1.19) with ESMTP id 374FOjaY011606; Fri, 4 Aug 2023 17:00:36 GMT Received: from nam10-bn7-obe.outbound.protection.outlook.com (mail-bn7nam10lp2107.outbound.protection.outlook.com [104.47.70.107]) by phxpaimrmta01.imrmtpd1.prodappphxaev1.oraclevcn.com (PPS) with ESMTPS id 3s8m2s3hxt-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Fri, 04 Aug 2023 17:00:36 +0000 ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=gOxgs4DzR+mhVvgUcO4Z+11Xh6M4rSo7H2+u+aEvxnqRqNvbHxAiwnLEB1/euAXvRG0T1dSB0KePgSoxRGh6Kry88ZmNu95cM7zFbxfsprEIvG7H0NP1IoEhM4nwqVch3mvCu8Okexi5KaaKeMHjMrP/NjZT8ZHg7X/H7llP9O6D5RQxEYK+aPlkucQdioDWPqqC2TEtz+uIIct8qbciRABo/dstwj6W6gQWoYQuixF/hqLJK71mV6Mw2Qiozk1ySs5Sej63YFrLZXl3npIy0SJnuHC50XyZn2y36pIVNfldYSPToEVmx/tTGqNANIXK9fbPvLmGSmFtO4cEI+JzCg== 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=m65lrO2qFmAh9M4Ry8wuMUS7xfZox23yZiJJhAn8EW0=; b=YsSuwzH9Qo4oIUwOHj5DguCzJdZXe8K/PfoIeQGa2XivRpaTWqbfHtfI4IFIGvATtBlHdQLVq2sEN2dyG+Am4HjY5D9g9dr1fJBRegcM5sIJ/fzXp0ef61FumuWPAu8lL8ZBYwlKnr9FwqU5OzIfpYMGAF0cxiuMIDNr8eUlfnmddXgSNXzdhLpzbmRV+ABqBxsisO23X89DvC3A8jhntpN2pf/8rE3kX1Nr8TTLDpbiTPl5Qb5PJWUsZrV2tXfXPCOl9oak4oppw2okh8Fe3iLIv40pvZq58pq2Mw/4mmHzyH0T/q/tf+ytJdSBUqmReAQBzupDBGSUHktJ2OvFfA== 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=m65lrO2qFmAh9M4Ry8wuMUS7xfZox23yZiJJhAn8EW0=; b=z6ILSysOieTbcmXsux5cQ+XPQyTNy8ux7XmrL5p+gIXz40gItzlezt0zNk7mjLigx1nWUyem08tCxb7GfP9VIeQ05cCL4I59bzbWgKQjJLo2sXcdSF150j9IBJQ+qXGcDQQeOPrFFidn/hR4e/tnlnkLt9dfeindWM1B0VYF7EM= Received: from SN6PR10MB3022.namprd10.prod.outlook.com (2603:10b6:805:d8::25) by CH0PR10MB4939.namprd10.prod.outlook.com (2603:10b6:610:c0::14) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.6652.21; Fri, 4 Aug 2023 17:00:32 +0000 Received: from SN6PR10MB3022.namprd10.prod.outlook.com ([fe80::26d3:6f41:6415:8c35]) by SN6PR10MB3022.namprd10.prod.outlook.com ([fe80::26d3:6f41:6415:8c35%3]) with mapi id 15.20.6631.046; Fri, 4 Aug 2023 17:00:32 +0000 From: "Liam R. Howlett" To: Andrew Morton Cc: maple-tree@lists.infradead.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, "Paul E . McKenney" , Suren Baghdasaryan , Matthew Wilcox , "Liam R. Howlett" Subject: [PATCH 6/6] maple_tree: Replace data before marking dead in split and spanning store Date: Fri, 4 Aug 2023 12:59:51 -0400 Message-Id: <20230804165951.2661157-7-Liam.Howlett@oracle.com> X-Mailer: git-send-email 2.39.2 In-Reply-To: <20230804165951.2661157-1-Liam.Howlett@oracle.com> References: <20230804165951.2661157-1-Liam.Howlett@oracle.com> Content-Transfer-Encoding: quoted-printable X-ClientProxiedBy: YT4PR01CA0166.CANPRD01.PROD.OUTLOOK.COM (2603:10b6:b01:ac::27) To SN6PR10MB3022.namprd10.prod.outlook.com (2603:10b6:805:d8::25) MIME-Version: 1.0 X-MS-PublicTrafficType: Email X-MS-TrafficTypeDiagnostic: SN6PR10MB3022:EE_|CH0PR10MB4939:EE_ X-MS-Office365-Filtering-Correlation-Id: ff35facf-918c-4829-5544-08db950c5081 X-MS-Exchange-SenderADCheck: 1 X-MS-Exchange-AntiSpam-Relay: 0 X-Microsoft-Antispam: BCL:0; X-Microsoft-Antispam-Message-Info: A/xJAayClsC2SomTNEBlCZ6rh/mmvUD8BsxpAqzrQhJ1ajxd7um82zAQuLr99R03k8xIlEnrylyG3piJZ916BF2EYYqRl0EADqHH0LPBmwpC67ilp1tOhA/OJug+9+BjY/xYGxnBzw9HadbglAHkerx3HoWLSA24eudeHkfzJzwnpnRql6wIftAgO2jK9bzIP/HMUxu0wDjoWBTzZIu3KJfw6FfDJCC55Args7ClHR7PkaxW2mnLZH8tPt1WIs1WKLQxO0e7Vvgdxlk8vLodebMn+RnxcnEvlrZ8aXpTU6lpicbXObbEmRYCUb+j5Ofx9NiHpT/iC5hcWxFBLVHOZ5m/o6F+CVR+7vSc1kvcFG1fEtLpCiIvwEOp7kxczzL6uO/6CBxHRv4zkuBxEY9M2oCAbDez/HVmJSCeY7jG0udwXjAN63/yUNWufMR/Q41S08ky344ULTexKflffNGIskqqgIfXXDm8fnp21wfdyWAptWFZE0Oh75pcoz3JODdnY58akyDN83qwBmQiWM8hH2XBfOrxcBoKXdq7f00E3M584SPWVeEEdYJ/MVJIgd4F 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)(366004)(396003)(39860400002)(346002)(376002)(136003)(186006)(451199021)(1800799003)(6666004)(6486002)(6512007)(86362001)(6506007)(26005)(1076003)(107886003)(36756003)(2616005)(83380400001)(38100700002)(5660300002)(41300700001)(8936002)(8676002)(4326008)(6916009)(66476007)(2906002)(66556008)(66946007)(316002)(30864003)(478600001)(54906003);DIR:OUT;SFP:1101; X-MS-Exchange-AntiSpam-MessageData-ChunkCount: 1 X-MS-Exchange-AntiSpam-MessageData-0: =?us-ascii?Q?drUee/OZjF9XdWStFvLeBlAphd/ZnNA5NcJrrcPSSDsMsRNAkjtZgcoIpJQN?= =?us-ascii?Q?V0CwNHWm37PrzZLYqrlNnZ4sWuhdmhPg3RAx4hhaE4p/oSgRkix60e4xSrCm?= =?us-ascii?Q?FibbsSuJQc/xcOIq95dL9c+OcwqL5cXUU8zEAxTmErNZpwefIUucpKMdKcKA?= =?us-ascii?Q?5HDpNZuVfrPVuhEiEL3skuwhlMV02R5nN5z/+u71KlhClrxub89uNn1XTMrh?= =?us-ascii?Q?CHUeEfOpquCcjeJ/Bbj9zyP7kUhHmpCSxO3zBxIDVQ0+BlPixpljvrDIvxLw?= =?us-ascii?Q?M2eA+1TdPM5KimTclPtUmeiSBAvLgQhjaABC4ipGIR5n+1lk3tSFKE/bOrp6?= =?us-ascii?Q?m5DWz7x/Gj8WaFCOAmFgTJa/2okK7Lu/YQGSBrLA+Ffraiir4E3nKkh9wY6/?= =?us-ascii?Q?wW/2quUG5E2OUrtAybPsSmetazXDmu9xYwsaPBObWhkArSfuumKlZrLfNmh1?= =?us-ascii?Q?Q8sy59vYeD+2usEUp5ubv674ooMmj8/QMOg+52iQA3yA6iT0waFf3d5OYKmp?= =?us-ascii?Q?YCJUIv1unL6NE9Lb3CweOmLZuwTj0ZRSSmUVVFfbGTOtjQUeq4+V817ACGBs?= =?us-ascii?Q?3vyG1gaQNUmbHBw0LB6RX/3Z+4w7LniMLxfKytj4SCoZ5QKGKowrZW0wTPtA?= =?us-ascii?Q?sm5bj6axAEQbbrtS5OuagHusmiszIPjXQQ/oGzpTcfAjc0OzSSNOIKfhqN1g?= =?us-ascii?Q?ICPWW4JeOgQzJ2Rl57pyfTL/CbOaghaZOCXPAQbe21DRUlR5ckoxnxyFCQUZ?= =?us-ascii?Q?jWYrd/0aotbmimewiQAD4H2Us8X6g9PRCwXUaucYGfGvkmroSKSCcNh+yb1c?= =?us-ascii?Q?GpNQw6FFCBZoH5m8ot8hkYxrSR5BPpmur7zA1ztCgUTa4hELE5cMu7jhO3+P?= =?us-ascii?Q?1/nyw9aArSZXoei4CALd9ghEYBDrnGim56PCZlAcC59NL3cxffYJT6arTgK3?= =?us-ascii?Q?w9Iz+9OgGPaXiMBzN6obXp0wbm/GtEA9q72F5YF8IzLzQjsAKe78PxKwTmNI?= =?us-ascii?Q?lxqAItg4u/tJ264rNSCvhuyf7kVWvcmZVvVTYCUvOdAZHFu/d2ijjjzhZ1ie?= =?us-ascii?Q?3QxDnIiE3IE4ffH+hqMgCW8G8PQzZuv7h15qzHTITGB3MA0JERXLsT5u3p41?= =?us-ascii?Q?7WDWO42S9O0zRGLaooTv8uLfLru6O1YTpwzVfXR5pUQ4st4Cn0yIP5QG4MMe?= =?us-ascii?Q?jPYK4D1mzMKz15ml/8dZ1xxNUfJjw1dDPbs7OiXJCMBb62WKS4gYmUDhGXjI?= =?us-ascii?Q?S/DanANuiEGsBaGQRb9yTbfcpWUrKsgPuBj+3UlrMBdPkALlFg3yxPw5j5fj?= =?us-ascii?Q?vHTMswh7/dbGiFkulIFpDhs7+ISne8646+tfU5H088B0K8sjqGXgdqkLlt37?= =?us-ascii?Q?KgMdfyph1odSLW+Ve7kVmpqXcAkyPfzp7H2zmmuDonP+BqEHS2o52Nr4j65V?= =?us-ascii?Q?ocBk8LnpeAwY5bRhO1iDUjrha5RqbTmqPV7qAjpL5sJwy/ybMKSoBZIKBiXq?= =?us-ascii?Q?Ep7tfP5AVWsPmus91pKLccXLNdwWUAGVgq50odYifNE65edUBEA0PQUKdPBY?= =?us-ascii?Q?rGZQ/AG+q2KQ8lw4P27OKu7VkchOQtm5orf7q2Mq2/eSrxRLRMtULAbYcmKM?= =?us-ascii?Q?dA=3D=3D?= X-MS-Exchange-AntiSpam-ExternalHop-MessageData-ChunkCount: 1 X-MS-Exchange-AntiSpam-ExternalHop-MessageData-0: =?us-ascii?Q?g/CkzaosCmgi1TUiWOUnHxjf1Q08RQuMzM8Rs0C7AlpxiMmzh2q1v4y7Yvgl?= =?us-ascii?Q?8jgTAD60sadnvxRlQesFEaIlRNCEK5RAguwxaZo5KFH0y2uhJht4hTXQyXdT?= =?us-ascii?Q?akQWblaBSMq0KXBwntHS9k+cWTeQFTqbMuq4Txh8eKNgTR72+ZY9K0CW2HYz?= =?us-ascii?Q?44FUfkyPnoZ4u27RU+3p5xhSQ79/+DcMOyVuwqnu3n2lfKQoJjY1GE7scBrT?= =?us-ascii?Q?I0sUrqDpU/8DL2A4dAQydy0Yr79zDWsdGsRIBHSjH69PFTOD1B5nKkq0y9WJ?= =?us-ascii?Q?61Etxr9QnQGtSb9SFbR1rQUytW07+OgeU0ZTKYMO7E6MS/cD/wsXO0xuCAk2?= =?us-ascii?Q?jXQ+nazOssYlWSosfhdcyYSD573rX5MdfRaUjH2Mt4gNgz/ynYwE4BhgdwYT?= =?us-ascii?Q?XMihwZnDG4v98vF1hSCSNdx7QOxlk/RROF27yH67WRvENLb+6OVcFNqArDup?= =?us-ascii?Q?PHmFeJjTa5Vj9tRNiaDFm8lBxuwUIXbsZ1nrHNnysSOZTyh/d/wlmxGE5zhU?= =?us-ascii?Q?WmrKbSwjvXH+3SENSkEqAp2NFAilxE4Kr4DUhh3XIrdoIdRksvT0ZwDpoaFU?= =?us-ascii?Q?nIOAKC4YEjjSp6nSrkmUbWVaMlqLtNfvBBgoAEN5gxqzHJPiYBV/250XHXct?= =?us-ascii?Q?XjKqbxiwYrBgwWJAiOEOEA6sIcHY4UTdwlD5DZUNJcC1jT3ohLxNyBZ94syN?= =?us-ascii?Q?y7gHMalpdyNiNKwAy10OGzWGZ9cXtyPL1kNawcT8bujAIJOtUaMAtsW3TexL?= =?us-ascii?Q?oWS3iRmANKQkK5ceF/xYXxIKYaauy+8UmvivMqKz6rQ5BqXy5QUg3lHRW7GG?= =?us-ascii?Q?v0xoydKnhtG/n7TwE2kBWvzirxB0F1uTtVKaQa46xgTB1FSOHChlaMnrCPjo?= =?us-ascii?Q?wB2qxyS2FeOHi30oVjO00jgybs3ciVIdSl89UsqlsIOMoQA2Ge/4RNfmxHtf?= =?us-ascii?Q?VJCBsElcUcWJmhal0XAS5GO536xLHwaeWzFHnb5KkH0=3D?= X-OriginatorOrg: oracle.com X-MS-Exchange-CrossTenant-Network-Message-Id: ff35facf-918c-4829-5544-08db950c5081 X-MS-Exchange-CrossTenant-AuthSource: SN6PR10MB3022.namprd10.prod.outlook.com X-MS-Exchange-CrossTenant-AuthAs: Internal X-MS-Exchange-CrossTenant-OriginalArrivalTime: 04 Aug 2023 17:00:32.8119 (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: HmoyJepjIlIaW4bXerUYLblY1dN9U4QGscerk4AGClSNE/hXudPAH7yRRXd1yMGekDXyL619z4QiPDSU6Dubzw== X-MS-Exchange-Transport-CrossTenantHeadersStamped: CH0PR10MB4939 X-Proofpoint-Virus-Version: vendor=baseguard engine=ICAP:2.0.267,Aquarius:18.0.957,Hydra:6.0.591,FMLib:17.11.176.26 definitions=2023-08-04_16,2023-08-03_01,2023-05-22_02 X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 malwarescore=0 bulkscore=0 phishscore=0 mlxscore=0 spamscore=0 adultscore=0 suspectscore=0 mlxlogscore=999 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2306200000 definitions=main-2308040151 X-Proofpoint-ORIG-GUID: MKoSml2S4K5IJulrLV5KuaJWlkqmBszm X-Proofpoint-GUID: MKoSml2S4K5IJulrLV5KuaJWlkqmBszm Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Type: text/plain; charset="utf-8" Reorder the operations for split and spanning stores so that new data is placed in the tree prior to marking the old data as dead. This will limit re-walks on dead data to just once instead of a retry loop. The order of operations is as follows: Create the new data, put the new data in place, mark the top node of the old data as dead. Then repair parent links in the reused nodes through all levels of the tree, following the new nodes downwards. Finally walk the top dead node looking for nodes that are no longer used, or subtrees that should be destroyed (marked dead throughout then freed), follow the partially used nodes downwards to discover other dead nodes and subtrees. Signed-off-by: Liam R. Howlett --- lib/maple_tree.c | 493 ++++++++++++++++------------------------------- 1 file changed, 168 insertions(+), 325 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 8e94f5495a97..ffb9d15bd815 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -982,27 +982,9 @@ static inline void mat_add(struct ma_topiary *mat, mat->tail =3D dead_enode; } =20 -static void mte_destroy_walk(struct maple_enode *, struct maple_tree *); -static inline void mas_free(struct ma_state *mas, struct maple_enode *used= ); - -/* - * mas_mat_free() - Free all nodes in a dead list. - * @mas - the maple state - * @mat - the ma_topiary linked list of dead nodes to free. - * - * Free walk a dead list. - */ -static void mas_mat_free(struct ma_state *mas, struct ma_topiary *mat) -{ - struct maple_enode *next; - - while (mat->head) { - next =3D mte_to_mat(mat->head)->next; - mas_free(mas, mat->head); - mat->head =3D next; - } -} - +static void mt_free_walk(struct rcu_head *head); +static void mt_destroy_walk(struct maple_enode *enode, struct maple_tree *= mt, + bool free); /* * mas_mat_destroy() - Free all nodes and subtrees in a dead list. * @mas - the maple state @@ -1013,10 +995,15 @@ static void mas_mat_free(struct ma_state *mas, struc= t ma_topiary *mat) static void mas_mat_destroy(struct ma_state *mas, struct ma_topiary *mat) { struct maple_enode *next; + struct maple_node *node; + bool in_rcu =3D mt_in_rcu(mas->tree); =20 while (mat->head) { next =3D mte_to_mat(mat->head)->next; - mte_destroy_walk(mat->head, mat->mtree); + node =3D mte_to_node(mat->head); + mt_destroy_walk(mat->head, mas->tree, !in_rcu); + if (in_rcu) + call_rcu(&node->rcu, mt_free_walk); mat->head =3D next; } } @@ -1759,11 +1746,11 @@ static inline void mas_replace_node(struct ma_state= *mas, } =20 /* - * mas_new_child() - Find the new child of a node. - * @mas: the maple state + * mas_find_child() - Find a child who has the parent @mas->node. + * @mas: the maple state with the parent. * @child: the maple state to store the child. */ -static inline bool mas_new_child(struct ma_state *mas, struct ma_state *ch= ild) +static inline bool mas_find_child(struct ma_state *mas, struct ma_state *c= hild) __must_hold(mas->tree->ma_lock) { enum maple_type mt; @@ -2065,56 +2052,6 @@ static inline void mab_mas_cp(struct maple_big_node = *b_node, } } =20 -/* - * mas_descend_adopt() - Descend through a sub-tree and adopt children. - * @mas: the maple state with the maple encoded node of the sub-tree. - * - * Descend through a sub-tree and adopt children who do not have the corre= ct - * parents set. Follow the parents which have the correct parents as they= are - * the new entries which need to be followed to find other incorrectly set - * parents. - */ -static inline void mas_descend_adopt(struct ma_state *mas) -{ - struct ma_state list[3], next[3]; - int i, n; - - /* - * At each level there may be up to 3 correct parent pointers which indic= ates - * the new nodes which need to be walked to find any new nodes at a lower= level. - */ - - for (i =3D 0; i < 3; i++) { - list[i] =3D *mas; - list[i].offset =3D 0; - next[i].offset =3D 0; - } - next[0] =3D *mas; - - while (!mte_is_leaf(list[0].node)) { - n =3D 0; - for (i =3D 0; i < 3; i++) { - if (mas_is_none(&list[i])) - continue; - - if (i && list[i-1].node =3D=3D list[i].node) - continue; - - while ((n < 3) && (mas_new_child(&list[i], &next[n]))) - n++; - - mas_adopt_children(&list[i], list[i].node); - } - - while (n < 3) - next[n++].node =3D MAS_NONE; - - /* descend by setting the list to the children */ - for (i =3D 0; i < 3; i++) - list[i] =3D next[i]; - } -} - /* * mas_bulk_rebalance() - Rebalance the end of a tree after a bulk insert. * @mas: The maple state @@ -2304,98 +2241,6 @@ static inline void mas_wr_node_walk(struct ma_wr_sta= te *wr_mas) wr_mas->offset_end =3D mas->offset =3D offset; } =20 -/* - * mas_topiary_range() - Add a range of slots to the topiary. - * @mas: The maple state - * @destroy: The topiary to add the slots (usually destroy) - * @start: The starting slot inclusively - * @end: The end slot inclusively - */ -static inline void mas_topiary_range(struct ma_state *mas, - struct ma_topiary *destroy, unsigned char start, unsigned char end) -{ - void __rcu **slots; - unsigned char offset; - - MAS_BUG_ON(mas, mte_is_leaf(mas->node)); - - slots =3D ma_slots(mas_mn(mas), mte_node_type(mas->node)); - for (offset =3D start; offset <=3D end; offset++) { - struct maple_enode *enode =3D mas_slot_locked(mas, slots, offset); - - if (mte_dead_node(enode)) - continue; - - mat_add(destroy, enode); - } -} - -/* - * mast_topiary() - Add the portions of the tree to the removal list; eith= er to - * be freed or discarded (destroy walk). - * @mast: The maple_subtree_state. - */ -static inline void mast_topiary(struct maple_subtree_state *mast) -{ - MA_WR_STATE(wr_mas, mast->orig_l, NULL); - unsigned char r_start, r_end; - unsigned char l_start, l_end; - void __rcu **l_slots, **r_slots; - - wr_mas.type =3D mte_node_type(mast->orig_l->node); - mast->orig_l->index =3D mast->orig_l->last; - mas_wr_node_walk(&wr_mas); - l_start =3D mast->orig_l->offset + 1; - l_end =3D mas_data_end(mast->orig_l); - r_start =3D 0; - r_end =3D mast->orig_r->offset; - - if (r_end) - r_end--; - - l_slots =3D ma_slots(mas_mn(mast->orig_l), - mte_node_type(mast->orig_l->node)); - - r_slots =3D ma_slots(mas_mn(mast->orig_r), - mte_node_type(mast->orig_r->node)); - - if ((l_start < l_end) && - mte_dead_node(mas_slot_locked(mast->orig_l, l_slots, l_start))) { - l_start++; - } - - if (mte_dead_node(mas_slot_locked(mast->orig_r, r_slots, r_end))) { - if (r_end) - r_end--; - } - - if ((l_start > r_end) && (mast->orig_l->node =3D=3D mast->orig_r->node)) - return; - - /* At the node where left and right sides meet, add the parts between */ - if (mast->orig_l->node =3D=3D mast->orig_r->node) { - return mas_topiary_range(mast->orig_l, mast->destroy, - l_start, r_end); - } - - /* mast->orig_r is different and consumed. */ - if (mte_is_leaf(mast->orig_r->node)) - return; - - if (mte_dead_node(mas_slot_locked(mast->orig_l, l_slots, l_end))) - l_end--; - - - if (l_start <=3D l_end) - mas_topiary_range(mast->orig_l, mast->destroy, l_start, l_end); - - if (mte_dead_node(mas_slot_locked(mast->orig_r, r_slots, r_start))) - r_start++; - - if (r_start <=3D r_end) - mas_topiary_range(mast->orig_r, mast->destroy, 0, r_end); -} - /* * mast_rebalance_next() - Rebalance against the next node * @mast: The maple subtree state @@ -2431,7 +2276,7 @@ static inline void mast_rebalance_prev(struct maple_s= ubtree_state *mast) /* * mast_spanning_rebalance() - Rebalance nodes with nearest neighbour favo= uring * the node to the right. Checking the nodes to the right then the left a= t each - * level upwards until root is reached. Free and destroy as needed. + * level upwards until root is reached. * Data is copied into the @mast->bn. * @mast: The maple_subtree_state. */ @@ -2440,8 +2285,6 @@ bool mast_spanning_rebalance(struct maple_subtree_sta= te *mast) { struct ma_state r_tmp =3D *mast->orig_r; struct ma_state l_tmp =3D *mast->orig_l; - struct maple_enode *ancestor =3D NULL; - unsigned char start, end; unsigned char depth =3D 0; =20 r_tmp =3D *mast->orig_r; @@ -2450,87 +2293,25 @@ bool mast_spanning_rebalance(struct maple_subtree_s= tate *mast) mas_ascend(mast->orig_r); mas_ascend(mast->orig_l); depth++; - if (!ancestor && - (mast->orig_r->node =3D=3D mast->orig_l->node)) { - ancestor =3D mast->orig_r->node; - end =3D mast->orig_r->offset - 1; - start =3D mast->orig_l->offset + 1; - } - if (mast->orig_r->offset < mas_data_end(mast->orig_r)) { - if (!ancestor) { - ancestor =3D mast->orig_r->node; - start =3D 0; - } - mast->orig_r->offset++; do { mas_descend(mast->orig_r); mast->orig_r->offset =3D 0; - depth--; - } while (depth); + } while (--depth); =20 mast_rebalance_next(mast); - do { - unsigned char l_off =3D 0; - struct maple_enode *child =3D r_tmp.node; - - mas_ascend(&r_tmp); - if (ancestor =3D=3D r_tmp.node) - l_off =3D start; - - if (r_tmp.offset) - r_tmp.offset--; - - if (l_off < r_tmp.offset) - mas_topiary_range(&r_tmp, mast->destroy, - l_off, r_tmp.offset); - - if (l_tmp.node !=3D child) - mat_add(mast->free, child); - - } while (r_tmp.node !=3D ancestor); - *mast->orig_l =3D l_tmp; return true; - } else if (mast->orig_l->offset !=3D 0) { - if (!ancestor) { - ancestor =3D mast->orig_l->node; - end =3D mas_data_end(mast->orig_l); - } - mast->orig_l->offset--; do { mas_descend(mast->orig_l); mast->orig_l->offset =3D mas_data_end(mast->orig_l); - depth--; - } while (depth); + } while (--depth); =20 mast_rebalance_prev(mast); - do { - unsigned char r_off; - struct maple_enode *child =3D l_tmp.node; - - mas_ascend(&l_tmp); - if (ancestor =3D=3D l_tmp.node) - r_off =3D end; - else - r_off =3D mas_data_end(&l_tmp); - - if (l_tmp.offset < r_off) - l_tmp.offset++; - - if (l_tmp.offset < r_off) - mas_topiary_range(&l_tmp, mast->destroy, - l_tmp.offset, r_off); - - if (r_tmp.node !=3D child) - mat_add(mast->free, child); - - } while (l_tmp.node !=3D ancestor); - *mast->orig_r =3D r_tmp; return true; } @@ -2542,36 +2323,24 @@ bool mast_spanning_rebalance(struct maple_subtree_s= tate *mast) } =20 /* - * mast_ascend_free() - Add current original maple state nodes to the free= list - * and ascend. + * mast_ascend() - Ascend the original left and right maple states. * @mast: the maple subtree state. * - * Ascend the original left and right sides and add the previous nodes to = the - * free list. Set the slots to point to the correct location in the new n= odes. + * Ascend the original left and right sides. Set the offsets to point to = the + * data already in the new tree (@mast->l and @mast->r). */ -static inline void -mast_ascend_free(struct maple_subtree_state *mast) +static inline void mast_ascend(struct maple_subtree_state *mast) { MA_WR_STATE(wr_mas, mast->orig_r, NULL); - struct maple_enode *left =3D mast->orig_l->node; - struct maple_enode *right =3D mast->orig_r->node; - mas_ascend(mast->orig_l); mas_ascend(mast->orig_r); - mat_add(mast->free, left); - - if (left !=3D right) - mat_add(mast->free, right); =20 mast->orig_r->offset =3D 0; mast->orig_r->index =3D mast->r->max; /* last should be larger than or equal to index */ if (mast->orig_r->last < mast->orig_r->index) mast->orig_r->last =3D mast->orig_r->index; - /* - * The node may not contain the value so set slot to ensure all - * of the nodes contents are freed or destroyed. - */ + wr_mas.type =3D mte_node_type(mast->orig_r->node); mas_wr_node_walk(&wr_mas); /* Set up the left side of things */ @@ -2750,66 +2519,152 @@ static inline void mast_set_split_parents(struct m= aple_subtree_state *mast, } =20 /* - * mas_wmb_replace() - Write memory barrier and replace - * @mas: The maple state - * @free: the maple topiary list of nodes to free - * @destroy: The maple topiary list of nodes to destroy (walk and free) + * mas_topiary_node() - Dispose of a singe node + * @mas: The maple state for pushing nodes + * @enode: The encoded maple node + * @in_rcu: If the tree is in rcu mode * - * Updates gap as necessary. + * The node will either be RCU freed or pushed back on the maple state. */ -static inline void mas_wmb_replace(struct ma_state *mas, - struct ma_topiary *free, - struct ma_topiary *destroy) +static inline void mas_topiary_node(struct ma_state *mas, + struct maple_enode *enode, bool in_rcu) { - struct maple_enode *old_enode; + struct maple_node *tmp; =20 - if (mte_is_root(mas->node)) { - old_enode =3D mas_root_locked(mas); - } else { - unsigned char offset =3D mte_parent_slot(mas->node); - void __rcu **slots =3D ma_slots(mte_parent(mas->node), - mas_parent_type(mas, mas->node)); + if (enode =3D=3D MAS_NONE) + return; =20 - old_enode =3D mas_slot_locked(mas, slots, offset); - } + tmp =3D mte_to_node(enode); + mte_set_node_dead(enode); + if (in_rcu) + ma_free_rcu(tmp); + else + mas_push_node(mas, tmp); +} =20 - /* Insert the new data in the tree */ +/* + * mas_topiary_replace() - Replace the data with new data, then repair the + * parent links within the new tree. Iterate over the dead sub-tree and c= ollect + * the dead subtrees and topiary the nodes that are no longer of use. + * + * The new tree will have up to three children with the correct parent. K= eep + * track of the new entries as they need to be followed to find the next l= evel + * of new entries. + * + * The old tree will have up to three children with the old parent. Keep = track + * of the old entries as they may have more nodes below replaced. Nodes w= ithin + * [index, last] are dead subtrees, others need to be freed and followed. + * + * @mas: The maple state pointing at the new data + * @old_enode: The maple encoded node being replaced + * + */ +static inline void mas_topiary_replace(struct ma_state *mas, + struct maple_enode *old_enode) +{ + struct ma_state tmp[3], tmp_next[3]; + MA_TOPIARY(subtrees, mas->tree); + bool in_rcu; + int i, n; + + /* Place data in tree & then mark node as old */ mas_put_in_tree(mas, old_enode); =20 - if (!mte_is_leaf(mas->node)) - mas_descend_adopt(mas); + /* Update the parent pointers in the tree */ + tmp[0] =3D *mas; + tmp[0].offset =3D 0; + tmp[1].node =3D MAS_NONE; + tmp[2].node =3D MAS_NONE; + while (!mte_is_leaf(tmp[0].node)) { + n =3D 0; + for (i =3D 0; i < 3; i++) { + if (mas_is_none(&tmp[i])) + continue; + + while (n < 3) { + if (!mas_find_child(&tmp[i], &tmp_next[n])) + break; + n++; + } + + mas_adopt_children(&tmp[i], tmp[i].node); + } =20 - mas_mat_free(mas, free); + if (MAS_WARN_ON(mas, n =3D=3D 0)) + break; =20 - if (destroy) - mas_mat_destroy(mas, destroy); + while (n < 3) + tmp_next[n++].node =3D MAS_NONE; =20 - if (mte_is_leaf(mas->node)) - return; + for (i =3D 0; i < 3; i++) + tmp[i] =3D tmp_next[i]; + } =20 - mas_update_gap(mas); + /* Collect the old nodes that need to be discarded */ + if (mte_is_leaf(old_enode)) + return mas_free(mas, old_enode); + + tmp[0] =3D *mas; + tmp[0].offset =3D 0; + tmp[0].node =3D old_enode; + tmp[1].node =3D MAS_NONE; + tmp[2].node =3D MAS_NONE; + in_rcu =3D mt_in_rcu(mas->tree); + do { + n =3D 0; + for (i =3D 0; i < 3; i++) { + if (mas_is_none(&tmp[i])) + continue; + + while (n < 3) { + if (!mas_find_child(&tmp[i], &tmp_next[n])) + break; + + if ((tmp_next[n].min >=3D tmp_next->index) && + (tmp_next[n].max <=3D tmp_next->last)) { + mat_add(&subtrees, tmp_next[n].node); + tmp_next[n].node =3D MAS_NONE; + } else { + n++; + } + } + } + + if (MAS_WARN_ON(mas, n =3D=3D 0)) + break; + + while (n < 3) + tmp_next[n++].node =3D MAS_NONE; + + for (i =3D 0; i < 3; i++) { + mas_topiary_node(mas, tmp[i].node, in_rcu); + tmp[i] =3D tmp_next[i]; + } + } while (!mte_is_leaf(tmp[0].node)); + + for (i =3D 0; i < 3; i++) + mas_topiary_node(mas, tmp[i].node, in_rcu); + + mas_mat_destroy(mas, &subtrees); } =20 /* - * mast_new_root() - Set a new tree root during subtree creation - * @mast: The maple subtree state + * mas_wmb_replace() - Write memory barrier and replace * @mas: The maple state + * @old: The old maple encoded node that is being replaced. + * + * Updates gap as necessary. */ -static inline void mast_new_root(struct maple_subtree_state *mast, - struct ma_state *mas) +static inline void mas_wmb_replace(struct ma_state *mas, + struct maple_enode *old_enode) { - mas_mn(mast->l)->parent =3D ma_parent_ptr(mas_tree_parent(mas)); - if (!mte_dead_node(mast->orig_l->node) && - !mte_is_root(mast->orig_l->node)) { - do { - mast_ascend_free(mast); - mast_topiary(mast); - } while (!mte_is_root(mast->orig_l->node)); - } - if ((mast->orig_l->node !=3D mas->node) && - (mast->l->depth > mas_mt_height(mas))) { - mat_add(mast->free, mas->node); - } + /* Insert the new data in the tree */ + mas_topiary_replace(mas, old_enode); + + if (mte_is_leaf(mas->node)) + return; + + mas_update_gap(mas); } =20 /* @@ -2995,12 +2850,11 @@ static int mas_spanning_rebalance(struct ma_state *= mas, unsigned char split, mid_split; unsigned char slot =3D 0; struct maple_enode *left =3D NULL, *middle =3D NULL, *right =3D NULL; + struct maple_enode *old_enode; =20 MA_STATE(l_mas, mas->tree, mas->index, mas->index); MA_STATE(r_mas, mas->tree, mas->index, mas->last); MA_STATE(m_mas, mas->tree, mas->index, mas->index); - MA_TOPIARY(free, mas->tree); - MA_TOPIARY(destroy, mas->tree); =20 /* * The tree needs to be rebalanced and leaves need to be kept at the same= level. @@ -3009,8 +2863,6 @@ static int mas_spanning_rebalance(struct ma_state *ma= s, mast->l =3D &l_mas; mast->m =3D &m_mas; mast->r =3D &r_mas; - mast->free =3D &free; - mast->destroy =3D &destroy; l_mas.node =3D r_mas.node =3D m_mas.node =3D MAS_NONE; =20 /* Check if this is not root and has sufficient data. */ @@ -3018,7 +2870,7 @@ static int mas_spanning_rebalance(struct ma_state *ma= s, unlikely(mast->bn->b_end <=3D mt_min_slots[mast->bn->type])) mast_spanning_rebalance(mast); =20 - mast->orig_l->depth =3D 0; + l_mas.depth =3D 0; =20 /* * Each level of the tree is examined and balanced, pushing data to the l= eft or @@ -3029,7 +2881,7 @@ static int mas_spanning_rebalance(struct ma_state *ma= s, * original tree and the partially new tree. To remedy the parent pointe= rs in * the old tree, the new data is swapped into the active tree and a walk = down * the tree is performed and the parent pointers are updated. - * See mas_descend_adopt() for more information.. + * See mas_topiary_replace() for more information. */ while (count--) { mast->bn->b_end--; @@ -3046,13 +2898,13 @@ static int mas_spanning_rebalance(struct ma_state *= mas, */ memset(mast->bn, 0, sizeof(struct maple_big_node)); mast->bn->type =3D mte_node_type(left); - mast->orig_l->depth++; + l_mas.depth++; =20 /* Root already stored in l->node. */ if (mas_is_root_limits(mast->l)) goto new_root; =20 - mast_ascend_free(mast); + mast_ascend(mast); mast_combine_cp_left(mast); l_mas.offset =3D mast->bn->b_end; mab_set_b_end(mast->bn, &l_mas, left); @@ -3061,7 +2913,6 @@ static int mas_spanning_rebalance(struct ma_state *ma= s, =20 /* Copy anything necessary out of the right node. */ mast_combine_cp_right(mast); - mast_topiary(mast); mast->orig_l->last =3D mast->orig_l->max; =20 if (mast_sufficient(mast)) @@ -3083,7 +2934,7 @@ static int mas_spanning_rebalance(struct ma_state *ma= s, =20 l_mas.node =3D mt_mk_node(ma_mnode_ptr(mas_pop_node(mas)), mte_node_type(mast->orig_l->node)); - mast->orig_l->depth++; + l_mas.depth++; mab_mas_cp(mast->bn, 0, mt_slots[mast->bn->type] - 1, &l_mas, true); mas_set_parent(mas, left, l_mas.node, slot); if (middle) @@ -3094,23 +2945,20 @@ static int mas_spanning_rebalance(struct ma_state *= mas, =20 if (mas_is_root_limits(mast->l)) { new_root: - mast_new_root(mast, mas); + mas_mn(mast->l)->parent =3D ma_parent_ptr(mas_tree_parent(mas)); + while (!mte_is_root(mast->orig_l->node)) + mast_ascend(mast); } else { mas_mn(&l_mas)->parent =3D mas_mn(mast->orig_l)->parent; } =20 - if (!mte_dead_node(mast->orig_l->node)) - mat_add(&free, mast->orig_l->node); - - mas->depth =3D mast->orig_l->depth; - *mast->orig_l =3D l_mas; - mte_set_node_dead(mas->node); - - /* Set up mas for insertion. */ - mast->orig_l->depth =3D mas->depth; - mast->orig_l->alloc =3D mas->alloc; - *mas =3D *mast->orig_l; - mas_wmb_replace(mas, &free, &destroy); + old_enode =3D mast->orig_l->node; + mas->depth =3D l_mas.depth; + mas->node =3D l_mas.node; + mas->min =3D l_mas.min; + mas->max =3D l_mas.max; + mas->offset =3D l_mas.offset; + mas_wmb_replace(mas, old_enode); mtree_range_walk(mas); return mast->bn->b_end; } @@ -3341,7 +3189,6 @@ static inline void mast_fill_bnode(struct maple_subtr= ee_state *mast, unsigned char skip) { bool cp =3D true; - struct maple_enode *old =3D mas->node; unsigned char split; =20 memset(mast->bn->gap, 0, sizeof(unsigned long) * ARRAY_SIZE(mast->bn->gap= )); @@ -3353,7 +3200,6 @@ static inline void mast_fill_bnode(struct maple_subtr= ee_state *mast, cp =3D false; } else { mas_ascend(mas); - mat_add(mast->free, old); mas->offset =3D mte_parent_slot(mas->node); } =20 @@ -3457,13 +3303,11 @@ static inline bool mas_push_data(struct ma_state *m= as, int height, split =3D mt_slots[mast->bn->type] - 2; if (left) { /* Switch mas to prev node */ - mat_add(mast->free, mas->node); *mas =3D tmp_mas; /* Start using mast->l for the left side. */ tmp_mas.node =3D mast->l->node; *mast->l =3D tmp_mas; } else { - mat_add(mast->free, tmp_mas.node); tmp_mas.node =3D mast->r->node; *mast->r =3D tmp_mas; split =3D slot_total - split; @@ -3490,6 +3334,7 @@ static int mas_split(struct ma_state *mas, struct map= le_big_node *b_node) struct maple_subtree_state mast; int height =3D 0; unsigned char mid_split, split =3D 0; + struct maple_enode *old; =20 /* * Splitting is handled differently from any other B-tree; the Maple @@ -3512,7 +3357,6 @@ static int mas_split(struct ma_state *mas, struct map= le_big_node *b_node) MA_STATE(r_mas, mas->tree, mas->index, mas->last); MA_STATE(prev_l_mas, mas->tree, mas->index, mas->last); MA_STATE(prev_r_mas, mas->tree, mas->index, mas->last); - MA_TOPIARY(mat, mas->tree); =20 trace_ma_op(__func__, mas); mas->depth =3D mas_mt_height(mas); @@ -3525,7 +3369,6 @@ static int mas_split(struct ma_state *mas, struct map= le_big_node *b_node) mast.r =3D &r_mas; mast.orig_l =3D &prev_l_mas; mast.orig_r =3D &prev_r_mas; - mast.free =3D &mat; mast.bn =3D b_node; =20 while (height++ <=3D mas->depth) { @@ -3565,9 +3408,9 @@ static int mas_split(struct ma_state *mas, struct map= le_big_node *b_node) } =20 /* Set the original node as dead */ - mat_add(mast.free, mas->node); + old =3D mas->node; mas->node =3D l_mas.node; - mas_wmb_replace(mas, mast.free, NULL); + mas_wmb_replace(mas, old); mtree_range_walk(mas); return 1; } @@ -3903,6 +3746,7 @@ static inline void *mtree_lookup_walk(struct ma_state= *mas) return NULL; } =20 +static void mte_destroy_walk(struct maple_enode *, struct maple_tree *); /* * mas_new_root() - Create a new root node that only contains the entry pa= ssed * in. @@ -3969,7 +3813,6 @@ static inline int mas_wr_spanning_store(struct ma_wr_= state *wr_mas) /* Left and Right side of spanning store */ MA_STATE(l_mas, NULL, 0, 0); MA_STATE(r_mas, NULL, 0, 0); - MA_WR_STATE(r_wr_mas, &r_mas, wr_mas->entry); MA_WR_STATE(l_wr_mas, &l_mas, wr_mas->entry); =20 --=20 2.39.2