* Peng Zhang <zhangpeng.00@xxxxxxxxxxxxx> [230310 14:03]:
>
> 在 2023/3/11 02:27, Liam R. Howlett 写道:
> > * Peng Zhang <zhangpeng.00@xxxxxxxxxxxxx> [230310 09:09]:
> > > There is a concurrency bug that may cause the wrong value to be loaded
> > > when a CPU is modifying the maple tree.
> > >
> > > CPU1:
> > > mtree_insert_range()
> > > mas_insert()
> > > mas_store_root()
> > > ...
> > > mas_root_expand()
> > > ...
> > > rcu_assign_pointer(mas->tree->ma_root, mte_mk_root(mas->node));
> > > ma_set_meta(node, maple_leaf_64, 0, slot); <---IP
> > >
> > > CPU2:
> > > mtree_load()
> > > mtree_lookup_walk()
> > > ma_data_end();
> > >
> > > When CPU1 is about to execute the instruction pointed to by IP,
> > > the ma_data_end() executed by CPU2 may return the wrong end position,
> > > which will cause the value loaded by mtree_load() to be wrong.
> > >
> > > An example of triggering the bug:
> > >
> > > Add mdelay(100) between rcu_assign_pointer() and ma_set_meta() in
> > > mas_root_expand().
> > >
> > > static DEFINE_MTREE(tree);
> > > int work(void *p) {
> > > unsigned long val;
> > > for (int i = 0 ; i< 30; ++i) {
> > > val = (unsigned long)mtree_load(&tree, 8);
> > > mdelay(5);
> > > pr_info("%lu",val);
> > > }
> > > return 0;
> > > }
> > >
> > > mt_init_flags(&tree, MT_FLAGS_USE_RCU);
> > > mtree_insert(&tree, 0, (void*)12345, GFP_KERNEL);
> > > run_thread(work)
> > > mtree_insert(&tree, 1, (void*)56789, GFP_KERNEL);
> > >
> > > In RCU mode, mtree_load() should always return the value before or after
> > > the data structure is modified, and in this example mtree_load(&tree, 8)
> > > may return 56789 which is not expected, it should always return NULL.
> > > Fix it by put ma_set_meta() before rcu_assign_pointer().
> > Are you able to write a test case for this issue? I understand it's a
> > race so it may be difficult to catch.
> Yes it's hard to catch. I'll try to think of a test case next week.
> It is difficult because of the need to expand the competitive area.
This should have a fixes tag as well.
Fixes: 54a611b60590 ("Maple Tree: add new data structure")
> >
> > > Signed-off-by: Peng Zhang <zhangpeng.00@xxxxxxxxxxxxx>
> > Reviewed-by: Liam R. Howlett <Liam.Howlett@xxxxxxxxxx>
> >
> > > ---
> > > lib/maple_tree.c | 3 +--
> > > 1 file changed, 1 insertion(+), 2 deletions(-)
> > >
> > > diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> > > index 4d15202a0692..de43ff19da72 100644
> > > --- a/lib/maple_tree.c
> > > +++ b/lib/maple_tree.c
> > > @@ -3635,10 +3635,9 @@ static inline int mas_root_expand(struct ma_state *mas, void *entry)
> > > slot++;
> > > mas->depth = 1;
> > > mas_set_height(mas);
> > > -
> > > + ma_set_meta(node, maple_leaf_64, 0, slot);
> > > /* swap the new root into the tree */
> > > rcu_assign_pointer(mas->tree->ma_root, mte_mk_root(mas->node));
> > > - ma_set_meta(node, maple_leaf_64, 0, slot);
> > > return slot;
> > > }
> > > --
> > > 2.20.1
> > >
