The patch titled
Subject: maple_tree: i is always less than or equal to mas_end
has been added to the -mm mm-unstable branch. Its filename is
maple_tree-i-is-always-less-than-or-equal-to-mas_end.patch
This patch will shortly appear at
https://git.kernel.org/pub/scm/linux/kernel/git/akpm/25-new.git/tree/patches/maple_tree-i-is-always-less-than-or-equal-to-mas_end.patch
This patch will later appear in the mm-unstable branch at
git://git.kernel.org/pub/scm/linux/kernel/git/akpm/mm
Before you just go and hit "reply", please:
a) Consider who else should be cc'ed
b) Prefer to cc a suitable mailing list as well
c) Ideally: find the original patch on the mailing list and do a
reply-to-all to that, adding suitable additional cc's
*** Remember to use Documentation/process/submit-checklist.rst when testing your code ***
The -mm tree is included into linux-next via the mm-everything
branch at git://git.kernel.org/pub/scm/linux/kernel/git/akpm/mm
and is updated there every 2-3 working days
------------------------------------------------------
From: Wei Yang <richard.weiyang@xxxxxxxxx>
Subject: maple_tree: i is always less than or equal to mas_end
Date: Wed, 11 Sep 2024 14:27:58 +0000
Patch series "refine mas_mab_cp()".
By analysis of the code, one condition check can be removed and one case
would hit a redundant assignment.
This patch (of 2):
mas_mab_cp() copy range [mas_start, mas_end] inclusively from a
maple_node to maple_big_node. This implies mas_start <= mas_end.
Based on the relationship of mas_start and mas_end, we can have the
following four cases:
| mas_start == mas_end | mas_start < mas_end
---------------+----------------------+----------------------
mas_start == 0 | 1 | 2
---------------+----------------------+----------------------
mas_start != 0 | 3 | 4
We can see in all these four cases, i is always less than or equal to
mas_end after finish the loop:
Case 1: After assign pivot 0, i is set to 1, which is bigger than
mas_end 0. So it jumps to complete and skip the check.
Case 2: After assign pivot 0, i is set to 1.
â?µ (mas_start < mas_end) && (mas_start == 0)
==> (1 <= mas_end)
â?µ (i == 1) && (1 <= mas_end)
==> (i <= mas_end)
â?´ Before loop, we have (i <= mas_end). And we still hold this
if it skips the loop. For example, (i == mas_end).
Now let's see what happens in the loop:
â?µ piv_end = min(mas_end, mt_pivots[mt])
==> (piv_end <= mas_end)
â?µ loop condition is (i < piv_end)
==> (i <= piv_end) on finish the loop both normally or break
â?µ (i <= piv_end) && (piv_end <= mas_end)
==> (i <= mas_end)
â?´ After loop, we still get (i <= mas_end) in this case
Case 3: This case would skip both if clause and loop. So when it comes
to the check, i is still mas_start which equals to mas_end.
Case 4: This case would skip the if clause.
â?µ (mas_start < mas_end) && (i == mas_start)
==> (i < mas_end)
â?´ Before loop, we have (i < mas_end).
The loop process is similar with Case 2, so we get the same
result.
Now we can conclude in all cases, we get (i <= mas_end) when doing
check. Then it is not necessary to do the check.
Link: https://lkml.kernel.org/r/20240911142759.20989-1-richard.weiyang@xxxxxxxxx
Link: https://lkml.kernel.org/r/20240911142759.20989-2-richard.weiyang@xxxxxxxxx
Signed-off-by: Wei Yang <richard.weiyang@xxxxxxxxx>
Reviewed-by: Liam R. Howlett <Liam.Howlett@xxxxxxxxxx>
Signed-off-by: Andrew Morton <akpm@xxxxxxxxxxxxxxxxxxxx>
---
lib/maple_tree.c | 3 +--
1 file changed, 1 insertion(+), 2 deletions(-)
--- a/lib/maple_tree.c~maple_tree-i-is-always-less-than-or-equal-to-mas_end
+++ a/lib/maple_tree.c
@@ -1949,8 +1949,7 @@ static inline void mas_mab_cp(struct ma_
goto complete;
}
- if (likely(i <= mas_end))
- b_node->pivot[j] = mas_safe_pivot(mas, pivots, i, mt);
+ b_node->pivot[j] = mas_safe_pivot(mas, pivots, i, mt);
complete:
b_node->b_end = ++j;
_
Patches currently in -mm which might be from richard.weiyang@xxxxxxxxx are
maple_tree-i-is-always-less-than-or-equal-to-mas_end.patch
maple_tree-goto-complete-directly-on-a-pivot-of-0.patch
