diff options
Diffstat (limited to 'lib/maple_tree.c')
| -rw-r--r-- | lib/maple_tree.c | 1182 |
1 files changed, 684 insertions, 498 deletions
diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 110a36479dce..4eb220008f72 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -194,7 +194,7 @@ static void mas_set_height(struct ma_state *mas) unsigned int new_flags = mas->tree->ma_flags; new_flags &= ~MT_FLAGS_HEIGHT_MASK; - BUG_ON(mas->depth > MAPLE_HEIGHT_MAX); + MAS_BUG_ON(mas, mas->depth > MAPLE_HEIGHT_MAX); new_flags |= mas->depth << MT_FLAGS_HEIGHT_OFFSET; mas->tree->ma_flags = new_flags; } @@ -240,12 +240,12 @@ static inline void mas_set_err(struct ma_state *mas, long err) mas->node = MA_ERROR(err); } -static inline bool mas_is_ptr(struct ma_state *mas) +static inline bool mas_is_ptr(const struct ma_state *mas) { return mas->node == MAS_ROOT; } -static inline bool mas_is_start(struct ma_state *mas) +static inline bool mas_is_start(const struct ma_state *mas) { return mas->node == MAS_START; } @@ -425,28 +425,26 @@ static inline unsigned long mte_parent_slot_mask(unsigned long parent) } /* - * mas_parent_enum() - Return the maple_type of the parent from the stored + * mas_parent_type() - Return the maple_type of the parent from the stored * parent type. * @mas: The maple state - * @node: The maple_enode to extract the parent's enum + * @enode: The maple_enode to extract the parent's enum * Return: The node->parent maple_type */ static inline -enum maple_type mte_parent_enum(struct maple_enode *p_enode, - struct maple_tree *mt) +enum maple_type mas_parent_type(struct ma_state *mas, struct maple_enode *enode) { unsigned long p_type; - p_type = (unsigned long)p_enode; - if (p_type & MAPLE_PARENT_ROOT) - return 0; /* Validated in the caller. */ + p_type = (unsigned long)mte_to_node(enode)->parent; + if (WARN_ON(p_type & MAPLE_PARENT_ROOT)) + return 0; p_type &= MAPLE_NODE_MASK; - p_type = p_type & ~(MAPLE_PARENT_ROOT | mte_parent_slot_mask(p_type)); - + p_type &= ~mte_parent_slot_mask(p_type); switch (p_type) { case MAPLE_PARENT_RANGE64: /* or MAPLE_PARENT_ARANGE64 */ - if (mt_is_alloc(mt)) + if (mt_is_alloc(mas->tree)) return maple_arange_64; return maple_range_64; } @@ -454,14 +452,8 @@ enum maple_type mte_parent_enum(struct maple_enode *p_enode, return 0; } -static inline -enum maple_type mas_parent_enum(struct ma_state *mas, struct maple_enode *enode) -{ - return mte_parent_enum(ma_enode_ptr(mte_to_node(enode)->parent), mas->tree); -} - /* - * mte_set_parent() - Set the parent node and encode the slot + * mas_set_parent() - Set the parent node and encode the slot * @enode: The encoded maple node. * @parent: The encoded maple node that is the parent of @enode. * @slot: The slot that @enode resides in @parent. @@ -470,16 +462,16 @@ enum maple_type mas_parent_enum(struct ma_state *mas, struct maple_enode *enode) * parent type. */ static inline -void mte_set_parent(struct maple_enode *enode, const struct maple_enode *parent, - unsigned char slot) +void mas_set_parent(struct ma_state *mas, struct maple_enode *enode, + const struct maple_enode *parent, unsigned char slot) { unsigned long val = (unsigned long)parent; unsigned long shift; unsigned long type; enum maple_type p_type = mte_node_type(parent); - BUG_ON(p_type == maple_dense); - BUG_ON(p_type == maple_leaf_64); + MAS_BUG_ON(mas, p_type == maple_dense); + MAS_BUG_ON(mas, p_type == maple_leaf_64); switch (p_type) { case maple_range_64: @@ -671,22 +663,22 @@ static inline unsigned long *ma_gaps(struct maple_node *node, } /* - * mte_pivot() - Get the pivot at @piv of the maple encoded node. - * @mn: The maple encoded node. + * mas_pivot() - Get the pivot at @piv of the maple encoded node. + * @mas: The maple state. * @piv: The pivot. * * Return: the pivot at @piv of @mn. */ -static inline unsigned long mte_pivot(const struct maple_enode *mn, - unsigned char piv) +static inline unsigned long mas_pivot(struct ma_state *mas, unsigned char piv) { - struct maple_node *node = mte_to_node(mn); - enum maple_type type = mte_node_type(mn); + struct maple_node *node = mas_mn(mas); + enum maple_type type = mte_node_type(mas->node); - if (piv >= mt_pivots[type]) { - WARN_ON(1); + if (MAS_WARN_ON(mas, piv >= mt_pivots[type])) { + mas_set_err(mas, -EIO); return 0; } + switch (type) { case maple_arange_64: return node->ma64.pivot[piv]; @@ -971,8 +963,6 @@ static inline unsigned char ma_meta_end(struct maple_node *mn, static inline unsigned char ma_meta_gap(struct maple_node *mn, enum maple_type mt) { - BUG_ON(mt != maple_arange_64); - return mn->ma64.meta.gap; } @@ -1111,7 +1101,6 @@ static int mas_ascend(struct ma_state *mas) enum maple_type a_type; unsigned long min, max; unsigned long *pivots; - unsigned char offset; bool set_max = false, set_min = false; a_node = mas_mn(mas); @@ -1123,8 +1112,9 @@ static int mas_ascend(struct ma_state *mas) p_node = mte_parent(mas->node); if (unlikely(a_node == p_node)) return 1; - a_type = mas_parent_enum(mas, mas->node); - offset = mte_parent_slot(mas->node); + + a_type = mas_parent_type(mas, mas->node); + mas->offset = mte_parent_slot(mas->node); a_enode = mt_mk_node(p_node, a_type); /* Check to make sure all parent information is still accurate */ @@ -1132,7 +1122,6 @@ static int mas_ascend(struct ma_state *mas) return 1; mas->node = a_enode; - mas->offset = offset; if (mte_is_root(a_enode)) { mas->max = ULONG_MAX; @@ -1140,11 +1129,17 @@ static int mas_ascend(struct ma_state *mas) return 0; } + if (!mas->min) + set_min = true; + + if (mas->max == ULONG_MAX) + set_max = true; + min = 0; max = ULONG_MAX; do { p_enode = a_enode; - a_type = mas_parent_enum(mas, p_enode); + a_type = mas_parent_type(mas, p_enode); a_node = mte_parent(p_enode); a_slot = mte_parent_slot(p_enode); a_enode = mt_mk_node(a_node, a_type); @@ -1401,9 +1396,9 @@ static inline struct maple_enode *mas_start(struct ma_state *mas) mas->min = 0; mas->max = ULONG_MAX; - mas->depth = 0; retry: + mas->depth = 0; root = mas_root(mas); /* Tree with nodes */ if (likely(xa_is_node(root))) { @@ -1631,6 +1626,7 @@ static inline unsigned long mas_max_gap(struct ma_state *mas) return mas_leaf_max_gap(mas); node = mas_mn(mas); + MAS_BUG_ON(mas, mt != maple_arange_64); offset = ma_meta_gap(node, mt); if (offset == MAPLE_ARANGE64_META_MAX) return 0; @@ -1659,11 +1655,12 @@ static inline void mas_parent_gap(struct ma_state *mas, unsigned char offset, enum maple_type pmt; pnode = mte_parent(mas->node); - pmt = mas_parent_enum(mas, mas->node); + pmt = mas_parent_type(mas, mas->node); penode = mt_mk_node(pnode, pmt); pgaps = ma_gaps(pnode, pmt); ascend: + MAS_BUG_ON(mas, pmt != maple_arange_64); meta_offset = ma_meta_gap(pnode, pmt); if (meta_offset == MAPLE_ARANGE64_META_MAX) meta_gap = 0; @@ -1691,7 +1688,7 @@ ascend: /* Go to the parent node. */ pnode = mte_parent(penode); - pmt = mas_parent_enum(mas, penode); + pmt = mas_parent_type(mas, penode); pgaps = ma_gaps(pnode, pmt); offset = mte_parent_slot(penode); penode = mt_mk_node(pnode, pmt); @@ -1718,7 +1715,7 @@ static inline void mas_update_gap(struct ma_state *mas) pslot = mte_parent_slot(mas->node); p_gap = ma_gaps(mte_parent(mas->node), - mas_parent_enum(mas, mas->node))[pslot]; + mas_parent_type(mas, mas->node))[pslot]; if (p_gap != max_gap) mas_parent_gap(mas, pslot, max_gap); @@ -1743,7 +1740,7 @@ static inline void mas_adopt_children(struct ma_state *mas, offset = ma_data_end(node, type, pivots, mas->max); do { child = mas_slot_locked(mas, slots, offset); - mte_set_parent(child, parent, offset); + mas_set_parent(mas, child, parent, offset); } while (offset--); } @@ -1767,7 +1764,7 @@ static inline void mas_replace(struct ma_state *mas, bool advanced) } else { offset = mte_parent_slot(mas->node); slots = ma_slots(mte_parent(mas->node), - mas_parent_enum(mas, mas->node)); + mas_parent_type(mas, mas->node)); old_enode = mas_slot_locked(mas, slots, offset); } @@ -1943,8 +1940,9 @@ static inline int mab_calc_split(struct ma_state *mas, * causes one node to be deficient. * NOTE: mt_min_slots is 1 based, b_end and split are zero. */ - while (((bn->pivot[split] - min) < slot_count - 1) && - (split < slot_count - 1) && (b_end - split > slot_min)) + while ((split < slot_count - 1) && + ((bn->pivot[split] - min) < slot_count - 1) && + (b_end - split > slot_min)) split++; } @@ -2347,7 +2345,8 @@ static inline void mas_topiary_range(struct ma_state *mas, void __rcu **slots; unsigned char offset; - MT_BUG_ON(mas->tree, mte_is_leaf(mas->node)); + MAS_BUG_ON(mas, mte_is_leaf(mas->node)); + slots = ma_slots(mas_mn(mas), mte_node_type(mas->node)); for (offset = start; offset <= end; offset++) { struct maple_enode *enode = mas_slot_locked(mas, slots, offset); @@ -2707,9 +2706,9 @@ static inline void mas_set_split_parent(struct ma_state *mas, return; if ((*slot) <= split) - mte_set_parent(mas->node, left, *slot); + mas_set_parent(mas, mas->node, left, *slot); else if (right) - mte_set_parent(mas->node, right, (*slot) - split - 1); + mas_set_parent(mas, mas->node, right, (*slot) - split - 1); (*slot)++; } @@ -3106,12 +3105,12 @@ static int mas_spanning_rebalance(struct ma_state *mas, mte_node_type(mast->orig_l->node)); mast->orig_l->depth++; mab_mas_cp(mast->bn, 0, mt_slots[mast->bn->type] - 1, &l_mas, true); - mte_set_parent(left, l_mas.node, slot); + mas_set_parent(mas, left, l_mas.node, slot); if (middle) - mte_set_parent(middle, l_mas.node, ++slot); + mas_set_parent(mas, middle, l_mas.node, ++slot); if (right) - mte_set_parent(right, l_mas.node, ++slot); + mas_set_parent(mas, right, l_mas.node, ++slot); if (mas_is_root_limits(mast->l)) { new_root: @@ -3250,7 +3249,7 @@ static inline void mas_destroy_rebalance(struct ma_state *mas, unsigned char end l_mas.max = l_pivs[split]; mas->min = l_mas.max + 1; eparent = mt_mk_node(mte_parent(l_mas.node), - mas_parent_enum(&l_mas, l_mas.node)); + mas_parent_type(&l_mas, l_mas.node)); tmp += end; if (!in_rcu) { unsigned char max_p = mt_pivots[mt]; @@ -3293,7 +3292,7 @@ static inline void mas_destroy_rebalance(struct ma_state *mas, unsigned char end /* replace parent. */ offset = mte_parent_slot(mas->node); - mt = mas_parent_enum(&l_mas, l_mas.node); + mt = mas_parent_type(&l_mas, l_mas.node); parent = mas_pop_node(mas); slots = ma_slots(parent, mt); pivs = ma_pivots(parent, mt); @@ -3338,8 +3337,8 @@ static inline bool mas_split_final_node(struct maple_subtree_state *mast, * The Big_node data should just fit in a single node. */ ancestor = mas_new_ma_node(mas, mast->bn); - mte_set_parent(mast->l->node, ancestor, mast->l->offset); - mte_set_parent(mast->r->node, ancestor, mast->r->offset); + mas_set_parent(mas, mast->l->node, ancestor, mast->l->offset); + mas_set_parent(mas, mast->r->node, ancestor, mast->r->offset); mte_to_node(ancestor)->parent = mas_mn(mas)->parent; mast->l->node = ancestor; @@ -4263,11 +4262,13 @@ done: static inline void mas_wr_end_piv(struct ma_wr_state *wr_mas) { - while ((wr_mas->mas->last > wr_mas->end_piv) && - (wr_mas->offset_end < wr_mas->node_end)) - wr_mas->end_piv = wr_mas->pivots[++wr_mas->offset_end]; + while ((wr_mas->offset_end < wr_mas->node_end) && + (wr_mas->mas->last > wr_mas->pivots[wr_mas->offset_end])) + wr_mas->offset_end++; - if (wr_mas->mas->last > wr_mas->end_piv) + if (wr_mas->offset_end < wr_mas->node_end) + wr_mas->end_piv = wr_mas->pivots[wr_mas->offset_end]; + else wr_mas->end_piv = wr_mas->mas->max; } @@ -4424,7 +4425,6 @@ static inline void *mas_wr_store_entry(struct ma_wr_state *wr_mas) } /* At this point, we are at the leaf node that needs to be altered. */ - wr_mas->end_piv = wr_mas->r_max; mas_wr_end_piv(wr_mas); if (!wr_mas->entry) @@ -4498,6 +4498,25 @@ exists: } +static inline void mas_rewalk(struct ma_state *mas, unsigned long index) +{ +retry: + mas_set(mas, index); + mas_state_walk(mas); + if (mas_is_start(mas)) + goto retry; +} + +static inline bool mas_rewalk_if_dead(struct ma_state *mas, + struct maple_node *node, const unsigned long index) +{ + if (unlikely(ma_dead_node(node))) { + mas_rewalk(mas, index); + return true; + } + return false; +} + /* * mas_prev_node() - Find the prev non-null entry at the same level in the * tree. The prev value will be mas->node[mas->offset] or MAS_NONE. @@ -4513,15 +4532,19 @@ static inline int mas_prev_node(struct ma_state *mas, unsigned long min) int offset, level; void __rcu **slots; struct maple_node *node; - struct maple_enode *enode; unsigned long *pivots; + unsigned long max; - if (mas_is_none(mas)) - return 0; + node = mas_mn(mas); + if (!mas->min) + goto no_entry; + + max = mas->min - 1; + if (max < min) + goto no_entry; level = 0; do { - node = mas_mn(mas); if (ma_is_root(node)) goto no_entry; @@ -4530,64 +4553,41 @@ static inline int mas_prev_node(struct ma_state *mas, unsigned long min) return 1; offset = mas->offset; level++; + node = mas_mn(mas); } while (!offset); offset--; mt = mte_node_type(mas->node); - node = mas_mn(mas); - slots = ma_slots(node, mt); - pivots = ma_pivots(node, mt); - if (unlikely(ma_dead_node(node))) - return 1; - - mas->max = pivots[offset]; - if (offset) - mas->min = pivots[offset - 1] + 1; - if (unlikely(ma_dead_node(node))) - return 1; - - if (mas->max < min) - goto no_entry_min; - while (level > 1) { level--; - enode = mas_slot(mas, slots, offset); + slots = ma_slots(node, mt); + mas->node = mas_slot(mas, slots, offset); if (unlikely(ma_dead_node(node))) return 1; - mas->node = enode; mt = mte_node_type(mas->node); node = mas_mn(mas); - slots = ma_slots(node, mt); pivots = ma_pivots(node, mt); - offset = ma_data_end(node, mt, pivots, mas->max); + offset = ma_data_end(node, mt, pivots, max); if (unlikely(ma_dead_node(node))) return 1; - - if (offset) - mas->min = pivots[offset - 1] + 1; - - if (offset < mt_pivots[mt]) - mas->max = pivots[offset]; - - if (mas->max < min) - goto no_entry; } + slots = ma_slots(node, mt); mas->node = mas_slot(mas, slots, offset); + pivots = ma_pivots(node, mt); if (unlikely(ma_dead_node(node))) return 1; + if (likely(offset)) + mas->min = pivots[offset - 1] + 1; + mas->max = max; mas->offset = mas_data_end(mas); if (unlikely(mte_dead_node(mas->node))) return 1; return 0; -no_entry_min: - mas->offset = offset; - if (offset) - mas->min = pivots[offset - 1] + 1; no_entry: if (unlikely(ma_dead_node(node))) return 1; @@ -4597,6 +4597,76 @@ no_entry: } /* + * mas_prev_slot() - Get the entry in the previous slot + * + * @mas: The maple state + * @max: The minimum starting range + * + * Return: The entry in the previous slot which is possibly NULL + */ +static void *mas_prev_slot(struct ma_state *mas, unsigned long min, bool empty) +{ + void *entry; + void __rcu **slots; + unsigned long pivot; + enum maple_type type; + unsigned long *pivots; + struct maple_node *node; + unsigned long save_point = mas->index; + +retry: + node = mas_mn(mas); + type = mte_node_type(mas->node); + pivots = ma_pivots(node, type); + if (unlikely(mas_rewalk_if_dead(mas, node, save_point))) + goto retry; + +again: + if (mas->min <= min) { + pivot = mas_safe_min(mas, pivots, mas->offset); + + if (unlikely(mas_rewalk_if_dead(mas, node, save_point))) + goto retry; + + if (pivot <= min) + return NULL; + } + + if (likely(mas->offset)) { + mas->offset--; + mas->last = mas->index - 1; + mas->index = mas_safe_min(mas, pivots, mas->offset); + } else { + if (mas_prev_node(mas, min)) { + mas_rewalk(mas, save_point); + goto retry; + } + + if (mas_is_none(mas)) + return NULL; + + mas->last = mas->max; + node = mas_mn(mas); + type = mte_node_type(mas->node); + pivots = ma_pivots(node, type); + mas->index = pivots[mas->offset - 1] + 1; + } + + slots = ma_slots(node, type); + entry = mas_slot(mas, slots, mas->offset); + if (unlikely(mas_rewalk_if_dead(mas, node, save_point))) + goto retry; + + if (likely(entry)) + return entry; + + if (!empty) + goto again; + + return entry; +} + +/* * mas_next_node() - Get the next node at the same level in the tree. * @mas: The maple state * @max: The maximum pivot value to check. @@ -4607,11 +4677,10 @@ no_entry: static inline int mas_next_node(struct ma_state *mas, struct maple_node *node, unsigned long max) { - unsigned long min, pivot; + unsigned long min; unsigned long *pivots; struct maple_enode *enode; int level = 0; - unsigned char offset; unsigned char node_end; enum maple_type mt; void __rcu **slots; @@ -4619,19 +4688,16 @@ static inline int mas_next_node(struct ma_state *mas, struct maple_node *node, if (mas->max >= max) goto no_entry; + min = mas->max + 1; level = 0; do { if (ma_is_root(node)) goto no_entry; - min = mas->max + 1; - if (min > max) - goto no_entry; - + /* Walk up. */ if (unlikely(mas_ascend(mas))) return 1; - offset = mas->offset; level++; node = mas_mn(mas); mt = mte_node_type(mas->node); @@ -4640,36 +4706,37 @@ static inline int mas_next_node(struct ma_state *mas, struct maple_node *node, if (unlikely(ma_dead_node(node))) return 1; - } while (unlikely(offset == node_end)); + } while (unlikely(mas->offset == node_end)); slots = ma_slots(node, mt); - pivot = mas_safe_pivot(mas, pivots, ++offset, mt); - while (unlikely(level > 1)) { - /* Descend, if necessary */ - enode = mas_slot(mas, slots, offset); - if (unlikely(ma_dead_node(node))) - return 1; + mas->offset++; + enode = mas_slot(mas, slots, mas->offset); + if (unlikely(ma_dead_node(node))) + return 1; - mas->node = enode; + if (level > 1) + mas->offset = 0; + + while (unlikely(level > 1)) { level--; + mas->node = enode; node = mas_mn(mas); mt = mte_node_type(mas->node); slots = ma_slots(node, mt); - pivots = ma_pivots(node, mt); + enode = mas_slot(mas, slots, 0); if (unlikely(ma_dead_node(node))) return 1; - - offset = 0; - pivot = pivots[0]; } - enode = mas_slot(mas, slots, offset); + if (!mas->offset) + pivots = ma_pivots(node, mt); + + mas->max = mas_safe_pivot(mas, pivots, mas->offset, mt); if (unlikely(ma_dead_node(node))) return 1; mas->node = enode; mas->min = min; - mas->max = pivot; return 0; no_entry: @@ -4681,92 +4748,88 @@ no_entry: } /* - * mas_next_nentry() - Get the next node entry - * @mas: The maple state - * @max: The maximum value to check - * @*range_start: Pointer to store the start of the range. + * mas_next_slot() - Get the entry in the next slot * - * Sets @mas->offset to the offset of the next node entry, @mas->last to the - * pivot of the entry. + * @mas: The maple state + * @max: The maximum starting range + * @empty: Can be empty * - * Return: The next entry, %NULL otherwise + * Return: The entry in the next slot which is possibly NULL */ -static inline void *mas_next_nentry(struct ma_state *mas, - struct maple_node *node, unsigned long max, enum maple_type type) +static void *mas_next_slot(struct ma_state *mas, unsigned long max, bool empty) { - unsigned char count; - unsigned long pivot; - unsigned long *pivots; void __rcu **slots; + unsigned long *pivots; + unsigned long pivot; + enum maple_type type; + struct maple_node *node; + unsigned char data_end; + unsigned long save_point = mas->last; void *entry; - if (mas->last == mas->max) { - mas->index = mas->max; - return NULL; - } - - slots = ma_slots(node, type); +retry: + node = mas_mn(mas); + type = mte_node_type(mas->node); pivots = ma_pivots(node, type); - count = ma_data_end(node, type, pivots, mas->max); - if (unlikely(ma_dead_node(node))) - return NULL; - - mas->index = mas_safe_min(mas, pivots, mas->offset); - if (unlikely(ma_dead_node(node))) - return NULL; - - if (mas->index > max) - return NULL; - - if (mas->offset > count) - return NULL; + data_end = ma_data_end(node, type, pivots, mas->max); + if (unlikely(mas_rewalk_if_dead(mas, node, save_point))) + goto retry; - while (mas->offset < count) { - pivot = pivots[mas->offset]; - entry = mas_slot(mas, slots, mas->offset); - if (ma_dead_node(node)) - return NULL; +again: + if (mas->max >= max) { + if (likely(mas->offset < data_end)) + pivot = pivots[mas->offset]; + else + return NULL; /* must be mas->max */ - if (entry) - goto found; + if (unlikely(mas_rewalk_if_dead(mas, node, save_point))) + goto retry; if (pivot >= max) return NULL; + } - mas->index = pivot + 1; + if (likely(mas->offset < data_end)) { + mas->index = pivots[mas->offset] + 1; mas->offset++; - } + if (likely(mas->offset < data_end)) + mas->last = pivots[mas->offset]; + else + mas->last = mas->max; + } else { + if (mas_next_node(mas, node, max)) { + mas_rewalk(mas, save_point); + goto retry; + } - if (mas->index > mas->max) { - mas->index = mas->last; - return NULL; + if (mas_is_none(mas)) + return NULL; + + mas->offset = 0; + mas->index = mas->min; + node = mas_mn(mas); + type = mte_node_type(mas->node); + pivots = ma_pivots(node, type); + mas->last = pivots[0]; } - pivot = mas_safe_pivot(mas, pivots, mas->offset, type); - entry = mas_slot(mas, slots, mas->offset); - if (ma_dead_node(node)) - return NULL; + slots = ma_slots(node, type); + entry = mt_slot(mas->tree, slots, mas->offset); + if (unlikely(mas_rewalk_if_dead(mas, node, save_point))) + goto retry; - if (!pivot) - return NULL; + if (entry) + return entry; - if (!entry) - return NULL; + if (!empty) { + if (!mas->offset) + data_end = 2; + goto again; + } -found: - mas->last = pivot; return entry; } -static inline void mas_rewalk(struct ma_state *mas, unsigned long index) -{ -retry: - mas_set(mas, index); - mas_state_walk(mas); - if (mas_is_start(mas)) - goto retry; -} - /* * mas_next_entry() - Internal function to get the next entry. * @mas: The maple state @@ -4781,155 +4844,10 @@ retry: */ static inline void *mas_next_entry(struct ma_state *mas, unsigned long limit) { - void *entry = NULL; - struct maple_enode *prev_node; - struct maple_node *node; - unsigned char offset; - unsigned long last; - enum maple_type mt; - - if (mas->index > limit) { - mas->index = mas->last = limit; - mas_pause(mas); + if (mas->last >= limit) return NULL; - } - last = mas->last; -retry: - offset = mas->offset; - prev_node = mas->node; - node = mas_mn(mas); - mt = mte_node_type(mas->node); - mas->offset++; - if (unlikely(mas->offset >= mt_slots[mt])) { - mas->offset = mt_slots[mt] - 1; - goto next_node; - } - while (!mas_is_none(mas)) { - entry = mas_next_nentry(mas, node, limit, mt); - if (unlikely(ma_dead_node(node))) { - mas_rewalk(mas, last); - goto retry; - } - - if (likely(entry)) - return entry; - - if (unlikely((mas->index > limit))) - break; - -next_node: - prev_node = mas->node; - offset = mas->offset; - if (unlikely(mas_next_node(mas, node, limit))) { - mas_rewalk(mas, last); - goto retry; - } - mas->offset = 0; - node = mas_mn(mas); - mt = mte_node_type(mas->node); - } - - mas->index = mas->last = limit; - mas->offset = offset; - mas->node = prev_node; - return NULL; -} - -/* - * mas_prev_nentry() - Get the previous node entry. - * @mas: The maple state. - * @limit: The lower limit to check for a value. - * - * Return: the entry, %NULL otherwise. - */ -static inline void *mas_prev_nentry(struct ma_state *mas, unsigned long limit, - unsigned long index) -{ - unsigned long pivot, min; - unsigned char offset; - struct maple_node *mn; - enum maple_type mt; - unsigned long *pivots; - void __rcu **slots; - void *entry; - -retry: - if (!mas->offset) - return NULL; - - mn = mas_mn(mas); - mt = mte_node_type(mas->node); - offset = mas->offset - 1; - if (offset >= mt_slots[mt]) - offset = mt_slots[mt] - 1; - - slots = ma_slots(mn, mt); - pivots = ma_pivots(mn, mt); - if (unlikely(ma_dead_node(mn))) { - mas_rewalk(mas, index); - goto retry; - } - - if (offset == mt_pivots[mt]) - pivot = mas->max; - else - pivot = pivots[offset]; - - if (unlikely(ma_dead_node(mn))) { - mas_rewalk(mas, index); - goto retry; - } - - while (offset && ((!mas_slot(mas, slots, offset) && pivot >= limit) || - !pivot)) - pivot = pivots[--offset]; - - min = mas_safe_min(mas, pivots, offset); - entry = mas_slot(mas, slots, offset); - if (unlikely(ma_dead_node(mn))) { - mas_rewalk(mas, index); - goto retry; - } - - if (likely(entry)) { - mas->offset = offset; - mas->last = pivot; - mas->index = min; - } - return entry; -} - -static inline void *mas_prev_entry(struct ma_state *mas, unsigned long min) -{ - void *entry; - - if (mas->index < min) { - mas->index = mas->last = min; - mas->node = MAS_NONE; - return NULL; - } -retry: - while (likely(!mas_is_none(mas))) { - entry = mas_prev_nentry(mas, min, mas->index); - if (unlikely(mas->last < min)) - goto not_found; - - if (likely(entry)) - return entry; - - if (unlikely(mas_prev_node(mas, min))) { - mas_rewalk(mas, mas->index); - goto retry; - } - - mas->offset++; - } - - mas->offset--; -not_found: - mas->index = mas->last = min; - return NULL; + return mas_next_slot(mas, limit, false); } /* @@ -5105,24 +5023,25 @@ void *mas_walk(struct ma_state *mas) { void *entry; + if (mas_is_none(mas) || mas_is_paused(mas) || mas_is_ptr(mas)) + mas->node = MAS_START; retry: entry = mas_state_walk(mas); - if (mas_is_start(mas)) + if (mas_is_start(mas)) { goto retry; - - if (mas_is_ptr(mas)) { + } else if (mas_is_none(mas)) { + mas->index = 0; + mas->last = ULONG_MAX; + } else if (mas_is_ptr(mas)) { if (!mas->index) { mas->last = 0; - } else { - mas->index = 1; - mas->last = ULONG_MAX; + return entry; } - return entry; - } - if (mas_is_none(mas)) { - mas->index = 0; + mas->index = 1; mas->last = ULONG_MAX; + mas->node = MAS_NONE; + return NULL; } return entry; @@ -5289,7 +5208,10 @@ int mas_empty_area(struct ma_state *mas, unsigned long min, unsigned long *pivots; enum maple_type mt; - if (min >= max) + if (min > max) + return -EINVAL; + + if (size == 0 || max - min < size - 1) return -EINVAL; if (mas_is_start(mas)) @@ -5317,15 +5239,9 @@ int mas_empty_area(struct ma_state *mas, unsigned long min, mt = mte_node_type(mas->node); pivots = ma_pivots(mas_mn(mas), mt); - if (offset) - mas->min = pivots[offset - 1] + 1; - - if (offset < mt_pivots[mt]) - mas->max = pivots[offset]; - - if (mas->index < mas->min) - mas->index = mas->min; - + min = mas_safe_min(mas, pivots, offset); + if (mas->index < min) + mas->index = min; mas->last = mas->index + size - 1; return 0; } @@ -5344,7 +5260,10 @@ int mas_empty_area_rev(struct ma_state *mas, unsigned long min, { struct maple_enode *last = mas->node; - if (min >= max) + if (min > max) + return -EINVAL; + + if (size == 0 || max - min < size - 1) return -EINVAL; if (mas_is_start(mas)) { @@ -5380,7 +5299,7 @@ int mas_empty_area_rev(struct ma_state *mas, unsigned long min, return -EBUSY; /* Trim the upper limit to the max. */ - if (max <= mas->last) + if (max < mas->last) mas->last = max; mas->index = mas->last - size + 1; @@ -5400,8 +5319,8 @@ static inline int mas_alloc(struct ma_state *mas, void *entry, return xa_err(mas->node); if (!mas->index) - return mte_pivot(mas->node, 0); - return mte_pivot(mas->node, 1); + return mas_pivot(mas, 0); + return mas_pivot(mas, 1); } /* Must be walking a tree. */ @@ -5418,7 +5337,10 @@ static inline int mas_alloc(struct ma_state *mas, void *entry, */ min = mas->min; if (mas->offset) - min = mte_pivot(mas->node, mas->offset - 1) + 1; + min = mas_pivot(mas, mas->offset - 1) + 1; + + if (mas_is_err(mas)) + return xa_err(mas->node); if (mas->index < min) mas->index = min; @@ -5700,9 +5622,9 @@ void *mas_store(struct ma_state *mas, void *entry) trace_ma_write(__func__, mas, 0, entry); #ifdef CONFIG_DEBUG_MAPLE_TREE - if (mas->index > mas->last) - pr_err("Error %lu > %lu %p\n", mas->index, mas->last, entry); - MT_BUG_ON(mas->tree, mas->index > mas->last); + if (MAS_WARN_ON(mas, mas->index > mas->last)) + pr_err("Error %lX > %lX %p\n", mas->index, mas->last, entry); + if (mas->index > mas->last) { mas_set_err(mas, -EINVAL); return NULL; @@ -5762,7 +5684,7 @@ void mas_store_prealloc(struct ma_state *mas, void *entry) mas_wr_store_setup(&wr_mas); trace_ma_write(__func__, mas, 0, entry); mas_wr_store_entry(&wr_mas); - BUG_ON(mas_is_err(mas)); + MAS_WR_BUG_ON(&wr_mas, mas_is_err(mas)); mas_destroy(mas); } EXPORT_SYMBOL_GPL(mas_store_prealloc); @@ -5814,9 +5736,7 @@ void mas_destroy(struct ma_state *mas) if (mas->mas_flags & MA_STATE_REBALANCE) { unsigned char end; - if (mas_is_start(mas)) - mas_start(mas); - + mas_start(mas); mtree_range_walk(mas); end = mas_data_end(mas) + 1; if (end < mt_min_slot_count(mas->node) - 1) @@ -5906,6 +5826,34 @@ int mas_expected_entries(struct ma_state *mas, unsigned long nr_entries) } EXPORT_SYMBOL_GPL(mas_expected_entries); +static inline bool mas_next_setup(struct ma_state *mas, unsigned long max, + void **entry) +{ + bool was_none = mas_is_none(mas); + + if (mas_is_none(mas) || mas_is_paused(mas)) + mas->node = MAS_START; + + if (mas_is_start(mas)) + *entry = mas_walk(mas); /* Retries on dead nodes handled by mas_walk */ + + if (mas_is_ptr(mas)) { + *entry = NULL; + if (was_none && mas->index == 0) { + mas->index = mas->last = 0; + return true; + } + mas->index = 1; + mas->last = ULONG_MAX; + mas->node = MAS_NONE; + return true; + } + + if (mas_is_none(mas)) + return true; + return false; +} + /** * mas_next() - Get the next entry. * @mas: The maple state @@ -5919,27 +5867,38 @@ EXPORT_SYMBOL_GPL(mas_expected_entries); */ void *mas_next(struct ma_state *mas, unsigned long max) { - if (mas_is_none(mas) || mas_is_paused(mas)) - mas->node = MAS_START; + void *entry = NULL; - if (mas_is_start(mas)) - mas_walk(mas); /* Retries on dead nodes handled by mas_walk */ + if (mas_next_setup(mas, max, &entry)) + return entry; - if (mas_is_ptr(mas)) { - if (!mas->index) { - mas->index = 1; - mas->last = ULONG_MAX; - } - return NULL; - } + /* Retries on dead nodes handled by mas_next_slot */ + return mas_next_slot(mas, max, false); +} +EXPORT_SYMBOL_GPL(mas_next); - if (mas->last == ULONG_MAX) - return NULL; +/** + * mas_next_range() - Advance the maple state to the next range + * @mas: The maple state + * @max: The maximum index to check. + * + * Sets @mas->index and @mas->last to the range. + * Must hold rcu_read_lock or the write lock. + * Can return the zero entry. + * + * Return: The next entry or %NULL + */ +void *mas_next_range(struct ma_state *mas, unsigned long max) +{ + void *entry = NULL; + + if (mas_next_setup(mas, max, &entry)) + return entry; - /* Retries on dead nodes handled by mas_next_entry */ - return mas_next_entry(mas, max); + /* Retries on dead nodes handled by mas_next_slot */ + return mas_next_slot(mas, max, true); } -EXPORT_SYMBOL_GPL(mas_next); +EXPORT_SYMBOL_GPL(mas_next_range); /** * mt_next() - get the next value in the maple tree @@ -5961,6 +5920,47 @@ void *mt_next(struct maple_tree *mt, unsigned long index, unsigned long max) } EXPORT_SYMBOL_GPL(mt_next); +static inline bool mas_prev_setup(struct ma_state *mas, unsigned long min, + void **entry) +{ + if (mas->index <= min) + goto none; + + if (mas_is_none(mas) || mas_is_paused(mas)) + mas->node = MAS_START; + + if (mas_is_start(mas)) { + mas_walk(mas); + if (!mas->index) + goto none; + } + + if (unlikely(mas_is_ptr(mas))) { + if (!mas->index) + goto none; + mas->index = mas->last = 0; + *entry = mas_root(mas); + return true; + } + + if (mas_is_none(mas)) { + if (mas->index) { + /* Walked to out-of-range pointer? */ + mas->index = mas->last = 0; + mas->node = MAS_ROOT; + *entry = mas_root(mas); + return true; + } + return true; + } + + return false; + +none: + mas->node = MAS_NONE; + return true; +} + /** * mas_prev() - Get the previous entry * @mas: The maple state @@ -5974,37 +5974,37 @@ EXPORT_SYMBOL_GPL(mt_next); */ void *mas_prev(struct ma_state *mas, unsigned long min) { - if (!mas->index) { - /* Nothing comes before 0 */ - mas->last = 0; - mas->node = MAS_NONE; - return NULL; - } + void *entry = NULL; - if (unlikely(mas_is_ptr(mas))) - return NULL; + if (mas_prev_setup(mas, min, &entry)) + return entry; - if (mas_is_none(mas) || mas_is_paused(mas)) - mas->node = MAS_START; + return mas_prev_slot(mas, min, false); +} +EXPORT_SYMBOL_GPL(mas_prev); - if (mas_is_start(mas)) { - mas_walk(mas); - if (!mas->index) - return NULL; - } +/** + * mas_prev_range() - Advance to the previous range + * @mas: The maple state + * @min: The minimum value to check. + * + * Sets @mas->index and @mas->last to the range. + * Must hold rcu_read_lock or the write lock. + * Will reset mas to MAS_START if the node is MAS_NONE. Will stop on not + * searchable nodes. + * + * Return: the previous value or %NULL. + */ +void *mas_prev_range(struct ma_state *mas, unsigned long min) +{ + void *entry = NULL; - if (mas_is_ptr(mas)) { - if (!mas->index) { - mas->last = 0; - return NULL; - } + if (mas_prev_setup(mas, min, &entry)) + return entry; - mas->index = mas->last = 0; - return mas_root_locked(mas); - } - return mas_prev_entry(mas, min); + return mas_prev_slot(mas, min, true); } -EXPORT_SYMBOL_GPL(mas_prev); +EXPORT_SYMBOL_GPL(mas_prev_range); /** * mt_prev() - get the previous value in the maple tree @@ -6046,6 +6046,64 @@ void mas_pause(struct ma_state *mas) EXPORT_SYMBOL_GPL(mas_pause); /** + * mas_find_setup() - Internal function to set up mas_find*(). + * @mas: The maple state + * @max: The maximum index + * @entry: Pointer to the entry + * + * Returns: True if entry is the answer, false otherwise. + */ +static inline bool mas_find_setup(struct ma_state *mas, unsigned long max, + void **entry) +{ + *entry = NULL; + + if (unlikely(mas_is_none(mas))) { + if (unlikely(mas->last >= max)) + return true; + + mas->index = mas->last; + mas->node = MAS_START; + } else if (unlikely(mas_is_paused(mas))) { + if (unlikely(mas->last >= max)) + return true; + + mas->node = MAS_START; + mas->index = ++mas->last; + } else if (unlikely(mas_is_ptr(mas))) + goto ptr_out_of_range; + + if (unlikely(mas_is_start(mas))) { + /* First run or continue */ + if (mas->index > max) + return true; + + *entry = mas_walk(mas); + if (*entry) + return true; + + } + + if (unlikely(!mas_searchable(mas))) { + if (unlikely(mas_is_ptr(mas))) + goto ptr_out_of_range; + + return true; + } + + if (mas->index == max) + return true; + + return false; + +ptr_out_of_range: + mas->node = MAS_NONE; + mas->index = 1; + mas->last = ULONG_MAX; + return true; +} + +/** * mas_find() - On the first call, find the entry at or after mas->index up to * %max. Otherwise, find the entry after mas->index. * @mas: The maple state @@ -6059,37 +6117,105 @@ EXPORT_SYMBOL_GPL(mas_pause); */ void *mas_find(struct ma_state *mas, unsigned long max) { + void *entry = NULL; + + if (mas_find_setup(mas, max, &entry)) + return entry; + + /* Retries on dead nodes handled by mas_next_slot */ + return mas_next_slot(mas, max, false); +} +EXPORT_SYMBOL_GPL(mas_find); + +/** + * mas_find_range() - On the first call, find the entry at or after + * mas->index up to %max. Otherwise, advance to the next slot mas->index. + * @mas: The maple state + * @max: The maximum value to check. + * + * Must hold rcu_read_lock or the write lock. + * If an entry exists, last and index are updated accordingly. + * May set @mas->node to MAS_NONE. + * + * Return: The entry or %NULL. + */ +void *mas_find_range(struct ma_state *mas, unsigned long max) +{ + void *entry; + + if (mas_find_setup(mas, max, &entry)) + return entry; + + /* Retries on dead nodes handled by mas_next_slot */ + return mas_next_slot(mas, max, true); +} +EXPORT_SYMBOL_GPL(mas_find_range); + +/** + * mas_find_rev_setup() - Internal function to set up mas_find_*_rev() + * @mas: The maple state + * @min: The minimum index + * @entry: Pointer to the entry + * + * Returns: True if entry is the answer, false otherwise. + */ +static inline bool mas_find_rev_setup(struct ma_state *mas, unsigned long min, + void **entry) +{ + *entry = NULL; + + if (unlikely(mas_is_none(mas))) { + if (mas->index <= min) + goto none; + + mas->last = mas->index; + mas->node = MAS_START; + } + if (unlikely(mas_is_paused(mas))) { - if (unlikely(mas->last == ULONG_MAX)) { + if (unlikely(mas->index <= min)) { mas->node = MAS_NONE; - return NULL; + return true; } mas->node = MAS_START; - mas->index = ++mas->last; + mas->last = --mas->index; } - if (unlikely(mas_is_none(mas))) - mas->node = MAS_START; - if (unlikely(mas_is_start(mas))) { /* First run or continue */ - void *entry; + if (mas->index < min) + return true; - if (mas->index > max) - return NULL; + *entry = mas_walk(mas); + if (*entry) + return true; + } - entry = mas_walk(mas); - if (entry) - return entry; + if (unlikely(!mas_searchable(mas))) { + if (mas_is_ptr(mas)) + goto none; + + if (mas_is_none(mas)) { + /* + * Walked to the location, and there was nothing so the + * previous location is 0. + */ + mas->last = mas->index = 0; + mas->node = MAS_ROOT; + *entry = mas_root(mas); + return true; + } } - if (unlikely(!mas_searchable(mas))) - return NULL; + if (mas->index < min) + return true; + + return false; - /* Retries on dead nodes handled by mas_next_entry */ - return mas_next_entry(mas, max); +none: + mas->node = MAS_NONE; + return true; } -EXPORT_SYMBOL_GPL(mas_find); /** * mas_find_rev: On the first call, find the first non-null entry at or below @@ -6106,37 +6232,41 @@ EXPORT_SYMBOL_GPL(mas_find); */ void *mas_find_rev(struct ma_state *mas, unsigned long min) { - if (unlikely(mas_is_paused(mas))) { - if (unlikely(mas->last == ULONG_MAX)) { - mas->node = MAS_NONE; - return NULL; - } - mas->node = MAS_START; - mas->last = --mas->index; - } + void *entry; - if (unlikely(mas_is_start(mas))) { - /* First run or continue */ - void *entry; + if (mas_find_rev_setup(mas, min, &entry)) + return entry; - if (mas->index < min) - return NULL; + /* Retries on dead nodes handled by mas_prev_slot */ + return mas_prev_slot(mas, min, false); - entry = mas_walk(mas); - if (entry) - return entry; - } +} +EXPORT_SYMBOL_GPL(mas_find_rev); - if (unlikely(!mas_searchable(mas))) - return NULL; +/** + * mas_find_range_rev: On the first call, find the first non-null entry at or + * below mas->index down to %min. Otherwise advance to the previous slot after + * mas->index down to %min. + * @mas: The maple state + * @min: The minimum value to check. + * + * Must hold rcu_read_lock or the write lock. + * If an entry exists, last and index are updated accordingly. + * May set @mas->node to MAS_NONE. + * + * Return: The entry or %NULL. + */ +void *mas_find_range_rev(struct ma_state *mas, unsigned long min) +{ + void *entry; - if (mas->index < min) - return NULL; + if (mas_find_rev_setup(mas, min, &entry)) + return entry; - /* Retries on dead nodes handled by mas_prev_entry */ - return mas_prev_entry(mas, min); + /* Retries on dead nodes handled by mas_prev_slot */ + return mas_prev_slot(mas, min, true); } -EXPORT_SYMBOL_GPL(mas_find_rev); +EXPORT_SYMBOL_GPL(mas_find_range_rev); /** * mas_erase() - Find the range in which index resides and erase the entire @@ -6363,7 +6493,7 @@ int mtree_alloc_range(struct maple_tree *mt, unsigned long *startp, { int ret = 0; - MA_STATE(mas, mt, min, max - size); + MA_STATE(mas, mt, min, min); if (!mt_is_alloc(mt)) return -EINVAL; @@ -6383,7 +6513,7 @@ int mtree_alloc_range(struct maple_tree *mt, unsigned long *startp, retry: mas.offset = 0; mas.index = min; - mas.last = max - size; + mas.last = max - size + 1; ret = mas_alloc(&mas, entry, size, startp); if (mas_nomem(&mas, gfp)) goto retry; @@ -6399,14 +6529,14 @@ int mtree_alloc_rrange(struct maple_tree *mt, unsigned long *startp, { int ret = 0; - MA_STATE(mas, mt, min, max - size); + MA_STATE(mas, mt, min, max - size + 1); if (!mt_is_alloc(mt)) return -EINVAL; if (WARN_ON_ONCE(mt_is_reserved(entry))) return -EINVAL; - if (min >= max) + if (min > max) return -EINVAL; if (max < size - 1) @@ -6518,7 +6648,7 @@ retry: if (entry) goto unlock; - while (mas_searchable(&mas) && (mas.index < max)) { + while (mas_searchable(&mas) && (mas.last < max)) { entry = mas_next_entry(&mas, max); if (likely(entry && !xa_is_zero(entry))) break; @@ -6531,10 +6661,9 @@ unlock: if (likely(entry)) { *index = mas.last + 1; #ifdef CONFIG_DEBUG_MAPLE_TREE - if ((*index) && (*index) <= copy) + if (MT_WARN_ON(mt, (*index) && ((*index) <= copy))) pr_err("index not increased! %lx <= %lx\n", *index, copy); - MT_BUG_ON(mt, (*index) && ((*index) <= copy)); #endif } @@ -6680,7 +6809,7 @@ static inline void *mas_first_entry(struct ma_state *mas, struct maple_node *mn, max = mas->max; mas->offset = 0; while (likely(!ma_is_leaf(mt))) { - MT_BUG_ON(mas->tree, mte_dead_node(mas->node)); + MAS_WARN_ON(mas, mte_dead_node(mas->node)); slots = ma_slots(mn, mt); entry = mas_slot(mas, slots, 0); pivots = ma_pivots(mn, mt); @@ -6691,7 +6820,7 @@ static inline void *mas_first_entry(struct ma_state *mas, struct maple_node *mn, mn = mas_mn(mas); mt = mte_node_type(mas->node); } - MT_BUG_ON(mas->tree, mte_dead_node(mas->node)); + MAS_WARN_ON(mas, mte_dead_node(mas->node)); mas->max = max; slots = ma_slots(mn, mt); @@ -6741,15 +6870,12 @@ static void mas_dfs_postorder(struct ma_state *mas, unsigned long max) mas->node = mn; mas_ascend(mas); - while (mas->node != MAS_NONE) { + do { p = mas->node; p_min = mas->min; p_max = mas->max; mas_prev_node(mas, 0); - } - - if (p == MAS_NONE) - return; + } while (!mas_is_none(mas)); mas->node = p; mas->max = p_max; @@ -6758,22 +6884,33 @@ static void mas_dfs_postorder(struct ma_state *mas, unsigned long max) /* Tree validations */ static void mt_dump_node(const struct maple_tree *mt, void *entry, - unsigned long min, unsigned long max, unsigned int depth); + unsigned long min, unsigned long max, unsigned int depth, + enum mt_dump_format format); static void mt_dump_range(unsigned long min, unsigned long max, - unsigned int depth) + unsigned int depth, enum mt_dump_format format) { static const char spaces[] = " "; - if (min == max) - pr_info("%.*s%lu: ", depth * 2, spaces, min); - else - pr_info("%.*s%lu-%lu: ", depth * 2, spaces, min, max); + switch(format) { + case mt_dump_hex: + if (min == max) + pr_info("%.*s%lx: ", depth * 2, spaces, min); + else + pr_info("%.*s%lx-%lx: ", depth * 2, spaces, min, max); + break; + default: + case mt_dump_dec: + if (min == max) + pr_info("%.*s%lu: ", depth * 2, spaces, min); + else + pr_info("%.*s%lu-%lu: ", depth * 2, spaces, min, max); + } } static void mt_dump_entry(void *entry, unsigned long min, unsigned long max, - unsigned int depth) + unsigned int depth, enum mt_dump_format format) { - mt_dump_range(min, max, depth); + mt_dump_range(min, max, depth, format); if (xa_is_value(entry)) pr_cont("value %ld (0x%lx) [%p]\n", xa_to_value(entry), @@ -6787,7 +6924,8 @@ static void mt_dump_entry(void *entry, unsigned long min, unsigned long max, } static void mt_dump_range64(const struct maple_tree *mt, void *entry, - unsigned long min, unsigned long max, unsigned int depth) + unsigned long min, unsigned long max, unsigned int depth, + enum mt_dump_format format) { struct maple_range_64 *node = &mte_to_node(entry)->mr64; bool leaf = mte_is_leaf(entry); @@ -6795,8 +6933,16 @@ static void mt_dump_range64(const struct maple_tree *mt, void *entry, int i; pr_cont(" contents: "); - for (i = 0; i < MAPLE_RANGE64_SLOTS - 1; i++) - pr_cont("%p %lu ", node->slot[i], node->pivot[i]); + for (i = 0; i < MAPLE_RANGE64_SLOTS - 1; i++) { + switch(format) { + case mt_dump_hex: + pr_cont("%p %lX ", node->slot[i], node->pivot[i]); + break; + default: + case mt_dump_dec: + pr_cont("%p %lu ", node->slot[i], node->pivot[i]); + } + } pr_cont("%p\n", node->slot[i]); for (i = 0; i < MAPLE_RANGE64_SLOTS; i++) { unsigned long last = max; @@ -6809,24 +6955,32 @@ static void mt_dump_range64(const struct maple_tree *mt, void *entry, break; if (leaf) mt_dump_entry(mt_slot(mt, node->slot, i), - first, last, depth + 1); + first, last, depth + 1, format); else if (node->slot[i]) mt_dump_node(mt, mt_slot(mt, node->slot, i), - first, last, depth + 1); + first, last, depth + 1, format); if (last == max) break; if (last > max) { - pr_err("node %p last (%lu) > max (%lu) at pivot %d!\n", + switch(format) { + case mt_dump_hex: + pr_err("node %p last (%lx) > max (%lx) at pivot %d!\n", node, last, max, i); - break; + break; + default: + case mt_dump_dec: + pr_err("node %p last (%lu) > max (%lu) at pivot %d!\n", + node, last, max, i); + } } first = last + 1; } } static void mt_dump_arange64(const struct maple_tree *mt, void *entry, - unsigned long min, unsigned long max, unsigned int depth) + unsigned long min, unsigned long max, unsigned int depth, + enum mt_dump_format format) { struct maple_arange_64 *node = &mte_to_node(entry)->ma64; bool leaf = mte_is_leaf(entry); @@ -6851,10 +7005,10 @@ static void mt_dump_arange64(const struct maple_tree *mt, void *entry, break; if (leaf) mt_dump_entry(mt_slot(mt, node->slot, i), - first, last, depth + 1); + first, last, depth + 1, format); else if (node->slot[i]) mt_dump_node(mt, mt_slot(mt, node->slot, i), - first, last, depth + 1); + first, last, depth + 1, format); if (last == max) break; @@ -6868,13 +7022,14 @@ static void mt_dump_arange64(const struct maple_tree *mt, void *entry, } static void mt_dump_node(const struct maple_tree *mt, void *entry, - unsigned long min, unsigned long max, unsigned int depth) + unsigned long min, unsigned long max, unsigned int depth, + enum mt_dump_format format) { struct maple_node *node = mte_to_node(entry); unsigned int type = mte_node_type(entry); unsigned int i; - mt_dump_range(min, max, depth); + mt_dump_range(min, max, depth, format); pr_cont("node %p depth %d type %d parent %p", node, depth, type, node ? node->parent : NULL); @@ -6885,15 +7040,15 @@ static void mt_dump_node(const struct maple_tree *mt, void *entry, if (min + i > max) pr_cont("OUT OF RANGE: "); mt_dump_entry(mt_slot(mt, node->slot, i), - min + i, min + i, depth); + min + i, min + i, depth, format); } break; case maple_leaf_64: case maple_range_64: - mt_dump_range64(mt, entry, min, max, depth); + mt_dump_range64(mt, entry, min, max, depth, format); break; case maple_arange_64: - mt_dump_arange64(mt, entry, min, max, depth); + mt_dump_arange64(mt, entry, min, max, depth, format); break; default: @@ -6901,16 +7056,16 @@ static void mt_dump_node(const struct maple_tree *mt, void *entry, } } -void mt_dump(const struct maple_tree *mt) +void mt_dump(const struct maple_tree *mt, enum mt_dump_format format) { void *entry = rcu_dereference_check(mt->ma_root, mt_locked(mt)); pr_info("maple_tree(%p) flags %X, height %u root %p\n", mt, mt->ma_flags, mt_height(mt), entry); if (!xa_is_node(entry)) - mt_dump_entry(entry, 0, 0, 0); + mt_dump_entry(entry, 0, 0, 0, format); else if (entry) - mt_dump_node(mt, entry, 0, mt_node_max(entry), 0); + mt_dump_node(mt, entry, 0, mt_node_max(entry), 0, format); } EXPORT_SYMBOL_GPL(mt_dump); @@ -6963,7 +7118,7 @@ static void mas_validate_gaps(struct ma_state *mas) mas_mn(mas), i, mas_get_slot(mas, i), gap, p_end, p_start); - mt_dump(mas->tree); + mt_dump(mas->tree, mt_dump_hex); MT_BUG_ON(mas->tree, gap != p_end - p_start + 1); @@ -6994,27 +7149,29 @@ counted: p_slot = mte_parent_slot(mas->node); p_mn = mte_parent(mte); MT_BUG_ON(mas->tree, max_gap > mas->max); - if (ma_gaps(p_mn, mas_parent_enum(mas, mte))[p_slot] != max_gap) { + if (ma_gaps(p_mn, mas_parent_type(mas, mte))[p_slot] != max_gap) { pr_err("gap %p[%u] != %lu\n", p_mn, p_slot, max_gap); - mt_dump(mas->tree); + mt_dump(mas->tree, mt_dump_hex); } MT_BUG_ON(mas->tree, - ma_gaps(p_mn, mas_parent_enum(mas, mte))[p_slot] != max_gap); + ma_gaps(p_mn, mas_parent_type(mas, mte))[p_slot] != max_gap); } static void mas_validate_parent_slot(struct ma_state *mas) { struct maple_node *parent; struct maple_enode *node; - enum maple_type p_type = mas_parent_enum(mas, mas->node); - unsigned char p_slot = mte_parent_slot(mas->node); + enum maple_type p_type; + unsigned char p_slot; void __rcu **slots; int i; if (mte_is_root(mas->node)) return; + p_slot = mte_parent_slot(mas->node); + p_type = mas_parent_type(mas, mas->node); parent = mte_parent(mas->node); slots = ma_slots(parent, p_type); MT_BUG_ON(mas->tree, mas_mn(mas) == parent); @@ -7107,18 +7264,18 @@ static void mas_validate_limits(struct ma_state *mas) if (prev_piv > piv) { pr_err("%p[%u] piv %lu < prev_piv %lu\n", mas_mn(mas), i, piv, prev_piv); - MT_BUG_ON(mas->tree, piv < prev_piv); + MAS_WARN_ON(mas, piv < prev_piv); } if (piv < mas->min) { pr_err("%p[%u] %lu < %lu\n", mas_mn(mas), i, piv, mas->min); - MT_BUG_ON(mas->tree, piv < mas->min); + MAS_WARN_ON(mas, piv < mas->min); } if (piv > mas->max) { pr_err("%p[%u] %lu > %lu\n", mas_mn(mas), i, piv, mas->max); - MT_BUG_ON(mas->tree, piv > mas->max); + MAS_WARN_ON(mas, piv > mas->max); } prev_piv = piv; if (piv == mas->max) @@ -7141,7 +7298,7 @@ static void mas_validate_limits(struct ma_state *mas) pr_err("%p[%u] should not have piv %lu\n", mas_mn(mas), i, piv); - MT_BUG_ON(mas->tree, i < mt_pivots[type] - 1); + MAS_WARN_ON(mas, i < mt_pivots[type] - 1); } } } @@ -7200,16 +7357,15 @@ void mt_validate(struct maple_tree *mt) mas_first_entry(&mas, mas_mn(&mas), ULONG_MAX, mte_node_type(mas.node)); while (!mas_is_none(&mas)) { - MT_BUG_ON(mas.tree, mte_dead_node(mas.node)); + MAS_WARN_ON(&mas, mte_dead_node(mas.node)); if (!mte_is_root(mas.node)) { end = mas_data_end(&mas); - if ((end < mt_min_slot_count(mas.node)) && - (mas.max != ULONG_MAX)) { + if (MAS_WARN_ON(&mas, + (end < mt_min_slot_count(mas.node)) && + (mas.max != ULONG_MAX))) { pr_err("Invalid size %u of %p\n", end, - mas_mn(&mas)); - MT_BUG_ON(mas.tree, 1); + mas_mn(&mas)); } - } mas_validate_parent_slot(&mas); mas_validate_child_slot(&mas); @@ -7225,4 +7381,34 @@ done: } EXPORT_SYMBOL_GPL(mt_validate); +void mas_dump(const struct ma_state *mas) +{ + pr_err("MAS: tree=%p enode=%p ", mas->tree, mas->node); + if (mas_is_none(mas)) + pr_err("(MAS_NONE) "); + else if (mas_is_ptr(mas)) + pr_err("(MAS_ROOT) "); + else if (mas_is_start(mas)) + pr_err("(MAS_START) "); + else if (mas_is_paused(mas)) + pr_err("(MAS_PAUSED) "); + + pr_err("[%u] index=%lx last=%lx\n", mas->offset, mas->index, mas->last); + pr_err(" min=%lx max=%lx alloc=%p, depth=%u, flags=%x\n", + mas->min, mas->max, mas->alloc, mas->depth, mas->mas_flags); + if (mas->index > mas->last) + pr_err("Check index & last\n"); +} +EXPORT_SYMBOL_GPL(mas_dump); + +void mas_wr_dump(const struct ma_wr_state *wr_mas) +{ + pr_err("WR_MAS: node=%p r_min=%lx r_max=%lx\n", + wr_mas->node, wr_mas->r_min, wr_mas->r_max); + pr_err(" type=%u off_end=%u, node_end=%u, end_piv=%lx\n", + wr_mas->type, wr_mas->offset_end, wr_mas->node_end, + wr_mas->end_piv); +} +EXPORT_SYMBOL_GPL(mas_wr_dump); + #endif /* CONFIG_DEBUG_MAPLE_TREE */ |