From 16513260af908170a4e518fdfc85f2adf5df2361 Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Fri, 17 Jul 2020 15:51:27 -0400 Subject: [PATCH] maple_tree: mas_split cleanup Signed-off-by: Liam R. Howlett --- lib/maple_tree.c | 241 ++++++++++++++++++++++++----------------------- 1 file changed, 121 insertions(+), 120 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 3151891ce66f..01f08b15cb54 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -1496,7 +1496,8 @@ static inline int mab_calc_split(struct maple_big_node *b_node, int split = b_node->b_end / 2; // Assume equal split. unsigned char slot_cnt = mt_slots[b_node->type]; - if (mab_middle_node(b_node, b_node->b_end, split, slot_cnt)) { + if (ma_is_leaf(b_node->type) && + mab_middle_node(b_node, b_node->b_end, split, slot_cnt)) { split = b_node->b_end / 3; *mid_split = split * 2; } else { @@ -1552,9 +1553,9 @@ static inline void mas_mab_cp(struct ma_state *mas, unsigned char mas_start, b_node->b_end = j; } -static inline int mab_mas_cp(struct maple_big_node *b_node, - unsigned char mab_start, unsigned char mab_end, - struct ma_state *mas, unsigned char mas_start) +static inline void mab_mas_cp(struct maple_big_node *b_node, + unsigned char mab_start, unsigned char mab_end, + struct ma_state *mas, unsigned char mas_start) { int i, j; @@ -1570,8 +1571,6 @@ static inline int mab_mas_cp(struct maple_big_node *b_node, if (!mte_is_leaf(mas->node) && mt_is_alloc(mas->tree)) mte_set_gap(mas->node, j, b_node->gap[i]); } - - return i; } static inline void mas_descend_adopt(struct ma_state *mas) @@ -1708,29 +1707,23 @@ static inline bool mas_next_sibling(struct ma_state *mas) mas_descend(mas); return true; } -/* mast_consume() - Add the portions of the tree which will be replaced by the +/* mast_topiary() - Add the portions of the tree which will be replaced by the * operation to the removal list; either to be @free or @discard (destroy walk). */ -static inline void mast_consume(struct maple_subtree_state *mast) +static inline void mast_topiary(struct maple_subtree_state *mast) { unsigned char l_slot, r_slot, slot, end; - unsigned long l_min, range_min, range_max; + unsigned long l_index, range_min, range_max; // The left node is consumed, so add to the free list. - l_min = mast->orig_l->index; + l_index = mast->orig_l->index; mast->orig_l->index = mast->orig_l->last; mas_node_walk(mast->orig_l, mte_node_type(mast->orig_l->node), &range_min, &range_max); - mast->orig_l->index = l_min; + mast->orig_l->index = l_index; l_slot = mas_get_slot(mast->orig_l); r_slot = mas_get_slot(mast->orig_r); if (mast->orig_l->node == mast->orig_r->node) { - /* If the contents up to l_slot and from r_slot to end are - * still valid and it's the same node, then the rest may need to - * be mast->destroyed. The exception is if a there is data taken - * from the parent in the previous iteration which is still in - * use. - */ for (slot = l_slot + 1; slot < r_slot; slot++) mat_add(mast->destroy, mas_get_rcu_slot(mast->orig_l, slot)); @@ -1740,7 +1733,7 @@ static inline void mast_consume(struct maple_subtree_state *mast) if (mte_is_leaf(mast->orig_r->node)) return; - /* Now free l_slot + 1 -> end and 0 -> r_slot - 1 */ + /* Now destroy l_slot + 1 -> end and 0 -> r_slot - 1 */ end = mas_data_end(mast->orig_l); for (slot = l_slot + 1; slot <= end; slot++) mat_add(mast->destroy, mas_get_rcu_slot(mast->orig_l, slot)); @@ -2020,7 +2013,7 @@ static inline bool mast_new_root(struct maple_subtree_state *mast, } else { do { mast_ascend_free(mast); - mast_consume(mast); + mast_topiary(mast); } while (!mte_is_root(mast->orig_l->node)); } @@ -2096,6 +2089,14 @@ static inline bool mast_sufficient(struct maple_subtree_state *mast) return false; } + +static inline void mast_setup_bnode_for_split(struct maple_subtree_state *mast) +{ + mast->bn->b_end--; + mast->bn->min = mast->orig_l->min; + mast->bn->type = mte_node_type(mast->orig_l->node); +} + /* Private * * mas_combine_separate() - Follow the tree upwards from @l_mas and @r_mas for @@ -2114,7 +2115,8 @@ static inline bool mast_sufficient(struct maple_subtree_state *mast) * Returns the number of elements in b_node during the last loop. */ static inline int mas_combine_separate(struct ma_state *mas, - struct maple_subtree_state *mast, unsigned char count) + struct maple_subtree_state *mast, + unsigned char count) { unsigned char split, mid_split; unsigned char slot = 0; @@ -2135,11 +2137,9 @@ static inline int mas_combine_separate(struct ma_state *mas, /* MA_START doesn't work here */ l_mas.node = r_mas.node = m_mas.node = NULL; - mast_consume(mast); + mast_topiary(mast); while(count--) { - mast->bn->b_end--; - mast->bn->min = mast->orig_l->min; - mast->bn->type = mte_node_type(mast->orig_l->node); + 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, right, split); @@ -2147,16 +2147,14 @@ static inline int mas_combine_separate(struct ma_state *mas, /* Copy data from next level in the tree to mast->bn from next iteration */ memset(mast->bn, 0, sizeof(struct maple_big_node)); + mast->bn->b_end = 0; mast->orig_l->depth++; if (mast_new_root(mast, mas)) goto new_root; mast_ascend_free(mast); - - mast->bn->b_end = 0; mast_combine_cp_left(mast); - mas_set_slot(&l_mas, mast->bn->b_end); mab_set_b_end(mast->bn, &l_mas, left); mab_set_b_end(mast->bn, &m_mas, middle); @@ -2164,7 +2162,7 @@ static inline int mas_combine_separate(struct ma_state *mas, // Copy anything necessary out of the right node. mast_combine_cp_right(mast); - mast_consume(mast); + mast_topiary(mast); mast->orig_l->last = mast->orig_l->max; if(mast_sufficient(mast)) @@ -2249,19 +2247,81 @@ static inline int mas_rebalance(struct ma_state *mas, return mas_combine_separate(mas, &mast, empty_cnt); } +static inline bool mas_split_final_node(struct maple_subtree_state *mast, + struct ma_state *mas, int height) +{ + struct maple_enode *ancestor; + + if (height <= mas->full_cnt) + return false; + + if (mte_is_root(mas->node)) { + if (mt_is_alloc(mas->tree)) + mast->bn->type = maple_arange_64; + else + mast->bn->type = maple_range_64; + mas->depth = height; + } + /* Only a single node is used here, could be root. + * Big_node should just fit in a single node. + */ + ancestor = mas_new_ma_node(mas, mast->bn); + mte_set_parent(mast->l->node, ancestor, mas_get_slot(mast->l)); + mte_set_parent(mast->r->node, ancestor, mas_get_slot(mast->r)); + mte_to_node(ancestor)->parent = mas_mn(mas)->parent; + // New root requires a new height. + if (mas->full_cnt >= mas->tree->ma_height) + mas->tree->ma_height++; + + mast->l->node = ancestor; + mab_mas_cp(mast->bn, 0, mt_slots[mast->bn->type] - 1, mast->l, 0); + return true; +} + +static inline void mast_split_fill_bnode(struct maple_subtree_state *mast, + struct ma_state *mas) +{ + bool cp = true; + struct maple_enode *old = mas->node; + unsigned char split; + + memset(mast->bn, 0, sizeof(struct maple_big_node)); + if (mte_is_root(mas->node)) { + cp = false; + } else { + mas_ascend(mas); + mat_add(mast->free, old); + mas_set_slot(mas, mte_parent_slot(mas->node)); + } + + mast->bn->min = mas->min; + if (cp && mas_get_slot(mast->l)) + mas_mab_cp(mas, 0, mas_get_slot(mast->l) - 1, mast->bn, 0); + + split = mast->bn->b_end; + mab_set_b_end(mast->bn, mast->l, mast->l->node); + mas_set_slot(mast->r, mast->bn->b_end); + mab_set_b_end(mast->bn, mast->r, mast->r->node); + if (cp) + mas_mab_cp(mas, split + 1, mt_slot_count(mas->node) - 1, + mast->bn, mast->bn->b_end); + mast->bn->b_end--; + mast->bn->type = mte_node_type(mas->node); +} + static inline int mas_split(struct ma_state *mas, struct maple_big_node *b_node) { - struct maple_enode *ancestor = MAS_NONE; - unsigned char split = 0; - int j, height = 0; + struct maple_subtree_state mast; + unsigned char p_slot, split = 0; + int height = 0; + unsigned char mid_split; 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_STATE(prev_l_mas, mas->tree, mas->index, mas->last); + MA_STATE(prev_r_mas, mas->tree, mas->index, mas->last); MA_TOPIARY(mat, mas->tree); // Allocation failures will happen early. @@ -2269,103 +2329,42 @@ static inline int mas_split(struct ma_state *mas, if (mas_is_err(mas)) return 0; + mast.l = &l_mas; + mast.r = &r_mas; + mast.free = &mat; + mast.bn = b_node; + while (height++ <= mas->full_cnt) { - unsigned char mid_split; - unsigned char slot_cnt = mt_slot_count(mas->node); - bool cp = true; - - b_node->type = mte_node_type(mas->node); - if (height > mas->full_cnt) { - // The last node to be created. - if (mte_is_root(mas->node)) { - if (mt_is_alloc(mas->tree)) - b_node->type = maple_arange_64; - else - b_node->type = maple_range_64; - mas->depth = height; - } - /* Only a single node is used here, could be root. - * Big_node should just fit in a single node. - */ - ancestor = mas_new_ma_node(mas, b_node); - mte_set_parent(l_mas.node, ancestor, - mas_get_slot(&l_mas)); - mte_set_parent(r_mas.node, ancestor, - mas_get_slot(&r_mas)); - mte_to_node(ancestor)->parent = mas_mn(mas)->parent; - // New root requires a new height. - if (mas->full_cnt >= mas->tree->ma_height) - mas->tree->ma_height++; - l_mas.node = ancestor; - mab_mas_cp(b_node, 0, mt_slots[b_node->type] - 1, - &l_mas, 0); + if (mas_split_final_node(&mast, mas, height)) break; - } - b_node->min = mas->min; mas_dup_state(&l_mas, mas); mas_dup_state(&r_mas, mas); l_mas.node = mas_new_ma_node(mas, b_node); r_mas.node = mas_new_ma_node(mas, b_node); - if (mte_is_leaf(mas->node)) { - split = mab_calc_split(b_node, &mid_split); - if (split < slot_cnt) - j = mab_mas_cp(b_node, 0, split, &l_mas, 0); - else - j = mab_mas_cp(b_node, 0, slot_cnt, &l_mas, 0); - - mte_set_pivot(r_mas.node, 0, r_mas.max); - mab_mas_cp(b_node, j, b_node->b_end, &r_mas, 0); - mas_set_slot(&l_mas, mte_parent_slot(mas->node)); - r_mas.min = l_mas.max + 1; - // In the case of empty. - mas_set_slot(&r_mas, mas_get_slot(&l_mas) + 1); - } else { - unsigned char p_slot; - /* Note, look into shifting data left or right */ - /* internal node split - cut in half for now. */ - split = slot_cnt / 2; - j = mab_mas_cp(b_node, 0, split, &l_mas, 0); - l_mas.max = b_node->pivot[j - 1]; - r_mas.min = l_mas.max + 1; - mab_mas_cp(b_node, j, slot_cnt, &r_mas, 0); - p_slot = mas_get_slot(&orig_l_mas); - mas_set_split_parent(&orig_l_mas, l_mas.node, - r_mas.node, &p_slot, split); - mas_set_split_parent(&orig_r_mas, l_mas.node, - r_mas.node, &p_slot, split); - } - - b_node->b_end = 0; - memset(b_node, 0, sizeof(struct maple_big_node)); - 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)); + split = mab_calc_split(b_node, &mid_split); + mab_mas_cp(b_node, 0, split, &l_mas, 0); + mte_set_pivot(r_mas.node, 0, r_mas.max); + mab_mas_cp(b_node, split + 1, b_node->b_end, &r_mas, 0); + mas_set_slot(&l_mas, mte_parent_slot(mas->node)); + l_mas.max = b_node->pivot[split]; + r_mas.min = l_mas.max + 1; + if (!mte_is_leaf(mas->node)) { + p_slot = mas_get_slot(&prev_l_mas); + mas_set_split_parent(&prev_l_mas, l_mas.node, + r_mas.node, &p_slot, split); + mas_set_split_parent(&prev_r_mas, l_mas.node, + r_mas.node, &p_slot, split); } - - if (cp && mas_get_slot(&l_mas)) - mas_mab_cp(mas, 0, mas_get_slot(&l_mas) - 1, b_node, 0); - - split = b_node->b_end; - mab_set_b_end(b_node, &l_mas, l_mas.node); - mas_set_slot(&r_mas, b_node->b_end); - mab_set_b_end(b_node, &r_mas, r_mas.node); - mas_dup_state(&orig_l_mas, &l_mas); - mas_dup_state(&orig_r_mas, &r_mas); - if (cp) - mas_mab_cp(mas, split + 1, mt_slot_count(mas->node) - 1, - b_node, b_node->b_end); + mast_split_fill_bnode(&mast, mas); + mas_dup_state(&prev_l_mas, mast.l); + mas_dup_state(&prev_r_mas, mast.r); } // Set the original node as dead - mat_add(&mat, mas->node); - mas->node = ancestor; - mas_wmb_replace(mas, &mat, NULL); + mat_add(mast.free, mas->node); + mas->node = l_mas.node; + mas_wmb_replace(mas, mast.free, NULL); return 1; } @@ -2857,6 +2856,7 @@ static inline void *_mas_store(struct ma_state *mas, void *entry, bool overwrite memset(&b_node, 0, sizeof(struct maple_big_node)); mas_set_slot(mas, slot); b_node.b_end = mas_store_b_node(mas, &b_node, entry); + b_node.min = mas->min; // Check if this is an append operation. end = mas_data_end(mas); @@ -2876,6 +2876,7 @@ static inline void *_mas_store(struct ma_state *mas, void *entry, bool overwrite else if (b_node.b_end < mt_min_slot_cnt(mas->node)) mas_cnt_empty(mas); + b_node.type = mte_node_type(mas->node); mas_commit_b_node(mas, &b_node); if (mas_is_err(mas)) ret = 3; -- 2.50.1