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

[Wei Yang]

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