[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-Id: <20250901-maple-sheaves-v1-11-d6a1166b53f2@suse.cz>
Date: Mon, 01 Sep 2025 13:09:01 +0200
From: Vlastimil Babka <vbabka@...e.cz>
To: "Liam R. Howlett" <Liam.Howlett@...cle.com>,
Matthew Wilcox <willy@...radead.org>,
Lorenzo Stoakes <lorenzo.stoakes@...cle.com>, Jann Horn <jannh@...gle.com>,
Pedro Falcato <pfalcato@...e.de>, Suren Baghdasaryan <surenb@...gle.com>
Cc: Harry Yoo <harry.yoo@...cle.com>,
Andrew Morton <akpm@...ux-foundation.org>, maple-tree@...ts.infradead.org,
linux-mm@...ck.org, linux-fsdevel@...r.kernel.org,
linux-kernel@...r.kernel.org, Vlastimil Babka <vbabka@...e.cz>,
"Liam R. Howlett" <Liam.Howlett@...cle.com>
Subject: [PATCH 11/12] maple_tree: Add single node allocation support to
maple state
From: "Liam R. Howlett" <Liam.Howlett@...cle.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@...cle.com>
Signed-off-by: Vlastimil Babka <vbabka@...e.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 cfe80c50a97e3118eefc24275fbcd2eec5e6e6e8..61a322f945c28f5c3297c506923f00bcce5c7bca 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -1095,16 +1095,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;
}
@@ -1115,9 +1122,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;
@@ -5380,8 +5412,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);
@@ -6079,7 +6114,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 da3e03d73b52162dab6fa5c368ad7b71b9e58521..89da991e12cd97e44971757ddc105ef46c68ea4c 100644
--- a/tools/testing/radix-tree/maple.c
+++ b/tools/testing/radix-tree/maple.c
@@ -35095,10 +35095,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
Powered by blists - more mailing lists