From: Peng Zhang zhangpeng.00@bytedance.com
mainline inclusion from mainline-v6.8-rc1 commit 7e552dcd803f4ff60165271c573ab2e38d15769f category: performance bugzilla: https://gitee.com/openeuler/kernel/issues/I9N4V1 CVE: NA
Reference: https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/commit/?i...
----------------------------------------------------------------------
The last range stored in maple tree is typically quite large. By checking if it exceeds the sum of the remaining ranges in that node, it is possible to avoid checking all other gaps.
Running the maple tree test suite in user mode almost always results in a near 100% hit rate for this optimization.
Link: https://lkml.kernel.org/r/20231215074632.82045-1-zhangpeng.00@bytedance.com Signed-off-by: Peng Zhang zhangpeng.00@bytedance.com Reviewed-by: Liam R. Howlett Liam.Howlett@oracle.com Signed-off-by: Andrew Morton akpm@linux-foundation.org Signed-off-by: Li Zetao lizetao1@huawei.com --- lib/maple_tree.c | 3 +++ 1 file changed, 3 insertions(+)
diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 98b3ded67d06..da227397e4d8 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -1547,6 +1547,9 @@ static unsigned long mas_leaf_max_gap(struct ma_state *mas) gap = ULONG_MAX - pivots[max_piv]; if (gap > max_gap) max_gap = gap; + + if (max_gap > pivots[max_piv] - mas->min) + return max_gap; }
for (; i <= max_piv; i++) {