[PATCH] maple_tree: fix alloc node fail issue

[Jiazi Li]

On Tue, Jun 25, 2024 at 10:10:33AM -0400, Liam R. Howlett wrote:
> * Jiazi Li <jqqlijiazi at gmail.com> [240625 03:08]:
> > On Mon, Jun 24, 2024 at 11:38:34AM -0400, Liam R. Howlett wrote:
> > > 
> > > * Jiazi Li <jqqlijiazi at gmail.com> [240624 08:01]:
> > > > In the following code, the second call to the mas_node_count will
> > > > return -ENOMEM:
> > > > 
> > > > 	mas_node_count(&maple_tree, 31);
> > > > 	mas_node_count(&maple_tree, 62);
> > > 
> > > This implies mas_node_count() takes a maple tree, but it takes a maple
> > > state.
> > > 
> > > > 
> > > > This is because get a node with node_count is MAPLE_ALLOC_SLOTS in
> > > > while loop of mas_alloc_nodes. And this will result in max_req
> > > > is zero in next loop.
> > > 
> > > This description could use some work on clarity.
> > > 
> > > Please provide a testcase that reproduces the issue that will go into
> > > tools/testing/radix-tree/maple.c  It looks like it should go around line
> > > 460.
> > > 
> > > 
> > Ok, thanks for your suggestion.
> 
> Thanks for your patch and debugging!
> 
> > > > Signed-off-by: Jiazi Li <jiazi.li at transsion.com>
> > > 
> > > Your Signed-off-by does not match the from address.
> > > 
> > Sorry, I will use from address to signed-off in the future.
> > > Please add a Fixes tag.
> > > 
> > Ok.
> > > > ---
> > > >  lib/maple_tree.c | 4 +++-
> > > >  1 file changed, 3 insertions(+), 1 deletion(-)
> > > > 
> > > > diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> > > > index aa3a5df15b8e..82c236972115 100644
> > > > --- a/lib/maple_tree.c
> > > > +++ b/lib/maple_tree.c
> > > > @@ -1272,7 +1272,9 @@ static inline void mas_alloc_nodes(struct ma_state *mas, gfp_t gfp)
> > > >  
> > > >  		node->node_count += count;
> > > >  		allocated += count;
> > > > -		node = node->slot[0];
> > > > +		do {
> > > > +			node = node->slot[0];
> > > > +		} while (unlikely(node->node_count == MAPLE_ALLOC_SLOTS));
> > > 
> > > Please change this to an 'if' statement as it would be more clear what's
> > > going on.
> > > 
> > I think change this to an 'if', the new node we get may still be full.
> > For example, the following code:
> > 	mas_alloc_node(&mas, 61);
> > 	mas_alloc_node(&mas, 92);//will failed
> 
> Prior to entering this loop, there is a check for the
> mas->alloc->node_count == MAPLE_ALLOC_SLOTS case, which might avoid this
> failure?
I conducted an experiment, but it cannot be avoided.
Below, I will try to describe the process of failure:
1. alloc 61 maple_node
2. mas->alloc points node1, which points 30 other nodes
3. node1->slot[0] points to node2, which also points 30 other nodes
4. currently, there are 61 nodes, both node1 and node2 are full
5. alloc 92 nodes, there are already 61 nodes, need alloc 31
6. in mas_alloc_nodes, before while loop, find node1 is full, alloc new
node node0, node0->slot[0] point to node1, enter while loop, need alloc
30
7. in first loop, node0->slot could store 29 nodes, so still need 1 node
in second loop
8. node0->slot[0] is node1, which is full, node1->slot[0] is node2,
which also full.
9. a simple 'if' statement could not get a non-full node

> 
> It should be trivial to test this as well with a test case when you add
> your other tests.  I'd rather the simple 'if' statement, if it works.
> 
> I insist on having tests for any bugs we find so that they never
> reappear in future modifications.  I feel this is very important so if
> you see anything to add to testing, then please add them.  So, please
> add this potential failure as well?
> 
> Regards,
> Liam