From ca4e337a23a03812ee8612937a4ce3d1dc777d78 Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Mon, 8 Mar 2021 22:46:05 -0500 Subject: [PATCH] maple_tree: Fix spanning_rebalance() insufficient nodes and mas state. Fix mas state when expanding a root, the offset on rebalance, and the node and offset when doing a spanning store. Note that spanning rebalance needed to do some tricky free/no free based on where the node data comes from. Next would skip the free of the next node as it is picked up when mas_topiary() trims the parents children Signed-off-by: Liam R. Howlett --- lib/maple_tree.c | 134 +++++++++++++++++++++++++++++------------- lib/test_maple_tree.c | 20 ++++++- 2 files changed, 112 insertions(+), 42 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 62c8c90f6af2..508e3dfae75c 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -74,7 +74,7 @@ struct maple_big_node { struct maple_subtree_state { struct ma_state *orig_l; /* Original left side of subtree */ - struct ma_state *orig_r; /* Original rigth side of subtree */ + struct ma_state *orig_r; /* Original right side of subtree */ struct ma_state *l; /* New left side of subtree */ struct ma_state *m; /* New middle of subtree (rare) */ struct ma_state *r; /* New right side of subtree */ @@ -2013,6 +2013,7 @@ static inline void mast_topiary(struct maple_subtree_state *mast) for (offset = l_off + 1; offset < r_off; offset++) mat_add(mast->destroy, mas_slot_locked(mast->orig_l, slots, offset)); + return; } /* mast->orig_r is different and consumed. */ @@ -2026,6 +2027,7 @@ static inline void mast_topiary(struct maple_subtree_state *mast) child = mas_slot_locked(mast->orig_l, slots, offset++); if (!child) break; + mat_add(mast->destroy, child); } @@ -2042,13 +2044,15 @@ static inline void mast_topiary(struct maple_subtree_state *mast) * @old_r: The encoded maple node to the right (next node). */ static inline void mast_rebalance_next(struct maple_subtree_state *mast, - struct maple_enode *old_r) + struct maple_enode *old_r, bool free) { unsigned char b_end = mast->bn->b_end; mas_mab_cp(mast->orig_r, 0, mt_slot_count(mast->orig_r->node), mast->bn, b_end); - mat_add(mast->free, old_r); + if (free) + mat_add(mast->free, old_r); + mast->orig_r->last = mast->orig_r->max; if (old_r == mast->orig_l->node) mast->orig_l->node = mast->orig_r->node; @@ -2081,14 +2085,15 @@ static inline void mast_rebalance_prev(struct maple_subtree_state *mast, * Check the right side, then the left. Data is copied into the @mast->bn. * @mast: The maple_subtree_state. */ -static inline bool mast_sibling_rebalance_right(struct maple_subtree_state *mast) +static inline +bool mast_sibling_rebalance_right(struct maple_subtree_state *mast, bool free) { struct maple_enode *old_r; struct maple_enode *old_l; old_r = mast->orig_r->node; if (mas_next_sibling(mast->orig_r)) { - mast_rebalance_next(mast, old_r); + mast_rebalance_next(mast, old_r, free); return true; } @@ -2109,7 +2114,8 @@ static inline unsigned long mas_next_node(struct ma_state *mas, * Check the right side, then the left. Data is copied into the @mast->bn. * @mast: The maple_subtree_state. */ -static inline bool mast_cousin_rebalance_right(struct maple_subtree_state *mast) +static inline +bool mast_cousin_rebalance_right(struct maple_subtree_state *mast, bool free) { struct maple_enode *old_l = mast->orig_l->node; struct maple_enode *old_r = mast->orig_r->node; @@ -2119,7 +2125,7 @@ static inline bool mast_cousin_rebalance_right(struct maple_subtree_state *mast) mas_dup_state(&tmp, mast->orig_r); mas_next_node(mast->orig_r, ULONG_MAX); if (!mas_is_none(mast->orig_r)) { - mast_rebalance_next(mast, old_r); + mast_rebalance_next(mast, old_r, free); return true; } @@ -2185,7 +2191,7 @@ mast_ascend_free(struct maple_subtree_state *mast) * @b_node: the maple_big_node with the type encoding. * * Use the node type from the maple_big_node to allocate a new node from the - * maple_state. This function exists mainly for code readability. + * ma_state. This function exists mainly for code readability. * * Return: A new maple encoded node */ @@ -2414,11 +2420,9 @@ static inline void mast_new_root(struct maple_subtree_state *mast, * @mid_split: The location to split between middle and right. */ static inline void mast_cp_to_nodes(struct maple_subtree_state *mast, - struct maple_enode *left, - struct maple_enode *middle, - struct maple_enode *right, - unsigned char split, - unsigned char mid_split) + struct maple_enode *left, struct maple_enode *middle, + struct maple_enode *right, unsigned char split, unsigned char mid_split, + struct ma_state *save) { mast->l->node = mte_node_or_none(left); mast->m->node = mte_node_or_none(middle); @@ -2433,6 +2437,13 @@ static inline void mast_cp_to_nodes(struct maple_subtree_state *mast, mab_mas_cp(mast->bn, 1 + split, mid_split, mast->m); mast->m->min = mast->bn->pivot[split] + 1; mast->m->max = mast->bn->pivot[mid_split]; + if (!save->node && + (save->offset > split) && (save->offset < mid_split)) { + save->offset -= (split + 1); + save->node= mast->m->node; + save->min = mast->m->min; + save->max = mast->m->max; + } split = mid_split; } @@ -2440,6 +2451,17 @@ static inline void mast_cp_to_nodes(struct maple_subtree_state *mast, mab_mas_cp(mast->bn, 1 + split, mast->bn->b_end, mast->r); mast->r->min = mast->bn->pivot[split] + 1; mast->r->max = mast->bn->pivot[mast->bn->b_end]; + if (!save->node && (save->offset > split)) { + save->offset -= (split + 1); + save->node= mast->r->node; + save->min = mast->r->min; + save->max = mast->r->max; + } + } + if (!save->node) { + save->node= mast->l->node; + save->min = mast->l->min; + save->max = mast->l->max; } } @@ -2531,9 +2553,9 @@ static inline void mast_setup_bnode_for_split(struct maple_subtree_state *mast) * Return: the number of elements in b_node during the last loop. */ static int mas_spanning_rebalance(struct ma_state *mas, - struct maple_subtree_state *mast, - unsigned char count) + struct maple_subtree_state *mast, unsigned char count) { + struct ma_state restore; unsigned char split, mid_split; unsigned char slot = 0; struct maple_enode *left = NULL, *middle = NULL, *right = NULL; @@ -2550,16 +2572,25 @@ static int mas_spanning_rebalance(struct ma_state *mas, mast->free = &free; mast->destroy = &destroy; l_mas.node = r_mas.node = m_mas.node = MAS_NONE; - + if (!mas_is_root_limits(mas) && + unlikely(mast->bn->b_end <= mt_min_slots[mast->bn->type])) { + // Do not free the current node as it may be freed in a bulk + // free. + if (!mast_sibling_rebalance_right(mast, false)) + mast_cousin_rebalance_right(mast, false); + } + restore.node = NULL; + restore.offset = mas->offset; mast->orig_l->depth = 0; - mast_topiary(mast); + while (count--) { mast_setup_bnode_for_split(mast); split = mas_mab_to_node(mas, mast->bn, &left, &right, &middle, &mid_split); mast_set_split_parents(mast, left, middle, right, split, mid_split); - mast_cp_to_nodes(mast, left, middle, right, split, mid_split); + mast_cp_to_nodes(mast, left, middle, right, split, mid_split, + &restore); /* Copy data from next level in the tree to mast->bn from next iteration */ memset(mast->bn, 0, sizeof(struct maple_big_node)); @@ -2594,8 +2625,8 @@ static int mas_spanning_rebalance(struct ma_state *mas, // Try to get enough data for the next iteration. - if (!mast_sibling_rebalance_right(mast)) - if (!mast_cousin_rebalance_right(mast)) + if (!mast_sibling_rebalance_right(mast, true)) + if (!mast_cousin_rebalance_right(mast, true)) break; // rebalancing from other nodes may require another loop. @@ -2628,6 +2659,10 @@ new_root: // Set up mas for insertion. mas_dup_state(mas, mast->orig_l); mas_wmb_replace(mas, &free, &destroy); + mas->offset = restore.offset; + mas->min = restore.min; + mas->max = restore.max; + mas->node = restore.node; return mast->bn->b_end; } @@ -2641,7 +2676,8 @@ new_root: * * Return: the number of elements in b_node during the last loop. */ -static inline int mas_rebalance(struct ma_state *mas, struct maple_big_node *b_node) +static inline int mas_rebalance(struct ma_state *mas, + struct maple_big_node *b_node) { char empty_count = mas_mt_height(mas); struct maple_subtree_state mast; @@ -2672,6 +2708,7 @@ static inline int mas_rebalance(struct ma_state *mas, struct maple_big_node *b_n mas_prev_sibling(&l_mas); shift = mas_data_end(&l_mas) + 1; mab_shift_right(b_node, shift); + mas->offset += shift; mas_mab_cp(&l_mas, 0, shift - 1, b_node, 0); b_node->b_end = shift + b_end; l_mas.index = l_mas.last = l_mas.min; @@ -2908,8 +2945,7 @@ static inline void mast_fill_bnode(struct maple_subtree_state *mast, * @split: The location to split the big node */ static inline void mast_split_data(struct maple_subtree_state *mast, - struct ma_state *mas, - unsigned char split) + struct ma_state *mas, unsigned char split, struct ma_state *save) { unsigned char p_slot; @@ -2925,6 +2961,17 @@ static inline void mast_split_data(struct maple_subtree_state *mast, mast->r->node, &p_slot, split); mas_set_split_parent(mast->orig_r, mast->l->node, mast->r->node, &p_slot, split); + } else { + if (save->offset > split) { + save->node = mast->r->node; + save->min = mast->r->min; + save->max = mast->r->max; + save->offset -= (split + 1); + } else { + save->node = mast->l->node; + save->min = mast->l->min; + save->max = mast->l->max; + } } } @@ -2941,7 +2988,8 @@ static inline void mast_split_data(struct maple_subtree_state *mast, * Return: True if pushed, false otherwise. */ static inline bool mas_push_data(struct ma_state *mas, int height, - struct maple_subtree_state *mast, bool left) + struct maple_subtree_state *mast, bool left, + struct ma_state *save) { unsigned char slot_total = mast->bn->b_end; unsigned char end, space, split; @@ -2974,6 +3022,8 @@ static inline bool mas_push_data(struct ma_state *mas, int height, mab_shift_right(mast->bn, end + 1); mas_mab_cp(&tmp_mas, 0, end, mast->bn, 0); mast->bn->b_end = slot_total + 1; + if (!save->node) + save->offset = mas->offset + end + 1; } else { mas_mab_cp(&tmp_mas, 0, end, mast->bn, mast->bn->b_end); } @@ -2998,7 +3048,7 @@ static inline bool mas_push_data(struct ma_state *mas, int height, if (left) mast->orig_l->offset += end + 1; - mast_split_data(mast, mas, split); + mast_split_data(mast, mas, split, save); mast_fill_bnode(mast, mas, 2); _mas_split_final_node(mast, mas, height + 1); return true; @@ -3016,6 +3066,7 @@ static int mas_split(struct ma_state *mas, struct maple_big_node *b_node) struct maple_subtree_state mast; int height = 0; unsigned char mid_split, split = 0; + struct ma_state restore; MA_STATE(l_mas, mas->tree, mas->index, mas->last); MA_STATE(r_mas, mas->tree, mas->index, mas->last); @@ -3036,6 +3087,8 @@ static int mas_split(struct ma_state *mas, struct maple_big_node *b_node) mast.orig_r = &prev_r_mas; mast.free = &mat; mast.bn = b_node; + restore.node = NULL; + restore.offset = mas->offset; while (height++ <= mas->depth) { if (mas_split_final_node(&mast, mas, height)) @@ -3046,15 +3099,15 @@ static int mas_split(struct ma_state *mas, struct maple_big_node *b_node) l_mas.node = mas_new_ma_node(mas, b_node); r_mas.node = mas_new_ma_node(mas, b_node); // Try to push left. - if (mas_push_data(mas, height, &mast, true)) + if (mas_push_data(mas, height, &mast, true, &restore)) break; // Try to push right. - if (mas_push_data(mas, height, &mast, false)) + if (mas_push_data(mas, height, &mast, false, &restore)) break; split = mab_calc_split(mas, b_node, &mid_split); - mast_split_data(&mast, mas, split); + mast_split_data(&mast, mas, split, &restore); // Usually correct, mab_mas_cp in the above call overwrites r->max. mast.r->max = mas->max; mast_fill_bnode(&mast, mas, 1); @@ -3066,6 +3119,10 @@ static int mas_split(struct ma_state *mas, struct maple_big_node *b_node) mat_add(mast.free, mas->node); mas->node = l_mas.node; mas_wmb_replace(mas, mast.free, NULL); + mas->offset = restore.offset; + mas->min = restore.min; + mas->max = restore.max; + mas->node = restore.node; return 1; } @@ -3128,7 +3185,7 @@ static inline int mas_commit_b_node(struct ma_state *mas, return mas_split(mas, b_node); if (mas_reuse_node(mas, b_node, end)) - goto reused_node; + goto reuse_node; mas_node_count(mas, 1); if (mas_is_err(mas)) @@ -3137,12 +3194,11 @@ static inline int mas_commit_b_node(struct ma_state *mas, new_node = mt_mk_node(mas_pop_node(mas), mte_node_type(mas->node)); mte_to_node(new_node)->parent = mas_mn(mas)->parent; mas->node = new_node; - mab_mas_cp(b_node, 0, b_end, mas); mas_replace(mas, false); -reused_node: +reuse_node: mas_update_gap(mas); - return 2; + return 1; } /* @@ -3197,7 +3253,8 @@ static inline int mas_root_expand(struct ma_state *mas, void *entry) * * Return: 0 on success, 1 otherwise. */ -static inline int mas_root_ptr(struct ma_state *mas, void *entry, bool overwrite) +static inline int mas_root_ptr(struct ma_state *mas, void *entry, + bool overwrite) { int ret = 1; @@ -3213,8 +3270,10 @@ static inline int mas_root_ptr(struct ma_state *mas, void *entry, bool overwrite ret = mas_root_expand(mas, entry); else if (((unsigned long) (entry) & 3) == 2) ret = mas_root_expand(mas, entry); - else + else { rcu_assign_pointer(mas->tree->ma_root, entry); + mas->node = MAS_START; + } return ret; exists: @@ -5191,9 +5250,6 @@ void *mas_store(struct ma_state *mas, void *entry) if (unlikely(mas_is_err(mas))) return existing; - if (unlikely(!mte_is_leaf(mas->node))) // spanning store occurred - mas_walk(mas); - return existing; } @@ -5221,11 +5277,7 @@ retry: if (unlikely(mas_is_err(mas))) return xa_err(mas->node); - if (unlikely(!mte_is_leaf(mas->node))) // spanning store occurred - mas_walk(mas); - return 0; - } /* diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c index 315f54693669..75a875fcfa8a 100644 --- a/lib/test_maple_tree.c +++ b/lib/test_maple_tree.c @@ -22588,6 +22588,7 @@ SNULL, 140249682087935, 140249710600191, STORE, 140249652703232, 140249682087935, STORE, 140249682087936, 140249710600191, }; + unsigned long set26[] = { STORE, 140737488347136, 140737488351231, STORE, 140729464770560, 140737488351231, @@ -35875,6 +35876,20 @@ static noinline void check_rcu(struct maple_tree *mt) rcu_unregister_thread(); } +/* Test spanning writes that require balancing right sibling or right cousin + */ +static noinline void check_spanning_relatives(struct maple_tree *mt) +{ + + unsigned long i, nr_entries = 1000; + for (i = 0; i <= nr_entries; i++) + mtree_store_range(mt, i*10, i*10 + 5, + xa_mk_value(i), GFP_KERNEL); + + + mtree_store_range(mt, 9365, 9955, NULL, GFP_KERNEL); +} + static DEFINE_MTREE(tree); static int maple_tree_seed(void) { @@ -36103,11 +36118,14 @@ static int maple_tree_seed(void) next_prev_test(&tree); mtree_destroy(&tree); - mtree_init(&tree, MAPLE_ALLOC_RANGE); check_rcu(&tree); mtree_destroy(&tree); + mtree_init(&tree, MAPLE_ALLOC_RANGE); + check_spanning_relatives(&tree); + mtree_destroy(&tree); + #if defined(BENCH) skip: #endif -- 2.50.1