[PATCH 00/10] Clean ups for maple tree

[PATCH 00/10] Clean ups for maple tree

[Peng Zhang]

Some clean ups, mainly to make the code of maple tree more concise.
This patchset has passed the self-test.

0001-0002 - These two patches are collected from [1]
0005-0010 - Make mas_wr_modify() and its subfunctions clearer. Make the store
            operation of maple tree more efficient in some cases

[1] https://lore.kernel.org/lkml/20230510061049.53977-1-zhangpeng.00@bytedance.com/

Peng Zhang (10):
  maple_tree: Drop the test code for mtree_alloc_{range,rrange}()
  maple_tree: Drop mtree_alloc_{range,rrange}() and related functions.
  maple_tree: Remove __must_hold() which does not work
  maple_tree: Simplify mas_is_span_wr()
  maple_tree: Make the code symmetrical in mas_wr_extend_null()
  maple_tree: Wrap the replace operation with an inline function.
  maple_tree: Add mas_wr_new_end() to calculate new_end accurately
  maple_tree: Add comments and some minor cleanups to mas_wr_append()
  maple_tree: Rework mas_wr_slot_store() to be cleaner and more
    efficient.
  maple_tree: Simplify and clean up mas_wr_node_store()

 include/linux/maple_tree.h |   7 -
 lib/maple_tree.c           | 500 ++++++++++++-------------------------
 lib/test_maple_tree.c      | 389 -----------------------------
 3 files changed, 162 insertions(+), 734 deletions(-)

-- 
2.20.1

[PATCH 01/10] maple_tree: Drop the test code for mtree_alloc_{range,rrange}()

[Peng Zhang]

Drop the test code for mtree_alloc_{range,rrange}() because we are going
to drop them.

Signed-off-by: Peng Zhang <zhangpeng.00@bytedance.com>
---
 lib/test_maple_tree.c | 389 ------------------------------------------
 1 file changed, 389 deletions(-)

diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c
index 9939be34e516e..86d7f742d243e 100644
--- a/lib/test_maple_tree.c
+++ b/lib/test_maple_tree.c
@@ -97,42 +97,6 @@ static void __init *mtree_test_erase(struct maple_tree *mt, unsigned long index)
 	return mtree_erase(mt, index);
 }
 
-#if defined(CONFIG_64BIT)
-static noinline void __init check_mtree_alloc_range(struct maple_tree *mt,
-		unsigned long start, unsigned long end, unsigned long size,
-		unsigned long expected, int eret, void *ptr)
-{
-
-	unsigned long result = expected + 1;
-	int ret;
-
-	ret = mtree_alloc_range(mt, &result, ptr, size, start, end,
-			GFP_KERNEL);
-	MT_BUG_ON(mt, ret != eret);
-	if (ret)
-		return;
-
-	MT_BUG_ON(mt, result != expected);
-}
-
-static noinline void __init check_mtree_alloc_rrange(struct maple_tree *mt,
-		unsigned long start, unsigned long end, unsigned long size,
-		unsigned long expected, int eret, void *ptr)
-{
-
-	unsigned long result = expected + 1;
-	int ret;
-
-	ret = mtree_alloc_rrange(mt, &result, ptr, size, start, end,
-			GFP_KERNEL);
-	MT_BUG_ON(mt, ret != eret);
-	if (ret)
-		return;
-
-	MT_BUG_ON(mt, result != expected);
-}
-#endif
-
 static noinline void __init check_load(struct maple_tree *mt,
 				       unsigned long index, void *ptr)
 {
@@ -635,348 +599,6 @@ static noinline void __init check_find_2(struct maple_tree *mt)
 	/*MT_BUG_ON(mt, !mtree_empty(mt)); */
 }
 
-
-#if defined(CONFIG_64BIT)
-static noinline void __init check_alloc_rev_range(struct maple_tree *mt)
-{
-	/*
-	 * Generated by:
-	 * cat /proc/self/maps | awk '{print $1}'|
-	 * awk -F "-" '{printf "0x%s, 0x%s, ", $1, $2}'
-	 */
-
-	static const unsigned long range[] = {
-	/*      Inclusive     , Exclusive. */
-		0x565234af2000, 0x565234af4000,
-		0x565234af4000, 0x565234af9000,
-		0x565234af9000, 0x565234afb000,
-		0x565234afc000, 0x565234afd000,
-		0x565234afd000, 0x565234afe000,
-		0x565235def000, 0x565235e10000,
-		0x7f36d4bfd000, 0x7f36d4ee2000,
-		0x7f36d4ee2000, 0x7f36d4f04000,
-		0x7f36d4f04000, 0x7f36d504c000,
-		0x7f36d504c000, 0x7f36d5098000,
-		0x7f36d5098000, 0x7f36d5099000,
-		0x7f36d5099000, 0x7f36d509d000,
-		0x7f36d509d000, 0x7f36d509f000,
-		0x7f36d509f000, 0x7f36d50a5000,
-		0x7f36d50b9000, 0x7f36d50db000,
-		0x7f36d50db000, 0x7f36d50dc000,
-		0x7f36d50dc000, 0x7f36d50fa000,
-		0x7f36d50fa000, 0x7f36d5102000,
-		0x7f36d5102000, 0x7f36d5103000,
-		0x7f36d5103000, 0x7f36d5104000,
-		0x7f36d5104000, 0x7f36d5105000,
-		0x7fff5876b000, 0x7fff5878d000,
-		0x7fff5878e000, 0x7fff58791000,
-		0x7fff58791000, 0x7fff58793000,
-	};
-
-	static const unsigned long holes[] = {
-		/*
-		 * Note: start of hole is INCLUSIVE
-		 *        end of hole is EXCLUSIVE
-		 *        (opposite of the above table.)
-		 * Start of hole, end of hole,  size of hole (+1)
-		 */
-		0x565234afb000, 0x565234afc000, 0x1000,
-		0x565234afe000, 0x565235def000, 0x12F1000,
-		0x565235e10000, 0x7f36d4bfd000, 0x28E49EDED000,
-	};
-
-	/*
-	 * req_range consists of 4 values.
-	 * 1. min index
-	 * 2. max index
-	 * 3. size
-	 * 4. number that should be returned.
-	 * 5. return value
-	 */
-	static const unsigned long req_range[] = {
-		0x565234af9000, /* Min */
-		0x7fff58791000, /* Max */
-		0x1000,         /* Size */
-		0x7fff5878d << 12,  /* First rev hole of size 0x1000 */
-		0,              /* Return value success. */
-
-		0x0,            /* Min */
-		0x565234AF0 << 12,    /* Max */
-		0x3000,         /* Size */
-		0x565234AEE << 12,  /* max - 3. */
-		0,              /* Return value success. */
-
-		0x0,            /* Min */
-		-1,             /* Max */
-		0x1000,         /* Size */
-		562949953421311 << 12,/* First rev hole of size 0x1000 */
-		0,              /* Return value success. */
-
-		0x0,            /* Min */
-		0x7F36D5109 << 12,    /* Max */
-		0x4000,         /* Size */
-		0x7F36D5106 << 12,    /* First rev hole of size 0x4000 */
-		0,              /* Return value success. */
-
-		/* Ascend test. */
-		0x0,
-		34148798628 << 12,
-		19 << 12,
-		34148797418 << 12,
-		0x0,
-
-		/* Too big test. */
-		0x0,
-		18446744073709551615UL,
-		562915594369134UL << 12,
-		0x0,
-		-EBUSY,
-
-		/* Single space test. */
-		34148798725 << 12,
-		34148798725 << 12,
-		1 << 12,
-		34148798725 << 12,
-		0,
-	};
-
-	int i, range_count = ARRAY_SIZE(range);
-	int req_range_count = ARRAY_SIZE(req_range);
-	unsigned long min = 0;
-
-	MA_STATE(mas, mt, 0, 0);
-
-	mtree_store_range(mt, MTREE_ALLOC_MAX, ULONG_MAX, XA_ZERO_ENTRY,
-			  GFP_KERNEL);
-#define DEBUG_REV_RANGE 0
-	for (i = 0; i < range_count; i += 2) {
-		/* Inclusive, Inclusive (with the -1) */
-
-#if DEBUG_REV_RANGE
-		pr_debug("\t%s: Insert %lu-%lu\n", __func__, range[i] >> 12,
-				(range[i + 1] >> 12) - 1);
-#endif
-		check_insert_range(mt, range[i] >> 12, (range[i + 1] >> 12) - 1,
-				xa_mk_value(range[i] >> 12), 0);
-		mt_validate(mt);
-	}
-
-
-	mas_lock(&mas);
-	for (i = 0; i < ARRAY_SIZE(holes); i += 3) {
-#if DEBUG_REV_RANGE
-		pr_debug("Search from %lu-%lu for gap %lu should be at %lu\n",
-				min, holes[i+1]>>12, holes[i+2]>>12,
-				holes[i] >> 12);
-#endif
-		MT_BUG_ON(mt, mas_empty_area_rev(&mas, min,
-					holes[i+1] >> 12,
-					holes[i+2] >> 12));
-#if DEBUG_REV_RANGE
-		pr_debug("Found %lu %lu\n", mas.index, mas.last);
-		pr_debug("gap %lu %lu\n", (holes[i] >> 12),
-				(holes[i+1] >> 12));
-#endif
-		MT_BUG_ON(mt, mas.last + 1 != (holes[i+1] >> 12));
-		MT_BUG_ON(mt, mas.index != (holes[i+1] >> 12) - (holes[i+2] >> 12));
-		min = holes[i+1] >> 12;
-		mas_reset(&mas);
-	}
-
-	mas_unlock(&mas);
-	for (i = 0; i < req_range_count; i += 5) {
-#if DEBUG_REV_RANGE
-		pr_debug("\tReverse request %d between %lu-%lu size %lu, should get %lu\n",
-				i, req_range[i] >> 12,
-				(req_range[i + 1] >> 12),
-				req_range[i+2] >> 12,
-				req_range[i+3] >> 12);
-#endif
-		check_mtree_alloc_rrange(mt,
-				req_range[i]   >> 12, /* start */
-				req_range[i+1] >> 12, /* end */
-				req_range[i+2] >> 12, /* size */
-				req_range[i+3] >> 12, /* expected address */
-				req_range[i+4],       /* expected return */
-				xa_mk_value(req_range[i] >> 12)); /* pointer */
-		mt_validate(mt);
-	}
-
-	mt_set_non_kernel(1);
-	mtree_erase(mt, 34148798727); /* create a deleted range. */
-	mtree_erase(mt, 34148798725);
-	check_mtree_alloc_rrange(mt, 0, 34359052173, 210253414,
-			34148798725, 0, mt);
-
-	mtree_destroy(mt);
-}
-
-static noinline void __init check_alloc_range(struct maple_tree *mt)
-{
-	/*
-	 * Generated by:
-	 * cat /proc/self/maps|awk '{print $1}'|
-	 * awk -F "-" '{printf "0x%s, 0x%s, ", $1, $2}'
-	 */
-
-	static const unsigned long range[] = {
-	/*      Inclusive     , Exclusive. */
-		0x565234af2000, 0x565234af4000,
-		0x565234af4000, 0x565234af9000,
-		0x565234af9000, 0x565234afb000,
-		0x565234afc000, 0x565234afd000,
-		0x565234afd000, 0x565234afe000,
-		0x565235def000, 0x565235e10000,
-		0x7f36d4bfd000, 0x7f36d4ee2000,
-		0x7f36d4ee2000, 0x7f36d4f04000,
-		0x7f36d4f04000, 0x7f36d504c000,
-		0x7f36d504c000, 0x7f36d5098000,
-		0x7f36d5098000, 0x7f36d5099000,
-		0x7f36d5099000, 0x7f36d509d000,
-		0x7f36d509d000, 0x7f36d509f000,
-		0x7f36d509f000, 0x7f36d50a5000,
-		0x7f36d50b9000, 0x7f36d50db000,
-		0x7f36d50db000, 0x7f36d50dc000,
-		0x7f36d50dc000, 0x7f36d50fa000,
-		0x7f36d50fa000, 0x7f36d5102000,
-		0x7f36d5102000, 0x7f36d5103000,
-		0x7f36d5103000, 0x7f36d5104000,
-		0x7f36d5104000, 0x7f36d5105000,
-		0x7fff5876b000, 0x7fff5878d000,
-		0x7fff5878e000, 0x7fff58791000,
-		0x7fff58791000, 0x7fff58793000,
-	};
-	static const unsigned long holes[] = {
-		/* Start of hole, end of hole,  size of hole (+1) */
-		0x565234afb000, 0x565234afc000, 0x1000,
-		0x565234afe000, 0x565235def000, 0x12F1000,
-		0x565235e10000, 0x7f36d4bfd000, 0x28E49EDED000,
-	};
-
-	/*
-	 * req_range consists of 4 values.
-	 * 1. min index
-	 * 2. max index
-	 * 3. size
-	 * 4. number that should be returned.
-	 * 5. return value
-	 */
-	static const unsigned long req_range[] = {
-		0x565234af9000, /* Min */
-		0x7fff58791000, /* Max */
-		0x1000,         /* Size */
-		0x565234afb000, /* First hole in our data of size 1000. */
-		0,              /* Return value success. */
-
-		0x0,            /* Min */
-		0x7fff58791000, /* Max */
-		0x1F00,         /* Size */
-		0x0,            /* First hole in our data of size 2000. */
-		0,              /* Return value success. */
-
-		/* Test ascend. */
-		34148797436 << 12, /* Min */
-		0x7fff587AF000,    /* Max */
-		0x3000,         /* Size */
-		34148798629 << 12,             /* Expected location */
-		0,              /* Return value success. */
-
-		/* Test failing. */
-		34148798623 << 12,  /* Min */
-		34148798683 << 12,  /* Max */
-		0x15000,            /* Size */
-		0,             /* Expected location */
-		-EBUSY,              /* Return value failed. */
-
-		/* Test filling entire gap. */
-		34148798623 << 12,  /* Min */
-		0x7fff587AF000,    /* Max */
-		0x10000,           /* Size */
-		34148798632 << 12,             /* Expected location */
-		0,              /* Return value success. */
-
-		/* Test walking off the end of root. */
-		0,                  /* Min */
-		-1,                 /* Max */
-		-1,                 /* Size */
-		0,                  /* Expected location */
-		-EBUSY,             /* Return value failure. */
-
-		/* Test looking for too large a hole across entire range. */
-		0,                  /* Min */
-		-1,                 /* Max */
-		4503599618982063UL << 12,  /* Size */
-		34359052178 << 12,  /* Expected location */
-		-EBUSY,             /* Return failure. */
-
-		/* Test a single entry */
-		34148798648 << 12,		/* Min */
-		34148798648 << 12,		/* Max */
-		4096,			/* Size of 1 */
-		34148798648 << 12,	/* Location is the same as min/max */
-		0,			/* Success */
-	};
-	int i, range_count = ARRAY_SIZE(range);
-	int req_range_count = ARRAY_SIZE(req_range);
-	unsigned long min = 0x565234af2000;
-	MA_STATE(mas, mt, 0, 0);
-
-	mtree_store_range(mt, MTREE_ALLOC_MAX, ULONG_MAX, XA_ZERO_ENTRY,
-			  GFP_KERNEL);
-	for (i = 0; i < range_count; i += 2) {
-#define DEBUG_ALLOC_RANGE 0
-#if DEBUG_ALLOC_RANGE
-		pr_debug("\tInsert %lu-%lu\n", range[i] >> 12,
-			 (range[i + 1] >> 12) - 1);
-		mt_dump(mt, mt_dump_hex);
-#endif
-		check_insert_range(mt, range[i] >> 12, (range[i + 1] >> 12) - 1,
-				xa_mk_value(range[i] >> 12), 0);
-		mt_validate(mt);
-	}
-
-
-
-	mas_lock(&mas);
-	for (i = 0; i < ARRAY_SIZE(holes); i += 3) {
-
-#if DEBUG_ALLOC_RANGE
-		pr_debug("\tGet empty %lu-%lu size %lu (%lx-%lx)\n", min >> 12,
-			holes[i+1] >> 12, holes[i+2] >> 12,
-			min, holes[i+1]);
-#endif
-		MT_BUG_ON(mt, mas_empty_area(&mas, min >> 12,
-					holes[i+1] >> 12,
-					holes[i+2] >> 12));
-		MT_BUG_ON(mt, mas.index != holes[i] >> 12);
-		min = holes[i+1];
-		mas_reset(&mas);
-	}
-	mas_unlock(&mas);
-	for (i = 0; i < req_range_count; i += 5) {
-#if DEBUG_ALLOC_RANGE
-		pr_debug("\tTest %d: %lu-%lu size %lu expected %lu (%lu-%lu)\n",
-			 i/5, req_range[i]   >> 12, req_range[i + 1]   >> 12,
-			 req_range[i + 2]   >> 12, req_range[i + 3]   >> 12,
-			 req_range[i], req_range[i+1]);
-#endif
-		check_mtree_alloc_range(mt,
-				req_range[i]   >> 12, /* start */
-				req_range[i+1] >> 12, /* end */
-				req_range[i+2] >> 12, /* size */
-				req_range[i+3] >> 12, /* expected address */
-				req_range[i+4],       /* expected return */
-				xa_mk_value(req_range[i] >> 12)); /* pointer */
-		mt_validate(mt);
-#if DEBUG_ALLOC_RANGE
-		mt_dump(mt, mt_dump_hex);
-#endif
-	}
-
-	mtree_destroy(mt);
-}
-#endif
-
 static noinline void __init check_ranges(struct maple_tree *mt)
 {
 	int i, val, val2;
@@ -3448,17 +3070,6 @@ static int __init maple_tree_seed(void)
 	check_ranges(&tree);
 	mtree_destroy(&tree);
 
-#if defined(CONFIG_64BIT)
-	/* These tests have ranges outside of 4GB */
-	mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
-	check_alloc_range(&tree);
-	mtree_destroy(&tree);
-
-	mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
-	check_alloc_rev_range(&tree);
-	mtree_destroy(&tree);
-#endif
-
 	mt_init_flags(&tree, 0);
 
 	check_load(&tree, set[0], NULL);       /* See if 5015 -> NULL */
-- 
2.20.1

[PATCH 02/10] maple_tree: Drop mtree_alloc_{range,rrange}() and related functions.

[Peng Zhang]

Drop mtree_alloc_{range,rrange}(), mas_{rev_}alloc() and mas_fill_gap().
mtree_alloc_{range,rrange}() currently have no users and can be easily
implemented with mas_empty_area{_rev}(). mas_{rev_}alloc() and
mas_fill_gap() are just their internal functions, drop them together.

Signed-off-by: Peng Zhang <zhangpeng.00@bytedance.com>
---
 include/linux/maple_tree.h |   7 --
 lib/maple_tree.c           | 177 -------------------------------------
 2 files changed, 184 deletions(-)

diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h
index 542b09118a09f..3dd6edccf83af 100644
--- a/include/linux/maple_tree.h
+++ b/include/linux/maple_tree.h
@@ -306,13 +306,6 @@ int mtree_insert(struct maple_tree *mt, unsigned long index,
 		void *entry, gfp_t gfp);
 int mtree_insert_range(struct maple_tree *mt, unsigned long first,
 		unsigned long last, void *entry, gfp_t gfp);
-int mtree_alloc_range(struct maple_tree *mt, unsigned long *startp,
-		void *entry, unsigned long size, unsigned long min,
-		unsigned long max, gfp_t gfp);
-int mtree_alloc_rrange(struct maple_tree *mt, unsigned long *startp,
-		void *entry, unsigned long size, unsigned long min,
-		unsigned long max, gfp_t gfp);
-
 int mtree_store_range(struct maple_tree *mt, unsigned long first,
 		      unsigned long last, void *entry, gfp_t gfp);
 int mtree_store(struct maple_tree *mt, unsigned long index,
diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index b37065a6f570d..49dfe81dfa1b6 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -5120,46 +5120,6 @@ static inline void mas_awalk(struct ma_state *mas, unsigned long size)
 	}
 }
 
-/*
- * mas_fill_gap() - Fill a located gap with @entry.
- * @mas: The maple state
- * @entry: The value to store
- * @slot: The offset into the node to store the @entry
- * @size: The size of the entry
- * @index: The start location
- */
-static inline void mas_fill_gap(struct ma_state *mas, void *entry,
-		unsigned char slot, unsigned long size, unsigned long *index)
-{
-	MA_WR_STATE(wr_mas, mas, entry);
-	unsigned char pslot = mte_parent_slot(mas->node);
-	struct maple_enode *mn = mas->node;
-	unsigned long *pivots;
-	enum maple_type ptype;
-	/*
-	 * mas->index is the start address for the search
-	 *  which may no longer be needed.
-	 * mas->last is the end address for the search
-	 */
-
-	*index = mas->index;
-	mas->last = mas->index + size - 1;
-
-	/*
-	 * It is possible that using mas->max and mas->min to correctly
-	 * calculate the index and last will cause an issue in the gap
-	 * calculation, so fix the ma_state here
-	 */
-	mas_ascend(mas);
-	ptype = mte_node_type(mas->node);
-	pivots = ma_pivots(mas_mn(mas), ptype);
-	mas->max = mas_safe_pivot(mas, pivots, pslot, ptype);
-	mas->min = mas_safe_min(mas, pivots, pslot);
-	mas->node = mn;
-	mas->offset = slot;
-	mas_wr_store_entry(&wr_mas);
-}
-
 /*
  * mas_sparse_area() - Internal function.  Return upper or lower limit when
  * searching for a gap in an empty tree.
@@ -5307,74 +5267,6 @@ int mas_empty_area_rev(struct ma_state *mas, unsigned long min,
 }
 EXPORT_SYMBOL_GPL(mas_empty_area_rev);
 
-static inline int mas_alloc(struct ma_state *mas, void *entry,
-		unsigned long size, unsigned long *index)
-{
-	unsigned long min;
-
-	mas_start(mas);
-	if (mas_is_none(mas) || mas_is_ptr(mas)) {
-		mas_root_expand(mas, entry);
-		if (mas_is_err(mas))
-			return xa_err(mas->node);
-
-		if (!mas->index)
-			return mas_pivot(mas, 0);
-		return mas_pivot(mas, 1);
-	}
-
-	/* Must be walking a tree. */
-	mas_awalk(mas, size);
-	if (mas_is_err(mas))
-		return xa_err(mas->node);
-
-	if (mas->offset == MAPLE_NODE_SLOTS)
-		goto no_gap;
-
-	/*
-	 * At this point, mas->node points to the right node and we have an
-	 * offset that has a sufficient gap.
-	 */
-	min = mas->min;
-	if (mas->offset)
-		min = mas_pivot(mas, mas->offset - 1) + 1;
-
-	if (mas_is_err(mas))
-		return xa_err(mas->node);
-
-	if (mas->index < min)
-		mas->index = min;
-
-	mas_fill_gap(mas, entry, mas->offset, size, index);
-	return 0;
-
-no_gap:
-	return -EBUSY;
-}
-
-static inline int mas_rev_alloc(struct ma_state *mas, unsigned long min,
-				unsigned long max, void *entry,
-				unsigned long size, unsigned long *index)
-{
-	int ret = 0;
-
-	ret = mas_empty_area_rev(mas, min, max, size);
-	if (ret)
-		return ret;
-
-	if (mas_is_err(mas))
-		return xa_err(mas->node);
-
-	if (mas->offset == MAPLE_NODE_SLOTS)
-		goto no_gap;
-
-	mas_fill_gap(mas, entry, mas->offset, size, index);
-	return 0;
-
-no_gap:
-	return -EBUSY;
-}
-
 /*
  * mte_dead_leaves() - Mark all leaves of a node as dead.
  * @mas: The maple state
@@ -6481,75 +6373,6 @@ int mtree_insert(struct maple_tree *mt, unsigned long index, void *entry,
 }
 EXPORT_SYMBOL(mtree_insert);
 
-int mtree_alloc_range(struct maple_tree *mt, unsigned long *startp,
-		void *entry, unsigned long size, unsigned long min,
-		unsigned long max, gfp_t gfp)
-{
-	int ret = 0;
-
-	MA_STATE(mas, mt, min, min);
-	if (!mt_is_alloc(mt))
-		return -EINVAL;
-
-	if (WARN_ON_ONCE(mt_is_reserved(entry)))
-		return -EINVAL;
-
-	if (min > max)
-		return -EINVAL;
-
-	if (max < size)
-		return -EINVAL;
-
-	if (!size)
-		return -EINVAL;
-
-	mtree_lock(mt);
-retry:
-	mas.offset = 0;
-	mas.index = min;
-	mas.last = max - size + 1;
-	ret = mas_alloc(&mas, entry, size, startp);
-	if (mas_nomem(&mas, gfp))
-		goto retry;
-
-	mtree_unlock(mt);
-	return ret;
-}
-EXPORT_SYMBOL(mtree_alloc_range);
-
-int mtree_alloc_rrange(struct maple_tree *mt, unsigned long *startp,
-		void *entry, unsigned long size, unsigned long min,
-		unsigned long max, gfp_t gfp)
-{
-	int ret = 0;
-
-	MA_STATE(mas, mt, min, max - size + 1);
-	if (!mt_is_alloc(mt))
-		return -EINVAL;
-
-	if (WARN_ON_ONCE(mt_is_reserved(entry)))
-		return -EINVAL;
-
-	if (min > max)
-		return -EINVAL;
-
-	if (max < size - 1)
-		return -EINVAL;
-
-	if (!size)
-		return -EINVAL;
-
-	mtree_lock(mt);
-retry:
-	ret = mas_rev_alloc(&mas, min, max, entry, size, startp);
-	if (mas_nomem(&mas, gfp))
-		goto retry;
-
-	mtree_unlock(mt);
-	return ret;
-}
-EXPORT_SYMBOL(mtree_alloc_rrange);
-
 /**
  * mtree_erase() - Find an index and erase the entire range.
  * @mt: The maple tree
-- 
2.20.1

[PATCH 03/10] maple_tree: Remove __must_hold() which does not work

[Peng Zhang]

The arguments to __must_hold() seem to be wrong so they should not work,
remove them.

Signed-off-by: Peng Zhang <zhangpeng.00@bytedance.com>
---
 lib/maple_tree.c | 3 ---
 1 file changed, 3 deletions(-)

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index 49dfe81dfa1b6..43a25d3042c1b 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -1752,7 +1752,6 @@ static inline void mas_adopt_children(struct ma_state *mas,
  * leave the node (true) and handle the adoption and free elsewhere.
  */
 static inline void mas_replace(struct ma_state *mas, bool advanced)
-	__must_hold(mas->tree->lock)
 {
 	struct maple_node *mn = mas_mn(mas);
 	struct maple_enode *old_enode;
@@ -1792,7 +1791,6 @@ static inline void mas_replace(struct ma_state *mas, bool advanced)
  * @child: the maple state to store the child.
  */
 static inline bool mas_new_child(struct ma_state *mas, struct ma_state *child)
-	__must_hold(mas->tree->lock)
 {
 	enum maple_type mt;
 	unsigned char offset;
@@ -6198,7 +6196,6 @@ EXPORT_SYMBOL_GPL(mas_erase);
  * Return: true on allocation, false otherwise.
  */
 bool mas_nomem(struct ma_state *mas, gfp_t gfp)
-	__must_hold(mas->tree->lock)
 {
 	if (likely(mas->node != MA_ERROR(-ENOMEM))) {
 		mas_destroy(mas);
-- 
2.20.1

[PATCH 04/10] maple_tree: Simplify mas_is_span_wr()

[Peng Zhang]

Make the code for detecting spanning writes more concise.

Signed-off-by: Peng Zhang <zhangpeng.00@bytedance.com>
---
 lib/maple_tree.c | 36 +++++++++---------------------------
 1 file changed, 9 insertions(+), 27 deletions(-)

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index 43a25d3042c1b..fbb6efc40e576 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -3728,41 +3728,23 @@ static bool mas_is_span_wr(struct ma_wr_state *wr_mas)
 {
 	unsigned long max;
 	unsigned long last = wr_mas->mas->last;
-	unsigned long piv = wr_mas->r_max;
 	enum maple_type type = wr_mas->type;
 	void *entry = wr_mas->entry;
 
-	/* Contained in this pivot */
-	if (piv > last)
+	max = unlikely(ma_is_leaf(type)) ? wr_mas->mas->max : wr_mas->r_max;
+	if (last < max) {
+		/* Contained in this pivot or this leaf node */
 		return false;
-
-	max = wr_mas->mas->max;
-	if (unlikely(ma_is_leaf(type))) {
-		/* Fits in the node, but may span slots. */
-		if (last < max)
-			return false;
-
-		/* Writes to the end of the node but not null. */
-		if ((last == max) && entry)
-			return false;
-
+	} else if (last == max) {
 		/*
-		 * Writing ULONG_MAX is not a spanning write regardless of the
-		 * value being written as long as the range fits in the node.
+		 * The last entry of leaf node cannot be NULL unless it is the
+		 * rightmost node (writing ULONG_MAX), otherwise it spans slots.
+		 * If this is not leaf node, detect spanning store wr walk.
 		 */
-		if ((last == ULONG_MAX) && (last == max))
-			return false;
-	} else if (piv == last) {
-		if (entry)
-			return false;
-
-		/* Detect spanning store wr walk */
-		if (last == ULONG_MAX)
+		if (entry || last == ULONG_MAX)
 			return false;
 	}
-
-	trace_ma_write(__func__, wr_mas->mas, piv, entry);
-
+	trace_ma_write(__func__, wr_mas->mas, wr_mas->r_max, entry);
 	return true;
 }
 
-- 
2.20.1

[PATCH 05/10] maple_tree: Make the code symmetrical in mas_wr_extend_null()

[Peng Zhang]

Just make the code symmetrical to improve readability.

Signed-off-by: Peng Zhang <zhangpeng.00@bytedance.com>
---
 lib/maple_tree.c | 26 ++++++++++++++------------
 1 file changed, 14 insertions(+), 12 deletions(-)

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index fbb6efc40e576..4c649d75a4923 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -4256,19 +4256,21 @@ static inline void mas_wr_extend_null(struct ma_wr_state *wr_mas)
 {
 	struct ma_state *mas = wr_mas->mas;
 
-	if (mas->last < wr_mas->end_piv && !wr_mas->slots[wr_mas->offset_end])
+	if (!wr_mas->slots[wr_mas->offset_end]) {
+		/* If this one is null, the next and prev are not */
 		mas->last = wr_mas->end_piv;
-
-	/* Check next slot(s) if we are overwriting the end */
-	if ((mas->last == wr_mas->end_piv) &&
-	    (wr_mas->node_end != wr_mas->offset_end) &&
-	    !wr_mas->slots[wr_mas->offset_end + 1]) {
-		wr_mas->offset_end++;
-		if (wr_mas->offset_end == wr_mas->node_end)
-			mas->last = mas->max;
-		else
-			mas->last = wr_mas->pivots[wr_mas->offset_end];
-		wr_mas->end_piv = mas->last;
+	} else {
+		/* Check next slot(s) if we are overwriting the end */
+		if ((mas->last == wr_mas->end_piv) &&
+		    (wr_mas->node_end != wr_mas->offset_end) &&
+		    !wr_mas->slots[wr_mas->offset_end + 1]) {
+			wr_mas->offset_end++;
+			if (wr_mas->offset_end == wr_mas->node_end)
+				mas->last = mas->max;
+			else
+				mas->last = wr_mas->pivots[wr_mas->offset_end];
+			wr_mas->end_piv = mas->last;
+		}
 	}
 
 	if (!wr_mas->content) {
-- 
2.20.1

[PATCH 06/10] maple_tree: Wrap the replace operation with an inline function.

[Peng Zhang]

To make mas_wr_modify() cleaner, wrap the replace operation with an
inline function.

Signed-off-by: Peng Zhang <zhangpeng.00@bytedance.com>
---
 lib/maple_tree.c | 21 +++++++++++++++------
 1 file changed, 15 insertions(+), 6 deletions(-)

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index 4c649d75a4923..ce695adc670ec 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -4288,6 +4288,19 @@ static inline void mas_wr_extend_null(struct ma_wr_state *wr_mas)
 	}
 }
 
+static inline bool mas_wr_replace(struct ma_wr_state *wr_mas)
+{
+	struct ma_state *mas = wr_mas->mas;
+
+	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 true;
+	}
+	return false;
+}
+
 static inline bool mas_wr_append(struct ma_wr_state *wr_mas)
 {
 	unsigned char end = wr_mas->node_end;
@@ -4347,13 +4360,9 @@ static inline void mas_wr_modify(struct ma_wr_state *wr_mas)
 	unsigned char node_size;
 	struct ma_state *mas = wr_mas->mas;
 
-	/* 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);
+	/* Attempt to direct replace */
+	if (mas_wr_replace(wr_mas))
 		return;
-	}
 
 	/* Attempt to append */
 	node_slots = mt_slots[wr_mas->type];
-- 
2.20.1

[PATCH 07/10] maple_tree: Add mas_wr_new_end() to calculate new_end accurately

[Peng Zhang]

The previous new_end calculation is inaccurate, because it assumes that
two new pivots must be added (this is inaccurate), and sometimes it will
miss the fast path and enter the slow path. Add mas_wr_new_end() to
accurately calculate new_end to make the conditions for entering the
fast path more accurate.

Signed-off-by: Peng Zhang <zhangpeng.00@bytedance.com>
---
 lib/maple_tree.c | 33 ++++++++++++++++++++++-----------
 1 file changed, 22 insertions(+), 11 deletions(-)

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index ce695adc670ec..20082ef8c396c 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -4301,6 +4301,20 @@ static inline bool mas_wr_replace(struct ma_wr_state *wr_mas)
 	return false;
 }
 
+static inline unsigned char mas_wr_new_end(struct ma_wr_state *wr_mas)
+{
+	struct ma_state *mas = wr_mas->mas;
+	unsigned char new_end = wr_mas->node_end + 2;
+
+	new_end -= wr_mas->offset_end - mas->offset;
+	if (wr_mas->r_min == mas->index)
+		new_end--;
+	if (wr_mas->end_piv == mas->last)
+		new_end--;
+
+	return new_end;
+}
+
 static inline bool mas_wr_append(struct ma_wr_state *wr_mas)
 {
 	unsigned char end = wr_mas->node_end;
@@ -4356,25 +4370,22 @@ static void mas_wr_bnode(struct ma_wr_state *wr_mas)
 
 static inline void mas_wr_modify(struct ma_wr_state *wr_mas)
 {
-	unsigned char node_slots;
-	unsigned char node_size;
 	struct ma_state *mas = wr_mas->mas;
+	unsigned char new_end;
 
 	/* Attempt to direct replace */
 	if (mas_wr_replace(wr_mas))
 		return;
 
-	/* Attempt to append */
-	node_slots = mt_slots[wr_mas->type];
-	node_size = wr_mas->node_end - wr_mas->offset_end + mas->offset + 2;
-	if (mas->max == ULONG_MAX)
-		node_size++;
-
-	/* slot and node store will not fit, go to the slow path */
-	if (unlikely(node_size >= node_slots))
+	/*
+	 * 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;
 
-	if (wr_mas->entry && (wr_mas->node_end < node_slots - 1) &&
+	if (wr_mas->entry && (wr_mas->node_end < mt_slots[wr_mas->type] - 1) &&
 	    (mas->offset == wr_mas->node_end) && mas_wr_append(wr_mas)) {
 		if (!wr_mas->content || !wr_mas->entry)
 			mas_update_gap(mas);
-- 
2.20.1

[PATCH 08/10] maple_tree: Add comments and some minor cleanups to mas_wr_append()

[Peng Zhang]

Add comment for mas_wr_append(), move mas_update_gap() into
mas_wr_append(), and other cleanups to make mas_wr_modify() cleaner.

Signed-off-by: Peng Zhang <zhangpeng.00@bytedance.com>
---
 lib/maple_tree.c | 52 ++++++++++++++++++++++++++++++++++++------------
 1 file changed, 39 insertions(+), 13 deletions(-)

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index 20082ef8c396c..538e49feafbe4 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -4315,6 +4315,31 @@ static inline unsigned char mas_wr_new_end(struct ma_wr_state *wr_mas)
 	return new_end;
 }
 
+/*
+ * mas_wr_append: Attempt to append
+ * @wr_mas: the maple write state
+ *
+ * Return: True if appended, false otherwise
+ *
+ * Case 1:
+ *                       r_min   r_max/end_piv
+ *                 +-------+-------+
+ * original range: |       |offset |
+ *                 +-------+-------+
+ *                             +---+
+ *      overwrite:             |   |
+ *                             +---+
+ *                           index last
+ * Case 2:
+ *                       r_min   r_max/end_piv
+ *                 +-------+-------+
+ * original range: |       |offset |
+ *                 +-------+-------+
+ *                         +---+
+ *      overwrite:         |   |
+ *                         +---+
+ *                       index last
+ */
 static inline bool mas_wr_append(struct ma_wr_state *wr_mas)
 {
 	unsigned char end = wr_mas->node_end;
@@ -4322,7 +4347,11 @@ static inline bool mas_wr_append(struct ma_wr_state *wr_mas)
 	struct ma_state *mas = wr_mas->mas;
 	unsigned char node_pivots = mt_pivots[wr_mas->type];
 
+	if (!(mas->offset == wr_mas->node_end))
+		return false;
+
 	if ((mas->index != wr_mas->r_min) && (mas->last == wr_mas->r_max)) {
+		/* Case 1 */
 		if (new_end < node_pivots)
 			wr_mas->pivots[new_end] = wr_mas->pivots[end];
 
@@ -4330,13 +4359,10 @@ static inline bool mas_wr_append(struct ma_wr_state *wr_mas)
 			ma_set_meta(wr_mas->node, maple_leaf_64, 0, new_end);
 
 		rcu_assign_pointer(wr_mas->slots[new_end], wr_mas->entry);
-		mas->offset = new_end;
 		wr_mas->pivots[end] = mas->index - 1;
-
-		return true;
-	}
-
-	if ((mas->index == wr_mas->r_min) && (mas->last < wr_mas->r_max)) {
+		mas->offset = new_end;
+	} else if ((mas->index == wr_mas->r_min) && (mas->last < wr_mas->r_max)) {
+		/* Case 2 */
 		if (new_end < node_pivots)
 			wr_mas->pivots[new_end] = wr_mas->pivots[end];
 
@@ -4346,10 +4372,13 @@ static inline bool mas_wr_append(struct ma_wr_state *wr_mas)
 
 		wr_mas->pivots[end] = mas->last;
 		rcu_assign_pointer(wr_mas->slots[end], wr_mas->entry);
-		return true;
+	} else {
+		return false;
 	}
 
-	return false;
+	if (!wr_mas->content || !wr_mas->entry)
+		mas_update_gap(mas);
+	return  true;
 }
 
 /*
@@ -4385,12 +4414,9 @@ static inline void mas_wr_modify(struct ma_wr_state *wr_mas)
 	if (new_end >= mt_slots[wr_mas->type])
 		goto slow_path;
 
-	if (wr_mas->entry && (wr_mas->node_end < mt_slots[wr_mas->type] - 1) &&
-	    (mas->offset == wr_mas->node_end) && mas_wr_append(wr_mas)) {
-		if (!wr_mas->content || !wr_mas->entry)
-			mas_update_gap(mas);
+	/* Attempt to append */
+	if (new_end == wr_mas->node_end + 1 && mas_wr_append(wr_mas))
 		return;
-	}
 
 	if ((wr_mas->offset_end - mas->offset <= 1) && mas_wr_slot_store(wr_mas))
 		return;
-- 
2.20.1

[PATCH 09/10] maple_tree: Rework mas_wr_slot_store() to be cleaner and more efficient.

[Peng Zhang]

The code of mas_wr_slot_store() is messy, make it clearer and concise,
and add comments. In addition, get whether the two gaps are empty to
avoid calling mas_update_gap() all the time.

Signed-off-by: Peng Zhang <zhangpeng.00@bytedance.com>
---
 lib/maple_tree.c | 79 +++++++++++++++++++++++++++---------------------
 1 file changed, 44 insertions(+), 35 deletions(-)

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index 538e49feafbe4..d558e7bcb6da8 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -4190,53 +4190,62 @@ static inline bool mas_wr_node_store(struct ma_wr_state *wr_mas)
  * @wr_mas: the maple write state
  *
  * Return: True if stored, false otherwise
+ *
+ * Case 1:
+ *                       r_min   r_max    lmax
+ *                 +-------+-------+-------+
+ * original range: |       |offset | end   |
+ *                 +-----------------------+
+ *                         +-----------+
+ * overwrite:              |           |
+ *                         +-----------+
+ *                        index       last
+ *
+ * Case 2:
+ *                       r_min   r_max    lmax
+ *                 +-------+-------+-------+
+ * original range: |       |offest | end   |
+ *                 +-------+---------------+
+ *                             +-----------+
+ * overwrite:                  |           |
+ *                             +-----------+
+ *                           index        last
  */
 static inline bool mas_wr_slot_store(struct ma_wr_state *wr_mas)
 {
 	struct ma_state *mas = wr_mas->mas;
-	unsigned long lmax; /* Logical max. */
 	unsigned char offset = mas->offset;
+	unsigned char offset_end = wr_mas->offset_end;
+	unsigned long lmax = wr_mas->end_piv; /* Logical max. */
+	bool gap = false;
 
-	if ((wr_mas->r_max > mas->last) && ((wr_mas->r_min != mas->index) ||
-				  (offset != wr_mas->node_end)))
-		return false;
-
-	if (offset == wr_mas->node_end - 1)
-		lmax = mas->max;
-	else
-		lmax = wr_mas->pivots[offset + 1];
-
-	/* going to overwrite too many slots. */
-	if (lmax < mas->last)
+	if (offset_end - offset != 1)
 		return false;
 
-	if (wr_mas->r_min == mas->index) {
-		/* overwriting two or more ranges with one. */
-		if (lmax == mas->last)
-			return false;
-
-		/* Overwriting all of offset and a portion of offset + 1. */
+	if (mas->index == wr_mas->r_min && mas->last < lmax) {
+		/* Case 1 */
+		gap |= !mt_slot_locked(mas->tree, wr_mas->slots, offset);
+		gap |= !mt_slot_locked(mas->tree, wr_mas->slots, offset + 1);
 		rcu_assign_pointer(wr_mas->slots[offset], wr_mas->entry);
 		wr_mas->pivots[offset] = mas->last;
-		goto done;
-	}
-
-	/* Doesn't end on the next range end. */
-	if (lmax != mas->last)
+	} else if (mas->index > wr_mas->r_min && mas->last == lmax) {
+		/* Case 2 */
+		gap |= !mt_slot_locked(mas->tree, wr_mas->slots, offset);
+		gap |= !mt_slot_locked(mas->tree, wr_mas->slots, offset + 1);
+		rcu_assign_pointer(wr_mas->slots[offset + 1], wr_mas->entry);
+		wr_mas->pivots[offset] = mas->index - 1;
+		mas->offset++; /* Keep mas accurate. */
+	} else {
 		return false;
+	}
 
-	/* Overwriting a portion of offset and all of offset + 1 */
-	if ((offset + 1 < mt_pivots[wr_mas->type]) &&
-	    (wr_mas->entry || wr_mas->pivots[offset + 1]))
-		wr_mas->pivots[offset + 1] = mas->last;
-
-	rcu_assign_pointer(wr_mas->slots[offset + 1], wr_mas->entry);
-	wr_mas->pivots[offset] = mas->index - 1;
-	mas->offset++; /* Keep mas accurate. */
-
-done:
 	trace_ma_write(__func__, mas, 0, wr_mas->entry);
-	mas_update_gap(mas);
+	/*
+	 * Only update gap when the new entry is empty or there is an empty
+	 * entry in the original two ranges.
+	 */
+	if (!wr_mas->entry || gap)
+		mas_update_gap(mas);
 	return true;
 }
 
@@ -4418,7 +4427,7 @@ static inline void mas_wr_modify(struct ma_wr_state *wr_mas)
 	if (new_end == wr_mas->node_end + 1 && mas_wr_append(wr_mas))
 		return;
 
-	if ((wr_mas->offset_end - mas->offset <= 1) && mas_wr_slot_store(wr_mas))
+	if (new_end == wr_mas->node_end && mas_wr_slot_store(wr_mas))
 		return;
 	else if (mas_wr_node_store(wr_mas))
 		return;
-- 
2.20.1

[PATCH 10/10] maple_tree: Simplify and clean up mas_wr_node_store()

[Peng Zhang]

Simplify and clean up mas_wr_node_store(), remove unnecessary code.

Signed-off-by: Peng Zhang <zhangpeng.00@bytedance.com>
---
 lib/maple_tree.c | 75 +++++++++++++-----------------------------------
 1 file changed, 20 insertions(+), 55 deletions(-)

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index d558e7bcb6da8..ff4aa01cf88b6 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -4066,46 +4066,21 @@ static inline int mas_wr_spanning_store(struct ma_wr_state *wr_mas)
  *
  * Return: True if stored, false otherwise
  */
-static inline bool mas_wr_node_store(struct ma_wr_state *wr_mas)
+static inline bool mas_wr_node_store(struct ma_wr_state *wr_mas,
+				     unsigned char new_end)
 {
 	struct ma_state *mas = wr_mas->mas;
 	void __rcu **dst_slots;
 	unsigned long *dst_pivots;
 	unsigned char dst_offset;
-	unsigned char new_end = wr_mas->node_end;
-	unsigned char offset;
-	unsigned char node_slots = mt_slots[wr_mas->type];
 	struct maple_node reuse, *newnode;
-	unsigned char copy_size, max_piv = mt_pivots[wr_mas->type];
+	unsigned char copy_size, node_pivots = mt_pivots[wr_mas->type];
 	bool in_rcu = mt_in_rcu(mas->tree);
 
-	offset = mas->offset;
-	if (mas->last == wr_mas->r_max) {
-		/* runs right to the end of the node */
-		if (mas->last == mas->max)
-			new_end = offset;
-		/* don't copy this offset */
+	if (mas->last == wr_mas->end_piv)
 		wr_mas->offset_end++;
-	} else if (mas->last < wr_mas->r_max) {
-		/* new range ends in this range */
-		if (unlikely(wr_mas->r_max == ULONG_MAX))
-			mas_bulk_rebalance(mas, wr_mas->node_end, wr_mas->type);
-
-		new_end++;
-	} else {
-		if (wr_mas->end_piv == mas->last)
-			wr_mas->offset_end++;
-
-		new_end -= wr_mas->offset_end - offset - 1;
-	}
-
-	/* new range starts within a range */
-	if (wr_mas->r_min < mas->index)
-		new_end++;
-
-	/* Not enough room */
-	if (new_end >= node_slots)
-		return false;
+	else if (unlikely(wr_mas->r_max == ULONG_MAX))
+		mas_bulk_rebalance(mas, wr_mas->node_end, wr_mas->type);
 
 	/* Not enough data. */
 	if (!mte_is_root(mas->node) && (new_end <= mt_min_slots[wr_mas->type]) &&
@@ -4128,47 +4103,36 @@ static inline bool mas_wr_node_store(struct ma_wr_state *wr_mas)
 	dst_pivots = ma_pivots(newnode, wr_mas->type);
 	dst_slots = ma_slots(newnode, wr_mas->type);
 	/* Copy from start to insert point */
-	memcpy(dst_pivots, wr_mas->pivots, sizeof(unsigned long) * (offset + 1));
-	memcpy(dst_slots, wr_mas->slots, sizeof(void *) * (offset + 1));
-	dst_offset = offset;
+	memcpy(dst_pivots, wr_mas->pivots, sizeof(unsigned long) * mas->offset);
+	memcpy(dst_slots, wr_mas->slots, sizeof(void *) * mas->offset);
 
 	/* Handle insert of new range starting after old range */
 	if (wr_mas->r_min < mas->index) {
-		mas->offset++;
-		rcu_assign_pointer(dst_slots[dst_offset], wr_mas->content);
-		dst_pivots[dst_offset++] = mas->index - 1;
+		rcu_assign_pointer(dst_slots[mas->offset], wr_mas->content);
+		dst_pivots[mas->offset++] = mas->index - 1;
 	}
 
 	/* Store the new entry and range end. */
-	if (dst_offset < max_piv)
-		dst_pivots[dst_offset] = mas->last;
-	mas->offset = dst_offset;
-	rcu_assign_pointer(dst_slots[dst_offset], wr_mas->entry);
+	if (mas->offset < node_pivots)
+		dst_pivots[mas->offset] = mas->last;
+	rcu_assign_pointer(dst_slots[mas->offset], wr_mas->entry);
 
 	/*
 	 * this range wrote to the end of the node or it overwrote the rest of
 	 * the data
 	 */
-	if (wr_mas->offset_end > wr_mas->node_end || mas->last >= mas->max) {
-		new_end = dst_offset;
+	if (wr_mas->offset_end > wr_mas->node_end)
 		goto done;
-	}
 
-	dst_offset++;
+	dst_offset = mas->offset + 1;
 	/* Copy to the end of node if necessary. */
 	copy_size = wr_mas->node_end - wr_mas->offset_end + 1;
 	memcpy(dst_slots + dst_offset, wr_mas->slots + wr_mas->offset_end,
 	       sizeof(void *) * copy_size);
-	if (dst_offset < max_piv) {
-		if (copy_size > max_piv - dst_offset)
-			copy_size = max_piv - dst_offset;
+	memcpy(dst_pivots + dst_offset, wr_mas->pivots + wr_mas->offset_end,
+	       sizeof(unsigned long) * (copy_size - 1));
 
-		memcpy(dst_pivots + dst_offset,
-		       wr_mas->pivots + wr_mas->offset_end,
-		       sizeof(unsigned long) * copy_size);
-	}
-
-	if ((wr_mas->node_end == node_slots - 1) && (new_end < node_slots - 1))
+	if (new_end < node_pivots)
 		dst_pivots[new_end] = mas->max;
 
 done:
@@ -4429,7 +4393,8 @@ static inline void mas_wr_modify(struct ma_wr_state *wr_mas)
 
 	if (new_end == wr_mas->node_end && mas_wr_slot_store(wr_mas))
 		return;
-	else if (mas_wr_node_store(wr_mas))
+
+	if (mas_wr_node_store(wr_mas, new_end))
 		return;
 
 	if (mas_is_err(mas))
-- 
2.20.1

Re: [PATCH 03/10] maple_tree: Remove __must_hold() which does not work

[Matthew Wilcox]

On Mon, May 15, 2023 at 09:17:50PM +0800, Peng Zhang wrote:
> The arguments to __must_hold() seem to be wrong so they should not work,
> remove them.

Why not fix them?

Re: [PATCH 03/10] maple_tree: Remove __must_hold() which does not work

[Liam R. Howlett]

* Peng Zhang <zhangpeng.00@bytedance.com> [230515 09:18]:
> The arguments to __must_hold() seem to be wrong so they should not work,
> remove them.

This is for spase [1]. I'd like to keep them if they can be made
functional - maybe fix it to mas->tree->ma_lock? 

[1] https://www.kernel.org/doc/html/v6.1/dev-tools/sparse.html#using-sparse-for-lock-checking

> 
> Signed-off-by: Peng Zhang <zhangpeng.00@bytedance.com>
> ---
>  lib/maple_tree.c | 3 ---
>  1 file changed, 3 deletions(-)
> 
> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> index 49dfe81dfa1b6..43a25d3042c1b 100644
> --- a/lib/maple_tree.c
> +++ b/lib/maple_tree.c
> @@ -1752,7 +1752,6 @@ static inline void mas_adopt_children(struct ma_state *mas,
>   * leave the node (true) and handle the adoption and free elsewhere.
>   */
>  static inline void mas_replace(struct ma_state *mas, bool advanced)
> -	__must_hold(mas->tree->lock)
>  {
>  	struct maple_node *mn = mas_mn(mas);
>  	struct maple_enode *old_enode;
> @@ -1792,7 +1791,6 @@ static inline void mas_replace(struct ma_state *mas, bool advanced)
>   * @child: the maple state to store the child.
>   */
>  static inline bool mas_new_child(struct ma_state *mas, struct ma_state *child)
> -	__must_hold(mas->tree->lock)
>  {
>  	enum maple_type mt;
>  	unsigned char offset;
> @@ -6198,7 +6196,6 @@ EXPORT_SYMBOL_GPL(mas_erase);
>   * Return: true on allocation, false otherwise.
>   */
>  bool mas_nomem(struct ma_state *mas, gfp_t gfp)
> -	__must_hold(mas->tree->lock)
>  {
>  	if (likely(mas->node != MA_ERROR(-ENOMEM))) {
>  		mas_destroy(mas);
> -- 
> 2.20.1
> 

Re: [PATCH 04/10] maple_tree: Simplify mas_is_span_wr()

[Liam R. Howlett]

* Peng Zhang <zhangpeng.00@bytedance.com> [230515 09:18]:
> Make the code for detecting spanning writes more concise.
> 
> Signed-off-by: Peng Zhang <zhangpeng.00@bytedance.com>
> ---
>  lib/maple_tree.c | 36 +++++++++---------------------------
>  1 file changed, 9 insertions(+), 27 deletions(-)
> 
> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> index 43a25d3042c1b..fbb6efc40e576 100644
> --- a/lib/maple_tree.c
> +++ b/lib/maple_tree.c
> @@ -3728,41 +3728,23 @@ static bool mas_is_span_wr(struct ma_wr_state *wr_mas)
>  {
>  	unsigned long max;
>  	unsigned long last = wr_mas->mas->last;
> -	unsigned long piv = wr_mas->r_max;
>  	enum maple_type type = wr_mas->type;
>  	void *entry = wr_mas->entry;
>  
> -	/* Contained in this pivot */
> -	if (piv > last)

I test this first since it is far more likely than the rest of the cases
in this function.  Most writes will land in a leaf node eventually, so
this will be true most of the time.  I'd like to keep it as a fast path.

> +	max = unlikely(ma_is_leaf(type)) ? wr_mas->mas->max : wr_mas->r_max;

Please expand this to multiple lines.  It is better to be more clear
than compact lines of code.

> +	if (last < max) {
> +		/* Contained in this pivot or this leaf node */
>  		return false;
> -
> -	max = wr_mas->mas->max;
> -	if (unlikely(ma_is_leaf(type))) {
> -		/* Fits in the node, but may span slots. */
> -		if (last < max)
> -			return false;
> -
> -		/* Writes to the end of the node but not null. */
> -		if ((last == max) && entry)
> -			return false;
> -
> +	} else if (last == max) {
>  		/*
> -		 * Writing ULONG_MAX is not a spanning write regardless of the
> -		 * value being written as long as the range fits in the node.
> +		 * The last entry of leaf node cannot be NULL unless it is the
> +		 * rightmost node (writing ULONG_MAX), otherwise it spans slots.
> +		 * If this is not leaf node, detect spanning store wr walk.
>  		 */
> -		if ((last == ULONG_MAX) && (last == max))
> -			return false;
> -	} else if (piv == last) {
> -		if (entry)
> -			return false;
> -
> -		/* Detect spanning store wr walk */
> -		if (last == ULONG_MAX)
> +		if (entry || last == ULONG_MAX)
>  			return false;
>  	}
> -
> -	trace_ma_write(__func__, wr_mas->mas, piv, entry);
> -
> +	trace_ma_write(__func__, wr_mas->mas, wr_mas->r_max, entry);
>  	return true;
>  }
>  
> -- 
> 2.20.1
> 

Re: [PATCH 01/10] maple_tree: Drop the test code for mtree_alloc_{range,rrange}()

[Liam R. Howlett]

* Peng Zhang <zhangpeng.00@bytedance.com> [230515 09:18]:
> Drop the test code for mtree_alloc_{range,rrange}() because we are going
> to drop them.
> 
> Signed-off-by: Peng Zhang <zhangpeng.00@bytedance.com>

Reviewed-by: Liam R. Howlett <Liam.Howlett@oracle.com>

> ---
>  lib/test_maple_tree.c | 389 ------------------------------------------
>  1 file changed, 389 deletions(-)
> 
> diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c
> index 9939be34e516e..86d7f742d243e 100644
> --- a/lib/test_maple_tree.c
> +++ b/lib/test_maple_tree.c
> @@ -97,42 +97,6 @@ static void __init *mtree_test_erase(struct maple_tree *mt, unsigned long index)
>  	return mtree_erase(mt, index);
>  }
>  
> -#if defined(CONFIG_64BIT)
> -static noinline void __init check_mtree_alloc_range(struct maple_tree *mt,
> -		unsigned long start, unsigned long end, unsigned long size,
> -		unsigned long expected, int eret, void *ptr)
> -{
> -
> -	unsigned long result = expected + 1;
> -	int ret;
> -
> -	ret = mtree_alloc_range(mt, &result, ptr, size, start, end,
> -			GFP_KERNEL);
> -	MT_BUG_ON(mt, ret != eret);
> -	if (ret)
> -		return;
> -
> -	MT_BUG_ON(mt, result != expected);
> -}
> -
> -static noinline void __init check_mtree_alloc_rrange(struct maple_tree *mt,
> -		unsigned long start, unsigned long end, unsigned long size,
> -		unsigned long expected, int eret, void *ptr)
> -{
> -
> -	unsigned long result = expected + 1;
> -	int ret;
> -
> -	ret = mtree_alloc_rrange(mt, &result, ptr, size, start, end,
> -			GFP_KERNEL);
> -	MT_BUG_ON(mt, ret != eret);
> -	if (ret)
> -		return;
> -
> -	MT_BUG_ON(mt, result != expected);
> -}
> -#endif
> -
>  static noinline void __init check_load(struct maple_tree *mt,
>  				       unsigned long index, void *ptr)
>  {
> @@ -635,348 +599,6 @@ static noinline void __init check_find_2(struct maple_tree *mt)
>  	/*MT_BUG_ON(mt, !mtree_empty(mt)); */
>  }
>  
> -
> -#if defined(CONFIG_64BIT)
> -static noinline void __init check_alloc_rev_range(struct maple_tree *mt)
> -{
> -	/*
> -	 * Generated by:
> -	 * cat /proc/self/maps | awk '{print $1}'|
> -	 * awk -F "-" '{printf "0x%s, 0x%s, ", $1, $2}'
> -	 */
> -
> -	static const unsigned long range[] = {
> -	/*      Inclusive     , Exclusive. */
> -		0x565234af2000, 0x565234af4000,
> -		0x565234af4000, 0x565234af9000,
> -		0x565234af9000, 0x565234afb000,
> -		0x565234afc000, 0x565234afd000,
> -		0x565234afd000, 0x565234afe000,
> -		0x565235def000, 0x565235e10000,
> -		0x7f36d4bfd000, 0x7f36d4ee2000,
> -		0x7f36d4ee2000, 0x7f36d4f04000,
> -		0x7f36d4f04000, 0x7f36d504c000,
> -		0x7f36d504c000, 0x7f36d5098000,
> -		0x7f36d5098000, 0x7f36d5099000,
> -		0x7f36d5099000, 0x7f36d509d000,
> -		0x7f36d509d000, 0x7f36d509f000,
> -		0x7f36d509f000, 0x7f36d50a5000,
> -		0x7f36d50b9000, 0x7f36d50db000,
> -		0x7f36d50db000, 0x7f36d50dc000,
> -		0x7f36d50dc000, 0x7f36d50fa000,
> -		0x7f36d50fa000, 0x7f36d5102000,
> -		0x7f36d5102000, 0x7f36d5103000,
> -		0x7f36d5103000, 0x7f36d5104000,
> -		0x7f36d5104000, 0x7f36d5105000,
> -		0x7fff5876b000, 0x7fff5878d000,
> -		0x7fff5878e000, 0x7fff58791000,
> -		0x7fff58791000, 0x7fff58793000,
> -	};
> -
> -	static const unsigned long holes[] = {
> -		/*
> -		 * Note: start of hole is INCLUSIVE
> -		 *        end of hole is EXCLUSIVE
> -		 *        (opposite of the above table.)
> -		 * Start of hole, end of hole,  size of hole (+1)
> -		 */
> -		0x565234afb000, 0x565234afc000, 0x1000,
> -		0x565234afe000, 0x565235def000, 0x12F1000,
> -		0x565235e10000, 0x7f36d4bfd000, 0x28E49EDED000,
> -	};
> -
> -	/*
> -	 * req_range consists of 4 values.
> -	 * 1. min index
> -	 * 2. max index
> -	 * 3. size
> -	 * 4. number that should be returned.
> -	 * 5. return value
> -	 */
> -	static const unsigned long req_range[] = {
> -		0x565234af9000, /* Min */
> -		0x7fff58791000, /* Max */
> -		0x1000,         /* Size */
> -		0x7fff5878d << 12,  /* First rev hole of size 0x1000 */
> -		0,              /* Return value success. */
> -
> -		0x0,            /* Min */
> -		0x565234AF0 << 12,    /* Max */
> -		0x3000,         /* Size */
> -		0x565234AEE << 12,  /* max - 3. */
> -		0,              /* Return value success. */
> -
> -		0x0,            /* Min */
> -		-1,             /* Max */
> -		0x1000,         /* Size */
> -		562949953421311 << 12,/* First rev hole of size 0x1000 */
> -		0,              /* Return value success. */
> -
> -		0x0,            /* Min */
> -		0x7F36D5109 << 12,    /* Max */
> -		0x4000,         /* Size */
> -		0x7F36D5106 << 12,    /* First rev hole of size 0x4000 */
> -		0,              /* Return value success. */
> -
> -		/* Ascend test. */
> -		0x0,
> -		34148798628 << 12,
> -		19 << 12,
> -		34148797418 << 12,
> -		0x0,
> -
> -		/* Too big test. */
> -		0x0,
> -		18446744073709551615UL,
> -		562915594369134UL << 12,
> -		0x0,
> -		-EBUSY,
> -
> -		/* Single space test. */
> -		34148798725 << 12,
> -		34148798725 << 12,
> -		1 << 12,
> -		34148798725 << 12,
> -		0,
> -	};
> -
> -	int i, range_count = ARRAY_SIZE(range);
> -	int req_range_count = ARRAY_SIZE(req_range);
> -	unsigned long min = 0;
> -
> -	MA_STATE(mas, mt, 0, 0);
> -
> -	mtree_store_range(mt, MTREE_ALLOC_MAX, ULONG_MAX, XA_ZERO_ENTRY,
> -			  GFP_KERNEL);
> -#define DEBUG_REV_RANGE 0
> -	for (i = 0; i < range_count; i += 2) {
> -		/* Inclusive, Inclusive (with the -1) */
> -
> -#if DEBUG_REV_RANGE
> -		pr_debug("\t%s: Insert %lu-%lu\n", __func__, range[i] >> 12,
> -				(range[i + 1] >> 12) - 1);
> -#endif
> -		check_insert_range(mt, range[i] >> 12, (range[i + 1] >> 12) - 1,
> -				xa_mk_value(range[i] >> 12), 0);
> -		mt_validate(mt);
> -	}
> -
> -
> -	mas_lock(&mas);
> -	for (i = 0; i < ARRAY_SIZE(holes); i += 3) {
> -#if DEBUG_REV_RANGE
> -		pr_debug("Search from %lu-%lu for gap %lu should be at %lu\n",
> -				min, holes[i+1]>>12, holes[i+2]>>12,
> -				holes[i] >> 12);
> -#endif
> -		MT_BUG_ON(mt, mas_empty_area_rev(&mas, min,
> -					holes[i+1] >> 12,
> -					holes[i+2] >> 12));
> -#if DEBUG_REV_RANGE
> -		pr_debug("Found %lu %lu\n", mas.index, mas.last);
> -		pr_debug("gap %lu %lu\n", (holes[i] >> 12),
> -				(holes[i+1] >> 12));
> -#endif
> -		MT_BUG_ON(mt, mas.last + 1 != (holes[i+1] >> 12));
> -		MT_BUG_ON(mt, mas.index != (holes[i+1] >> 12) - (holes[i+2] >> 12));
> -		min = holes[i+1] >> 12;
> -		mas_reset(&mas);
> -	}
> -
> -	mas_unlock(&mas);
> -	for (i = 0; i < req_range_count; i += 5) {
> -#if DEBUG_REV_RANGE
> -		pr_debug("\tReverse request %d between %lu-%lu size %lu, should get %lu\n",
> -				i, req_range[i] >> 12,
> -				(req_range[i + 1] >> 12),
> -				req_range[i+2] >> 12,
> -				req_range[i+3] >> 12);
> -#endif
> -		check_mtree_alloc_rrange(mt,
> -				req_range[i]   >> 12, /* start */
> -				req_range[i+1] >> 12, /* end */
> -				req_range[i+2] >> 12, /* size */
> -				req_range[i+3] >> 12, /* expected address */
> -				req_range[i+4],       /* expected return */
> -				xa_mk_value(req_range[i] >> 12)); /* pointer */
> -		mt_validate(mt);
> -	}
> -
> -	mt_set_non_kernel(1);
> -	mtree_erase(mt, 34148798727); /* create a deleted range. */
> -	mtree_erase(mt, 34148798725);
> -	check_mtree_alloc_rrange(mt, 0, 34359052173, 210253414,
> -			34148798725, 0, mt);
> -
> -	mtree_destroy(mt);
> -}
> -
> -static noinline void __init check_alloc_range(struct maple_tree *mt)
> -{
> -	/*
> -	 * Generated by:
> -	 * cat /proc/self/maps|awk '{print $1}'|
> -	 * awk -F "-" '{printf "0x%s, 0x%s, ", $1, $2}'
> -	 */
> -
> -	static const unsigned long range[] = {
> -	/*      Inclusive     , Exclusive. */
> -		0x565234af2000, 0x565234af4000,
> -		0x565234af4000, 0x565234af9000,
> -		0x565234af9000, 0x565234afb000,
> -		0x565234afc000, 0x565234afd000,
> -		0x565234afd000, 0x565234afe000,
> -		0x565235def000, 0x565235e10000,
> -		0x7f36d4bfd000, 0x7f36d4ee2000,
> -		0x7f36d4ee2000, 0x7f36d4f04000,
> -		0x7f36d4f04000, 0x7f36d504c000,
> -		0x7f36d504c000, 0x7f36d5098000,
> -		0x7f36d5098000, 0x7f36d5099000,
> -		0x7f36d5099000, 0x7f36d509d000,
> -		0x7f36d509d000, 0x7f36d509f000,
> -		0x7f36d509f000, 0x7f36d50a5000,
> -		0x7f36d50b9000, 0x7f36d50db000,
> -		0x7f36d50db000, 0x7f36d50dc000,
> -		0x7f36d50dc000, 0x7f36d50fa000,
> -		0x7f36d50fa000, 0x7f36d5102000,
> -		0x7f36d5102000, 0x7f36d5103000,
> -		0x7f36d5103000, 0x7f36d5104000,
> -		0x7f36d5104000, 0x7f36d5105000,
> -		0x7fff5876b000, 0x7fff5878d000,
> -		0x7fff5878e000, 0x7fff58791000,
> -		0x7fff58791000, 0x7fff58793000,
> -	};
> -	static const unsigned long holes[] = {
> -		/* Start of hole, end of hole,  size of hole (+1) */
> -		0x565234afb000, 0x565234afc000, 0x1000,
> -		0x565234afe000, 0x565235def000, 0x12F1000,
> -		0x565235e10000, 0x7f36d4bfd000, 0x28E49EDED000,
> -	};
> -
> -	/*
> -	 * req_range consists of 4 values.
> -	 * 1. min index
> -	 * 2. max index
> -	 * 3. size
> -	 * 4. number that should be returned.
> -	 * 5. return value
> -	 */
> -	static const unsigned long req_range[] = {
> -		0x565234af9000, /* Min */
> -		0x7fff58791000, /* Max */
> -		0x1000,         /* Size */
> -		0x565234afb000, /* First hole in our data of size 1000. */
> -		0,              /* Return value success. */
> -
> -		0x0,            /* Min */
> -		0x7fff58791000, /* Max */
> -		0x1F00,         /* Size */
> -		0x0,            /* First hole in our data of size 2000. */
> -		0,              /* Return value success. */
> -
> -		/* Test ascend. */
> -		34148797436 << 12, /* Min */
> -		0x7fff587AF000,    /* Max */
> -		0x3000,         /* Size */
> -		34148798629 << 12,             /* Expected location */
> -		0,              /* Return value success. */
> -
> -		/* Test failing. */
> -		34148798623 << 12,  /* Min */
> -		34148798683 << 12,  /* Max */
> -		0x15000,            /* Size */
> -		0,             /* Expected location */
> -		-EBUSY,              /* Return value failed. */
> -
> -		/* Test filling entire gap. */
> -		34148798623 << 12,  /* Min */
> -		0x7fff587AF000,    /* Max */
> -		0x10000,           /* Size */
> -		34148798632 << 12,             /* Expected location */
> -		0,              /* Return value success. */
> -
> -		/* Test walking off the end of root. */
> -		0,                  /* Min */
> -		-1,                 /* Max */
> -		-1,                 /* Size */
> -		0,                  /* Expected location */
> -		-EBUSY,             /* Return value failure. */
> -
> -		/* Test looking for too large a hole across entire range. */
> -		0,                  /* Min */
> -		-1,                 /* Max */
> -		4503599618982063UL << 12,  /* Size */
> -		34359052178 << 12,  /* Expected location */
> -		-EBUSY,             /* Return failure. */
> -
> -		/* Test a single entry */
> -		34148798648 << 12,		/* Min */
> -		34148798648 << 12,		/* Max */
> -		4096,			/* Size of 1 */
> -		34148798648 << 12,	/* Location is the same as min/max */
> -		0,			/* Success */
> -	};
> -	int i, range_count = ARRAY_SIZE(range);
> -	int req_range_count = ARRAY_SIZE(req_range);
> -	unsigned long min = 0x565234af2000;
> -	MA_STATE(mas, mt, 0, 0);
> -
> -	mtree_store_range(mt, MTREE_ALLOC_MAX, ULONG_MAX, XA_ZERO_ENTRY,
> -			  GFP_KERNEL);
> -	for (i = 0; i < range_count; i += 2) {
> -#define DEBUG_ALLOC_RANGE 0
> -#if DEBUG_ALLOC_RANGE
> -		pr_debug("\tInsert %lu-%lu\n", range[i] >> 12,
> -			 (range[i + 1] >> 12) - 1);
> -		mt_dump(mt, mt_dump_hex);
> -#endif
> -		check_insert_range(mt, range[i] >> 12, (range[i + 1] >> 12) - 1,
> -				xa_mk_value(range[i] >> 12), 0);
> -		mt_validate(mt);
> -	}
> -
> -
> -
> -	mas_lock(&mas);
> -	for (i = 0; i < ARRAY_SIZE(holes); i += 3) {
> -
> -#if DEBUG_ALLOC_RANGE
> -		pr_debug("\tGet empty %lu-%lu size %lu (%lx-%lx)\n", min >> 12,
> -			holes[i+1] >> 12, holes[i+2] >> 12,
> -			min, holes[i+1]);
> -#endif
> -		MT_BUG_ON(mt, mas_empty_area(&mas, min >> 12,
> -					holes[i+1] >> 12,
> -					holes[i+2] >> 12));
> -		MT_BUG_ON(mt, mas.index != holes[i] >> 12);
> -		min = holes[i+1];
> -		mas_reset(&mas);
> -	}
> -	mas_unlock(&mas);
> -	for (i = 0; i < req_range_count; i += 5) {
> -#if DEBUG_ALLOC_RANGE
> -		pr_debug("\tTest %d: %lu-%lu size %lu expected %lu (%lu-%lu)\n",
> -			 i/5, req_range[i]   >> 12, req_range[i + 1]   >> 12,
> -			 req_range[i + 2]   >> 12, req_range[i + 3]   >> 12,
> -			 req_range[i], req_range[i+1]);
> -#endif
> -		check_mtree_alloc_range(mt,
> -				req_range[i]   >> 12, /* start */
> -				req_range[i+1] >> 12, /* end */
> -				req_range[i+2] >> 12, /* size */
> -				req_range[i+3] >> 12, /* expected address */
> -				req_range[i+4],       /* expected return */
> -				xa_mk_value(req_range[i] >> 12)); /* pointer */
> -		mt_validate(mt);
> -#if DEBUG_ALLOC_RANGE
> -		mt_dump(mt, mt_dump_hex);
> -#endif
> -	}
> -
> -	mtree_destroy(mt);
> -}
> -#endif
> -
>  static noinline void __init check_ranges(struct maple_tree *mt)
>  {
>  	int i, val, val2;
> @@ -3448,17 +3070,6 @@ static int __init maple_tree_seed(void)
>  	check_ranges(&tree);
>  	mtree_destroy(&tree);
>  
> -#if defined(CONFIG_64BIT)
> -	/* These tests have ranges outside of 4GB */
> -	mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
> -	check_alloc_range(&tree);
> -	mtree_destroy(&tree);
> -
> -	mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
> -	check_alloc_rev_range(&tree);
> -	mtree_destroy(&tree);
> -#endif
> -
>  	mt_init_flags(&tree, 0);
>  
>  	check_load(&tree, set[0], NULL);       /* See if 5015 -> NULL */
> -- 
> 2.20.1
> 

Re: [PATCH 02/10] maple_tree: Drop mtree_alloc_{range,rrange}() and related functions.

[Liam R. Howlett]

* Peng Zhang <zhangpeng.00@bytedance.com> [230515 09:18]:
> Drop mtree_alloc_{range,rrange}(), mas_{rev_}alloc() and mas_fill_gap().
> mtree_alloc_{range,rrange}() currently have no users and can be easily
> implemented with mas_empty_area{_rev}(). mas_{rev_}alloc() and
> mas_fill_gap() are just their internal functions, drop them together.
> 
> Signed-off-by: Peng Zhang <zhangpeng.00@bytedance.com>

Reviewed-by: Liam R. Howlett <Liam.Howlett@oracle.com>

> ---
>  include/linux/maple_tree.h |   7 --
>  lib/maple_tree.c           | 177 -------------------------------------
>  2 files changed, 184 deletions(-)
> 
> diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h
> index 542b09118a09f..3dd6edccf83af 100644
> --- a/include/linux/maple_tree.h
> +++ b/include/linux/maple_tree.h
> @@ -306,13 +306,6 @@ int mtree_insert(struct maple_tree *mt, unsigned long index,
>  		void *entry, gfp_t gfp);
>  int mtree_insert_range(struct maple_tree *mt, unsigned long first,
>  		unsigned long last, void *entry, gfp_t gfp);
> -int mtree_alloc_range(struct maple_tree *mt, unsigned long *startp,
> -		void *entry, unsigned long size, unsigned long min,
> -		unsigned long max, gfp_t gfp);
> -int mtree_alloc_rrange(struct maple_tree *mt, unsigned long *startp,
> -		void *entry, unsigned long size, unsigned long min,
> -		unsigned long max, gfp_t gfp);
> -
>  int mtree_store_range(struct maple_tree *mt, unsigned long first,
>  		      unsigned long last, void *entry, gfp_t gfp);
>  int mtree_store(struct maple_tree *mt, unsigned long index,
> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> index b37065a6f570d..49dfe81dfa1b6 100644
> --- a/lib/maple_tree.c
> +++ b/lib/maple_tree.c
> @@ -5120,46 +5120,6 @@ static inline void mas_awalk(struct ma_state *mas, unsigned long size)
>  	}
>  }
>  
> -/*
> - * mas_fill_gap() - Fill a located gap with @entry.
> - * @mas: The maple state
> - * @entry: The value to store
> - * @slot: The offset into the node to store the @entry
> - * @size: The size of the entry
> - * @index: The start location
> - */
> -static inline void mas_fill_gap(struct ma_state *mas, void *entry,
> -		unsigned char slot, unsigned long size, unsigned long *index)
> -{
> -	MA_WR_STATE(wr_mas, mas, entry);
> -	unsigned char pslot = mte_parent_slot(mas->node);
> -	struct maple_enode *mn = mas->node;
> -	unsigned long *pivots;
> -	enum maple_type ptype;
> -	/*
> -	 * mas->index is the start address for the search
> -	 *  which may no longer be needed.
> -	 * mas->last is the end address for the search
> -	 */
> -
> -	*index = mas->index;
> -	mas->last = mas->index + size - 1;
> -
> -	/*
> -	 * It is possible that using mas->max and mas->min to correctly
> -	 * calculate the index and last will cause an issue in the gap
> -	 * calculation, so fix the ma_state here
> -	 */
> -	mas_ascend(mas);
> -	ptype = mte_node_type(mas->node);
> -	pivots = ma_pivots(mas_mn(mas), ptype);
> -	mas->max = mas_safe_pivot(mas, pivots, pslot, ptype);
> -	mas->min = mas_safe_min(mas, pivots, pslot);
> -	mas->node = mn;
> -	mas->offset = slot;
> -	mas_wr_store_entry(&wr_mas);
> -}
> -
>  /*
>   * mas_sparse_area() - Internal function.  Return upper or lower limit when
>   * searching for a gap in an empty tree.
> @@ -5307,74 +5267,6 @@ int mas_empty_area_rev(struct ma_state *mas, unsigned long min,
>  }
>  EXPORT_SYMBOL_GPL(mas_empty_area_rev);
>  
> -static inline int mas_alloc(struct ma_state *mas, void *entry,
> -		unsigned long size, unsigned long *index)
> -{
> -	unsigned long min;
> -
> -	mas_start(mas);
> -	if (mas_is_none(mas) || mas_is_ptr(mas)) {
> -		mas_root_expand(mas, entry);
> -		if (mas_is_err(mas))
> -			return xa_err(mas->node);
> -
> -		if (!mas->index)
> -			return mas_pivot(mas, 0);
> -		return mas_pivot(mas, 1);
> -	}
> -
> -	/* Must be walking a tree. */
> -	mas_awalk(mas, size);
> -	if (mas_is_err(mas))
> -		return xa_err(mas->node);
> -
> -	if (mas->offset == MAPLE_NODE_SLOTS)
> -		goto no_gap;
> -
> -	/*
> -	 * At this point, mas->node points to the right node and we have an
> -	 * offset that has a sufficient gap.
> -	 */
> -	min = mas->min;
> -	if (mas->offset)
> -		min = mas_pivot(mas, mas->offset - 1) + 1;
> -
> -	if (mas_is_err(mas))
> -		return xa_err(mas->node);
> -
> -	if (mas->index < min)
> -		mas->index = min;
> -
> -	mas_fill_gap(mas, entry, mas->offset, size, index);
> -	return 0;
> -
> -no_gap:
> -	return -EBUSY;
> -}
> -
> -static inline int mas_rev_alloc(struct ma_state *mas, unsigned long min,
> -				unsigned long max, void *entry,
> -				unsigned long size, unsigned long *index)
> -{
> -	int ret = 0;
> -
> -	ret = mas_empty_area_rev(mas, min, max, size);
> -	if (ret)
> -		return ret;
> -
> -	if (mas_is_err(mas))
> -		return xa_err(mas->node);
> -
> -	if (mas->offset == MAPLE_NODE_SLOTS)
> -		goto no_gap;
> -
> -	mas_fill_gap(mas, entry, mas->offset, size, index);
> -	return 0;
> -
> -no_gap:
> -	return -EBUSY;
> -}
> -
>  /*
>   * mte_dead_leaves() - Mark all leaves of a node as dead.
>   * @mas: The maple state
> @@ -6481,75 +6373,6 @@ int mtree_insert(struct maple_tree *mt, unsigned long index, void *entry,
>  }
>  EXPORT_SYMBOL(mtree_insert);
>  
> -int mtree_alloc_range(struct maple_tree *mt, unsigned long *startp,
> -		void *entry, unsigned long size, unsigned long min,
> -		unsigned long max, gfp_t gfp)
> -{
> -	int ret = 0;
> -
> -	MA_STATE(mas, mt, min, min);
> -	if (!mt_is_alloc(mt))
> -		return -EINVAL;
> -
> -	if (WARN_ON_ONCE(mt_is_reserved(entry)))
> -		return -EINVAL;
> -
> -	if (min > max)
> -		return -EINVAL;
> -
> -	if (max < size)
> -		return -EINVAL;
> -
> -	if (!size)
> -		return -EINVAL;
> -
> -	mtree_lock(mt);
> -retry:
> -	mas.offset = 0;
> -	mas.index = min;
> -	mas.last = max - size + 1;
> -	ret = mas_alloc(&mas, entry, size, startp);
> -	if (mas_nomem(&mas, gfp))
> -		goto retry;
> -
> -	mtree_unlock(mt);
> -	return ret;
> -}
> -EXPORT_SYMBOL(mtree_alloc_range);
> -
> -int mtree_alloc_rrange(struct maple_tree *mt, unsigned long *startp,
> -		void *entry, unsigned long size, unsigned long min,
> -		unsigned long max, gfp_t gfp)
> -{
> -	int ret = 0;
> -
> -	MA_STATE(mas, mt, min, max - size + 1);
> -	if (!mt_is_alloc(mt))
> -		return -EINVAL;
> -
> -	if (WARN_ON_ONCE(mt_is_reserved(entry)))
> -		return -EINVAL;
> -
> -	if (min > max)
> -		return -EINVAL;
> -
> -	if (max < size - 1)
> -		return -EINVAL;
> -
> -	if (!size)
> -		return -EINVAL;
> -
> -	mtree_lock(mt);
> -retry:
> -	ret = mas_rev_alloc(&mas, min, max, entry, size, startp);
> -	if (mas_nomem(&mas, gfp))
> -		goto retry;
> -
> -	mtree_unlock(mt);
> -	return ret;
> -}
> -EXPORT_SYMBOL(mtree_alloc_rrange);
> -
>  /**
>   * mtree_erase() - Find an index and erase the entire range.
>   * @mt: The maple tree
> -- 
> 2.20.1
> 

Re: [PATCH 05/10] maple_tree: Make the code symmetrical in mas_wr_extend_null()

[Liam R. Howlett]

* Peng Zhang <zhangpeng.00@bytedance.com> [230515 09:18]:
> Just make the code symmetrical to improve readability.
> 
> Signed-off-by: Peng Zhang <zhangpeng.00@bytedance.com>

Reviewed-by: Liam R. Howlett <Liam.Howlett@oracle.com>

> ---
>  lib/maple_tree.c | 26 ++++++++++++++------------
>  1 file changed, 14 insertions(+), 12 deletions(-)
> 
> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> index fbb6efc40e576..4c649d75a4923 100644
> --- a/lib/maple_tree.c
> +++ b/lib/maple_tree.c
> @@ -4256,19 +4256,21 @@ static inline void mas_wr_extend_null(struct ma_wr_state *wr_mas)
>  {
>  	struct ma_state *mas = wr_mas->mas;
>  
> -	if (mas->last < wr_mas->end_piv && !wr_mas->slots[wr_mas->offset_end])
> +	if (!wr_mas->slots[wr_mas->offset_end]) {
> +		/* If this one is null, the next and prev are not */
>  		mas->last = wr_mas->end_piv;
> -
> -	/* Check next slot(s) if we are overwriting the end */
> -	if ((mas->last == wr_mas->end_piv) &&
> -	    (wr_mas->node_end != wr_mas->offset_end) &&
> -	    !wr_mas->slots[wr_mas->offset_end + 1]) {
> -		wr_mas->offset_end++;
> -		if (wr_mas->offset_end == wr_mas->node_end)
> -			mas->last = mas->max;
> -		else
> -			mas->last = wr_mas->pivots[wr_mas->offset_end];
> -		wr_mas->end_piv = mas->last;
> +	} else {
> +		/* Check next slot(s) if we are overwriting the end */
> +		if ((mas->last == wr_mas->end_piv) &&
> +		    (wr_mas->node_end != wr_mas->offset_end) &&
> +		    !wr_mas->slots[wr_mas->offset_end + 1]) {
> +			wr_mas->offset_end++;
> +			if (wr_mas->offset_end == wr_mas->node_end)
> +				mas->last = mas->max;
> +			else
> +				mas->last = wr_mas->pivots[wr_mas->offset_end];
> +			wr_mas->end_piv = mas->last;
> +		}
>  	}
>  
>  	if (!wr_mas->content) {
> -- 
> 2.20.1
> 

Re: [PATCH 06/10] maple_tree: Wrap the replace operation with an inline function.

[Liam R. Howlett]

* Peng Zhang <zhangpeng.00@bytedance.com> [230515 09:18]:
> To make mas_wr_modify() cleaner, wrap the replace operation with an
> inline function.

mas_wr_modify() is already pretty small.  Is there any reason you want
this in its own function besides it looking cleaner?

> 
> Signed-off-by: Peng Zhang <zhangpeng.00@bytedance.com>
> ---
>  lib/maple_tree.c | 21 +++++++++++++++------
>  1 file changed, 15 insertions(+), 6 deletions(-)
> 
> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> index 4c649d75a4923..ce695adc670ec 100644
> --- a/lib/maple_tree.c
> +++ b/lib/maple_tree.c
> @@ -4288,6 +4288,19 @@ static inline void mas_wr_extend_null(struct ma_wr_state *wr_mas)
>  	}
>  }
>  
> +static inline bool mas_wr_replace(struct ma_wr_state *wr_mas)
> +{
> +	struct ma_state *mas = wr_mas->mas;
> +
> +	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 true;
> +	}
> +	return false;
> +}
> +
>  static inline bool mas_wr_append(struct ma_wr_state *wr_mas)
>  {
>  	unsigned char end = wr_mas->node_end;
> @@ -4347,13 +4360,9 @@ static inline void mas_wr_modify(struct ma_wr_state *wr_mas)
>  	unsigned char node_size;
>  	struct ma_state *mas = wr_mas->mas;
>  
> -	/* 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);
> +	/* Attempt to direct replace */
> +	if (mas_wr_replace(wr_mas))
>  		return;
> -	}
>  
>  	/* Attempt to append */
>  	node_slots = mt_slots[wr_mas->type];
> -- 
> 2.20.1
> 

Re: [PATCH 02/10] maple_tree: Drop mtree_alloc_{range,rrange}() and related functions.

[Matthew Wilcox]

On Mon, May 15, 2023 at 09:17:49PM +0800, Peng Zhang wrote:
> Drop mtree_alloc_{range,rrange}(), mas_{rev_}alloc() and mas_fill_gap().
> mtree_alloc_{range,rrange}() currently have no users and can be easily
> implemented with mas_empty_area{_rev}(). mas_{rev_}alloc() and
> mas_fill_gap() are just their internal functions, drop them together.

No, I think this is the wrong way to go.

Most users should not be using the mas_* API.  These are the advanced
APIs.  Most users will want to use mtree_alloc_range().  Just like most
users of the XArray use the xa_insert() API rather than open-coding the
xa_state and calling the xas_* APIs.

Please read Documentation/core-api/xarray.rst and maple_tree.rst for more
details on Normal vs Advanced API.  The real problem is that we have so
few users today, so you haven't seen that most people don't want to use
the advanced APIs.

Re: [PATCH 08/10] maple_tree: Add comments and some minor cleanups to mas_wr_append()

[Liam R. Howlett]

* Peng Zhang <zhangpeng.00@bytedance.com> [230515 09:18]:
> Add comment for mas_wr_append(), move mas_update_gap() into
> mas_wr_append(), and other cleanups to make mas_wr_modify() cleaner.

Sorry, no.

I won't accept cases in the comments and referencing it in the code.
I'm not making any vma_adjust() or vma_merge()-like comment blocks.

Please change Case 1/2 to "Append to start of range"/"Append to end of
range"

This path leads to chaos.

> 
> Signed-off-by: Peng Zhang <zhangpeng.00@bytedance.com>
> ---
>  lib/maple_tree.c | 52 ++++++++++++++++++++++++++++++++++++------------
>  1 file changed, 39 insertions(+), 13 deletions(-)
> 
> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> index 20082ef8c396c..538e49feafbe4 100644
> --- a/lib/maple_tree.c
> +++ b/lib/maple_tree.c
> @@ -4315,6 +4315,31 @@ static inline unsigned char mas_wr_new_end(struct ma_wr_state *wr_mas)
>  	return new_end;
>  }
>  
> +/*
> + * mas_wr_append: Attempt to append
> + * @wr_mas: the maple write state
> + *
> + * Return: True if appended, false otherwise
> + *
> + * Case 1:
> + *                       r_min   r_max/end_piv
> + *                 +-------+-------+
> + * original range: |       |offset |
> + *                 +-------+-------+
> + *                             +---+
> + *      overwrite:             |   |
> + *                             +---+
> + *                           index last
> + * Case 2:
> + *                       r_min   r_max/end_piv
> + *                 +-------+-------+
> + * original range: |       |offset |
> + *                 +-------+-------+
> + *                         +---+
> + *      overwrite:         |   |
> + *                         +---+
> + *                       index last
> + */
>  static inline bool mas_wr_append(struct ma_wr_state *wr_mas)
>  {
>  	unsigned char end = wr_mas->node_end;
> @@ -4322,7 +4347,11 @@ static inline bool mas_wr_append(struct ma_wr_state *wr_mas)
>  	struct ma_state *mas = wr_mas->mas;
>  	unsigned char node_pivots = mt_pivots[wr_mas->type];
>  
> +	if (!(mas->offset == wr_mas->node_end))
> +		return false;
> +
>  	if ((mas->index != wr_mas->r_min) && (mas->last == wr_mas->r_max)) {
> +		/* Case 1 */
>  		if (new_end < node_pivots)
>  			wr_mas->pivots[new_end] = wr_mas->pivots[end];
>  
> @@ -4330,13 +4359,10 @@ static inline bool mas_wr_append(struct ma_wr_state *wr_mas)
>  			ma_set_meta(wr_mas->node, maple_leaf_64, 0, new_end);
>  
>  		rcu_assign_pointer(wr_mas->slots[new_end], wr_mas->entry);
> -		mas->offset = new_end;
>  		wr_mas->pivots[end] = mas->index - 1;
> -
> -		return true;
> -	}
> -
> -	if ((mas->index == wr_mas->r_min) && (mas->last < wr_mas->r_max)) {
> +		mas->offset = new_end;
> +	} else if ((mas->index == wr_mas->r_min) && (mas->last < wr_mas->r_max)) {
> +		/* Case 2 */
>  		if (new_end < node_pivots)
>  			wr_mas->pivots[new_end] = wr_mas->pivots[end];
>  
> @@ -4346,10 +4372,13 @@ static inline bool mas_wr_append(struct ma_wr_state *wr_mas)
>  
>  		wr_mas->pivots[end] = mas->last;
>  		rcu_assign_pointer(wr_mas->slots[end], wr_mas->entry);
> -		return true;
> +	} else {
> +		return false;
>  	}
>  
> -	return false;
> +	if (!wr_mas->content || !wr_mas->entry)
> +		mas_update_gap(mas);
> +	return  true;
>  }
>  
>  /*
> @@ -4385,12 +4414,9 @@ static inline void mas_wr_modify(struct ma_wr_state *wr_mas)
>  	if (new_end >= mt_slots[wr_mas->type])
>  		goto slow_path;
>  
> -	if (wr_mas->entry && (wr_mas->node_end < mt_slots[wr_mas->type] - 1) &&
> -	    (mas->offset == wr_mas->node_end) && mas_wr_append(wr_mas)) {
> -		if (!wr_mas->content || !wr_mas->entry)
> -			mas_update_gap(mas);
> +	/* Attempt to append */
> +	if (new_end == wr_mas->node_end + 1 && mas_wr_append(wr_mas))
>  		return;
> -	}
>  
>  	if ((wr_mas->offset_end - mas->offset <= 1) && mas_wr_slot_store(wr_mas))
>  		return;
> -- 
> 2.20.1
> 

Re: [PATCH 02/10] maple_tree: Drop mtree_alloc_{range,rrange}() and related functions.

[Liam R. Howlett]

* Matthew Wilcox <willy@infradead.org> [230515 13:27]:
> On Mon, May 15, 2023 at 09:17:49PM +0800, Peng Zhang wrote:
> > Drop mtree_alloc_{range,rrange}(), mas_{rev_}alloc() and mas_fill_gap().
> > mtree_alloc_{range,rrange}() currently have no users and can be easily
> > implemented with mas_empty_area{_rev}(). mas_{rev_}alloc() and
> > mas_fill_gap() are just their internal functions, drop them together.
> 
> No, I think this is the wrong way to go.
> 
> Most users should not be using the mas_* API.  These are the advanced
> APIs.  Most users will want to use mtree_alloc_range().  Just like most
> users of the XArray use the xa_insert() API rather than open-coding the
> xa_state and calling the xas_* APIs.
> 
> Please read Documentation/core-api/xarray.rst and maple_tree.rst for more
> details on Normal vs Advanced API.  The real problem is that we have so
> few users today, so you haven't seen that most people don't want to use
> the advanced APIs.


Peng, Apologies on the confusion.  Please do as Matthew said.  If you
have a way to unify the functionality to use the same internal
functions, then I think that would be a welcome change.

Re: [PATCH 09/10] maple_tree: Rework mas_wr_slot_store() to be cleaner and more efficient.

[Liam R. Howlett]

* Peng Zhang <zhangpeng.00@bytedance.com> [230515 09:18]:
> The code of mas_wr_slot_store() is messy, make it clearer and concise,
> and add comments. In addition, get whether the two gaps are empty to
> avoid calling mas_update_gap() all the time.

Please drop the cases from the comments.  These aren't that complicated
to need diagrams.

Case 1: Overwriting the range and over a part of the next range
Case 2: Overwriting a part of the range and over the entire next range

> 
> Signed-off-by: Peng Zhang <zhangpeng.00@bytedance.com>
> ---
>  lib/maple_tree.c | 79 +++++++++++++++++++++++++++---------------------
>  1 file changed, 44 insertions(+), 35 deletions(-)
> 
> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> index 538e49feafbe4..d558e7bcb6da8 100644
> --- a/lib/maple_tree.c
> +++ b/lib/maple_tree.c
> @@ -4190,53 +4190,62 @@ static inline bool mas_wr_node_store(struct ma_wr_state *wr_mas)
>   * @wr_mas: the maple write state
>   *
>   * Return: True if stored, false otherwise
> + *
> + * Case 1:
> + *                       r_min   r_max    lmax
> + *                 +-------+-------+-------+
> + * original range: |       |offset | end   |
> + *                 +-----------------------+
> + *                         +-----------+
> + * overwrite:              |           |
> + *                         +-----------+
> + *                        index       last
> + *
> + * Case 2:
> + *                       r_min   r_max    lmax
> + *                 +-------+-------+-------+
> + * original range: |       |offest | end   |
> + *                 +-------+---------------+
> + *                             +-----------+
> + * overwrite:                  |           |
> + *                             +-----------+
> + *                           index        last
>   */
>  static inline bool mas_wr_slot_store(struct ma_wr_state *wr_mas)
>  {
>  	struct ma_state *mas = wr_mas->mas;
> -	unsigned long lmax; /* Logical max. */
>  	unsigned char offset = mas->offset;
> +	unsigned char offset_end = wr_mas->offset_end;
> +	unsigned long lmax = wr_mas->end_piv; /* Logical max. */
> +	bool gap = false;
>  
> -	if ((wr_mas->r_max > mas->last) && ((wr_mas->r_min != mas->index) ||
> -				  (offset != wr_mas->node_end)))
> -		return false;
> -
> -	if (offset == wr_mas->node_end - 1)
> -		lmax = mas->max;
> -	else
> -		lmax = wr_mas->pivots[offset + 1];
> -
> -	/* going to overwrite too many slots. */
> -	if (lmax < mas->last)
> +	if (offset_end - offset != 1)
>  		return false;
>  
> -	if (wr_mas->r_min == mas->index) {
> -		/* overwriting two or more ranges with one. */
> -		if (lmax == mas->last)
> -			return false;
> -
> -		/* Overwriting all of offset and a portion of offset + 1. */
> +	if (mas->index == wr_mas->r_min && mas->last < lmax) {
> +		/* Case 1 */
> +		gap |= !mt_slot_locked(mas->tree, wr_mas->slots, offset);
> +		gap |= !mt_slot_locked(mas->tree, wr_mas->slots, offset + 1);
>  		rcu_assign_pointer(wr_mas->slots[offset], wr_mas->entry);
>  		wr_mas->pivots[offset] = mas->last;
> -		goto done;
> -	}
> -
> -	/* Doesn't end on the next range end. */
> -	if (lmax != mas->last)
> +	} else if (mas->index > wr_mas->r_min && mas->last == lmax) {
> +		/* Case 2 */
> +		gap |= !mt_slot_locked(mas->tree, wr_mas->slots, offset);
> +		gap |= !mt_slot_locked(mas->tree, wr_mas->slots, offset + 1);
> +		rcu_assign_pointer(wr_mas->slots[offset + 1], wr_mas->entry);
> +		wr_mas->pivots[offset] = mas->index - 1;

These two lines need to be in opposite order to ensure a reader sees
either the value or the previous value.  If you overwrite something with
a new value, it is possible that a reader looking for the next range
will get the value stored at offset (but not entry).

> +		mas->offset++; /* Keep mas accurate. */
> +	} else {
>  		return false;
> +	}
>  
> -	/* Overwriting a portion of offset and all of offset + 1 */
> -	if ((offset + 1 < mt_pivots[wr_mas->type]) &&
> -	    (wr_mas->entry || wr_mas->pivots[offset + 1]))
> -		wr_mas->pivots[offset + 1] = mas->last;
> -
> -	rcu_assign_pointer(wr_mas->slots[offset + 1], wr_mas->entry);
> -	wr_mas->pivots[offset] = mas->index - 1;
> -	mas->offset++; /* Keep mas accurate. */
> -
> -done:
>  	trace_ma_write(__func__, mas, 0, wr_mas->entry);
> -	mas_update_gap(mas);
> +	/*
> +	 * Only update gap when the new entry is empty or there is an empty
> +	 * entry in the original two ranges.
> +	 */
> +	if (!wr_mas->entry || gap)
> +		mas_update_gap(mas);
>  	return true;
>  }
>  
> @@ -4418,7 +4427,7 @@ static inline void mas_wr_modify(struct ma_wr_state *wr_mas)
>  	if (new_end == wr_mas->node_end + 1 && mas_wr_append(wr_mas))
>  		return;
>  
> -	if ((wr_mas->offset_end - mas->offset <= 1) && mas_wr_slot_store(wr_mas))
> +	if (new_end == wr_mas->node_end && mas_wr_slot_store(wr_mas))
>  		return;
>  	else if (mas_wr_node_store(wr_mas))
>  		return;
> -- 
> 2.20.1
> 

Re: [PATCH 10/10] maple_tree: Simplify and clean up mas_wr_node_store()

[Liam R. Howlett]

* Peng Zhang <zhangpeng.00@bytedance.com> [230515 09:18]:
> Simplify and clean up mas_wr_node_store(), remove unnecessary code.

This change fails the userspace testing for me.

> 
> Signed-off-by: Peng Zhang <zhangpeng.00@bytedance.com>
> ---
>  lib/maple_tree.c | 75 +++++++++++++-----------------------------------
>  1 file changed, 20 insertions(+), 55 deletions(-)
> 
> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> index d558e7bcb6da8..ff4aa01cf88b6 100644
> --- a/lib/maple_tree.c
> +++ b/lib/maple_tree.c
> @@ -4066,46 +4066,21 @@ static inline int mas_wr_spanning_store(struct ma_wr_state *wr_mas)
>   *
>   * Return: True if stored, false otherwise
>   */
> -static inline bool mas_wr_node_store(struct ma_wr_state *wr_mas)
> +static inline bool mas_wr_node_store(struct ma_wr_state *wr_mas,
> +				     unsigned char new_end)
>  {
>  	struct ma_state *mas = wr_mas->mas;
>  	void __rcu **dst_slots;
>  	unsigned long *dst_pivots;
>  	unsigned char dst_offset;
> -	unsigned char new_end = wr_mas->node_end;
> -	unsigned char offset;
> -	unsigned char node_slots = mt_slots[wr_mas->type];
>  	struct maple_node reuse, *newnode;
> -	unsigned char copy_size, max_piv = mt_pivots[wr_mas->type];
> +	unsigned char copy_size, node_pivots = mt_pivots[wr_mas->type];
>  	bool in_rcu = mt_in_rcu(mas->tree);
>  
> -	offset = mas->offset;
> -	if (mas->last == wr_mas->r_max) {
> -		/* runs right to the end of the node */
> -		if (mas->last == mas->max)
> -			new_end = offset;
> -		/* don't copy this offset */
> +	if (mas->last == wr_mas->end_piv)
>  		wr_mas->offset_end++;
> -	} else if (mas->last < wr_mas->r_max) {
> -		/* new range ends in this range */
> -		if (unlikely(wr_mas->r_max == ULONG_MAX))
> -			mas_bulk_rebalance(mas, wr_mas->node_end, wr_mas->type);
> -
> -		new_end++;
> -	} else {
> -		if (wr_mas->end_piv == mas->last)
> -			wr_mas->offset_end++;
> -
> -		new_end -= wr_mas->offset_end - offset - 1;
> -	}
> -
> -	/* new range starts within a range */
> -	if (wr_mas->r_min < mas->index)
> -		new_end++;
> -
> -	/* Not enough room */
> -	if (new_end >= node_slots)
> -		return false;
> +	else if (unlikely(wr_mas->r_max == ULONG_MAX))
> +		mas_bulk_rebalance(mas, wr_mas->node_end, wr_mas->type);
>  
>  	/* Not enough data. */
>  	if (!mte_is_root(mas->node) && (new_end <= mt_min_slots[wr_mas->type]) &&
> @@ -4128,47 +4103,36 @@ static inline bool mas_wr_node_store(struct ma_wr_state *wr_mas)
>  	dst_pivots = ma_pivots(newnode, wr_mas->type);
>  	dst_slots = ma_slots(newnode, wr_mas->type);
>  	/* Copy from start to insert point */
> -	memcpy(dst_pivots, wr_mas->pivots, sizeof(unsigned long) * (offset + 1));
> -	memcpy(dst_slots, wr_mas->slots, sizeof(void *) * (offset + 1));
> -	dst_offset = offset;
> +	memcpy(dst_pivots, wr_mas->pivots, sizeof(unsigned long) * mas->offset);
> +	memcpy(dst_slots, wr_mas->slots, sizeof(void *) * mas->offset);
>  
>  	/* Handle insert of new range starting after old range */
>  	if (wr_mas->r_min < mas->index) {
> -		mas->offset++;
> -		rcu_assign_pointer(dst_slots[dst_offset], wr_mas->content);
> -		dst_pivots[dst_offset++] = mas->index - 1;
> +		rcu_assign_pointer(dst_slots[mas->offset], wr_mas->content);
> +		dst_pivots[mas->offset++] = mas->index - 1;
>  	}
>  
>  	/* Store the new entry and range end. */
> -	if (dst_offset < max_piv)
> -		dst_pivots[dst_offset] = mas->last;
> -	mas->offset = dst_offset;
> -	rcu_assign_pointer(dst_slots[dst_offset], wr_mas->entry);
> +	if (mas->offset < node_pivots)
> +		dst_pivots[mas->offset] = mas->last;
> +	rcu_assign_pointer(dst_slots[mas->offset], wr_mas->entry);
>  
>  	/*
>  	 * this range wrote to the end of the node or it overwrote the rest of
>  	 * the data
>  	 */
> -	if (wr_mas->offset_end > wr_mas->node_end || mas->last >= mas->max) {
> -		new_end = dst_offset;
> +	if (wr_mas->offset_end > wr_mas->node_end)
>  		goto done;
> -	}
>  
> -	dst_offset++;
> +	dst_offset = mas->offset + 1;
>  	/* Copy to the end of node if necessary. */
>  	copy_size = wr_mas->node_end - wr_mas->offset_end + 1;
>  	memcpy(dst_slots + dst_offset, wr_mas->slots + wr_mas->offset_end,
>  	       sizeof(void *) * copy_size);
> -	if (dst_offset < max_piv) {
> -		if (copy_size > max_piv - dst_offset)
> -			copy_size = max_piv - dst_offset;
> +	memcpy(dst_pivots + dst_offset, wr_mas->pivots + wr_mas->offset_end,
> +	       sizeof(unsigned long) * (copy_size - 1));
>  
> -		memcpy(dst_pivots + dst_offset,
> -		       wr_mas->pivots + wr_mas->offset_end,
> -		       sizeof(unsigned long) * copy_size);
> -	}
> -
> -	if ((wr_mas->node_end == node_slots - 1) && (new_end < node_slots - 1))
> +	if (new_end < node_pivots)
>  		dst_pivots[new_end] = mas->max;
>  
>  done:
> @@ -4429,7 +4393,8 @@ static inline void mas_wr_modify(struct ma_wr_state *wr_mas)
>  
>  	if (new_end == wr_mas->node_end && mas_wr_slot_store(wr_mas))
>  		return;
> -	else if (mas_wr_node_store(wr_mas))
> +
> +	if (mas_wr_node_store(wr_mas, new_end))
>  		return;
>  
>  	if (mas_is_err(mas))
> -- 
> 2.20.1
> 

Re: [PATCH 10/10] maple_tree: Simplify and clean up mas_wr_node_store()

[Peng Zhang]

在 2023/5/16 02:58, Liam R. Howlett 写道:
> * Peng Zhang <zhangpeng.00@bytedance.com> [230515 09:18]:
>> Simplify and clean up mas_wr_node_store(), remove unnecessary code.
> 
> This change fails the userspace testing for me.
Can you tell which commit this patchset is based on when you run
userspace testing? I'll have a look.
> 
>>
>> Signed-off-by: Peng Zhang <zhangpeng.00@bytedance.com>
>> ---
>>   lib/maple_tree.c | 75 +++++++++++++-----------------------------------
>>   1 file changed, 20 insertions(+), 55 deletions(-)
>>
>> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
>> index d558e7bcb6da8..ff4aa01cf88b6 100644
>> --- a/lib/maple_tree.c
>> +++ b/lib/maple_tree.c
>> @@ -4066,46 +4066,21 @@ static inline int mas_wr_spanning_store(struct ma_wr_state *wr_mas)
>>    *
>>    * Return: True if stored, false otherwise
>>    */
>> -static inline bool mas_wr_node_store(struct ma_wr_state *wr_mas)
>> +static inline bool mas_wr_node_store(struct ma_wr_state *wr_mas,
>> +				     unsigned char new_end)
>>   {
>>   	struct ma_state *mas = wr_mas->mas;
>>   	void __rcu **dst_slots;
>>   	unsigned long *dst_pivots;
>>   	unsigned char dst_offset;
>> -	unsigned char new_end = wr_mas->node_end;
>> -	unsigned char offset;
>> -	unsigned char node_slots = mt_slots[wr_mas->type];
>>   	struct maple_node reuse, *newnode;
>> -	unsigned char copy_size, max_piv = mt_pivots[wr_mas->type];
>> +	unsigned char copy_size, node_pivots = mt_pivots[wr_mas->type];
>>   	bool in_rcu = mt_in_rcu(mas->tree);
>>   
>> -	offset = mas->offset;
>> -	if (mas->last == wr_mas->r_max) {
>> -		/* runs right to the end of the node */
>> -		if (mas->last == mas->max)
>> -			new_end = offset;
>> -		/* don't copy this offset */
>> +	if (mas->last == wr_mas->end_piv)
>>   		wr_mas->offset_end++;
>> -	} else if (mas->last < wr_mas->r_max) {
>> -		/* new range ends in this range */
>> -		if (unlikely(wr_mas->r_max == ULONG_MAX))
>> -			mas_bulk_rebalance(mas, wr_mas->node_end, wr_mas->type);
>> -
>> -		new_end++;
>> -	} else {
>> -		if (wr_mas->end_piv == mas->last)
>> -			wr_mas->offset_end++;
>> -
>> -		new_end -= wr_mas->offset_end - offset - 1;
>> -	}
>> -
>> -	/* new range starts within a range */
>> -	if (wr_mas->r_min < mas->index)
>> -		new_end++;
>> -
>> -	/* Not enough room */
>> -	if (new_end >= node_slots)
>> -		return false;
>> +	else if (unlikely(wr_mas->r_max == ULONG_MAX))
>> +		mas_bulk_rebalance(mas, wr_mas->node_end, wr_mas->type);
>>   
>>   	/* Not enough data. */
>>   	if (!mte_is_root(mas->node) && (new_end <= mt_min_slots[wr_mas->type]) &&
>> @@ -4128,47 +4103,36 @@ static inline bool mas_wr_node_store(struct ma_wr_state *wr_mas)
>>   	dst_pivots = ma_pivots(newnode, wr_mas->type);
>>   	dst_slots = ma_slots(newnode, wr_mas->type);
>>   	/* Copy from start to insert point */
>> -	memcpy(dst_pivots, wr_mas->pivots, sizeof(unsigned long) * (offset + 1));
>> -	memcpy(dst_slots, wr_mas->slots, sizeof(void *) * (offset + 1));
>> -	dst_offset = offset;
>> +	memcpy(dst_pivots, wr_mas->pivots, sizeof(unsigned long) * mas->offset);
>> +	memcpy(dst_slots, wr_mas->slots, sizeof(void *) * mas->offset);
>>   
>>   	/* Handle insert of new range starting after old range */
>>   	if (wr_mas->r_min < mas->index) {
>> -		mas->offset++;
>> -		rcu_assign_pointer(dst_slots[dst_offset], wr_mas->content);
>> -		dst_pivots[dst_offset++] = mas->index - 1;
>> +		rcu_assign_pointer(dst_slots[mas->offset], wr_mas->content);
>> +		dst_pivots[mas->offset++] = mas->index - 1;
>>   	}
>>   
>>   	/* Store the new entry and range end. */
>> -	if (dst_offset < max_piv)
>> -		dst_pivots[dst_offset] = mas->last;
>> -	mas->offset = dst_offset;
>> -	rcu_assign_pointer(dst_slots[dst_offset], wr_mas->entry);
>> +	if (mas->offset < node_pivots)
>> +		dst_pivots[mas->offset] = mas->last;
>> +	rcu_assign_pointer(dst_slots[mas->offset], wr_mas->entry);
>>   
>>   	/*
>>   	 * this range wrote to the end of the node or it overwrote the rest of
>>   	 * the data
>>   	 */
>> -	if (wr_mas->offset_end > wr_mas->node_end || mas->last >= mas->max) {
>> -		new_end = dst_offset;
>> +	if (wr_mas->offset_end > wr_mas->node_end)
>>   		goto done;
>> -	}
>>   
>> -	dst_offset++;
>> +	dst_offset = mas->offset + 1;
>>   	/* Copy to the end of node if necessary. */
>>   	copy_size = wr_mas->node_end - wr_mas->offset_end + 1;
>>   	memcpy(dst_slots + dst_offset, wr_mas->slots + wr_mas->offset_end,
>>   	       sizeof(void *) * copy_size);
>> -	if (dst_offset < max_piv) {
>> -		if (copy_size > max_piv - dst_offset)
>> -			copy_size = max_piv - dst_offset;
>> +	memcpy(dst_pivots + dst_offset, wr_mas->pivots + wr_mas->offset_end,
>> +	       sizeof(unsigned long) * (copy_size - 1));
>>   
>> -		memcpy(dst_pivots + dst_offset,
>> -		       wr_mas->pivots + wr_mas->offset_end,
>> -		       sizeof(unsigned long) * copy_size);
>> -	}
>> -
>> -	if ((wr_mas->node_end == node_slots - 1) && (new_end < node_slots - 1))
>> +	if (new_end < node_pivots)
>>   		dst_pivots[new_end] = mas->max;
>>   
>>   done:
>> @@ -4429,7 +4393,8 @@ static inline void mas_wr_modify(struct ma_wr_state *wr_mas)
>>   
>>   	if (new_end == wr_mas->node_end && mas_wr_slot_store(wr_mas))
>>   		return;
>> -	else if (mas_wr_node_store(wr_mas))
>> +
>> +	if (mas_wr_node_store(wr_mas, new_end))
>>   		return;
>>   
>>   	if (mas_is_err(mas))
>> -- 
>> 2.20.1
>>

Re: [PATCH 02/10] maple_tree: Drop mtree_alloc_{range,rrange}() and related functions.

[Peng Zhang]

在 2023/5/16 01:35, Liam R. Howlett 写道:
> * Matthew Wilcox <willy@infradead.org> [230515 13:27]:
>> On Mon, May 15, 2023 at 09:17:49PM +0800, Peng Zhang wrote:
>>> Drop mtree_alloc_{range,rrange}(), mas_{rev_}alloc() and mas_fill_gap().
>>> mtree_alloc_{range,rrange}() currently have no users and can be easily
>>> implemented with mas_empty_area{_rev}(). mas_{rev_}alloc() and
>>> mas_fill_gap() are just their internal functions, drop them together.
>>
>> No, I think this is the wrong way to go.
>>
>> Most users should not be using the mas_* API.  These are the advanced
>> APIs.  Most users will want to use mtree_alloc_range().  Just like most
>> users of the XArray use the xa_insert() API rather than open-coding the
>> xa_state and calling the xas_* APIs.
>>
>> Please read Documentation/core-api/xarray.rst and maple_tree.rst for more
>> details on Normal vs Advanced API.  The real problem is that we have so
>> few users today, so you haven't seen that most people don't want to use
>> the advanced APIs.
> 
> 
> Peng, Apologies on the confusion.  Please do as Matthew said.  If you
> have a way to unify the functionality to use the same internal
> functions, then I think that would be a welcome change.
> 
I will implement new mtree_alloc_{range,rrange}() using other internal 
functions.

Re: [PATCH 03/10] maple_tree: Remove __must_hold() which does not work

[Peng Zhang]

在 2023/5/15 22:55, Matthew Wilcox 写道:
> On Mon, May 15, 2023 at 09:17:50PM +0800, Peng Zhang wrote:
>> The arguments to __must_hold() seem to be wrong so they should not work,
>> remove them.
> 
> Why not fix them?
I'll fix it in v2.

Re: [PATCH 06/10] maple_tree: Wrap the replace operation with an inline function.

[Peng Zhang]

在 2023/5/16 01:07, Liam R. Howlett 写道:
> * Peng Zhang <zhangpeng.00@bytedance.com> [230515 09:18]:
>> To make mas_wr_modify() cleaner, wrap the replace operation with an
>> inline function.
> 
> mas_wr_modify() is already pretty small.  Is there any reason you want
> this in its own function besides it looking cleaner?
I just want to make the four fast paths in mas_wr_modify()
look uniform without any functional effect.
> 
>>
>> Signed-off-by: Peng Zhang <zhangpeng.00@bytedance.com>
>> ---
>>   lib/maple_tree.c | 21 +++++++++++++++------
>>   1 file changed, 15 insertions(+), 6 deletions(-)
>>
>> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
>> index 4c649d75a4923..ce695adc670ec 100644
>> --- a/lib/maple_tree.c
>> +++ b/lib/maple_tree.c
>> @@ -4288,6 +4288,19 @@ static inline void mas_wr_extend_null(struct ma_wr_state *wr_mas)
>>   	}
>>   }
>>   
>> +static inline bool mas_wr_replace(struct ma_wr_state *wr_mas)
>> +{
>> +	struct ma_state *mas = wr_mas->mas;
>> +
>> +	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 true;
>> +	}
>> +	return false;
>> +}
>> +
>>   static inline bool mas_wr_append(struct ma_wr_state *wr_mas)
>>   {
>>   	unsigned char end = wr_mas->node_end;
>> @@ -4347,13 +4360,9 @@ static inline void mas_wr_modify(struct ma_wr_state *wr_mas)
>>   	unsigned char node_size;
>>   	struct ma_state *mas = wr_mas->mas;
>>   
>> -	/* 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);
>> +	/* Attempt to direct replace */
>> +	if (mas_wr_replace(wr_mas))
>>   		return;
>> -	}
>>   
>>   	/* Attempt to append */
>>   	node_slots = mt_slots[wr_mas->type];
>> -- 
>> 2.20.1
>>

Re: [PATCH 09/10] maple_tree: Rework mas_wr_slot_store() to be cleaner and more efficient.

[Peng Zhang]

在 2023/5/16 02:01, Liam R. Howlett 写道:
> * Peng Zhang <zhangpeng.00@bytedance.com> [230515 09:18]:
>> The code of mas_wr_slot_store() is messy, make it clearer and concise,
>> and add comments. In addition, get whether the two gaps are empty to
>> avoid calling mas_update_gap() all the time.
> 
> Please drop the cases from the comments.  These aren't that complicated
> to need diagrams.
> 
> Case 1: Overwriting the range and over a part of the next range
> Case 2: Overwriting a part of the range and over the entire next range
> 
>>
>> Signed-off-by: Peng Zhang <zhangpeng.00@bytedance.com>
>> ---
>>   lib/maple_tree.c | 79 +++++++++++++++++++++++++++---------------------
>>   1 file changed, 44 insertions(+), 35 deletions(-)
>>
>> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
>> index 538e49feafbe4..d558e7bcb6da8 100644
>> --- a/lib/maple_tree.c
>> +++ b/lib/maple_tree.c
>> @@ -4190,53 +4190,62 @@ static inline bool mas_wr_node_store(struct ma_wr_state *wr_mas)
>>    * @wr_mas: the maple write state
>>    *
>>    * Return: True if stored, false otherwise
>> + *
>> + * Case 1:
>> + *                       r_min   r_max    lmax
>> + *                 +-------+-------+-------+
>> + * original range: |       |offset | end   |
>> + *                 +-----------------------+
>> + *                         +-----------+
>> + * overwrite:              |           |
>> + *                         +-----------+
>> + *                        index       last
>> + *
>> + * Case 2:
>> + *                       r_min   r_max    lmax
>> + *                 +-------+-------+-------+
>> + * original range: |       |offest | end   |
>> + *                 +-------+---------------+
>> + *                             +-----------+
>> + * overwrite:                  |           |
>> + *                             +-----------+
>> + *                           index        last
>>    */
>>   static inline bool mas_wr_slot_store(struct ma_wr_state *wr_mas)
>>   {
>>   	struct ma_state *mas = wr_mas->mas;
>> -	unsigned long lmax; /* Logical max. */
>>   	unsigned char offset = mas->offset;
>> +	unsigned char offset_end = wr_mas->offset_end;
>> +	unsigned long lmax = wr_mas->end_piv; /* Logical max. */
>> +	bool gap = false;
>>   
>> -	if ((wr_mas->r_max > mas->last) && ((wr_mas->r_min != mas->index) ||
>> -				  (offset != wr_mas->node_end)))
>> -		return false;
>> -
>> -	if (offset == wr_mas->node_end - 1)
>> -		lmax = mas->max;
>> -	else
>> -		lmax = wr_mas->pivots[offset + 1];
>> -
>> -	/* going to overwrite too many slots. */
>> -	if (lmax < mas->last)
>> +	if (offset_end - offset != 1)
>>   		return false;
>>   
>> -	if (wr_mas->r_min == mas->index) {
>> -		/* overwriting two or more ranges with one. */
>> -		if (lmax == mas->last)
>> -			return false;
>> -
>> -		/* Overwriting all of offset and a portion of offset + 1. */
>> +	if (mas->index == wr_mas->r_min && mas->last < lmax) {
>> +		/* Case 1 */
>> +		gap |= !mt_slot_locked(mas->tree, wr_mas->slots, offset);
>> +		gap |= !mt_slot_locked(mas->tree, wr_mas->slots, offset + 1);
>>   		rcu_assign_pointer(wr_mas->slots[offset], wr_mas->entry);
>>   		wr_mas->pivots[offset] = mas->last;
>> -		goto done;
>> -	}
>> -
>> -	/* Doesn't end on the next range end. */
>> -	if (lmax != mas->last)
>> +	} else if (mas->index > wr_mas->r_min && mas->last == lmax) {
>> +		/* Case 2 */
>> +		gap |= !mt_slot_locked(mas->tree, wr_mas->slots, offset);
>> +		gap |= !mt_slot_locked(mas->tree, wr_mas->slots, offset + 1);
>> +		rcu_assign_pointer(wr_mas->slots[offset + 1], wr_mas->entry);
>> +		wr_mas->pivots[offset] = mas->index - 1;
> 
> These two lines need to be in opposite order to ensure a reader sees
> either the value or the previous value.  If you overwrite something with
> a new value, it is possible that a reader looking for the next range
> will get the value stored at offset (but not entry).
Please think again, did you think wrong?
It doesn't happen, swapping the order introduces the problem.
If we update the pivot first, it will cause a part of the value
of the range indexed by offset to change to the value of the
range indexed by offset+1, which is illegal.

My assignment order remains the same as the previous version.

> 
>> +		mas->offset++; /* Keep mas accurate. */
>> +	} else {
>>   		return false;
>> +	}
>>   
>> -	/* Overwriting a portion of offset and all of offset + 1 */
>> -	if ((offset + 1 < mt_pivots[wr_mas->type]) &&
>> -	    (wr_mas->entry || wr_mas->pivots[offset + 1]))
>> -		wr_mas->pivots[offset + 1] = mas->last;
>> -
>> -	rcu_assign_pointer(wr_mas->slots[offset + 1], wr_mas->entry);
>> -	wr_mas->pivots[offset] = mas->index - 1;
>> -	mas->offset++; /* Keep mas accurate. */
>> -
>> -done:
>>   	trace_ma_write(__func__, mas, 0, wr_mas->entry);
>> -	mas_update_gap(mas);
>> +	/*
>> +	 * Only update gap when the new entry is empty or there is an empty
>> +	 * entry in the original two ranges.
>> +	 */
>> +	if (!wr_mas->entry || gap)
>> +		mas_update_gap(mas);
>>   	return true;
>>   }
>>   
>> @@ -4418,7 +4427,7 @@ static inline void mas_wr_modify(struct ma_wr_state *wr_mas)
>>   	if (new_end == wr_mas->node_end + 1 && mas_wr_append(wr_mas))
>>   		return;
>>   
>> -	if ((wr_mas->offset_end - mas->offset <= 1) && mas_wr_slot_store(wr_mas))
>> +	if (new_end == wr_mas->node_end && mas_wr_slot_store(wr_mas))
>>   		return;
>>   	else if (mas_wr_node_store(wr_mas))
>>   		return;
>> -- 
>> 2.20.1
>>
> 

Re: [PATCH 08/10] maple_tree: Add comments and some minor cleanups to mas_wr_append()

[Peng Zhang]

在 2023/5/16 01:29, Liam R. Howlett 写道:
> * Peng Zhang <zhangpeng.00@bytedance.com> [230515 09:18]:
>> Add comment for mas_wr_append(), move mas_update_gap() into
>> mas_wr_append(), and other cleanups to make mas_wr_modify() cleaner.
> 
> Sorry, no.
> 
> I won't accept cases in the comments and referencing it in the code.
> I'm not making any vma_adjust() or vma_merge()-like comment blocks.
> 
> Please change Case 1/2 to "Append to start of range"/"Append to end of
> range"
> 
> This path leads to chaos.
I'll remove these comments in v2.
> 
>>
>> Signed-off-by: Peng Zhang <zhangpeng.00@bytedance.com>
>> ---
>>   lib/maple_tree.c | 52 ++++++++++++++++++++++++++++++++++++------------
>>   1 file changed, 39 insertions(+), 13 deletions(-)
>>
>> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
>> index 20082ef8c396c..538e49feafbe4 100644
>> --- a/lib/maple_tree.c
>> +++ b/lib/maple_tree.c
>> @@ -4315,6 +4315,31 @@ static inline unsigned char mas_wr_new_end(struct ma_wr_state *wr_mas)
>>   	return new_end;
>>   }
>>   
>> +/*
>> + * mas_wr_append: Attempt to append
>> + * @wr_mas: the maple write state
>> + *
>> + * Return: True if appended, false otherwise
>> + *
>> + * Case 1:
>> + *                       r_min   r_max/end_piv
>> + *                 +-------+-------+
>> + * original range: |       |offset |
>> + *                 +-------+-------+
>> + *                             +---+
>> + *      overwrite:             |   |
>> + *                             +---+
>> + *                           index last
>> + * Case 2:
>> + *                       r_min   r_max/end_piv
>> + *                 +-------+-------+
>> + * original range: |       |offset |
>> + *                 +-------+-------+
>> + *                         +---+
>> + *      overwrite:         |   |
>> + *                         +---+
>> + *                       index last
>> + */
>>   static inline bool mas_wr_append(struct ma_wr_state *wr_mas)
>>   {
>>   	unsigned char end = wr_mas->node_end;
>> @@ -4322,7 +4347,11 @@ static inline bool mas_wr_append(struct ma_wr_state *wr_mas)
>>   	struct ma_state *mas = wr_mas->mas;
>>   	unsigned char node_pivots = mt_pivots[wr_mas->type];
>>   
>> +	if (!(mas->offset == wr_mas->node_end))
>> +		return false;
>> +
>>   	if ((mas->index != wr_mas->r_min) && (mas->last == wr_mas->r_max)) {
>> +		/* Case 1 */
>>   		if (new_end < node_pivots)
>>   			wr_mas->pivots[new_end] = wr_mas->pivots[end];
>>   
>> @@ -4330,13 +4359,10 @@ static inline bool mas_wr_append(struct ma_wr_state *wr_mas)
>>   			ma_set_meta(wr_mas->node, maple_leaf_64, 0, new_end);
>>   
>>   		rcu_assign_pointer(wr_mas->slots[new_end], wr_mas->entry);
>> -		mas->offset = new_end;
>>   		wr_mas->pivots[end] = mas->index - 1;
>> -
>> -		return true;
>> -	}
>> -
>> -	if ((mas->index == wr_mas->r_min) && (mas->last < wr_mas->r_max)) {
>> +		mas->offset = new_end;
>> +	} else if ((mas->index == wr_mas->r_min) && (mas->last < wr_mas->r_max)) {
>> +		/* Case 2 */
>>   		if (new_end < node_pivots)
>>   			wr_mas->pivots[new_end] = wr_mas->pivots[end];
>>   
>> @@ -4346,10 +4372,13 @@ static inline bool mas_wr_append(struct ma_wr_state *wr_mas)
>>   
>>   		wr_mas->pivots[end] = mas->last;
>>   		rcu_assign_pointer(wr_mas->slots[end], wr_mas->entry);
>> -		return true;
>> +	} else {
>> +		return false;
>>   	}
>>   
>> -	return false;
>> +	if (!wr_mas->content || !wr_mas->entry)
>> +		mas_update_gap(mas);
>> +	return  true;
>>   }
>>   
>>   /*
>> @@ -4385,12 +4414,9 @@ static inline void mas_wr_modify(struct ma_wr_state *wr_mas)
>>   	if (new_end >= mt_slots[wr_mas->type])
>>   		goto slow_path;
>>   
>> -	if (wr_mas->entry && (wr_mas->node_end < mt_slots[wr_mas->type] - 1) &&
>> -	    (mas->offset == wr_mas->node_end) && mas_wr_append(wr_mas)) {
>> -		if (!wr_mas->content || !wr_mas->entry)
>> -			mas_update_gap(mas);
>> +	/* Attempt to append */
>> +	if (new_end == wr_mas->node_end + 1 && mas_wr_append(wr_mas))
>>   		return;
>> -	}
>>   
>>   	if ((wr_mas->offset_end - mas->offset <= 1) && mas_wr_slot_store(wr_mas))
>>   		return;
>> -- 
>> 2.20.1
>>
> 

Re: [PATCH 10/10] maple_tree: Simplify and clean up mas_wr_node_store()

[Peng Zhang]

在 2023/5/16 02:58, Liam R. Howlett 写道:
> * Peng Zhang <zhangpeng.00@bytedance.com> [230515 09:18]:
>> Simplify and clean up mas_wr_node_store(), remove unnecessary code.
> 
> This change fails the userspace testing for me.
> 
>>
>> Signed-off-by: Peng Zhang <zhangpeng.00@bytedance.com>
>> ---
>>   lib/maple_tree.c | 75 +++++++++++++-----------------------------------
>>   1 file changed, 20 insertions(+), 55 deletions(-)
>>
>> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
>> index d558e7bcb6da8..ff4aa01cf88b6 100644
>> --- a/lib/maple_tree.c
>> +++ b/lib/maple_tree.c
>> @@ -4066,46 +4066,21 @@ static inline int mas_wr_spanning_store(struct ma_wr_state *wr_mas)
>>    *
>>    * Return: True if stored, false otherwise
>>    */
>> -static inline bool mas_wr_node_store(struct ma_wr_state *wr_mas)
>> +static inline bool mas_wr_node_store(struct ma_wr_state *wr_mas,
>> +				     unsigned char new_end)
>>   {
>>   	struct ma_state *mas = wr_mas->mas;
>>   	void __rcu **dst_slots;
>>   	unsigned long *dst_pivots;
>>   	unsigned char dst_offset;
>> -	unsigned char new_end = wr_mas->node_end;
>> -	unsigned char offset;
>> -	unsigned char node_slots = mt_slots[wr_mas->type];
>>   	struct maple_node reuse, *newnode;
>> -	unsigned char copy_size, max_piv = mt_pivots[wr_mas->type];
>> +	unsigned char copy_size, node_pivots = mt_pivots[wr_mas->type];
>>   	bool in_rcu = mt_in_rcu(mas->tree);
>>   
>> -	offset = mas->offset;
>> -	if (mas->last == wr_mas->r_max) {
>> -		/* runs right to the end of the node */
>> -		if (mas->last == mas->max)
>> -			new_end = offset;
>> -		/* don't copy this offset */
>> +	if (mas->last == wr_mas->end_piv)
>>   		wr_mas->offset_end++;
I guess there is a problem here? If we modify wr_mas->offset_end,
but this function fails to try the fast path, it will enter the
slow path with the modified offset_end. But it also has this
problem in the previous version.

I applied this patch to linux-next/master but it passed the
userspace tests. I need more information to confirm what the
problem is.

Thanks.

>> -	} else if (mas->last < wr_mas->r_max) {
>> -		/* new range ends in this range */
>> -		if (unlikely(wr_mas->r_max == ULONG_MAX))
>> -			mas_bulk_rebalance(mas, wr_mas->node_end, wr_mas->type);
>> -
>> -		new_end++;
>> -	} else {
>> -		if (wr_mas->end_piv == mas->last)
>> -			wr_mas->offset_end++;
>> -
>> -		new_end -= wr_mas->offset_end - offset - 1;
>> -	}
>> -
>> -	/* new range starts within a range */
>> -	if (wr_mas->r_min < mas->index)
>> -		new_end++;
>> -
>> -	/* Not enough room */
>> -	if (new_end >= node_slots)
>> -		return false;
>> +	else if (unlikely(wr_mas->r_max == ULONG_MAX))
>> +		mas_bulk_rebalance(mas, wr_mas->node_end, wr_mas->type);
>>   
>>   	/* Not enough data. */
>>   	if (!mte_is_root(mas->node) && (new_end <= mt_min_slots[wr_mas->type]) &&
>> @@ -4128,47 +4103,36 @@ static inline bool mas_wr_node_store(struct ma_wr_state *wr_mas)
>>   	dst_pivots = ma_pivots(newnode, wr_mas->type);
>>   	dst_slots = ma_slots(newnode, wr_mas->type);
>>   	/* Copy from start to insert point */
>> -	memcpy(dst_pivots, wr_mas->pivots, sizeof(unsigned long) * (offset + 1));
>> -	memcpy(dst_slots, wr_mas->slots, sizeof(void *) * (offset + 1));
>> -	dst_offset = offset;
>> +	memcpy(dst_pivots, wr_mas->pivots, sizeof(unsigned long) * mas->offset);
>> +	memcpy(dst_slots, wr_mas->slots, sizeof(void *) * mas->offset);
>>   
>>   	/* Handle insert of new range starting after old range */
>>   	if (wr_mas->r_min < mas->index) {
>> -		mas->offset++;
>> -		rcu_assign_pointer(dst_slots[dst_offset], wr_mas->content);
>> -		dst_pivots[dst_offset++] = mas->index - 1;
>> +		rcu_assign_pointer(dst_slots[mas->offset], wr_mas->content);
>> +		dst_pivots[mas->offset++] = mas->index - 1;
>>   	}
>>   
>>   	/* Store the new entry and range end. */
>> -	if (dst_offset < max_piv)
>> -		dst_pivots[dst_offset] = mas->last;
>> -	mas->offset = dst_offset;
>> -	rcu_assign_pointer(dst_slots[dst_offset], wr_mas->entry);
>> +	if (mas->offset < node_pivots)
>> +		dst_pivots[mas->offset] = mas->last;
>> +	rcu_assign_pointer(dst_slots[mas->offset], wr_mas->entry);
>>   
>>   	/*
>>   	 * this range wrote to the end of the node or it overwrote the rest of
>>   	 * the data
>>   	 */
>> -	if (wr_mas->offset_end > wr_mas->node_end || mas->last >= mas->max) {
>> -		new_end = dst_offset;
>> +	if (wr_mas->offset_end > wr_mas->node_end)
>>   		goto done;
>> -	}
>>   
>> -	dst_offset++;
>> +	dst_offset = mas->offset + 1;
>>   	/* Copy to the end of node if necessary. */
>>   	copy_size = wr_mas->node_end - wr_mas->offset_end + 1;
>>   	memcpy(dst_slots + dst_offset, wr_mas->slots + wr_mas->offset_end,
>>   	       sizeof(void *) * copy_size);
>> -	if (dst_offset < max_piv) {
>> -		if (copy_size > max_piv - dst_offset)
>> -			copy_size = max_piv - dst_offset;
>> +	memcpy(dst_pivots + dst_offset, wr_mas->pivots + wr_mas->offset_end,
>> +	       sizeof(unsigned long) * (copy_size - 1));
>>   
>> -		memcpy(dst_pivots + dst_offset,
>> -		       wr_mas->pivots + wr_mas->offset_end,
>> -		       sizeof(unsigned long) * copy_size);
>> -	}
>> -
>> -	if ((wr_mas->node_end == node_slots - 1) && (new_end < node_slots - 1))
>> +	if (new_end < node_pivots)
>>   		dst_pivots[new_end] = mas->max;
>>   
>>   done:
>> @@ -4429,7 +4393,8 @@ static inline void mas_wr_modify(struct ma_wr_state *wr_mas)
>>   
>>   	if (new_end == wr_mas->node_end && mas_wr_slot_store(wr_mas))
>>   		return;
>> -	else if (mas_wr_node_store(wr_mas))
>> +
>> +	if (mas_wr_node_store(wr_mas, new_end))
>>   		return;
>>   
>>   	if (mas_is_err(mas))
>> -- 
>> 2.20.1
>>

Re: [PATCH 06/10] maple_tree: Wrap the replace operation with an inline function.

[Liam R. Howlett]

* Peng Zhang <zhangpeng.00@bytedance.com> [230515 20:46]:
> 
> 
> 在 2023/5/16 01:07, Liam R. Howlett 写道:
> > * Peng Zhang <zhangpeng.00@bytedance.com> [230515 09:18]:
> > > To make mas_wr_modify() cleaner, wrap the replace operation with an
> > > inline function.
> > 
> > mas_wr_modify() is already pretty small.  Is there any reason you want
> > this in its own function besides it looking cleaner?
> I just want to make the four fast paths in mas_wr_modify()
> look uniform without any functional effect.

I'd like to keep it the way it is. I think the comment stating what is
going on is clear enough and mas_wr_modify() isn't too big.

> > 
> > > 
> > > Signed-off-by: Peng Zhang <zhangpeng.00@bytedance.com>
> > > ---
> > >   lib/maple_tree.c | 21 +++++++++++++++------
> > >   1 file changed, 15 insertions(+), 6 deletions(-)
> > > 
> > > diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> > > index 4c649d75a4923..ce695adc670ec 100644
> > > --- a/lib/maple_tree.c
> > > +++ b/lib/maple_tree.c
> > > @@ -4288,6 +4288,19 @@ static inline void mas_wr_extend_null(struct ma_wr_state *wr_mas)
> > >   	}
> > >   }
> > > +static inline bool mas_wr_replace(struct ma_wr_state *wr_mas)
> > > +{
> > > +	struct ma_state *mas = wr_mas->mas;
> > > +
> > > +	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 true;
> > > +	}
> > > +	return false;
> > > +}
> > > +
> > >   static inline bool mas_wr_append(struct ma_wr_state *wr_mas)
> > >   {
> > >   	unsigned char end = wr_mas->node_end;
> > > @@ -4347,13 +4360,9 @@ static inline void mas_wr_modify(struct ma_wr_state *wr_mas)
> > >   	unsigned char node_size;
> > >   	struct ma_state *mas = wr_mas->mas;
> > > -	/* 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);
> > > +	/* Attempt to direct replace */
> > > +	if (mas_wr_replace(wr_mas))
> > >   		return;
> > > -	}
> > >   	/* Attempt to append */
> > >   	node_slots = mt_slots[wr_mas->type];
> > > -- 
> > > 2.20.1
> > > 

Re: [PATCH 09/10] maple_tree: Rework mas_wr_slot_store() to be cleaner and more efficient.

[Liam R. Howlett]

* Peng Zhang <zhangpeng.00@bytedance.com> [230516 03:27]:
> 
> 
> 在 2023/5/16 02:01, Liam R. Howlett 写道:
> > * Peng Zhang <zhangpeng.00@bytedance.com> [230515 09:18]:
> > > The code of mas_wr_slot_store() is messy, make it clearer and concise,
> > > and add comments. In addition, get whether the two gaps are empty to
> > > avoid calling mas_update_gap() all the time.
> > 
> > Please drop the cases from the comments.  These aren't that complicated
> > to need diagrams.
> > 
> > Case 1: Overwriting the range and over a part of the next range
> > Case 2: Overwriting a part of the range and over the entire next range
> > 
> > > 
> > > Signed-off-by: Peng Zhang <zhangpeng.00@bytedance.com>
> > > ---
> > >   lib/maple_tree.c | 79 +++++++++++++++++++++++++++---------------------
> > >   1 file changed, 44 insertions(+), 35 deletions(-)
> > > 
> > > diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> > > index 538e49feafbe4..d558e7bcb6da8 100644
> > > --- a/lib/maple_tree.c
> > > +++ b/lib/maple_tree.c
> > > @@ -4190,53 +4190,62 @@ static inline bool mas_wr_node_store(struct ma_wr_state *wr_mas)
> > >    * @wr_mas: the maple write state
> > >    *
> > >    * Return: True if stored, false otherwise
> > > + *
> > > + * Case 1:
> > > + *                       r_min   r_max    lmax
> > > + *                 +-------+-------+-------+
> > > + * original range: |       |offset | end   |
> > > + *                 +-----------------------+
> > > + *                         +-----------+
> > > + * overwrite:              |           |
> > > + *                         +-----------+
> > > + *                        index       last
> > > + *
> > > + * Case 2:
> > > + *                       r_min   r_max    lmax
> > > + *                 +-------+-------+-------+
> > > + * original range: |       |offest | end   |
> > > + *                 +-------+---------------+
> > > + *                             +-----------+
> > > + * overwrite:                  |           |
> > > + *                             +-----------+
> > > + *                           index        last
> > >    */
> > >   static inline bool mas_wr_slot_store(struct ma_wr_state *wr_mas)
> > >   {
> > >   	struct ma_state *mas = wr_mas->mas;
> > > -	unsigned long lmax; /* Logical max. */
> > >   	unsigned char offset = mas->offset;
> > > +	unsigned char offset_end = wr_mas->offset_end;
> > > +	unsigned long lmax = wr_mas->end_piv; /* Logical max. */
> > > +	bool gap = false;
> > > -	if ((wr_mas->r_max > mas->last) && ((wr_mas->r_min != mas->index) ||
> > > -				  (offset != wr_mas->node_end)))
> > > -		return false;
> > > -
> > > -	if (offset == wr_mas->node_end - 1)
> > > -		lmax = mas->max;
> > > -	else
> > > -		lmax = wr_mas->pivots[offset + 1];
> > > -
> > > -	/* going to overwrite too many slots. */
> > > -	if (lmax < mas->last)
> > > +	if (offset_end - offset != 1)
> > >   		return false;
> > > -	if (wr_mas->r_min == mas->index) {
> > > -		/* overwriting two or more ranges with one. */
> > > -		if (lmax == mas->last)
> > > -			return false;
> > > -
> > > -		/* Overwriting all of offset and a portion of offset + 1. */
> > > +	if (mas->index == wr_mas->r_min && mas->last < lmax) {
> > > +		/* Case 1 */
> > > +		gap |= !mt_slot_locked(mas->tree, wr_mas->slots, offset);
> > > +		gap |= !mt_slot_locked(mas->tree, wr_mas->slots, offset + 1);
> > >   		rcu_assign_pointer(wr_mas->slots[offset], wr_mas->entry);
> > >   		wr_mas->pivots[offset] = mas->last;
> > > -		goto done;
> > > -	}
> > > -
> > > -	/* Doesn't end on the next range end. */
> > > -	if (lmax != mas->last)
> > > +	} else if (mas->index > wr_mas->r_min && mas->last == lmax) {
> > > +		/* Case 2 */
> > > +		gap |= !mt_slot_locked(mas->tree, wr_mas->slots, offset);
> > > +		gap |= !mt_slot_locked(mas->tree, wr_mas->slots, offset + 1);
> > > +		rcu_assign_pointer(wr_mas->slots[offset + 1], wr_mas->entry);
> > > +		wr_mas->pivots[offset] = mas->index - 1;
> > 
> > These two lines need to be in opposite order to ensure a reader sees
> > either the value or the previous value.  If you overwrite something with
> > a new value, it is possible that a reader looking for the next range
> > will get the value stored at offset (but not entry).
> Please think again, did you think wrong?

I did, thanks.

> It doesn't happen, swapping the order introduces the problem.
> If we update the pivot first, it will cause a part of the value
> of the range indexed by offset to change to the value of the
> range indexed by offset+1, which is illegal.
> 
> My assignment order remains the same as the previous version.

Yes, you are correct.  There is a place where the reverse is required
for RCU, but that's appending.

> 
> > 
> > > +		mas->offset++; /* Keep mas accurate. */
> > > +	} else {
> > >   		return false;
> > > +	}
> > > -	/* Overwriting a portion of offset and all of offset + 1 */
> > > -	if ((offset + 1 < mt_pivots[wr_mas->type]) &&
> > > -	    (wr_mas->entry || wr_mas->pivots[offset + 1]))
> > > -		wr_mas->pivots[offset + 1] = mas->last;
> > > -
> > > -	rcu_assign_pointer(wr_mas->slots[offset + 1], wr_mas->entry);
> > > -	wr_mas->pivots[offset] = mas->index - 1;
> > > -	mas->offset++; /* Keep mas accurate. */
> > > -
> > > -done:
> > >   	trace_ma_write(__func__, mas, 0, wr_mas->entry);
> > > -	mas_update_gap(mas);
> > > +	/*
> > > +	 * Only update gap when the new entry is empty or there is an empty
> > > +	 * entry in the original two ranges.
> > > +	 */
> > > +	if (!wr_mas->entry || gap)
> > > +		mas_update_gap(mas);
> > >   	return true;
> > >   }
> > > @@ -4418,7 +4427,7 @@ static inline void mas_wr_modify(struct ma_wr_state *wr_mas)
> > >   	if (new_end == wr_mas->node_end + 1 && mas_wr_append(wr_mas))
> > >   		return;
> > > -	if ((wr_mas->offset_end - mas->offset <= 1) && mas_wr_slot_store(wr_mas))
> > > +	if (new_end == wr_mas->node_end && mas_wr_slot_store(wr_mas))
> > >   		return;
> > >   	else if (mas_wr_node_store(wr_mas))
> > >   		return;
> > > -- 
> > > 2.20.1
> > > 
> > 

Re: [PATCH 06/10] maple_tree: Wrap the replace operation with an inline function.

[Peng Zhang]

在 2023/5/16 22:16, Liam R. Howlett 写道:
> * Peng Zhang <zhangpeng.00@bytedance.com> [230515 20:46]:
>>
>>
>> 在 2023/5/16 01:07, Liam R. Howlett 写道:
>>> * Peng Zhang <zhangpeng.00@bytedance.com> [230515 09:18]:
>>>> To make mas_wr_modify() cleaner, wrap the replace operation with an
>>>> inline function.
>>>
>>> mas_wr_modify() is already pretty small.  Is there any reason you want
>>> this in its own function besides it looking cleaner?
>> I just want to make the four fast paths in mas_wr_modify()
>> look uniform without any functional effect.
> 
> I'd like to keep it the way it is. I think the comment stating what is
> going on is clear enough and mas_wr_modify() isn't too big.
Ok, I'll drop this patch in v3.
> 
>>>
>>>>
>>>> Signed-off-by: Peng Zhang <zhangpeng.00@bytedance.com>
>>>> ---
>>>>    lib/maple_tree.c | 21 +++++++++++++++------
>>>>    1 file changed, 15 insertions(+), 6 deletions(-)
>>>>
>>>> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
>>>> index 4c649d75a4923..ce695adc670ec 100644
>>>> --- a/lib/maple_tree.c
>>>> +++ b/lib/maple_tree.c
>>>> @@ -4288,6 +4288,19 @@ static inline void mas_wr_extend_null(struct ma_wr_state *wr_mas)
>>>>    	}
>>>>    }
>>>> +static inline bool mas_wr_replace(struct ma_wr_state *wr_mas)
>>>> +{
>>>> +	struct ma_state *mas = wr_mas->mas;
>>>> +
>>>> +	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 true;
>>>> +	}
>>>> +	return false;
>>>> +}
>>>> +
>>>>    static inline bool mas_wr_append(struct ma_wr_state *wr_mas)
>>>>    {
>>>>    	unsigned char end = wr_mas->node_end;
>>>> @@ -4347,13 +4360,9 @@ static inline void mas_wr_modify(struct ma_wr_state *wr_mas)
>>>>    	unsigned char node_size;
>>>>    	struct ma_state *mas = wr_mas->mas;
>>>> -	/* 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);
>>>> +	/* Attempt to direct replace */
>>>> +	if (mas_wr_replace(wr_mas))
>>>>    		return;
>>>> -	}
>>>>    	/* Attempt to append */
>>>>    	node_slots = mt_slots[wr_mas->type];
>>>> -- 
>>>> 2.20.1
>>>>

Re: [PATCH 10/10] maple_tree: Simplify and clean up mas_wr_node_store()

[Liam R. Howlett]

* Peng Zhang <zhangpeng.00@bytedance.com> [230516 06:53]:
> 
> 
> 在 2023/5/16 02:58, Liam R. Howlett 写道:
> > * Peng Zhang <zhangpeng.00@bytedance.com> [230515 09:18]:
> > > Simplify and clean up mas_wr_node_store(), remove unnecessary code.
> > 
> > This change fails the userspace testing for me.
> > 
> > > 
> > > Signed-off-by: Peng Zhang <zhangpeng.00@bytedance.com>
> > > ---
> > >   lib/maple_tree.c | 75 +++++++++++++-----------------------------------
> > >   1 file changed, 20 insertions(+), 55 deletions(-)
> > > 
> > > diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> > > index d558e7bcb6da8..ff4aa01cf88b6 100644
> > > --- a/lib/maple_tree.c
> > > +++ b/lib/maple_tree.c
> > > @@ -4066,46 +4066,21 @@ static inline int mas_wr_spanning_store(struct ma_wr_state *wr_mas)
> > >    *
> > >    * Return: True if stored, false otherwise
> > >    */
> > > -static inline bool mas_wr_node_store(struct ma_wr_state *wr_mas)
> > > +static inline bool mas_wr_node_store(struct ma_wr_state *wr_mas,
> > > +				     unsigned char new_end)
> > >   {
> > >   	struct ma_state *mas = wr_mas->mas;
> > >   	void __rcu **dst_slots;
> > >   	unsigned long *dst_pivots;
> > >   	unsigned char dst_offset;
> > > -	unsigned char new_end = wr_mas->node_end;
> > > -	unsigned char offset;
> > > -	unsigned char node_slots = mt_slots[wr_mas->type];
> > >   	struct maple_node reuse, *newnode;
> > > -	unsigned char copy_size, max_piv = mt_pivots[wr_mas->type];
> > > +	unsigned char copy_size, node_pivots = mt_pivots[wr_mas->type];
> > >   	bool in_rcu = mt_in_rcu(mas->tree);
> > > -	offset = mas->offset;
> > > -	if (mas->last == wr_mas->r_max) {
> > > -		/* runs right to the end of the node */
> > > -		if (mas->last == mas->max)
> > > -			new_end = offset;
> > > -		/* don't copy this offset */

Can you re-add the comments that you removed?  I know the code was more
lines, but the comments really help follow things through on what is
going on.

> > > +	if (mas->last == wr_mas->end_piv)
> > >   		wr_mas->offset_end++;
> I guess there is a problem here? If we modify wr_mas->offset_end,
> but this function fails to try the fast path, it will enter the
> slow path with the modified offset_end. But it also has this
> problem in the previous version.

I don't think we can enter the slow path if this is true.  We must have
enough room, right?

> 
> I applied this patch to linux-next/master but it passed the
> userspace tests. I need more information to confirm what the
> problem is.

The failure was pretty consistent for me so I thought it wouldn't be an
issue reproducing.  I tested against mm-unstable and it happened every
time I ran the whole patch set yesterday.  Today is a different story
and it isn't happening for me now.

Here is the failure log:

$ CC=gcc make maple && LSAN_OPTIONS="report_objects=1" ./maple
gcc  -O2 -g -Wall -I. -I../../include -g -Og -Wall -D_LGPL_SOURCE -fsanitize=address -fsanitize=undefined   -c -o maple.o maple.c
gcc -fsanitize=address -fsanitize=undefined  maple.o xarray.o radix-tree.o idr.o linux.o test.o find_bit.o bitmap.o slab.o  -lpthread -lurcu -o maple
CC=gcc make maple  5.10s user 0.18s system 99% cpu 5.283 total
maple_tree(0x7ffea7d35b00) flags 0, height 0 root (nil)
0: (nil)
maple_tree(0x7ffea7d35b00) flags 0, height 0 root 0x1
0: value 0 (0x0) [0x1]
maple_tree(0x7ffea7d35b00) flags 0, height 0 root 0x61500000010c
0: 0x61500000010c
0x61c000737100[14] should not have entry 0xfeadfeffe001
BUG at mas_validate_limits:7110 (1)
maple_tree(0x7ffea7d35b00) flags D, height 3 root 0x61e00099551e

....<lots of tree stuff>...
      7f56ecffa000-7f56ecffafff: value 140011320090624 (0x7f56ecffa000) [0xfeadd9ff4001]
    7f56ecffb000-7f56efffffff: node 0x61e000989500 depth 2 type 1 parent 0x61c000736916 contents: 0xfeadd9ff6001 7F56ED7FAFFF 0xfeaddaff6001 7F56ED7FBFFF 0xfeaddaff8001 7F56EDFFBFFF 0xfeaddbff8001 7F56EDFFCFFF 0xfeaddbffa001 7F56EE7FCFFF 0xfeaddcffa001 7F56EE7FDFFF 0xfeaddcffc001 7F56EEFFDFFF 0xfeadddffc001 7F56EEFFEFFF 0xfeadddffe001 7F56EF7FEFFF 0xfeaddeffe001 7F56EF7FFFFF 0xfeaddf000001 7F56EFFFFFFF (nil) 0 (nil) 0 (nil) 0 (nil) 0 0xa
      7f56ecffb000-7f56ed7fafff: value 140011320094720 (0x7f56ecffb000) [0xfeadd9ff6001]
      7f56ed7fb000-7f56ed7fbfff: value 140011328483328 (0x7f56ed7fb000) [0xfeaddaff6001]
      7f56ed7fc000-7f56edffbfff: value 140011328487424 (0x7f56ed7fc000) [0xfeaddaff8001]
      7f56edffc000-7f56edffcfff: value 140011336876032 (0x7f56edffc000) [0xfeaddbff8001]
      7f56edffd000-7f56ee7fcfff: value 140011336880128 (0x7f56edffd000) [0xfeaddbffa001]
      7f56ee7fd000-7f56ee7fdfff: value 140011345268736 (0x7f56ee7fd000) [0xfeaddcffa001]
      7f56ee7fe000-7f56eeffdfff: value 140011345272832 (0x7f56ee7fe000) [0xfeaddcffc001]
      7f56eeffe000-7f56eeffefff: value 140011353661440 (0x7f56eeffe000) [0xfeadddffc001]
      7f56eefff000-7f56ef7fefff: value 140011353665536 (0x7f56eefff000) [0xfeadddffe001]
      7f56ef7ff000-7f56ef7fffff: value 140011362054144 (0x7f56ef7ff000) [0xfeaddeffe001]
      7f56ef800000-7f56efffffff: value 140011362058240 (0x7f56ef800000) [0xfeaddf000001]
    7f56f0000000-7f56ffffffff: node 0x61c000737100 depth 2 type 1 parent 0x61c00073691e contents: 0xfeade0000001 7F56F0020FFF 0xfeade0042001 7F56F3FFFFFF (nil) 7F56F5FFBFFF 0xfeadebff8001 7F56F5FFCFFF 0xfeadebffa001 7F56F67FCFFF 0xfeadecffa001 7F56F67FDFFF 0xfeadecffc001 7F56F6FFDFFF 0xfeadedffc001 7F56F6FFEFFF 0xfeadedffe001 7F56F7FFFFFF 0xfeadf0000001 7F56F8020FFF 0xfeadf0042001 7F56FBFFFFFF (nil) 7F56FE7FCFFF 0xfeadfcffa001 7F56FE7FDFFF 0xfeadfcffc001 7F56FFFFFFFF 0xfeadfeffe001 7F56FFFFFFFF 0xe
      7f56f0000000-7f56f0020fff: value 140011370446848 (0x7f56f0000000) [0xfeade0000001]
      7f56f0021000-7f56f3ffffff: value 140011370582016 (0x7f56f0021000) [0xfeade0042001]
      7f56f4000000-7f56f5ffbfff: (nil)
      7f56f5ffc000-7f56f5ffcfff: value 140011471093760 (0x7f56f5ffc000) [0xfeadebff8001]
      7f56f5ffd000-7f56f67fcfff: value 140011471097856 (0x7f56f5ffd000) [0xfeadebffa001]
      7f56f67fd000-7f56f67fdfff: value 140011479486464 (0x7f56f67fd000) [0xfeadecffa001]
      7f56f67fe000-7f56f6ffdfff: value 140011479490560 (0x7f56f67fe000) [0xfeadecffc001]
      7f56f6ffe000-7f56f6ffefff: value 140011487879168 (0x7f56f6ffe000) [0xfeadedffc001]
      7f56f6fff000-7f56f7ffffff: value 140011487883264 (0x7f56f6fff000) [0xfeadedffe001]
      7f56f8000000-7f56f8020fff: value 140011504664576 (0x7f56f8000000) [0xfeadf0000001]
      7f56f8021000-7f56fbffffff: value 140011504799744 (0x7f56f8021000) [0xfeadf0042001]
      7f56fc000000-7f56fe7fcfff: (nil)
      7f56fe7fd000-7f56fe7fdfff: value 140011613704192 (0x7f56fe7fd000) [0xfeadfcffa001]
      7f56fe7fe000-7f56ffffffff: value 140011613708288 (0x7f56fe7fe000) [0xfeadfcffc001]
    7f5700000000-7f570c7f9fff: node 0x61c000737900 depth 2 type 1 parent 0x61c000736926 contents: 0xfeae00000001 7F5700020FFF 0xfeae00042001 7F5703FFFFFF (nil) 7F57047F8FFF 0xfeae08ff2001 7F5706FFDFFF 0xfeae0dffc001 7F5706FFEFFF 0xfeae0dffe001 7F57077FEFFF 0xfeae0effe001 7F57077FFFFF 0xfeae0f000001 7F5707FFFFFF 0xfeae10000001 7F5708020FFF 0xfeae10042001 7F570BFFFFFF (nil) 7F570C7F8FFF 0xfeae18ff2001 7F570C7F9FFF (nil) 0 (nil) 0 (nil) 0 0xb

...<lots more tree stuff>...

Pass: 609373594 Run:609373595
maple: ../../../lib/maple_tree.c:7110: mas_validate_limits: Assertion `0' failed.
[1]    855591 IOT instruction (core dumped)  LSAN_OPTIONS="report_objects=1" ./maple
LSAN_OPTIONS="report_objects=1" ./maple  128.63s user 66.12s system 444% cpu 43.818 total

The middle node in that output has the issue.  If you notice that slot
13 and 14 have the maximum limit here (7F56FFFFFFFF) so the verbose
output of the last value/line is not printed.

The line "0x61c000737100[14] should not have entry 0xfeadfeffe001" is
telling us that there is a value beyond what is expected, and it is at
slot 14 of that node.

A bit of context for the test may help.  During the development, I was
seeing odd errors and discovered that I was not clearing old data from
free areas of a node sometimes.  It was not detected because the maximum
value of a node is hit, until another modification caused that data to
be re-introduced into the tree.  This test detects data beyond what is
expected to be the end of the node.

This would also happen if you copy too far, but that shouldn't be
intermittent, assuming the test is okay.

I re-tested today and it isn't happening for me now.  This is probably
an RCU error that is intermittent.  The problem may not even be in this
patch - if it is RCU it probably is not this patch.  It seemed to fail
consistently on this patch - and I reverted the previous patch and also
saw the failure because I suspected it had a potential RCU issue, which
you pointed out was not an issue.  I wouldn't expect the issue to be
this patch because we use a new node in RCU mode, so the node with data
beyond the end would be in the tree for a longer time.

The failures I saw were always the same.

Could this be an append operation caught by RCU?  It might just be a
test issue and your updates change the timing?

> 
> Thanks.
> 
> > > -	} else if (mas->last < wr_mas->r_max) {
> > > -		/* new range ends in this range */
> > > -		if (unlikely(wr_mas->r_max == ULONG_MAX))
> > > -			mas_bulk_rebalance(mas, wr_mas->node_end, wr_mas->type);
> > > -
> > > -		new_end++;
> > > -	} else {
> > > -		if (wr_mas->end_piv == mas->last)
> > > -			wr_mas->offset_end++;
> > > -
> > > -		new_end -= wr_mas->offset_end - offset - 1;
> > > -	}
> > > -
> > > -	/* new range starts within a range */
> > > -	if (wr_mas->r_min < mas->index)
> > > -		new_end++;
> > > -
> > > -	/* Not enough room */
> > > -	if (new_end >= node_slots)
> > > -		return false;
> > > +	else if (unlikely(wr_mas->r_max == ULONG_MAX))
> > > +		mas_bulk_rebalance(mas, wr_mas->node_end, wr_mas->type);
> > >   	/* Not enough data. */
> > >   	if (!mte_is_root(mas->node) && (new_end <= mt_min_slots[wr_mas->type]) &&
> > > @@ -4128,47 +4103,36 @@ static inline bool mas_wr_node_store(struct ma_wr_state *wr_mas)
> > >   	dst_pivots = ma_pivots(newnode, wr_mas->type);
> > >   	dst_slots = ma_slots(newnode, wr_mas->type);
> > >   	/* Copy from start to insert point */
> > > -	memcpy(dst_pivots, wr_mas->pivots, sizeof(unsigned long) * (offset + 1));
> > > -	memcpy(dst_slots, wr_mas->slots, sizeof(void *) * (offset + 1));
> > > -	dst_offset = offset;
> > > +	memcpy(dst_pivots, wr_mas->pivots, sizeof(unsigned long) * mas->offset);
> > > +	memcpy(dst_slots, wr_mas->slots, sizeof(void *) * mas->offset);
> > >   	/* Handle insert of new range starting after old range */
> > >   	if (wr_mas->r_min < mas->index) {
> > > -		mas->offset++;
> > > -		rcu_assign_pointer(dst_slots[dst_offset], wr_mas->content);
> > > -		dst_pivots[dst_offset++] = mas->index - 1;
> > > +		rcu_assign_pointer(dst_slots[mas->offset], wr_mas->content);
> > > +		dst_pivots[mas->offset++] = mas->index - 1;
> > >   	}
> > >   	/* Store the new entry and range end. */
> > > -	if (dst_offset < max_piv)
> > > -		dst_pivots[dst_offset] = mas->last;
> > > -	mas->offset = dst_offset;
> > > -	rcu_assign_pointer(dst_slots[dst_offset], wr_mas->entry);
> > > +	if (mas->offset < node_pivots)
> > > +		dst_pivots[mas->offset] = mas->last;
> > > +	rcu_assign_pointer(dst_slots[mas->offset], wr_mas->entry);
> > >   	/*
> > >   	 * this range wrote to the end of the node or it overwrote the rest of
> > >   	 * the data
> > >   	 */
> > > -	if (wr_mas->offset_end > wr_mas->node_end || mas->last >= mas->max) {
> > > -		new_end = dst_offset;
> > > +	if (wr_mas->offset_end > wr_mas->node_end)
> > >   		goto done;
> > > -	}
> > > -	dst_offset++;
> > > +	dst_offset = mas->offset + 1;
> > >   	/* Copy to the end of node if necessary. */
> > >   	copy_size = wr_mas->node_end - wr_mas->offset_end + 1;
> > >   	memcpy(dst_slots + dst_offset, wr_mas->slots + wr_mas->offset_end,
> > >   	       sizeof(void *) * copy_size);
> > > -	if (dst_offset < max_piv) {
> > > -		if (copy_size > max_piv - dst_offset)
> > > -			copy_size = max_piv - dst_offset;
> > > +	memcpy(dst_pivots + dst_offset, wr_mas->pivots + wr_mas->offset_end,
> > > +	       sizeof(unsigned long) * (copy_size - 1));
> > > -		memcpy(dst_pivots + dst_offset,
> > > -		       wr_mas->pivots + wr_mas->offset_end,
> > > -		       sizeof(unsigned long) * copy_size);
> > > -	}
> > > -
> > > -	if ((wr_mas->node_end == node_slots - 1) && (new_end < node_slots - 1))
> > > +	if (new_end < node_pivots)
> > >   		dst_pivots[new_end] = mas->max;
> > >   done:
> > > @@ -4429,7 +4393,8 @@ static inline void mas_wr_modify(struct ma_wr_state *wr_mas)
> > >   	if (new_end == wr_mas->node_end && mas_wr_slot_store(wr_mas))
> > >   		return;
> > > -	else if (mas_wr_node_store(wr_mas))
> > > +
> > > +	if (mas_wr_node_store(wr_mas, new_end))
> > >   		return;
> > >   	if (mas_is_err(mas))
> > > -- 
> > > 2.20.1
> > > 

Re: [PATCH 10/10] maple_tree: Simplify and clean up mas_wr_node_store()

[Peng Zhang]

在 2023/5/16 23:52, Liam R. Howlett 写道:
> * Peng Zhang <zhangpeng.00@bytedance.com> [230516 06:53]:
>>
>>
>> 在 2023/5/16 02:58, Liam R. Howlett 写道:
>>> * Peng Zhang <zhangpeng.00@bytedance.com> [230515 09:18]:
>>>> Simplify and clean up mas_wr_node_store(), remove unnecessary code.
>>>
>>> This change fails the userspace testing for me.
>>>
>>>>
>>>> Signed-off-by: Peng Zhang <zhangpeng.00@bytedance.com>
>>>> ---
>>>>    lib/maple_tree.c | 75 +++++++++++++-----------------------------------
>>>>    1 file changed, 20 insertions(+), 55 deletions(-)
>>>>
>>>> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
>>>> index d558e7bcb6da8..ff4aa01cf88b6 100644
>>>> --- a/lib/maple_tree.c
>>>> +++ b/lib/maple_tree.c
>>>> @@ -4066,46 +4066,21 @@ static inline int mas_wr_spanning_store(struct ma_wr_state *wr_mas)
>>>>     *
>>>>     * Return: True if stored, false otherwise
>>>>     */
>>>> -static inline bool mas_wr_node_store(struct ma_wr_state *wr_mas)
>>>> +static inline bool mas_wr_node_store(struct ma_wr_state *wr_mas,
>>>> +				     unsigned char new_end)
>>>>    {
>>>>    	struct ma_state *mas = wr_mas->mas;
>>>>    	void __rcu **dst_slots;
>>>>    	unsigned long *dst_pivots;
>>>>    	unsigned char dst_offset;
>>>> -	unsigned char new_end = wr_mas->node_end;
>>>> -	unsigned char offset;
>>>> -	unsigned char node_slots = mt_slots[wr_mas->type];
>>>>    	struct maple_node reuse, *newnode;
>>>> -	unsigned char copy_size, max_piv = mt_pivots[wr_mas->type];
>>>> +	unsigned char copy_size, node_pivots = mt_pivots[wr_mas->type];
>>>>    	bool in_rcu = mt_in_rcu(mas->tree);
>>>> -	offset = mas->offset;
>>>> -	if (mas->last == wr_mas->r_max) {
>>>> -		/* runs right to the end of the node */
>>>> -		if (mas->last == mas->max)
>>>> -			new_end = offset;
>>>> -		/* don't copy this offset */
> 
> Can you re-add the comments that you removed?  I know the code was more
> lines, but the comments really help follow things through on what is
> going on.
OK, I will.
> 
>>>> +	if (mas->last == wr_mas->end_piv)
>>>>    		wr_mas->offset_end++;
>> I guess there is a problem here? If we modify wr_mas->offset_end,
>> but this function fails to try the fast path, it will enter the
>> slow path with the modified offset_end. But it also has this
>> problem in the previous version.
> 
> I don't think we can enter the slow path if this is true.  We must have
> enough room, right?
Yes, but there is another case here, if the number of entries
of a maple_node is less than mt_min_slots[type].
> 
>>
>> I applied this patch to linux-next/master but it passed the
>> userspace tests. I need more information to confirm what the
>> problem is.
> 
> The failure was pretty consistent for me so I thought it wouldn't be an
> issue reproducing.  I tested against mm-unstable and it happened every
> time I ran the whole patch set yesterday.  Today is a different story
> and it isn't happening for me now.
> 
> Here is the failure log:
> 
> $ CC=gcc make maple && LSAN_OPTIONS="report_objects=1" ./maple
> gcc  -O2 -g -Wall -I. -I../../include -g -Og -Wall -D_LGPL_SOURCE -fsanitize=address -fsanitize=undefined   -c -o maple.o maple.c
> gcc -fsanitize=address -fsanitize=undefined  maple.o xarray.o radix-tree.o idr.o linux.o test.o find_bit.o bitmap.o slab.o  -lpthread -lurcu -o maple
> CC=gcc make maple  5.10s user 0.18s system 99% cpu 5.283 total
> maple_tree(0x7ffea7d35b00) flags 0, height 0 root (nil)
> 0: (nil)
> maple_tree(0x7ffea7d35b00) flags 0, height 0 root 0x1
> 0: value 0 (0x0) [0x1]
> maple_tree(0x7ffea7d35b00) flags 0, height 0 root 0x61500000010c
> 0: 0x61500000010c
> 0x61c000737100[14] should not have entry 0xfeadfeffe001
> BUG at mas_validate_limits:7110 (1)
> maple_tree(0x7ffea7d35b00) flags D, height 3 root 0x61e00099551e
> 
> ....<lots of tree stuff>...
>        7f56ecffa000-7f56ecffafff: value 140011320090624 (0x7f56ecffa000) [0xfeadd9ff4001]
>      7f56ecffb000-7f56efffffff: node 0x61e000989500 depth 2 type 1 parent 0x61c000736916 contents: 0xfeadd9ff6001 7F56ED7FAFFF 0xfeaddaff6001 7F56ED7FBFFF 0xfeaddaff8001 7F56EDFFBFFF 0xfeaddbff8001 7F56EDFFCFFF 0xfeaddbffa001 7F56EE7FCFFF 0xfeaddcffa001 7F56EE7FDFFF 0xfeaddcffc001 7F56EEFFDFFF 0xfeadddffc001 7F56EEFFEFFF 0xfeadddffe001 7F56EF7FEFFF 0xfeaddeffe001 7F56EF7FFFFF 0xfeaddf000001 7F56EFFFFFFF (nil) 0 (nil) 0 (nil) 0 (nil) 0 0xa
>        7f56ecffb000-7f56ed7fafff: value 140011320094720 (0x7f56ecffb000) [0xfeadd9ff6001]
>        7f56ed7fb000-7f56ed7fbfff: value 140011328483328 (0x7f56ed7fb000) [0xfeaddaff6001]
>        7f56ed7fc000-7f56edffbfff: value 140011328487424 (0x7f56ed7fc000) [0xfeaddaff8001]
>        7f56edffc000-7f56edffcfff: value 140011336876032 (0x7f56edffc000) [0xfeaddbff8001]
>        7f56edffd000-7f56ee7fcfff: value 140011336880128 (0x7f56edffd000) [0xfeaddbffa001]
>        7f56ee7fd000-7f56ee7fdfff: value 140011345268736 (0x7f56ee7fd000) [0xfeaddcffa001]
>        7f56ee7fe000-7f56eeffdfff: value 140011345272832 (0x7f56ee7fe000) [0xfeaddcffc001]
>        7f56eeffe000-7f56eeffefff: value 140011353661440 (0x7f56eeffe000) [0xfeadddffc001]
>        7f56eefff000-7f56ef7fefff: value 140011353665536 (0x7f56eefff000) [0xfeadddffe001]
>        7f56ef7ff000-7f56ef7fffff: value 140011362054144 (0x7f56ef7ff000) [0xfeaddeffe001]
>        7f56ef800000-7f56efffffff: value 140011362058240 (0x7f56ef800000) [0xfeaddf000001]
>      7f56f0000000-7f56ffffffff: node 0x61c000737100 depth 2 type 1 parent 0x61c00073691e contents: 0xfeade0000001 7F56F0020FFF 0xfeade0042001 7F56F3FFFFFF (nil) 7F56F5FFBFFF 0xfeadebff8001 7F56F5FFCFFF 0xfeadebffa001 7F56F67FCFFF 0xfeadecffa001 7F56F67FDFFF 0xfeadecffc001 7F56F6FFDFFF 0xfeadedffc001 7F56F6FFEFFF 0xfeadedffe001 7F56F7FFFFFF 0xfeadf0000001 7F56F8020FFF 0xfeadf0042001 7F56FBFFFFFF (nil) 7F56FE7FCFFF 0xfeadfcffa001 7F56FE7FDFFF 0xfeadfcffc001 7F56FFFFFFFF 0xfeadfeffe001 7F56FFFFFFFF 0xe
>        7f56f0000000-7f56f0020fff: value 140011370446848 (0x7f56f0000000) [0xfeade0000001]
>        7f56f0021000-7f56f3ffffff: value 140011370582016 (0x7f56f0021000) [0xfeade0042001]
>        7f56f4000000-7f56f5ffbfff: (nil)
>        7f56f5ffc000-7f56f5ffcfff: value 140011471093760 (0x7f56f5ffc000) [0xfeadebff8001]
>        7f56f5ffd000-7f56f67fcfff: value 140011471097856 (0x7f56f5ffd000) [0xfeadebffa001]
>        7f56f67fd000-7f56f67fdfff: value 140011479486464 (0x7f56f67fd000) [0xfeadecffa001]
>        7f56f67fe000-7f56f6ffdfff: value 140011479490560 (0x7f56f67fe000) [0xfeadecffc001]
>        7f56f6ffe000-7f56f6ffefff: value 140011487879168 (0x7f56f6ffe000) [0xfeadedffc001]
>        7f56f6fff000-7f56f7ffffff: value 140011487883264 (0x7f56f6fff000) [0xfeadedffe001]
>        7f56f8000000-7f56f8020fff: value 140011504664576 (0x7f56f8000000) [0xfeadf0000001]
>        7f56f8021000-7f56fbffffff: value 140011504799744 (0x7f56f8021000) [0xfeadf0042001]
>        7f56fc000000-7f56fe7fcfff: (nil)
>        7f56fe7fd000-7f56fe7fdfff: value 140011613704192 (0x7f56fe7fd000) [0xfeadfcffa001]
>        7f56fe7fe000-7f56ffffffff: value 140011613708288 (0x7f56fe7fe000) [0xfeadfcffc001]
>      7f5700000000-7f570c7f9fff: node 0x61c000737900 depth 2 type 1 parent 0x61c000736926 contents: 0xfeae00000001 7F5700020FFF 0xfeae00042001 7F5703FFFFFF (nil) 7F57047F8FFF 0xfeae08ff2001 7F5706FFDFFF 0xfeae0dffc001 7F5706FFEFFF 0xfeae0dffe001 7F57077FEFFF 0xfeae0effe001 7F57077FFFFF 0xfeae0f000001 7F5707FFFFFF 0xfeae10000001 7F5708020FFF 0xfeae10042001 7F570BFFFFFF (nil) 7F570C7F8FFF 0xfeae18ff2001 7F570C7F9FFF (nil) 0 (nil) 0 (nil) 0 0xb
> 
> ...<lots more tree stuff>...
> 
> Pass: 609373594 Run:609373595
> maple: ../../../lib/maple_tree.c:7110: mas_validate_limits: Assertion `0' failed.
> [1]    855591 IOT instruction (core dumped)  LSAN_OPTIONS="report_objects=1" ./maple
> LSAN_OPTIONS="report_objects=1" ./maple  128.63s user 66.12s system 444% cpu 43.818 total
> 
> The middle node in that output has the issue.  If you notice that slot
> 13 and 14 have the maximum limit here (7F56FFFFFFFF) so the verbose
> output of the last value/line is not printed.
> 
> The line "0x61c000737100[14] should not have entry 0xfeadfeffe001" is
> telling us that there is a value beyond what is expected, and it is at
> slot 14 of that node.
> 
> A bit of context for the test may help.  During the development, I was
> seeing odd errors and discovered that I was not clearing old data from
> free areas of a node sometimes.  It was not detected because the maximum
> value of a node is hit, until another modification caused that data to
> be re-introduced into the tree.  This test detects data beyond what is
> expected to be the end of the node.
> 
> This would also happen if you copy too far, but that shouldn't be
> intermittent, assuming the test is okay.
> 
> I re-tested today and it isn't happening for me now.  This is probably
> an RCU error that is intermittent.  The problem may not even be in this
> patch - if it is RCU it probably is not this patch.  It seemed to fail
> consistently on this patch - and I reverted the previous patch and also
> saw the failure because I suspected it had a potential RCU issue, which
> you pointed out was not an issue.  I wouldn't expect the issue to be
> this patch because we use a new node in RCU mode, so the node with data
> beyond the end would be in the tree for a longer time.
> 
> The failures I saw were always the same.
> 
> Could this be an append operation caught by RCU?  It might just be a
> test issue and your updates change the timing?
> 
>>
>> Thanks.
>>
>>>> -	} else if (mas->last < wr_mas->r_max) {
>>>> -		/* new range ends in this range */
>>>> -		if (unlikely(wr_mas->r_max == ULONG_MAX))
>>>> -			mas_bulk_rebalance(mas, wr_mas->node_end, wr_mas->type);
>>>> -
>>>> -		new_end++;
>>>> -	} else {
>>>> -		if (wr_mas->end_piv == mas->last)
>>>> -			wr_mas->offset_end++;
>>>> -
>>>> -		new_end -= wr_mas->offset_end - offset - 1;
>>>> -	}
>>>> -
>>>> -	/* new range starts within a range */
>>>> -	if (wr_mas->r_min < mas->index)
>>>> -		new_end++;
>>>> -
>>>> -	/* Not enough room */
>>>> -	if (new_end >= node_slots)
>>>> -		return false;
>>>> +	else if (unlikely(wr_mas->r_max == ULONG_MAX))
>>>> +		mas_bulk_rebalance(mas, wr_mas->node_end, wr_mas->type);
>>>>    	/* Not enough data. */
>>>>    	if (!mte_is_root(mas->node) && (new_end <= mt_min_slots[wr_mas->type]) &&
>>>> @@ -4128,47 +4103,36 @@ static inline bool mas_wr_node_store(struct ma_wr_state *wr_mas)
>>>>    	dst_pivots = ma_pivots(newnode, wr_mas->type);
>>>>    	dst_slots = ma_slots(newnode, wr_mas->type);
>>>>    	/* Copy from start to insert point */
>>>> -	memcpy(dst_pivots, wr_mas->pivots, sizeof(unsigned long) * (offset + 1));
>>>> -	memcpy(dst_slots, wr_mas->slots, sizeof(void *) * (offset + 1));
>>>> -	dst_offset = offset;
>>>> +	memcpy(dst_pivots, wr_mas->pivots, sizeof(unsigned long) * mas->offset);
>>>> +	memcpy(dst_slots, wr_mas->slots, sizeof(void *) * mas->offset);
>>>>    	/* Handle insert of new range starting after old range */
>>>>    	if (wr_mas->r_min < mas->index) {
>>>> -		mas->offset++;
>>>> -		rcu_assign_pointer(dst_slots[dst_offset], wr_mas->content);
>>>> -		dst_pivots[dst_offset++] = mas->index - 1;
>>>> +		rcu_assign_pointer(dst_slots[mas->offset], wr_mas->content);
>>>> +		dst_pivots[mas->offset++] = mas->index - 1;
>>>>    	}
>>>>    	/* Store the new entry and range end. */
>>>> -	if (dst_offset < max_piv)
>>>> -		dst_pivots[dst_offset] = mas->last;
>>>> -	mas->offset = dst_offset;
>>>> -	rcu_assign_pointer(dst_slots[dst_offset], wr_mas->entry);
>>>> +	if (mas->offset < node_pivots)
>>>> +		dst_pivots[mas->offset] = mas->last;
>>>> +	rcu_assign_pointer(dst_slots[mas->offset], wr_mas->entry);
>>>>    	/*
>>>>    	 * this range wrote to the end of the node or it overwrote the rest of
>>>>    	 * the data
>>>>    	 */
>>>> -	if (wr_mas->offset_end > wr_mas->node_end || mas->last >= mas->max) {
>>>> -		new_end = dst_offset;
>>>> +	if (wr_mas->offset_end > wr_mas->node_end)
>>>>    		goto done;
>>>> -	}
>>>> -	dst_offset++;
>>>> +	dst_offset = mas->offset + 1;
>>>>    	/* Copy to the end of node if necessary. */
>>>>    	copy_size = wr_mas->node_end - wr_mas->offset_end + 1;
>>>>    	memcpy(dst_slots + dst_offset, wr_mas->slots + wr_mas->offset_end,
>>>>    	       sizeof(void *) * copy_size);
>>>> -	if (dst_offset < max_piv) {
>>>> -		if (copy_size > max_piv - dst_offset)
>>>> -			copy_size = max_piv - dst_offset;
>>>> +	memcpy(dst_pivots + dst_offset, wr_mas->pivots + wr_mas->offset_end,
>>>> +	       sizeof(unsigned long) * (copy_size - 1));
>>>> -		memcpy(dst_pivots + dst_offset,
>>>> -		       wr_mas->pivots + wr_mas->offset_end,
>>>> -		       sizeof(unsigned long) * copy_size);
>>>> -	}
>>>> -
>>>> -	if ((wr_mas->node_end == node_slots - 1) && (new_end < node_slots - 1))
>>>> +	if (new_end < node_pivots)
>>>>    		dst_pivots[new_end] = mas->max;
>>>>    done:
>>>> @@ -4429,7 +4393,8 @@ static inline void mas_wr_modify(struct ma_wr_state *wr_mas)
>>>>    	if (new_end == wr_mas->node_end && mas_wr_slot_store(wr_mas))
>>>>    		return;
>>>> -	else if (mas_wr_node_store(wr_mas))
>>>> +
>>>> +	if (mas_wr_node_store(wr_mas, new_end))
>>>>    		return;
>>>>    	if (mas_is_err(mas))
>>>> -- 
>>>> 2.20.1
>>>>
> 

Re: [PATCH 10/10] maple_tree: Simplify and clean up mas_wr_node_store()

[Peng Zhang]

在 2023/5/16 23:52, Liam R. Howlett 写道:
> * Peng Zhang <zhangpeng.00@bytedance.com> [230516 06:53]:
>>
>>
>> 在 2023/5/16 02:58, Liam R. Howlett 写道:
>>> * Peng Zhang <zhangpeng.00@bytedance.com> [230515 09:18]:
>>>> Simplify and clean up mas_wr_node_store(), remove unnecessary code.
>>>
>>> This change fails the userspace testing for me.
>>>
>>>>
>>>> Signed-off-by: Peng Zhang <zhangpeng.00@bytedance.com>
>>>> ---
>>>>    lib/maple_tree.c | 75 +++++++++++++-----------------------------------
>>>>    1 file changed, 20 insertions(+), 55 deletions(-)
>>>>
>>>> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
>>>> index d558e7bcb6da8..ff4aa01cf88b6 100644
>>>> --- a/lib/maple_tree.c
>>>> +++ b/lib/maple_tree.c
>>>> @@ -4066,46 +4066,21 @@ static inline int mas_wr_spanning_store(struct ma_wr_state *wr_mas)
>>>>     *
>>>>     * Return: True if stored, false otherwise
>>>>     */
>>>> -static inline bool mas_wr_node_store(struct ma_wr_state *wr_mas)
>>>> +static inline bool mas_wr_node_store(struct ma_wr_state *wr_mas,
>>>> +				     unsigned char new_end)
>>>>    {
>>>>    	struct ma_state *mas = wr_mas->mas;
>>>>    	void __rcu **dst_slots;
>>>>    	unsigned long *dst_pivots;
>>>>    	unsigned char dst_offset;
>>>> -	unsigned char new_end = wr_mas->node_end;
>>>> -	unsigned char offset;
>>>> -	unsigned char node_slots = mt_slots[wr_mas->type];
>>>>    	struct maple_node reuse, *newnode;
>>>> -	unsigned char copy_size, max_piv = mt_pivots[wr_mas->type];
>>>> +	unsigned char copy_size, node_pivots = mt_pivots[wr_mas->type];
>>>>    	bool in_rcu = mt_in_rcu(mas->tree);
>>>> -	offset = mas->offset;
>>>> -	if (mas->last == wr_mas->r_max) {
>>>> -		/* runs right to the end of the node */
>>>> -		if (mas->last == mas->max)
>>>> -			new_end = offset;
>>>> -		/* don't copy this offset */
> 
> Can you re-add the comments that you removed?  I know the code was more
> lines, but the comments really help follow things through on what is
> going on.
> 
>>>> +	if (mas->last == wr_mas->end_piv)
>>>>    		wr_mas->offset_end++;
>> I guess there is a problem here? If we modify wr_mas->offset_end,
>> but this function fails to try the fast path, it will enter the
>> slow path with the modified offset_end. But it also has this
>> problem in the previous version.
> 
> I don't think we can enter the slow path if this is true.  We must have
> enough room, right?
> 
>>
>> I applied this patch to linux-next/master but it passed the
>> userspace tests. I need more information to confirm what the
>> problem is.
> 
> The failure was pretty consistent for me so I thought it wouldn't be an
> issue reproducing.  I tested against mm-unstable and it happened every
> time I ran the whole patch set yesterday.  Today is a different story
> and it isn't happening for me now.
> 
> Here is the failure log:
> 
> $ CC=gcc make maple && LSAN_OPTIONS="report_objects=1" ./maple
> gcc  -O2 -g -Wall -I. -I../../include -g -Og -Wall -D_LGPL_SOURCE -fsanitize=address -fsanitize=undefined   -c -o maple.o maple.c
> gcc -fsanitize=address -fsanitize=undefined  maple.o xarray.o radix-tree.o idr.o linux.o test.o find_bit.o bitmap.o slab.o  -lpthread -lurcu -o maple
> CC=gcc make maple  5.10s user 0.18s system 99% cpu 5.283 total
> maple_tree(0x7ffea7d35b00) flags 0, height 0 root (nil)
> 0: (nil)
> maple_tree(0x7ffea7d35b00) flags 0, height 0 root 0x1
> 0: value 0 (0x0) [0x1]
> maple_tree(0x7ffea7d35b00) flags 0, height 0 root 0x61500000010c
> 0: 0x61500000010c
> 0x61c000737100[14] should not have entry 0xfeadfeffe001
> BUG at mas_validate_limits:7110 (1)
> maple_tree(0x7ffea7d35b00) flags D, height 3 root 0x61e00099551e
> 
> ....<lots of tree stuff>...
>        7f56ecffa000-7f56ecffafff: value 140011320090624 (0x7f56ecffa000) [0xfeadd9ff4001]
>      7f56ecffb000-7f56efffffff: node 0x61e000989500 depth 2 type 1 parent 0x61c000736916 contents: 0xfeadd9ff6001 7F56ED7FAFFF 0xfeaddaff6001 7F56ED7FBFFF 0xfeaddaff8001 7F56EDFFBFFF 0xfeaddbff8001 7F56EDFFCFFF 0xfeaddbffa001 7F56EE7FCFFF 0xfeaddcffa001 7F56EE7FDFFF 0xfeaddcffc001 7F56EEFFDFFF 0xfeadddffc001 7F56EEFFEFFF 0xfeadddffe001 7F56EF7FEFFF 0xfeaddeffe001 7F56EF7FFFFF 0xfeaddf000001 7F56EFFFFFFF (nil) 0 (nil) 0 (nil) 0 (nil) 0 0xa
>        7f56ecffb000-7f56ed7fafff: value 140011320094720 (0x7f56ecffb000) [0xfeadd9ff6001]
>        7f56ed7fb000-7f56ed7fbfff: value 140011328483328 (0x7f56ed7fb000) [0xfeaddaff6001]
>        7f56ed7fc000-7f56edffbfff: value 140011328487424 (0x7f56ed7fc000) [0xfeaddaff8001]
>        7f56edffc000-7f56edffcfff: value 140011336876032 (0x7f56edffc000) [0xfeaddbff8001]
>        7f56edffd000-7f56ee7fcfff: value 140011336880128 (0x7f56edffd000) [0xfeaddbffa001]
>        7f56ee7fd000-7f56ee7fdfff: value 140011345268736 (0x7f56ee7fd000) [0xfeaddcffa001]
>        7f56ee7fe000-7f56eeffdfff: value 140011345272832 (0x7f56ee7fe000) [0xfeaddcffc001]
>        7f56eeffe000-7f56eeffefff: value 140011353661440 (0x7f56eeffe000) [0xfeadddffc001]
>        7f56eefff000-7f56ef7fefff: value 140011353665536 (0x7f56eefff000) [0xfeadddffe001]
>        7f56ef7ff000-7f56ef7fffff: value 140011362054144 (0x7f56ef7ff000) [0xfeaddeffe001]
>        7f56ef800000-7f56efffffff: value 140011362058240 (0x7f56ef800000) [0xfeaddf000001]
>      7f56f0000000-7f56ffffffff: node 0x61c000737100 depth 2 type 1 parent 0x61c00073691e contents: 0xfeade0000001 7F56F0020FFF 0xfeade0042001 7F56F3FFFFFF (nil) 7F56F5FFBFFF 0xfeadebff8001 7F56F5FFCFFF 0xfeadebffa001 7F56F67FCFFF 0xfeadecffa001 7F56F67FDFFF 0xfeadecffc001 7F56F6FFDFFF 0xfeadedffc001 7F56F6FFEFFF 0xfeadedffe001 7F56F7FFFFFF 0xfeadf0000001 7F56F8020FFF 0xfeadf0042001 7F56FBFFFFFF (nil) 7F56FE7FCFFF 0xfeadfcffa001 7F56FE7FDFFF 0xfeadfcffc001 7F56FFFFFFFF 0xfeadfeffe001 7F56FFFFFFFF 0xe
>        7f56f0000000-7f56f0020fff: value 140011370446848 (0x7f56f0000000) [0xfeade0000001]
>        7f56f0021000-7f56f3ffffff: value 140011370582016 (0x7f56f0021000) [0xfeade0042001]
>        7f56f4000000-7f56f5ffbfff: (nil)
>        7f56f5ffc000-7f56f5ffcfff: value 140011471093760 (0x7f56f5ffc000) [0xfeadebff8001]
>        7f56f5ffd000-7f56f67fcfff: value 140011471097856 (0x7f56f5ffd000) [0xfeadebffa001]
>        7f56f67fd000-7f56f67fdfff: value 140011479486464 (0x7f56f67fd000) [0xfeadecffa001]
>        7f56f67fe000-7f56f6ffdfff: value 140011479490560 (0x7f56f67fe000) [0xfeadecffc001]
>        7f56f6ffe000-7f56f6ffefff: value 140011487879168 (0x7f56f6ffe000) [0xfeadedffc001]
>        7f56f6fff000-7f56f7ffffff: value 140011487883264 (0x7f56f6fff000) [0xfeadedffe001]
>        7f56f8000000-7f56f8020fff: value 140011504664576 (0x7f56f8000000) [0xfeadf0000001]
>        7f56f8021000-7f56fbffffff: value 140011504799744 (0x7f56f8021000) [0xfeadf0042001]
>        7f56fc000000-7f56fe7fcfff: (nil)
>        7f56fe7fd000-7f56fe7fdfff: value 140011613704192 (0x7f56fe7fd000) [0xfeadfcffa001]
>        7f56fe7fe000-7f56ffffffff: value 140011613708288 (0x7f56fe7fe000) [0xfeadfcffc001]
>      7f5700000000-7f570c7f9fff: node 0x61c000737900 depth 2 type 1 parent 0x61c000736926 contents: 0xfeae00000001 7F5700020FFF 0xfeae00042001 7F5703FFFFFF (nil) 7F57047F8FFF 0xfeae08ff2001 7F5706FFDFFF 0xfeae0dffc001 7F5706FFEFFF 0xfeae0dffe001 7F57077FEFFF 0xfeae0effe001 7F57077FFFFF 0xfeae0f000001 7F5707FFFFFF 0xfeae10000001 7F5708020FFF 0xfeae10042001 7F570BFFFFFF (nil) 7F570C7F8FFF 0xfeae18ff2001 7F570C7F9FFF (nil) 0 (nil) 0 (nil) 0 0xb
> 
> ...<lots more tree stuff>...
> 
> Pass: 609373594 Run:609373595
> maple: ../../../lib/maple_tree.c:7110: mas_validate_limits: Assertion `0' failed.
> [1]    855591 IOT instruction (core dumped)  LSAN_OPTIONS="report_objects=1" ./maple
> LSAN_OPTIONS="report_objects=1" ./maple  128.63s user 66.12s system 444% cpu 43.818 total
> 
> The middle node in that output has the issue.  If you notice that slot
> 13 and 14 have the maximum limit here (7F56FFFFFFFF) so the verbose
> output of the last value/line is not printed.
> 
> The line "0x61c000737100[14] should not have entry 0xfeadfeffe001" is
> telling us that there is a value beyond what is expected, and it is at
> slot 14 of that node.
> 
> A bit of context for the test may help.  During the development, I was
> seeing odd errors and discovered that I was not clearing old data from
> free areas of a node sometimes.  It was not detected because the maximum
> value of a node is hit, until another modification caused that data to
> be re-introduced into the tree.  This test detects data beyond what is
> expected to be the end of the node.
> 
> This would also happen if you copy too far, but that shouldn't be
> intermittent, assuming the test is okay.
> 
> I re-tested today and it isn't happening for me now.  This is probably
> an RCU error that is intermittent.  The problem may not even be in this
> patch - if it is RCU it probably is not this patch.  It seemed to fail
> consistently on this patch - and I reverted the previous patch and also
> saw the failure because I suspected it had a potential RCU issue, which
> you pointed out was not an issue.  I wouldn't expect the issue to be
> this patch because we use a new node in RCU mode, so the node with data
> beyond the end would be in the tree for a longer time.
> 
> The failures I saw were always the same.
> 
> Could this be an append operation caught by RCU?  It might just be a
> test issue and your updates change the timing?
I may know why it fails. I don't know if this fix patch[1] was
applied to maple_tree when you tested. I revert this patch and
the same problem occurs. This is because wr_mas->end_piv may
be a wrong value without this fix patch, and then I used this
wrong value to cause the failure. Maybe in your failed tests,
this fix patch was not applied, and in your successful tests,
this fix patch was applied.

[1] 
https://lore.kernel.org/lkml/20230506024752.2550-1-zhangpeng.00@bytedance.com/
> 
>>
>> Thanks.
>>
>>>> -	} else if (mas->last < wr_mas->r_max) {
>>>> -		/* new range ends in this range */
>>>> -		if (unlikely(wr_mas->r_max == ULONG_MAX))
>>>> -			mas_bulk_rebalance(mas, wr_mas->node_end, wr_mas->type);
>>>> -
>>>> -		new_end++;
>>>> -	} else {
>>>> -		if (wr_mas->end_piv == mas->last)
>>>> -			wr_mas->offset_end++;
>>>> -
>>>> -		new_end -= wr_mas->offset_end - offset - 1;
>>>> -	}
>>>> -
>>>> -	/* new range starts within a range */
>>>> -	if (wr_mas->r_min < mas->index)
>>>> -		new_end++;
>>>> -
>>>> -	/* Not enough room */
>>>> -	if (new_end >= node_slots)
>>>> -		return false;
>>>> +	else if (unlikely(wr_mas->r_max == ULONG_MAX))
>>>> +		mas_bulk_rebalance(mas, wr_mas->node_end, wr_mas->type);
>>>>    	/* Not enough data. */
>>>>    	if (!mte_is_root(mas->node) && (new_end <= mt_min_slots[wr_mas->type]) &&
>>>> @@ -4128,47 +4103,36 @@ static inline bool mas_wr_node_store(struct ma_wr_state *wr_mas)
>>>>    	dst_pivots = ma_pivots(newnode, wr_mas->type);
>>>>    	dst_slots = ma_slots(newnode, wr_mas->type);
>>>>    	/* Copy from start to insert point */
>>>> -	memcpy(dst_pivots, wr_mas->pivots, sizeof(unsigned long) * (offset + 1));
>>>> -	memcpy(dst_slots, wr_mas->slots, sizeof(void *) * (offset + 1));
>>>> -	dst_offset = offset;
>>>> +	memcpy(dst_pivots, wr_mas->pivots, sizeof(unsigned long) * mas->offset);
>>>> +	memcpy(dst_slots, wr_mas->slots, sizeof(void *) * mas->offset);
>>>>    	/* Handle insert of new range starting after old range */
>>>>    	if (wr_mas->r_min < mas->index) {
>>>> -		mas->offset++;
>>>> -		rcu_assign_pointer(dst_slots[dst_offset], wr_mas->content);
>>>> -		dst_pivots[dst_offset++] = mas->index - 1;
>>>> +		rcu_assign_pointer(dst_slots[mas->offset], wr_mas->content);
>>>> +		dst_pivots[mas->offset++] = mas->index - 1;
>>>>    	}
>>>>    	/* Store the new entry and range end. */
>>>> -	if (dst_offset < max_piv)
>>>> -		dst_pivots[dst_offset] = mas->last;
>>>> -	mas->offset = dst_offset;
>>>> -	rcu_assign_pointer(dst_slots[dst_offset], wr_mas->entry);
>>>> +	if (mas->offset < node_pivots)
>>>> +		dst_pivots[mas->offset] = mas->last;
>>>> +	rcu_assign_pointer(dst_slots[mas->offset], wr_mas->entry);
>>>>    	/*
>>>>    	 * this range wrote to the end of the node or it overwrote the rest of
>>>>    	 * the data
>>>>    	 */
>>>> -	if (wr_mas->offset_end > wr_mas->node_end || mas->last >= mas->max) {
>>>> -		new_end = dst_offset;
>>>> +	if (wr_mas->offset_end > wr_mas->node_end)
>>>>    		goto done;
>>>> -	}
>>>> -	dst_offset++;
>>>> +	dst_offset = mas->offset + 1;
>>>>    	/* Copy to the end of node if necessary. */
>>>>    	copy_size = wr_mas->node_end - wr_mas->offset_end + 1;
>>>>    	memcpy(dst_slots + dst_offset, wr_mas->slots + wr_mas->offset_end,
>>>>    	       sizeof(void *) * copy_size);
>>>> -	if (dst_offset < max_piv) {
>>>> -		if (copy_size > max_piv - dst_offset)
>>>> -			copy_size = max_piv - dst_offset;
>>>> +	memcpy(dst_pivots + dst_offset, wr_mas->pivots + wr_mas->offset_end,
>>>> +	       sizeof(unsigned long) * (copy_size - 1));
>>>> -		memcpy(dst_pivots + dst_offset,
>>>> -		       wr_mas->pivots + wr_mas->offset_end,
>>>> -		       sizeof(unsigned long) * copy_size);
>>>> -	}
>>>> -
>>>> -	if ((wr_mas->node_end == node_slots - 1) && (new_end < node_slots - 1))
>>>> +	if (new_end < node_pivots)
>>>>    		dst_pivots[new_end] = mas->max;
>>>>    done:
>>>> @@ -4429,7 +4393,8 @@ static inline void mas_wr_modify(struct ma_wr_state *wr_mas)
>>>>    	if (new_end == wr_mas->node_end && mas_wr_slot_store(wr_mas))
>>>>    		return;
>>>> -	else if (mas_wr_node_store(wr_mas))
>>>> +
>>>> +	if (mas_wr_node_store(wr_mas, new_end))
>>>>    		return;
>>>>    	if (mas_is_err(mas))
>>>> -- 
>>>> 2.20.1
>>>>
>