From 95cf6f54e05f7ff386e14816d413339bd0301975 Mon Sep 17 00:00:00 2001 From: Sidhartha Kumar Date: Mon, 7 Apr 2025 18:41:00 +0000 Subject: [PATCH] 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 Reviewed-by: Wei Yang Reviewed-by: Liam R. Howlett Signed-off-by: Sidhartha Kumar --- 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 066edcab96d7..0cacb8f07550 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -2899,11 +2899,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.49.0