From af2bfb0454c5609a02850605ac9891103f8e9e3b Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Thu, 2 Jul 2020 21:03:51 -0400 Subject: [PATCH] maple_tree: wip, fix splitting into 3, fix range of combine_separate, fix test for gap_combining. Splitting into 3 was not functioning due to an error in setting the parent and the split calc. combine_separate was not copying the contents of the mas state over to orig_l_mas which became a problem with the limit checking the end of data. gap_combining tests were rendered broken due to splitting changes with a NULL ending. Signed-off-by: Liam R. Howlett --- lib/maple_tree.c | 61 +++++++++++++++++++++++++++---------------- lib/test_maple_tree.c | 31 ++++++++++++---------- 2 files changed, 56 insertions(+), 36 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 962058aeffad..1ee6dc351965 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -828,6 +828,8 @@ static inline void mas_ascend(struct ma_state *mas) if (_ma_is_root(a_node)) goto no_parent; + printk("ascend: Starting at %p\n", a_node); + p_enode = mt_mk_node(mte_parent(mas->node), mas_parent_enum(mas, mas->node)); @@ -1559,26 +1561,36 @@ static inline void mab_shift_right(struct maple_big_node *b_node, } while (b_end--); } +static inline bool mab_middle_node(struct maple_big_node *b_node, int size, + unsigned char slot_cnt) +{ + int split = (size - 1) / 2; // Assume equal split. + + if (!b_node->slot[split] && (size >= (2 * slot_cnt - 1))) + return true; + return false; +} static inline int mab_calc_split(struct maple_big_node *b_node, int size, unsigned char slot_cnt, unsigned long min) { int split = (size - 1) / 2; // Assume equal split. + printk("orig split %u\n", split); - if (size > 2* slot_cnt) { + 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 + */ + while (((b_node->pivot[split] - min) < slot_cnt - 1) && + (split < slot_cnt)) + split++; } - //printk("Guessing leaf split of %u (size is %d)\n", split, size); - /* Avoid ending a node in NULL and avoid having a range less than the - * slot count - */ - while (((b_node->pivot[split] - min) < slot_cnt) && - split < slot_cnt) { - //printk("Skipping ahead due to min span\n"); - split++; - } - + printk("adjusted split %u\n", split); if (!b_node->slot[split]) { + printk("%u is null\n", split); if (split < slot_cnt - 1) split++; else @@ -1855,28 +1867,30 @@ static inline int mas_combine_separate(struct ma_state *mas, r = mt_mk_node(ma_mnode_ptr(mas_next_alloc(mas)), mte_node_type(orig_l_mas->node)); } - if (b_end > slot_cnt*2) + if (mab_middle_node(b_node, b_end, slot_cnt)) m = mt_mk_node(ma_mnode_ptr(mas_next_alloc(mas)), mte_node_type(orig_l_mas->node)); printk("Splitting %u at %u\n", b_end, split); /* Set parents from previous run */ if (l_mas.node) { - printk("Set parent of %p to either %p or %p\n", mas_mn(&l_mas), - l, r); - printk("child %u split %u\n", child, split); if (child <= split) mte_set_parent(l_mas.node, l, child); else mte_set_parent(l_mas.node, r, child - split); + printk("Set parent of %p to %p\n", mas_mn(&l_mas), + mte_parent(l_mas.node)); + printk("child %u split %u\n", child, split); } if (m_mas.node) { - child *= 2; + child++; if (child <= split) mte_set_parent(m_mas.node, l, child); else mte_set_parent(m_mas.node, r, child - split); - child++; + printk("Set parent of m %p to %p\n", mas_mn(&m_mas), + mte_parent(m_mas.node)); + printk("child %u split %u\n", child, split); } if (r_mas.node) { child++; @@ -1884,6 +1898,9 @@ static inline int mas_combine_separate(struct ma_state *mas, mte_set_parent(r_mas.node, l, child); else mte_set_parent(r_mas.node, r, child - split); + printk("Set parent of r %p to %p\n", mas_mn(&r_mas), + mte_parent(r_mas.node)); + printk("child %u split %u\n", child, split); } /* Copy data from b_node to new nodes */ @@ -1923,7 +1940,7 @@ static inline int mas_combine_separate(struct ma_state *mas, mas_mn(&l_mas)->parent = ma_parent_ptr( ((unsigned long)mas->tree | MA_ROOT_PARENT)); mas->depth = orig_l_mas->depth; - orig_l_mas->node = l_mas.node; + mas_dup_state(orig_l_mas, &l_mas); return 0; } @@ -2021,6 +2038,7 @@ static inline int mas_combine_separate(struct ma_state *mas, // copy in prev. mas_mab_cp(orig_l_mas, 0, end, b_node, 0); b_end += end + 1; + child += end + 1; if (!count) count++; } @@ -2068,6 +2086,7 @@ static inline int mas_combine_separate(struct ma_state *mas, (mt_is_alloc(mas->tree) ? true : false)); // copy in prev. mas_mab_cp(orig_l_mas, 0, end, b_node, 0); + child += end + 1; b_end += end + 1; printk("b_end is %u\n", b_end); } @@ -2101,7 +2120,7 @@ static inline int mas_combine_separate(struct ma_state *mas, mas_mn(&l_mas)->parent = mas_mn(orig_l_mas)->parent; } - orig_l_mas->node = l_mas.node; + mas_dup_state(orig_l_mas, &l_mas); mas->depth = orig_l_mas->depth; return b_end; @@ -2818,7 +2837,6 @@ static inline int mas_spanning_store(struct ma_state *mas, void *entry) mas_set_slot(&r_mas, 0); __mas_walk(&r_mas, &range_min, &range_max); r_mas.last = r_mas.index = mas->last; - mt_dump(mas->tree); // Set up left side. mas_set_slot(&l_mas, 0); @@ -2873,7 +2891,7 @@ static inline int mas_spanning_store(struct ma_state *mas, void *entry) if (mte_is_leaf(mas->node)) return 1; - //mt_dump(mas->tree); + mt_dump(mas->tree); mas_descend_adopt(mas); @@ -2942,7 +2960,6 @@ static inline void *_mas_store(struct ma_state *mas, void *entry, bool overwrite /* Expand store of NULL, if necessary */ if (!entry) { - mt_dump(mas->tree); mas_extend_null(mas, mas); slot = mas_get_slot(mas); printk("store is now %lu-%lu at slot %u\n", mas->index, diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c index 92011b3fe462..bf6564d0d3e5 100644 --- a/lib/test_maple_tree.c +++ b/lib/test_maple_tree.c @@ -29686,7 +29686,6 @@ ERASE, 140612699410432, 140612707799039, void *ptr = NULL; MA_STATE(mas, mt, 0, 0); -// goto skip; mt_set_non_kernel(3); check_erase2_testset(mt, set, ARRAY_SIZE(set)); mtree_destroy(mt); @@ -29775,7 +29774,6 @@ ERASE, 140612699410432, 140612707799039, mas_get_unmapped_area_rev(&mas, 0, 140373518663680, 4096); rcu_read_unlock(); mtree_destroy(mt); -//skip: mtree_init(mt, MAPLE_ALLOC_RANGE); check_erase2_testset(mt, set14, ARRAY_SIZE(set14)); rcu_barrier(); @@ -30369,7 +30367,7 @@ static noinline void check_ranges(struct maple_tree *mt) mtree_destroy(mt); check_seq(mt, 50, false); - return;// FIXME + return; mt_set_non_kernel(4); check_store_range(mt, 5, 47, xa_mk_value(47), 0); mtree_destroy(mt); @@ -30574,7 +30572,7 @@ static noinline void check_gap_combining(struct maple_tree *mt) { struct maple_enode *mn1, *mn2; void *entry; - unsigned long index = 86; + unsigned long index = 82; MA_STATE(mas, mt, index, index); @@ -30582,26 +30580,29 @@ static noinline void check_gap_combining(struct maple_tree *mt) check_seq(mt, 100, false); // create 100 singletons. mt_set_non_kernel(1); - mtree_test_erase(mt, 88); - check_load(mt, 88, NULL); - mtree_test_erase(mt, 87); - check_load(mt, 87, NULL); + mtree_test_erase(mt, 83); + check_load(mt, 83, NULL); + mtree_test_erase(mt, 84); + check_load(mt, 84, NULL); rcu_read_lock(); entry = mas_find(&mas, ULONG_MAX); MT_BUG_ON(mt, entry != xa_mk_value(index)); mn1 = mas.node; + printk("node %p\n", mn1); + mas_next(&mas, ULONG_MAX); entry = mas_next(&mas, ULONG_MAX); - MT_BUG_ON(mt, entry != xa_mk_value(index + 3)); + MT_BUG_ON(mt, entry != xa_mk_value(index + 4)); mn2 = mas.node; MT_BUG_ON(mt, mn1 == mn2); // test the test. - // At this point, there is a gap of 2 in either 1 or 2 nodes. Find a - // gap of size 2 from 100 down to 50. + /* At this point, there is a gap of 2 at index + 1 between 50-100. + * Search for the gap. + */ mt_set_non_kernel(1); mas_reset(&mas); MT_BUG_ON(mt, mas_get_unmapped_area_rev(&mas, 50, 100, 2)); - MT_BUG_ON(mt, mas.index != 87); + MT_BUG_ON(mt, mas.index != index + 1); rcu_read_unlock(); mtree_test_erase(mt, 38); @@ -30620,11 +30621,13 @@ static noinline void check_gap_combining(struct maple_tree *mt) mn1 = mas.node; entry = mas_next(&mas, ULONG_MAX); MT_BUG_ON(mt, entry != xa_mk_value(index + 4)); + mas_next(&mas, ULONG_MAX); // go to the next node. mn2 = mas.node; MT_BUG_ON(mt, mn1 == mn2); - // At this point, there is a gap of 2 in either 1 or 2 nodes. Find a - // gap of size 2 from 100 down to 50. + /* At this point, there is a gap of 3 at 38. Find it by searching 20 - + * 50 for size 3. + */ mas_reset(&mas); MT_BUG_ON(mt, mas_get_unmapped_area_rev(&mas, 20, 50, 3)); MT_BUG_ON(mt, mas.index != 38); -- 2.50.1