[PATCH 2/2] maple_tree: one single entry couldn't represent the whole range

[Liam R. Howlett]

nack

* Wei Yang <richard.weiyang at gmail.com> [241015 19:39]:
> The current behavior of overwriting the whole range with NULL is not
> correct.
> 
> For example, we store range [0, ULONG_MAX] to a new tree:
> 
>   mas_set_range(&ms, 0, ULONG_MAX);
>   mas_store(&ms, NULL);
>   mt_dump(mt, mt_dump_dec);
> 
> The dump result shows:
> 
>   maple_tree(0x7ffd9506e350) flags 7, height 1 root 0x61500000010e
>   0-18446744073709551615: node 0x615000000100 depth 0 type 1 parent 0x7ffd9506e351 contents: (nil) 18446744073709551615 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil)
>     0-18446744073709551615: (nil)
> 
> But if we do the store on a tree with value:
> 
>   mas_set_range(&ms, 5, ULONG_MAX);
>   mas_store(&ms, NULL);
>   mas_set_range(&ms, 0, ULONG_MAX);
>   mas_store(&ms, NULL);
>   mt_dump(mt, mt_dump_dec);
> 
> The dump result shows:
> 
>   maple_tree(0x7ffd9506e350) flags 3, height 0 root (nil)
>   0: (nil)
> 
> We can see even we write the same range, these two trees are different.
> The second tree only has an entry represent range [0, 0] instead of range
> [0, ULONG_MAX], which is not correct.
> 
> The good news is it doesn't affect user, because mtree_load() still
> return NULL for each index.
> 
> Let's create a node to represent the entire range even for NULL entry.
> 
> Fixes: 54a611b60590 ("Maple Tree: add new data structure")
> 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 | 9 ---------
>  1 file changed, 9 deletions(-)
> 
> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> index 3a12866a4a89..5dfc589a8cde 100644
> --- a/lib/maple_tree.c
> +++ b/lib/maple_tree.c
> @@ -3594,14 +3594,6 @@ static inline void mas_new_root(struct ma_state *mas, void *entry)
>  	void __rcu **slots;
>  	unsigned long *pivots;
>  
> -	if (!entry) {
> -		mas->depth = 0;
> -		mas_set_height(mas);
> -		rcu_assign_pointer(mas->tree->ma_root, entry);
> -		mas->status = ma_start;
> -		goto done;
> -	}
> -
>  	node = mas_pop_node(mas);
>  	pivots = ma_pivots(node, type);
>  	slots = ma_slots(node, type);
> @@ -3614,7 +3606,6 @@ static inline void mas_new_root(struct ma_state *mas, void *entry)
>  	mas_set_height(mas);
>  	rcu_assign_pointer(mas->tree->ma_root, mte_mk_root(mas->node));
>  
> -done:
>  	if (xa_is_node(root))
>  		mte_destroy_walk(root, mas->tree);
>  
> -- 
> 2.34.1
>