From patchwork Fri Feb 21 16:36:09 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Sidhartha Kumar X-Patchwork-Id: 13985958 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by smtp.lore.kernel.org (Postfix) with ESMTP id 4FF33C021B6 for ; Fri, 21 Feb 2025 16:36:34 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 09AE128001D; Fri, 21 Feb 2025 11:36:32 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id F159928001B; Fri, 21 Feb 2025 11:36:31 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id D6AAF28001D; Fri, 21 Feb 2025 11:36:31 -0500 (EST) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0013.hostedemail.com [216.40.44.13]) by kanga.kvack.org (Postfix) with ESMTP id AC7DF28001E for ; Fri, 21 Feb 2025 11:36:31 -0500 (EST) Received: from smtpin25.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay07.hostedemail.com (Postfix) with ESMTP id 3582916190D for ; Fri, 21 Feb 2025 16:36:31 +0000 (UTC) X-FDA: 83144504982.25.B6F7271 Received: from mx0b-00069f02.pphosted.com (mx0b-00069f02.pphosted.com [205.220.177.32]) by imf24.hostedemail.com (Postfix) with ESMTP id 20491180021 for ; Fri, 21 Feb 2025 16:36:28 +0000 (UTC) Authentication-Results: imf24.hostedemail.com; dkim=pass header.d=oracle.com header.s=corp-2023-11-20 header.b=eAbp4WFU; spf=pass (imf24.hostedemail.com: domain of sidhartha.kumar@oracle.com designates 205.220.177.32 as permitted sender) smtp.mailfrom=sidhartha.kumar@oracle.com; dmarc=pass (policy=reject) header.from=oracle.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1740155789; h=from:from:sender:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:mime-version: content-type:content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references:dkim-signature; bh=m5qZMtJyHxKtlfah8mpfmJ81/MTbcNVeb2GVVQ6Wzio=; b=hbHQ62aME+WM3MYE4tcYTNWCjhClqlK2NU2Aak70Z2lAEFfxNZWHraJ+AVkgoQVD+REgxa uIGnlQxNG0S8emqRvciDqpHRJkd39QgajMEqXP7cSknSQlRq0i72YM2p8TgEseXyLXrdfw iTRXqt7CCuxDAi0GClltuHt04AuXm0I= ARC-Authentication-Results: i=1; imf24.hostedemail.com; dkim=pass header.d=oracle.com header.s=corp-2023-11-20 header.b=eAbp4WFU; spf=pass (imf24.hostedemail.com: domain of sidhartha.kumar@oracle.com designates 205.220.177.32 as permitted sender) smtp.mailfrom=sidhartha.kumar@oracle.com; dmarc=pass (policy=reject) header.from=oracle.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1740155789; a=rsa-sha256; cv=none; b=s5LY7k/kLrFYWGZAodHgelB9JyjxnXIyZNYjgTuV1085fx/twykXGItG0tRoEYQ9ByzPfR gxe8hfdtocSoM9EJfiMYg+QVrIqQt7an/VxJOTcrrb9YOmUNpZfgPNgVUYSmlQXpmyw3EP X1JgKN4TYmB4v1AaJtaH24kvhHvGEKw= Received: from pps.filterd (m0333520.ppops.net [127.0.0.1]) by mx0b-00069f02.pphosted.com (8.18.1.2/8.18.1.2) with ESMTP id 51L8fcXp002374; Fri, 21 Feb 2025 16:36:27 GMT DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=oracle.com; h=cc :content-transfer-encoding:date:from:in-reply-to:message-id :mime-version:references:subject:to; s=corp-2023-11-20; bh=m5qZM tJyHxKtlfah8mpfmJ81/MTbcNVeb2GVVQ6Wzio=; b=eAbp4WFUVNS4ckfmwdP25 L+81aVdS5CGUwwQqIh58kVtfnD9cs0ALZogF+oW/zWrVKkkYBqTny2HvwErWZJGl /FIhRY0dnqiNRCAO1I3zag+H1EHw8BZd9c+Ab/zI/VwGvTodNN1NEJbYUPaJ5hUe vhiiHtQlVzpxGVtZ/CDPtVVshErMj/Tq0RENcTUViiC3OhMt6KrJvatyFAtRiYYZ LvuOkpY7NH3OgTFE9UnvFeh1Ab4/tFPuBGSl6eZS4siORXUwQldxpIZVHku3QzKm FoVo+fEzdDIDqgrawYrtGPDNbJ8+i6wAu1cMyGF2/iemcYql0FYSPL0k6cTivhox A== Received: from iadpaimrmta03.imrmtpd1.prodappiadaev1.oraclevcn.com (iadpaimrmta03.appoci.oracle.com [130.35.103.27]) by mx0b-00069f02.pphosted.com (PPS) with ESMTPS id 44w00m6r2h-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Fri, 21 Feb 2025 16:36:27 +0000 (GMT) Received: from pps.filterd (iadpaimrmta03.imrmtpd1.prodappiadaev1.oraclevcn.com [127.0.0.1]) by iadpaimrmta03.imrmtpd1.prodappiadaev1.oraclevcn.com (8.18.1.2/8.18.1.2) with ESMTP id 51LFaxtO010538; Fri, 21 Feb 2025 16:36:15 GMT Received: from pps.reinject (localhost [127.0.0.1]) by iadpaimrmta03.imrmtpd1.prodappiadaev1.oraclevcn.com (PPS) with ESMTPS id 44w07gxm8n-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Fri, 21 Feb 2025 16:36:15 +0000 Received: from iadpaimrmta03.imrmtpd1.prodappiadaev1.oraclevcn.com (iadpaimrmta03.imrmtpd1.prodappiadaev1.oraclevcn.com [127.0.0.1]) by pps.reinject (8.17.1.5/8.17.1.5) with ESMTP id 51LGUIXL005786; Fri, 21 Feb 2025 16:36:14 GMT Received: from sidhakum-ubuntu.osdevelopmeniad.oraclevcn.com (sidhakum-ubuntu.allregionaliads.osdevelopmeniad.oraclevcn.com [100.100.250.108]) by iadpaimrmta03.imrmtpd1.prodappiadaev1.oraclevcn.com (PPS) with ESMTP id 44w07gxm69-6; Fri, 21 Feb 2025 16:36:14 +0000 From: Sidhartha Kumar To: linux-kernel@vger.kernel.org, maple-tree@lists.infradead.org Cc: linux-mm@kvack.org, akpm@linux-foundation.org, liam.howlett@oracle.com, richard.weiyang@gmail.com, Sidhartha Kumar Subject: [PATCH v2 5/6] maple_tree: add sufficient height Date: Fri, 21 Feb 2025 16:36:09 +0000 Message-ID: <20250221163610.578409-6-sidhartha.kumar@oracle.com> X-Mailer: git-send-email 2.43.0 In-Reply-To: <20250221163610.578409-1-sidhartha.kumar@oracle.com> References: <20250221163610.578409-1-sidhartha.kumar@oracle.com> MIME-Version: 1.0 X-Proofpoint-Virus-Version: vendor=baseguard engine=ICAP:2.0.293,Aquarius:18.0.1057,Hydra:6.0.680,FMLib:17.12.68.34 definitions=2025-02-21_05,2025-02-20_02,2024-11-22_01 X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 mlxscore=0 adultscore=0 bulkscore=0 mlxlogscore=999 malwarescore=0 suspectscore=0 spamscore=0 phishscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2502100000 definitions=main-2502210118 X-Proofpoint-ORIG-GUID: XYYj4G4kU-p-4171gN7Xba356-yhrB6z X-Proofpoint-GUID: XYYj4G4kU-p-4171gN7Xba356-yhrB6z X-Rspam-User: X-Rspamd-Queue-Id: 20491180021 X-Stat-Signature: trwnbae6xbzzs49da9fp6siyuze4gii1 X-Rspamd-Server: rspam03 X-HE-Tag: 1740155788-382238 X-HE-Meta: U2FsdGVkX18Oq2HpKGm8517RiU9bhGuJUDd1C3Tt3+p7Myin6QiyqHiZBMObXdyWTCV+6H9pharYCTajrXWT1o4x8ip014Exz/dbMDBRgAvhg3wHE03xzv+Pf6Nqb8zQN4tEk55NhIVzETEHVtxZfc+Q0InCYn2v80GxjNKu/p3ZrlAoAXdRL79agkfjAvjcuWLKaNQYBBKu7AE0JxJQRW2WDFbgiAdNBJJ3beQ6dvGO5KU3p9kTgPSRvlFUB6vocqIZKcapp7OpRTF+PTYAvelK3vIcYK1HADPJW1GbHypDaWDA1TNp0TbyWhtp/fag4ONN4INyLlpSj8i0IM4fQa86MjQr1rRQ2RX35h7GwoQKNd1hyh9WpaF771naPHd1HYjVGMI+5hbv5RyyAfpEb8zPeO+Js7U48iCZCWOi2BwTgTvvJgze5jK89NtxXJH1JXszO3TrRNh7oT8UsGArQzi2tiiRo9BZJHWok0JipkW4rIxR2qSjUOLcdKuNOzwuE186QKG4TG9pvUQ9GUIXiimSbwaLRzmgNgLcCcw5SGFpIcJ8+O6K+63Twbo8baSGTyFPGomFU+OBnnfsivEDFCgyl833zjb6HAo9tK7pTRmkkV7dW1v1sO5ukcJBs+jcH4t3wXY0x7gmZ6hFzBXH1//x7YhD++yYLderZj9LwoVmv8yn/jUQnOWmH6UPfW6E3gD9MV9Mi19sxlKBq4slPXXuq1+jJy3dx8bESp8iyDhu07kDOOZEE9hTWRySMtkBVKZprX1Y41tETE2wmFP0PCTYo0DDTz2NchfabFQT/dWuJUm+qSOhxpu9iGquM9+NDh6H50cU1PcMyqDAq/xj9z7DgPYaR8FrEdkTxfUWC/1nlK8CYxeAeRKIB//bwNh3MiC3kzGjFUiWqkNq7gRzYXHAYbItqgHnQInSs/ldDi3TER1JuvOn/P/um9WnaRI/70VXjAyIU7+v6dm1BQM HrhPPgQX XvK9hDP1mvOQ0h/gvzYWw7snmEFkFQNF7jvVmjLRpIqsFKnU8XaJ+/m075mGc1R/dJz+l9zU4mvsPkVNDUCINB2LSDPI8v2bQcsHFZ31vczLxk/t2LWSfYKFZAR+JGuZiaQ2BPD+oVI8yKphvoyjZcHM7p6knF+TFGLWRgeB2Dm2cHJSCEsgVkARjmLD1cqOyaqFnJu9iYk/XAGxSUuekW3gh2/gz5Pjre0sai5dKAJ1+uKOfLH2/IkkI+3ObppfSbtR+fMdeOPvZx5Im48vGHCHx6bRGVIA2ca5Y1GtfCnBX4atN34WfEZy9+5hp4CqWsjxmfH+RARm91dCyVxtl9AzS07F4ZjqjlpCJMyNNAXUsIIE= X-Bogosity: Ham, tests=bogofilter, spamicity=0.000000, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: List-Subscribe: List-Unsubscribe: If a parent node is vacant but holds mt_min_slots + 1 entries, rebalancing with a leaf node could cause this parent node to become insufficient. This will lead to another level of rebalancing in the tree and requires more node allocations. Therefore, we also have to track the level at which there is a node with > mt_min_slots entries. We can use this as the worst case for the spanning and rebalacning stores. Signed-off-by: Sidhartha Kumar --- include/linux/maple_tree.h | 4 +++- lib/maple_tree.c | 17 +++++++++++++++-- tools/testing/radix-tree/maple.c | 28 ++++++++++++++++++++++++++++ 3 files changed, 46 insertions(+), 3 deletions(-) diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h index 7d777aa2d9ed..37dc9525dff6 100644 --- a/include/linux/maple_tree.h +++ b/include/linux/maple_tree.h @@ -464,6 +464,7 @@ struct ma_wr_state { void *entry; /* The entry to write */ void *content; /* The existing entry that is being overwritten */ unsigned char vacant_height; /* Depth of lowest node with free space */ + unsigned char sufficient_height;/* Depth of lowest node with min sufficiency + 1 nodes */ }; #define mas_lock(mas) spin_lock(&((mas)->tree->ma_lock)) @@ -499,7 +500,8 @@ struct ma_wr_state { .mas = ma_state, \ .content = NULL, \ .entry = wr_entry, \ - .vacant_height = 0 \ + .vacant_height = 0, \ + .sufficient_height = 0 \ } #define MA_TOPIARY(name, tree) \ diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 4de257003251..8fdd3f477198 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -3558,6 +3558,13 @@ static bool mas_wr_walk(struct ma_wr_state *wr_mas) if (mas->end < mt_slots[wr_mas->type] - 1) wr_mas->vacant_height = mas->depth + 1; + if (ma_is_root(mas_mn(mas))) { + /* root needs more than 2 entries to be sufficient + 1 */ + if (mas->end > 2) + wr_mas->sufficient_height = 1; + } else if (mas->end > mt_min_slots[wr_mas->type] + 1) + wr_mas->sufficient_height = mas->depth + 1; + mas_wr_walk_traverse(wr_mas); } @@ -4193,13 +4200,19 @@ static inline int mas_prealloc_calc(struct ma_wr_state *wr_mas, void *entry) ret = 0; break; case wr_spanning_store: - ret = height * 3 + 1; + if (wr_mas->sufficient_height < wr_mas->vacant_height) + ret = (height - wr_mas->sufficient_height) * 3 + 1; + else + ret = delta * 3 + 1; break; case wr_split_store: ret = delta * 2 + 1; break; case wr_rebalance: - ret = height * 2 + 1; + if (wr_mas->sufficient_height < wr_mas->vacant_height) + ret = (height - wr_mas->sufficient_height) * 2 + 1; + else + ret = delta * 2 + 1; break; case wr_node_store: ret = mt_in_rcu(mas->tree) ? 1 : 0; diff --git a/tools/testing/radix-tree/maple.c b/tools/testing/radix-tree/maple.c index d22c1008dffe..d40f70671cb8 100644 --- a/tools/testing/radix-tree/maple.c +++ b/tools/testing/radix-tree/maple.c @@ -36334,6 +36334,30 @@ static noinline void __init check_mtree_dup(struct maple_tree *mt) extern void test_kmem_cache_bulk(void); +/* + * Test to check the path of a spanning rebalance which results in + * a collapse where the rebalancing of the child node leads to + * insufficieny in the parent node. + */ +static void check_collapsing_rebalance(struct maple_tree *mt) +{ + int i = 0; + MA_STATE(mas, mt, ULONG_MAX, ULONG_MAX); + + /* create a height 4 tree */ + while (mt_height(mt) < 4) { + mtree_store_range(mt, i, i + 10, xa_mk_value(i), GFP_KERNEL); + i += 9; + } + + /* delete all entries one at a time, starting from the right */ + do { + mas_erase(&mas); + } while (mas_prev(&mas, 0) != NULL); + + mtree_unlock(mt); +} + /* callback function used for check_nomem_writer_race() */ static void writer2(void *maple_tree) { @@ -36500,6 +36524,10 @@ void farmer_tests(void) check_spanning_write(&tree); mtree_destroy(&tree); + mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); + check_collapsing_rebalance(&tree); + mtree_destroy(&tree); + mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); check_null_expand(&tree); mtree_destroy(&tree);