[PATCH 00/18] Introduce a store type enum for the Maple tree

[PATCH 00/18] Introduce a store type enum for the Maple tree

[Sidhartha Kumar]

================================ OVERVIEW ================================

This series implements two work items[1]: "aligning mas_store_gfp() with
mas_preallocate()" and "enum for store type". 

mas_store_gfp() is modified to preallocate nodes. This simplies many of
the write helper functions by allowing them to use mas_store_gfp() rather
than open coding node allocation and error handling.

The enum defines the following store types:

enum store_type {
	wr_invalid,
	wr_new_root,
	wr_store_root,
	wr_exact_fit,
	wr_spanning_store,
	wr_split_store,
	wr_rebalance,
	wr_append,
	wr_node_store,
	wr_slot_store,
	wr_bnode
};

In the current maple tree code, a walk down the tree is done in
mas_preallocate() to determine the number of nodes needed for this write.
After node allocation, mas_wr_store_entry() will perform another walk to
determine which write helper function to use to complete the write.

Rather than performing the second walk, we can store the type of write
in the maple write state during node allocation and read this field to
complete the write.

================================ RESULTS =================================

./malloc1_processes -t 4 -s 30
v6.10-rc1 (mm-unstable 06/03/24)
average:14178
v6.10-rc1 + this series
average:17197

+21.3%

./mmap1_processes -t 4 -s 30
v6.10-rc1 (mm-unstable 06/03/24)
average:24579
v6.10-rc1 + this series
average:28625

+16.4%

./brk1_processes -t 4 -s 30
v6.10-rc1 (mm-unstable 06/03/24)
average:46663
v6.10-rc1 + this series
average:55388

+18.7%

================================ TESTING =================================

Testing was done with the maple tree test suite. A new test case is also
added to validate the order in which we test for and assign the store type.

[1]: https://lists.infradead.org/pipermail/maple-tree/2023-December/003098.html


Sidhartha Kumar (18):
  maple_tree: introduce store_type enum
  maple_tree: introduce mas_wr_prealloc_setup()
  maple_tree: move up mas_wr_store_setup() and mas_wr_prealloc_setup()
  maple_tree: introduce mas_wr_store_type()
  maple_tree: set store type in mas_store_prealloc()
  maple_tree: remove mas_destroy() from mas_nomem()
  maple_tree: use mas_store_gfp() in mas_erase()
  maple_tree: set write store type in mas_store()
  maple_tree: use mas_store_gfp() in mtree_store_range()
  maple_tree: print store type in mas_dump()
  maple_tree: use store type in mas_wr_store_entry()
  maple_tree: convert mas_insert() to preallocate nodes
  maple_tree: simplify mas_commit_b_node()
  maple_tree: remove mas_wr_modify()
  maple_tree: have mas_store() allocate nodes if needed
  maple_tree: remove node allocations from various write helper
    functions
  maple_tree: remove repeated sanity checks from mas_wr_append()
  maple_tree: remove unneeded mas_wr_walk() in mas_store_prealloc()

 include/linux/maple_tree.h       |  15 +
 lib/maple_tree.c                 | 559 ++++++++++++++++++-------------
 tools/testing/radix-tree/maple.c |  46 ++-
 3 files changed, 386 insertions(+), 234 deletions(-)

-- 
2.45.1

[PATCH 01/18] maple_tree: introduce store_type enum

[Sidhartha Kumar]

Add a store_type enum that is stored in ma_state. This will be used to
keep track of partial walks of the tree so that subsequent walks can
pick up where a previous walk left off.

Signed-off-by: Sidhartha Kumar <sidhartha.kumar@oracle.com>
---
 include/linux/maple_tree.h | 15 +++++++++++++++
 1 file changed, 15 insertions(+)

diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h
index a53ad4dabd7e..2a2abda9eb32 100644
--- a/include/linux/maple_tree.h
+++ b/include/linux/maple_tree.h
@@ -148,6 +148,19 @@ enum maple_type {
 	maple_arange_64,
 };
 
+enum store_type {
+	wr_invalid,
+	wr_new_root,
+	wr_store_root,
+	wr_exact_fit,
+	wr_spanning_store,
+	wr_split_store,
+	wr_rebalance,
+	wr_append,
+	wr_node_store,
+	wr_slot_store,
+	wr_bnode
+};
 
 /**
  * DOC: Maple tree flags
@@ -436,6 +449,7 @@ struct ma_state {
 	unsigned char offset;
 	unsigned char mas_flags;
 	unsigned char end;		/* The end of the node */
+	enum store_type store_type;	/* The type of store needed for this operation */
 };
 
 struct ma_wr_state {
@@ -477,6 +491,7 @@ struct ma_wr_state {
 		.max = ULONG_MAX,					\
 		.alloc = NULL,						\
 		.mas_flags = 0,						\
+		.store_type = wr_invalid,				\
 	}
 
 #define MA_WR_STATE(name, ma_state, wr_entry)				\
-- 
2.45.1

[PATCH 02/18] maple_tree: introduce mas_wr_prealloc_setup()

[Sidhartha Kumar]

Introduce a helper function, mas_wr_prealoc_setup(), that will set up a
maple write state in order to start a walk of a maple tree.

Signed-off-by: Sidhartha Kumar <sidhartha.kumar@oracle.com>
---
 lib/maple_tree.c | 10 ++++++++--
 1 file changed, 8 insertions(+), 2 deletions(-)

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index 2d7d27e6ae3c..ccbec0f66562 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -5402,6 +5402,13 @@ static void mas_wr_store_setup(struct ma_wr_state *wr_mas)
 	mas_reset(wr_mas->mas);
 }
 
+static inline void mas_wr_prealloc_setup(struct ma_wr_state *wr_mas)
+{
+	struct ma_state *mas = wr_mas->mas;
+
+	mas_wr_store_setup(wr_mas);
+	wr_mas->content = mas_start(mas);
+}
 /* Interface */
 
 /**
@@ -5507,8 +5514,7 @@ int mas_preallocate(struct ma_state *mas, void *entry, gfp_t gfp)
 	if (unlikely(!mas->index && mas->last == ULONG_MAX))
 		goto ask_now;
 
-	mas_wr_store_setup(&wr_mas);
-	wr_mas.content = mas_start(mas);
+	mas_wr_prealloc_setup(&wr_mas);
 	/* Root expand */
 	if (unlikely(mas_is_none(mas) || mas_is_ptr(mas)))
 		goto ask_now;
-- 
2.45.1

[PATCH 03/18] maple_tree: move up mas_wr_store_setup() and mas_wr_prealloc_setup()

[Sidhartha Kumar]

Subsequent patches require these definitions to be higher, no functional
changes intended.

Signed-off-by: Sidhartha Kumar <sidhartha.kumar@oracle.com>
---
 lib/maple_tree.c | 96 ++++++++++++++++++++++++------------------------
 1 file changed, 48 insertions(+), 48 deletions(-)

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index ccbec0f66562..2558d15bb748 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -4230,6 +4230,54 @@ static inline void *mas_wr_store_entry(struct ma_wr_state *wr_mas)
 	return wr_mas->content;
 }
 
+static void mas_wr_store_setup(struct ma_wr_state *wr_mas)
+{
+	if (!mas_is_active(wr_mas->mas)) {
+		if (mas_is_start(wr_mas->mas))
+			return;
+
+		if (unlikely(mas_is_paused(wr_mas->mas)))
+			goto reset;
+
+		if (unlikely(mas_is_none(wr_mas->mas)))
+			goto reset;
+
+		if (unlikely(mas_is_overflow(wr_mas->mas)))
+			goto reset;
+
+		if (unlikely(mas_is_underflow(wr_mas->mas)))
+			goto reset;
+	}
+
+	/*
+	 * A less strict version of mas_is_span_wr() where we allow spanning
+	 * writes within this node.  This is to stop partial walks in
+	 * mas_prealloc() from being reset.
+	 */
+	if (wr_mas->mas->last > wr_mas->mas->max)
+		goto reset;
+
+	if (wr_mas->entry)
+		return;
+
+	if (mte_is_leaf(wr_mas->mas->node) &&
+	    wr_mas->mas->last == wr_mas->mas->max)
+		goto reset;
+
+	return;
+
+reset:
+	mas_reset(wr_mas->mas);
+}
+
+static inline void mas_wr_prealloc_setup(struct ma_wr_state *wr_mas)
+{
+	struct ma_state *mas = wr_mas->mas;
+
+	mas_wr_store_setup(wr_mas);
+	wr_mas->content = mas_start(mas);
+}
+
 /**
  * mas_insert() - Internal call to insert a value
  * @mas: The maple state
@@ -5361,54 +5409,6 @@ static inline void mte_destroy_walk(struct maple_enode *enode,
 		mt_destroy_walk(enode, mt, true);
 	}
 }
-
-static void mas_wr_store_setup(struct ma_wr_state *wr_mas)
-{
-	if (!mas_is_active(wr_mas->mas)) {
-		if (mas_is_start(wr_mas->mas))
-			return;
-
-		if (unlikely(mas_is_paused(wr_mas->mas)))
-			goto reset;
-
-		if (unlikely(mas_is_none(wr_mas->mas)))
-			goto reset;
-
-		if (unlikely(mas_is_overflow(wr_mas->mas)))
-			goto reset;
-
-		if (unlikely(mas_is_underflow(wr_mas->mas)))
-			goto reset;
-	}
-
-	/*
-	 * A less strict version of mas_is_span_wr() where we allow spanning
-	 * writes within this node.  This is to stop partial walks in
-	 * mas_prealloc() from being reset.
-	 */
-	if (wr_mas->mas->last > wr_mas->mas->max)
-		goto reset;
-
-	if (wr_mas->entry)
-		return;
-
-	if (mte_is_leaf(wr_mas->mas->node) &&
-	    wr_mas->mas->last == wr_mas->mas->max)
-		goto reset;
-
-	return;
-
-reset:
-	mas_reset(wr_mas->mas);
-}
-
-static inline void mas_wr_prealloc_setup(struct ma_wr_state *wr_mas)
-{
-	struct ma_state *mas = wr_mas->mas;
-
-	mas_wr_store_setup(wr_mas);
-	wr_mas->content = mas_start(mas);
-}
 /* Interface */
 
 /**
-- 
2.45.1

[PATCH 04/18] maple_tree: introduce mas_wr_store_type()

[Sidhartha Kumar]

Introduce mas_wr_store_type() which will set the correct store type
based on a walk of the tree.

mas_prealloc_calc() is also introduced to abstract the calculation used
to determine the number of nodes needed for a store operation.

Also, add a test case to validate the ordering for store type checks is
correct. This test models a vma expanding and then shrinking which is part
of the boot process.

mas_wr_preallocate() is introduced as a wrapper function to set the store
type and preallcoate enough nodes.

Signed-off-by: Sidhartha Kumar <sidhartha.kumar@oracle.com>
---
 lib/maple_tree.c                 | 210 ++++++++++++++++++++++---------
 tools/testing/radix-tree/maple.c |  35 ++++++
 2 files changed, 186 insertions(+), 59 deletions(-)

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index 2558d15bb748..b37fa8690558 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -4278,6 +4278,150 @@ static inline void mas_wr_prealloc_setup(struct ma_wr_state *wr_mas)
 	wr_mas->content = mas_start(mas);
 }
 
+/**
+ * mas_prealloc_calc() - Calculate number of nodes needed for a
+ * given store oepration
+ * @mas: The maple state.
+ *
+ * Return: Number of nodes required for preallocation.
+ */
+static inline int mas_prealloc_calc(struct ma_state *mas, void *entry)
+{
+	int ret = mas_mt_height(mas) * 3 + 1;
+
+	switch (mas->store_type) {
+	case wr_invalid:
+		WARN_ON_ONCE(1);
+		break;
+	case wr_new_root:
+		ret = 1;
+		break;
+	case wr_store_root:
+		if (likely((mas->last != 0) || (mas->index != 0)))
+			ret = 1;
+		else if (((unsigned long) (entry) & 3) == 2)
+			ret = 1;
+		else
+			ret = 0;
+		break;
+	case wr_spanning_store:
+		ret =  mas_mt_height(mas) * 3 + 1;
+		break;
+	case wr_split_store:
+		ret =  mas_mt_height(mas) * 2 + 1;
+		break;
+	case wr_rebalance:
+		ret =  mas_mt_height(mas) * 2 - 1;
+		break;
+	case wr_node_store:
+	case wr_bnode:
+		ret = mt_in_rcu(mas->tree) ? 1 : 0;
+		break;
+	case wr_append:
+	case wr_exact_fit:
+	case wr_slot_store:
+		ret = 0;
+	}
+
+	return ret;
+}
+
+/*
+ * mas_wr_store_type() - Set the store type for a given
+ * store operation.
+ * @wr_mas: The maple write state
+ */
+static inline void mas_wr_store_type(struct ma_wr_state *wr_mas)
+{
+	struct ma_state *mas = wr_mas->mas;
+	unsigned char new_end;
+
+	if (unlikely(mas_is_none(mas) || mas_is_ptr(mas))) {
+		mas->store_type = wr_store_root;
+		return;
+	}
+
+	if (unlikely(!mas_wr_walk(wr_mas))) {
+		mas->store_type = wr_spanning_store;
+		return;
+	}
+
+	/* At this point, we are at the leaf node that needs to be altered. */
+	mas_wr_end_piv(wr_mas);
+	if (!wr_mas->entry)
+		mas_wr_extend_null(wr_mas);
+
+	new_end = mas_wr_new_end(wr_mas);
+	if ((wr_mas->r_min == mas->index) && (wr_mas->r_max == mas->last)) {
+		mas->store_type = wr_exact_fit;
+		return;
+	}
+
+	if (unlikely(!mas->index && mas->last == ULONG_MAX)) {
+		mas->store_type = wr_new_root;
+		return;
+	}
+
+	/* Potential spanning rebalance collapsing a node */
+	if (new_end < mt_min_slots[wr_mas->type]) {
+		if (!mte_is_root(mas->node)) {
+			mas->store_type = wr_rebalance;
+			return;
+		}
+		mas->store_type = wr_node_store;
+		return;
+	}
+
+	if (new_end >= mt_slots[wr_mas->type]) {
+		mas->store_type = wr_split_store;
+		return;
+	}
+
+	if (!mt_in_rcu(mas->tree) && (mas->offset == mas->end)) {
+		mas->store_type = wr_append;
+		return;
+	}
+
+	if ((new_end == mas->end) && (!mt_in_rcu(mas->tree) ||
+		(wr_mas->offset_end - mas->offset == 1))) {
+		mas->store_type = wr_slot_store;
+		return;
+	}
+
+	if (mte_is_root(mas->node) || !(new_end <= mt_min_slots[wr_mas->type]) ||
+		(mas->mas_flags & MA_STATE_BULK)) {
+		mas->store_type = wr_node_store;
+		return;
+	}
+
+	mas->store_type = wr_bnode;
+}
+
+/**
+ * mas_wr_preallocate() - Preallocate enough nodes for a store operation
+ * @wr_mas: The maple write state
+ * @entry: The entry that will be stored
+ * @gfp: The GFP_FLAGS to use for allocations.
+ *
+ */
+static inline void mas_wr_preallocate(struct ma_wr_state *wr_mas, void *entry, gfp_t gfp)
+{
+	struct ma_state *mas = wr_mas->mas;
+	int request;
+
+	mas_wr_prealloc_setup(wr_mas);
+	mas_wr_store_type(wr_mas);
+	request = mas_prealloc_calc(mas, entry);
+	if (!request)
+		return;
+
+	mas_node_count_gfp(mas, request, gfp);
+	if (likely(!mas_is_err(mas)))
+		return;
+
+	mas_set_alloc_req(mas, 0);
+}
+
 /**
  * mas_insert() - Internal call to insert a value
  * @mas: The maple state
@@ -5506,69 +5650,17 @@ EXPORT_SYMBOL_GPL(mas_store_prealloc);
 int mas_preallocate(struct ma_state *mas, void *entry, gfp_t gfp)
 {
 	MA_WR_STATE(wr_mas, mas, entry);
-	unsigned char node_size;
-	int request = 1;
-	int ret;
-
-
-	if (unlikely(!mas->index && mas->last == ULONG_MAX))
-		goto ask_now;
-
-	mas_wr_prealloc_setup(&wr_mas);
-	/* Root expand */
-	if (unlikely(mas_is_none(mas) || mas_is_ptr(mas)))
-		goto ask_now;
-
-	if (unlikely(!mas_wr_walk(&wr_mas))) {
-		/* Spanning store, use worst case for now */
-		request = 1 + mas_mt_height(mas) * 3;
-		goto ask_now;
-	}
-
-	/* At this point, we are at the leaf node that needs to be altered. */
-	/* Exact fit, no nodes needed. */
-	if (wr_mas.r_min == mas->index && wr_mas.r_max == mas->last)
-		return 0;
-
-	mas_wr_end_piv(&wr_mas);
-	node_size = mas_wr_new_end(&wr_mas);
-
-	/* Slot store, does not require additional nodes */
-	if (node_size == mas->end) {
-		/* reuse node */
-		if (!mt_in_rcu(mas->tree))
-			return 0;
-		/* shifting boundary */
-		if (wr_mas.offset_end - mas->offset == 1)
-			return 0;
-	}
+	int ret = 0;
 
-	if (node_size >= mt_slots[wr_mas.type]) {
-		/* Split, worst case for now. */
-		request = 1 + mas_mt_height(mas) * 2;
-		goto ask_now;
+	mas_wr_preallocate(&wr_mas, entry, gfp);
+	if (mas_is_err(mas)) {
+		ret = xa_err(mas->node);
+		mas_destroy(mas);
+		mas_reset(mas);
+		return ret;
 	}
 
-	/* New root needs a single node */
-	if (unlikely(mte_is_root(mas->node)))
-		goto ask_now;
-
-	/* Potential spanning rebalance collapsing a node, use worst-case */
-	if (node_size  - 1 <= mt_min_slots[wr_mas.type])
-		request = mas_mt_height(mas) * 2 - 1;
-
-	/* node store, slot store needs one node */
-ask_now:
-	mas_node_count_gfp(mas, request, gfp);
 	mas->mas_flags |= MA_STATE_PREALLOC;
-	if (likely(!mas_is_err(mas)))
-		return 0;
-
-	mas_set_alloc_req(mas, 0);
-	ret = xa_err(mas->node);
-	mas_reset(mas);
-	mas_destroy(mas);
-	mas_reset(mas);
 	return ret;
 }
 EXPORT_SYMBOL_GPL(mas_preallocate);
diff --git a/tools/testing/radix-tree/maple.c b/tools/testing/radix-tree/maple.c
index f1caf4bcf937..c57979de1576 100644
--- a/tools/testing/radix-tree/maple.c
+++ b/tools/testing/radix-tree/maple.c
@@ -36223,6 +36223,37 @@ static noinline void __init check_mtree_dup(struct maple_tree *mt)
 
 extern void test_kmem_cache_bulk(void);
 
+
+ /* test to simulate expanding a vma from [0x7fffffffe000, 0x7ffffffff000)
+  * to [0x7ffde4ca1000, 0x7ffffffff000) and then shrinking the vma to
+  * [0x7ffde4ca1000, 0x7ffde4ca2000)
+  */
+static inline int check_vma_modification(struct maple_tree *mt)
+{
+	MA_STATE(mas, mt, 0, 0);
+
+	/* vma with old start and old end */
+	__mas_set_range(&mas, 0x7fffffffe000, 0x7ffffffff000 - 1);
+	mas_preallocate(&mas, xa_mk_value(1), GFP_KERNEL);
+	mas_store_prealloc(&mas, xa_mk_value(1));
+
+	/* next write occurs partly in previous range [0, 0x7fffffffe000)*/
+	mas_prev_range(&mas, 0);
+	/* expand vma to {0x7ffde4ca1000, 0x7ffffffff000) */
+	__mas_set_range(&mas, 0x7ffde4ca1000, 0x7ffffffff000 - 1);
+	mas_preallocate(&mas, xa_mk_value(1), GFP_KERNEL);
+	mas_store_prealloc(&mas, xa_mk_value(1));
+
+	/* shrink vma to [0x7ffde4ca1000, 7ffde4ca2000) */
+	__mas_set_range(&mas, 0x7ffde4ca2000, 0x7ffffffff000 - 1);
+	mas_preallocate(&mas, NULL, GFP_KERNEL);
+	mas_store_prealloc(&mas, NULL);
+	mt_dump(mt, mt_dump_hex);
+
+	return 0;
+}
+
+
 void farmer_tests(void)
 {
 	struct maple_node *node;
@@ -36230,6 +36261,10 @@ void farmer_tests(void)
 
 	mt_dump(&tree, mt_dump_dec);
 
+	mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE | MT_FLAGS_LOCK_EXTERN | MT_FLAGS_USE_RCU);
+	check_vma_modification(&tree);
+	mtree_destroy(&tree);
+
 	tree.ma_root = xa_mk_value(0);
 	mt_dump(&tree, mt_dump_dec);
 
-- 
2.45.1

[PATCH 05/18] maple_tree: set store type in mas_store_prealloc()

[Sidhartha Kumar]

Set the store type in mas_store_prealloc(). This is needed as
mas_wr_store_entry() will be modified to read the store type to make a
decision about how to complete the store.

Signed-off-by: Sidhartha Kumar <sidhartha.kumar@oracle.com>
---
 lib/maple_tree.c | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index b37fa8690558..3780d4bb0415 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -5631,7 +5631,8 @@ void mas_store_prealloc(struct ma_state *mas, void *entry)
 {
 	MA_WR_STATE(wr_mas, mas, entry);
 
-	mas_wr_store_setup(&wr_mas);
+	mas_wr_prealloc_setup(&wr_mas);
+	mas_wr_store_type(&wr_mas);
 	trace_ma_write(__func__, mas, 0, entry);
 	mas_wr_store_entry(&wr_mas);
 	MAS_WR_BUG_ON(&wr_mas, mas_is_err(mas));
-- 
2.45.1

[PATCH 06/18] maple_tree: remove mas_destroy() from mas_nomem()

[Sidhartha Kumar]

Separate call to mas_destroy() from mas_nomem() so we can check for no
memory errors without destroying the current maple state in
mas_store_gfp(). We then add calls to mas_destroy() to callers of
mas_nomem().

Signed-off-by: Sidhartha Kumar <sidhartha.kumar@oracle.com>
---
 lib/maple_tree.c                 | 39 ++++++++++++++++++++------------
 tools/testing/radix-tree/maple.c | 11 +++++----
 2 files changed, 31 insertions(+), 19 deletions(-)

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index 3780d4bb0415..f1496817e52a 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -4526,6 +4526,7 @@ int mas_alloc_cyclic(struct ma_state *mas, unsigned long *startp,
 	if (*next == 0)
 		mas->tree->ma_flags |= MT_FLAGS_ALLOC_WRAPPED;
 
+	mas_destroy(mas);
 	return ret;
 }
 EXPORT_SYMBOL(mas_alloc_cyclic);
@@ -5606,18 +5607,22 @@ EXPORT_SYMBOL_GPL(mas_store);
 int mas_store_gfp(struct ma_state *mas, void *entry, gfp_t gfp)
 {
 	MA_WR_STATE(wr_mas, mas, entry);
+	int ret;
 
-	mas_wr_store_setup(&wr_mas);
-	trace_ma_write(__func__, mas, 0, entry);
 retry:
-	mas_wr_store_entry(&wr_mas);
+	mas_wr_preallocate(&wr_mas, entry, gfp);
+	WARN_ON_ONCE(mas->store_type == wr_invalid);
+
 	if (unlikely(mas_nomem(mas, gfp)))
 		goto retry;
+	if (mas_is_err(mas))
+		goto out;
 
-	if (unlikely(mas_is_err(mas)))
-		return xa_err(mas->node);
-
-	return 0;
+	mas_wr_store_entry(&wr_mas);
+out:
+	ret = xa_err(mas->node);
+	mas_destroy(mas);
+	return ret;
 }
 EXPORT_SYMBOL_GPL(mas_store_gfp);
 
@@ -6365,6 +6370,7 @@ void *mas_erase(struct ma_state *mas)
 	if (mas_nomem(mas, GFP_KERNEL))
 		goto write_retry;
 
+	mas_destroy(mas);
 	return entry;
 }
 EXPORT_SYMBOL_GPL(mas_erase);
@@ -6379,10 +6385,8 @@ EXPORT_SYMBOL_GPL(mas_erase);
 bool mas_nomem(struct ma_state *mas, gfp_t gfp)
 	__must_hold(mas->tree->ma_lock)
 {
-	if (likely(mas->node != MA_ERROR(-ENOMEM))) {
-		mas_destroy(mas);
+	if (likely(mas->node != MA_ERROR(-ENOMEM)))
 		return false;
-	}
 
 	if (gfpflags_allow_blocking(gfp) && !mt_external_lock(mas->tree)) {
 		mtree_unlock(mas->tree);
@@ -6460,6 +6464,7 @@ int mtree_store_range(struct maple_tree *mt, unsigned long index,
 {
 	MA_STATE(mas, mt, index, last);
 	MA_WR_STATE(wr_mas, &mas, entry);
+	int ret = 0;
 
 	trace_ma_write(__func__, &mas, 0, entry);
 	if (WARN_ON_ONCE(xa_is_advanced(entry)))
@@ -6475,10 +6480,12 @@ int mtree_store_range(struct maple_tree *mt, unsigned long index,
 		goto retry;
 
 	mtree_unlock(mt);
+
 	if (mas_is_err(&mas))
-		return xa_err(mas.node);
+		ret = xa_err(mas.node);
 
-	return 0;
+	mas_destroy(&mas);
+	return ret;
 }
 EXPORT_SYMBOL(mtree_store_range);
 
@@ -6514,6 +6521,7 @@ int mtree_insert_range(struct maple_tree *mt, unsigned long first,
 		unsigned long last, void *entry, gfp_t gfp)
 {
 	MA_STATE(ms, mt, first, last);
+	int ret = 0;
 
 	if (WARN_ON_ONCE(xa_is_advanced(entry)))
 		return -EINVAL;
@@ -6529,9 +6537,10 @@ int mtree_insert_range(struct maple_tree *mt, unsigned long first,
 
 	mtree_unlock(mt);
 	if (mas_is_err(&ms))
-		return xa_err(ms.node);
+		ret = xa_err(ms.node);
 
-	return 0;
+	mas_destroy(&ms);
+	return ret;
 }
 EXPORT_SYMBOL(mtree_insert_range);
 
@@ -6586,6 +6595,7 @@ int mtree_alloc_range(struct maple_tree *mt, unsigned long *startp,
 
 unlock:
 	mtree_unlock(mt);
+	mas_destroy(&mas);
 	return ret;
 }
 EXPORT_SYMBOL(mtree_alloc_range);
@@ -6667,6 +6677,7 @@ int mtree_alloc_rrange(struct maple_tree *mt, unsigned long *startp,
 
 unlock:
 	mtree_unlock(mt);
+	mas_destroy(&mas);
 	return ret;
 }
 EXPORT_SYMBOL(mtree_alloc_rrange);
diff --git a/tools/testing/radix-tree/maple.c b/tools/testing/radix-tree/maple.c
index c57979de1576..c834e91e6810 100644
--- a/tools/testing/radix-tree/maple.c
+++ b/tools/testing/radix-tree/maple.c
@@ -119,7 +119,7 @@ static noinline void __init check_new_node(struct maple_tree *mt)
 	MT_BUG_ON(mt, mas.alloc->slot[0] == NULL);
 	mas_push_node(&mas, mn);
 	mas_reset(&mas);
-	mas_nomem(&mas, GFP_KERNEL); /* free */
+	mas_destroy(&mas);
 	mtree_unlock(mt);
 
 
@@ -143,7 +143,7 @@ static noinline void __init check_new_node(struct maple_tree *mt)
 	mn->parent = ma_parent_ptr(mn);
 	ma_free_rcu(mn);
 	mas.status = ma_start;
-	mas_nomem(&mas, GFP_KERNEL);
+	mas_destroy(&mas);
 	/* Allocate 3 nodes, will fail. */
 	mas_node_count(&mas, 3);
 	/* Drop the lock and allocate 3 nodes. */
@@ -160,7 +160,7 @@ static noinline void __init check_new_node(struct maple_tree *mt)
 	MT_BUG_ON(mt, mas_allocated(&mas) != 3);
 	/* Free. */
 	mas_reset(&mas);
-	mas_nomem(&mas, GFP_KERNEL);
+	mas_destroy(&mas);
 
 	/* Set allocation request to 1. */
 	mas_set_alloc_req(&mas, 1);
@@ -275,7 +275,7 @@ static noinline void __init check_new_node(struct maple_tree *mt)
 			MT_BUG_ON(mt, mas_allocated(&mas) != i - j - 1);
 		}
 		mas_reset(&mas);
-		MT_BUG_ON(mt, mas_nomem(&mas, GFP_KERNEL));
+		mas_destroy(&mas);
 
 	}
 
@@ -298,7 +298,7 @@ static noinline void __init check_new_node(struct maple_tree *mt)
 	}
 	MT_BUG_ON(mt, mas_allocated(&mas) != total);
 	mas_reset(&mas);
-	mas_nomem(&mas, GFP_KERNEL); /* Free. */
+	mas_destroy(&mas); /* Free. */
 
 	MT_BUG_ON(mt, mas_allocated(&mas) != 0);
 	for (i = 1; i < 128; i++) {
@@ -35846,6 +35846,7 @@ static noinline void __init check_nomem(struct maple_tree *mt)
 	mas_store(&ms, &ms); /* insert 1 -> &ms */
 	mas_nomem(&ms, GFP_KERNEL); /* Node allocated in here. */
 	mtree_unlock(mt);
+	mas_destroy(&ms);
 	mtree_destroy(mt);
 }
 
-- 
2.45.1

[PATCH 07/18] maple_tree: use mas_store_gfp() in mas_erase()

[Sidhartha Kumar]

Refactor mas_erase() to simply call mas_store_gfp() which will abstract
storing the null, memory allocation, and error handling.

Signed-off-by: Sidhartha Kumar <sidhartha.kumar@oracle.com>
---
 lib/maple_tree.c | 9 +--------
 1 file changed, 1 insertion(+), 8 deletions(-)

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index f1496817e52a..d74847045bf7 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -6352,7 +6352,6 @@ EXPORT_SYMBOL_GPL(mas_find_range_rev);
 void *mas_erase(struct ma_state *mas)
 {
 	void *entry;
-	MA_WR_STATE(wr_mas, mas, NULL);
 
 	if (!mas_is_active(mas) || !mas_is_start(mas))
 		mas->status = ma_start;
@@ -6362,15 +6361,9 @@ void *mas_erase(struct ma_state *mas)
 	if (!entry)
 		return NULL;
 
-write_retry:
 	/* Must reset to ensure spanning writes of last slot are detected */
 	mas_reset(mas);
-	mas_wr_store_setup(&wr_mas);
-	mas_wr_store_entry(&wr_mas);
-	if (mas_nomem(mas, GFP_KERNEL))
-		goto write_retry;
-
-	mas_destroy(mas);
+	mas_store_gfp(mas, NULL, GFP_KERNEL);
 	return entry;
 }
 EXPORT_SYMBOL_GPL(mas_erase);
-- 
2.45.1

[PATCH 08/18] maple_tree: set write store type in mas_store()

[Sidhartha Kumar]

Set the correct mas->store_type in mas_store() so that the subsequent
changes to mas_wr_store_entry() can use the store type to complete the
write.

Signed-off-by: Sidhartha Kumar <sidhartha.kumar@oracle.com>
---
 lib/maple_tree.c | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index d74847045bf7..34ff1b3f729c 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -5589,7 +5589,8 @@ void *mas_store(struct ma_state *mas, void *entry)
 	 * want to examine what happens if a single store operation was to
 	 * overwrite multiple entries within a self-balancing B-Tree.
 	 */
-	mas_wr_store_setup(&wr_mas);
+	mas_wr_prealloc_setup(&wr_mas);
+	mas_wr_store_type(&wr_mas);
 	mas_wr_store_entry(&wr_mas);
 	return wr_mas.content;
 }
-- 
2.45.1

[PATCH 09/18] maple_tree: use mas_store_gfp() in mtree_store_range()

[Sidhartha Kumar]

Refactor mtree_store_range() to use mas_store_gfp() which will abstract
the store, memory allocation, and error handling.

Signed-off-by: Sidhartha Kumar <sidhartha.kumar@oracle.com>
---
 lib/maple_tree.c | 12 ++----------
 1 file changed, 2 insertions(+), 10 deletions(-)

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index 34ff1b3f729c..e3ec6649f7da 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -6457,7 +6457,6 @@ int mtree_store_range(struct maple_tree *mt, unsigned long index,
 		unsigned long last, void *entry, gfp_t gfp)
 {
 	MA_STATE(mas, mt, index, last);
-	MA_WR_STATE(wr_mas, &mas, entry);
 	int ret = 0;
 
 	trace_ma_write(__func__, &mas, 0, entry);
@@ -6468,17 +6467,10 @@ int mtree_store_range(struct maple_tree *mt, unsigned long index,
 		return -EINVAL;
 
 	mtree_lock(mt);
-retry:
-	mas_wr_store_entry(&wr_mas);
-	if (mas_nomem(&mas, gfp))
-		goto retry;
-
+	ret = mas_store_gfp(&mas, entry, gfp);
 	mtree_unlock(mt);
 
-	if (mas_is_err(&mas))
-		ret = xa_err(mas.node);
-
-	mas_destroy(&mas);
+	MT_BUG_ON(mas.tree, mas.store_type == wr_invalid);
 	return ret;
 }
 EXPORT_SYMBOL(mtree_store_range);
-- 
2.45.1

[PATCH 10/18] maple_tree: print store type in mas_dump()

[Sidhartha Kumar]

Knowing the store type of the maple state could be helpful for debugging.
Have mas_dump() print mas->store_type.

Signed-off-by: Sidhartha Kumar <sidhartha.kumar@oracle.com>
---
 lib/maple_tree.c | 39 +++++++++++++++++++++++++++++++++++++++
 1 file changed, 39 insertions(+)

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index e3ec6649f7da..abd2f396bb1e 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -7729,6 +7729,45 @@ void mas_dump(const struct ma_state *mas)
 		break;
 	}
 
+	pr_err("Store Type: ");
+	switch (mas->store_type) {
+	case wr_invalid:
+		pr_err("invalid store type\n");
+		break;
+	case wr_new_root:
+		pr_err("new_root\n");
+		break;
+	case wr_store_root:
+		pr_err("store_root\n");
+		break;
+	case wr_exact_fit:
+		pr_err("exact_fit\n");
+		break;
+	case wr_split_store:
+		pr_err("split_store\n");
+		break;
+	case wr_slot_store:
+		pr_err("slot_store\n");
+		break;
+	case wr_append:
+		pr_err("append\n");
+		break;
+	case wr_node_store:
+		pr_err("node_store\n");
+		break;
+	case wr_spanning_store:
+		pr_err("spanning_store\n");
+		break;
+	case wr_rebalance:
+		pr_err("rebalance\n");
+		break;
+	case wr_bnode:
+		pr_err("write_bnode\n");
+		break;
+
+	}
+
+
 	pr_err("[%u/%u] index=%lx last=%lx\n", mas->offset, mas->end,
 	       mas->index, mas->last);
 	pr_err("     min=%lx max=%lx alloc=%p, depth=%u, flags=%x\n",
-- 
2.45.1

[PATCH 11/18] maple_tree: use store type in mas_wr_store_entry()

[Sidhartha Kumar]

When storing an entry, we can read the store type that was set from a
previous partial walk of the tree. Now that the type of store is known,
select the correct write helper function to use to complete the store.

Signed-off-by: Sidhartha Kumar <sidhartha.kumar@oracle.com>
---
 lib/maple_tree.c | 47 +++++++++++++++++++++++++++++++----------------
 1 file changed, 31 insertions(+), 16 deletions(-)

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index abd2f396bb1e..20e9d13c2980 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -4206,27 +4206,42 @@ static inline void mas_wr_modify(struct ma_wr_state *wr_mas)
 static inline void *mas_wr_store_entry(struct ma_wr_state *wr_mas)
 {
 	struct ma_state *mas = wr_mas->mas;
+	unsigned char new_end = mas_wr_new_end(wr_mas);
 
-	wr_mas->content = mas_start(mas);
-	if (mas_is_none(mas) || mas_is_ptr(mas)) {
+	switch (mas->store_type) {
+	case wr_invalid:
+		MT_BUG_ON(mas->tree, 1);
+		return NULL;
+	case wr_new_root:
+		mas_new_root(mas, wr_mas->entry);
+		break;
+	case wr_store_root:
 		mas_store_root(mas, wr_mas->entry);
-		return wr_mas->content;
-	}
-
-	if (unlikely(!mas_wr_walk(wr_mas))) {
+		break;
+	case wr_exact_fit:
+		rcu_assign_pointer(wr_mas->slots[mas->offset], wr_mas->entry);
+		if (!!wr_mas->entry ^ !!wr_mas->content)
+			mas_update_gap(mas);
+		break;
+	case wr_append:
+		mas_wr_append(wr_mas, new_end);
+		break;
+	case wr_slot_store:
+		mas_wr_slot_store(wr_mas);
+		break;
+	case wr_node_store:
+		mas_wr_node_store(wr_mas, new_end);
+		break;
+	case wr_spanning_store:
 		mas_wr_spanning_store(wr_mas);
-		return wr_mas->content;
-	}
-
-	/* At this point, we are at the leaf node that needs to be altered. */
-	mas_wr_end_piv(wr_mas);
-	/* New root for a single pointer */
-	if (unlikely(!mas->index && mas->last == ULONG_MAX)) {
-		mas_new_root(mas, wr_mas->entry);
-		return wr_mas->content;
+		break;
+	case wr_split_store:
+	case wr_rebalance:
+	case wr_bnode:
+		mas_wr_bnode(wr_mas);
+		break;
 	}
 
-	mas_wr_modify(wr_mas);
 	return wr_mas->content;
 }
 
-- 
2.45.1

[PATCH 12/18] maple_tree: convert mas_insert() to preallocate nodes

[Sidhartha Kumar]

By setting the store type in mas_insert(), we no longer need to use
mas_wr_modify() to determine the correct store function to use. Instead,
set the store type and call mas_wr_store_entry(). Also, pass in the
requested gfp flags to mas_insert() so they can be passed to the call to
mas_wr_preallocate().

Signed-off-by: Sidhartha Kumar <sidhartha.kumar@oracle.com>
---
 lib/maple_tree.c | 32 +++++++++++++++-----------------
 1 file changed, 15 insertions(+), 17 deletions(-)

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index 20e9d13c2980..314691fd1c67 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -4445,7 +4445,7 @@ static inline void mas_wr_preallocate(struct ma_wr_state *wr_mas, void *entry, g
  * Return: %NULL or the contents that already exists at the requested index
  * otherwise.  The maple state needs to be checked for error conditions.
  */
-static inline void *mas_insert(struct ma_state *mas, void *entry)
+static inline void *mas_insert(struct ma_state *mas, void *entry, gfp_t gfp)
 {
 	MA_WR_STATE(wr_mas, mas, entry);
 
@@ -4467,26 +4467,24 @@ static inline void *mas_insert(struct ma_state *mas, void *entry)
 	if (wr_mas.content)
 		goto exists;
 
-	if (mas_is_none(mas) || mas_is_ptr(mas)) {
-		mas_store_root(mas, entry);
+	mas_wr_preallocate(&wr_mas, entry, gfp);
+	if (mas_is_err(mas))
 		return NULL;
-	}
 
 	/* spanning writes always overwrite something */
-	if (!mas_wr_walk(&wr_mas))
+	if (mas->store_type == wr_spanning_store)
 		goto exists;
 
 	/* At this point, we are at the leaf node that needs to be altered. */
-	wr_mas.offset_end = mas->offset;
-	wr_mas.end_piv = wr_mas.r_max;
-
-	if (wr_mas.content || (mas->last > wr_mas.r_max))
-		goto exists;
+	if (mas->store_type != wr_new_root && mas->store_type != wr_store_root) {
+		wr_mas.offset_end = mas->offset;
+		wr_mas.end_piv = wr_mas.r_max;
 
-	if (!entry)
-		return NULL;
+		if (wr_mas.content || (mas->last > wr_mas.r_max))
+			goto exists;
+	}
 
-	mas_wr_modify(&wr_mas);
+	mas_wr_store_entry(&wr_mas);
 	return wr_mas.content;
 
 exists:
@@ -4531,7 +4529,7 @@ int mas_alloc_cyclic(struct ma_state *mas, unsigned long *startp,
 		return ret;
 
 	do {
-		mas_insert(mas, entry);
+		mas_insert(mas, entry, gfp);
 	} while (mas_nomem(mas, gfp));
 	if (mas_is_err(mas))
 		return xa_err(mas->node);
@@ -6532,7 +6530,7 @@ int mtree_insert_range(struct maple_tree *mt, unsigned long first,
 
 	mtree_lock(mt);
 retry:
-	mas_insert(&ms, entry);
+	mas_insert(&ms, entry, gfp);
 	if (mas_nomem(&ms, gfp))
 		goto retry;
 
@@ -6581,7 +6579,7 @@ int mtree_alloc_range(struct maple_tree *mt, unsigned long *startp,
 	if (ret)
 		goto unlock;
 
-	mas_insert(&mas, entry);
+	mas_insert(&mas, entry, gfp);
 	/*
 	 * mas_nomem() may release the lock, causing the allocated area
 	 * to be unavailable, so try to allocate a free area again.
@@ -6663,7 +6661,7 @@ int mtree_alloc_rrange(struct maple_tree *mt, unsigned long *startp,
 	if (ret)
 		goto unlock;
 
-	mas_insert(&mas, entry);
+	mas_insert(&mas, entry, gfp);
 	/*
 	 * mas_nomem() may release the lock, causing the allocated area
 	 * to be unavailable, so try to allocate a free area again.
-- 
2.45.1

[PATCH 13/18] maple_tree: simplify mas_commit_b_node()

[Sidhartha Kumar]

Use mas->store_type to simplify the logic of identifying the type of
write.

Signed-off-by: Sidhartha Kumar <sidhartha.kumar@oracle.com>
---
 lib/maple_tree.c | 6 ++----
 1 file changed, 2 insertions(+), 4 deletions(-)

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index 314691fd1c67..faadddbe2086 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -3437,12 +3437,10 @@ static noinline_for_kasan int mas_commit_b_node(struct ma_wr_state *wr_mas,
 	enum maple_type b_type = b_node->type;
 
 	old_enode = wr_mas->mas->node;
-	if ((b_end < mt_min_slots[b_type]) &&
-	    (!mte_is_root(old_enode)) &&
-	    (mas_mt_height(wr_mas->mas) > 1))
+	if (wr_mas->mas->store_type == wr_rebalance)
 		return mas_rebalance(wr_mas->mas, b_node);
 
-	if (b_end >= mt_slots[b_type])
+	if (wr_mas->mas->store_type == wr_split_store)
 		return mas_split(wr_mas->mas, b_node);
 
 	if (mas_reuse_node(wr_mas, b_node, end))
-- 
2.45.1

[PATCH 14/18] maple_tree: remove mas_wr_modify()

[Sidhartha Kumar]

There are no more users of the function, safely remove it.

Signed-off-by: Sidhartha Kumar <sidhartha.kumar@oracle.com>
---
 lib/maple_tree.c | 38 --------------------------------------
 1 file changed, 38 deletions(-)

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index faadddbe2086..74c89aad8bca 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -4156,44 +4156,6 @@ static void mas_wr_bnode(struct ma_wr_state *wr_mas)
 	mas_commit_b_node(wr_mas, &b_node, wr_mas->mas->end);
 }
 
-static inline void mas_wr_modify(struct ma_wr_state *wr_mas)
-{
-	struct ma_state *mas = wr_mas->mas;
-	unsigned char new_end;
-
-	/* Direct replacement */
-	if (wr_mas->r_min == mas->index && wr_mas->r_max == mas->last) {
-		rcu_assign_pointer(wr_mas->slots[mas->offset], wr_mas->entry);
-		if (!!wr_mas->entry ^ !!wr_mas->content)
-			mas_update_gap(mas);
-		return;
-	}
-
-	/*
-	 * new_end exceeds the size of the maple node and cannot enter the fast
-	 * path.
-	 */
-	new_end = mas_wr_new_end(wr_mas);
-	if (new_end >= mt_slots[wr_mas->type])
-		goto slow_path;
-
-	/* Attempt to append */
-	if (mas_wr_append(wr_mas, new_end))
-		return;
-
-	if (new_end == mas->end && mas_wr_slot_store(wr_mas))
-		return;
-
-	if (mas_wr_node_store(wr_mas, new_end))
-		return;
-
-	if (mas_is_err(mas))
-		return;
-
-slow_path:
-	mas_wr_bnode(wr_mas);
-}
-
 /*
  * mas_wr_store_entry() - Internal call to store a value
  * @mas: The maple state
-- 
2.45.1

[PATCH 15/18] maple_tree: have mas_store() allocate nodes if needed

[Sidhartha Kumar]

Not all users of mas_store() enter with nodes already preallocated.
Check for the MA_STATE_PREALLOC flag to decide whether to preallocate nodes
within mas_store() rather than relying on future write helper functions
to perform the allocations. This allows the write helper functions to be
simplified as they do not have to do checks to make sure there are
enough allocated nodes to perform the write.

Signed-off-by: Sidhartha Kumar <sidhartha.kumar@oracle.com>
---
 lib/maple_tree.c | 32 ++++++++++++++++++++++++++++----
 1 file changed, 28 insertions(+), 4 deletions(-)

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index 74c89aad8bca..42853afc3885 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -5527,6 +5527,20 @@ static inline void mte_destroy_walk(struct maple_enode *enode,
 		mt_destroy_walk(enode, mt, true);
 	}
 }
+
+static inline void mas_wr_store_prealloc(struct ma_wr_state *wr_mas, void *entry)
+{
+	struct ma_state *mas = wr_mas->mas;
+	int request;
+
+	mas_wr_prealloc_setup(wr_mas);
+	mas_wr_store_type(wr_mas);
+	request = mas_prealloc_calc(mas, entry);
+	if (!request)
+		return;
+
+	mas_node_count(mas, request);
+}
 /* Interface */
 
 /**
@@ -5535,8 +5549,6 @@ static inline void mte_destroy_walk(struct maple_enode *enode,
  * @entry: The entry to store.
  *
  * The @mas->index and @mas->last is used to set the range for the @entry.
- * Note: The @mas should have pre-allocated entries to ensure there is memory to
- * store the entry.  Please see mas_expected_entries()/mas_destroy() for more details.
  *
  * Return: the first entry between mas->index and mas->last or %NULL.
  */
@@ -5562,9 +5574,21 @@ void *mas_store(struct ma_state *mas, void *entry)
 	 * want to examine what happens if a single store operation was to
 	 * overwrite multiple entries within a self-balancing B-Tree.
 	 */
-	mas_wr_prealloc_setup(&wr_mas);
-	mas_wr_store_type(&wr_mas);
+	if (mas->mas_flags & MA_STATE_PREALLOC) {
+		mas_wr_prealloc_setup(&wr_mas);
+		mas_wr_store_type(&wr_mas);
+		mas_wr_store_entry(&wr_mas);
+		MAS_WR_BUG_ON(&wr_mas, mas_is_err(mas));
+		return wr_mas.content;
+	}
+
+	mas_wr_store_prealloc(&wr_mas, entry);
+	WARN_ON_ONCE(mas->store_type == wr_invalid);
+	if (mas_is_err(mas))
+		return NULL;
+
 	mas_wr_store_entry(&wr_mas);
+	mas_destroy(mas);
 	return wr_mas.content;
 }
 EXPORT_SYMBOL_GPL(mas_store);
-- 
2.45.1

[PATCH 16/18] maple_tree: remove node allocations from various write helper functions

[Sidhartha Kumar]

These write helper functions are all called from store paths which
preallocate enough nodes that will be needed for the write. There is no
more need to allocate within the functions themselves.

Signed-off-by: Sidhartha Kumar <sidhartha.kumar@oracle.com>
---
 lib/maple_tree.c | 31 -------------------------------
 1 file changed, 31 deletions(-)

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index 42853afc3885..3d2d8c2c24df 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -2976,9 +2976,6 @@ static inline int mas_rebalance(struct ma_state *mas,
 	 * tries to combine the data in the same way.  If one node contains the
 	 * entire range of the tree, then that node is used as a new root node.
 	 */
-	mas_node_count(mas, empty_count * 2 - 1);
-	if (mas_is_err(mas))
-		return 0;
 
 	mast.orig_l = &l_mas;
 	mast.orig_r = &r_mas;
@@ -3029,11 +3026,6 @@ static inline void mas_destroy_rebalance(struct ma_state *mas, unsigned char end
 
 	/* set up node. */
 	if (in_rcu) {
-		/* Allocate for both left and right as well as parent. */
-		mas_node_count(mas, 3);
-		if (mas_is_err(mas))
-			return;
-
 		newnode = mas_pop_node(mas);
 	} else {
 		newnode = &reuse;
@@ -3341,10 +3333,6 @@ static int mas_split(struct ma_state *mas, struct maple_big_node *b_node)
 
 	trace_ma_op(__func__, mas);
 	mas->depth = mas_mt_height(mas);
-	/* Allocation failures will happen early. */
-	mas_node_count(mas, 1 + mas->depth * 2);
-	if (mas_is_err(mas))
-		return 0;
 
 	mast.l = &l_mas;
 	mast.r = &r_mas;
@@ -3446,10 +3434,6 @@ static noinline_for_kasan int mas_commit_b_node(struct ma_wr_state *wr_mas,
 	if (mas_reuse_node(wr_mas, b_node, end))
 		goto reuse_node;
 
-	mas_node_count(wr_mas->mas, 1);
-	if (mas_is_err(wr_mas->mas))
-		return 0;
-
 	node = mas_pop_node(wr_mas->mas);
 	node->parent = mas_mn(wr_mas->mas)->parent;
 	wr_mas->mas->node = mt_mk_node(node, b_type);
@@ -3475,10 +3459,6 @@ static inline int mas_root_expand(struct ma_state *mas, void *entry)
 	unsigned long *pivots;
 	int slot = 0;
 
-	mas_node_count(mas, 1);
-	if (unlikely(mas_is_err(mas)))
-		return 0;
-
 	node = mas_pop_node(mas);
 	pivots = ma_pivots(node, type);
 	slots = ma_slots(node, type);
@@ -3747,10 +3727,6 @@ static inline int mas_new_root(struct ma_state *mas, void *entry)
 		goto done;
 	}
 
-	mas_node_count(mas, 1);
-	if (mas_is_err(mas))
-		return 0;
-
 	node = mas_pop_node(mas);
 	pivots = ma_pivots(node, type);
 	slots = ma_slots(node, type);
@@ -3813,9 +3789,6 @@ static inline int mas_wr_spanning_store(struct ma_wr_state *wr_mas)
 	 * entries per level plus a new root.
 	 */
 	height = mas_mt_height(mas);
-	mas_node_count(mas, 1 + height * 3);
-	if (mas_is_err(mas))
-		return 0;
 
 	/*
 	 * Set up right side.  Need to get to the next offset after the spanning
@@ -3899,10 +3872,6 @@ static inline bool mas_wr_node_store(struct ma_wr_state *wr_mas,
 
 	/* set up node. */
 	if (in_rcu) {
-		mas_node_count(mas, 1);
-		if (mas_is_err(mas))
-			return false;
-
 		newnode = mas_pop_node(mas);
 	} else {
 		memset(&reuse, 0, sizeof(struct maple_node));
-- 
2.45.1

[PATCH 17/18] maple_tree: remove repeated sanity checks from mas_wr_append()

[Sidhartha Kumar]

These sanity checks are now redundant as they are already checked in
mas_wr_store_type(). We can remove them from mas_wr_append().

Signed-off-by: Sidhartha Kumar <sidhartha.kumar@oracle.com>
---
 lib/maple_tree.c | 12 ++----------
 1 file changed, 2 insertions(+), 10 deletions(-)

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index 3d2d8c2c24df..a90512d15549 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -4062,17 +4062,9 @@ static inline unsigned char mas_wr_new_end(struct ma_wr_state *wr_mas)
 static inline bool mas_wr_append(struct ma_wr_state *wr_mas,
 		unsigned char new_end)
 {
-	struct ma_state *mas;
+	struct ma_state *mas = wr_mas->mas;
 	void __rcu **slots;
-	unsigned char end;
-
-	mas = wr_mas->mas;
-	if (mt_in_rcu(mas->tree))
-		return false;
-
-	end = mas->end;
-	if (mas->offset != end)
-		return false;
+	unsigned char end = mas->end;
 
 	if (new_end < mt_pivots[wr_mas->type]) {
 		wr_mas->pivots[new_end] = wr_mas->pivots[end];
-- 
2.45.1

[PATCH 18/18] maple_tree: remove unneeded mas_wr_walk() in mas_store_prealloc()

[Sidhartha Kumar]

Users of mas_store_prealloc() enter this function with nodes already
preallocated. This means the store type must be already set. We can then
remove the call to mas_wr_store_type() and initialize the write state to
continue the partial walk that was done when determining the store type.

Signed-off-by: Sidhartha Kumar <sidhartha.kumar@oracle.com>
---
 lib/maple_tree.c | 18 +++++++++++++-----
 1 file changed, 13 insertions(+), 5 deletions(-)

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index a90512d15549..eeb8def13f63 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -4028,9 +4028,6 @@ static inline void mas_wr_end_piv(struct ma_wr_state *wr_mas)
 		wr_mas->end_piv = wr_mas->pivots[wr_mas->offset_end];
 	else
 		wr_mas->end_piv = wr_mas->mas->max;
-
-	if (!wr_mas->entry)
-		mas_wr_extend_null(wr_mas);
 }
 
 static inline unsigned char mas_wr_new_end(struct ma_wr_state *wr_mas)
@@ -5595,12 +5592,23 @@ void mas_store_prealloc(struct ma_state *mas, void *entry)
 {
 	MA_WR_STATE(wr_mas, mas, entry);
 
-	mas_wr_prealloc_setup(&wr_mas);
-	mas_wr_store_type(&wr_mas);
+	if (mas->store_type == wr_store_root) {
+		mas_wr_prealloc_setup(&wr_mas);
+		goto store;
+	}
+
+	mas_wr_walk_descend(&wr_mas);
+	if (mas->store_type != wr_spanning_store) {
+		/* set wr_mas->content to current slot */
+		wr_mas.content = mas_slot_locked(mas, wr_mas.slots, mas->offset);
+		mas_wr_end_piv(&wr_mas);
+	}
+store:
 	trace_ma_write(__func__, mas, 0, entry);
 	mas_wr_store_entry(&wr_mas);
 	MAS_WR_BUG_ON(&wr_mas, mas_is_err(mas));
 	mas_destroy(mas);
+
 }
 EXPORT_SYMBOL_GPL(mas_store_prealloc);
 
-- 
2.45.1

Re: [PATCH 04/18] maple_tree: introduce mas_wr_store_type()

[Liam R. Howlett]

* Sidhartha Kumar <sidhartha.kumar@oracle.com> [240604 13:42]:
> Introduce mas_wr_store_type() which will set the correct store type
> based on a walk of the tree.
> 
> mas_prealloc_calc() is also introduced to abstract the calculation used
> to determine the number of nodes needed for a store operation.
> 
> Also, add a test case to validate the ordering for store type checks is
> correct. This test models a vma expanding and then shrinking which is part
> of the boot process.
> 
> mas_wr_preallocate() is introduced as a wrapper function to set the store
> type and preallcoate enough nodes.
> 
> Signed-off-by: Sidhartha Kumar <sidhartha.kumar@oracle.com>
> ---
>  lib/maple_tree.c                 | 210 ++++++++++++++++++++++---------
>  tools/testing/radix-tree/maple.c |  35 ++++++
>  2 files changed, 186 insertions(+), 59 deletions(-)
> 
> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> index 2558d15bb748..b37fa8690558 100644
> --- a/lib/maple_tree.c
> +++ b/lib/maple_tree.c
> @@ -4278,6 +4278,150 @@ static inline void mas_wr_prealloc_setup(struct ma_wr_state *wr_mas)
>  	wr_mas->content = mas_start(mas);
>  }
>  
> +/**
> + * mas_prealloc_calc() - Calculate number of nodes needed for a
> + * given store oepration
> + * @mas: The maple state.
> + *
> + * Return: Number of nodes required for preallocation.
> + */
> +static inline int mas_prealloc_calc(struct ma_state *mas, void *entry)
> +{
> +	int ret = mas_mt_height(mas) * 3 + 1;
> +
> +	switch (mas->store_type) {
> +	case wr_invalid:
> +		WARN_ON_ONCE(1);
> +		break;
> +	case wr_new_root:
> +		ret = 1;
> +		break;
> +	case wr_store_root:
> +		if (likely((mas->last != 0) || (mas->index != 0)))
> +			ret = 1;
> +		else if (((unsigned long) (entry) & 3) == 2)
> +			ret = 1;
> +		else
> +			ret = 0;
> +		break;
> +	case wr_spanning_store:
> +		ret =  mas_mt_height(mas) * 3 + 1;
> +		break;
> +	case wr_split_store:
> +		ret =  mas_mt_height(mas) * 2 + 1;
> +		break;
> +	case wr_rebalance:
> +		ret =  mas_mt_height(mas) * 2 - 1;
> +		break;
> +	case wr_node_store:
> +	case wr_bnode:
> +		ret = mt_in_rcu(mas->tree) ? 1 : 0;
> +		break;
> +	case wr_append:
> +	case wr_exact_fit:
> +	case wr_slot_store:
> +		ret = 0;
> +	}
> +
> +	return ret;
> +}
> +
> +/*
> + * mas_wr_store_type() - Set the store type for a given
> + * store operation.
> + * @wr_mas: The maple write state
> + */
> +static inline void mas_wr_store_type(struct ma_wr_state *wr_mas)
> +{
> +	struct ma_state *mas = wr_mas->mas;
> +	unsigned char new_end;
> +
> +	if (unlikely(mas_is_none(mas) || mas_is_ptr(mas))) {
> +		mas->store_type = wr_store_root;
> +		return;
> +	}
> +
> +	if (unlikely(!mas_wr_walk(wr_mas))) {
> +		mas->store_type = wr_spanning_store;
> +		return;
> +	}
> +
> +	/* At this point, we are at the leaf node that needs to be altered. */
> +	mas_wr_end_piv(wr_mas);
> +	if (!wr_mas->entry)
> +		mas_wr_extend_null(wr_mas);
> +
> +	new_end = mas_wr_new_end(wr_mas);
> +	if ((wr_mas->r_min == mas->index) && (wr_mas->r_max == mas->last)) {
> +		mas->store_type = wr_exact_fit;
> +		return;
> +	}
> +
> +	if (unlikely(!mas->index && mas->last == ULONG_MAX)) {
> +		mas->store_type = wr_new_root;
> +		return;
> +	}
> +
> +	/* Potential spanning rebalance collapsing a node */
> +	if (new_end < mt_min_slots[wr_mas->type]) {
> +		if (!mte_is_root(mas->node)) {
> +			mas->store_type = wr_rebalance;
> +			return;
> +		}
> +		mas->store_type = wr_node_store;
> +		return;
> +	}
> +
> +	if (new_end >= mt_slots[wr_mas->type]) {
> +		mas->store_type = wr_split_store;
> +		return;
> +	}
> +
> +	if (!mt_in_rcu(mas->tree) && (mas->offset == mas->end)) {
> +		mas->store_type = wr_append;
> +		return;
> +	}
> +
> +	if ((new_end == mas->end) && (!mt_in_rcu(mas->tree) ||
> +		(wr_mas->offset_end - mas->offset == 1))) {
> +		mas->store_type = wr_slot_store;
> +		return;
> +	}
> +
> +	if (mte_is_root(mas->node) || !(new_end <= mt_min_slots[wr_mas->type]) ||
> +		(mas->mas_flags & MA_STATE_BULK)) {
> +		mas->store_type = wr_node_store;
> +		return;
> +	}
> +
> +	mas->store_type = wr_bnode;
> +}
> +
> +/**
> + * mas_wr_preallocate() - Preallocate enough nodes for a store operation
> + * @wr_mas: The maple write state
> + * @entry: The entry that will be stored
> + * @gfp: The GFP_FLAGS to use for allocations.
> + *
> + */
> +static inline void mas_wr_preallocate(struct ma_wr_state *wr_mas, void *entry, gfp_t gfp)
> +{
> +	struct ma_state *mas = wr_mas->mas;
> +	int request;
> +
> +	mas_wr_prealloc_setup(wr_mas);
> +	mas_wr_store_type(wr_mas);
> +	request = mas_prealloc_calc(mas, entry);
> +	if (!request)
> +		return;
> +
> +	mas_node_count_gfp(mas, request, gfp);
> +	if (likely(!mas_is_err(mas)))
> +		return;
> +
> +	mas_set_alloc_req(mas, 0);
> +}
> +
>  /**
>   * mas_insert() - Internal call to insert a value
>   * @mas: The maple state
> @@ -5506,69 +5650,17 @@ EXPORT_SYMBOL_GPL(mas_store_prealloc);
>  int mas_preallocate(struct ma_state *mas, void *entry, gfp_t gfp)
>  {
>  	MA_WR_STATE(wr_mas, mas, entry);
> -	unsigned char node_size;
> -	int request = 1;
> -	int ret;
> -
> -
> -	if (unlikely(!mas->index && mas->last == ULONG_MAX))
> -		goto ask_now;
> -
> -	mas_wr_prealloc_setup(&wr_mas);
> -	/* Root expand */
> -	if (unlikely(mas_is_none(mas) || mas_is_ptr(mas)))
> -		goto ask_now;
> -
> -	if (unlikely(!mas_wr_walk(&wr_mas))) {
> -		/* Spanning store, use worst case for now */
> -		request = 1 + mas_mt_height(mas) * 3;
> -		goto ask_now;
> -	}
> -
> -	/* At this point, we are at the leaf node that needs to be altered. */
> -	/* Exact fit, no nodes needed. */
> -	if (wr_mas.r_min == mas->index && wr_mas.r_max == mas->last)
> -		return 0;
> -
> -	mas_wr_end_piv(&wr_mas);
> -	node_size = mas_wr_new_end(&wr_mas);
> -
> -	/* Slot store, does not require additional nodes */
> -	if (node_size == mas->end) {
> -		/* reuse node */
> -		if (!mt_in_rcu(mas->tree))
> -			return 0;
> -		/* shifting boundary */
> -		if (wr_mas.offset_end - mas->offset == 1)
> -			return 0;
> -	}
> +	int ret = 0;
>  
> -	if (node_size >= mt_slots[wr_mas.type]) {
> -		/* Split, worst case for now. */
> -		request = 1 + mas_mt_height(mas) * 2;
> -		goto ask_now;
> +	mas_wr_preallocate(&wr_mas, entry, gfp);
> +	if (mas_is_err(mas)) {
> +		ret = xa_err(mas->node);

mas_reset(mas); was silently dropped here.  I don't think that's wrong,
but it should probably be mentioned or commented on.  I believe the
reset was necessary for the rebalance case, which may not be necessary
anymore and probably not an issue here.  Since the state is separated
from the node in the maple state, it may not be necessary to reset at
all anymore.

> +		mas_destroy(mas);
> +		mas_reset(mas);
> +		return ret;
>  	}
>  
> -	/* New root needs a single node */
> -	if (unlikely(mte_is_root(mas->node)))
> -		goto ask_now;
> -
> -	/* Potential spanning rebalance collapsing a node, use worst-case */
> -	if (node_size  - 1 <= mt_min_slots[wr_mas.type])
> -		request = mas_mt_height(mas) * 2 - 1;
> -
> -	/* node store, slot store needs one node */
> -ask_now:
> -	mas_node_count_gfp(mas, request, gfp);
>  	mas->mas_flags |= MA_STATE_PREALLOC;
> -	if (likely(!mas_is_err(mas)))
> -		return 0;
> -
> -	mas_set_alloc_req(mas, 0);
> -	ret = xa_err(mas->node);
> -	mas_reset(mas);
> -	mas_destroy(mas);
> -	mas_reset(mas);
>  	return ret;
>  }
>  EXPORT_SYMBOL_GPL(mas_preallocate);
> diff --git a/tools/testing/radix-tree/maple.c b/tools/testing/radix-tree/maple.c
> index f1caf4bcf937..c57979de1576 100644
> --- a/tools/testing/radix-tree/maple.c
> +++ b/tools/testing/radix-tree/maple.c
> @@ -36223,6 +36223,37 @@ static noinline void __init check_mtree_dup(struct maple_tree *mt)
>  
>  extern void test_kmem_cache_bulk(void);
>  
> +
> + /* test to simulate expanding a vma from [0x7fffffffe000, 0x7ffffffff000)
> +  * to [0x7ffde4ca1000, 0x7ffffffff000) and then shrinking the vma to
> +  * [0x7ffde4ca1000, 0x7ffde4ca2000)
> +  */
> +static inline int check_vma_modification(struct maple_tree *mt)
> +{
> +	MA_STATE(mas, mt, 0, 0);


Don't we need locking in here?

> +
> +	/* vma with old start and old end */
> +	__mas_set_range(&mas, 0x7fffffffe000, 0x7ffffffff000 - 1);
> +	mas_preallocate(&mas, xa_mk_value(1), GFP_KERNEL);
> +	mas_store_prealloc(&mas, xa_mk_value(1));
> +
> +	/* next write occurs partly in previous range [0, 0x7fffffffe000)*/
> +	mas_prev_range(&mas, 0);
> +	/* expand vma to {0x7ffde4ca1000, 0x7ffffffff000) */
> +	__mas_set_range(&mas, 0x7ffde4ca1000, 0x7ffffffff000 - 1);
> +	mas_preallocate(&mas, xa_mk_value(1), GFP_KERNEL);
> +	mas_store_prealloc(&mas, xa_mk_value(1));
> +
> +	/* shrink vma to [0x7ffde4ca1000, 7ffde4ca2000) */
> +	__mas_set_range(&mas, 0x7ffde4ca2000, 0x7ffffffff000 - 1);
> +	mas_preallocate(&mas, NULL, GFP_KERNEL);
> +	mas_store_prealloc(&mas, NULL);
> +	mt_dump(mt, mt_dump_hex);
> +
> +	return 0;
> +}
> +
> +
>  void farmer_tests(void)
>  {
>  	struct maple_node *node;
> @@ -36230,6 +36261,10 @@ void farmer_tests(void)
>  
>  	mt_dump(&tree, mt_dump_dec);
>  
> +	mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE | MT_FLAGS_LOCK_EXTERN | MT_FLAGS_USE_RCU);
> +	check_vma_modification(&tree);
> +	mtree_destroy(&tree);
> +
>  	tree.ma_root = xa_mk_value(0);
>  	mt_dump(&tree, mt_dump_dec);
>  
> -- 
> 2.45.1
> 

Re: [PATCH 06/18] maple_tree: remove mas_destroy() from mas_nomem()

[Liam R. Howlett]

* Sidhartha Kumar <sidhartha.kumar@oracle.com> [240604 13:42]:
> Separate call to mas_destroy() from mas_nomem() so we can check for no
> memory errors without destroying the current maple state in
> mas_store_gfp(). We then add calls to mas_destroy() to callers of
> mas_nomem().
> 
> Signed-off-by: Sidhartha Kumar <sidhartha.kumar@oracle.com>
> ---
>  lib/maple_tree.c                 | 39 ++++++++++++++++++++------------
>  tools/testing/radix-tree/maple.c | 11 +++++----
>  2 files changed, 31 insertions(+), 19 deletions(-)
> 
> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> index 3780d4bb0415..f1496817e52a 100644
> --- a/lib/maple_tree.c
> +++ b/lib/maple_tree.c
> @@ -4526,6 +4526,7 @@ int mas_alloc_cyclic(struct ma_state *mas, unsigned long *startp,
>  	if (*next == 0)
>  		mas->tree->ma_flags |= MT_FLAGS_ALLOC_WRAPPED;
>  
> +	mas_destroy(mas);
>  	return ret;
>  }
>  EXPORT_SYMBOL(mas_alloc_cyclic);
> @@ -5606,18 +5607,22 @@ EXPORT_SYMBOL_GPL(mas_store);
>  int mas_store_gfp(struct ma_state *mas, void *entry, gfp_t gfp)
>  {
>  	MA_WR_STATE(wr_mas, mas, entry);
> +	int ret;
>  
> -	mas_wr_store_setup(&wr_mas);
> -	trace_ma_write(__func__, mas, 0, entry);
>  retry:
> -	mas_wr_store_entry(&wr_mas);
> +	mas_wr_preallocate(&wr_mas, entry, gfp);
> +	WARN_ON_ONCE(mas->store_type == wr_invalid);
> +
>  	if (unlikely(mas_nomem(mas, gfp)))
>  		goto retry;

Nit: missing new line

> +	if (mas_is_err(mas))
> +		goto out;
>  
> -	if (unlikely(mas_is_err(mas)))
> -		return xa_err(mas->node);
> -
> -	return 0;
> +	mas_wr_store_entry(&wr_mas);
> +out:
> +	ret = xa_err(mas->node);

Looking at what xa_err() does, it would probably be wise to only assign
the ret to xa_err() on mas_is_err(), which you do elsewhere so I'm not
sure why this is special.

> +	mas_destroy(mas);
> +	return ret;
>  }
>  EXPORT_SYMBOL_GPL(mas_store_gfp);
>  
> @@ -6365,6 +6370,7 @@ void *mas_erase(struct ma_state *mas)
>  	if (mas_nomem(mas, GFP_KERNEL))
>  		goto write_retry;
>  
> +	mas_destroy(mas);
>  	return entry;
>  }
>  EXPORT_SYMBOL_GPL(mas_erase);
> @@ -6379,10 +6385,8 @@ EXPORT_SYMBOL_GPL(mas_erase);
>  bool mas_nomem(struct ma_state *mas, gfp_t gfp)
>  	__must_hold(mas->tree->ma_lock)
>  {
> -	if (likely(mas->node != MA_ERROR(-ENOMEM))) {
> -		mas_destroy(mas);
> +	if (likely(mas->node != MA_ERROR(-ENOMEM)))
>  		return false;
> -	}
>  
>  	if (gfpflags_allow_blocking(gfp) && !mt_external_lock(mas->tree)) {
>  		mtree_unlock(mas->tree);
> @@ -6460,6 +6464,7 @@ int mtree_store_range(struct maple_tree *mt, unsigned long index,
>  {
>  	MA_STATE(mas, mt, index, last);
>  	MA_WR_STATE(wr_mas, &mas, entry);
> +	int ret = 0;
>  
>  	trace_ma_write(__func__, &mas, 0, entry);
>  	if (WARN_ON_ONCE(xa_is_advanced(entry)))
> @@ -6475,10 +6480,12 @@ int mtree_store_range(struct maple_tree *mt, unsigned long index,
>  		goto retry;
>  
>  	mtree_unlock(mt);
> +
>  	if (mas_is_err(&mas))
> -		return xa_err(mas.node);
> +		ret = xa_err(mas.node);
>  
> -	return 0;
> +	mas_destroy(&mas);
> +	return ret;
>  }
>  EXPORT_SYMBOL(mtree_store_range);
>  
> @@ -6514,6 +6521,7 @@ int mtree_insert_range(struct maple_tree *mt, unsigned long first,
>  		unsigned long last, void *entry, gfp_t gfp)
>  {
>  	MA_STATE(ms, mt, first, last);
> +	int ret = 0;
>  
>  	if (WARN_ON_ONCE(xa_is_advanced(entry)))
>  		return -EINVAL;
> @@ -6529,9 +6537,10 @@ int mtree_insert_range(struct maple_tree *mt, unsigned long first,
>  
>  	mtree_unlock(mt);
>  	if (mas_is_err(&ms))
> -		return xa_err(ms.node);
> +		ret = xa_err(ms.node);
>  
> -	return 0;
> +	mas_destroy(&ms);
> +	return ret;
>  }
>  EXPORT_SYMBOL(mtree_insert_range);
>  
> @@ -6586,6 +6595,7 @@ int mtree_alloc_range(struct maple_tree *mt, unsigned long *startp,
>  
>  unlock:
>  	mtree_unlock(mt);
> +	mas_destroy(&mas);
>  	return ret;
>  }
>  EXPORT_SYMBOL(mtree_alloc_range);
> @@ -6667,6 +6677,7 @@ int mtree_alloc_rrange(struct maple_tree *mt, unsigned long *startp,
>  
>  unlock:
>  	mtree_unlock(mt);
> +	mas_destroy(&mas);
>  	return ret;
>  }
>  EXPORT_SYMBOL(mtree_alloc_rrange);
> diff --git a/tools/testing/radix-tree/maple.c b/tools/testing/radix-tree/maple.c
> index c57979de1576..c834e91e6810 100644
> --- a/tools/testing/radix-tree/maple.c
> +++ b/tools/testing/radix-tree/maple.c
> @@ -119,7 +119,7 @@ static noinline void __init check_new_node(struct maple_tree *mt)
>  	MT_BUG_ON(mt, mas.alloc->slot[0] == NULL);
>  	mas_push_node(&mas, mn);
>  	mas_reset(&mas);
> -	mas_nomem(&mas, GFP_KERNEL); /* free */
> +	mas_destroy(&mas);
>  	mtree_unlock(mt);
>  
>  
> @@ -143,7 +143,7 @@ static noinline void __init check_new_node(struct maple_tree *mt)
>  	mn->parent = ma_parent_ptr(mn);
>  	ma_free_rcu(mn);
>  	mas.status = ma_start;
> -	mas_nomem(&mas, GFP_KERNEL);
> +	mas_destroy(&mas);
>  	/* Allocate 3 nodes, will fail. */
>  	mas_node_count(&mas, 3);
>  	/* Drop the lock and allocate 3 nodes. */
> @@ -160,7 +160,7 @@ static noinline void __init check_new_node(struct maple_tree *mt)
>  	MT_BUG_ON(mt, mas_allocated(&mas) != 3);
>  	/* Free. */
>  	mas_reset(&mas);
> -	mas_nomem(&mas, GFP_KERNEL);
> +	mas_destroy(&mas);
>  
>  	/* Set allocation request to 1. */
>  	mas_set_alloc_req(&mas, 1);
> @@ -275,7 +275,7 @@ static noinline void __init check_new_node(struct maple_tree *mt)
>  			MT_BUG_ON(mt, mas_allocated(&mas) != i - j - 1);
>  		}
>  		mas_reset(&mas);
> -		MT_BUG_ON(mt, mas_nomem(&mas, GFP_KERNEL));
> +		mas_destroy(&mas);

This was checking something with an MT_BUG_ON() that was dropped.  Can
we check it another way?

>  
>  	}
>  
> @@ -298,7 +298,7 @@ static noinline void __init check_new_node(struct maple_tree *mt)
>  	}
>  	MT_BUG_ON(mt, mas_allocated(&mas) != total);
>  	mas_reset(&mas);
> -	mas_nomem(&mas, GFP_KERNEL); /* Free. */
> +	mas_destroy(&mas); /* Free. */
>  
>  	MT_BUG_ON(mt, mas_allocated(&mas) != 0);
>  	for (i = 1; i < 128; i++) {
> @@ -35846,6 +35846,7 @@ static noinline void __init check_nomem(struct maple_tree *mt)
>  	mas_store(&ms, &ms); /* insert 1 -> &ms */
>  	mas_nomem(&ms, GFP_KERNEL); /* Node allocated in here. */
>  	mtree_unlock(mt);
> +	mas_destroy(&ms);
>  	mtree_destroy(mt);
>  }
>  
> -- 
> 2.45.1
> 

Re: [PATCH 09/18] maple_tree: use mas_store_gfp() in mtree_store_range()

[Liam R. Howlett]

* Sidhartha Kumar <sidhartha.kumar@oracle.com> [240604 13:42]:
> Refactor mtree_store_range() to use mas_store_gfp() which will abstract
> the store, memory allocation, and error handling.
> 
> Signed-off-by: Sidhartha Kumar <sidhartha.kumar@oracle.com>
> ---
>  lib/maple_tree.c | 12 ++----------
>  1 file changed, 2 insertions(+), 10 deletions(-)
> 
> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> index 34ff1b3f729c..e3ec6649f7da 100644
> --- a/lib/maple_tree.c
> +++ b/lib/maple_tree.c
> @@ -6457,7 +6457,6 @@ int mtree_store_range(struct maple_tree *mt, unsigned long index,
>  		unsigned long last, void *entry, gfp_t gfp)
>  {
>  	MA_STATE(mas, mt, index, last);
> -	MA_WR_STATE(wr_mas, &mas, entry);
>  	int ret = 0;
>  
>  	trace_ma_write(__func__, &mas, 0, entry);
> @@ -6468,17 +6467,10 @@ int mtree_store_range(struct maple_tree *mt, unsigned long index,
>  		return -EINVAL;
>  
>  	mtree_lock(mt);
> -retry:
> -	mas_wr_store_entry(&wr_mas);
> -	if (mas_nomem(&mas, gfp))
> -		goto retry;
> -
> +	ret = mas_store_gfp(&mas, entry, gfp);
>  	mtree_unlock(mt);
>  
> -	if (mas_is_err(&mas))
> -		ret = xa_err(mas.node);
> -
> -	mas_destroy(&mas);
> +	MT_BUG_ON(mas.tree, mas.store_type == wr_invalid);

This check should be inside the lock as it dumps the tree.

>  	return ret;
>  }
>  EXPORT_SYMBOL(mtree_store_range);
> -- 
> 2.45.1
> 

Re: [PATCH 05/18] maple_tree: set store type in mas_store_prealloc()

[Liam R. Howlett]

* Sidhartha Kumar <sidhartha.kumar@oracle.com> [240604 13:42]:
> Set the store type in mas_store_prealloc(). This is needed as
> mas_wr_store_entry() will be modified to read the store type to make a
> decision about how to complete the store.

You have two of these small patches, one has a different description
"set write store type" vs "set store type".  I think they both can be
combined into the mas_wr_store_entry() modification?  They are pretty
straight forward and the commit log can explain them.

> 
> Signed-off-by: Sidhartha Kumar <sidhartha.kumar@oracle.com>
> ---
>  lib/maple_tree.c | 3 ++-
>  1 file changed, 2 insertions(+), 1 deletion(-)
> 
> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> index b37fa8690558..3780d4bb0415 100644
> --- a/lib/maple_tree.c
> +++ b/lib/maple_tree.c
> @@ -5631,7 +5631,8 @@ void mas_store_prealloc(struct ma_state *mas, void *entry)
>  {
>  	MA_WR_STATE(wr_mas, mas, entry);
>  
> -	mas_wr_store_setup(&wr_mas);
> +	mas_wr_prealloc_setup(&wr_mas);
> +	mas_wr_store_type(&wr_mas);
>  	trace_ma_write(__func__, mas, 0, entry);
>  	mas_wr_store_entry(&wr_mas);
>  	MAS_WR_BUG_ON(&wr_mas, mas_is_err(mas));
> -- 
> 2.45.1
> 

Re: [PATCH 13/18] maple_tree: simplify mas_commit_b_node()

[Liam R. Howlett]

* Sidhartha Kumar <sidhartha.kumar@oracle.com> [240604 13:42]:
> Use mas->store_type to simplify the logic of identifying the type of
> write.

Since b_type is now only used in one location, we can use
mas_new_ma_node() instead of mt_mk_node() and remove b_type entirely
from this function.  This is also true of the maple_node *node pointer.

old_enode and b_end could also be moved below all the returns as they
are only used after all the other options.

> 
> Signed-off-by: Sidhartha Kumar <sidhartha.kumar@oracle.com>
> ---
>  lib/maple_tree.c | 6 ++----
>  1 file changed, 2 insertions(+), 4 deletions(-)
> 
> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> index 314691fd1c67..faadddbe2086 100644
> --- a/lib/maple_tree.c
> +++ b/lib/maple_tree.c
> @@ -3437,12 +3437,10 @@ static noinline_for_kasan int mas_commit_b_node(struct ma_wr_state *wr_mas,
>  	enum maple_type b_type = b_node->type;
>  
>  	old_enode = wr_mas->mas->node;
> -	if ((b_end < mt_min_slots[b_type]) &&
> -	    (!mte_is_root(old_enode)) &&
> -	    (mas_mt_height(wr_mas->mas) > 1))
> +	if (wr_mas->mas->store_type == wr_rebalance)
>  		return mas_rebalance(wr_mas->mas, b_node);
>  
> -	if (b_end >= mt_slots[b_type])
> +	if (wr_mas->mas->store_type == wr_split_store)
>  		return mas_split(wr_mas->mas, b_node);
>  
>  	if (mas_reuse_node(wr_mas, b_node, end))
> -- 
> 2.45.1
> 

Re: [PATCH 04/18] maple_tree: introduce mas_wr_store_type()

[kernel test robot]

Hi Sidhartha,

kernel test robot noticed the following build warnings:

[auto build test WARNING on akpm-mm/mm-nonmm-unstable]
[also build test WARNING on linus/master v6.10-rc2 next-20240604]
[If your patch is applied to the wrong git tree, kindly drop us a note.
And when submitting patch, we suggest to use '--base' as documented in
https://git-scm.com/docs/git-format-patch#_base_tree_information]

url:    https://github.com/intel-lab-lkp/linux/commits/Sidhartha-Kumar/maple_tree-introduce-store_type-enum/20240605-014633
base:   https://git.kernel.org/pub/scm/linux/kernel/git/akpm/mm.git mm-nonmm-unstable
patch link:    https://lore.kernel.org/r/20240604174145.563900-5-sidhartha.kumar%40oracle.com
patch subject: [PATCH 04/18] maple_tree: introduce mas_wr_store_type()
config: openrisc-allnoconfig (https://download.01.org/0day-ci/archive/20240605/202406050440.xjLxhyu5-lkp@intel.com/config)
compiler: or1k-linux-gcc (GCC) 13.2.0
reproduce (this is a W=1 build): (https://download.01.org/0day-ci/archive/20240605/202406050440.xjLxhyu5-lkp@intel.com/reproduce)

If you fix the issue in a separate patch/commit (i.e. not just a new version of
the same patch/commit), kindly add following tags
| Reported-by: kernel test robot <lkp@intel.com>
| Closes: https://lore.kernel.org/oe-kbuild-all/202406050440.xjLxhyu5-lkp@intel.com/

All warnings (new ones prefixed by >>):

>> lib/maple_tree.c:4289: warning: Function parameter or struct member 'entry' not described in 'mas_prealloc_calc'


vim +4289 lib/maple_tree.c

  4280	
  4281	/**
  4282	 * mas_prealloc_calc() - Calculate number of nodes needed for a
  4283	 * given store oepration
  4284	 * @mas: The maple state.
  4285	 *
  4286	 * Return: Number of nodes required for preallocation.
  4287	 */
  4288	static inline int mas_prealloc_calc(struct ma_state *mas, void *entry)
> 4289	{
  4290		int ret = mas_mt_height(mas) * 3 + 1;
  4291	
  4292		switch (mas->store_type) {
  4293		case wr_invalid:
  4294			WARN_ON_ONCE(1);
  4295			break;
  4296		case wr_new_root:
  4297			ret = 1;
  4298			break;
  4299		case wr_store_root:
  4300			if (likely((mas->last != 0) || (mas->index != 0)))
  4301				ret = 1;
  4302			else if (((unsigned long) (entry) & 3) == 2)
  4303				ret = 1;
  4304			else
  4305				ret = 0;
  4306			break;
  4307		case wr_spanning_store:
  4308			ret =  mas_mt_height(mas) * 3 + 1;
  4309			break;
  4310		case wr_split_store:
  4311			ret =  mas_mt_height(mas) * 2 + 1;
  4312			break;
  4313		case wr_rebalance:
  4314			ret =  mas_mt_height(mas) * 2 - 1;
  4315			break;
  4316		case wr_node_store:
  4317		case wr_bnode:
  4318			ret = mt_in_rcu(mas->tree) ? 1 : 0;
  4319			break;
  4320		case wr_append:
  4321		case wr_exact_fit:
  4322		case wr_slot_store:
  4323			ret = 0;
  4324		}
  4325	
  4326		return ret;
  4327	}
  4328	

-- 
0-DAY CI Kernel Test Service
https://github.com/intel/lkp-tests/wiki

Re: [PATCH 11/18] maple_tree: use store type in mas_wr_store_entry()

[kernel test robot]

Hi Sidhartha,

kernel test robot noticed the following build warnings:

[auto build test WARNING on akpm-mm/mm-nonmm-unstable]
[also build test WARNING on linus/master v6.10-rc2 next-20240604]
[If your patch is applied to the wrong git tree, kindly drop us a note.
And when submitting patch, we suggest to use '--base' as documented in
https://git-scm.com/docs/git-format-patch#_base_tree_information]

url:    https://github.com/intel-lab-lkp/linux/commits/Sidhartha-Kumar/maple_tree-introduce-store_type-enum/20240605-014633
base:   https://git.kernel.org/pub/scm/linux/kernel/git/akpm/mm.git mm-nonmm-unstable
patch link:    https://lore.kernel.org/r/20240604174145.563900-12-sidhartha.kumar%40oracle.com
patch subject: [PATCH 11/18] maple_tree: use store type in mas_wr_store_entry()
config: um-allnoconfig (https://download.01.org/0day-ci/archive/20240605/202406050515.BP3o0Meg-lkp@intel.com/config)
compiler: clang version 17.0.6 (https://github.com/llvm/llvm-project 6009708b4367171ccdbf4b5905cb6a803753fe18)
reproduce (this is a W=1 build): (https://download.01.org/0day-ci/archive/20240605/202406050515.BP3o0Meg-lkp@intel.com/reproduce)

If you fix the issue in a separate patch/commit (i.e. not just a new version of
the same patch/commit), kindly add following tags
| Reported-by: kernel test robot <lkp@intel.com>
| Closes: https://lore.kernel.org/oe-kbuild-all/202406050515.BP3o0Meg-lkp@intel.com/

All warnings (new ones prefixed by >>):

   lib/maple_tree.c:351:21: warning: unused function 'mte_set_full' [-Wunused-function]
     351 | static inline void *mte_set_full(const struct maple_enode *node)
         |                     ^~~~~~~~~~~~
   lib/maple_tree.c:356:21: warning: unused function 'mte_clear_full' [-Wunused-function]
     356 | static inline void *mte_clear_full(const struct maple_enode *node)
         |                     ^~~~~~~~~~~~~~
   lib/maple_tree.c:361:20: warning: unused function 'mte_has_null' [-Wunused-function]
     361 | static inline bool mte_has_null(const struct maple_enode *node)
         |                    ^~~~~~~~~~~~
>> lib/maple_tree.c:4206:21: warning: stack frame size (1032) exceeds limit (1024) in 'mas_wr_store_entry' [-Wframe-larger-than]
    4206 | static inline void *mas_wr_store_entry(struct ma_wr_state *wr_mas)
         |                     ^
   lib/maple_tree.c:4151:13: warning: stack frame size (1048) exceeds limit (1024) in 'mas_wr_bnode' [-Wframe-larger-than]
    4151 | static void mas_wr_bnode(struct ma_wr_state *wr_mas)
         |             ^
   5 warnings generated.


vim +/mas_wr_store_entry +4206 lib/maple_tree.c

54a611b605901c Liam R. Howlett 2022-09-06  4198  
54a611b605901c Liam R. Howlett 2022-09-06  4199  /*
54a611b605901c Liam R. Howlett 2022-09-06  4200   * mas_wr_store_entry() - Internal call to store a value
54a611b605901c Liam R. Howlett 2022-09-06  4201   * @mas: The maple state
54a611b605901c Liam R. Howlett 2022-09-06  4202   * @entry: The entry to store.
54a611b605901c Liam R. Howlett 2022-09-06  4203   *
54a611b605901c Liam R. Howlett 2022-09-06  4204   * Return: The contents that was stored at the index.
54a611b605901c Liam R. Howlett 2022-09-06  4205   */
54a611b605901c Liam R. Howlett 2022-09-06 @4206  static inline void *mas_wr_store_entry(struct ma_wr_state *wr_mas)
54a611b605901c Liam R. Howlett 2022-09-06  4207  {
54a611b605901c Liam R. Howlett 2022-09-06  4208  	struct ma_state *mas = wr_mas->mas;
7ad45cca258711 Sidhartha Kumar 2024-06-04  4209  	unsigned char new_end = mas_wr_new_end(wr_mas);
54a611b605901c Liam R. Howlett 2022-09-06  4210  
7ad45cca258711 Sidhartha Kumar 2024-06-04  4211  	switch (mas->store_type) {
7ad45cca258711 Sidhartha Kumar 2024-06-04  4212  	case wr_invalid:
7ad45cca258711 Sidhartha Kumar 2024-06-04  4213  		MT_BUG_ON(mas->tree, 1);
7ad45cca258711 Sidhartha Kumar 2024-06-04  4214  		return NULL;
7ad45cca258711 Sidhartha Kumar 2024-06-04  4215  	case wr_new_root:
7ad45cca258711 Sidhartha Kumar 2024-06-04  4216  		mas_new_root(mas, wr_mas->entry);
7ad45cca258711 Sidhartha Kumar 2024-06-04  4217  		break;
7ad45cca258711 Sidhartha Kumar 2024-06-04  4218  	case wr_store_root:
54a611b605901c Liam R. Howlett 2022-09-06  4219  		mas_store_root(mas, wr_mas->entry);
7ad45cca258711 Sidhartha Kumar 2024-06-04  4220  		break;
7ad45cca258711 Sidhartha Kumar 2024-06-04  4221  	case wr_exact_fit:
7ad45cca258711 Sidhartha Kumar 2024-06-04  4222  		rcu_assign_pointer(wr_mas->slots[mas->offset], wr_mas->entry);
7ad45cca258711 Sidhartha Kumar 2024-06-04  4223  		if (!!wr_mas->entry ^ !!wr_mas->content)
7ad45cca258711 Sidhartha Kumar 2024-06-04  4224  			mas_update_gap(mas);
7ad45cca258711 Sidhartha Kumar 2024-06-04  4225  		break;
7ad45cca258711 Sidhartha Kumar 2024-06-04  4226  	case wr_append:
7ad45cca258711 Sidhartha Kumar 2024-06-04  4227  		mas_wr_append(wr_mas, new_end);
7ad45cca258711 Sidhartha Kumar 2024-06-04  4228  		break;
7ad45cca258711 Sidhartha Kumar 2024-06-04  4229  	case wr_slot_store:
7ad45cca258711 Sidhartha Kumar 2024-06-04  4230  		mas_wr_slot_store(wr_mas);
7ad45cca258711 Sidhartha Kumar 2024-06-04  4231  		break;
7ad45cca258711 Sidhartha Kumar 2024-06-04  4232  	case wr_node_store:
7ad45cca258711 Sidhartha Kumar 2024-06-04  4233  		mas_wr_node_store(wr_mas, new_end);
7ad45cca258711 Sidhartha Kumar 2024-06-04  4234  		break;
7ad45cca258711 Sidhartha Kumar 2024-06-04  4235  	case wr_spanning_store:
54a611b605901c Liam R. Howlett 2022-09-06  4236  		mas_wr_spanning_store(wr_mas);
7ad45cca258711 Sidhartha Kumar 2024-06-04  4237  		break;
7ad45cca258711 Sidhartha Kumar 2024-06-04  4238  	case wr_split_store:
7ad45cca258711 Sidhartha Kumar 2024-06-04  4239  	case wr_rebalance:
7ad45cca258711 Sidhartha Kumar 2024-06-04  4240  	case wr_bnode:
7ad45cca258711 Sidhartha Kumar 2024-06-04  4241  		mas_wr_bnode(wr_mas);
7ad45cca258711 Sidhartha Kumar 2024-06-04  4242  		break;
54a611b605901c Liam R. Howlett 2022-09-06  4243  	}
54a611b605901c Liam R. Howlett 2022-09-06  4244  
54a611b605901c Liam R. Howlett 2022-09-06  4245  	return wr_mas->content;
54a611b605901c Liam R. Howlett 2022-09-06  4246  }
54a611b605901c Liam R. Howlett 2022-09-06  4247  

-- 
0-DAY CI Kernel Test Service
https://github.com/intel/lkp-tests/wiki

Re: [PATCH 12/18] maple_tree: convert mas_insert() to preallocate nodes

[kernel test robot]

Hi Sidhartha,

kernel test robot noticed the following build warnings:

[auto build test WARNING on akpm-mm/mm-nonmm-unstable]
[also build test WARNING on linus/master v6.10-rc2 next-20240604]
[If your patch is applied to the wrong git tree, kindly drop us a note.
And when submitting patch, we suggest to use '--base' as documented in
https://git-scm.com/docs/git-format-patch#_base_tree_information]

url:    https://github.com/intel-lab-lkp/linux/commits/Sidhartha-Kumar/maple_tree-introduce-store_type-enum/20240605-014633
base:   https://git.kernel.org/pub/scm/linux/kernel/git/akpm/mm.git mm-nonmm-unstable
patch link:    https://lore.kernel.org/r/20240604174145.563900-13-sidhartha.kumar%40oracle.com
patch subject: [PATCH 12/18] maple_tree: convert mas_insert() to preallocate nodes
config: openrisc-allnoconfig (https://download.01.org/0day-ci/archive/20240605/202406050614.NwHTjXFD-lkp@intel.com/config)
compiler: or1k-linux-gcc (GCC) 13.2.0
reproduce (this is a W=1 build): (https://download.01.org/0day-ci/archive/20240605/202406050614.NwHTjXFD-lkp@intel.com/reproduce)

If you fix the issue in a separate patch/commit (i.e. not just a new version of
the same patch/commit), kindly add following tags
| Reported-by: kernel test robot <lkp@intel.com>
| Closes: https://lore.kernel.org/oe-kbuild-all/202406050614.NwHTjXFD-lkp@intel.com/

All warnings (new ones prefixed by >>):

   lib/maple_tree.c:4304: warning: Function parameter or struct member 'entry' not described in 'mas_prealloc_calc'
>> lib/maple_tree.c:4449: warning: Function parameter or struct member 'gfp' not described in 'mas_insert'


vim +4449 lib/maple_tree.c

e0c5446b52f6a9 Sidhartha Kumar 2024-06-04  4439  
54a611b605901c Liam R. Howlett 2022-09-06  4440  /**
54a611b605901c Liam R. Howlett 2022-09-06  4441   * mas_insert() - Internal call to insert a value
54a611b605901c Liam R. Howlett 2022-09-06  4442   * @mas: The maple state
54a611b605901c Liam R. Howlett 2022-09-06  4443   * @entry: The entry to store
54a611b605901c Liam R. Howlett 2022-09-06  4444   *
54a611b605901c Liam R. Howlett 2022-09-06  4445   * Return: %NULL or the contents that already exists at the requested index
54a611b605901c Liam R. Howlett 2022-09-06  4446   * otherwise.  The maple state needs to be checked for error conditions.
54a611b605901c Liam R. Howlett 2022-09-06  4447   */
9d36d13535c7c8 Sidhartha Kumar 2024-06-04  4448  static inline void *mas_insert(struct ma_state *mas, void *entry, gfp_t gfp)
54a611b605901c Liam R. Howlett 2022-09-06 @4449  {
54a611b605901c Liam R. Howlett 2022-09-06  4450  	MA_WR_STATE(wr_mas, mas, entry);
54a611b605901c Liam R. Howlett 2022-09-06  4451  
54a611b605901c Liam R. Howlett 2022-09-06  4452  	/*
54a611b605901c Liam R. Howlett 2022-09-06  4453  	 * Inserting a new range inserts either 0, 1, or 2 pivots within the
54a611b605901c Liam R. Howlett 2022-09-06  4454  	 * tree.  If the insert fits exactly into an existing gap with a value
54a611b605901c Liam R. Howlett 2022-09-06  4455  	 * of NULL, then the slot only needs to be written with the new value.
54a611b605901c Liam R. Howlett 2022-09-06  4456  	 * If the range being inserted is adjacent to another range, then only a
54a611b605901c Liam R. Howlett 2022-09-06  4457  	 * single pivot needs to be inserted (as well as writing the entry).  If
54a611b605901c Liam R. Howlett 2022-09-06  4458  	 * the new range is within a gap but does not touch any other ranges,
54a611b605901c Liam R. Howlett 2022-09-06  4459  	 * then two pivots need to be inserted: the start - 1, and the end.  As
54a611b605901c Liam R. Howlett 2022-09-06  4460  	 * usual, the entry must be written.  Most operations require a new node
54a611b605901c Liam R. Howlett 2022-09-06  4461  	 * to be allocated and replace an existing node to ensure RCU safety,
54a611b605901c Liam R. Howlett 2022-09-06  4462  	 * when in RCU mode.  The exception to requiring a newly allocated node
54a611b605901c Liam R. Howlett 2022-09-06  4463  	 * is when inserting at the end of a node (appending).  When done
54a611b605901c Liam R. Howlett 2022-09-06  4464  	 * carefully, appending can reuse the node in place.
54a611b605901c Liam R. Howlett 2022-09-06  4465  	 */
54a611b605901c Liam R. Howlett 2022-09-06  4466  	wr_mas.content = mas_start(mas);
54a611b605901c Liam R. Howlett 2022-09-06  4467  	if (wr_mas.content)
54a611b605901c Liam R. Howlett 2022-09-06  4468  		goto exists;
54a611b605901c Liam R. Howlett 2022-09-06  4469  
9d36d13535c7c8 Sidhartha Kumar 2024-06-04  4470  	mas_wr_preallocate(&wr_mas, entry, gfp);
9d36d13535c7c8 Sidhartha Kumar 2024-06-04  4471  	if (mas_is_err(mas))
54a611b605901c Liam R. Howlett 2022-09-06  4472  		return NULL;
54a611b605901c Liam R. Howlett 2022-09-06  4473  
54a611b605901c Liam R. Howlett 2022-09-06  4474  	/* spanning writes always overwrite something */
9d36d13535c7c8 Sidhartha Kumar 2024-06-04  4475  	if (mas->store_type == wr_spanning_store)
54a611b605901c Liam R. Howlett 2022-09-06  4476  		goto exists;
54a611b605901c Liam R. Howlett 2022-09-06  4477  
54a611b605901c Liam R. Howlett 2022-09-06  4478  	/* At this point, we are at the leaf node that needs to be altered. */
9d36d13535c7c8 Sidhartha Kumar 2024-06-04  4479  	if (mas->store_type != wr_new_root && mas->store_type != wr_store_root) {
54a611b605901c Liam R. Howlett 2022-09-06  4480  		wr_mas.offset_end = mas->offset;
54a611b605901c Liam R. Howlett 2022-09-06  4481  		wr_mas.end_piv = wr_mas.r_max;
54a611b605901c Liam R. Howlett 2022-09-06  4482  
54a611b605901c Liam R. Howlett 2022-09-06  4483  		if (wr_mas.content || (mas->last > wr_mas.r_max))
54a611b605901c Liam R. Howlett 2022-09-06  4484  			goto exists;
9d36d13535c7c8 Sidhartha Kumar 2024-06-04  4485  	}
54a611b605901c Liam R. Howlett 2022-09-06  4486  
9d36d13535c7c8 Sidhartha Kumar 2024-06-04  4487  	mas_wr_store_entry(&wr_mas);
54a611b605901c Liam R. Howlett 2022-09-06  4488  	return wr_mas.content;
54a611b605901c Liam R. Howlett 2022-09-06  4489  
54a611b605901c Liam R. Howlett 2022-09-06  4490  exists:
54a611b605901c Liam R. Howlett 2022-09-06  4491  	mas_set_err(mas, -EEXIST);
54a611b605901c Liam R. Howlett 2022-09-06  4492  	return wr_mas.content;
54a611b605901c Liam R. Howlett 2022-09-06  4493  

-- 
0-DAY CI Kernel Test Service
https://github.com/intel/lkp-tests/wiki

Re: [PATCH 04/18] maple_tree: introduce mas_wr_store_type()

[Sidhartha Kumar]

On 6/4/24 12:07 PM, Liam R. Howlett wrote:
> * Sidhartha Kumar <sidhartha.kumar@oracle.com> [240604 13:42]:
>> Introduce mas_wr_store_type() which will set the correct store type
>> based on a walk of the tree.
>>
>> mas_prealloc_calc() is also introduced to abstract the calculation used
>> to determine the number of nodes needed for a store operation.
>>
>> Also, add a test case to validate the ordering for store type checks is
>> correct. This test models a vma expanding and then shrinking which is part
>> of the boot process.
>>
>> mas_wr_preallocate() is introduced as a wrapper function to set the store
>> type and preallcoate enough nodes.
>>
>> Signed-off-by: Sidhartha Kumar <sidhartha.kumar@oracle.com>
>> ---

....................

>> diff --git a/tools/testing/radix-tree/maple.c b/tools/testing/radix-tree/maple.c
>> index f1caf4bcf937..c57979de1576 100644
>> --- a/tools/testing/radix-tree/maple.c
>> +++ b/tools/testing/radix-tree/maple.c
>> @@ -36223,6 +36223,37 @@ static noinline void __init check_mtree_dup(struct maple_tree *mt)
>>   
>>   extern void test_kmem_cache_bulk(void);
>>   
>> +
>> + /* test to simulate expanding a vma from [0x7fffffffe000, 0x7ffffffff000)
>> +  * to [0x7ffde4ca1000, 0x7ffffffff000) and then shrinking the vma to
>> +  * [0x7ffde4ca1000, 0x7ffde4ca2000)
>> +  */
>> +static inline int check_vma_modification(struct maple_tree *mt)
>> +{
>> +	MA_STATE(mas, mt, 0, 0);
> 
> 
> Don't we need locking in here?

Ya, I think I'm also missing a mas_destroy() at the end of this function. I'll 
add mt_lock()/mt_unlock() as well as mas_destroy().

Thanks,
Sid
> 
>> +
>> +	/* vma with old start and old end */
>> +	__mas_set_range(&mas, 0x7fffffffe000, 0x7ffffffff000 - 1);
>> +	mas_preallocate(&mas, xa_mk_value(1), GFP_KERNEL);
>> +	mas_store_prealloc(&mas, xa_mk_value(1));
>> +
>> +	/* next write occurs partly in previous range [0, 0x7fffffffe000)*/
>> +	mas_prev_range(&mas, 0);
>> +	/* expand vma to {0x7ffde4ca1000, 0x7ffffffff000) */
>> +	__mas_set_range(&mas, 0x7ffde4ca1000, 0x7ffffffff000 - 1);
>> +	mas_preallocate(&mas, xa_mk_value(1), GFP_KERNEL);
>> +	mas_store_prealloc(&mas, xa_mk_value(1));
>> +
>> +	/* shrink vma to [0x7ffde4ca1000, 7ffde4ca2000) */
>> +	__mas_set_range(&mas, 0x7ffde4ca2000, 0x7ffffffff000 - 1);
>> +	mas_preallocate(&mas, NULL, GFP_KERNEL);
>> +	mas_store_prealloc(&mas, NULL);
>> +	mt_dump(mt, mt_dump_hex);
>> +
>> +	return 0;
>> +}
>> +
>> +
>>   void farmer_tests(void)
>>   {
>>   	struct maple_node *node;
>> @@ -36230,6 +36261,10 @@ void farmer_tests(void)
>>   
>>   	mt_dump(&tree, mt_dump_dec);
>>   
>> +	mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE | MT_FLAGS_LOCK_EXTERN | MT_FLAGS_USE_RCU);
>> +	check_vma_modification(&tree);
>> +	mtree_destroy(&tree);
>> +
>>   	tree.ma_root = xa_mk_value(0);
>>   	mt_dump(&tree, mt_dump_dec);
>>   
>> -- 
>> 2.45.1
>>

Re: [PATCH 13/18] maple_tree: simplify mas_commit_b_node()

[Mateusz Guzik]

On Tue, Jun 04, 2024 at 10:41:40AM -0700, Sidhartha Kumar wrote:
> Use mas->store_type to simplify the logic of identifying the type of
> write.
> 
> Signed-off-by: Sidhartha Kumar <sidhartha.kumar@oracle.com>
> ---
>  lib/maple_tree.c | 6 ++----
>  1 file changed, 2 insertions(+), 4 deletions(-)
> 
> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> index 314691fd1c67..faadddbe2086 100644
> --- a/lib/maple_tree.c
> +++ b/lib/maple_tree.c
> @@ -3437,12 +3437,10 @@ static noinline_for_kasan int mas_commit_b_node(struct ma_wr_state *wr_mas,
>  	enum maple_type b_type = b_node->type;
>  
>  	old_enode = wr_mas->mas->node;
> -	if ((b_end < mt_min_slots[b_type]) &&
> -	    (!mte_is_root(old_enode)) &&
> -	    (mas_mt_height(wr_mas->mas) > 1))
> +	if (wr_mas->mas->store_type == wr_rebalance)
>  		return mas_rebalance(wr_mas->mas, b_node);
>  
> -	if (b_end >= mt_slots[b_type])
> +	if (wr_mas->mas->store_type == wr_split_store)
>  		return mas_split(wr_mas->mas, b_node);
>  
>  	if (mas_reuse_node(wr_mas, b_node, end))


This reliably results in "kernel BUG at mm/mmap.c:3412!".

bt below

reliably reproduces as follows: spawn "perf top", hit enter twice to
disassemble a func. tui hangs indefinitely, console shows the splat
below.

I verified going one commit down produces a working kernel.

kernel BUG at mm/mmap.c:3412!
[   35.820042] Oops: invalid opcode: 0000 [#1] PREEMPT SMP NOPTI
[   35.821101] CPU: 4 PID: 1066 Comm: perf-top-UI Tainted: G        W          6.10.0-rc5-00304-g30e5748b1d44 #155
[   35.822929] Hardware name: QEMU Standard PC (Q35 + ICH9, 2009), BIOS rel-1.16.1-0-g3208b098f51a-prebuilt.qemu.org 04/01/2014
[   35.824957] RIP: 0010:exit_mmap+0x392/0x3a0
[   35.825794] Code: ef e8 02 9f fe ff eb d7 be 01 00 00 00 48 89 ef e8 73 a3 fe ff eb be 31 f6 48 89 ef
e8 a7 a2 fe ff eb a8 0f 0b e9 75 fe ff ff <0f> 0b e8 a7 b2 c1 00 0f 1f 80 00 00 00 00 90 90 90 90 90 90 90 90
[   35.829141] RSP: 0018:ff7fe6c8c2393c40 EFLAGS: 00010293
[   35.830103] RAX: 0000000000000000 RBX: 0000000000000000 RCX: 0000000000000000
[   35.831398] RDX: ff39fe34499c3c00 RSI: 0000000000000001 RDI: ff39fe34499c3c08
[   35.832705] RBP: ff39fe3441a28580 R08: 000000000000000c R09: 0000000000000060
[   35.834010] R10: ff39fe3450ad5600 R11: 0000000000000000 R12: 00000000000000e8
[   35.835295] R13: 0000000000003593 R14: ff39fe3441a28628 R15: ff39fe3441a285c0
[   35.836569] FS:  0000000000000000(0000) GS:ff39fe39a7700000(0000) knlGS:0000000000000000
[   35.838042] CS:  0010 DS: 0000 ES: 0000 CR0: 0000000080050033
[   35.839093] CR2: 00007efd624f39ed CR3: 000000010130e001 CR4: 0000000000371ef0
[   35.840389] DR0: 0000000000000000 DR1: 0000000000000000 DR2: 0000000000000000
[   35.841892] DR3: 0000000000000000 DR6: 00000000fffe07f0 DR7: 0000000000000400
[   35.843182] Call Trace:
[   35.843646]  <TASK>
[   35.844051]  ? die+0x36/0x90
[   35.844602]  ? do_trap+0xdd/0x100
[   35.845226]  ? exit_mmap+0x392/0x3a0
[   35.845915]  ? do_error_trap+0x65/0x80
[   35.846614]  ? exit_mmap+0x392/0x3a0
[   35.847287]  ? exc_invalid_op+0x50/0x70
[   35.847999]  ? exit_mmap+0x392/0x3a0
[   35.848662]  ? asm_exc_invalid_op+0x1a/0x20
[   35.849437]  ? exit_mmap+0x392/0x3a0
[   35.850120]  __mmput+0x3d/0x130
[   35.850713]  begin_new_exec+0x4ed/0xb00
[   35.851428]  ? load_elf_phdrs+0x6c/0xc0
[   35.852150]  load_elf_binary+0x2ca/0x15a0
[   35.852890]  ? __kernel_read+0x1d8/0x2f0
[   35.853621]  ? __kernel_read+0x1d8/0x2f0
[   35.854348]  ? load_misc_binary+0x1f6/0x310
[   35.855113]  bprm_execve+0x243/0x600
[   35.855784]  do_execveat_common.isra.0+0x1bd/0x220
[   35.856672]  __x64_sys_execve+0x36/0x40
[   35.857384]  do_syscall_64+0x52/0x150
[   35.858088]  entry_SYSCALL_64_after_hwframe+0x76/0x7e
[   35.859014] RIP: 0033:0x7efd624f3a17
[   35.859677] Code: Unable to access opcode bytes at 0x7efd624f39ed.
[   35.860790] RSP: 002b:00007efd48bf8dc8 EFLAGS: 00000202 ORIG_RAX: 000000000000003b
[   35.862170] RAX: ffffffffffffffda RBX: 000055e5736a44e3 RCX: 00007efd624f3a17
[   35.863472] RDX: 000055e59c315000 RSI: 00007efd48bf9050 RDI: 000055e5736a44e3
[   35.864768] RBP: 00007efd48bf8e40 R08: 0000000000000000 R09: 00007efd48c006c0
[   35.866475] R10: 00007efd62430e50 R11: 0000000000000202 R12: 00007efd48bf9050
[   35.868167] R13: 000055e59c315000 R14: 0000000000000001 R15: 0000000000000001
[   35.869873]  </TASK>
[   35.870676] Modules linked in:
[   35.871944] ---[ end trace 0000000000000000 ]---

Re: [PATCH 13/18] maple_tree: simplify mas_commit_b_node()

[Andrew Morton]

On Wed, 26 Jun 2024 12:40:19 +0200 Mateusz Guzik <mjguzik@gmail.com> wrote:

> This reliably results in "kernel BUG at mm/mmap.c:3412!".

Thanks, I'll drop v3 of the series "Introduce a store type enum for the
Maple tree"

Re: [PATCH 13/18] maple_tree: simplify mas_commit_b_node()

[Sidhartha Kumar]

On 6/26/24 3:40 AM, Mateusz Guzik wrote:
> On Tue, Jun 04, 2024 at 10:41:40AM -0700, Sidhartha Kumar wrote:
>> Use mas->store_type to simplify the logic of identifying the type of
>> write.
>>
>> Signed-off-by: Sidhartha Kumar <sidhartha.kumar@oracle.com>
>> ---
>>   lib/maple_tree.c | 6 ++----
>>   1 file changed, 2 insertions(+), 4 deletions(-)
>>
>> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
>> index 314691fd1c67..faadddbe2086 100644
>> --- a/lib/maple_tree.c
>> +++ b/lib/maple_tree.c
>> @@ -3437,12 +3437,10 @@ static noinline_for_kasan int mas_commit_b_node(struct ma_wr_state *wr_mas,
>>   	enum maple_type b_type = b_node->type;
>>   
>>   	old_enode = wr_mas->mas->node;
>> -	if ((b_end < mt_min_slots[b_type]) &&
>> -	    (!mte_is_root(old_enode)) &&
>> -	    (mas_mt_height(wr_mas->mas) > 1))
>> +	if (wr_mas->mas->store_type == wr_rebalance)
>>   		return mas_rebalance(wr_mas->mas, b_node);
>>   
>> -	if (b_end >= mt_slots[b_type])
>> +	if (wr_mas->mas->store_type == wr_split_store)
>>   		return mas_split(wr_mas->mas, b_node);
>>   
>>   	if (mas_reuse_node(wr_mas, b_node, end))
> 
> 
> This reliably results in "kernel BUG at mm/mmap.c:3412!".
> 
> bt below
> 
> reliably reproduces as follows: spawn "perf top", hit enter twice to
> disassemble a func. tui hangs indefinitely, console shows the splat
> below.
> 

Hello,

Thanks for your report. When I run perf top and disassemble a function tui 
doesn't hang. In dmesg I see:

[   17.836399] perf: interrupt took too long (2705 > 2500), lowering 
kernel.perf_event_max_sample_rate to 73000
[   17.837532] perf: interrupt took too long (3561 > 3381), lowering 
kernel.perf_event_max_sample_rate to 56000
[   17.838818] perf: interrupt took too long (4654 > 4451), lowering 
kernel.perf_event_max_sample_rate to 42000
[   17.840267] perf: interrupt took too long (5930 > 5817), lowering 
kernel.perf_event_max_sample_rate to 33000


but not the bug that your seeing. Could you send your config file so I could 
test with that?

Thanks,
Sid



> I verified going one commit down produces a working kernel.
> 
> kernel BUG at mm/mmap.c:3412!
> [   35.820042] Oops: invalid opcode: 0000 [#1] PREEMPT SMP NOPTI
> [   35.821101] CPU: 4 PID: 1066 Comm: perf-top-UI Tainted: G        W          6.10.0-rc5-00304-g30e5748b1d44 #155
> [   35.822929] Hardware name: QEMU Standard PC (Q35 + ICH9, 2009), BIOS rel-1.16.1-0-g3208b098f51a-prebuilt.qemu.org 04/01/2014
> [   35.824957] RIP: 0010:exit_mmap+0x392/0x3a0
> [   35.825794] Code: ef e8 02 9f fe ff eb d7 be 01 00 00 00 48 89 ef e8 73 a3 fe ff eb be 31 f6 48 89 ef
> e8 a7 a2 fe ff eb a8 0f 0b e9 75 fe ff ff <0f> 0b e8 a7 b2 c1 00 0f 1f 80 00 00 00 00 90 90 90 90 90 90 90 90
> [   35.829141] RSP: 0018:ff7fe6c8c2393c40 EFLAGS: 00010293
> [   35.830103] RAX: 0000000000000000 RBX: 0000000000000000 RCX: 0000000000000000
> [   35.831398] RDX: ff39fe34499c3c00 RSI: 0000000000000001 RDI: ff39fe34499c3c08
> [   35.832705] RBP: ff39fe3441a28580 R08: 000000000000000c R09: 0000000000000060
> [   35.834010] R10: ff39fe3450ad5600 R11: 0000000000000000 R12: 00000000000000e8
> [   35.835295] R13: 0000000000003593 R14: ff39fe3441a28628 R15: ff39fe3441a285c0
> [   35.836569] FS:  0000000000000000(0000) GS:ff39fe39a7700000(0000) knlGS:0000000000000000
> [   35.838042] CS:  0010 DS: 0000 ES: 0000 CR0: 0000000080050033
> [   35.839093] CR2: 00007efd624f39ed CR3: 000000010130e001 CR4: 0000000000371ef0
> [   35.840389] DR0: 0000000000000000 DR1: 0000000000000000 DR2: 0000000000000000
> [   35.841892] DR3: 0000000000000000 DR6: 00000000fffe07f0 DR7: 0000000000000400
> [   35.843182] Call Trace:
> [   35.843646]  <TASK>
> [   35.844051]  ? die+0x36/0x90
> [   35.844602]  ? do_trap+0xdd/0x100
> [   35.845226]  ? exit_mmap+0x392/0x3a0
> [   35.845915]  ? do_error_trap+0x65/0x80
> [   35.846614]  ? exit_mmap+0x392/0x3a0
> [   35.847287]  ? exc_invalid_op+0x50/0x70
> [   35.847999]  ? exit_mmap+0x392/0x3a0
> [   35.848662]  ? asm_exc_invalid_op+0x1a/0x20
> [   35.849437]  ? exit_mmap+0x392/0x3a0
> [   35.850120]  __mmput+0x3d/0x130
> [   35.850713]  begin_new_exec+0x4ed/0xb00
> [   35.851428]  ? load_elf_phdrs+0x6c/0xc0
> [   35.852150]  load_elf_binary+0x2ca/0x15a0
> [   35.852890]  ? __kernel_read+0x1d8/0x2f0
> [   35.853621]  ? __kernel_read+0x1d8/0x2f0
> [   35.854348]  ? load_misc_binary+0x1f6/0x310
> [   35.855113]  bprm_execve+0x243/0x600
> [   35.855784]  do_execveat_common.isra.0+0x1bd/0x220
> [   35.856672]  __x64_sys_execve+0x36/0x40
> [   35.857384]  do_syscall_64+0x52/0x150
> [   35.858088]  entry_SYSCALL_64_after_hwframe+0x76/0x7e
> [   35.859014] RIP: 0033:0x7efd624f3a17
> [   35.859677] Code: Unable to access opcode bytes at 0x7efd624f39ed.
> [   35.860790] RSP: 002b:00007efd48bf8dc8 EFLAGS: 00000202 ORIG_RAX: 000000000000003b
> [   35.862170] RAX: ffffffffffffffda RBX: 000055e5736a44e3 RCX: 00007efd624f3a17
> [   35.863472] RDX: 000055e59c315000 RSI: 00007efd48bf9050 RDI: 000055e5736a44e3
> [   35.864768] RBP: 00007efd48bf8e40 R08: 0000000000000000 R09: 00007efd48c006c0
> [   35.866475] R10: 00007efd62430e50 R11: 0000000000000202 R12: 00007efd48bf9050
> [   35.868167] R13: 000055e59c315000 R14: 0000000000000001 R15: 0000000000000001
> [   35.869873]  </TASK>
> [   35.870676] Modules linked in:
> [   35.871944] ---[ end trace 0000000000000000 ]---
> 

Re: [PATCH 13/18] maple_tree: simplify mas_commit_b_node()

[Mateusz Guzik]

On Wed, Jun 26, 2024 at 7:45 PM Sidhartha Kumar
<sidhartha.kumar@oracle.com> wrote:
>
> On 6/26/24 3:40 AM, Mateusz Guzik wrote:
> > On Tue, Jun 04, 2024 at 10:41:40AM -0700, Sidhartha Kumar wrote:
> >> Use mas->store_type to simplify the logic of identifying the type of
> >> write.
> >>
> >> Signed-off-by: Sidhartha Kumar <sidhartha.kumar@oracle.com>
> >> ---
> >>   lib/maple_tree.c | 6 ++----
> >>   1 file changed, 2 insertions(+), 4 deletions(-)
> >>
> >> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> >> index 314691fd1c67..faadddbe2086 100644
> >> --- a/lib/maple_tree.c
> >> +++ b/lib/maple_tree.c
> >> @@ -3437,12 +3437,10 @@ static noinline_for_kasan int mas_commit_b_node(struct ma_wr_state *wr_mas,
> >>      enum maple_type b_type = b_node->type;
> >>
> >>      old_enode = wr_mas->mas->node;
> >> -    if ((b_end < mt_min_slots[b_type]) &&
> >> -        (!mte_is_root(old_enode)) &&
> >> -        (mas_mt_height(wr_mas->mas) > 1))
> >> +    if (wr_mas->mas->store_type == wr_rebalance)
> >>              return mas_rebalance(wr_mas->mas, b_node);
> >>
> >> -    if (b_end >= mt_slots[b_type])
> >> +    if (wr_mas->mas->store_type == wr_split_store)
> >>              return mas_split(wr_mas->mas, b_node);
> >>
> >>      if (mas_reuse_node(wr_mas, b_node, end))
> >
> >
> > This reliably results in "kernel BUG at mm/mmap.c:3412!".
> >
> > bt below
> >
> > reliably reproduces as follows: spawn "perf top", hit enter twice to
> > disassemble a func. tui hangs indefinitely, console shows the splat
> > below.
> >
>
> Hello,
>
> Thanks for your report. When I run perf top and disassemble a function tui
> doesn't hang. In dmesg I see:
>
> [   17.836399] perf: interrupt took too long (2705 > 2500), lowering
> kernel.perf_event_max_sample_rate to 73000
> [   17.837532] perf: interrupt took too long (3561 > 3381), lowering
> kernel.perf_event_max_sample_rate to 56000
> [   17.838818] perf: interrupt took too long (4654 > 4451), lowering
> kernel.perf_event_max_sample_rate to 42000
> [   17.840267] perf: interrupt took too long (5930 > 5817), lowering
> kernel.perf_event_max_sample_rate to 33000
>
>
> but not the bug that your seeing. Could you send your config file so I could
> test with that?
>

https://people.freebsd.org/~mjg/.linux-crap/.config-maple-crash

I verified again this reliably crashes when going to:
commit 30e5748b1d44e3eefc41773e27c63e51910ed718 (HEAD)
Author: Sidhartha Kumar <sidhartha.kumar@oracle.com>
Date:   Tue Jun 18 13:47:45 2024 -0700

    maple_tree: simplify mas_commit_b_node()

on linux-next

Userspace is Debian 12 (which may be of significance), but just in
case I'll note I'm building the kernel on a Ubuntu 24.04.

> Thanks,
> Sid
>
>
>
> > I verified going one commit down produces a working kernel.
> >
> > kernel BUG at mm/mmap.c:3412!
> > [   35.820042] Oops: invalid opcode: 0000 [#1] PREEMPT SMP NOPTI
> > [   35.821101] CPU: 4 PID: 1066 Comm: perf-top-UI Tainted: G        W          6.10.0-rc5-00304-g30e5748b1d44 #155
> > [   35.822929] Hardware name: QEMU Standard PC (Q35 + ICH9, 2009), BIOS rel-1.16.1-0-g3208b098f51a-prebuilt.qemu.org 04/01/2014
> > [   35.824957] RIP: 0010:exit_mmap+0x392/0x3a0
> > [   35.825794] Code: ef e8 02 9f fe ff eb d7 be 01 00 00 00 48 89 ef e8 73 a3 fe ff eb be 31 f6 48 89 ef
> > e8 a7 a2 fe ff eb a8 0f 0b e9 75 fe ff ff <0f> 0b e8 a7 b2 c1 00 0f 1f 80 00 00 00 00 90 90 90 90 90 90 90 90
> > [   35.829141] RSP: 0018:ff7fe6c8c2393c40 EFLAGS: 00010293
> > [   35.830103] RAX: 0000000000000000 RBX: 0000000000000000 RCX: 0000000000000000
> > [   35.831398] RDX: ff39fe34499c3c00 RSI: 0000000000000001 RDI: ff39fe34499c3c08
> > [   35.832705] RBP: ff39fe3441a28580 R08: 000000000000000c R09: 0000000000000060
> > [   35.834010] R10: ff39fe3450ad5600 R11: 0000000000000000 R12: 00000000000000e8
> > [   35.835295] R13: 0000000000003593 R14: ff39fe3441a28628 R15: ff39fe3441a285c0
> > [   35.836569] FS:  0000000000000000(0000) GS:ff39fe39a7700000(0000) knlGS:0000000000000000
> > [   35.838042] CS:  0010 DS: 0000 ES: 0000 CR0: 0000000080050033
> > [   35.839093] CR2: 00007efd624f39ed CR3: 000000010130e001 CR4: 0000000000371ef0
> > [   35.840389] DR0: 0000000000000000 DR1: 0000000000000000 DR2: 0000000000000000
> > [   35.841892] DR3: 0000000000000000 DR6: 00000000fffe07f0 DR7: 0000000000000400
> > [   35.843182] Call Trace:
> > [   35.843646]  <TASK>
> > [   35.844051]  ? die+0x36/0x90
> > [   35.844602]  ? do_trap+0xdd/0x100
> > [   35.845226]  ? exit_mmap+0x392/0x3a0
> > [   35.845915]  ? do_error_trap+0x65/0x80
> > [   35.846614]  ? exit_mmap+0x392/0x3a0
> > [   35.847287]  ? exc_invalid_op+0x50/0x70
> > [   35.847999]  ? exit_mmap+0x392/0x3a0
> > [   35.848662]  ? asm_exc_invalid_op+0x1a/0x20
> > [   35.849437]  ? exit_mmap+0x392/0x3a0
> > [   35.850120]  __mmput+0x3d/0x130
> > [   35.850713]  begin_new_exec+0x4ed/0xb00
> > [   35.851428]  ? load_elf_phdrs+0x6c/0xc0
> > [   35.852150]  load_elf_binary+0x2ca/0x15a0
> > [   35.852890]  ? __kernel_read+0x1d8/0x2f0
> > [   35.853621]  ? __kernel_read+0x1d8/0x2f0
> > [   35.854348]  ? load_misc_binary+0x1f6/0x310
> > [   35.855113]  bprm_execve+0x243/0x600
> > [   35.855784]  do_execveat_common.isra.0+0x1bd/0x220
> > [   35.856672]  __x64_sys_execve+0x36/0x40
> > [   35.857384]  do_syscall_64+0x52/0x150
> > [   35.858088]  entry_SYSCALL_64_after_hwframe+0x76/0x7e
> > [   35.859014] RIP: 0033:0x7efd624f3a17
> > [   35.859677] Code: Unable to access opcode bytes at 0x7efd624f39ed.
> > [   35.860790] RSP: 002b:00007efd48bf8dc8 EFLAGS: 00000202 ORIG_RAX: 000000000000003b
> > [   35.862170] RAX: ffffffffffffffda RBX: 000055e5736a44e3 RCX: 00007efd624f3a17
> > [   35.863472] RDX: 000055e59c315000 RSI: 00007efd48bf9050 RDI: 000055e5736a44e3
> > [   35.864768] RBP: 00007efd48bf8e40 R08: 0000000000000000 R09: 00007efd48c006c0
> > [   35.866475] R10: 00007efd62430e50 R11: 0000000000000202 R12: 00007efd48bf9050
> > [   35.868167] R13: 000055e59c315000 R14: 0000000000000001 R15: 0000000000000001
> > [   35.869873]  </TASK>
> > [   35.870676] Modules linked in:
> > [   35.871944] ---[ end trace 0000000000000000 ]---
> >
>


-- 
Mateusz Guzik <mjguzik gmail.com>