Re: [PATCH v8 22/23] maple_tree: Add single node allocation support to maple state

[Suren Baghdasaryan <surenb@google.com>]

On Wed, Sep 10, 2025 at 1:01 AM Vlastimil Babka <vbabka@suse.cz> wrote:
>
> From: "Liam R. Howlett" <Liam.Howlett@Oracle.com>
>
> The fast path through a write will require replacing a single node in
> the tree.  Using a sheaf (32 nodes) is too heavy for the fast path, so
> special case the node store operation by just allocating one node in the
> maple state.
>
> Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>
> Signed-off-by: Vlastimil Babka <vbabka@suse.cz>
> ---
>  include/linux/maple_tree.h       |  4 +++-
>  lib/maple_tree.c                 | 47 +++++++++++++++++++++++++++++++++++-----
>  tools/testing/radix-tree/maple.c |  9 ++++++--
>  3 files changed, 51 insertions(+), 9 deletions(-)
>
> diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h
> index 166fd67e00d882b1e6de1f80c1b590bba7497cd3..562a1e9e5132b5b1fa8f8402a7cadd8abb65e323 100644
> --- a/include/linux/maple_tree.h
> +++ b/include/linux/maple_tree.h
> @@ -443,6 +443,7 @@ struct ma_state {
>         unsigned long min;              /* The minimum index of this node - implied pivot min */
>         unsigned long max;              /* The maximum index of this node - implied pivot max */
>         struct slab_sheaf *sheaf;       /* Allocated nodes for this operation */
> +       struct maple_node *alloc;       /* allocated nodes */
>         unsigned long node_request;
>         enum maple_status status;       /* The status of the state (active, start, none, etc) */
>         unsigned char depth;            /* depth of tree descent during write */
> @@ -491,8 +492,9 @@ struct ma_wr_state {
>                 .status = ma_start,                                     \
>                 .min = 0,                                               \
>                 .max = ULONG_MAX,                                       \
> -               .node_request= 0,                                       \
>                 .sheaf = NULL,                                          \
> +               .alloc = NULL,                                          \
> +               .node_request= 0,                                       \
>                 .mas_flags = 0,                                         \
>                 .store_type = wr_invalid,                               \
>         }
> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> index a3fcb20227e506ed209554cc8c041a53f7ef4903..a912e6a1d4378e72b967027b60f8f564476ad14e 100644
> --- a/lib/maple_tree.c
> +++ b/lib/maple_tree.c
> @@ -1073,16 +1073,23 @@ static int mas_ascend(struct ma_state *mas)
>   *
>   * Return: A pointer to a maple node.
>   */
> -static inline struct maple_node *mas_pop_node(struct ma_state *mas)
> +static __always_inline struct maple_node *mas_pop_node(struct ma_state *mas)
>  {
>         struct maple_node *ret;
>
> +       if (mas->alloc) {
> +               ret = mas->alloc;
> +               mas->alloc = NULL;
> +               goto out;
> +       }
> +
>         if (WARN_ON_ONCE(!mas->sheaf))
>                 return NULL;
>
>         ret = kmem_cache_alloc_from_sheaf(maple_node_cache, GFP_NOWAIT, mas->sheaf);
> -       memset(ret, 0, sizeof(*ret));
>
> +out:
> +       memset(ret, 0, sizeof(*ret));
>         return ret;
>  }
>
> @@ -1093,9 +1100,34 @@ static inline struct maple_node *mas_pop_node(struct ma_state *mas)
>   */
>  static inline void mas_alloc_nodes(struct ma_state *mas, gfp_t gfp)
>  {
> -       if (unlikely(mas->sheaf)) {
> -               unsigned long refill = mas->node_request;
> +       if (!mas->node_request)
> +               return;
> +
> +       if (mas->node_request == 1) {
> +               if (mas->sheaf)
> +                       goto use_sheaf;

Hmm, I don't get the above logic. One node is requested and instead of
using possibly available mas->alloc, we jump to using mas->sheaf and
freeing mas->alloc... That does not sound efficient. What am I
missing?

> +
> +               if (mas->alloc)
> +                       return;
>
> +               mas->alloc = mt_alloc_one(gfp);
> +               if (!mas->alloc)
> +                       goto error;
> +
> +               mas->node_request = 0;
> +               return;
> +       }
> +
> +use_sheaf:
> +       if (unlikely(mas->alloc)) {
> +               kfree(mas->alloc);
> +               mas->alloc = NULL;
> +       }
> +
> +       if (mas->sheaf) {
> +               unsigned long refill;
> +
> +               refill = mas->node_request;
>                 if(kmem_cache_sheaf_size(mas->sheaf) >= refill) {
>                         mas->node_request = 0;
>                         return;
> @@ -5180,8 +5212,11 @@ void mas_destroy(struct ma_state *mas)
>         mas->node_request = 0;
>         if (mas->sheaf)
>                 mt_return_sheaf(mas->sheaf);
> -
>         mas->sheaf = NULL;
> +
> +       if (mas->alloc)
> +               kfree(mas->alloc);
> +       mas->alloc = NULL;
>  }
>  EXPORT_SYMBOL_GPL(mas_destroy);
>
> @@ -5816,7 +5851,7 @@ bool mas_nomem(struct ma_state *mas, gfp_t gfp)
>                 mas_alloc_nodes(mas, gfp);
>         }
>
> -       if (!mas->sheaf)
> +       if (!mas->sheaf && !mas->alloc)
>                 return false;
>
>         mas->status = ma_start;
> diff --git a/tools/testing/radix-tree/maple.c b/tools/testing/radix-tree/maple.c
> index 72a8fe8e832a4150c6567b711768eba6a3fa6768..83260f2efb1990b71093e456950069c24d75560e 100644
> --- a/tools/testing/radix-tree/maple.c
> +++ b/tools/testing/radix-tree/maple.c
> @@ -35085,10 +35085,15 @@ static unsigned char get_vacant_height(struct ma_wr_state *wr_mas, void *entry)
>
>  static int mas_allocated(struct ma_state *mas)
>  {
> +       int total = 0;
> +
> +       if (mas->alloc)
> +               total++;
> +
>         if (mas->sheaf)
> -               return kmem_cache_sheaf_size(mas->sheaf);
> +               total += kmem_cache_sheaf_size(mas->sheaf);
>
> -       return 0;
> +       return total;
>  }
>  /* Preallocation testing */
>  static noinline void __init check_prealloc(struct maple_tree *mt)
>
> --
> 2.51.0
>