diff options
| author | Sidhartha Kumar <sidhartha.kumar@oracle.com> | 2025-04-10 22:14:44 +0300 |
|---|---|---|
| committer | Andrew Morton <akpm@linux-foundation.org> | 2025-05-12 03:48:28 +0300 |
| commit | 300a5b4ffedf826998ed1f1b5d107e9fb0ef7579 (patch) | |
| tree | d5b5aff6fc1d63505f2a558b70e7d2e47944255a /lib | |
| parent | ad88fc17d2dafe45e40de2af80207f4b2e3b1f71 (diff) | |
| download | linux-300a5b4ffedf826998ed1f1b5d107e9fb0ef7579.tar.xz | |
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.
Link: https://lkml.kernel.org/r/20250410191446.2474640-5-sidhartha.kumar@oracle.com
Signed-off-by: Sidhartha Kumar <sidhartha.kumar@oracle.com>
Suggested-by: Liam Howlett <liam.howlett@oracle.com>
Reviewed-by: Wei Yang <richard.weiyang@gmail.com>
Reviewed-by: Liam R. Howlett <Liam.Howlett@Oracle.com>
Cc: Matthew Wilcox (Oracle) <willy@infradead.org>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Diffstat (limited to 'lib')
| -rw-r--r-- | lib/maple_tree.c | 16 |
1 files changed, 13 insertions, 3 deletions
diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 3f794ef072f4..5610b3742a79 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -2893,11 +2893,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)) |