[PATCH v2 4/5] maple_tree: refine mas_root_expand() on storing NULL

[Liam R. Howlett]

* Wei Yang <richard.weiyang at gmail.com> [241017 09:46]:
> Currently, when storing NULL on mas_root_expand(), the behavior could be
> improved.
> 
> For example possible cases are:
> 
>   * store NULL at any range result a new node
>   * store NULL at range [m, n] where m > 0 to a single entry tree result
>     a new node with range [m, n] set to NULL
>   * store NULL at range [m, n] where m > 0 to an empty tree result
>     consecutive NULL slot
> 
> This patch tries to improve in:
> 
>   * memory efficient by setting to empty tree instead of using a node
>   * remove the possibility of consecutive NULL slot which will prohibit
>     extended null in later operation
> 
> Signed-off-by: Wei Yang <richard.weiyang at gmail.com>
> CC: Liam R. Howlett <Liam.Howlett at Oracle.com>
> CC: Sidhartha Kumar <sidhartha.kumar at oracle.com>
> CC: Lorenzo Stoakes <lorenzo.stoakes at oracle.com>
> ---
>  lib/maple_tree.c | 18 ++++++++++++++++++
>  1 file changed, 18 insertions(+)
> 
> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> index a90c29156fe2..15d2124acc36 100644
> --- a/lib/maple_tree.c
> +++ b/lib/maple_tree.c
> @@ -3335,6 +3335,24 @@ static inline void mas_root_expand(struct ma_state *mas, void *entry)
>  	unsigned long *pivots;
>  	int slot = 0;
>  
> +	if (!entry) {
> +		/*
> +		 * We come here in two cases:
> +		 * 1. This is an empty tree
> +		 * 2. This is a single entry tree with range [0, 0]
> +		 *
> +		 * If this is an empty tree, the result should still be an
> +		 * empty tree no matter what the range is.
> +		 *
> +		 * If this is a single entry tree, we should set it to an
> +		 * empty tree if the range cover [0, 0]. Otherwise, we don't
> +		 * need to change it.
> +		 */
> +		if (!mas->index && contents)
> +			rcu_assign_pointer(mas->tree->ma_root, NULL);
> +		return;
> +	}
> +

This fix should be done in mas_store_root(), which will probably reduce
or remove your lengthy comment.

mas_root_expand() should... expand the root, and this isn't what is
happening now.

>  	node = mas_pop_node(mas);
>  	pivots = ma_pivots(node, type);
>  	slots = ma_slots(node, type);
> -- 
> 2.34.1
>