From 6165068a3ae432095f308e66f7c2f220162b3547 Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Thu, 2 Jul 2020 21:34:43 -0400 Subject: [PATCH] maple_tree: wip, fix underrun on root expand when range starts at zero but ends elsewhere Signed-off-by: Liam R. Howlett --- lib/maple_tree.c | 25 ++++++++++++------------- lib/test_maple_tree.c | 1 - 2 files changed, 12 insertions(+), 14 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 1ee6dc351965..a8ae9c4374df 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -1571,24 +1571,23 @@ static inline bool mab_middle_node(struct maple_big_node *b_node, int size, return false; } static inline int mab_calc_split(struct maple_big_node *b_node, int size, - unsigned char slot_cnt, unsigned long min) + unsigned char slot_cnt, unsigned long min, + enum maple_type type) { int split = (size - 1) / 2; // Assume equal split. - printk("orig split %u\n", split); if (mab_middle_node(b_node, size, slot_cnt)) { split = (size + 1) / 3; - printk("3 split %u\n", split); } else { - /* Avoid ending a node in NULL and avoid having a range less - * than the slot count - */ + /* Avoid having a range less than the slot count unless it + * causes one node to be deficient. */ while (((b_node->pivot[split] - min) < slot_cnt - 1) && - (split < slot_cnt)) + (split < slot_cnt) && + (size - split > mt_min_slots[type])) split++; } - printk("adjusted split %u\n", split); + /* Avoid ending a node on a NULL entry */ if (!b_node->slot[split]) { printk("%u is null\n", split); if (split < slot_cnt - 1) @@ -1596,7 +1595,7 @@ static inline int mab_calc_split(struct maple_big_node *b_node, int size, else split--; } - //printk("Setting split (leaf split) to %u\n", split); + return split; } @@ -1863,7 +1862,8 @@ static inline int mas_combine_separate(struct ma_state *mas, split = b_end; } else { split = mab_calc_split(b_node, b_end, slot_cnt, - orig_l_mas->min); + orig_l_mas->min, + mte_node_type(orig_l_mas->node)); r = mt_mk_node(ma_mnode_ptr(mas_next_alloc(mas)), mte_node_type(orig_l_mas->node)); } @@ -2299,7 +2299,7 @@ static inline int mas_split(struct ma_state *mas, if (mte_is_leaf(mas->node)) { printk("Splitting leaf %p\n", mas_mn(mas)); split = mab_calc_split(b_node, new_end, slot_cnt, - mas->min); + mas->min, type); printk("Splitting at %u\n", split); if (split < slot_cnt) i = mab_mas_cp(b_node, 0, split, &l_mas, 0); @@ -2480,12 +2480,11 @@ static inline int mas_root_expand(struct ma_state *mas, void *entry) if (contents) mte_set_rcu_slot(mas->node, slot++, contents); - if (!mas->index) + if (!mas->index && slot) slot--; else if (mas->index > 1) mte_set_pivot(mas->node, slot++, mas->index - 1); - mte_set_rcu_slot(mas->node, slot, entry); mte_set_pivot(mas->node, slot++, mas->last); diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c index bf6564d0d3e5..c6adf2419a15 100644 --- a/lib/test_maple_tree.c +++ b/lib/test_maple_tree.c @@ -30367,7 +30367,6 @@ static noinline void check_ranges(struct maple_tree *mt) mtree_destroy(mt); check_seq(mt, 50, false); - return; mt_set_non_kernel(4); check_store_range(mt, 5, 47, xa_mk_value(47), 0); mtree_destroy(mt); -- 2.50.1