From 6d2693c690423ce0982c21a82c89d2f90b1ddc7e Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Fri, 15 Mar 2019 16:01:22 -0400 Subject: [PATCH] maple_tree: Add maple_tree alloc support for gaps. Start populating gaps with values Remove the maple_aleaf_64 type and use regular maple_leaf_64. Rework pivot calculations to be more straight forward. Don't use dense nodes in the root node to avoid having a dense node as the right-most node. Signed-off-by: Liam R. Howlett --- include/linux/maple_tree.h | 1 - lib/maple_tree.c | 238 ++++++++++++++++++++++++++++--------- lib/test_maple_tree.c | 2 +- 3 files changed, 185 insertions(+), 56 deletions(-) diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h index 0dc1c5e5da86..cde19ec723fa 100644 --- a/include/linux/maple_tree.h +++ b/include/linux/maple_tree.h @@ -142,7 +142,6 @@ enum maple_type { maple_leaf_16, maple_leaf_32, maple_leaf_64, - maple_aleaf_64, maple_range_16, maple_range_32, maple_range_64, diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 49980c400c22..1444bf186ceb 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -27,7 +27,6 @@ unsigned long mt_max[] = { [maple_leaf_16] = (1UL << 16) - 1, [maple_leaf_32] = UINT_MAX, [maple_leaf_64] = ULONG_MAX, - [maple_aleaf_64] = ULONG_MAX, [maple_range_16] = (1UL << 16) - 1, [maple_range_32] = UINT_MAX, [maple_range_64] = ULONG_MAX, @@ -47,7 +46,6 @@ unsigned char mt_slots[] = { [maple_leaf_16] = MAPLE_RANGE16_SLOTS, [maple_leaf_32] = MAPLE_RANGE32_SLOTS, [maple_leaf_64] = MAPLE_RANGE64_SLOTS, - [maple_aleaf_64] = MAPLE_ARANGE64_SLOTS, [maple_range_16] = MAPLE_RANGE16_SLOTS, [maple_range_32] = MAPLE_RANGE32_SLOTS, [maple_range_64] = MAPLE_RANGE64_SLOTS, @@ -65,7 +63,6 @@ unsigned char mt_pivots[] = { [maple_leaf_16] = MAPLE_RANGE16_SLOTS - 1, [maple_leaf_32] = MAPLE_RANGE32_SLOTS - 1, [maple_leaf_64] = MAPLE_RANGE64_SLOTS - 1, - [maple_aleaf_64] = MAPLE_ARANGE64_SLOTS - 1, [maple_range_16] = MAPLE_RANGE16_SLOTS - 1, [maple_range_32] = MAPLE_RANGE32_SLOTS - 1, [maple_range_64] = MAPLE_RANGE64_SLOTS - 1, @@ -333,7 +330,6 @@ static inline unsigned long _ma_get_pivot(const struct maple_enode *mn, { switch (type) { case maple_arange_64: - case maple_aleaf_64: return mt_to_node(mn)->ma64.pivot[slot]; case maple_range_64: case maple_leaf_64: @@ -378,7 +374,6 @@ static inline void ma_set_pivot(struct maple_enode *mn, unsigned char slot, (&mt_to_node(mn)->mr64)->pivot[slot] = val; break; case maple_arange_64: - case maple_aleaf_64: (&mt_to_node(mn)->ma64)->pivot[slot] = val; case maple_dense: break; @@ -427,7 +422,6 @@ static inline struct maple_enode *_ma_get_rcu_slot(const struct maple_enode *mn, case maple_dense: return rcu_dereference(mt_to_node(mn)->slot[slot]); case maple_arange_64: - case maple_aleaf_64: return rcu_dereference(mt_to_node(mn)->ma64.slot[slot]); case maple_sparse_6: return rcu_dereference(mt_to_node(mn)->ms6.slot[slot]); @@ -495,7 +489,6 @@ static inline void ma_set_rcu_slot(const struct maple_enode *mn, RCU_INIT_POINTER(mt_to_node(mn)->mr64.slot[slot], val); break; case maple_arange_64: - case maple_aleaf_64: RCU_INIT_POINTER(mt_to_node(mn)->ma64.slot[slot], val); break; } @@ -520,7 +513,6 @@ static inline void ma_update_rcu_slot(const struct maple_enode *mn, rcu_assign_pointer(mt_to_node(mn)->slot[slot], val); break; case maple_arange_64: - case maple_aleaf_64: rcu_assign_pointer(mt_to_node(mn)->ma64.slot[slot], val); break; case maple_sparse_6: @@ -552,16 +544,21 @@ static inline void ma_update_rcu_slot(const struct maple_enode *mn, } } -static inline unsigned long ma_get_gap(const struct maple_enode *mn, +static inline unsigned long _ma_get_gap(const struct maple_node *mn, unsigned char gap, enum maple_type type) { switch (type) { case maple_arange_64: - return mt_to_node(mn)->ma64.gap[gap]; + return mn->ma64.gap[gap]; default: return 0; } } +static inline unsigned long ma_get_gap(const struct maple_enode *mn, + unsigned char gap) +{ + return _ma_get_gap(mt_to_node(mn), gap, mt_node_type(mn)); +} static inline void ma_set_gap(const struct maple_enode *mn, unsigned char gap, unsigned long val) { @@ -577,7 +574,7 @@ static inline void ma_set_gap(const struct maple_enode *mn, static inline void ma_cp_gap(struct maple_enode *dst, unsigned char dloc, struct maple_enode *src, unsigned long sloc) { - ma_set_gap(dst, dloc, ma_get_gap(src, sloc, mt_node_type(src))); + ma_set_gap(dst, dloc, ma_get_gap(src, sloc)); } static inline void mas_update_limits(struct ma_state *ms, unsigned char slot, @@ -586,7 +583,7 @@ static inline void mas_update_limits(struct ma_state *ms, unsigned char slot, if (slot > 0) ms->min = _ma_get_pivot(ms->node, slot - 1, type) + 1; - if (slot < mt_slots[type] - 1) + if (slot < mt_pivots[type]) ms->max = _ma_get_pivot(ms->node, slot, type); } static inline void ma_encoded_parent(struct ma_state *mas) @@ -609,6 +606,7 @@ static inline void ma_encoded_parent(struct ma_state *mas) mas->node = mt_mk_node(gparent, mt_parent_enum(mas, parent)); ma_set_slot(mas, slot); mas_update_limits(mas, slot, mt_parent_enum(mas, parent)); + //mas->node = ma_get_rcu_slot(mas->node, slot); mas->node = ma_get_rcu_slot(mas->node, slot); return; } @@ -752,7 +750,7 @@ static inline unsigned char ma_data_end(const struct maple_enode *mn, return data_end; } -// FIXME: don't use the same pointers for maple_node and maple_enode + static inline unsigned char ma_calc_split(struct ma_state *mas, struct maple_enode **left, struct maple_enode **right) { @@ -764,6 +762,13 @@ static inline unsigned char ma_calc_split(struct ma_state *mas, unsigned long half = mt_slots[type] / 2; unsigned char data_end = ma_data_end(mas->node, type); + if (ma_is_root(mas->node)) { + i = half; + *left = (struct maple_enode*)ma_next_alloc(mas); + *right = (struct maple_enode*)ma_next_alloc(mas); + goto even_split; + } + *left = (struct maple_enode*)ma_next_alloc(mas); for (i = 0; i < data_end; i++) { max = ma_get_pivot(mas->node, i); @@ -805,10 +810,10 @@ static inline unsigned char ma_calc_split(struct ma_state *mas, *left = mt_mk_node(ma_mnode_ptr(*left), type); *right = mt_mk_node(ma_mnode_ptr(*right), maple_dense); return j; - } else { - *left = mt_mk_node(ma_mnode_ptr(*left), type); - *right = mt_mk_node(ma_mnode_ptr(*right), type); } +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; } @@ -852,6 +857,105 @@ static inline void ma_dense_cp(struct ma_state *mas, struct ma_cp *cp) } } +static inline unsigned long ma_leaf_max_gap(struct ma_state *mas) +{ + enum maple_type mt = mt_node_type(mas->node); + unsigned long max_gap = 0; + unsigned long gap = 0; + unsigned long pstart, pend; + + + if (mt == maple_dense) { + for (int i = 0; i < mt_slot_count(mas->node); i++) { + if (ma_get_rcu_slot(mas->node, i)) { + if (gap > max_gap) + max_gap = gap; + gap = 0; + } else { + gap++; + } + } + if (gap > max_gap) + max_gap = gap; + goto done; + } + + pstart = mas->min; + for (int i = 0; i < mt_slots[mt]; i++) { + if (i < mt_pivots[mt]) + pend = ma_get_pivot(mas->node, i); + else + pend = mas->max; + + gap = (pend ? pend : mas->max) - pstart; + if ((gap > max_gap) && !ma_get_rcu_slot(mas->node, i)) + max_gap = gap; + + if (!pend) + break; + + pstart = pend; + } +done: + return max_gap; + +} +static inline unsigned long ma_max_gap(struct ma_state *mas) +{ + unsigned long max_gap = 0; + for (int i = 0; i < mt_slot_count(mas->node); i++) { + unsigned long gap; + gap = ma_get_gap(mas->node, i); + if ( gap > max_gap) + max_gap = gap; + } + return max_gap; +} +static inline void ma_parent_gap(struct ma_state *mas, unsigned char slot, + unsigned long new) +{ + unsigned long max_gap = 0; + + if (ma_is_root(mas->node)) { + ma_set_gap(mas->node, slot, new); + return; + } + + ma_encoded_parent(mas); + max_gap = ma_max_gap(mas); + ma_set_gap(mas->node, slot, new); + + if(max_gap < new) { + unsigned char pslot = mt_parent_slot(mas->node); + ma_parent_gap(mas, pslot, new); + } +} +/* Private + */ +static inline void ma_update_gap(struct ma_state *mas) +{ + unsigned char pslot; + unsigned long p_gap, max_gap = 0; + + + if (!mt_is_leaf(mas->node)) + return; + + if (ma_is_root(mas->node)) + return; + + /* Get the largest gap in this leaf and check it against the reported + * largest. + */ + max_gap = ma_leaf_max_gap(mas); + pslot = mt_parent_slot(mas->node); + p_gap = _ma_get_gap(mt_parent(mas->node), pslot, + mt_parent_enum(mas, mas->node)); + if (p_gap != max_gap) + ma_parent_gap(mas, pslot, max_gap); +} + + static inline void ma_copy(struct ma_state *mas, struct ma_cp *cp) { unsigned char sloc = cp->src_start; // src location @@ -888,7 +992,7 @@ static inline void ma_copy(struct ma_state *mas, struct ma_cp *cp) ma_set_pivot(cp->dst, dloc, mas->max); } - if (mt_is_alloc(mas->tree)) + if (mt_node_type(cp->dst) == maple_arange_64) ma_cp_gap(cp->dst, dloc, cp->src, sloc); ma_cp_rcu_slot(cp->dst, dloc++, cp->src, sloc++); } @@ -986,6 +1090,22 @@ static inline void mas_partial_copy(struct ma_state *mas, return; } +static inline void ma_gap_link(struct ma_state *mas, struct maple_enode *parent, + unsigned char slot, unsigned long pivot) +{ + unsigned long gap; + + if (slot) + mas->min = ma_get_pivot(parent, slot - 1) + 1; + + mas->max = pivot; + if (!mt_is_leaf(mas->node)) + gap = ma_max_gap(mas); + else + gap = ma_leaf_max_gap(mas); + + ma_set_gap(parent, slot, gap); +} static inline void ma_link(struct maple_enode *new, struct maple_enode *parent, unsigned char slot, unsigned long pivot, enum maple_type type) { @@ -1082,33 +1202,30 @@ static inline int ma_split(struct ma_state *mas, unsigned char slot) // the node type for the children types. // Node types must be set to copy data into them. ma_split_data(mas, left, right, split); - - - if (right) { - // Set up the link to the right in the new parent - if (mt_node_type(right) == maple_dense) { - pivot = ma_get_pivot(mas->node, split) - + mt_node_max(right) - 1; - } - else if (ma_is_root(full)) { - pivot = mt_node_max(mas->node); - } - else { - pivot = ma_get_pivot(old_parent, p_slot); - } - - ma_link(right, new_parent, p_slot + 1, pivot, ptype); + pivot = ma_get_pivot(left, split); + } else { + pivot = mt_node_max(left); + if (p_slot) + pivot += ma_get_pivot(new_parent, p_slot - 1); + else + pivot += mas->min; } - // Set up the link to the left in the new parent - if (!right) - pivot = mt_node_max(left) - 1; - else if (split < slot_cnt - 1) - pivot = ma_get_pivot(mas->node, split); - else - pivot = ma_get_pivot(left, split - 1); ma_link(left, new_parent, p_slot, pivot, ptype); + if (right) + ma_link(right, new_parent, p_slot + 1, mas->max, ptype); + + if (mt_is_alloc(mas->tree)) { + if (right) { + unsigned long min = mas->min; + mas->node = right; + ma_gap_link(mas, new_parent, p_slot + 1, mas->max); + mas->min = min; + } + mas->node = left; + ma_gap_link(mas, new_parent, p_slot, pivot); + } // Copy grand parent to the parent, including slot encoding. mt_to_node(new_parent)->parent = mt_to_node(old_parent)->parent; @@ -1116,17 +1233,23 @@ static inline int ma_split(struct ma_state *mas, unsigned char slot) ma_adopt_children(new_parent); // Set up maple state to replace the parent node in the grandparent. mas->node = new_parent; + // Replace the parent node & free the old parent. mt_replace(mas); // Set up the ma_state for the return. Point to the correct node for // the insert or subsequent split. + if (!mt_is_alloc(mas->tree)) + p_slot = slot - p_slot; + if (mas->index <= pivot) { mas->node = left; - p_slot = slot - p_slot + 1; + p_slot += 1; + mas->max = pivot; } else { mas->node = right; - p_slot = slot - p_slot + 2; + p_slot += 2; + mas->min = pivot; } if (mas->index > mt_node_max(mas->node) + mas->min) { @@ -1138,6 +1261,7 @@ static inline int ma_split(struct ma_state *mas, unsigned char slot) if (old_parent != full) mt_free(mt_to_node(full)); + return split; } @@ -1146,7 +1270,6 @@ static inline enum maple_type ma_ptype_leaf(struct ma_state *mas) { switch (pt) { case maple_arange_64: - return maple_aleaf_64; case maple_range_64: default: return maple_leaf_64; @@ -1213,8 +1336,9 @@ static inline int _ma_insert(struct ma_state *mas, void *entry, do ma_update_rcu_slot(mas->node, min++, entry); while(min < max); - - return max - min; + if (mt_is_alloc(mas->tree)) + ma_update_gap(mas); + return max - min + 1; } /* Calculate the range of the slot */ @@ -1255,9 +1379,6 @@ static inline int _ma_insert(struct ma_state *mas, void *entry, unsigned long o_min = mas->min; unsigned long o_max = mas->max; - if (mt_is_alloc(mas->tree)) - mt = maple_aleaf_64; - mas_node_cnt(mas, 1); if (mas_is_err(mas)) return 0; @@ -1308,6 +1429,13 @@ static inline int _ma_insert(struct ma_state *mas, void *entry, wmb(); ma_set_pivot(mas->node, slot, mas->index - 1); + if (mt_is_alloc(mas->tree)) { + unsigned long gap = mas->min; + if (slot > 0) + gap = ma_get_pivot(mas->node, slot - 1); + gap = (mas->index - 1) - gap; + ma_set_gap(mas->node, slot, gap); + } slot += 2; ret = 2; } else { @@ -1330,9 +1458,14 @@ static inline int _ma_insert(struct ma_state *mas, void *entry, cp.dst_end = n_end; ma_copy(mas, &cp); + //mas->max = mas->last; + if (p_mn != mas->node) mt_replace(mas); + if (mt_is_alloc(mas->tree)) + ma_update_gap(mas); + return ret; } @@ -1347,8 +1480,6 @@ static inline void ma_root_expand(struct ma_state *ms, void *entry) return; mn = ma_next_alloc(ms); - if (mt_is_alloc(ms->tree)) - mt = maple_aleaf_64; ms->node = mt_mk_node(mn, mt); mn->parent = ma_parent_ptr( ((unsigned long)ms->tree | MA_ROOT_PARENT)); @@ -1823,7 +1954,7 @@ void mt_dump_arange64(void *entry, unsigned long min, unsigned long max, pr_cont(" contents: "); for (i = 0; i < MAPLE_ARANGE64_SLOTS; i++) pr_cont("%lu ", node->gap[i]); - pr_cont(" | "); + pr_cont("| "); for (i = 0; i < MAPLE_ARANGE64_SLOTS - 1; i++) pr_cont("%p %lu ", node->slot[i], node->pivot[i]); pr_cont("%p\n", node->slot[i]); @@ -1866,9 +1997,9 @@ void mt_dump_node(void *entry, unsigned long min, unsigned long max, case maple_dense: pr_cont("\n"); for (i = 0; i < MAPLE_NODE_SLOTS; i++) { + if (min + i > max) + pr_cont("OUT OF RANGE: "); mt_dump_entry(node->slot[i], min + i, min + i); - if (min + i == max) - break; } break; case maple_leaf_64: @@ -1876,7 +2007,6 @@ void mt_dump_node(void *entry, unsigned long min, unsigned long max, mt_dump_range64(entry, min, max, depth); break; case maple_arange_64: - case maple_aleaf_64: mt_dump_arange64(entry, min, max, depth); break; diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c index ad2d4709ca65..2ded74588739 100644 --- a/lib/test_maple_tree.c +++ b/lib/test_maple_tree.c @@ -290,7 +290,7 @@ static noinline void check_alloc_range(struct maple_tree *mt) for (i = 0; i < range_cnt/2; i+=2) { check_insert_range(mt, range[i] >> 12, (range[i + 1] >> 12) - 1, - check_alloc_range); + xa_mk_value(range[i] >> 12)); } -- 2.50.1