Re: [PATCH 29/34] maple_tree: Introduce mas_prev_slot() interface

["Liam R. Howlett" <Liam.Howlett@Oracle.com>]

* Peng Zhang <perlyzhang@gmail.com> [230428 04:27]:
> 
> 
> 在 2023/4/25 22:09, Liam R. Howlett 写道:
> > Sometimes the user needs to revert to the previous slot, regardless of
> > if it is empty or not.  Add an interface to go to the previous slot.
> > 
> > Since there can't be two consecutive NULLs in the tree, the mas_prev()
> > function can be implemented by calling mas_prev_slot() a maximum of 2
> > times.  Change the underlying interface to use mas_prev_slot() to align
> > the code.
> > 
> > Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com>
> > ---
> >   lib/maple_tree.c | 217 ++++++++++++++++++++---------------------------
> >   1 file changed, 90 insertions(+), 127 deletions(-)
> > 
> > diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> > index 7370d7c12fe3b..297d936321347 100644
> > --- a/lib/maple_tree.c
> > +++ b/lib/maple_tree.c
> > @@ -4498,6 +4498,25 @@ static inline void *mas_insert(struct ma_state *mas, void *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;
> > +}
> > +
> > +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.
> > @@ -4515,13 +4534,15 @@ static inline int mas_prev_node(struct ma_state *mas, unsigned long min)
> >   	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);
> > +	max = mas->min - 1;
> May underflow.

Thanks, I will address this in v2.

> > +	if (max < min)
> > +		goto no_entry;
> >   	level = 0;
> >   	do {
> > -		node = mas_mn(mas);
> >   		if (ma_is_root(node))
> >   			goto no_entry;
> > @@ -4530,11 +4551,11 @@ 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)))
> > @@ -4543,12 +4564,10 @@ static inline int mas_prev_node(struct ma_state *mas, unsigned long min)
> >   	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);
> > @@ -4569,9 +4588,6 @@ static inline int mas_prev_node(struct ma_state *mas, unsigned long min)
> >   		if (offset < mt_pivots[mt])
> >   			mas->max = pivots[offset];
> > -
> > -		if (mas->max < min)
> > -			goto no_entry;
> >   	}
> >   	mas->node = mas_slot(mas, slots, offset);
> > @@ -4584,10 +4600,6 @@ static inline int mas_prev_node(struct ma_state *mas, unsigned long min)
> >   	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;
> > @@ -4596,6 +4608,62 @@ static inline int mas_prev_node(struct ma_state *mas, unsigned long min)
> >   	return 0;
> >   }
> > +/*
> > + * 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
> > + */
> > +void *mas_prev_slot(struct ma_state *mas, unsigned long min)
> > +{
> > +	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);
> > +	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;
> > +	} 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 = mas_safe_min(mas, pivots, mas->offset);
> > +	slots = ma_slots(node, type);
> > +	entry = mas_slot(mas, slots, mas->offset);
> > +	if (unlikely(mas_rewalk_if_dead(mas, node, save_point)))
> > +		goto retry;
> > +
> > +	return entry;
> > +}
> > +
> >   /*
> >    * mas_next_node() - Get the next node at the same level in the tree.
> >    * @mas: The maple state
> > @@ -4680,25 +4748,6 @@ static inline int mas_next_node(struct ma_state *mas, struct maple_node *node,
> >   	return 0;
> >   }
> > -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_next_slot() - Get the entry in the next slot
> >    *
> > @@ -4777,117 +4826,31 @@ static inline void *mas_next_entry(struct ma_state *mas, unsigned long limit)
> >   	if (mas->last >= limit)
> >   		return NULL;
> > -	entry = mas_next_slot_limit(mas, limit);
> > +	entry = mas_next_slot(mas, limit);
> >   	if (entry)
> >   		return entry;
> >   	if (mas_is_none(mas))
> >   		return NULL;
> > -	return mas_next_slot_limit(mas, limit);
> > -}
> > -
> > -/*
> > - * 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, count;
> > -	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;
> > -	slots = ma_slots(mn, mt);
> > -	pivots = ma_pivots(mn, mt);
> > -	count = ma_data_end(mn, mt, pivots, mas->max);
> > -	if (unlikely(mas_rewalk_if_dead(mas, mn, index)))
> > -		goto retry;
> > -
> > -	offset = mas->offset - 1;
> > -	if (offset >= mt_slots[mt])
> > -		offset = mt_slots[mt] - 1;
> > -
> > -	if (offset >= count) {
> > -		pivot = mas->max;
> > -		offset = count;
> > -	} else {
> > -		pivot = pivots[offset];
> > -	}
> > -
> > -	if (unlikely(mas_rewalk_if_dead(mas, mn, index)))
> > -		goto retry;
> > -
> > -	while (offset && !mas_slot(mas, slots, offset)) {
> > -		pivot = pivots[--offset];
> > -		if (pivot >= limit)
> > -			break;
> > -	}
> > -
> > -	/*
> > -	 * If the slot was null but we've shifted outside the limits, then set
> > -	 * the range to the last NULL.
> > -	 */
> > -	if (unlikely((pivot < limit) && (offset < mas->offset)))
> > -		pivot = pivots[++offset];
> > -
> > -	min = mas_safe_min(mas, pivots, offset);
> > -	entry = mas_slot(mas, slots, offset);
> > -	if (unlikely(mas_rewalk_if_dead(mas, mn, index)))
> > -		goto retry;
> > -
> > -	mas->offset = offset;
> > -	mas->last = pivot;
> > -	mas->index = min;
> > -	return entry;
> > +	return mas_next_slot(mas, limit);
> >   }
> >   static inline void *mas_prev_entry(struct ma_state *mas, unsigned long min)
> >   {
> >   	void *entry;
> > -	struct maple_enode *prev_enode;
> > -	unsigned char prev_offset;
> >   	if (mas->index < min)
> >   		return NULL;
> > -retry:
> > -	prev_enode = mas->node;
> > -	prev_offset = mas->offset;
> > -	while (likely(!mas_is_none(mas))) {
> > -		entry = mas_prev_nentry(mas, min, mas->index);
> > -
> > -		if (likely(entry))
> > -			return entry;
> > -
> > -		if (unlikely(mas->index <= min))
> > -			return NULL;
> > -
> > -		if (unlikely(mas_prev_node(mas, min))) {
> > -			mas_rewalk(mas, mas->index);
> > -			goto retry;
> > -		}
> > +	entry = mas_prev_slot(mas, min);
> > +	if (entry)
> > +		return entry;
> > -		mas->offset++;
> > -	}
> > +	if (mas_is_none(mas))
> > +		return NULL;
> > -	mas->node = prev_enode;
> > -	mas->offset = prev_offset;
> > -	return NULL;
> > +	return mas_prev_slot(mas, min);
> >   }
> >   /*