From 2eef2b1b706a7c76163f5d592aea9ca5404ff7db Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Thu, 3 Sep 2020 21:41:44 -0400 Subject: [PATCH] maple_tree: Lower efficiency of node use. Split when there is a slot left to avoid overflow situation on a triple split. This is to avoid reworking the node estimate calculations prior to actually removing the node estimate calculations in favour of assuming no failures. Signed-off-by: Liam R. Howlett --- lib/maple_tree.c | 35 +++++++++++++------------- lib/test_maple_tree.c | 57 +++++++++++++++++++++++++++---------------- 2 files changed, 53 insertions(+), 39 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index ddf3ab60405b..205afdaee3d3 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -93,7 +93,7 @@ unsigned char mt_min_slots[] = { [maple_range_32] = MAPLE_RANGE32_SLOTS / 2, [maple_range_64] = (MAPLE_RANGE64_SLOTS / 2) - 2, #if defined(NODE256) - [maple_arange_64] = (MAPLE_ARANGE64_SLOTS / 2) - 1, + [maple_arange_64] = (MAPLE_ARANGE64_SLOTS / 2) - 2, #else [maple_arange_64] = (MAPLE_ARANGE64_SLOTS / 2), #endif @@ -915,7 +915,7 @@ no_parent: if (!max || min == ULONG_MAX) { if (mas->node == a_enode) { printk("Failed on node %p (%p)\n", mas_mn(mas), a_enode); - //FIXME: Restart and retry? + //FIXME: Restart and retry if the lock is held. MT_BUG_ON(mas->tree, mas->node == a_enode); } mas->node = a_enode; @@ -1593,16 +1593,13 @@ static inline void mas_mab_cp(struct ma_state *mas, unsigned char mas_start, if (!mte_is_leaf(mas->node) && mt_is_alloc(mas->tree)) b_node->gap[j] = mte_get_gap(mas->node, i); - if (i < mt_pivot_count(mas->node)) { + if (i < mt_pivot_count(mas->node)) b_node->pivot[j] = mas_get_safe_pivot(mas, i); - } else { + else b_node->pivot[j] = mas->max; - j++; - break; - } - if ((j && !b_node->pivot[j]) || - (mas->max == b_node->pivot[j])) { // end of node. + if ((mas->max == b_node->pivot[j]) || + (j && !b_node->pivot[j])) { // end of node. j++; break; } @@ -1629,6 +1626,7 @@ static inline void mab_mas_cp(struct maple_big_node *b_node, mas->max = b_node->pivot[i]; mte_set_rcu_slot(mas->node, j, b_node->slot[i]); + if (j < mt_pivot_count(mas->node)) mte_set_pivot(mas->node, j, b_node->pivot[i]); @@ -1800,10 +1798,11 @@ static inline bool mas_next_sibling(struct ma_state *mas) mas_ascend(&parent); p_end = mas_data_end(&parent); + if (p_end == p_slot) return false; - mas_ascend(mas); + mas_dup_state(mas, &parent); mas_set_offset(mas, p_slot + 1); mas_descend(mas); return true; @@ -2503,7 +2502,7 @@ static inline bool mas_split_final_node(struct maple_subtree_state *mast, return _mas_split_final_node(mast, mas, height); } -static inline void mast_split_fill_bnode(struct maple_subtree_state *mast, +static inline void mast_fill_bnode(struct maple_subtree_state *mast, struct ma_state *mas, unsigned char skip) { @@ -2528,6 +2527,9 @@ static inline void mast_split_fill_bnode(struct maple_subtree_state *mast, mab_set_b_end(mast->bn, mast->l, mast->l->node); mas_set_offset(mast->r, mast->bn->b_end); mab_set_b_end(mast->bn, mast->r, mast->r->node); + if (mast->bn->pivot[mast->bn->b_end - 1] == mas->max) + cp = false; + if (cp) mas_mab_cp(mas, split + skip, mt_slot_count(mas->node) - 1, mast->bn, mast->bn->b_end); @@ -2616,7 +2618,7 @@ static inline bool mas_push_data(struct ma_state *mas, int height, mas_set_offset(mast->orig_l, mas_offset(mast->orig_l) + end + 1); mast_split_data(mast, mas, split); - mast_split_fill_bnode(mast, mas, 2); + mast_fill_bnode(mast, mas, 2); _mas_split_final_node(mast, mas, height + 1); return true; } @@ -2679,7 +2681,7 @@ static inline int mas_split(struct ma_state *mas, mast_split_data(&mast, mas, split); // Usually correct, mab_mas_cp in the above call overwrites r->max. mast.r->max = mas->max; - mast_split_fill_bnode(&mast, mas, 1); + mast_fill_bnode(&mast, mas, 1); mas_dup_state(&prev_l_mas, mast.l); mas_dup_state(&prev_r_mas, mast.r); } @@ -2956,7 +2958,7 @@ static inline bool mas_wr_walk(struct ma_state *mas, unsigned long *range_min, if (end <= mt_min_slots[type]) mas_cnt_empty(mas); - else if (end >= mt_slots[type] - 1) + else if (end >= mt_slots[type] - 2) mas_cnt_full(mas); else mas->full_cnt = 0; @@ -3082,10 +3084,7 @@ static inline int mas_spanning_store(struct ma_state *mas, void *entry) trace_mas_spanning_store(mas); // Leaf nodes - if (mas->full_cnt > 0) - node_cnt = mas->full_cnt; // For split upwards. - else - node_cnt = mas_cnt_positive(mas); // For rebalance upwards. + node_cnt = mas_cnt_positive(mas); // For rebalance upwards. /* Node rebalancing may occur due to this store, so there may be two new * entries per level plus a new root. */ diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c index 0170ce4d5178..1a1761f6053e 100644 --- a/lib/test_maple_tree.c +++ b/lib/test_maple_tree.c @@ -1051,7 +1051,7 @@ static noinline void check_erase2_testset(struct maple_tree *mt, check = 0; addr = 0; mt_for_each(mt, foo, addr, ULONG_MAX) { -#if check_erase2_debug > 1 +#if check_erase2_debug > 2 pr_err("mt: %lu -> %p\n", addr+1, foo); #endif check++; @@ -1059,7 +1059,7 @@ static noinline void check_erase2_testset(struct maple_tree *mt, break; } -#if check_erase2_debug > 1 +#if check_erase2_debug > 2 pr_err("mt_for_each %d and cnt %d\n", check, entry_cnt); #endif @@ -1081,7 +1081,7 @@ static noinline void check_erase2_testset(struct maple_tree *mt, addr = mas.index; continue; } -#if check_erase2_debug > 1 +#if check_erase2_debug > 2 pr_err("mas: %lu -> %p\n", mas.index, foo); #endif check++; @@ -1089,7 +1089,7 @@ static noinline void check_erase2_testset(struct maple_tree *mt, break; } rcu_read_unlock(); -#if check_erase2_debug > 1 +#if check_erase2_debug > 2 pr_err("mas_for_each %d and cnt %d\n", check, entry_cnt); mt_validate(mt); #endif @@ -4061,7 +4061,7 @@ STORE, 140060022747136, 140060022755327, STORE, 140060022755328, 140060022759423, STORE, 140727079788544, 140727079792639, STORE, 140727079776256, 140727079788543, -STORE, 47572772409344, 47572772417535, +STORE, 47572772409344, 47572772417535, // this one caused issues when lowering the efficiency STORE, 47572772417536, 47572772425727, STORE, 47572772425728, 47572772532223, STORE, 47572772442112, 47572772532223, @@ -31181,6 +31181,7 @@ SNULL, 94376135094272, 94377208836095, mt_set_non_kernel(3); check_erase2_testset(mt, set, ARRAY_SIZE(set)); + mt_set_non_kernel(0); mtree_destroy(mt); mtree_init(mt, MAPLE_ALLOC_RANGE); @@ -31192,6 +31193,7 @@ SNULL, 94376135094272, 94377208836095, mt_set_non_kernel(2); mtree_init(mt, 0); check_erase2_testset(mt, set3, ARRAY_SIZE(set3)); + mt_set_non_kernel(0); mtree_destroy(mt); mtree_init(mt, 0); @@ -31209,6 +31211,7 @@ SNULL, 94376135094272, 94377208836095, mt_set_non_kernel(100); check_erase2_testset(mt, set5, ARRAY_SIZE(set5)); rcu_barrier(); + mt_set_non_kernel(0); mtree_destroy(mt); mtree_init(mt, MAPLE_ALLOC_RANGE); @@ -31284,6 +31287,7 @@ SNULL, 94376135094272, 94377208836095, rcu_barrier(); mas_get_empty_area_rev(&mas, 4096, 139921865637888, 0x6000); MT_BUG_ON(mt, mas.index != 139921865523200); + mt_set_non_kernel(0); mtree_destroy(mt); /* set17 found a bug in walking backwards and not counting nulls at @@ -31297,6 +31301,7 @@ SNULL, 94376135094272, 94377208836095, rcu_barrier(); mas_get_empty_area_rev(&mas, 4096, 139953197334528, 0x1000); MT_BUG_ON(mt, mas.index != 139953197318144); + mt_set_non_kernel(0); mtree_destroy(mt); /* set18 found a bug in walking backwards and not setting the max from @@ -31310,6 +31315,7 @@ SNULL, 94376135094272, 94377208836095, rcu_barrier(); mas_get_empty_area_rev(&mas, 4096, 140222972858368, 2215936); MT_BUG_ON(mt, mas.index != 140222966259712); + mt_set_non_kernel(0); mtree_destroy(mt); /* set19 found 2 bugs in prev. @@ -31328,6 +31334,7 @@ SNULL, 94376135094272, 94377208836095, MT_BUG_ON(mt, entry != xa_mk_value(140656779083776)); entry = mas_prev(&mas, 0); MT_BUG_ON(mt, entry != xa_mk_value(140656766251008)); + mt_set_non_kernel(0); mtree_destroy(mt); /* set20 found a bug in mas_may_move_gap due to the slot being @@ -31338,6 +31345,7 @@ SNULL, 94376135094272, 94377208836095, check_erase2_testset(mt, set20, ARRAY_SIZE(set20)); rcu_barrier(); check_load(mt, 94849009414144, NULL); + mt_set_non_kernel(0); mtree_destroy(mt); mt_set_non_kernel(99); @@ -31345,6 +31353,7 @@ SNULL, 94376135094272, 94377208836095, check_erase2_testset(mt, set21, ARRAY_SIZE(set21)); rcu_barrier(); mt_validate(mt); + mt_set_non_kernel(0); mtree_destroy(mt); mt_set_non_kernel(999); @@ -31501,8 +31510,8 @@ SNULL, 94376135094272, 94377208836095, mt_set_non_kernel(0); mt_validate(mt); mtree_destroy(mt); - mt_set_non_kernel(99); + mt_set_non_kernel(99); // Empty leaf at the end of a parent caused incorrect gap. mas_reset(&mas); mtree_init(mt, MAPLE_ALLOC_RANGE); @@ -31517,7 +31526,6 @@ SNULL, 94376135094272, 94377208836095, check_erase2_testset(mt, set37, ARRAY_SIZE(set37)); rcu_barrier(); MT_BUG_ON(mt, 0 != mtree_load(mt, 94637033459712)); - mt_set_non_kernel(0); mt_validate(mt); mtree_destroy(mt); @@ -31526,7 +31534,6 @@ SNULL, 94376135094272, 94377208836095, check_erase2_testset(mt, set38, ARRAY_SIZE(set38)); rcu_barrier(); MT_BUG_ON(mt, 0 != mtree_load(mt, 94637033459712)); - mt_set_non_kernel(0); mt_validate(mt); mtree_destroy(mt); @@ -31881,14 +31888,6 @@ static noinline void check_ranges(struct maple_tree *mt) 118, 128, }; - unsigned long overflow[] = { - 1317, - 1321, - 1351, - 1352, - 1365, - }; - MT_BUG_ON(mt, !mtree_empty(mt)); check_insert_range(mt, r[0], r[1], xa_mk_value(r[0]), 0); check_insert_range(mt, r[2], r[3], xa_mk_value(r[2]), 0); @@ -32102,17 +32101,33 @@ static noinline void check_ranges(struct maple_tree *mt) MT_BUG_ON(mt, !mt_height(mt)); mtree_destroy(mt); + // FIXME: After changing mas_wr_walk to actually count full nodes, this + // testcase and the one below should cause a height increment. mtree_init(mt, MAPLE_ALLOC_RANGE); - for (i = 0; i <= 1590; i++) { +// for (i = 0; i <= 1590; i++) { + for (i = 0; i <= 1420; i++) { val = i*10; val2 = (i+1)*10; check_store_range(mt, val, val2, xa_mk_value(val), 0); - if (mt_height(mt) >= 4) - BUG_ON(1); + MT_BUG_ON(mt, mt_height(mt) >= 4); } // Cause a 3 child split all the way up the tree. - check_store_range(mt, 15519, 15519, NULL, 0); - BUG_ON(mt_height(mt) < 4); + check_store_range(mt, 9755, 9759, NULL, 0); + MT_BUG_ON(mt, mt_height(mt) >= 4); + //MT_BUG_ON(mt, mt_height(mt) < 4); + mtree_destroy(mt); + + mtree_init(mt, MAPLE_ALLOC_RANGE); + for (i = 0; i <= 1420; i++) { + val = i*10; + val2 = (i+1)*10; + check_store_range(mt, val, val2, xa_mk_value(val), 0); + MT_BUG_ON(mt, mt_height(mt) >= 4); + } + // triple split across multiple levels. + check_store_range(mt, 9595, 9599, NULL, 0); + MT_BUG_ON(mt, mt_height(mt) >= 4); + //MT_BUG_ON(mt, mt_height(mt) < 4); } static noinline void check_next_entry(struct maple_tree *mt) -- 2.50.1