From efc18569418bc6e9cb1ed139b9b573ed9e0e6af3 Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Tue, 12 Mar 2019 14:52:59 -0400 Subject: [PATCH] maple_tree: Add initial maple_arange_64 node support. maple_arange_64 is for allocation ranges which need to track gaps in subtrees. This commit does not address tracking the gaps. Signed-off-by: Liam R. Howlett --- include/linux/maple_tree.h | 18 +- lib/maple_tree.c | 339 ++++++++++++++++++++++++++++++------- lib/test_maple_tree.c | 14 +- 3 files changed, 299 insertions(+), 72 deletions(-) diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h index 5481cf0186a7..ca34ecd52e71 100644 --- a/include/linux/maple_tree.h +++ b/include/linux/maple_tree.h @@ -28,6 +28,7 @@ #ifdef CONFIG_64BIT #define MAPLE_NODE_SLOTS 15 /* 128 bytes including ->parent */ #define MAPLE_RANGE64_SLOTS 8 /* 128 bytes */ +#define MAPLE_ARANGE64_SLOTS 5 /* 120 bytes */ #define MAPLE_RANGE32_SLOTS 10 /* 124 bytes */ #define MAPLE_RANGE16_SLOTS 12 /* 126 bytes */ #define MAPLE_SPARSE64_SLOTS 7 /* 120 bytes */ @@ -50,6 +51,13 @@ struct maple_range_64 { u64 pivot[MAPLE_RANGE64_SLOTS - 1]; }; +struct maple_arange_64 { + struct maple_node *parent; + u64 gap[MAPLE_ARANGE64_SLOTS]; + void __rcu *slot[MAPLE_ARANGE64_SLOTS]; + u64 pivot[MAPLE_ARANGE64_SLOTS - 1]; +}; + struct maple_range_32 { struct maple_node *parent; void __rcu *slot[MAPLE_RANGE32_SLOTS]; @@ -109,6 +117,7 @@ struct maple_node { struct rcu_head rcu; }; struct maple_range_64 mr64; + struct maple_arange_64 ma64; struct maple_range_32 mr32; struct maple_range_16 mr16; struct maple_sparse_64 ms64; @@ -131,11 +140,18 @@ enum maple_type { maple_leaf_16, maple_leaf_32, maple_leaf_64, + maple_aleaf_64, maple_range_16, maple_range_32, maple_range_64, + maple_arange_64, }; +/* Flags: + * MAPLE_ALLOC_RANGE - This tree is used to store allocation ranges. Use + * alloc range types (MAPLE_ARANGE_*) + */ +#define MAPLE_ALLOC_RANGE 1 struct maple_tree { spinlock_t ma_lock; unsigned int ma_flags; @@ -154,7 +170,7 @@ struct maple_tree { #define mtree_lock(mt) spin_lock(&mt->ma_lock); #define mtree_unlock(mt) spin_unlock(&mt->ma_lock); -void mtree_init(struct maple_tree *); +void mtree_init(struct maple_tree *, unsigned int ma_flags); void *mtree_load(struct maple_tree *, unsigned long index); int mtree_insert(struct maple_tree *, unsigned long index, void *entry, gfp_t); int mtree_insert_range(struct maple_tree *, unsigned long first, diff --git a/lib/maple_tree.c b/lib/maple_tree.c index f3d02e478122..0ca8195d3f8f 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -26,9 +26,11 @@ 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, + [maple_arange_64] = ULONG_MAX, }; #define mt_node_max(x) mt_max[mt_node_type(x)] @@ -44,9 +46,11 @@ 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, + [maple_arange_64] = MAPLE_ARANGE64_SLOTS, }; #define mt_slot_count(x) mt_slots[mt_node_type(x)] unsigned char mt_pivots[] = { @@ -60,9 +64,11 @@ 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, + [maple_arange_64] = MAPLE_ARANGE64_SLOTS - 1, }; #define mt_pivot_count(x) mt_pivots[mt_node_type(x)] // Functions @@ -169,6 +175,11 @@ static inline bool ma_is_root(struct maple_node *node) return false; } +static inline bool mt_is_alloc(struct maple_tree *mt) +{ + return (mt->ma_flags & MAPLE_ALLOC_RANGE); +} + static inline unsigned int mt_parent_shift(unsigned long parent) { if (!(parent & 2)) @@ -176,12 +187,8 @@ static inline unsigned int mt_parent_shift(unsigned long parent) return 3; } -static inline enum maple_type mt_parent_enum(struct maple_node *node) +static inline enum maple_type mt_parent_range_enum(unsigned long parent) { - unsigned long parent = (unsigned long) mt_to_node(node)->parent; - unsigned long slot_shift = mt_parent_shift(parent); - - parent &= (1 << slot_shift ) - 1; switch (parent) { case 6: return maple_range_64; @@ -193,17 +200,38 @@ static inline enum maple_type mt_parent_enum(struct maple_node *node) return maple_dense; } +static inline enum maple_type mt_parent_alloc_enum(unsigned long parent) +{ + switch (parent) { + case 6: + return maple_arange_64; + } + return maple_dense; +} + +static inline enum maple_type mt_parent_enum(struct ma_state *mas, + struct maple_node *node) +{ + unsigned long parent = (unsigned long) mt_to_node(node)->parent; + unsigned long slot_shift = mt_parent_shift(parent); + + parent &= (1 << slot_shift ) - 1; + if (mt_is_alloc(mas->tree)) + return mt_parent_alloc_enum(parent); + return mt_parent_range_enum(parent); +} + /* Private * * Type is encoded in the node->parent * bit 0: 1 = root, 0 otherwise * bit 1: 0 = range 16, 1 otherwise - * bit 2: 0 = range 32, 1 = range 64 | lowest bit of range_16's slot. + * bit 2: 0 = range 32, 1 = [a]range 64 | lowest bit of range_16's slot. * * Slot number is encoded in the node->parent * range_16, slot number is encoded in bits 2-6 * range_32, slot number is encoded in bits 3-6 - * range_64, slot number is encoded in bits 3-6 + * [a]range_64, slot number is encoded in bits 3-6 */ static inline void mt_set_parent(struct maple_node *node, struct maple_node *parent, unsigned char slot) @@ -215,6 +243,7 @@ static inline void mt_set_parent(struct maple_node *node, switch (mt_node_type(parent)) { case maple_range_64: + case maple_arange_64: type |= 4; /* fallthrough */ case maple_range_32: @@ -298,6 +327,9 @@ static inline unsigned long _ma_get_pivot(const struct maple_node *mn, unsigned char slot, enum maple_type type) { 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: return mt_to_node(mn)->mr64.pivot[slot]; @@ -340,33 +372,36 @@ static inline void ma_set_pivot(struct maple_node *mn, unsigned char slot, case maple_leaf_64: (&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; case maple_sparse_6: - mt_to_node(mn)->ms6.pivot = val; + (&mt_to_node(mn)->ms6)->pivot = val; break; case maple_sparse_9: - mt_to_node(mn)->ms9.pivot[slot] = val; + (&mt_to_node(mn)->ms9)->pivot[slot] = val; break; case maple_sparse_16: - mt_to_node(mn)->ms16.pivot[slot] = val; + (&mt_to_node(mn)->ms16)->pivot[slot] = val; break; case maple_sparse_21: - mt_to_node(mn)->ms21.pivot[slot] = val; + (&mt_to_node(mn)->ms21)->pivot[slot] = val; break; case maple_sparse_32: - mt_to_node(mn)->ms32.pivot[slot] = val; + (&mt_to_node(mn)->ms32)->pivot[slot] = val; break; case maple_sparse_64: - mt_to_node(mn)->ms64.pivot[slot] = val; + (&mt_to_node(mn)->ms64)->pivot[slot] = val; break; case maple_range_16: case maple_leaf_16: - mt_to_node(mn)->mr16.pivot[slot] = val; + (&mt_to_node(mn)->mr16)->pivot[slot] = val; break; case maple_range_32: case maple_leaf_32: - mt_to_node(mn)->mr32.pivot[slot] = val; + (&mt_to_node(mn)->mr32)->pivot[slot] = val; break; } return; @@ -386,6 +421,9 @@ static inline void __rcu *_ma_get_rcu_slot(const struct maple_node *mn, default: 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]); case maple_sparse_9: @@ -451,6 +489,10 @@ static inline void ma_set_rcu_slot(const struct maple_node *mn, case maple_leaf_64: 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; } } static inline void ma_cp_rcu_slot(struct maple_node *dst, @@ -472,6 +514,10 @@ static inline void ma_update_rcu_slot(const struct maple_node *mn, case maple_dense: 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: rcu_assign_pointer(mt_to_node(mn)->ms6.slot[slot], val); break; @@ -500,6 +546,35 @@ static inline void ma_update_rcu_slot(const struct maple_node *mn, break; } } + +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]; + default: + return 0; + } +} +static inline void ma_set_gap(const struct maple_node *mn, + unsigned char gap, unsigned long val) +{ + enum maple_type type = mt_node_type(mn); + switch (type) { + default: + break; + case maple_arange_64: + mt_to_node(mn)->ma64.gap[gap] = val; + break; + } +} +static inline void ma_cp_gap(struct maple_node *dst, + unsigned char dloc, struct maple_node *src, unsigned long sloc) +{ + ma_set_gap(dst, dloc, ma_get_gap(src, sloc, mt_node_type(src))); +} + static inline void mas_update_limits(struct ma_state *ms, unsigned char slot, enum maple_type type) { @@ -522,9 +597,9 @@ static inline void ma_encoded_parent(struct ma_state *mas) gparent = mt_parent(parent); slot = mt_parent_slot(parent); - mas->node = mt_mk_node(gparent, mt_parent_enum(parent)); + mas->node = mt_mk_node(gparent, mt_parent_enum(mas, parent)); ma_set_slot(mas, slot); - mas_update_limits(mas, slot, mt_parent_enum(parent)); + mas_update_limits(mas, slot, mt_parent_enum(mas, parent)); mas->node = ma_get_rcu_slot(gparent, slot); return; } @@ -673,10 +748,11 @@ static inline unsigned char ma_calc_split(struct ma_state *mas, struct maple_node **left, struct maple_node **right) { char i, j; - unsigned long min = mas->max; + unsigned long min = mas->min; unsigned long max = min; enum maple_type type = mt_node_type(mas->node); unsigned long pivot_cnt = mt_pivots[type]; + unsigned long half = mt_slots[type] / 2; unsigned char data_end = ma_data_end(mas->node, type); *left = ma_next_alloc(mas); @@ -695,7 +771,7 @@ static inline unsigned char ma_calc_split(struct ma_state *mas, } *right = ma_next_alloc(mas); - if (i >= 4) { + if (i >= half) { *left = mt_mk_node(*left, maple_dense); *right = mt_mk_node(*right, type); return i; @@ -716,7 +792,7 @@ static inline unsigned char ma_calc_split(struct ma_state *mas, } } while (j > 0); - if (data_end - j >= 4) { + if (data_end - j >= half) { *left = mt_mk_node(*left, type); *right = mt_mk_node(*right, maple_dense); return j; @@ -725,32 +801,48 @@ static inline unsigned char ma_calc_split(struct ma_state *mas, *right = mt_mk_node(*right, type); } - return i > 2 ? i : 3; + return i > 2 ? i : half - 1; } -static inline void ma_linear_cp(struct ma_state *mas, struct ma_cp *cp) +static inline void ma_dense_cp(struct ma_state *mas, struct ma_cp *cp) { unsigned char sloc = cp->src_start; // src location unsigned char pivot_cnt = mt_pivot_count(cp->src); - unsigned char slot; - unsigned long min = ma_get_pivot(cp->src, sloc); + unsigned long min, piv; + void *ptr; + + if (!sloc) { + min = mas->min; + } + else { + min = ma_get_pivot(cp->src, sloc - 1) + 1; + } + + piv = min; while (sloc <= cp->src_end) { - unsigned long piv; + unsigned long end; + unsigned char slot, end_slot; + + ptr = ma_get_rcu_slot(cp->src, sloc); if (sloc < pivot_cnt) { - piv = ma_get_pivot(cp->src, sloc); - if (sloc != 0 && !piv) - break; - slot = piv - min; + end = ma_get_pivot(cp->src, sloc); } else { - // Last slot. - slot = mas->max - min; - if (!ma_get_rcu_slot(cp->src, sloc)) + if (!ptr) break; + end = mas->max; + } + + slot = piv - min; + end_slot = end - min; + for ( ; slot <= end_slot; slot++) { + ma_set_rcu_slot(cp->dst, slot, ptr); } - ma_cp_rcu_slot(cp->dst, slot, cp->src, sloc); + + piv = end + 1; sloc++; } } + static inline void ma_copy(struct ma_state *mas, struct ma_cp *cp) { unsigned char sloc = cp->src_start; // src location @@ -758,12 +850,7 @@ static inline void ma_copy(struct ma_state *mas, struct ma_cp *cp) enum maple_type type = mt_node_type(cp->src); unsigned char pivot_cnt = mt_pivots[type]; - if (cp->dst) { - if (!mt_pivot_count(cp->dst)) { - ma_linear_cp(mas, cp); - return; - } - } else { + if (!cp->dst) { /* Allocate a new node */ mas_node_cnt(mas, 1); @@ -773,21 +860,28 @@ static inline void ma_copy(struct ma_state *mas, struct ma_cp *cp) cp->dst = mt_mk_node(cp->dst, type); } + if (!mt_pivot_count(cp->dst)) { + ma_dense_cp(mas, cp); + return; + } + while (sloc <= cp->src_end && - dloc <= cp->dst_end) { + dloc <= cp->dst_end) { if (sloc != 0 && sloc < pivot_cnt && - ma_get_pivot(cp->src, sloc) == 0) + ma_get_pivot(cp->src, sloc) == 0) break; if (dloc < pivot_cnt) { if (sloc < pivot_cnt) ma_cp_pivot(cp->dst, dloc, cp->src, sloc); else if (dloc > 0 && - ma_get_pivot(cp->dst, dloc - 1) != mas->max) + ma_get_pivot(cp->dst, dloc - 1) != mas->max) ma_set_pivot(cp->dst, dloc, mas->max); } + if (mt_is_alloc(mas->tree)) + ma_cp_gap(cp->dst, dloc, cp->src, sloc); ma_cp_rcu_slot(cp->dst, dloc++, cp->src, sloc++); } cp->dst_start = dloc; @@ -797,8 +891,6 @@ static inline int ma_split_data(struct ma_state *mas, struct maple_node *left, { MA_CP(cp, mas->node, left, 0, split); - if (!ma_get_rcu_slot(mas->node, split)) - cp.src_end--; ma_copy(mas, &cp); cp.src_start = split + 1; @@ -843,7 +935,7 @@ static inline void mt_replace(struct ma_state *mas) if (ma_is_root(mas->node)) { prev = mas->tree->ma_root; } else { - enum maple_type ptype = mt_parent_enum(mas->node); + enum maple_type ptype = mt_parent_enum(mas, mas->node); parent = mt_parent(mas->node); slot = mt_parent_slot(mas->node); prev = ma_get_rcu_slot(mt_mk_node(parent, ptype), slot); @@ -927,7 +1019,10 @@ static inline int ma_split(struct ma_state *mas, unsigned char slot) if (ma_is_root(mas->node)) { old_parent = full; - ptype = maple_range_64; + if(mt_is_alloc(mas->tree)) + ptype = maple_arange_64; + else + ptype = maple_range_64; p_slot = 0; mas->max = mt_max[ptype]; } else { @@ -983,13 +1078,16 @@ static inline int ma_split(struct ma_state *mas, unsigned char slot) if (right) { // Set up the link to the right in the new parent - if (mt_node_type(right) == maple_dense) + 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)) + } + else if (ma_is_root(full)) { pivot = mt_node_max(mas->node); - else + } + else { pivot = ma_get_pivot(old_parent, p_slot); + } ma_link(right, new_parent, p_slot + 1, pivot, ptype); } @@ -1030,9 +1128,49 @@ static inline int ma_split(struct ma_state *mas, unsigned char slot) // Free the full node. if (old_parent != full) mt_free(mt_to_node(full)); + return split; } +static inline enum maple_type ma_ptype_leaf(struct ma_state *mas) { + enum maple_type pt = mt_node_type(mas->node); + + switch (pt) { + case maple_arange_64: + return maple_aleaf_64; + case maple_range_64: + default: + return maple_leaf_64; + } +} +/* Private + * + * When inserting into non-leaf nodes in _ma_insert, a type is needed. + * + * Try to determine that type here. + */ +static inline enum maple_type ma_determine_type(struct ma_state *mas, + unsigned long min, unsigned char slot) +{ + struct maple_node *sibling; + unsigned char sibling_slot = slot; + enum maple_type stype, mt = ma_ptype_leaf(mas);; + + if (slot > 0) + sibling_slot -= 1; + else + sibling_slot += 1; + sibling = ma_get_rcu_slot(mas->node, sibling_slot); + if (!sibling) + return mt; + + stype = mt_node_type(sibling); + if (mt_max[stype] >= min - mas->index) + return stype; + + return mt; +} + /* Private * * Insert entry into a node. @@ -1103,29 +1241,24 @@ static inline int _ma_insert(struct ma_state *mas, void *entry, p_mn = mas->node; if (!mt_is_leaf(mas->node)) { - struct maple_node *leaf, *sibling; - unsigned char sibling_slot = slot; - enum maple_type mt = maple_leaf_64; + struct maple_node *leaf; + enum maple_type mt; 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; - if (slot > 0) - sibling_slot -= 1; - else - sibling_slot += 1; - - sibling = ma_get_rcu_slot(mas->node, sibling_slot); - if (sibling) - mt = mt_node_type(sibling); + mt = ma_determine_type(mas, min, slot); leaf = mt_mk_node(ma_next_alloc(mas), mt); mt_set_parent(leaf, mas->node, slot); mas->node = leaf; - mas->min = min; + mas->min = mas->index; mas->max = max; _ma_insert(mas, entry, 0); mas->min = o_min; @@ -1138,7 +1271,7 @@ static inline int _ma_insert(struct ma_state *mas, void *entry, /* Figure out if this is an append or not. * Appending does not need to create a new node. */ - if (slot - 1 == o_end) { + if (o_end == 0 || slot - 1 == o_end) { o_end = n_end; /* Appending */ } else { /* Not appending */ @@ -1198,13 +1331,16 @@ static inline void ma_root_expand(struct ma_state *ms, void *entry) { void *r_entry = rcu_dereference(ms->tree->ma_root); // root entry struct maple_node *mn; + enum maple_type mt = maple_leaf_64; mas_node_cnt(ms, 1); if (mas_is_err(ms)) return; mn = ma_next_alloc(ms); - ms->node = mt_mk_node(mn, maple_leaf_64); + if (mt_is_alloc(ms->tree)) + mt = maple_aleaf_64; + ms->node = mt_mk_node(mn, mt); mn->parent = (struct maple_node*) ((unsigned long)ms->tree | MA_ROOT_PARENT); @@ -1421,6 +1557,10 @@ void *mas_walk(struct ma_state *mas) return entry; } +unsigned long mas_walk_next(struct ma_state *mas) +{ + return 0; +} /* Private * Find an entry and erase the entire range */ @@ -1477,6 +1617,7 @@ void ma_destroy_walk(struct maple_node *mn) case maple_range_16: case maple_range_32: case maple_range_64: + case maple_arange_64: for (i = 0; i < slot_cnt; i++) { if (i > 0 && i < slot_cnt - 1 && ma_get_pivot(mn, i) == 0) @@ -1498,10 +1639,10 @@ void __init maple_tree_init(void) sizeof(struct maple_node), sizeof(struct maple_node), SLAB_PANIC | SLAB_RECLAIM_ACCOUNT, NULL); } -void mtree_init(struct maple_tree *mt) +void mtree_init(struct maple_tree *mt, unsigned int ma_flags) { spin_lock_init(&mt->ma_lock); - mt->ma_flags = 0; + mt->ma_flags = ma_flags; rcu_assign_pointer(mt->ma_root, NULL); } @@ -1549,6 +1690,30 @@ int mtree_insert(struct maple_tree *mt, unsigned long index, void *entry, return mtree_insert_range(mt, index, index, entry, gfp); } EXPORT_SYMBOL(mtree_insert); + +int mtree_alloc_range(struct maple_tree *mt, void *startp, + void *ptr, unsigned long size, unsigned long min, + unsigned long max, gfp_t gfp) +{ + int ret = 0; + + + return ret; +} + +int mtree_next(struct maple_tree *mt, unsigned long index, unsigned long *next) +{ + int ret = -ENOENT; + MA_STATE(mas, mt, index, index); + rcu_read_lock(); + *next = mas_walk_next(&mas); + rcu_read_unlock(); + + if (*next) + return 0; + return ret; + +} int mtree_erase(struct maple_tree *mt, unsigned long index) { int ret = -EINVAL; @@ -1565,6 +1730,7 @@ void mtree_destroy(struct maple_tree *mt) { mtree_lock(mt); struct maple_node *destroyed = mt->ma_root; + rcu_assign_pointer(mt->ma_root, NULL); if (xa_is_node(destroyed)) { ma_destroy_walk(mt_safe_root(destroyed)); @@ -1637,6 +1803,44 @@ void mt_dump_range64(void *entry, unsigned long min, unsigned long max, first = last + 1; } } +void mt_dump_arange64(void *entry, unsigned long min, unsigned long max, + unsigned int depth) +{ + struct maple_arange_64 *node = &mt_to_node(entry)->ma64; + bool leaf = mt_is_leaf(entry); + unsigned long first = min; + int i; + + pr_cont(" contents: "); + for (i = 0; i < MAPLE_ARANGE64_SLOTS; i++) + pr_cont("%lu ", node->gap[i]); + 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]); + for (i = 0; i < MAPLE_ARANGE64_SLOTS; i++) { + unsigned long last = max; + + if (i < (MAPLE_ARANGE64_SLOTS - 1)) + last = node->pivot[i]; + else if (node->slot[i] == NULL) + break; + if (last == 0 && i > 0) + break; + if (leaf) + mt_dump_entry(node->slot[i], first, last); + else if (node->slot[i]) + mt_dump_node(node->slot[i], first, last, depth + 1); + + if (last == max) + break; + if (last > max) { + pr_err("node %p last (%lu) > max (%lu) at pivot %d!\n", node, last, max, i); + break; + } + first = last + 1; + } +} void mt_dump_node(void *entry, unsigned long min, unsigned long max, unsigned int depth) @@ -1662,6 +1866,11 @@ void mt_dump_node(void *entry, unsigned long min, unsigned long max, case maple_range_64: mt_dump_range64(entry, min, max, depth); break; + case maple_arange_64: + case maple_aleaf_64: + mt_dump_arange64(entry, min, max, depth); + break; + default: pr_cont(" UNKNOWN TYPE\n"); } diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c index 435625e2206a..ad2d4709ca65 100644 --- a/lib/test_maple_tree.c +++ b/lib/test_maple_tree.c @@ -154,7 +154,6 @@ static noinline void check_new_node(struct maple_tree *mt) MT_BUG_ON(mt, mas.node != MA_ERROR(-ENOMEM)); // Allocate failed. MT_BUG_ON(mt, !mas_nomem(&mas, GFP_KERNEL)); - MT_BUG_ON(mt, ma_get_alloc_cnt(&mas) != 3); mn = ma_get_alloc(&mas); MT_BUG_ON(mt, mn == NULL); @@ -309,7 +308,10 @@ static int maple_tree_seed(void) pr_info("\nTEST STARTING\n\n"); - mtree_init(&tree); + mtree_init(&tree, MAPLE_ALLOC_RANGE); + check_alloc_range(&tree); + + mtree_init(&tree, 0); check_load(&tree, set[0], NULL); // See if 5015 -> NULL @@ -327,7 +329,7 @@ static int maple_tree_seed(void) /* Try to insert, insert a dup, and load back what was inserted. */ - mtree_init(&tree); + mtree_init(&tree, 0); check_insert(&tree, set[0], &tree); // Insert 5015 check_dup_insert(&tree, set[0], &tree); // Insert 5015 again check_load(&tree, set[0], &tree); // See if 5015 -> &tree @@ -353,7 +355,7 @@ static int maple_tree_seed(void) /* Clear out tree */ mtree_destroy(&tree); - mtree_init(&tree); + mtree_init(&tree, 0); /* Test inserting into a NULL hole. */ check_insert(&tree, set[5], ptr); // insert 1001 -> ptr check_insert(&tree, set[7], &tree); // insert 1003 -> &tree @@ -365,7 +367,7 @@ static int maple_tree_seed(void) /* Clear out the tree */ mtree_destroy(&tree); - mtree_init(&tree); + mtree_init(&tree, 0); check_insert_range(&tree, r[0], r[1], ptr); // Insert 10-15 => ptr check_insert_range(&tree, r[2], r[3], ptr); // Insert 20-25 => &tree @@ -373,7 +375,7 @@ static int maple_tree_seed(void) /* Clear out the tree */ mtree_destroy(&tree); - mtree_init(&tree); + mtree_init(&tree, 0); /* * set[] = {15, 14, 17, 25, 1000, * 1001, 1002, 1003, 1005, 0, -- 2.50.1