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

[Peng Zhang <perlyzhang@gmail.com>]

在 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.
> +
>   	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;