[PATCH] maple_tree: fix alloc node fail issue

[Liam R. Howlett]

* Jiazi Li <jqqlijiazi at gmail.com> [240625 23:26]:
> 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

Thank you.

Please include this test case as well.

> 
> > 
> > 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