Re: [PATCH] maple_tree: Fix mas_spanning_rebalance() on insufficient data

[Mike Rapoport <rppt@kernel.org>]

On Fri, Dec 16, 2022 at 06:53:15PM +0000, Liam Howlett wrote:
> Mike Rapoport contacted me off-list with a regression in running criu.
> Periodic tests fail with an RCU stall during execution.  Although rare,
> it is possible to hit this with other uses so this patch should be
> backported to fix the regression.
> 
> An insufficient node was causing an out-of-bounds access on the node in
> mas_leaf_max_gap().  The cause was the faulty detection of the new node
> being a root node when overwriting many entries at the end of the tree.
> 
> Fix the detection of a new root and ensure there is sufficient data
> prior to entering the spanning rebalance loop.
> 
> Add a testcase to the maple tree test suite for this issue.
> 
> Cc: Andrei Vagin <avagin@gmail.com>
> Cc: usama.anjum@collabora.com
> Reported-by: Mike Rapoport <rppt@kernel.org>
> Fixes: 54a611b60590 ("Maple Tree: add new data structure")
> Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com>

Tested-by: Mike Rapoport <rppt@kernel.org>

> ---
>  lib/maple_tree.c      |  4 +++-
>  lib/test_maple_tree.c | 23 +++++++++++++++++++++++
>  2 files changed, 26 insertions(+), 1 deletion(-)
> 
> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> index fe3947b80069..26e2045d3cda 100644
> --- a/lib/maple_tree.c
> +++ b/lib/maple_tree.c
> @@ -2994,7 +2994,9 @@ static int mas_spanning_rebalance(struct ma_state *mas,
>  	mast->free = &free;
>  	mast->destroy = &destroy;
>  	l_mas.node = r_mas.node = m_mas.node = MAS_NONE;
> -	if (!(mast->orig_l->min && mast->orig_r->max == ULONG_MAX) &&
> +
> +	/* Check if this is not root and has sufficient data.  */
> +	if (((mast->orig_l->min != 0) || (mast->orig_r->max != ULONG_MAX)) &&
>  	    unlikely(mast->bn->b_end <= mt_min_slots[mast->bn->type]))
>  		mast_spanning_rebalance(mast);
>  
> diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c
> index f425f169ef08..497fc93ccf9e 100644
> --- a/lib/test_maple_tree.c
> +++ b/lib/test_maple_tree.c
> @@ -2498,6 +2498,25 @@ static noinline void check_dup(struct maple_tree *mt)
>  	}
>  }
>  
> +static noinline void check_bnode_min_spanning(struct maple_tree *mt)
> +{
> +	int i = 50;
> +	MA_STATE(mas, mt, 0, 0);
> +
> +	mt_set_non_kernel(9999);
> +	mas_lock(&mas);
> +	do {
> +		mas_set_range(&mas, i*10, i*10+9);
> +		mas_store(&mas, check_bnode_min_spanning);
> +	} while (i--);
> +
> +	mas_set_range(&mas, 240, 509);
> +	mas_store(&mas, NULL);
> +	mas_unlock(&mas);
> +	mas_destroy(&mas);
> +	mt_set_non_kernel(0);
> +}
> +
>  static DEFINE_MTREE(tree);
>  static int maple_tree_seed(void)
>  {
> @@ -2742,6 +2761,10 @@ static int maple_tree_seed(void)
>  	check_dup(&tree);
>  	mtree_destroy(&tree);
>  
> +	mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
> +	check_bnode_min_spanning(&tree);
> +	mtree_destroy(&tree);
> +
>  #if defined(BENCH)
>  skip:
>  #endif
> -- 
> 2.35.1

-- 
Sincerely yours,
Mike.