diff options
Diffstat (limited to 'lib/maple_tree.c')
| -rw-r--r-- | lib/maple_tree.c | 1600 |
1 files changed, 821 insertions, 779 deletions
diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 8ebc43d4cc8c..bfffbb7cab26 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--); } @@ -1755,7 +1752,7 @@ static inline void mas_adopt_children(struct ma_state *mas, * leave the node (true) and handle the adoption and free elsewhere. */ static inline void mas_replace(struct ma_state *mas, bool advanced) - __must_hold(mas->tree->lock) + __must_hold(mas->tree->ma_lock) { struct maple_node *mn = mas_mn(mas); struct maple_enode *old_enode; @@ -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); } @@ -1795,7 +1792,7 @@ static inline void mas_replace(struct ma_state *mas, bool advanced) * @child: the maple state to store the child. */ static inline bool mas_new_child(struct ma_state *mas, struct ma_state *child) - __must_hold(mas->tree->lock) + __must_hold(mas->tree->ma_lock) { enum maple_type mt; unsigned char 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; @@ -3729,43 +3728,31 @@ static inline void mas_store_root(struct ma_state *mas, void *entry) */ static bool mas_is_span_wr(struct ma_wr_state *wr_mas) { - unsigned long max; + unsigned long max = wr_mas->r_max; unsigned long last = wr_mas->mas->last; - unsigned long piv = wr_mas->r_max; enum maple_type type = wr_mas->type; void *entry = wr_mas->entry; - /* Contained in this pivot */ - if (piv > last) + /* Contained in this pivot, fast path */ + if (last < max) return false; - max = wr_mas->mas->max; - if (unlikely(ma_is_leaf(type))) { - /* Fits in the node, but may span slots. */ + if (ma_is_leaf(type)) { + max = wr_mas->mas->max; if (last < max) return false; + } - /* Writes to the end of the node but not null. */ - if ((last == max) && entry) - return false; - + if (last == max) { /* - * Writing ULONG_MAX is not a spanning write regardless of the - * value being written as long as the range fits in the node. + * The last entry of leaf node cannot be NULL unless it is the + * rightmost node (writing ULONG_MAX), otherwise it spans slots. */ - if ((last == ULONG_MAX) && (last == max)) - return false; - } else if (piv == last) { - if (entry) - return false; - - /* Detect spanning store wr walk */ - if (last == ULONG_MAX) + if (entry || last == ULONG_MAX) return false; } - trace_ma_write(__func__, wr_mas->mas, piv, entry); - + trace_ma_write(__func__, wr_mas->mas, wr_mas->r_max, entry); return true; } @@ -4087,52 +4074,27 @@ static inline int mas_wr_spanning_store(struct ma_wr_state *wr_mas) * * Return: True if stored, false otherwise */ -static inline bool mas_wr_node_store(struct ma_wr_state *wr_mas) +static inline bool mas_wr_node_store(struct ma_wr_state *wr_mas, + unsigned char new_end) { struct ma_state *mas = wr_mas->mas; void __rcu **dst_slots; unsigned long *dst_pivots; - unsigned char dst_offset; - unsigned char new_end = wr_mas->node_end; - unsigned char offset; - unsigned char node_slots = mt_slots[wr_mas->type]; + unsigned char dst_offset, offset_end = wr_mas->offset_end; struct maple_node reuse, *newnode; - unsigned char copy_size, max_piv = mt_pivots[wr_mas->type]; + unsigned char copy_size, node_pivots = mt_pivots[wr_mas->type]; bool in_rcu = mt_in_rcu(mas->tree); - offset = mas->offset; - if (mas->last == wr_mas->r_max) { - /* runs right to the end of the node */ - if (mas->last == mas->max) - new_end = offset; - /* don't copy this offset */ - wr_mas->offset_end++; - } else if (mas->last < wr_mas->r_max) { - /* new range ends in this range */ - if (unlikely(wr_mas->r_max == ULONG_MAX)) - mas_bulk_rebalance(mas, wr_mas->node_end, wr_mas->type); - - new_end++; - } else { - if (wr_mas->end_piv == mas->last) - wr_mas->offset_end++; - - new_end -= wr_mas->offset_end - offset - 1; - } - - /* new range starts within a range */ - if (wr_mas->r_min < mas->index) - new_end++; - - /* Not enough room */ - if (new_end >= node_slots) - return false; - - /* Not enough data. */ + /* Check if there is enough data. The room is enough. */ if (!mte_is_root(mas->node) && (new_end <= mt_min_slots[wr_mas->type]) && !(mas->mas_flags & MA_STATE_BULK)) return false; + if (mas->last == wr_mas->end_piv) + offset_end++; /* don't copy this offset */ + else if (unlikely(wr_mas->r_max == ULONG_MAX)) + mas_bulk_rebalance(mas, wr_mas->node_end, wr_mas->type); + /* set up node. */ if (in_rcu) { mas_node_count(mas, 1); @@ -4149,47 +4111,36 @@ static inline bool mas_wr_node_store(struct ma_wr_state *wr_mas) dst_pivots = ma_pivots(newnode, wr_mas->type); dst_slots = ma_slots(newnode, wr_mas->type); /* Copy from start to insert point */ - memcpy(dst_pivots, wr_mas->pivots, sizeof(unsigned long) * (offset + 1)); - memcpy(dst_slots, wr_mas->slots, sizeof(void *) * (offset + 1)); - dst_offset = offset; + memcpy(dst_pivots, wr_mas->pivots, sizeof(unsigned long) * mas->offset); + memcpy(dst_slots, wr_mas->slots, sizeof(void *) * mas->offset); /* Handle insert of new range starting after old range */ if (wr_mas->r_min < mas->index) { - mas->offset++; - rcu_assign_pointer(dst_slots[dst_offset], wr_mas->content); - dst_pivots[dst_offset++] = mas->index - 1; + rcu_assign_pointer(dst_slots[mas->offset], wr_mas->content); + dst_pivots[mas->offset++] = mas->index - 1; } /* Store the new entry and range end. */ - if (dst_offset < max_piv) - dst_pivots[dst_offset] = mas->last; - mas->offset = dst_offset; - rcu_assign_pointer(dst_slots[dst_offset], wr_mas->entry); + if (mas->offset < node_pivots) + dst_pivots[mas->offset] = mas->last; + rcu_assign_pointer(dst_slots[mas->offset], wr_mas->entry); /* * this range wrote to the end of the node or it overwrote the rest of * the data */ - if (wr_mas->offset_end > wr_mas->node_end || mas->last >= mas->max) { - new_end = dst_offset; + if (offset_end > wr_mas->node_end) goto done; - } - dst_offset++; + dst_offset = mas->offset + 1; /* Copy to the end of node if necessary. */ - copy_size = wr_mas->node_end - wr_mas->offset_end + 1; - memcpy(dst_slots + dst_offset, wr_mas->slots + wr_mas->offset_end, + copy_size = wr_mas->node_end - offset_end + 1; + memcpy(dst_slots + dst_offset, wr_mas->slots + offset_end, sizeof(void *) * copy_size); - if (dst_offset < max_piv) { - if (copy_size > max_piv - dst_offset) - copy_size = max_piv - dst_offset; - - memcpy(dst_pivots + dst_offset, - wr_mas->pivots + wr_mas->offset_end, - sizeof(unsigned long) * copy_size); - } + memcpy(dst_pivots + dst_offset, wr_mas->pivots + offset_end, + sizeof(unsigned long) * (copy_size - 1)); - if ((wr_mas->node_end == node_slots - 1) && (new_end < node_slots - 1)) + if (new_end < node_pivots) dst_pivots[new_end] = mas->max; done: @@ -4215,59 +4166,46 @@ done: static inline bool mas_wr_slot_store(struct ma_wr_state *wr_mas) { struct ma_state *mas = wr_mas->mas; - unsigned long lmax; /* Logical max. */ unsigned char offset = mas->offset; + bool gap = false; - if ((wr_mas->r_max > mas->last) && ((wr_mas->r_min != mas->index) || - (offset != wr_mas->node_end))) - return false; - - if (offset == wr_mas->node_end - 1) - lmax = mas->max; - else - lmax = wr_mas->pivots[offset + 1]; - - /* going to overwrite too many slots. */ - if (lmax < mas->last) + if (wr_mas->offset_end - offset != 1) return false; - if (wr_mas->r_min == mas->index) { - /* overwriting two or more ranges with one. */ - if (lmax == mas->last) - return false; + gap |= !mt_slot_locked(mas->tree, wr_mas->slots, offset); + gap |= !mt_slot_locked(mas->tree, wr_mas->slots, offset + 1); - /* Overwriting all of offset and a portion of offset + 1. */ + if (mas->index == wr_mas->r_min) { + /* Overwriting the range and over a part of the next range. */ rcu_assign_pointer(wr_mas->slots[offset], wr_mas->entry); wr_mas->pivots[offset] = mas->last; - goto done; + } else { + /* Overwriting a part of the range and over the next range */ + rcu_assign_pointer(wr_mas->slots[offset + 1], wr_mas->entry); + wr_mas->pivots[offset] = mas->index - 1; + mas->offset++; /* Keep mas accurate. */ } - /* Doesn't end on the next range end. */ - if (lmax != mas->last) - return false; - - /* Overwriting a portion of offset and all of offset + 1 */ - if ((offset + 1 < mt_pivots[wr_mas->type]) && - (wr_mas->entry || wr_mas->pivots[offset + 1])) - wr_mas->pivots[offset + 1] = mas->last; - - rcu_assign_pointer(wr_mas->slots[offset + 1], wr_mas->entry); - wr_mas->pivots[offset] = mas->index - 1; - mas->offset++; /* Keep mas accurate. */ - -done: trace_ma_write(__func__, mas, 0, wr_mas->entry); - mas_update_gap(mas); + /* + * Only update gap when the new entry is empty or there is an empty + * entry in the original two ranges. + */ + if (!wr_mas->entry || gap) + mas_update_gap(mas); + return true; } 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; } @@ -4275,19 +4213,21 @@ static inline void mas_wr_extend_null(struct ma_wr_state *wr_mas) { struct ma_state *mas = wr_mas->mas; - if (mas->last < wr_mas->end_piv && !wr_mas->slots[wr_mas->offset_end]) + if (!wr_mas->slots[wr_mas->offset_end]) { + /* If this one is null, the next and prev are not */ mas->last = wr_mas->end_piv; - - /* Check next slot(s) if we are overwriting the end */ - if ((mas->last == wr_mas->end_piv) && - (wr_mas->node_end != wr_mas->offset_end) && - !wr_mas->slots[wr_mas->offset_end + 1]) { - wr_mas->offset_end++; - if (wr_mas->offset_end == wr_mas->node_end) - mas->last = mas->max; - else - mas->last = wr_mas->pivots[wr_mas->offset_end]; - wr_mas->end_piv = mas->last; + } else { + /* Check next slot(s) if we are overwriting the end */ + if ((mas->last == wr_mas->end_piv) && + (wr_mas->node_end != wr_mas->offset_end) && + !wr_mas->slots[wr_mas->offset_end + 1]) { + wr_mas->offset_end++; + if (wr_mas->offset_end == wr_mas->node_end) + mas->last = mas->max; + else + mas->last = wr_mas->pivots[wr_mas->offset_end]; + wr_mas->end_piv = mas->last; + } } if (!wr_mas->content) { @@ -4305,6 +4245,27 @@ static inline void mas_wr_extend_null(struct ma_wr_state *wr_mas) } } +static inline unsigned char mas_wr_new_end(struct ma_wr_state *wr_mas) +{ + struct ma_state *mas = wr_mas->mas; + unsigned char new_end = wr_mas->node_end + 2; + + new_end -= wr_mas->offset_end - mas->offset; + if (wr_mas->r_min == mas->index) + new_end--; + + if (wr_mas->end_piv == mas->last) + new_end--; + + return new_end; +} + +/* + * mas_wr_append: Attempt to append + * @wr_mas: the maple write state + * + * Return: True if appended, false otherwise + */ static inline bool mas_wr_append(struct ma_wr_state *wr_mas) { unsigned char end = wr_mas->node_end; @@ -4312,34 +4273,30 @@ static inline bool mas_wr_append(struct ma_wr_state *wr_mas) struct ma_state *mas = wr_mas->mas; unsigned char node_pivots = mt_pivots[wr_mas->type]; - if ((mas->index != wr_mas->r_min) && (mas->last == wr_mas->r_max)) { - if (new_end < node_pivots) - wr_mas->pivots[new_end] = wr_mas->pivots[end]; + if (mas->offset != wr_mas->node_end) + return false; - if (new_end < node_pivots) - ma_set_meta(wr_mas->node, maple_leaf_64, 0, new_end); + if (new_end < node_pivots) { + wr_mas->pivots[new_end] = wr_mas->pivots[end]; + ma_set_meta(wr_mas->node, maple_leaf_64, 0, new_end); + } + if (mas->last == wr_mas->r_max) { + /* Append to end of range */ rcu_assign_pointer(wr_mas->slots[new_end], wr_mas->entry); - mas->offset = new_end; wr_mas->pivots[end] = mas->index - 1; - - return true; - } - - if ((mas->index == wr_mas->r_min) && (mas->last < wr_mas->r_max)) { - if (new_end < node_pivots) - wr_mas->pivots[new_end] = wr_mas->pivots[end]; - + mas->offset = new_end; + } else { + /* Append to start of range */ rcu_assign_pointer(wr_mas->slots[new_end], wr_mas->content); - if (new_end < node_pivots) - ma_set_meta(wr_mas->node, maple_leaf_64, 0, new_end); - wr_mas->pivots[end] = mas->last; rcu_assign_pointer(wr_mas->slots[end], wr_mas->entry); - return true; } - return false; + if (!wr_mas->content || !wr_mas->entry) + mas_update_gap(mas); + + return true; } /* @@ -4360,9 +4317,8 @@ static void mas_wr_bnode(struct ma_wr_state *wr_mas) static inline void mas_wr_modify(struct ma_wr_state *wr_mas) { - unsigned char node_slots; - unsigned char node_size; struct ma_state *mas = wr_mas->mas; + unsigned char new_end; /* Direct replacement */ if (wr_mas->r_min == mas->index && wr_mas->r_max == mas->last) { @@ -4372,26 +4328,22 @@ static inline void mas_wr_modify(struct ma_wr_state *wr_mas) return; } - /* Attempt to append */ - node_slots = mt_slots[wr_mas->type]; - node_size = wr_mas->node_end - wr_mas->offset_end + mas->offset + 2; - if (mas->max == ULONG_MAX) - node_size++; - - /* slot and node store will not fit, go to the slow path */ - if (unlikely(node_size >= node_slots)) + /* + * new_end exceeds the size of the maple node and cannot enter the fast + * path. + */ + new_end = mas_wr_new_end(wr_mas); + if (new_end >= mt_slots[wr_mas->type]) goto slow_path; - if (wr_mas->entry && (wr_mas->node_end < node_slots - 1) && - (mas->offset == wr_mas->node_end) && mas_wr_append(wr_mas)) { - if (!wr_mas->content || !wr_mas->entry) - mas_update_gap(mas); + /* Attempt to append */ + if (new_end == wr_mas->node_end + 1 && mas_wr_append(wr_mas)) return; - } - if ((wr_mas->offset_end - mas->offset <= 1) && mas_wr_slot_store(wr_mas)) + if (new_end == wr_mas->node_end && mas_wr_slot_store(wr_mas)) return; - else if (mas_wr_node_store(wr_mas)) + + if (mas_wr_node_store(wr_mas, new_end)) return; if (mas_is_err(mas)) @@ -4424,7 +4376,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 +4449,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 +4483,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 +4504,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 +4548,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 +4628,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 +4639,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 +4657,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 +4699,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 +4795,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 +4974,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; @@ -5202,46 +5072,6 @@ static inline void mas_awalk(struct ma_state *mas, unsigned long size) } /* - * mas_fill_gap() - Fill a located gap with @entry. - * @mas: The maple state - * @entry: The value to store - * @slot: The offset into the node to store the @entry - * @size: The size of the entry - * @index: The start location - */ -static inline void mas_fill_gap(struct ma_state *mas, void *entry, - unsigned char slot, unsigned long size, unsigned long *index) -{ - MA_WR_STATE(wr_mas, mas, entry); - unsigned char pslot = mte_parent_slot(mas->node); - struct maple_enode *mn = mas->node; - unsigned long *pivots; - enum maple_type ptype; - /* - * mas->index is the start address for the search - * which may no longer be needed. - * mas->last is the end address for the search - */ - - *index = mas->index; - mas->last = mas->index + size - 1; - - /* - * It is possible that using mas->max and mas->min to correctly - * calculate the index and last will cause an issue in the gap - * calculation, so fix the ma_state here - */ - mas_ascend(mas); - ptype = mte_node_type(mas->node); - pivots = ma_pivots(mas_mn(mas), ptype); - mas->max = mas_safe_pivot(mas, pivots, pslot, ptype); - mas->min = mas_safe_min(mas, pivots, pslot); - mas->node = mn; - mas->offset = slot; - mas_wr_store_entry(&wr_mas); -} - -/* * mas_sparse_area() - Internal function. Return upper or lower limit when * searching for a gap in an empty tree. * @mas: The maple state @@ -5289,7 +5119,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)) @@ -5338,7 +5171,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)) { @@ -5374,7 +5210,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; @@ -5382,71 +5218,6 @@ int mas_empty_area_rev(struct ma_state *mas, unsigned long min, } EXPORT_SYMBOL_GPL(mas_empty_area_rev); -static inline int mas_alloc(struct ma_state *mas, void *entry, - unsigned long size, unsigned long *index) -{ - unsigned long min; - - mas_start(mas); - if (mas_is_none(mas) || mas_is_ptr(mas)) { - mas_root_expand(mas, entry); - if (mas_is_err(mas)) - return xa_err(mas->node); - - if (!mas->index) - return mte_pivot(mas->node, 0); - return mte_pivot(mas->node, 1); - } - - /* Must be walking a tree. */ - mas_awalk(mas, size); - if (mas_is_err(mas)) - return xa_err(mas->node); - - if (mas->offset == MAPLE_NODE_SLOTS) - goto no_gap; - - /* - * At this point, mas->node points to the right node and we have an - * offset that has a sufficient gap. - */ - min = mas->min; - if (mas->offset) - min = mte_pivot(mas->node, mas->offset - 1) + 1; - - if (mas->index < min) - mas->index = min; - - mas_fill_gap(mas, entry, mas->offset, size, index); - return 0; - -no_gap: - return -EBUSY; -} - -static inline int mas_rev_alloc(struct ma_state *mas, unsigned long min, - unsigned long max, void *entry, - unsigned long size, unsigned long *index) -{ - int ret = 0; - - ret = mas_empty_area_rev(mas, min, max, size); - if (ret) - return ret; - - if (mas_is_err(mas)) - return xa_err(mas->node); - - if (mas->offset == MAPLE_NODE_SLOTS) - goto no_gap; - - mas_fill_gap(mas, entry, mas->offset, size, index); - return 0; - -no_gap: - return -EBUSY; -} - /* * mte_dead_leaves() - Mark all leaves of a node as dead. * @mas: The maple state @@ -5694,9 +5465,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; @@ -5756,7 +5527,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); @@ -5808,9 +5579,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) @@ -5900,6 +5669,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 @@ -5913,27 +5710,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 @@ -5955,6 +5763,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 @@ -5968,37 +5817,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 @@ -6040,6 +5889,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 @@ -6053,37 +5960,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 @@ -6100,37 +6075,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 @@ -6176,7 +6155,7 @@ EXPORT_SYMBOL_GPL(mas_erase); * Return: true on allocation, false otherwise. */ bool mas_nomem(struct ma_state *mas, gfp_t gfp) - __must_hold(mas->tree->lock) + __must_hold(mas->tree->ma_lock) { if (likely(mas->node != MA_ERROR(-ENOMEM))) { mas_destroy(mas); @@ -6357,31 +6336,33 @@ 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, 0, 0); if (!mt_is_alloc(mt)) return -EINVAL; if (WARN_ON_ONCE(mt_is_reserved(entry))) return -EINVAL; - if (min > max) - return -EINVAL; - - if (max < size) - return -EINVAL; - - if (!size) - return -EINVAL; - mtree_lock(mt); retry: - mas.offset = 0; - mas.index = min; - mas.last = max - size; - ret = mas_alloc(&mas, entry, size, startp); + ret = mas_empty_area(&mas, min, max, size); + if (ret) + goto unlock; + + mas_insert(&mas, entry); + /* + * mas_nomem() may release the lock, causing the allocated area + * to be unavailable, so try to allocate a free area again. + */ if (mas_nomem(&mas, gfp)) goto retry; + if (mas_is_err(&mas)) + ret = xa_err(mas.node); + else + *startp = mas.index; + +unlock: mtree_unlock(mt); return ret; } @@ -6393,28 +6374,33 @@ 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, 0, 0); if (!mt_is_alloc(mt)) return -EINVAL; if (WARN_ON_ONCE(mt_is_reserved(entry))) return -EINVAL; - if (min >= max) - return -EINVAL; - - if (max < size - 1) - return -EINVAL; - - if (!size) - return -EINVAL; - mtree_lock(mt); retry: - ret = mas_rev_alloc(&mas, min, max, entry, size, startp); + ret = mas_empty_area_rev(&mas, min, max, size); + if (ret) + goto unlock; + + mas_insert(&mas, entry); + /* + * mas_nomem() may release the lock, causing the allocated area + * to be unavailable, so try to allocate a free area again. + */ if (mas_nomem(&mas, gfp)) goto retry; + if (mas_is_err(&mas)) + ret = xa_err(mas.node); + else + *startp = mas.index; + +unlock: mtree_unlock(mt); return ret; } @@ -6512,7 +6498,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; @@ -6525,10 +6511,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 } @@ -6674,7 +6659,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); @@ -6685,7 +6670,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); @@ -6735,15 +6720,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; @@ -6752,22 +6734,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), @@ -6781,7 +6774,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); @@ -6789,8 +6783,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; @@ -6803,24 +6805,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); @@ -6845,10 +6855,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; @@ -6862,13 +6872,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); @@ -6879,15 +6890,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: @@ -6895,16 +6906,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); @@ -6957,7 +6968,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); @@ -6988,27 +6999,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); @@ -7101,18 +7114,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) @@ -7135,7 +7148,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); } } } @@ -7194,16 +7207,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); @@ -7219,4 +7231,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 */ |