[merged mm-stable] maple_tree-avoid-checking-other-gaps-after-getting-the-largest-gap.patch removed from -mm tree

[merged mm-stable] maple_tree-avoid-checking-other-gaps-after-getting-the-largest-gap.patch removed from -mm tree

[Andrew Morton]

The quilt patch titled
     Subject: maple_tree: avoid checking other gaps after getting the largest gap
has been removed from the -mm tree.  Its filename was
     maple_tree-avoid-checking-other-gaps-after-getting-the-largest-gap.patch

This patch was dropped because it was merged into the mm-stable branch
of git://git.kernel.org/pub/scm/linux/kernel/git/akpm/mm

------------------------------------------------------
From: Peng Zhang <zhangpeng.00@bytedance.com>
Subject: maple_tree: avoid checking other gaps after getting the largest gap
Date: Fri, 15 Dec 2023 15:46:32 +0800

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>
---

 lib/maple_tree.c |    3 +++
 1 file changed, 3 insertions(+)

--- a/lib/maple_tree.c~maple_tree-avoid-checking-other-gaps-after-getting-the-largest-gap
+++ a/lib/maple_tree.c
@@ -1518,6 +1518,9 @@ static unsigned long mas_leaf_max_gap(st
 		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++) {
_

Patches currently in -mm which might be from zhangpeng.00@bytedance.com are