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
| ||
|
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
Powered by blists - more mailing lists