linux-kernel - [PATCH 8/8] bcache: Fix the tail IO latency regression by using equality-aware min heap API

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: <20250610215516.1513296-9-visitorckw@gmail.com>
Date: Wed, 11 Jun 2025 05:55:16 +0800
From: Kuan-Wei Chiu <visitorckw@...il.com>
To: corbet@....net,
	colyli@...nel.org,
	kent.overstreet@...ux.dev,
	akpm@...ux-foundation.org,
	robertpang@...gle.com
Cc: linux-kernel@...r.kernel.org,
	linux-doc@...r.kernel.org,
	linux-bcache@...r.kernel.org,
	jserv@...s.ncku.edu.tw,
	Kuan-Wei Chiu <visitorckw@...il.com>,
	stable@...r.kernel.org
Subject: [PATCH 8/8] bcache: Fix the tail IO latency regression by using equality-aware min heap API

Commit 866898efbb25 ("bcache: remove heap-related macros and switch to
generic min_heap") replaced the original top-down heap macros in bcache
with the generic min heap library, which uses a bottom-up heapify
strategy. However, in scenarios like invalidate_buckets_lru() -
especially before the cache is fully populated - many buckets remain
unfilled. This causes new_bucket_prio() to frequently return zero,
leading to a high rate of equal comparisons.

Bottom-up sift_down performs up to 2 * log2(n) comparisons in such
cases, resulting in a performance regression.

Switch to the _eqaware variants of the min heap API to restore the
original top-down sift_down behavior, which requires only O(1)
comparisons when many elements are equal.

Also use the inline versions of the heap functions to avoid performance
degradation introduced by commit 92a8b224b833 ("lib/min_heap: introduce
non-inline versions of min heap API functions"), as
invalidate_buckets_lru() is on a performance-critical hot path.

Fixes: 866898efbb25 ("bcache: remove heap-related macros and switch to generic min_heap")
Fixes: 92a8b224b833 ("lib/min_heap: introduce non-inline versions of min heap API functions")
Reported-by: Robert Pang <robertpang@...gle.com>
Closes: https://lore.kernel.org/linux-bcache/CAJhEC06F_AtrPgw2-7CvCqZgeStgCtitbD-ryuPpXQA-JG5XXw@mail.gmail.com
Cc: stable@...r.kernel.org # 6.11+
Signed-off-by: Kuan-Wei Chiu <visitorckw@...il.com>
---
 drivers/md/bcache/alloc.c | 15 ++++++++-------
 1 file changed, 8 insertions(+), 7 deletions(-)

diff --git a/drivers/md/bcache/alloc.c b/drivers/md/bcache/alloc.c
index 8998e61efa40..625c5c4eb962 100644
--- a/drivers/md/bcache/alloc.c
+++ b/drivers/md/bcache/alloc.c
@@ -207,15 +207,16 @@ static void invalidate_buckets_lru(struct cache *ca)
 		if (!bch_can_invalidate_bucket(ca, b))
 			continue;
 
-		if (!min_heap_full(&ca->heap))
-			min_heap_push(&ca->heap, &b, &bucket_max_cmp_callback, ca);
-		else if (!new_bucket_max_cmp(&b, min_heap_peek(&ca->heap), ca)) {
+		if (!min_heap_full_inline(&ca->heap))
+			min_heap_push_inline(&ca->heap, &b, &bucket_max_cmp_callback, ca);
+		else if (!new_bucket_max_cmp(&b, min_heap_peek_inline(&ca->heap), ca)) {
 			ca->heap.data[0] = b;
-			min_heap_sift_down(&ca->heap, 0, &bucket_max_cmp_callback, ca);
+			min_heap_sift_down_eqaware_inline(&ca->heap, 0, &bucket_max_cmp_callback,
+							  ca);
 		}
 	}
 
-	min_heapify_all(&ca->heap, &bucket_min_cmp_callback, ca);
+	min_heapify_all_eqaware_inline(&ca->heap, &bucket_min_cmp_callback, ca);
 
 	while (!fifo_full(&ca->free_inc)) {
 		if (!ca->heap.nr) {
@@ -227,8 +228,8 @@ static void invalidate_buckets_lru(struct cache *ca)
 			wake_up_gc(ca->set);
 			return;
 		}
-		b = min_heap_peek(&ca->heap)[0];
-		min_heap_pop(&ca->heap, &bucket_min_cmp_callback, ca);
+		b = min_heap_peek_inline(&ca->heap)[0];
+		min_heap_pop_eqaware_inline(&ca->heap, &bucket_min_cmp_callback, ca);
 
 		bch_invalidate_one_bucket(ca, b);
 	}
-- 
2.34.1