| Message ID | 20241015233909.23592-3-richard.weiyang@gmail.com (mailing list archive) |
|---|---|
| State | New |
| Headers | show |
| Series | fix mas_new_root() | expand |
nack * Wei Yang <richard.weiyang@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@gmail.com> > CC: Liam R. Howlett <Liam.Howlett@Oracle.com> > CC: Sidhartha Kumar <sidhartha.kumar@oracle.com> > CC: Lorenzo Stoakes <lorenzo.stoakes@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 >
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);
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@gmail.com> CC: Liam R. Howlett <Liam.Howlett@Oracle.com> CC: Sidhartha Kumar <sidhartha.kumar@oracle.com> CC: Lorenzo Stoakes <lorenzo.stoakes@oracle.com> --- lib/maple_tree.c | 9 --------- 1 file changed, 9 deletions(-)