From 55da3553b36af6472dab98c3ac4d8f72dde10fb6 Mon Sep 17 00:00:00 2001 From: Sidhartha Kumar Date: Thu, 28 Aug 2025 19:25:52 +0000 Subject: [PATCH] maple_tree: fix off by one error in mas_destroy_rebalance() Signed-off-by: Sidhartha Kumar --- lib/maple_tree.c | 9 +++++---- tools/testing/radix-tree/maple.c | 16 +++++++++------- 2 files changed, 14 insertions(+), 11 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index c57a4615bdff9..e93551073051a 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -1881,7 +1881,7 @@ static inline int mab_calc_split(struct ma_state *mas, */ if (unlikely((mas->mas_flags & MA_STATE_BULK))) { *mid_split = 0; - split = b_end - mt_min_slots[bn->type]; + split = b_end - mt_min_slots[bn->type] - 1; if (!ma_is_leaf(bn->type)) return split; @@ -3055,11 +3055,12 @@ static inline void mas_destroy_rebalance(struct ma_state *mas, unsigned char end tmp = mas_data_end(&l_mas) - split; memcpy(slots, l_slots + split + 1, sizeof(void *) * tmp); - memcpy(pivs, l_pivs + split + 1, sizeof(unsigned long) * tmp); - pivs[tmp] = l_mas.max; + memcpy(pivs, l_pivs + split + 1, sizeof(unsigned long) * (tmp - 1)); + pivs[tmp - 1] = l_mas.max; memcpy(slots + tmp, ma_slots(node, mt), sizeof(void *) * end); memcpy(pivs + tmp, ma_pivots(node, mt), sizeof(unsigned long) * end); + l_mas.max = l_pivs[split]; mas->min = l_mas.max + 1; old_eparent = mt_mk_node(mte_parent(l_mas.node), @@ -5575,7 +5576,7 @@ void mas_destroy(struct ma_state *mas) mas_start(mas); mtree_range_walk(mas); end = mas->end + 1; - if (end < mt_min_slot_count(mas->node) - 1) + if (mas->end < mt_min_slot_count(mas->node)) mas_destroy_rebalance(mas, end); mas->mas_flags &= ~MA_STATE_REBALANCE; diff --git a/tools/testing/radix-tree/maple.c b/tools/testing/radix-tree/maple.c index 05714c22994ea..cdabfe02de2ae 100644 --- a/tools/testing/radix-tree/maple.c +++ b/tools/testing/radix-tree/maple.c @@ -36468,18 +36468,20 @@ static inline int check_vma_modification(struct maple_tree *mt) */ static inline void check_bulk_rebalance(struct maple_tree *mt) { - MA_STATE(mas, mt, ULONG_MAX, ULONG_MAX); + MA_STATE(mas, mt, 0, 0); int max = 10; + int i = 0; - build_full_tree(mt, 0, 2); - - /* erase every entry in the tree */ - do { + while(mt_height(mt) < 3) { /* set up bulk store mode */ mas_expected_entries(&mas, max); - mas_erase(&mas); + mas_set_range(&mas, i, i + 9); + mas_store_gfp(&mas, xa_mk_value(0xA), GFP_KERNEL); MT_BUG_ON(mt, mas.store_type == wr_rebalance); - } while (mas_prev(&mas, 0) != NULL); + mas_destroy(&mas); + mt_validate(mt); + i += 10; + } mas_destroy(&mas); } -- 2.51.0