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

[Vlastimil Babka]

From: "Liam R. Howlett" <liam.howl...@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.howl...@oracle.com>
Signed-off-by: Vlastimil Babka <vba...@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;
+
+               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