revert-bcache-remove-heap-related-macros-and-switch-to-generic-min_heap.patch removed from -mm tree
The quilt patch titled
Subject: Revert "bcache: remove heap-related macros and switch to generic min_heap"
has been removed from the -mm tree. Its filename was
revert-bcache-remove-heap-related-macros-and-switch-to-generic-min_heap.patch
This patch was dropped because it was merged into the mm-hotfixes-stable branch of git://git.kernel.org/pub/scm/linux/kernel/git/akpm/mm
------------------------------------------------------
From: Kuan-Wei Chiu <[email protected]>
Subject: Revert "bcache: remove heap-related macros and switch to generic min_heap"
Date: Sun, 15 Jun 2025 04:23:52 +0800
This reverts commit 866898efbb25bb44fd42848318e46db9e785973a.
The generic bottom-up min_heap implementation causes performance regression in invalidate_buckets_lru(), a hot path in bcache. Before the cache is fully populated, new_bucket_prio() often returns zero, leading to many equal comparisons. In such cases, bottom-up sift_down performs up to 2 * log2(n) comparisons, while the original top-down approach completes with just O() comparisons, resulting in a measurable performance gap.
The performance degradation is further worsened by the non-inlined min_heap API functions introduced in commit 92a8b224b833 ("lib/min_heap:
introduce non-inline versions of min heap API functions"), adding function call overhead to this critical path.
As reported by Robert, bcache now suffers from latency spikes, with P100 (max) latency increasing from 600 ms to 2.4 seconds every 5 minutes. These regressions degrade bcache's effectiveness as a low-latency cache layer and lead to frequent timeouts and application stalls in production environments.
This revert aims to restore bcache's original low-latency behavior.
---
drivers/md/bcache/alloc.c | 64 ++++------------ drivers/md/bcache/bcache.h | 2 drivers/md/bcache/bset.c | 124 +++++++++++--------------------- drivers/md/bcache/bset.h | 42 ++++++---- drivers/md/bcache/btree.c | 69 +++++++---------- drivers/md/bcache/extents.c | 51 ++++--------- drivers/md/bcache/movinggc.c | 41 ++-------- drivers/md/bcache/super.c | 3 drivers/md/bcache/sysfs.c | 4 - drivers/md/bcache/util.h | 67 ++++++++++++++++- drivers/md/bcache/writeback.c | 13 +-- 11 files changed, 217 insertions(+), 263 deletions(-)
drivers/md/bcache/alloc.c renamed from drivers/md/bcache/alloc.c~revert-bcache-remove-heap-related-macros-and-switch-to-generic-min_heap +17 -47
@@ -164,68 +164,40 @@ static void bch_invalidate_one_bucket(st* prio is worth 1/8th of what INITIAL_PRIO is worth. */ -static inline unsigned int new_bucket_prio (struct cache *ca,struct bucket *b) -{ -unsigned int min_prio = (INITIAL_PRIO - ca->set->min_prio) /8 ; - -return (b->prio - ca->set->min_prio + min_prio) *GC_SECTORS_USED (b); -} - -static inline bool new_bucket_max_cmp (const void *l,const void *r,void *args) -{ -struct bucket **lhs = (struct bucket **)l; -struct bucket **rhs = (struct bucket **)r; -struct cache *ca = args; - -return new_bucket_prio (ca, *lhs) >new_bucket_prio (ca, *rhs); -} - -static inline bool new_bucket_min_cmp (const void *l,const void *r,void *args) -{ -struct bucket **lhs = (struct bucket **)l; -struct bucket **rhs = (struct bucket **)r; -struct cache *ca = args; - -return new_bucket_prio (ca, *lhs) <new_bucket_prio (ca, *rhs); -} - -static inline void new_bucket_swap (void *l,void *r,void __always_unused *args) -{ -struct bucket **lhs = l, **rhs = r; +#define bucket_prio (b) \ +({ \ + unsigned int min_prio = (INITIAL_PRIO - ca->set->min_prio) / 8; \ + \ + (b->prio - ca->set->min_prio + min_prio) * GC_SECTORS_USED(b); \ +}) -swap (*lhs, *rhs); -} +#define bucket_max_cmp (l, r) (bucket_prio(l) < bucket_prio(r)) +#define bucket_min_cmp (l, r) (bucket_prio(l) > bucket_prio(r))static void invalidate_buckets_lru (struct cache *ca) {struct bucket *b; -const struct min_heap_callbacks bucket_max_cmp_callback = { - .less = new_bucket_max_cmp, - .swp = new_bucket_swap, - }; -const struct min_heap_callbacks bucket_min_cmp_callback = { - .less = new_bucket_min_cmp, - .swp = new_bucket_swap, - }; +ssize_t i; - ca->heap.nr =0 ; + ca->heap.used =0 ;for_each_bucket (b, 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 (!heap_full (&ca->heap)) +heap_add (&ca->heap, b, bucket_max_cmp); +else if (bucket_max_cmp (b,heap_peek (&ca->heap))) { ca->heap.data[0 ] = b; -min_heap_sift_down (&ca->heap,0 , &bucket_max_cmp_callback, ca); +heap_sift (&ca->heap,0 , bucket_max_cmp); } } -min_heapify_all (&ca->heap, &bucket_min_cmp_callback, ca); +for (i = ca->heap.used /2 -1 ; i >=0 ; --i) +heap_sift (&ca->heap, i, bucket_min_cmp);while (!fifo_full (&ca->free_inc)) { -if (!ca->heap.nr) { +if (!heap_pop (&ca->heap, b, bucket_min_cmp)) {/* * We don't want to be calling invalidate_buckets() * multiple times when it can't do anything
@@ -234,8 +206,6 @@ static void invalidate_buckets_lru(strucwake_up_gc (ca->set);return ; } - b =min_heap_peek (&ca->heap)[0 ]; -min_heap_pop (&ca->heap, &bucket_min_cmp_callback, ca);bch_invalidate_one_bucket (ca, b); }
drivers/md/bcache/bcache.h renamed from drivers/md/bcache/bcache.h~revert-bcache-remove-heap-related-macros-and-switch-to-generic-min_heap +1 -1
@@ -458,7 +458,7 @@ struct cache {/* Allocation stuff: */ struct bucket *buckets; - DEFINE_MIN_HEAP(struct bucket *, cache_heap) heap; + DECLARE_HEAP(struct bucket *, heap);/* * If nonzero, we know we aren't going to find any buckets to invalidate
drivers/md/bcache/bset.c renamed from drivers/md/bcache/bset.c~revert-bcache-remove-heap-related-macros-and-switch-to-generic-min_heap +45 -79
257 lines not on this page · raw message
drivers/md/bcache/bset.h renamed from drivers/md/bcache/bset.h~revert-bcache-remove-heap-related-macros-and-switch-to-generic-min_heap +24 -18
72 lines not on this page · raw message
drivers/md/bcache/btree.c renamed from drivers/md/bcache/btree.c~revert-bcache-remove-heap-related-macros-and-switch-to-generic-min_heap +29 -40
188 lines not on this page · raw message
drivers/md/bcache/extents.c renamed from drivers/md/bcache/extents.c~revert-bcache-remove-heap-related-macros-and-switch-to-generic-min_heap +18 -33
105 lines not on this page · raw message
drivers/md/bcache/movinggc.c renamed from drivers/md/bcache/movinggc.c~revert-bcache-remove-heap-related-macros-and-switch-to-generic-min_heap +10 -31
85 lines not on this page · raw message
drivers/md/bcache/super.c renamed from drivers/md/bcache/super.c~revert-bcache-remove-heap-related-macros-and-switch-to-generic-min_heap +2 -1
@@ -1912,7 +1912,8 @@ struct cache_set *bch_cache_set_alloc(stINIT_LIST_HEAD (&c->btree_cache_freed);INIT_LIST_HEAD (&c->data_buckets); - iter_size = ((meta_bucket_pages (sb) *PAGE_SECTORS ) / sb->block_size) * + iter_size =sizeof (struct btree_iter ) + + ((meta_bucket_pages (sb) *PAGE_SECTORS ) / sb->block_size) *sizeof (struct btree_iter_set ); c->devices =kcalloc (c->nr_uuids,sizeof (void *),GFP_KERNEL );
drivers/md/bcache/sysfs.c renamed from drivers/md/bcache/sysfs.c~revert-bcache-remove-heap-related-macros-and-switch-to-generic-min_heap +1 -3
@@ -660,9 +660,7 @@ static unsigned int bch_root_usage(strucunsigned int bytes =0 ;struct bkey *k;struct btree *b; -struct btree_iter iter; - -min_heap_init (&iter.heap,NULL ,MAX_BSETS ); +struct btree_iter_stack iter; goto lock_root;
drivers/md/bcache/util.h renamed from drivers/md/bcache/util.h~revert-bcache-remove-heap-related-macros-and-switch-to-generic-min_heap +65 -2
88 lines not on this page · raw message
drivers/md/bcache/writeback.c renamed from drivers/md/bcache/writeback.c~revert-bcache-remove-heap-related-macros-and-switch-to-generic-min_heap +5 -8
@@ -908,16 +908,15 @@ static int bch_dirty_init_thread(void *astruct dirty_init_thrd_info *info = arg;struct bch_dirty_init_state *state = info->state;struct cache_set *c = state->c; -struct btree_iter iter; +struct btree_iter_stack iter;struct bkey *k, *p;int cur_idx, prev_idx, skip_nr; k = p =NULL ; prev_idx =0 ; -min_heap_init (&iter.heap,NULL ,MAX_BSETS ); -bch_btree_iter_init (&c->root->keys, &iter,NULL ); - k =bch_btree_iter_next_filter (&iter, &c->root->keys, bch_ptr_bad); +bch_btree_iter_stack_init (&c->root->keys, &iter,NULL ); + k =bch_btree_iter_next_filter (&iter.iter, &c->root->keys, bch_ptr_bad);BUG_ON (!k); p = k;
@@ -931,7 +930,7 @@ static int bch_dirty_init_thread(void *a skip_nr = cur_idx - prev_idx;while (skip_nr) { - k =bch_btree_iter_next_filter (&iter, + k =bch_btree_iter_next_filter (&iter.iter, &c->root->keys, bch_ptr_bad);if (k)
@@ -980,13 +979,11 @@ void bch_sectors_dirty_init(struct bcachint i;struct btree *b =NULL ;struct bkey *k =NULL ; -struct btree_iter iter; +struct btree_iter_stack iter;struct sectors_dirty_init op;struct cache_set *c = d->c;struct bch_dirty_init_state state; -min_heap_init (&iter.heap,NULL ,MAX_BSETS ); - retry_lock: b = c->root;rw_lock (0 , b, b->level);
_
Patches currently in -mm which might be from [email protected] are
lib-math-gcd-use-static-key-to-select-implementation-at-runtime.patch riscv-optimize-gcd-code-size-when-config_riscv_isa_zbb-is-disabled.patch riscv-optimize-gcd-performance-on-risc-v-without-zbb-extension.patch