Re: [PATCH 27/34] maple_tree: Introduce mas_next_slot() interface

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

* Peng Zhang <perlyzhang@gmail.com> [230428 02:48]:
> 
> 
> 在 2023/4/25 22:09, Liam R. Howlett 写道:
> > Sometimes, during a tree walk, the user needs the next slot regardless
> > of if it is empty or not.  Add an interface to get the next slot.
> > 
> > Since there are no consecutive NULLs allowed in the tree, the mas_next()
> > function can only advance two slots at most.  So use the new
> > mas_next_slot() interface to align both implementations.
> > 
> > Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com>
> > ---
> >   lib/maple_tree.c | 178 +++++++++++++++++++----------------------------
> >   1 file changed, 71 insertions(+), 107 deletions(-)
> > 
> > diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> > index 31cbfd7b44728..fe6c9da6f2bd5 100644
> > --- a/lib/maple_tree.c
> > +++ b/lib/maple_tree.c
> > @@ -4619,15 +4619,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;
> > +	if (min > max)
> > +		goto no_entry;
> Unnecessary check due to mas->max < max.

Thanks, I will address this in v2.

> > +
> >   	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;
> > @@ -4645,13 +4646,12 @@ static inline int mas_next_node(struct ma_state *mas, struct maple_node *node,
> >   	slots = ma_slots(node, mt);
> >   	pivot = mas_safe_pivot(mas, pivots, ++offset, mt);
> >   	while (unlikely(level > 1)) {
> > -		/* Descend, if necessary */
> > +		level--;
> >   		enode = mas_slot(mas, slots, offset);
> >   		if (unlikely(ma_dead_node(node)))
> >   			return 1;
> >   		mas->node = enode;
> > -		level--;
> >   		node = mas_mn(mas);
> >   		mt = mte_node_type(mas->node);
> >   		slots = ma_slots(node, mt);
> > @@ -4680,85 +4680,84 @@ 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_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
> >    *
> > - * 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)
> > +void *mas_next_slot(struct ma_state *mas, unsigned long max)
> >   {
> > -	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;
> > +	data_end = ma_data_end(node, type, pivots, mas->max);
> > +	pivot = mas_logical_pivot(mas, pivots, mas->offset, type);
> > +	if (unlikely(mas_rewalk_if_dead(mas, node, save_point)))
> > +		goto retry;
> > -	if (mas->offset > count)
> > +	if (pivot >= max)
> >   		return NULL;
> > -	while (mas->offset < count) {
> > -		pivot = pivots[mas->offset];
> > -		entry = mas_slot(mas, slots, mas->offset);
> > -		if (ma_dead_node(node))
> > -			return NULL;
> > -
> > -		mas->last = pivot;
> > -		if (entry)
> > -			return entry;
> > -
> > -		if (pivot >= max)
> > -			return NULL;
> > +	if (likely(data_end > mas->offset)) {
> > +		mas->offset++;
> > +		mas->index = mas->last + 1;
> > +	} else  {
> > +		if (mas_next_node(mas, node, max)) {
> > +			mas_rewalk(mas, save_point);
> > +			goto retry;
> > +		}
> > -		if (pivot >= mas->max)
> > +		if (mas_is_none(mas))
> >   			return NULL;
> > -		mas->index = pivot + 1;
> > -		mas->offset++;
> > +		mas->offset = 0;
> > +		mas->index = mas->min;
> > +		node = mas_mn(mas);
> > +		type = mte_node_type(mas->node);
> > +		pivots = ma_pivots(node, type);
> >   	}
> > -	pivot = mas_logical_pivot(mas, pivots, mas->offset, type);
> > +	slots = ma_slots(node, type);
> > +	mas->last = mas_logical_pivot(mas, pivots, mas->offset, type);
> >   	entry = mas_slot(mas, slots, mas->offset);
> > -	if (ma_dead_node(node))
> > -		return NULL;
> > +	if (unlikely(mas_rewalk_if_dead(mas, node, save_point)))
> > +		goto retry;
> > -	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
> > @@ -4774,47 +4773,18 @@ static inline void mas_rewalk(struct ma_state *mas, unsigned long index)
> >   static inline void *mas_next_entry(struct ma_state *mas, unsigned long limit)
> >   {
> >   	void *entry = NULL;
> > -	struct maple_node *node;
> > -	unsigned long last;
> > -	enum maple_type mt;
> >   	if (mas->last >= limit)
> >   		return NULL;
> > -	last = mas->last;
> > -retry:
> > -	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->last >= limit)))
> > -			return NULL;
> > +	entry = mas_next_slot_limit(mas, limit);
> > +	if (entry)
> > +		return entry;
> > -next_node:
> > -		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);
> > -	}
> > +	if (mas_is_none(mas))
> > +		return NULL;
> > -	return NULL;
> > +	return mas_next_slot_limit(mas, limit);
> >   }
> >   /*
> > @@ -4845,10 +4815,8 @@ static inline void *mas_prev_nentry(struct ma_state *mas, unsigned long limit,
> >   	slots = ma_slots(mn, mt);
> >   	pivots = ma_pivots(mn, mt);
> >   	count = ma_data_end(mn, mt, pivots, mas->max);
> > -	if (unlikely(ma_dead_node(mn))) {
> > -		mas_rewalk(mas, index);
> > +	if (unlikely(mas_rewalk_if_dead(mas, mn, index)))
> >   		goto retry;
> > -	}
> >   	offset = mas->offset - 1;
> >   	if (offset >= mt_slots[mt])
> > @@ -4861,10 +4829,8 @@ static inline void *mas_prev_nentry(struct ma_state *mas, unsigned long limit,
> >   		pivot = pivots[offset];
> >   	}
> > -	if (unlikely(ma_dead_node(mn))) {
> > -		mas_rewalk(mas, index);
> > +	if (unlikely(mas_rewalk_if_dead(mas, mn, index)))
> >   		goto retry;
> > -	}
> >   	while (offset && !mas_slot(mas, slots, offset)) {
> >   		pivot = pivots[--offset];
> > @@ -4881,10 +4847,8 @@ static inline void *mas_prev_nentry(struct ma_state *mas, unsigned long limit,
> >   	min = mas_safe_min(mas, pivots, offset);
> >   	entry = mas_slot(mas, slots, offset);
> > -	if (unlikely(ma_dead_node(mn))) {
> > -		mas_rewalk(mas, index);
> > +	if (unlikely(mas_rewalk_if_dead(mas, mn, index)))
> >   		goto retry;
> > -	}
> >   	mas->offset = offset;
> >   	mas->last = pivot;