[RFC PATCH v6.6] maple_tree: Fix mas_prealloc() reset

[Suren Baghdasaryan]

On Mon, Apr 28, 2025 at 12:02 PM Liam R. Howlett
<Liam.Howlett at oracle.com> wrote:
>
> A previously used maple state may not be in the correct state for the
> preallocation to correctly calculate the number of nodes necessary for the
> configured store operation.
>
> The user visible effect of which is warning that there are no nodes
> allocated followed by a crash when there is a null pointer dereference
> shortly after.
>
> The NULL pointer dereference has been reported to happen when a vma
> iterator is used to preallocate after walking to a leaf node but then
> requesting to preallocate for a store across node boundaries (in v6.6.
> of the kernel).  The altered range means that there may not been enough
> nodes as the maple state has been incorrectly configured.  A critical
> step is that the vma iterator then detects the misconfigured maple state
> and resets, thus ensuring the tree is not corrupted - but ultimately
> causes a failure when there are no nodes left.
>
> Detect a misconfigured maple state in the mas_preallocate() code by
> examining the current location and planned write to ensure a reset is
> done if required.  The performance impacts are minimal and within the
> noise in initial testing.

With this fix applied I can still see the issue using Hailong's
reproducers, both the userspace one that he shared over the weekend
and the one posted at
https://lore.kernel.org/all/1652f7eb-a51b-4fee-8058-c73af63bacd1@oppo.com/

>
> Reported-by: Zhaoyang Huang <zhaoyang.huang at unisoc.com>
> Reported-by: Hailong Liu <hailong.liu at oppo.com>
> Fixes: fec29364348fe ("maple_tree: reduce resets during store setup")
> Link: https://lore.kernel.org/all/1652f7eb-a51b-4fee-8058-c73af63bacd1@oppo.com/
> Cc: Lorenzo Stoakes <lorenzo.stoakes at oracle.com>
> Cc: Suren Baghdasaryan <surenb at google.com>
> Cc: Hailong Liu <hailong.liu at oppo.com>
> Cc: zhangpeng.00 at bytedance.com <zhangpeng.00 at bytedance.com>
> Cc: Steve Kang <Steve.Kang at unisoc.com>
> Cc: Matthew Wilcox <willy at infradead.org>
> Signed-off-by: Liam R. Howlett <Liam.Howlett at oracle.com>
> ---
>  lib/maple_tree.c | 35 +++++++++++++++++++++++++++++++----
>  1 file changed, 31 insertions(+), 4 deletions(-)
>
> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> index 4eda949063602..17af9073494f5 100644
> --- a/lib/maple_tree.c
> +++ b/lib/maple_tree.c
> @@ -5350,6 +5350,8 @@ static inline void mte_destroy_walk(struct maple_enode *enode,
>
>  static void mas_wr_store_setup(struct ma_wr_state *wr_mas)
>  {
> +       unsigned char node_size;
> +
>         if (!mas_is_active(wr_mas->mas)) {
>                 if (mas_is_start(wr_mas->mas))
>                         return;
> @@ -5372,17 +5374,42 @@ static void mas_wr_store_setup(struct ma_wr_state *wr_mas)
>          * writes within this node.  This is to stop partial walks in
>          * mas_prealloc() from being reset.
>          */
> +
> +       /* Leaf root node is safe */
> +       if (mte_is_root(wr_mas->mas->node))
> +               return;
> +
> +       /* Cannot span beyond this node */
>         if (wr_mas->mas->last > wr_mas->mas->max)
>                 goto reset;
>
> -       if (wr_mas->entry)
> +       /* Cannot span before this node */
> +       if (wr_mas->mas->index < wr_mas->mas->min)
> +               goto reset;
> +
> +       wr_mas->type = mte_node_type(wr_mas->mas->node);
> +       /* unfinished walk is okay */
> +       if (!ma_is_leaf(wr_mas->type))
>                 return;
>
> -       if (mte_is_leaf(wr_mas->mas->node) &&
> -           wr_mas->mas->last == wr_mas->mas->max)
> +       /* Leaf node that ends in 0 means a spanning store */
> +       if (!wr_mas->entry &&
> +           (wr_mas->mas->last == wr_mas->mas->max))
>                 goto reset;
>
> -       return;
> +       mas_wr_node_walk(wr_mas);
> +       if (wr_mas->r_min == wr_mas->mas->index &&
> +           wr_mas->r_max == wr_mas->mas->last)
> +               return; /* exact fit, no allocations */
> +
> +       wr_mas->slots = ma_slots(wr_mas->node, wr_mas->type);
> +       mas_wr_end_piv(wr_mas);
> +       node_size = mas_wr_new_end(wr_mas);
> +       if (node_size >= mt_slots[wr_mas->type])
> +               goto reset; /* Not going to fit */
> +
> +       if (node_size - 1 > mt_min_slots[wr_mas->type])
> +               return; /* sufficient and will fit */
>
>  reset:
>         mas_reset(wr_mas->mas);
> --
> 2.47.2
>