From 7c78bb546dae3a01b2b35a9a536a4ea871e44105 Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Tue, 9 Jun 2020 16:23:21 -0400 Subject: [PATCH] maple_tree: WIP, diet Signed-off-by: Liam R. Howlett --- lib/maple_tree.c | 1377 +--------------------------------------------- 1 file changed, 2 insertions(+), 1375 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index e3dd2f1cdfaf..f515d7549302 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -875,13 +875,6 @@ no_parent: mas->node = p_enode; } -static inline void mte_set_safe_piv(struct ma_state *mas, unsigned char slot, - unsigned long val) -{ - if (slot > mt_pivot_count(mas->node)) - mte_set_pivot(mas->node, slot, val); -} - static inline bool mas_touches_null(struct ma_state *mas) { unsigned char slot = mas_get_slot(mas); @@ -912,135 +905,6 @@ restart: mte_set_pivot(safe_mas.node, slot, val); } -/** Private - * mas_shift_pivot() - Shift a pivot from one node to the next. - * @left - the left node with mas slot set to the pivot location. - * @right - the right node with mas slot set to the pivot location. - * - * This exists when moving gaps across many levels of a tree. Basically, walk - * backwards until the nodes meet and set the pivots accordingly. - * - */ -void mte_destroy_walk(struct maple_enode *mn, struct maple_tree *mtree); -static inline void mas_shift_pivot(struct ma_state *curr, - struct ma_state *next, unsigned long piv) -{ - unsigned char l_p_slot; // left parent slot. - unsigned char r_p_slot; // right parent slot. - - MA_STATE(left, curr->tree, curr->index, curr->last); - MA_STATE(right, next->tree, next->index, next->last); - - mas_dup_state(&left, curr); - mas_dup_state(&right, next); - do { - bool leaf = true; - void *entry; - - // Ends with NULL side - l_p_slot = mte_parent_slot(left.node); - mas_set_slot(&left, l_p_slot); - mas_ascend(&left); - - // Starts with NULL side - r_p_slot = mte_parent_slot(right.node); - mas_set_slot(&right, r_p_slot); - mas_ascend(&right); - - mas_set_safe_pivot(&left, l_p_slot, piv); - if (!mte_is_leaf(left.node)) { - leaf = false; - } - - if (left.node == right.node) { - if (r_p_slot - 1 != l_p_slot) { - int slot = r_p_slot - 1; - do { - entry = mas_get_rcu_slot(&left, slot); - mte_set_pivot(left.node, slot, piv); - if (!leaf) { - if (mt_is_alloc(left.tree)) - mte_set_gap(left.node, slot, 0); - if (!xa_is_advanced(entry)) - mte_free(entry); // Destroy not needed. - } - } while (--slot > l_p_slot); - } - return; - } else { - /* Work right to left to ensure RCU-safe states. */ - while (r_p_slot--) { - entry = mas_get_rcu_slot(&right, r_p_slot); - mte_set_pivot(right.node, r_p_slot, piv); - if (!leaf ) { - if (mt_is_alloc(right.tree)) - mte_set_gap(right.node, r_p_slot, 0); - if (!xa_is_advanced(entry)) - mte_free(entry); - } - } - - /* Now the left */ - while (++l_p_slot < mt_slot_count(left.node)) { - entry = mas_get_rcu_slot(&left, l_p_slot); - if (l_p_slot < mt_pivot_count(left.node) && - !mte_get_pivot(left.node, l_p_slot)) - break; // end of left. - - if ((l_p_slot == mt_slot_count(left.node) - 1) && - (!entry)) - break; // last entry and it's empty. - - mte_set_pivot(left.node, l_p_slot, piv); - if (!leaf ) { - if (mt_is_alloc(left.tree)) - mte_set_gap(left.node, l_p_slot, 0); - if (!xa_is_advanced(entry)) - mte_free(entry); - } - - } - - - - - } - - } while (left.node != right.node); -} -/* mas_get_prev_pivot() - Return the previous pivot. - * - * Mainly for extracting the previous pivot in the case of slot = 0. - * Walk up the tree until the minimum changes, then get the previous pivot. - * - */ -static inline unsigned long mas_get_prev_pivot(const struct ma_state *mas, - unsigned char slot) -{ - unsigned char p_slot = MAPLE_NODE_SLOTS; // parent slot. - - MA_STATE(prev_piv, mas->tree, 0, 0); - - if (slot > 0) - return mas_get_safe_pivot(mas, slot - 1); - - if (mas->min == 0) - return 0; - - - prev_piv.node = mas->node; - prev_piv.min = mas->min; - - while (prev_piv.min == mas->min) { - p_slot = mte_parent_slot(prev_piv.node); - mas_ascend(&prev_piv); - if (p_slot) - break; - } - p_slot--; - return mte_get_pivot(prev_piv.node, slot); -} - static inline struct maple_node *mas_next_alloc(struct ma_state *ms) { int cnt; @@ -1156,7 +1020,8 @@ static inline void ma_free_alloc(struct maple_node *node) kfree(node); } -void mas_empty_alloc(struct ma_state *mas) { +void mas_empty_alloc(struct ma_state *mas) +{ struct maple_node *node = mas_get_alloc(mas); if (node) @@ -1279,484 +1144,6 @@ static inline unsigned char mas_data_end(const struct ma_state *mas) return _mas_data_end(mas, mte_node_type(mas->node), &l); } -// Set min/max for a given slot in mas->node. -static inline void mas_get_range(struct ma_state *mas, unsigned char slot, - unsigned long *min, unsigned long *max) -{ - *min = mas->min; - *max = mas_get_safe_pivot(mas, slot); - if (!(*max)) { - if (slot || mas->min) - *max = mas->max; - } - - if (slot) - *min = mte_get_pivot(mas->node, slot - 1) + 1; - - if ((*min) == 1) // empty node. - *min = mas->min; -} -/* mas_append_entry() - Append an entry to the target slot or overwrite a - * porting of the last slot. - */ -static inline unsigned char mas_append_entry(struct ma_state *mas, void *entry) -{ - unsigned long wr_pivot = mas->min ? mas->min - 1 : 0; - unsigned char dst_slot = mas_get_slot(mas); - - if (!mas_get_rcu_slot(mas, 0) && !mte_get_pivot(mas->node, 0)) - dst_slot = 0; // empty node. - else if (dst_slot > mt_slot_count(mas->node)) { // Should not happen. - dst_slot = _mas_data_end(mas, mte_node_type(mas->node), - &wr_pivot); // slot not set. - } else if (dst_slot) - wr_pivot = mas_get_safe_pivot(mas, dst_slot - 1); - - if (dst_slot && mas->index <= wr_pivot) { - mas_set_safe_pivot(mas, dst_slot - 1, mas->index - 1); - } else if (entry && mas->index && (mas->index - 1 != wr_pivot)) { - if (dst_slot && !mas_get_rcu_slot(mas, dst_slot - 1)) - dst_slot--; - - mte_set_rcu_slot(mas->node, dst_slot, NULL); - mas_set_safe_pivot(mas, dst_slot++, mas->index - 1); - } else if (!entry) { // appending NULL value. - if (mas_get_rcu_slot(mas, dst_slot)) { - mas_set_safe_pivot(mas, dst_slot, mas->index - 1); - dst_slot++; - } - } - - mte_set_rcu_slot(mas->node, dst_slot, entry); - mas_set_safe_pivot(mas, dst_slot, mas->last); - mas->max = mas->last; - - return dst_slot; -} - -static inline unsigned char _mas_append(struct ma_state *mas, - struct maple_node *smn, enum maple_type stype, - unsigned long src_max, - unsigned char src_start, unsigned char src_end) -{ - - unsigned long src_piv; - unsigned char src_slot = src_start; - unsigned char dst_slot = 0; - bool prev_null = false; - void *src_data = NULL; - - // Find last slot in the dst. - while (dst_slot < mt_slot_count(mas->node)) { - unsigned long this_piv; - void *dst_data; - - if (dst_slot < mt_pivot_count(mas->node)) - this_piv = mte_get_pivot(mas->node, dst_slot); - else { // Last slot, no pivot.. - if (src_end >= mt_pivots[stype]) - this_piv = src_max; - else - this_piv = ma_get_pivot(smn, src_end, stype); - } - - dst_data = mas_get_rcu_slot(mas, dst_slot); - if (!dst_data) { - if (!this_piv) - break; - - if (dst_slot == mt_pivot_count(mas->node)) - break; - - prev_null = true; - } else - prev_null = false; - dst_slot++; - } - - // Append data from src. - for (src_slot = src_start; src_slot <= src_end; src_slot++) { - bool next_dst = true; - - src_data = ma_get_rcu_slot(smn, src_slot, stype, mas->tree); - if (xa_is_retry(src_data)) - continue; - - if (src_slot >= mt_pivots[stype]) - src_piv = src_max; - else - src_piv = ma_get_pivot(smn, src_slot, stype); - - if (!src_data) { - if (prev_null && dst_slot) { - mas_set_safe_pivot(mas, dst_slot - 1, src_piv); - next_dst = false; - goto update_gap; - } - - prev_null = true; - } else { - prev_null = false; - } - - if (dst_slot >= mt_slot_count(mas->node) && next_dst) - return dst_slot; - - mte_set_rcu_slot(mas->node, dst_slot, src_data); - mas_set_safe_pivot(mas, dst_slot, src_piv); -update_gap: - if (!mte_is_leaf(mas->node) && mt_is_alloc(mas->tree)) - mte_set_gap(mas->node, dst_slot, - ma_get_gap(smn, src_slot, stype)); - - if (next_dst) - dst_slot++; - - if (mas->max < src_piv) - mas->max = src_piv; - } - - return dst_slot; -} -static inline unsigned char mas_append(struct ma_state *mas, - struct ma_state *src, unsigned char src_start, - unsigned char src_end) -{ - return _mas_append(mas, mas_mn(src), mte_node_type(src->node), - src->max, src_start, src_end); -} - -static inline unsigned char mas_append_calc_split(struct ma_state *mas, - bool active) -{ - unsigned char max = 7, ret = 7; - unsigned char slot; - unsigned long range = mas->max - mas->min; - unsigned long half; - unsigned long piv = 0; - enum maple_type mas_type = mte_node_type(mas->node); - - if (mas_type == maple_arange_64) { - max = 5; - ret = 5; - } - - if (!active) { - if (ma_is_leaf(mas_type)) - return max; - return max - 2; - } - - //if (mas->min == 0) - // max = 7; - - half = max / 2; - if (ma_is_leaf(mas_type)) { - if (range <= 8UL) - return ret; - - for (slot = 0; slot <= mt_pivots[mas_type]; slot++) { - piv = mas_get_safe_pivot(mas, slot); - - if (!piv && slot) - return ret; - - if (piv > mas->max) // possibly a retry. - return ret; - - if ((piv >= mas->index) && (piv <= mas->last)) - continue; - - range = piv - mas->min; - if (range >= 8) { - if (slot > half) - ret = slot; - else - ret = half; - goto done; - } - - } - } else { - for (slot = half; slot <= mt_pivots[mas_type]; slot++) { - piv = mas_get_safe_pivot(mas, slot); - if ((piv >= mas->index) && (piv <= mas->last)) - half++; - else - break; - } - } - - return half; - -done: - if (ret < max) { - bool null = false; - if (piv == ULONG_MAX) - ret++; - - if (mt_is_empty(mas_get_rcu_slot(mas, ret))) - null = true; - - while((ret < max) && // Skip deletes and retries. - ((piv == mas_get_safe_pivot(mas, ret + 1)) || - (null && mt_is_empty(mas_get_rcu_slot(mas, ret + 1))))) - ret++; - } - - return ret; -} -static inline unsigned char mas_skip_overwritten(struct ma_state *mas, - unsigned char data_end, unsigned char slot) -{ - unsigned char ret = slot; - void *entry; - -keep_going: - while ((data_end >= ret) && - (mas_get_safe_pivot(mas, ret) <= mas->last)) - ret++; - - if (!slot) { - // if this is a retry, then the pivot may be lower than - // mas->last and needs to be skipped. - entry = mas_get_rcu_slot(mas, 0); - if (xa_is_skip(entry) || xa_is_retry(entry)) { - slot++; - goto keep_going; - } - } - - return ret; -} -static void mas_split_may_switch_dst(struct ma_state **dst_mas, - struct ma_state *right, unsigned char *dst_slot, - unsigned char split) -{ - struct ma_state *dst = *dst_mas; - - if (dst == right) - return; - - if (*dst_slot >= mt_slot_count(dst->node) || - *dst_slot > split + 1) { - right->min = dst->max + 1; - *dst_mas = right; - *dst_slot = 0; - } -} - -/* Private - * - * mas_append_split_data() - Append the data of a split operation into either - * the left or the right node. If, during the append, the split limit is - * reached, then switch the destination node to the right. This function also - * places the new data within the node. - * @left: The left maple state - * @right: The right maple state - * @src: The source of the data - * @split: Where to start copying to the right node - * @start: The slot to start copying data from in @src - * @end: The last slot to copy data from in @src - * @entry: The new entry to be placed at @src->index - @src->last - */ -static unsigned char mas_append_split_data(struct ma_state *left, - struct ma_state *right, struct ma_state *src, - unsigned char split, unsigned char start, unsigned char end, - unsigned char slot, void *entry) -{ - void *existing_entry = mas_get_rcu_sanitized(src, slot); - struct ma_state *dst = left; - unsigned char dst_slot = slot; - unsigned long slot_min, slot_max; - - if (!left) { - dst = right; - // Adjust dst_slot to right. - dst_slot = slot - split - 1; - } - - while ((mte_get_pivot(src->node, start) < dst->min) && - (start <= end)) { - // Skip retries, etc. - start++; - dst_slot--; - } - - mas_get_range(src, slot, &slot_min, &slot_max); - - if (slot_min < dst->min) - slot_min = dst->min; - - if (dst_slot) { - mas_append(dst, src, start, slot - 1); - dst->max = mte_get_pivot(dst->node, slot - 1); - } - - if (slot_min == src->index) { - mas_set_safe_pivot(dst, dst_slot, dst->last); - mte_set_rcu_slot(dst->node, dst_slot++, entry); - dst->max = dst->last; - } else { - mas_set_safe_pivot(dst, dst_slot, dst->index - 1); - mte_set_rcu_slot(dst->node, dst_slot++, existing_entry); - dst->max = dst->index - 1; - mas_split_may_switch_dst(&dst, right, &dst_slot, split); - mas_set_safe_pivot(dst, dst_slot, dst->last); - mte_set_rcu_slot(dst->node, dst_slot++, entry); - dst->max = dst->last; - } - - // Check if it's time to switch. - mas_split_may_switch_dst(&dst, right, &dst_slot, split); - // Skip anything overwritten by this add - slot = mas_skip_overwritten(src, end, slot); - if (slot >= mt_slot_count(src->node)) - goto done; - - mas_get_range(src, slot, &slot_min, &slot_max); - existing_entry = mas_get_rcu_sanitized(src, slot); - - if (slot_min <= src->last && slot_max > src->last) { - mte_set_rcu_slot(dst->node, dst_slot, existing_entry); - mas_set_safe_pivot(dst, dst_slot++, slot_max); - dst->max = slot_max; - slot++; - } - - mas_split_may_switch_dst(&dst, right, &dst_slot, split); - - if (slot <= end && dst->max < src->max) { - mas_append(dst, src, slot, end); - dst->max = mas_get_safe_pivot(src, end); - slot = end + 1; - } -done: - if (left == dst) - right->min = dst->max + 1; - return slot; -} - -/* Private - * - * mas_append_split() - Helper function to set up the copy of data to two new - * destinations. - * @dst1: Maple state of the left side of the split. - * @dst2: Maple state of the right side of the split. - * @src: The source of the data to be split - * @slot: The target slot to split data - * @entry: The new entry for @src->index - @src->last - * @active: If this node is currently in the tree or not. - */ -static inline unsigned char mas_append_split(struct ma_state *dst1, - struct ma_state *dst2, struct ma_state *src, - unsigned char slot, void *entry, bool active) -{ - unsigned char split = mas_append_calc_split(src, active); - unsigned char data_end = mas_data_end(src); - bool add_entry = mte_is_leaf(src->node); - - mas_set_slot(dst1, slot); - dst1->max = mas_get_safe_pivot(src, split); - dst2->min = dst1->max + 1; - if (!add_entry) - goto not_a_leaf; - - if (slot <= split) { // going into the left one, at least a little. - slot = mas_append_split_data(dst1, dst2, src, split, 0, - split, slot, entry); - // overwriting last entry would cause the max to change. - mas_append(dst2, src, slot, data_end); - } else { // going into the right. - mas_append(dst1, src, 0, split); - mas_append_split_data(NULL, dst2, src, split, split + 1, - data_end, slot, entry); - } - - return split; - -not_a_leaf: - mas_append(dst1, src, 0, split); - if (split != data_end) - split++; - mas_append(dst2, src, split, data_end); - return split; -} - - -static inline unsigned char mas_dense_calc_split(struct ma_state *mas, - struct maple_enode **left, struct maple_enode **right) -{ - char i, j; - unsigned long min = mas->min; - unsigned long max = min; - enum maple_type type = mte_node_type(mas->node); - unsigned long pivot_cnt = mt_pivots[type]; - unsigned long half = mt_slots[type] / 2; - unsigned char data_end = mas_data_end(mas); - - if (mte_is_root(mas->node)) { - i = half; - *left = (struct maple_enode *)mas_next_alloc(mas); - *right = (struct maple_enode *)mas_next_alloc(mas); - goto even_split; - } - - *left = (struct maple_enode *)mas_next_alloc(mas); - for (i = 0; i < data_end; i++) { - max = mte_get_pivot(mas->node, i); - if ((max - min) > 15) { - if (i) - i--; - break; - } - } - - if (i >= data_end) { - *left = mt_mk_node(ma_mnode_ptr(*left), maple_dense); - if (mas->last >= mas->min + mt_max[type]) { - *right = (struct maple_enode *)mas_next_alloc(mas); - *right = mt_mk_node(ma_mnode_ptr(*right), type); - } - if (!i) - i = mt_max[type]; - return i; - } - - *right = (struct maple_enode *)mas_next_alloc(mas); - if (i >= half) { - *left = mt_mk_node(ma_mnode_ptr(*left), maple_dense); - *right = mt_mk_node(ma_mnode_ptr(*right), type); - return i; - } - - if (data_end < pivot_cnt) - max = mte_get_pivot(mas->node, data_end); - else - max = mas->max; - - j = data_end; - do { - j--; - min = mte_get_pivot(mas->node, j); - if ((max - min) > 15) { - j++; - break; - } - } while (j > 0); - - if (data_end - j >= half) { - *left = mt_mk_node(ma_mnode_ptr(*left), type); - *right = mt_mk_node(ma_mnode_ptr(*right), maple_dense); - return j; - } -even_split: - *left = mt_mk_node(ma_mnode_ptr(*left), type); - *right = mt_mk_node(ma_mnode_ptr(*right), type); - - return i > 2 ? i : half - 1; -} - static inline unsigned long mas_leaf_max_gap(struct ma_state *mas) { enum maple_type mt = mte_node_type(mas->node); @@ -2085,21 +1472,6 @@ static inline void mas_gap_link(struct ma_state *mas, struct maple_enode *parent mte_set_gap(parent, slot, gap); mas->max = max; } -static inline void mas_link(struct ma_state *mas, struct maple_enode *new, - struct maple_enode *parent, unsigned char slot, - unsigned long pivot, enum maple_type type) -{ - unsigned char pivot_cnt = mt_pivots[type]; - - mte_set_parent(new, parent, slot); - if (slot < pivot_cnt) - mte_set_pivot(parent, slot, pivot); - - mte_set_rcu_slot(parent, slot, new); - if (!mte_is_leaf(new)) - mas_adopt_children(mas, new); - -} static inline enum maple_type mas_ptype_leaf(struct ma_state *mas) { enum maple_type pt = mte_node_type(mas->node); @@ -2111,344 +1483,7 @@ static inline enum maple_type mas_ptype_leaf(struct ma_state *mas) return maple_leaf_64; } } -/* - * split late, that is to say.. the parent may be full and need to be split. - * Once we know there is space (we need only a single location), then we can - * continue. - * - * 1. Allocate 3 nodes: left, right, parent - * 2. If it's not root, copy all data from the old parent to the new one and - * leave a hole. - * 3. Calculate the location to split the nodes. - * 4. Figure out the type of the node - * 5. Copy the data to the new nodes - * 6. Link in the nodes - * 7. replace old_parent - * 8. set up ma_state for return. - * - */ -static inline int mas_split(struct ma_state *mas, unsigned char slot, - bool active, unsigned char entry_cnt, void *entry) -{ - struct maple_enode *full = mas->node; - unsigned char split, p_slot = 0, p_end = 0, link = 0; - struct maple_enode *old_parent; - enum maple_type ptype; // parent type. - enum maple_type type; // split type. - - MA_STATE(parent, mas->tree, mas->index, mas->last); - MA_STATE(left, mas->tree, mas->index, mas->last); - MA_STATE(right, mas->tree, mas->index, mas->last); - MA_STATE(new_p_mas, mas->tree, mas->index, mas->last); - - type = mte_node_type(mas->node); - if (mte_is_root(mas->node)) { - old_parent = full; - mas_dup_state(&parent, mas); - if (mt_is_alloc(mas->tree)) - ptype = maple_arange_64; - else - ptype = maple_range_64; - p_slot = 0; - } else { - unsigned long last_pivot; - unsigned char coalesce; - - p_slot = mte_parent_slot(mas->node); - mas_dup_state(&parent, mas); - mas_ascend(&parent); - old_parent = parent.node; - ptype = mas_parent_enum(mas, mas->node); - p_end = _mas_data_end(&parent, ptype, &last_pivot); - if (p_end - coalesce >= mt_slots[ptype] - 1) { - /* Must split the parent */ - mas_dup_state(mas, &parent); - split = mas_split(mas, p_slot, active, - p_end - coalesce + 1, entry); - if (mas_is_err(mas)) - return 0; - - mas_dup_state(&parent, mas); - ptype = mte_node_type(mas->node); - for (p_slot = 0; p_slot < mt_slots[ptype];p_slot++) { - if (mte_to_node(mas_get_rcu_slot(mas, p_slot)) == - mte_to_node(full)) - break; - } - mas_set_slot(&parent, p_slot); - } - ptype = mas_parent_enum(mas, mas->node); - p_end = mas_data_end(&parent); - mas_dup_state(mas, &parent); - mas_set_slot(mas, p_slot); - mas_descend(mas); - } - - mas_node_cnt(mas, 4); - if (mas_is_err(mas)) - return 0; - - // Allocations. - mas_dup_state(&new_p_mas, &parent); - new_p_mas.node = mt_mk_node(mas_next_alloc(mas), ptype); - - // Copy grand parent to the parent, including slot encoding. - mas_mn(&new_p_mas)->parent = mas_mn(&parent)->parent; - - mas_dup_state(&left, mas); - mas_dup_state(&right, mas); - left.node = mt_mk_node(ma_mnode_ptr(mas_next_alloc(mas)), type); - right.node = mt_mk_node(ma_mnode_ptr(mas_next_alloc(mas)), type); - - mte_set_parent(left.node, new_p_mas.node, p_slot); - mte_set_parent(right.node, new_p_mas.node, p_slot+1); - // split the data into left & right and do the insert. - split = mas_append_split(&left, &right, mas, slot, entry, active); - - // Copy the parent data up to p_slot - 1. - if (!mte_is_root(full) && p_slot) - link = mas_append(&new_p_mas, &parent, 0, p_slot - 1); - - // left will be placed in link, not p_slot as coalescing may occur. - mas_link(mas, left.node, new_p_mas.node, link, left.max, ptype); - - // right will be placed in link + 1; - mas_link(mas, right.node, new_p_mas.node, link + 1, - right.max, ptype); - - // Append data from p_slot + 1 to the end. - if (!mte_is_root(full) && (p_slot + 1 <= p_end)) - mas_append(&new_p_mas, &parent, p_slot + 1, p_end); - - // Update encoded slots in children - mas_adopt_children(&new_p_mas, new_p_mas.node); - - // Replace the parent node & free the old parent. - _mas_replace(&new_p_mas, active, true); - - if (mt_is_alloc(mas->tree)) - mas_update_gap(&new_p_mas, false); - - // Set up the ma_state for the return. Point to the correct node for - // the insert or subsequent split. - if (mas->index <= left.max) { - mas_dup_state(mas, &left); - p_slot += 1; - } else { - mas_dup_state(mas, &right); - p_slot += 2; - } - - // Free the full node, this may have happened in _mas_replace - if (old_parent != full) { // not root? - if (!active) - mas_push_node(mas, full); - else - mte_free(full); - } - - if (mt_is_alloc(mas->tree)) { - mas_update_gap(&left, false); - mas_update_gap(&right, false); - } - - return split; -} - -/* Private - * - * When inserting into non-leaf nodes in _mas_insert, a type is needed. - * - * Try to determine that type here. - */ -static inline enum maple_type mas_determine_type(struct ma_state *mas, - unsigned long min, unsigned char slot) -{ - struct maple_enode *sibling; - unsigned char sibling_slot = slot; - enum maple_type stype, mt = mas_ptype_leaf(mas); - - if (slot > 0) - sibling_slot -= 1; - else - sibling_slot += 1; - sibling = mas_get_rcu_slot(mas, sibling_slot); - if (!sibling) - return mt; - - stype = mte_node_type(sibling); - if (mt_max[stype] >= min - mas->index) - return stype; - - return mt; -} - -/** Private - * mas_may_move_gap() - May move the gap to the proceeding node. - * - * 1. Check back for a gap and move it - * 2. Check front for a gap. - * Ensure we cover the scenarios: - * 3. There is an empty node due to allocation failures - Move the gap wherever - * it can go and free this node. - * 4. There is a gap at the back and front of a node. - * - */ -static inline void mas_rebalance(struct ma_state *mas); -static inline void mas_move_gap_fwd(struct ma_state *mas, struct ma_state *curr, - unsigned long end, unsigned char new_end, - struct ma_state *next, unsigned char next_start, - bool empty) -{ - unsigned long last_piv = mas_get_safe_pivot(curr, new_end); - unsigned char slot = 0; - - MA_STATE(parent, mas->tree, mas->index, mas->last); - - if (empty) { - last_piv = --curr->min; - } else { - while (new_end++ != end) { - if (new_end < mt_pivot_count(curr->node)) - mte_set_pivot(curr->node, new_end, last_piv); - // The location storing these values has moved. - // FIXME: This doesn't exist. -// mte_set_rcu_slot(curr->node, new_end, XA_RETRY_ENTRY); - } - - } - if (curr->node == mas->node) - mas->max = last_piv; - else - mas->min = last_piv + 1; - - next->min = last_piv + 1; - curr->max = last_piv; - if (next_start) { - unsigned char next_end = 0; - MA_STATE(new, mas->tree, mas->index, mas->last); - - mas_dup_state(&new, next); - next_end = mas_data_end(next); - new.node = mt_mk_node(mas_next_alloc(mas), - mte_node_type(next->node)); - mas_mn(&new)->parent = mas_mn(next)->parent; - new.min = last_piv + 1; - mas_append(&new, next, 0, next_end); - mas_dup_state(next, &new); - mas_replace(&new); - } - - mas_set_slot(next, next_start); - mas_shift_pivot(curr, next, last_piv); - - if (empty) { - slot = mte_parent_slot(curr->node); - mas_dup_state(&parent, curr); - mas_ascend(&parent); - // FIXME: What do we do here? - //mte_set_rcu_slot(parent.node, slot, XA_RETRY_ENTRY); - mas_set_safe_pivot(&parent, slot, last_piv); - if (mt_is_alloc(mas->tree)) - mte_set_gap(parent.node, slot, 0); - } - - if (mt_is_alloc(mas->tree)) { - mas_update_gap(curr, true); - mas_update_gap(next, true); - } - - if (empty) { - mte_free(curr->node); - mas_dup_state(mas, next); - } -} - -static inline bool mas_move_gap_swap(struct ma_state *curr, - struct ma_state *next) -{ - mas_dup_state(next, curr); // make next == curr - mas_set_slot(curr, 0); - mas_prev(curr, 0); - if (mas_is_none(curr)) - return false; - - return true; -} -static inline void mas_may_move_gap(struct ma_state *mas) -{ - - unsigned long last_piv; - unsigned char end; - unsigned char new_end; - unsigned char next_start = 0; - void *entry = NULL; - void *next_entry = NULL; - - // node that starts with NULL - MA_STATE(next, mas->tree, mas->index, mas->last); - // node that ends with NULL - MA_STATE(curr, mas->tree, mas->index, mas->last); - MA_STATE(tmp, mas->tree, mas->index, mas->last); - - if (mte_is_root(mas->node)) - return; - mas_dup_state(&next, mas); - mas_dup_state(&curr, mas); - mas_dup_state(&tmp, mas); - mas_set_slot(&next, mt_slot_count(next.node) - 1); - mas_next(&next, ULONG_MAX); - - // Check both the gap from curr -> next and prev -> curr. - // First, check curr -> next, then redefine next = curr and curr -> prev - do { - bool empty = false; - next_start = 0; - - if (mas_is_none(&next)) - continue; - - /* Start by checking the back of the current node. */ - end = _mas_data_end(&curr, mte_node_type(curr.node), &last_piv); - new_end = end; - do { - entry = mas_get_rcu_slot(&curr, new_end); - if (entry && !xa_is_deleted(entry)) - break; - } while (new_end--); - - if (new_end == U8_MAX) { - // underflow. - new_end = 0; - empty = true; - } - - if (!empty && end == new_end) // no gap at back. - continue; - - next_entry = mas_get_rcu_slot(&next, next_start); - while ((xa_is_retry(next_entry)) && - (next_start < mt_slot_count(next.node) - 1)) { - next_entry = mas_get_rcu_slot(&next, ++next_start); - } - - if (next_entry) - continue; // Next does not start with null. - - if (next_start) { - mas_dup_state(&tmp, mas); - mas_node_cnt(mas, 1); - if (mas_is_err(mas)) { - mas_dup_state(mas, &tmp); - continue; - } - } - - mas_move_gap_fwd(mas, &curr, end, new_end, &next, next_start, empty); - - } while ((curr.node == mas->node) && (mas_move_gap_swap(&curr, &next))); -} #define MAPLE_BIG_NODE_SLOTS (MAPLE_NODE_SLOTS + 1) struct maple_big_node { struct maple_pnode *parent; @@ -4186,414 +3221,6 @@ void *mas_prev(struct ma_state *mas, unsigned long min) } EXPORT_SYMBOL_GPL(mas_prev); -/** Private - * - */ -static inline void mas_coalesce_root(struct ma_state *mas) -{ - struct maple_enode *this_enode = mas->node; - enum maple_type this_type = mte_node_type(this_enode); - unsigned long piv; - unsigned long min, max; - unsigned char end = _mas_data_end(mas, this_type, &piv); - - MA_STATE(old_mas, mas->tree, mas->index, mas->last); - - if (end > mt_min_slots[this_type] - 1) - return; - - /* Check for a single entry in the root node. - * 1. 0-oo => node - * 2. slot count == coalesce - * 3. one entry and one null. - */ - if (end == 1 && !mte_get_rcu_slot(this_enode, 1, mas->tree)) { - unsigned long piv; - - min = mas->min; - max = mas->max; - mas_set_slot(mas, 0); - piv = mas_first_node(mas, ULONG_MAX); - if (mte_is_leaf(this_enode)) { - if (!piv) { - void *entry = mte_get_rcu_slot(this_enode, - mas_get_slot(mas), mas->tree); - - rcu_assign_pointer(mas->tree->ma_root, - entry); - mte_free(this_enode); - return; - } - // coalesce the node.. - mas->min = min; - mas->max = max; - mas->node = this_enode; - goto coalesce; - } else if (mas_is_none(mas)) { - /* allocation failed to create a leaf for this empty - * node. - */ - rcu_assign_pointer(mas->tree->ma_root, NULL); - mte_free(this_enode); - return; - } - /* it's not a leaf, remove a level from the tree. */ - goto remove_level; - } else if (end <= mt_min_slots[this_type] - 1) { - goto coalesce; // Compact the node. - } - - return; - -coalesce: - mas_dup_state(&old_mas, mas); - mas_node_cnt(mas, 1); - if (mas_is_err(mas)) - return; - - mas->node = mt_mk_node(mas_next_alloc(mas), this_type); - mas_append(mas, &old_mas, 0, end); - - -remove_level: - mas_mn(mas)->parent = mte_to_node(this_enode)->parent; - mas->node = mte_mk_root(mas->node); - mas_replace(mas); -} - -/** Private - * mas_coalesce() - - * - * coalesce completely consumes the right node into this node. - * - */ -static inline bool mas_coalesce(struct ma_state *mas, unsigned char l_end_slot, - unsigned char l_coalesce, enum maple_type l_type, - struct ma_state *r_mas, unsigned char r_end_slot, - struct ma_state *p_mas, unsigned long total_slots) -{ - struct maple_node *mn; - struct maple_enode *this_node = mas->node; - bool free_left = false, alloc_failed = false, empty_left = false; - bool usable_left = false; // Can use left if there isn't dirty slots after the end of data. - int alloc_cnt = 2; - unsigned char r_p_slot = mte_parent_slot(r_mas->node); - - MA_STATE(dst, mas->tree, mas->index, mas->last); - // it is possible that all of the right node can be appended to the - // left. - if (l_end_slot - l_coalesce == 0) { - void *entry = mte_get_rcu_slot(r_mas->node, 0, r_mas->tree); - - if (entry == NULL) { // Can only be null. - empty_left = true; - alloc_cnt = 1; - } - } else if ((mas_get_rcu_slot(mas, l_end_slot + 1) == 0) && - (total_slots + 1 + l_coalesce < mt_slots[l_type])) { - usable_left = true; - alloc_cnt = 1; - } - - mas_node_cnt(mas, alloc_cnt); // ensure we have a node, or allocate one. - if (mas_is_err(mas)) { - if (alloc_cnt > 1) - return false; - - alloc_failed = true; - mas->node = this_node; - } - - if (empty_left) { - //The left can become a skip and the right can take the left - //into the first slot which is empty. - mas_set_safe_pivot(p_mas, mte_parent_slot(mas->node), - mas->min); - // FIXME: Don't reuse nodes, ever. -// mte_set_rcu_slot(p_mas->node, mte_parent_slot(mas->node), -// XA_SKIP_ENTRY); - if (mt_is_alloc(mas->tree)) - mte_set_gap(p_mas->node, mte_parent_slot(mas->node), - 0); - free_left = true; - mte_free(this_node); - mas->node = r_mas->node; - this_node = mas->node; - goto empty_left; - } else if (usable_left) { - goto use_left; - } else { - free_left = true; - mn = mas_next_alloc(mas); - mas_dup_state(&dst, mas); - mn->parent = mas_mn(mas)->parent; - dst.node = mt_mk_node(mn, l_type); - l_end_slot = mas_append(&dst, mas, 0, l_end_slot); - - // If there is no entry or pivot, then set one to avoid a - // first entry in r_mas being incorrect. - if (!l_end_slot && !mte_get_pivot(dst.node, 0)) { - mte_set_pivot(dst.node, 0, mas->max); - l_end_slot++; - } - mas->node = dst.node; - } - - -use_left: - // Copy data to the left node. - mas_append(mas, r_mas, 0, r_end_slot); - - if (!mte_is_leaf(mas->node)) - mas_adopt_children(mas, mas->node); - - // Redirect reads to the new node. - mas_set_safe_pivot(p_mas, mte_parent_slot(mas->node), r_mas->max); - // indicate to skip this slot. - // FIXME: Remove skips. -// mte_set_rcu_slot(p_mas->node, mte_parent_slot(r_mas->node), -// XA_SKIP_ENTRY); - if (mt_is_alloc(mas->tree)) - mte_set_gap(p_mas->node, mte_parent_slot(r_mas->node), 0); - - mte_free(r_mas->node); - -empty_left: - // There is a chance that the left and right node are not next to each - // other and separated by a skip entry. - while(mte_parent_slot(mas->node) < --r_p_slot) - mas_set_safe_pivot(p_mas, r_p_slot, r_mas->max); - - mas->max = r_mas->max; // update limits. - - // Remove the skip entry if the allocation was okay. - if (!alloc_failed) { - mas_dup_state(&dst, p_mas); - mn = mas_next_alloc(mas); - dst.node = mt_mk_node(mn, mte_node_type(p_mas->node)); - mas_append(&dst, p_mas, 0, mas_data_end(p_mas)); - mte_to_node(dst.node)->parent = mas_mn(p_mas)->parent; - p_mas->node = dst.node; - mas_replace(p_mas); - mas_mn(mas)->parent = mte_to_node(this_node)->parent; - } - - return free_left; -} -/* Private - * mas_rebalance_node() - rebalance a single node. - * Returns: true if rebalancing was necessary. - */ -static inline bool mas_rebalance_node(struct ma_state *mas) -{ - unsigned char l_end_slot, l_coalesce, r_end_slot, r_coalesce; - unsigned char l_p_slot; // parent slot of left node - unsigned char r_p_slot; // parent slot of right node. - unsigned char total_slots; - int copy_count; - unsigned long l_end_piv, r_end_piv; - enum maple_type l_type, r_type; - bool try_anyways = false; - bool free; - bool ret = false; - - MA_STATE(r_mas, mas->tree, mas->index, mas->last); // right state - MA_STATE(p_mas, mas->tree, mas->index, mas->last); // parent state - MA_STATE(src_mas, mas->tree, mas->index, mas->last); - - printk("Rebalance %p\n", mas_mn(mas)); - -start: - free = false; - l_type = mte_node_type(mas->node); - if (mte_is_root(mas->node)) { - mas_coalesce_root(mas); // height reduction and such. - return false; - } - - mas_dup_state(&p_mas, mas); - mas_ascend(&p_mas); - l_p_slot = mte_parent_slot(mas->node); - l_end_slot = _mas_data_end(mas, l_type, &l_end_piv); - if (!try_anyways && (l_end_slot >= mt_min_slots[l_type])) { - goto no_rebalancing; // Everything's perfectly all right now. - } - - try_anyways = false; - - // Make sure there is a right node. - mas_dup_state(&r_mas, &p_mas); - mas_set_slot(&r_mas, l_p_slot + 1); - if (!mas_next_nentry(&r_mas, ULONG_MAX, &r_end_piv)) { - // Right-most node coalescing. - mas_dup_state(&r_mas, &p_mas); - mas_set_slot(&r_mas, l_p_slot); - if (!mas_prev_nentry(&r_mas, 0, &r_end_piv)) { - // Single entry in the parent. - printk("%u and %u\n", l_end_slot, l_coalesce); - if (l_end_slot <= l_coalesce) { // Single entry is empty. - printk("Empty\n"); - free = true; - } else if (l_end_slot == l_coalesce && - mas->max == ULONG_MAX) { - // Possible single entry of null for ULONG_MAX - free = true; - } - printk("Single entry\n"); - goto single_entry; - } - // Not really r_mas, previous node is left. - mas_descend(&r_mas); - r_type = mte_node_type(r_mas.node); - r_end_slot = _mas_data_end(&r_mas, r_type, &r_end_piv); - if (r_end_slot - r_coalesce + l_end_slot - l_coalesce + 2 - < mt_slots[l_type]) { - // Force a coalesce of these nodes - try_anyways = true; - mas_dup_state(mas, &r_mas); - goto start; // restart with new left. - } - // right-most node is okay to be sparse. - goto no_rebalancing; - } - mas_descend(&r_mas); - - // We have a left and a right, check if they can be coalesced. - r_type = mte_node_type(r_mas.node); // not for racing. - r_end_slot = _mas_data_end(&r_mas, r_type, &r_end_piv); - r_p_slot = mte_parent_slot(r_mas.node); - printk("Taking from %p\n", mas_mn(&r_mas)); - - // end_slot values don't count slot 0, so add one. - total_slots = l_end_slot + 1 - l_coalesce; - total_slots += r_end_slot + 1 - r_coalesce; - if (l_end_piv + 1 != r_mas.min) - total_slots++; // will need a null entry between the two. - - mas_dup_state(&p_mas, mas); - mas_ascend(&p_mas); - - if (total_slots <= mt_slots[l_type]) { - // Totally consume the right node; coalesce. - printk("Coalesced\n"); - free = mas_coalesce(mas, l_end_slot, l_coalesce, l_type, - &r_mas, r_end_slot, &p_mas, total_slots); - - if (mas_is_err(mas)) - return ret; - - ret = true; - goto coalesced; - } - - // Rebalance between mas and r_mas nodes. - mas_node_cnt(mas, 1); // Try to allocate. - if (mas_is_err(mas)) { - // Allocation failed, we could try to append as much - // as possible here? - return ret; - } - - free = true; // free parent.node after the operation. - mas_dup_state(&src_mas, mas); - mas->node = mt_mk_node(mas_next_alloc(mas), l_type); - mas_mn(mas)->parent = mas_mn(&src_mas)->parent; - mas_append(mas, &src_mas, 0, l_end_slot); - - - // Put 1/2 of the contents into the left if not all of them can fit. - copy_count = (total_slots / 2) - (l_end_slot + 1 - l_coalesce); - printk("Copy count is %u\n", copy_count); - mas_append(mas, &r_mas, 0, copy_count); - // There is a chance that the left and right node are not next to each - // other and separated by a skip entry. - while(l_p_slot < --r_p_slot) - mas_set_safe_pivot(&p_mas, r_p_slot, mas->max); - - /* All relocations *must* be committed before removing real data */ - wmb(); - do { - // relocated. - printk("Set %p[%u] to retry\n", mas_mn(&r_mas), copy_count); -//mte_set_rcu_slot(r_mas.node, copy_count, XA_RETRY_ENTRY); - //FIXME .. - if (mt_is_alloc(r_mas.tree)) - mte_set_gap(r_mas.node, copy_count, 0); - mte_set_pivot(r_mas.node, copy_count, mas->max); - - } while (copy_count-- > 0); - - if (mt_is_alloc(mas->tree)) { - mas_update_gap(mas, true); - mas_update_gap(&r_mas, true); - } - - ret = true; - -coalesced: - if (!mte_is_leaf(mas->node)) - mas_adopt_children(mas, mas->node); - - if (free) - mas_replace(mas); - - mas_dup_state(&p_mas, mas); - l_p_slot = mte_parent_slot(mas->node); //may have changed. - mas_set_slot(&p_mas, l_p_slot); - mas_ascend(&p_mas); - mas_set_slot(&p_mas, l_p_slot); - printk("Set %p[%u]\n", mas_mn(&p_mas), l_p_slot); - mas_set_safe_pivot(&p_mas, l_p_slot, mas->max); - - if (mt_is_alloc(mas->tree)) - mas_update_gap(mas, true); -single_entry: - - - if (free && _ma_is_root(mte_parent(mas->node))) { - mas_coalesce_root(&p_mas); - mas_dup_state(mas, &p_mas); - } - -no_rebalancing: - mt_dump(mas->tree); - return ret; -} - -/** Private - * mas_rebalance() - - * - * rebalance moves data from the node to the right to this node if the - * low watermark of data is not met. It also calls coalesce if the right data - * can fully be moved to the left. - * - */ -static inline void mas_rebalance(struct ma_state *mas) -{ - bool at_root = false; - - do { - if (!mas_rebalance_node(mas)) - break; // We're all done here. - - if (mas_is_err(mas)) - return; - - // Check parent for rebalancing. - if (mte_is_root(mas->node)) - break; - - mas_ascend(mas); - } while (!at_root); - - mas_rebalance_gaps(mas); - if (mas_is_err(mas)) - return; - - mas->node = MAS_START; - _mas_walk(mas); // return to the updated location in the tree. -} - static inline bool _mas_rev_awalk(struct ma_state *mas, unsigned long size) { enum maple_type type; -- 2.50.1