[<prev] [next>] [<thread-prev] [day] [month] [year] [list]
Message-ID: <20250407184102.2155415-5-sidhartha.kumar@oracle.com>
Date: Mon, 7 Apr 2025 18:41:00 +0000
From: Sidhartha Kumar <sidhartha.kumar@...cle.com>
To: linux-kernel@...r.kernel.org, maple-tree@...ts.infradead.org
Cc: linux-mm@...ck.org, akpm@...ux-foundation.org, liam.howlett@...cle.com,
willy@...radead.org, Sidhartha Kumar <sidhartha.kumar@...cle.com>,
Wei Yang <richard.weiyang@...il.com>,
"Liam R . Howlett" <Liam.Howlett@...cle.com>
Subject: [PATCH v4 4/6] maple_tree: break on convergence in mas_spanning_rebalance()
This allows support for using the vacant height to calculate the worst
case number of nodes needed for wr_rebalance operation.
mas_spanning_rebalance() was seen to perform unnecessary node allocations.
We can reduce allocations by breaking early during the rebalancing loop
once we realize that we have ascended to a common ancestor.
Suggested-by: Liam Howlett <liam.howlett@...cle.com>
Reviewed-by: Wei Yang <richard.weiyang@...il.com>
Reviewed-by: Liam R. Howlett <Liam.Howlett@...cle.com>
Signed-off-by: Sidhartha Kumar <sidhartha.kumar@...cle.com>
---
lib/maple_tree.c | 16 +++++++++++++---
1 file changed, 13 insertions(+), 3 deletions(-)
diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index 203a1a529884..acecd4e8a6a0 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -2895,11 +2895,21 @@ static void mas_spanning_rebalance(struct ma_state *mas,
mast_combine_cp_right(mast);
mast->orig_l->last = mast->orig_l->max;
- if (mast_sufficient(mast))
- continue;
+ if (mast_sufficient(mast)) {
+ if (mast_overflow(mast))
+ continue;
+
+ if (mast->orig_l->node == mast->orig_r->node) {
+ /*
+ * The data in b_node should be stored in one
+ * node and in the tree
+ */
+ slot = mast->l->offset;
+ break;
+ }
- if (mast_overflow(mast))
continue;
+ }
/* May be a new root stored in mast->bn */
if (mas_is_root_limits(mast->orig_l))
--
2.43.0
Powered by blists - more mailing lists