nack
* Wei Yang <richard.weiyang@xxxxxxxxx> [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@xxxxxxxxx>
> CC: Liam R. Howlett <Liam.Howlett@xxxxxxxxxx>
> CC: Sidhartha Kumar <sidhartha.kumar@xxxxxxxxxx>
> CC: Lorenzo Stoakes <lorenzo.stoakes@xxxxxxxxxx>
> ---
> 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
>
