From dbc3ebf309ffb89b04e20e2d858d3b335e33541a Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Thu, 16 Jul 2020 11:05:44 -0400 Subject: [PATCH] maple_tree: Remove fixed array size from mas_split and use ma_topiary instead. Also, move common smp_wmb() from split and combine_separate function into a helper. Signed-off-by: Liam R. Howlett --- lib/maple_tree.c | 73 ++++++++++++++++++++++++------------------------ 1 file changed, 36 insertions(+), 37 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 6edde8819e19..5fc0ef6d9915 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -1837,6 +1837,31 @@ static inline void mas_separate_set_parent(struct ma_state *mas, (*slot)++; } + +static inline void mas_wmb_replace(struct ma_state *mas, + struct ma_topiary *free, + struct ma_topiary *destroy) +{ + smp_wmb(); + + // Insert the new data in the tree + mas_replace(mas, true); + + if (!mte_is_leaf(mas->node)) + mas_descend_adopt(mas); + + mat_free(free, false); + + if (destroy) + mat_free(destroy, true); + + if (mte_is_leaf(mas->node)) + return; + + if (mt_is_alloc(mas->tree)) + mas_update_gap(mas, false); +} + /* Private * * mas_combine_separate() - Follow the tree upwards from @l_mas and @r_mas for @@ -2113,22 +2138,7 @@ done: mte_set_node_dead(mas->node); // Set up mas for insertion. mas_dup_state(mas, orig_l_mas); - smp_wmb(); - - // Insert new sub-tree - mas_replace(mas, true); - if (!mte_is_leaf(mas->node)) - mas_descend_adopt(mas); - - mat_free(&free, false); - mat_free(&destroy, true); - - if (mte_is_leaf(mas->node)) - return b_node->b_end; - - if (mt_is_alloc(mas->tree)) - mas_update_gap(mas, false); - + mas_wmb_replace(mas, &free, &destroy); return b_node->b_end; } @@ -2173,14 +2183,15 @@ static inline int mas_split(struct ma_state *mas, struct maple_enode *ancestor = MAS_NONE; unsigned char split = 0; - int j, i = 0, height = 0; - struct maple_enode *list[15]; // Enough for an 8 level tree. + int j, height = 0; MA_STATE(l_mas, mas->tree, mas->index, mas->last); MA_STATE(r_mas, mas->tree, mas->index, mas->last); MA_STATE(orig_l_mas, mas->tree, mas->index, mas->last); MA_STATE(orig_r_mas, mas->tree, mas->index, mas->last); + MA_TOPIARY(mat, mas->tree); + // Allocation failures will happen early. // TODO: Increase this by one when optimizing with a rebalance. @@ -2198,7 +2209,7 @@ static inline int mas_split(struct ma_state *mas, * into the highest common ancestor necessary to be modified (which may * be a new root). */ - list[i++] = mas->node; + //list[i++] = mas->node; while (height++ <= mas->full_cnt) { struct maple_node *l, *r; enum maple_type type = mte_node_type(mas->node); @@ -2308,9 +2319,11 @@ static inline int mas_split(struct ma_state *mas, if (mte_is_root(mas->node)) cp = false; else { + struct maple_enode *old = mas->node; + mas_ascend(mas); + mat_add(&mat, old); mas_set_slot(mas, mte_parent_slot(mas->node)); - list[i++] = mas->node; } if (cp && mas_get_slot(&l_mas)) @@ -2336,24 +2349,10 @@ static inline int mas_split(struct ma_state *mas, j + 1); } - - mas->node = ancestor; - BUG_ON(mas_is_none(mas)); // Set the original node as dead - mte_set_node_dead(list[0]); - smp_wmb(); - - // Insert the new data in the tree - mas_replace(mas, true); - - mas_descend_adopt(mas); - do { - mte_free(list[--i]); - } while (i); - - if (mt_is_alloc(mas->tree)) - mas_update_gap(mas, false); - + mat_add(&mat, mas->node); + mas->node = ancestor; + mas_wmb_replace(mas, &mat, NULL); return 1; } -- 2.50.1