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

[Peng Zhang <perlyzhang@gmail.com>]

在 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.
> +	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);
>   }
>   
>   /*