[PATCH v4 4/5] maple_tree: refine mas_store_root() on storing NULL

[Liam R. Howlett]

* Wei Yang <richard.weiyang at gmail.com> [241018 22:37]:
> Currently, when storing NULL on mas_store_root(), 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 
>   * it allows for multiple NULL entries by expanding root to
>     store NULLs to an empty tree
> 
> 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>

Reviewed-by: Liam R. Howlett <Liam.Howlett at Oracle.com>

> 
> ---
> v3: move change into mas_store_root()
> v4: add a comment and simplify the logic a little
>     adjust the change log a little
> ---
>  lib/maple_tree.c | 13 ++++++++++++-
>  1 file changed, 12 insertions(+), 1 deletion(-)
> 
> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> index 2226e77c00cb..1205a5208cfe 100644
> --- a/lib/maple_tree.c
> +++ b/lib/maple_tree.c
> @@ -3439,9 +3439,20 @@ static inline void mas_root_expand(struct ma_state *mas, void *entry)
>  	return;
>  }
>  
> +/*
> + * mas_store_root() - Storing value into root.
> + * @mas: The maple state
> + * @entry: The entry to store.
> + *
> + * There is no root node now and we are storing a value into the root - this
> + * function either assigns the pointer or expands into a node.
> + */
>  static inline void mas_store_root(struct ma_state *mas, void *entry)
>  {
> -	if (likely((mas->last != 0) || (mas->index != 0)))
> +	if (!entry) {
> +		if (!mas->index)
> +			rcu_assign_pointer(mas->tree->ma_root, NULL);
> +	} else if (likely((mas->last != 0) || (mas->index != 0)))
>  		mas_root_expand(mas, entry);
>  	else if (((unsigned long) (entry) & 3) == 2)
>  		mas_root_expand(mas, entry);
> -- 
> 2.34.1
>