[PATCH v2 00/10] Clean ups for maple tree

[PATCH v2 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.

0006-0009 - Make mas_wr_modify() and its subfunctions clearer. Make the
            store operation of maple tree more efficient in some cases.

Thanks Liam and Matthew.

Changes since v1:
 - Rework mtree_alloc_{range,rrange}() instead of removing it. [01/10]
 - Fix the arguments to __must_hold() instead of removing it. [03/10]
 - Keep the fast path. Expand the compact code. [04/10]
 - Drop "maple_tree: Wrap the replace operation with an inline
   function.". [v1 06/10]
 - Remove some comments. [07/10] [08/10]
 - Avoid modifying wr_mas->offset_end in mas_wr_modify(). [09/10]
 - Add a patch to relocate mas_empty_area_rev(). [10/10]

Peng Zhang (10):
  maple_tree: Rework mtree_alloc_{range,rrange}()
  maple_tree: Drop mas_{rev_}alloc() and mas_fill_gap()
  maple_tree: Fix the arguments to __must_hold()
  maple_tree: Simplify mas_is_span_wr()
  maple_tree: Make the code symmetrical in mas_wr_extend_null()
  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()
  maple_tree: Relocate the declaration of mas_empty_area_rev().

 include/linux/maple_tree.h |  12 +-
 lib/maple_tree.c           | 455 +++++++++++++------------------------
 2 files changed, 160 insertions(+), 307 deletions(-)

-- 
2.20.1

[PATCH v2 01/10] maple_tree: Rework mtree_alloc_{range,rrange}()

[Peng Zhang]

Use mas_empty_area{_rev}() to refactor mtree_alloc_{range,rrange}()

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

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index 4eb220008f72..e1820e90f167 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -6493,32 +6493,31 @@ int mtree_alloc_range(struct maple_tree *mt, unsigned long *startp,
 {
 	int ret = 0;
 
-	MA_STATE(mas, mt, min, min);
+	MA_STATE(mas, mt, 0, 0);
 	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;
-
+	ret = mas_empty_area(&mas, min, max, size);
+	if (!ret) {
+		mas_insert(&mas, entry);
+		/*
+		 * mas_nomem() may release the lock, causing the allocated area
+		 * to be unavailable, so try to allocate a free area again.
+		 */
+		if (mas_nomem(&mas, gfp))
+			goto retry;
+	}
 	mtree_unlock(mt);
+	if (!ret) {
+		if (mas_is_err(&mas))
+			return xa_err(mas.node);
+		*startp = mas.index;
+	}
 	return ret;
 }
 EXPORT_SYMBOL(mtree_alloc_range);
@@ -6529,29 +6528,31 @@ int mtree_alloc_rrange(struct maple_tree *mt, unsigned long *startp,
 {
 	int ret = 0;
 
-	MA_STATE(mas, mt, min, max - size + 1);
+	MA_STATE(mas, mt, 0, 0);
 	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;
-
+	ret = mas_empty_area_rev(&mas, min, max, size);
+	if (!ret) {
+		mas_insert(&mas, entry);
+		/*
+		 * mas_nomem() may release the lock, causing the allocated area
+		 * to be unavailable, so try to allocate a free area again.
+		 */
+		if (mas_nomem(&mas, gfp))
+			goto retry;
+	}
 	mtree_unlock(mt);
+	if (!ret) {
+		if (mas_is_err(&mas))
+			return xa_err(mas.node);
+		*startp = mas.index;
+	}
 	return ret;
 }
 EXPORT_SYMBOL(mtree_alloc_rrange);
-- 
2.20.1

[PATCH v2 02/10] maple_tree: Drop mas_{rev_}alloc() and mas_fill_gap()

[Peng Zhang]

mas_{rev_}alloc() and mas_fill_gap() are useless, delete them.

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

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index e1820e90f167..c8176f360dc2 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
-- 
2.20.1

[PATCH v2 03/10] maple_tree: Fix the arguments to __must_hold()

[Peng Zhang]

Fix the arguments to __must_hold() to make sparse work.

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

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index c8176f360dc2..bec9906b0c8c 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -1752,7 +1752,7 @@ 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)
+	__must_hold(mas->tree->ma_lock)
 {
 	struct maple_node *mn = mas_mn(mas);
 	struct maple_enode *old_enode;
@@ -1792,7 +1792,7 @@ 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)
+	__must_hold(mas->tree->ma_lock)
 {
 	enum maple_type mt;
 	unsigned char offset;
@@ -6204,7 +6204,7 @@ 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)
+	__must_hold(mas->tree->ma_lock)
 {
 	if (likely(mas->node != MA_ERROR(-ENOMEM))) {
 		mas_destroy(mas);
-- 
2.20.1

[PATCH v2 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 | 42 ++++++++++++++----------------------------
 1 file changed, 14 insertions(+), 28 deletions(-)

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index bec9906b0c8c..82dccc660889 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -3728,43 +3728,29 @@ static inline void mas_store_root(struct ma_state *mas, void *entry)
  */
 static bool mas_is_span_wr(struct ma_wr_state *wr_mas)
 {
-	unsigned long max;
+	unsigned long max = wr_mas->r_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)
+	/* Contained in this pivot, fast path */
+	if (last < max)
 		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;
-
+	if (ma_is_leaf(type))
+		max = wr_mas->mas->max;
+	if (last < max) {
+		/* Contained in this pivot or this leaf node */
+		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 v2 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>
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 82dccc660889..f881bce1a9f6 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -4262,19 +4262,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 v2 06/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 f881bce1a9f6..3b9d227f3d7d 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -4294,6 +4294,20 @@ static inline void mas_wr_extend_null(struct ma_wr_state *wr_mas)
 	}
 }
 
+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;
@@ -4349,9 +4363,8 @@ 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;
 
 	/* Direct replacement */
 	if (wr_mas->r_min == mas->index && wr_mas->r_max == mas->last) {
@@ -4361,17 +4374,15 @@ static inline void mas_wr_modify(struct ma_wr_state *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 v2 07/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 | 33 ++++++++++++++++++++-------------
 1 file changed, 20 insertions(+), 13 deletions(-)

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index 3b9d227f3d7d..bbe4c6f2858c 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -4308,6 +4308,12 @@ 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
+ */
 static inline bool mas_wr_append(struct ma_wr_state *wr_mas)
 {
 	unsigned char end = wr_mas->node_end;
@@ -4315,7 +4321,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)) {
+		/* Append to end of range */
 		if (new_end < node_pivots)
 			wr_mas->pivots[new_end] = wr_mas->pivots[end];
 
@@ -4323,13 +4333,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)) {
+		/* Append to start of range */
 		if (new_end < node_pivots)
 			wr_mas->pivots[new_end] = wr_mas->pivots[end];
 
@@ -4339,10 +4346,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;
 }
 
 /*
@@ -4382,12 +4392,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 v2 08/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 | 59 ++++++++++++++++++++----------------------------
 1 file changed, 24 insertions(+), 35 deletions(-)

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index bbe4c6f2858c..25a8b7d5d598 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -4200,49 +4200,38 @@ static inline bool mas_wr_node_store(struct ma_wr_state *wr_mas)
 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)))
+	if (offset_end - offset != 1)
 		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)
-		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) {
+		/* Overwriting the range and over a part of the next range. */
+		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) {
+		/* Overwriting a part of the range and over the next range */
+		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;
 }
 
@@ -4396,7 +4385,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 v2 09/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 | 87 +++++++++++++++---------------------------------
 1 file changed, 26 insertions(+), 61 deletions(-)

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index 25a8b7d5d598..b86001ad4632 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -4072,52 +4072,27 @@ 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];
+	unsigned char dst_offset, offset_end = wr_mas->offset_end;
 	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 */
-		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;
-
-	/* Not enough data. */
+	/* Check if there is enough data. The room is enough. */
 	if (!mte_is_root(mas->node) && (new_end <= mt_min_slots[wr_mas->type]) &&
 	    !(mas->mas_flags & MA_STATE_BULK))
 		return false;
 
+	if (mas->last == wr_mas->end_piv)
+		offset_end++; /* don't copy this offset */
+	else if (unlikely(wr_mas->r_max == ULONG_MAX))
+		mas_bulk_rebalance(mas, wr_mas->node_end, wr_mas->type);
+
 	/* set up node. */
 	if (in_rcu) {
 		mas_node_count(mas, 1);
@@ -4134,47 +4109,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 (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,
+	copy_size = wr_mas->node_end - offset_end + 1;
+	memcpy(dst_slots + dst_offset, wr_mas->slots + 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);
-	}
+	memcpy(dst_pivots + dst_offset, wr_mas->pivots + offset_end,
+	       sizeof(unsigned long) * (copy_size - 1));
 
-	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:
@@ -4387,7 +4351,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

[PATCH v2 10/10] maple_tree: Relocate the declaration of mas_empty_area_rev().

[Peng Zhang]

Relocate the declaration of mas_empty_area_rev() so that
mas_empty_area() and mas_empty_area_rev() are together.

Signed-off-by: Peng Zhang <zhangpeng.00@bytedance.com>
---
 include/linux/maple_tree.h | 12 ++++++------
 1 file changed, 6 insertions(+), 6 deletions(-)

diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h
index 85559a34a098..c4681cb8414f 100644
--- a/include/linux/maple_tree.h
+++ b/include/linux/maple_tree.h
@@ -474,6 +474,12 @@ void *mas_next_range(struct ma_state *mas, unsigned long max);
 
 int mas_empty_area(struct ma_state *mas, unsigned long min, unsigned long max,
 		   unsigned long size);
+/*
+ * This finds an empty area from the highest address to the lowest.
+ * AKA "Topdown" version,
+ */
+int mas_empty_area_rev(struct ma_state *mas, unsigned long min,
+		       unsigned long max, unsigned long size);
 
 static inline void mas_init(struct ma_state *mas, struct maple_tree *tree,
 			    unsigned long addr)
@@ -497,12 +503,6 @@ static inline bool mas_is_paused(const struct ma_state *mas)
 	return mas->node == MAS_PAUSE;
 }
 
-/*
- * This finds an empty area from the highest address to the lowest.
- * AKA "Topdown" version,
- */
-int mas_empty_area_rev(struct ma_state *mas, unsigned long min,
-		       unsigned long max, unsigned long size);
 /**
  * mas_reset() - Reset a Maple Tree operation state.
  * @mas: Maple Tree operation state.
-- 
2.20.1

Re: [PATCH v2 01/10] maple_tree: Rework mtree_alloc_{range,rrange}()

[Liam R. Howlett]

* Peng Zhang <zhangpeng.00@bytedance.com> [230517 04:58]:
> Use mas_empty_area{_rev}() to refactor mtree_alloc_{range,rrange}()
> 
> Signed-off-by: Peng Zhang <zhangpeng.00@bytedance.com>
> ---
>  lib/maple_tree.c | 63 ++++++++++++++++++++++++------------------------
>  1 file changed, 32 insertions(+), 31 deletions(-)
> 
> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> index 4eb220008f72..e1820e90f167 100644
> --- a/lib/maple_tree.c
> +++ b/lib/maple_tree.c
> @@ -6493,32 +6493,31 @@ int mtree_alloc_range(struct maple_tree *mt, unsigned long *startp,
>  {
>  	int ret = 0;
>  
> -	MA_STATE(mas, mt, min, min);
> +	MA_STATE(mas, mt, 0, 0);
>  	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;
> -
> +	ret = mas_empty_area(&mas, min, max, size);
> +	if (!ret) {
> +		mas_insert(&mas, entry);
> +		/*
> +		 * mas_nomem() may release the lock, causing the allocated area
> +		 * to be unavailable, so try to allocate a free area again.
> +		 */
> +		if (mas_nomem(&mas, gfp))
> +			goto retry;
> +	}
>  	mtree_unlock(mt);
> +	if (!ret) {

Checking for a mas_is_err() should probably be outside if (!ret)
statement.  If mas_insert() returns something besides ENOMEM, we will
not detect the error.  I'm not sure if this is possible today since this
should never return an -EEXISTS, but having it this way doesn't add much
to the overhead.

> +		if (mas_is_err(&mas))
> +			return xa_err(mas.node);
> +		*startp = mas.index;
> +	}
>  	return ret;
>  }
>  EXPORT_SYMBOL(mtree_alloc_range);
> @@ -6529,29 +6528,31 @@ int mtree_alloc_rrange(struct maple_tree *mt, unsigned long *startp,
>  {
>  	int ret = 0;
>  
> -	MA_STATE(mas, mt, min, max - size + 1);
> +	MA_STATE(mas, mt, 0, 0);
>  	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;
> -
> +	ret = mas_empty_area_rev(&mas, min, max, size);
> +	if (!ret) {
> +		mas_insert(&mas, entry);
> +		/*
> +		 * mas_nomem() may release the lock, causing the allocated area
> +		 * to be unavailable, so try to allocate a free area again.
> +		 */
> +		if (mas_nomem(&mas, gfp))
> +			goto retry;
> +	}
>  	mtree_unlock(mt);
> +	if (!ret) {

Same here.

> +		if (mas_is_err(&mas))
> +			return xa_err(mas.node);
> +		*startp = mas.index;
> +	}
>  	return ret;
>  }
>  EXPORT_SYMBOL(mtree_alloc_rrange);
> -- 
> 2.20.1
> 

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

[Liam R. Howlett]

* Peng Zhang <zhangpeng.00@bytedance.com> [230517 04:59]:
> Make the code for detecting spanning writes more concise.
> 
> Signed-off-by: Peng Zhang <zhangpeng.00@bytedance.com>
> ---
>  lib/maple_tree.c | 42 ++++++++++++++----------------------------
>  1 file changed, 14 insertions(+), 28 deletions(-)
> 
> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> index bec9906b0c8c..82dccc660889 100644
> --- a/lib/maple_tree.c
> +++ b/lib/maple_tree.c
> @@ -3728,43 +3728,29 @@ static inline void mas_store_root(struct ma_state *mas, void *entry)
>   */
>  static bool mas_is_span_wr(struct ma_wr_state *wr_mas)
>  {
> -	unsigned long max;
> +	unsigned long max = wr_mas->r_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)
> +	/* Contained in this pivot, fast path */

Thanks for adding the fast path comment here.

> +	if (last < max)
>  		return false;
> -

Please have new lines after an if statement

> -	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;
> -
> +	if (ma_is_leaf(type))
> +		max = wr_mas->mas->max;

New line here too

> +	if (last < max) {
> +		/* Contained in this pivot or this leaf node */
> +		return false;

Since you have the last < max check earlier, this is only needed in the
if(mas_is_leaf()) statement above.  Making the below else if() an if()
should work.

> +	} 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 v2 06/10] maple_tree: Add mas_wr_new_end() to calculate new_end accurately

[Liam R. Howlett]

* Peng Zhang <zhangpeng.00@bytedance.com> [230517 04:59]:
> 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 f881bce1a9f6..3b9d227f3d7d 100644
> --- a/lib/maple_tree.c
> +++ b/lib/maple_tree.c
> @@ -4294,6 +4294,20 @@ static inline void mas_wr_extend_null(struct ma_wr_state *wr_mas)
>  	}
>  }
>  
> +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--;

nit: new line missing here

> +	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;
> @@ -4349,9 +4363,8 @@ 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;
>  
>  	/* Direct replacement */
>  	if (wr_mas->r_min == mas->index && wr_mas->r_max == mas->last) {
> @@ -4361,17 +4374,15 @@ static inline void mas_wr_modify(struct ma_wr_state *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
> 

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

[Liam R. Howlett]

* Peng Zhang <zhangpeng.00@bytedance.com> [230517 04:59]:
> 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 | 33 ++++++++++++++++++++-------------
>  1 file changed, 20 insertions(+), 13 deletions(-)
> 
> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> index 3b9d227f3d7d..bbe4c6f2858c 100644
> --- a/lib/maple_tree.c
> +++ b/lib/maple_tree.c
> @@ -4308,6 +4308,12 @@ 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
> + */
>  static inline bool mas_wr_append(struct ma_wr_state *wr_mas)
>  {
>  	unsigned char end = wr_mas->node_end;
> @@ -4315,7 +4321,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)) {
> +		/* Append to end of range */
>  		if (new_end < node_pivots)
>  			wr_mas->pivots[new_end] = wr_mas->pivots[end];
>  
> @@ -4323,13 +4333,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)) {
> +		/* Append to start of range */
>  		if (new_end < node_pivots)
>  			wr_mas->pivots[new_end] = wr_mas->pivots[end];
>  
> @@ -4339,10 +4346,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;

I don't think we can get here with your changes, what do you think?  If
so, we can move the metadata setting to the outside of the if/else.  I
checked by adding a BUG_ON() and the test code never gets here.

My thinking is, we know offset == node_end and new_end == node_end + 1..
so we must be inserting into the last slot and only adding one entry.

>  	}
>  
> -	return false;
> +	if (!wr_mas->content || !wr_mas->entry)
> +		mas_update_gap(mas);
> +	return  true;
>  }
>  
>  /*
> @@ -4382,12 +4392,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 v2 08/10] maple_tree: Rework mas_wr_slot_store() to be cleaner and more efficient.

[Liam R. Howlett]

* Peng Zhang <zhangpeng.00@bytedance.com> [230517 04:59]:
> 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 | 59 ++++++++++++++++++++----------------------------
>  1 file changed, 24 insertions(+), 35 deletions(-)
> 
> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> index bbe4c6f2858c..25a8b7d5d598 100644
> --- a/lib/maple_tree.c
> +++ b/lib/maple_tree.c
> @@ -4200,49 +4200,38 @@ static inline bool mas_wr_node_store(struct ma_wr_state *wr_mas)
>  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)))
> +	if (offset_end - offset != 1)
>  		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)
> -		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) {
> +		/* Overwriting the range and over a part of the next range. */
> +		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) {
> +		/* Overwriting a part of the range and over the next range */
> +		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;

Again here, I think you have already verified this will be a slot store
by offset_end - offset == 1 and new_end == wr_mas->node_end.

The checking of the slots for the gap could be moved outside the
statements.  WDYT?

> +	}
>  
> -	/* 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;
>  }
>  
> @@ -4396,7 +4385,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 v2 01/10] maple_tree: Rework mtree_alloc_{range,rrange}()

[Peng Zhang]

在 2023/5/18 02:17, Liam R. Howlett 写道:
> * Peng Zhang <zhangpeng.00@bytedance.com> [230517 04:58]:
>> Use mas_empty_area{_rev}() to refactor mtree_alloc_{range,rrange}()
>>
>> Signed-off-by: Peng Zhang <zhangpeng.00@bytedance.com>
>> ---
>>   lib/maple_tree.c | 63 ++++++++++++++++++++++++------------------------
>>   1 file changed, 32 insertions(+), 31 deletions(-)
>>
>> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
>> index 4eb220008f72..e1820e90f167 100644
>> --- a/lib/maple_tree.c
>> +++ b/lib/maple_tree.c
>> @@ -6493,32 +6493,31 @@ int mtree_alloc_range(struct maple_tree *mt, unsigned long *startp,
>>   {
>>   	int ret = 0;
>>   
>> -	MA_STATE(mas, mt, min, min);
>> +	MA_STATE(mas, mt, 0, 0);
>>   	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;
>> -
>> +	ret = mas_empty_area(&mas, min, max, size);
>> +	if (!ret) {
>> +		mas_insert(&mas, entry);
>> +		/*
>> +		 * mas_nomem() may release the lock, causing the allocated area
>> +		 * to be unavailable, so try to allocate a free area again.
>> +		 */
>> +		if (mas_nomem(&mas, gfp))
>> +			goto retry;
>> +	}
>>   	mtree_unlock(mt);
>> +	if (!ret) {
> 
> Checking for a mas_is_err() should probably be outside if (!ret)
> statement.  If mas_insert() returns something besides ENOMEM, we will
> not detect the error.  I'm not sure if this is possible today since this
> should never return an -EEXISTS, but having it this way doesn't add much
> to the overhead.
I don't think there will be error that can't be detected here.
In fact, there are two sources of errors:

1. mas_empty_area(), the error number is in the variable ret,
    and may also be in mas->node, but ret must contain all errors.

2. mas_insert(), the error number is in mas->node

When we check errors, we should first check errors from
mas_empty_area(). If there is no error in mas_empty_area(), we
will check errors from mas_insert().
So, mas_is_err() is inside the if (!ret) statement, no problem here.

Of course, even if mas_insert() returns -EEXISTS, it can be detected
under the current encoding, because "if (!ret)" is true in this case.
But I don't think this can happen, if it happens, it's a bug of maple
tree.

I don't think it's good to put mas_is_err() outside, because the error
number stored in mas->node may come from mas_empty_area(). We should use
the ret variable to detect the error from mas_empty_area() first.
> 
>> +		if (mas_is_err(&mas))
>> +			return xa_err(mas.node);
>> +		*startp = mas.index;
>> +	}
>>   	return ret;
>>   }
>>   EXPORT_SYMBOL(mtree_alloc_range);
>> @@ -6529,29 +6528,31 @@ int mtree_alloc_rrange(struct maple_tree *mt, unsigned long *startp,
>>   {
>>   	int ret = 0;
>>   
>> -	MA_STATE(mas, mt, min, max - size + 1);
>> +	MA_STATE(mas, mt, 0, 0);
>>   	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;
>> -
>> +	ret = mas_empty_area_rev(&mas, min, max, size);
>> +	if (!ret) {
>> +		mas_insert(&mas, entry);
>> +		/*
>> +		 * mas_nomem() may release the lock, causing the allocated area
>> +		 * to be unavailable, so try to allocate a free area again.
>> +		 */
>> +		if (mas_nomem(&mas, gfp))
>> +			goto retry;
>> +	}
>>   	mtree_unlock(mt);
>> +	if (!ret) {
> 
> Same here.
> 
>> +		if (mas_is_err(&mas))
>> +			return xa_err(mas.node);
>> +		*startp = mas.index;
>> +	}
>>   	return ret;
>>   }
>>   EXPORT_SYMBOL(mtree_alloc_rrange);
>> -- 
>> 2.20.1
>>

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

[Peng Zhang]

在 2023/5/18 03:33, Liam R. Howlett 写道:
> * Peng Zhang <zhangpeng.00@bytedance.com> [230517 04:59]:
>> 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 | 33 ++++++++++++++++++++-------------
>>   1 file changed, 20 insertions(+), 13 deletions(-)
>>
>> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
>> index 3b9d227f3d7d..bbe4c6f2858c 100644
>> --- a/lib/maple_tree.c
>> +++ b/lib/maple_tree.c
>> @@ -4308,6 +4308,12 @@ 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
>> + */
>>   static inline bool mas_wr_append(struct ma_wr_state *wr_mas)
>>   {
>>   	unsigned char end = wr_mas->node_end;
>> @@ -4315,7 +4321,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)) {
>> +		/* Append to end of range */
>>   		if (new_end < node_pivots)
>>   			wr_mas->pivots[new_end] = wr_mas->pivots[end];
>>   
>> @@ -4323,13 +4333,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)) {
>> +		/* Append to start of range */
>>   		if (new_end < node_pivots)
>>   			wr_mas->pivots[new_end] = wr_mas->pivots[end];
>>   
>> @@ -4339,10 +4346,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;
> 
> I don't think we can get here with your changes, what do you think?  If
> so, we can move the metadata setting to the outside of the if/else.  I
> checked by adding a BUG_ON() and the test code never gets here.
> 
> My thinking is, we know offset == node_end and new_end == node_end + 1..
> so we must be inserting into the last slot and only adding one entry.
Yes, I'll address this in v3. Thanks.
> 
>>   	}
>>   
>> -	return false;
>> +	if (!wr_mas->content || !wr_mas->entry)
>> +		mas_update_gap(mas);
>> +	return  true;
>>   }
>>   
>>   /*
>> @@ -4382,12 +4392,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 v2 08/10] maple_tree: Rework mas_wr_slot_store() to be cleaner and more efficient.

[Peng Zhang]

在 2023/5/18 06:48, Liam R. Howlett 写道:
> * Peng Zhang <zhangpeng.00@bytedance.com> [230517 04:59]:
>> 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 | 59 ++++++++++++++++++++----------------------------
>>   1 file changed, 24 insertions(+), 35 deletions(-)
>>
>> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
>> index bbe4c6f2858c..25a8b7d5d598 100644
>> --- a/lib/maple_tree.c
>> +++ b/lib/maple_tree.c
>> @@ -4200,49 +4200,38 @@ static inline bool mas_wr_node_store(struct ma_wr_state *wr_mas)
>>   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)))
>> +	if (offset_end - offset != 1)
>>   		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)
>> -		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) {
>> +		/* Overwriting the range and over a part of the next range. */
>> +		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) {
>> +		/* Overwriting a part of the range and over the next range */
>> +		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;
> 
> Again here, I think you have already verified this will be a slot store
> by offset_end - offset == 1 and new_end == wr_mas->node_end.
> 
> The checking of the slots for the gap could be moved outside the
> statements.  WDYT?
Yes, I'll address this in v3. Thanks.
> 
>> +	}
>>   
>> -	/* 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;
>>   }
>>   
>> @@ -4396,7 +4385,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 v2 01/10] maple_tree: Rework mtree_alloc_{range,rrange}()

[Liam R. Howlett]

* Peng Zhang <zhangpeng.00@bytedance.com> [230518 02:10]:
> 
> 
> 在 2023/5/18 02:17, Liam R. Howlett 写道:
> > * Peng Zhang <zhangpeng.00@bytedance.com> [230517 04:58]:
> > > Use mas_empty_area{_rev}() to refactor mtree_alloc_{range,rrange}()
> > > 
> > > Signed-off-by: Peng Zhang <zhangpeng.00@bytedance.com>
> > > ---
> > >   lib/maple_tree.c | 63 ++++++++++++++++++++++++------------------------
> > >   1 file changed, 32 insertions(+), 31 deletions(-)
> > > 
> > > diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> > > index 4eb220008f72..e1820e90f167 100644
> > > --- a/lib/maple_tree.c
> > > +++ b/lib/maple_tree.c
> > > @@ -6493,32 +6493,31 @@ int mtree_alloc_range(struct maple_tree *mt, unsigned long *startp,
> > >   {
> > >   	int ret = 0;
> > > -	MA_STATE(mas, mt, min, min);
> > > +	MA_STATE(mas, mt, 0, 0);
> > >   	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;
> > > -
> > > +	ret = mas_empty_area(&mas, min, max, size);
> > > +	if (!ret) {
> > > +		mas_insert(&mas, entry);
> > > +		/*
> > > +		 * mas_nomem() may release the lock, causing the allocated area
> > > +		 * to be unavailable, so try to allocate a free area again.
> > > +		 */
> > > +		if (mas_nomem(&mas, gfp))
> > > +			goto retry;
> > > +	}
> > >   	mtree_unlock(mt);
> > > +	if (!ret) {
> > 
> > Checking for a mas_is_err() should probably be outside if (!ret)
> > statement.  If mas_insert() returns something besides ENOMEM, we will
> > not detect the error.  I'm not sure if this is possible today since this
> > should never return an -EEXISTS, but having it this way doesn't add much
> > to the overhead.
> I don't think there will be error that can't be detected here.
> In fact, there are two sources of errors:
> 
> 1. mas_empty_area(), the error number is in the variable ret,
>    and may also be in mas->node, but ret must contain all errors.
> 
> 2. mas_insert(), the error number is in mas->node
> 
> When we check errors, we should first check errors from
> mas_empty_area(). If there is no error in mas_empty_area(), we
> will check errors from mas_insert().
> So, mas_is_err() is inside the if (!ret) statement, no problem here.
> 
> Of course, even if mas_insert() returns -EEXISTS, it can be detected
> under the current encoding, because "if (!ret)" is true in this case.
> But I don't think this can happen, if it happens, it's a bug of maple
> tree.

Right, thanks.

> 
> I don't think it's good to put mas_is_err() outside, because the error
> number stored in mas->node may come from mas_empty_area(). We should use
> the ret variable to detect the error from mas_empty_area() first.

Yeah, I would structure it as a 'goto' to undo the locking to avoid the
if (!ret) nesting, and move the unlock to just before the return:

if (ret)
	goto unlock;

...
	*startp = mas.index;

unlock:
	mtree_unlock(mt);
	return ret;

mas_empty_area() is an external interface and so already decodes the
error in the node using mas_is_err(), so this can be dropped completely.

I don't think holding the lock for the one extra assignment will make a
difference.

> > 
> > > +		if (mas_is_err(&mas))
> > > +			return xa_err(mas.node);
> > > +		*startp = mas.index;
> > > +	}
> > >   	return ret;
> > >   }
> > >   EXPORT_SYMBOL(mtree_alloc_range);
> > > @@ -6529,29 +6528,31 @@ int mtree_alloc_rrange(struct maple_tree *mt, unsigned long *startp,
> > >   {
> > >   	int ret = 0;
> > > -	MA_STATE(mas, mt, min, max - size + 1);
> > > +	MA_STATE(mas, mt, 0, 0);
> > >   	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;
> > > -
> > > +	ret = mas_empty_area_rev(&mas, min, max, size);
> > > +	if (!ret) {
> > > +		mas_insert(&mas, entry);
> > > +		/*
> > > +		 * mas_nomem() may release the lock, causing the allocated area
> > > +		 * to be unavailable, so try to allocate a free area again.
> > > +		 */
> > > +		if (mas_nomem(&mas, gfp))
> > > +			goto retry;
> > > +	}
> > >   	mtree_unlock(mt);
> > > +	if (!ret) {
> > 
> > Same here.
> > 
> > > +		if (mas_is_err(&mas))
> > > +			return xa_err(mas.node);
> > > +		*startp = mas.index;
> > > +	}
> > >   	return ret;
> > >   }
> > >   EXPORT_SYMBOL(mtree_alloc_rrange);
> > > -- 
> > > 2.20.1
> > >