linux-kernel - Re: [PATCH 3/4] maple_tree: Fix a potential concurrency bug in RCU mode

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <20230310192920.dsmd3plhwqgma6ak@revolver>
Date:   Fri, 10 Mar 2023 14:29:20 -0500
From:   "Liam R. Howlett" <Liam.Howlett@...cle.com>
To:     Peng Zhang <zhangpeng.00@...edance.com>
Cc:     linux-mm@...ck.org, linux-kernel@...r.kernel.org,
        maple-tree@...ts.infradead.org
Subject: Re: [PATCH 3/4] maple_tree: Fix a potential concurrency bug in RCU
 mode

* Peng Zhang <zhangpeng.00@...edance.com> [230310 14:03]:
> 
> 在 2023/3/11 02:27, Liam R. Howlett 写道:
> > * Peng Zhang <zhangpeng.00@...edance.com> [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@...edance.com>
> > Reviewed-by: Liam R. Howlett <Liam.Howlett@...cle.com>
> > 
> > > ---
> > >   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
> > >