The quilt patch titled
Subject: maple_tree: one single entry couldn't represent the whole range
has been removed from the -mm tree. Its filename was
maple_tree-one-single-entry-couldnt-represent-the-whole-range.patch
This patch was dropped because an updated version will be issued
------------------------------------------------------
From: Wei Yang <richard.weiyang@xxxxxxxxx>
Subject: maple_tree: one single entry couldn't represent the whole range
Date: Tue, 15 Oct 2024 23:39:09 +0000
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.
Link: https://lkml.kernel.org/r/20241015233909.23592-3-richard.weiyang@xxxxxxxxx
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>
Signed-off-by: Andrew Morton <akpm@xxxxxxxxxxxxxxxxxxxx>
---
lib/maple_tree.c | 9 ---------
1 file changed, 9 deletions(-)
--- a/lib/maple_tree.c~maple_tree-one-single-entry-couldnt-represent-the-whole-range
+++ a/lib/maple_tree.c
@@ -3670,14 +3670,6 @@ static inline void mas_new_root(struct m
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);
@@ -3690,7 +3682,6 @@ static inline void mas_new_root(struct m
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);
_
Patches currently in -mm which might be from richard.weiyang@xxxxxxxxx are
maple_tree-i-is-always-less-than-or-equal-to-mas_end.patch
maple_tree-goto-complete-directly-on-a-pivot-of-0.patch
maple_tree-remove-maple_big_nodeparent.patch
maple_tree-memset-maple_big_node-as-a-whole.patch
maple_tree-root-node-could-be-handled-by-p_slot-too.patch
maple_tree-clear-request_count-for-new-allocated-one.patch
maple_tree-total-is-not-changed-for-nomem_one-case.patch
maple_tree-simplify-mas_push_node.patch
maple_tree-calculate-new_end-when-needed.patch
maple_tree-remove-sanity-check-from-mas_wr_slot_store.patch
