linux-kernel - [PATCH 6.6 21/28] maple_tree: avoid checking other gaps after getting the largest gap

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-Id: <20241024132225.2271667-6-yukuai1@huaweicloud.com>
Date: Thu, 24 Oct 2024 21:22:18 +0800
From: Yu Kuai <yukuai1@...weicloud.com>
To: stable@...r.kernel.org,
	gregkh@...uxfoundation.org,
	harry.wentland@....com,
	sunpeng.li@....com,
	Rodrigo.Siqueira@....com,
	alexander.deucher@....com,
	christian.koenig@....com,
	Xinhui.Pan@....com,
	airlied@...il.com,
	daniel@...ll.ch,
	viro@...iv.linux.org.uk,
	brauner@...nel.org,
	Liam.Howlett@...cle.com,
	akpm@...ux-foundation.org,
	hughd@...gle.com,
	willy@...radead.org,
	sashal@...nel.org,
	srinivasan.shanmugam@....com,
	chiahsuan.chung@....com,
	mingo@...nel.org,
	mgorman@...hsingularity.net,
	yukuai3@...wei.com,
	chengming.zhou@...ux.dev,
	zhangpeng.00@...edance.com,
	chuck.lever@...cle.com
Cc: amd-gfx@...ts.freedesktop.org,
	dri-devel@...ts.freedesktop.org,
	linux-kernel@...r.kernel.org,
	linux-fsdevel@...r.kernel.org,
	maple-tree@...ts.infradead.org,
	linux-mm@...ck.org,
	yukuai1@...weicloud.com,
	yi.zhang@...wei.com,
	yangerkun@...wei.com
Subject: [PATCH 6.6 21/28] maple_tree: avoid checking other gaps after getting the largest gap

From: Peng Zhang <zhangpeng.00@...edance.com>

commit 7e552dcd803f4ff60165271c573ab2e38d15769f upstream.

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@...edance.com>
Reviewed-by: Liam R. Howlett <Liam.Howlett@...cle.com>
Signed-off-by: Andrew Morton <akpm@...ux-foundation.org>
Signed-off-by: Yu Kuai <yukuai3@...wei.com>
---
 lib/maple_tree.c | 3 +++
 1 file changed, 3 insertions(+)

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index 905fa1143f8d..1af83414877a 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++) {
-- 
2.39.2