[PATCH v2 0/5] Some cleanups of maple tree

[PATCH v2 0/5] Some cleanups of maple tree

[Peng Zhang]

These are some small cleanups of maple tree.

Just to mention, in v1, I forgot to CC LKML, but it has been added in this
version.

Changes since v1:
  - Removed the 'return' statement from [1/5].
  - Made slight modifications to the commit log of [5/5].

v1: http://lists.infradead.org/pipermail/maple-tree/2023-November/003047.html

Peng Zhang (5):
  maple_tree: Move the check forward to avoid static check warning
  maple_tree: Avoid ascending when mas->min is also the parent's minimum
  maple_tree: Remove an unused parameter for ma_meta_end()
  maple_tree: Delete one of the two identical checks
  maple_tree: Simplify mas_leaf_set_meta()

 lib/maple_tree.c | 45 ++++++++++++++-------------------------------
 1 file changed, 14 insertions(+), 31 deletions(-)

-- 
2.20.1

[PATCH v2 1/5] maple_tree: Move the check forward to avoid static check warning

[Peng Zhang]

Put the check for gap before its reference to avoid Smatch static check
warnings. This is not a bug, it's just a validation program. Even with this
change, Smatch may still generate warnings because MT_BUG_ON() doesn't
necessarily stop the program. It may require fixing Smatch itself to avoid
these warnings.

Reported-by: Dan Carpenter <dan.carpenter@linaro.org>
Closes: http://lists.infradead.org/pipermail/maple-tree/2023-November/003046.html
Signed-off-by: Peng Zhang <zhangpeng.00@bytedance.com>
---
 lib/maple_tree.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index aaba453b0d30..067b186202d7 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -7249,6 +7249,7 @@ static void mas_validate_gaps(struct ma_state *mas)
 
 counted:
 	if (mt == maple_arange_64) {
+		MT_BUG_ON(mas->tree, !gaps);
 		offset = ma_meta_gap(node, mt);
 		if (offset > i) {
 			pr_err("gap offset %p[%u] is invalid\n", node, offset);
@@ -7261,7 +7262,6 @@ static void mas_validate_gaps(struct ma_state *mas)
 			MT_BUG_ON(mas->tree, 1);
 		}
 
-		MT_BUG_ON(mas->tree, !gaps);
 		for (i++ ; i < mt_slot_count(mte); i++) {
 			if (gaps[i] != 0) {
 				pr_err("gap %p[%u] beyond node limit != 0\n",
-- 
2.20.1

[PATCH v2 2/5] maple_tree: Avoid ascending when mas->min is also the parent's minimum

[Peng Zhang]

When the child node is the first child of its parent node, mas->min does
not need to be updated. This can reduce the number of ascending times
in some cases.

Signed-off-by: Peng Zhang <zhangpeng.00@bytedance.com>
Reviewed-by: Liam R. Howlett <Liam.Howlett@oracle.com>
---
 lib/maple_tree.c | 8 +++++---
 1 file changed, 5 insertions(+), 3 deletions(-)

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index 067b186202d7..cc928b5f753d 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -1088,14 +1088,16 @@ static int mas_ascend(struct ma_state *mas)
 		return 0;
 	}
 
-	if (!mas->min)
+	min = 0;
+	max = ULONG_MAX;
+	if (!mas->offset) {
+		min = mas->min;
 		set_min = true;
+	}
 
 	if (mas->max == ULONG_MAX)
 		set_max = true;
 
-	min = 0;
-	max = ULONG_MAX;
 	do {
 		p_enode = a_enode;
 		a_type = mas_parent_type(mas, p_enode);
-- 
2.20.1

[PATCH v2 3/5] maple_tree: Remove an unused parameter for ma_meta_end()

[Peng Zhang]

The parameter maple_type is not used, so remove it.

Signed-off-by: Peng Zhang <zhangpeng.00@bytedance.com>
Reviewed-by: Liam R. Howlett <Liam.Howlett@oracle.com>
---
 lib/maple_tree.c | 10 ++++------
 1 file changed, 4 insertions(+), 6 deletions(-)

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index cc928b5f753d..3d894f849e57 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -930,10 +930,8 @@ static inline unsigned char ma_meta_end(struct maple_node *mn,
 /*
  * ma_meta_gap() - Get the largest gap location of a node from the metadata
  * @mn: The maple node
- * @mt: The maple node type
  */
-static inline unsigned char ma_meta_gap(struct maple_node *mn,
-					enum maple_type mt)
+static inline unsigned char ma_meta_gap(struct maple_node *mn)
 {
 	return mn->ma64.meta.gap;
 }
@@ -1587,7 +1585,7 @@ static inline unsigned long mas_max_gap(struct ma_state *mas)
 
 	node = mas_mn(mas);
 	MAS_BUG_ON(mas, mt != maple_arange_64);
-	offset = ma_meta_gap(node, mt);
+	offset = ma_meta_gap(node);
 	gaps = ma_gaps(node, mt);
 	return gaps[offset];
 }
@@ -1618,7 +1616,7 @@ static inline void mas_parent_gap(struct ma_state *mas, unsigned char offset,
 
 ascend:
 	MAS_BUG_ON(mas, pmt != maple_arange_64);
-	meta_offset = ma_meta_gap(pnode, pmt);
+	meta_offset = ma_meta_gap(pnode);
 	meta_gap = pgaps[meta_offset];
 
 	pgaps[offset] = new;
@@ -7252,7 +7250,7 @@ static void mas_validate_gaps(struct ma_state *mas)
 counted:
 	if (mt == maple_arange_64) {
 		MT_BUG_ON(mas->tree, !gaps);
-		offset = ma_meta_gap(node, mt);
+		offset = ma_meta_gap(node);
 		if (offset > i) {
 			pr_err("gap offset %p[%u] is invalid\n", node, offset);
 			MT_BUG_ON(mas->tree, 1);
-- 
2.20.1

[PATCH v2 4/5] maple_tree: Delete one of the two identical checks

[Peng Zhang]

There are two identical checks, delete one of them.

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

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index 3d894f849e57..bf64d080b376 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -4117,9 +4117,6 @@ static inline bool mas_wr_append(struct ma_wr_state *wr_mas,
 	if (mt_in_rcu(mas->tree))
 		return false;
 
-	if (mas->offset != mas->end)
-		return false;
-
 	end = mas->end;
 	if (mas->offset != end)
 		return false;
-- 
2.20.1

[PATCH v2 5/5] maple_tree: Simplify mas_leaf_set_meta()

[Peng Zhang]

Now it seems that the incoming 'end' is already pointing to the last item,
so we can simplify this function, considering only whether the last slot is
being used. This has passed the maple tree test suite.

Signed-off-by: Peng Zhang <zhangpeng.00@bytedance.com>
Reviewed-by: Liam R. Howlett <Liam.Howlett@oracle.com>
---
 lib/maple_tree.c | 22 ++++------------------
 1 file changed, 4 insertions(+), 18 deletions(-)

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index bf64d080b376..89f8d2160277 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -1964,27 +1964,13 @@ static inline void mas_mab_cp(struct ma_state *mas, unsigned char mas_start,
 
 /*
  * mas_leaf_set_meta() - Set the metadata of a leaf if possible.
- * @mas: The maple state
  * @node: The maple node
- * @pivots: pointer to the maple node pivots
  * @mt: The maple type
- * @end: The assumed end
- *
- * Note, end may be incremented within this function but not modified at the
- * source.  This is fine since the metadata is the last thing to be stored in a
- * node during a write.
+ * @end: The node end
  */
-static inline void mas_leaf_set_meta(struct ma_state *mas,
-		struct maple_node *node, unsigned long *pivots,
+static inline void mas_leaf_set_meta(struct maple_node *node,
 		enum maple_type mt, unsigned char end)
 {
-	/* There is no room for metadata already */
-	if (mt_pivots[mt] <= end)
-		return;
-
-	if (pivots[end] && pivots[end] < mas->max)
-		end++;
-
 	if (end < mt_slots[mt] - 1)
 		ma_set_meta(node, mt, 0, end);
 }
@@ -2041,7 +2027,7 @@ static inline void mab_mas_cp(struct maple_big_node *b_node,
 
 		ma_set_meta(node, mt, offset, end);
 	} else {
-		mas_leaf_set_meta(mas, node, pivots, mt, end);
+		mas_leaf_set_meta(node, mt, end);
 	}
 }
 
@@ -3962,7 +3948,7 @@ static inline bool mas_wr_node_store(struct ma_wr_state *wr_mas,
 		dst_pivots[new_end] = mas->max;
 
 done:
-	mas_leaf_set_meta(mas, newnode, dst_pivots, maple_leaf_64, new_end);
+	mas_leaf_set_meta(newnode, maple_leaf_64, new_end);
 	if (in_rcu) {
 		struct maple_enode *old_enode = mas->node;
 
-- 
2.20.1

Re: [PATCH v2 0/5] Some cleanups of maple tree

[Liam R. Howlett]

* Peng Zhang <zhangpeng.00@bytedance.com> [231120 02:09]:
> These are some small cleanups of maple tree.
> 
> Just to mention, in v1, I forgot to CC LKML, but it has been added in this
> version.
> 
> Changes since v1:
>   - Removed the 'return' statement from [1/5].
>   - Made slight modifications to the commit log of [5/5].
> 
> v1: http://lists.infradead.org/pipermail/maple-tree/2023-November/003047.html

Thanks, they all look good now.

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

> 
> Peng Zhang (5):
>   maple_tree: Move the check forward to avoid static check warning
>   maple_tree: Avoid ascending when mas->min is also the parent's minimum
>   maple_tree: Remove an unused parameter for ma_meta_end()
>   maple_tree: Delete one of the two identical checks
>   maple_tree: Simplify mas_leaf_set_meta()
> 
>  lib/maple_tree.c | 45 ++++++++++++++-------------------------------
>  1 file changed, 14 insertions(+), 31 deletions(-)
> 
> -- 
> 2.20.1
>