* [PATCH v2 0/3] bcache: Revert min_heap migration due to performance regression
@ 2025-06-14 20:23 Kuan-Wei Chiu
2025-06-14 20:23 ` [PATCH v2 1/3] Revert "bcache: update min_heap_callbacks to use default builtin swap" Kuan-Wei Chiu
` (2 more replies)
0 siblings, 3 replies; 7+ messages in thread
From: Kuan-Wei Chiu @ 2025-06-14 20:23 UTC (permalink / raw)
To: akpm, colyli, kent.overstreet, robertpang
Cc: linux-kernel, linux-bcache, jserv, Kuan-Wei Chiu
This patch series reverts the migration of bcache from its original
heap implementation to the generic min_heap library. While the original
change aimed to simplify the code and improve maintainability, it
introduced a severe performance regression in real-world scenarios.
As reported by Robert, systems using bcache now suffer from periodic
latency spikes, with P100 (max) latency increasing from 600 ms to
2.4 seconds every 5 minutes. This degrades bcache's value as a
low-latency caching layer, and leads to frequent timeouts and
application stalls in production environments.
The primary cause of this regression is the behavior of the generic
min_heap implementation's bottom-up sift_down, which performs up to
2 * log2(n) comparisons when many elements are equal. The original
top-down variant used by bcache only required O(1) comparisons in such
cases. The issue was further exacerbated by commit 92a8b224b833
("lib/min_heap: introduce non-inline versions of min heap API
functions"), which introduced non-inlined versions of the min_heap API,
adding function call overhead to a performance-critical hot path.
---
Changes in v2:
- Drop the proposed new min_heap API approach.
- Replace with full reverts of the min_heap-related changes in bcache.
v1: https://lore.kernel.org/lkml/20250610215516.1513296-1-visitorckw@gmail.com
Note: I'm aware that this revert series changes more than 100 lines of
code, which exceeds the typical guideline for stable backports.
However, introducing new generic APIs to fix this regression would also
involve over 100 lines of changes and add new features. In contrast,
reverting to a previously known-good state is a safer and more
straightforward solution in this case.
Kuan-Wei Chiu (3):
Revert "bcache: update min_heap_callbacks to use default builtin swap"
Revert "bcache: remove heap-related macros and switch to generic
min_heap"
bcache: Remove unnecessary select MIN_HEAP
drivers/md/bcache/Kconfig | 1 -
drivers/md/bcache/alloc.c | 57 +++++------------
drivers/md/bcache/bcache.h | 2 +-
drivers/md/bcache/bset.c | 116 +++++++++++++---------------------
drivers/md/bcache/bset.h | 40 +++++++-----
drivers/md/bcache/btree.c | 69 +++++++++-----------
drivers/md/bcache/extents.c | 45 ++++++-------
drivers/md/bcache/movinggc.c | 33 +++-------
drivers/md/bcache/super.c | 3 +-
drivers/md/bcache/sysfs.c | 4 +-
drivers/md/bcache/util.h | 67 +++++++++++++++++++-
drivers/md/bcache/writeback.c | 13 ++--
12 files changed, 217 insertions(+), 233 deletions(-)
--
2.34.1
^ permalink raw reply [flat|nested] 7+ messages in thread* [PATCH v2 1/3] Revert "bcache: update min_heap_callbacks to use default builtin swap" 2025-06-14 20:23 [PATCH v2 0/3] bcache: Revert min_heap migration due to performance regression Kuan-Wei Chiu @ 2025-06-14 20:23 ` Kuan-Wei Chiu 2025-06-15 5:51 ` Coly Li 2025-06-14 20:23 ` [PATCH v2 2/3] Revert "bcache: remove heap-related macros and switch to generic min_heap" Kuan-Wei Chiu 2025-06-14 20:23 ` [PATCH v2 3/3] bcache: Remove unnecessary select MIN_HEAP Kuan-Wei Chiu 2 siblings, 1 reply; 7+ messages in thread From: Kuan-Wei Chiu @ 2025-06-14 20:23 UTC (permalink / raw) To: akpm, colyli, kent.overstreet, robertpang Cc: linux-kernel, linux-bcache, jserv, Kuan-Wei Chiu, stable This reverts commit 3d8a9a1c35227c3f1b0bd132c9f0a80dbda07b65. Although removing the custom swap function simplified the code, this change is part of a broader migration to the generic min_heap API that introduced significant performance regressions in bcache. 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 is part of a series of changes to restore previous performance by undoing the min_heap transition. Link: https://lore.kernel.org/lkml/CAJhEC05+0S69z+3+FB2Cd0hD+pCRyWTKLEOsc8BOmH73p1m+KQ@mail.gmail.com 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@google.com> Closes: https://lore.kernel.org/linux-bcache/CAJhEC06F_AtrPgw2-7CvCqZgeStgCtitbD-ryuPpXQA-JG5XXw@mail.gmail.com Cc: stable@vger.kernel.org Signed-off-by: Kuan-Wei Chiu <visitorckw@gmail.com> --- drivers/md/bcache/alloc.c | 11 +++++++++-- drivers/md/bcache/bset.c | 14 +++++++++++--- drivers/md/bcache/extents.c | 10 +++++++++- drivers/md/bcache/movinggc.c | 10 +++++++++- 4 files changed, 38 insertions(+), 7 deletions(-) diff --git a/drivers/md/bcache/alloc.c b/drivers/md/bcache/alloc.c index 8998e61efa40..da50f6661bae 100644 --- a/drivers/md/bcache/alloc.c +++ b/drivers/md/bcache/alloc.c @@ -189,16 +189,23 @@ static inline bool new_bucket_min_cmp(const void *l, const void *r, void *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; + + swap(*lhs, *rhs); +} + 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 = NULL, + .swp = new_bucket_swap, }; const struct min_heap_callbacks bucket_min_cmp_callback = { .less = new_bucket_min_cmp, - .swp = NULL, + .swp = new_bucket_swap, }; ca->heap.nr = 0; diff --git a/drivers/md/bcache/bset.c b/drivers/md/bcache/bset.c index 68258a16e125..bd97d8626887 100644 --- a/drivers/md/bcache/bset.c +++ b/drivers/md/bcache/bset.c @@ -1093,6 +1093,14 @@ static inline bool new_btree_iter_cmp(const void *l, const void *r, void __alway return bkey_cmp(_l->k, _r->k) <= 0; } +static inline void new_btree_iter_swap(void *iter1, void *iter2, void __always_unused *args) +{ + struct btree_iter_set *_iter1 = iter1; + struct btree_iter_set *_iter2 = iter2; + + swap(*_iter1, *_iter2); +} + static inline bool btree_iter_end(struct btree_iter *iter) { return !iter->heap.nr; @@ -1103,7 +1111,7 @@ void bch_btree_iter_push(struct btree_iter *iter, struct bkey *k, { const struct min_heap_callbacks callbacks = { .less = new_btree_iter_cmp, - .swp = NULL, + .swp = new_btree_iter_swap, }; if (k != end) @@ -1149,7 +1157,7 @@ static inline struct bkey *__bch_btree_iter_next(struct btree_iter *iter, struct bkey *ret = NULL; const struct min_heap_callbacks callbacks = { .less = cmp, - .swp = NULL, + .swp = new_btree_iter_swap, }; if (!btree_iter_end(iter)) { @@ -1223,7 +1231,7 @@ static void btree_mergesort(struct btree_keys *b, struct bset *out, : bch_ptr_invalid; const struct min_heap_callbacks callbacks = { .less = b->ops->sort_cmp, - .swp = NULL, + .swp = new_btree_iter_swap, }; /* Heapify the iterator, using our comparison function */ diff --git a/drivers/md/bcache/extents.c b/drivers/md/bcache/extents.c index 4b84fda1530a..a7221e5dbe81 100644 --- a/drivers/md/bcache/extents.c +++ b/drivers/md/bcache/extents.c @@ -266,12 +266,20 @@ static bool new_bch_extent_sort_cmp(const void *l, const void *r, void __always_ return !(c ? c > 0 : _l->k < _r->k); } +static inline void new_btree_iter_swap(void *iter1, void *iter2, void __always_unused *args) +{ + struct btree_iter_set *_iter1 = iter1; + struct btree_iter_set *_iter2 = iter2; + + swap(*_iter1, *_iter2); +} + static struct bkey *bch_extent_sort_fixup(struct btree_iter *iter, struct bkey *tmp) { const struct min_heap_callbacks callbacks = { .less = new_bch_extent_sort_cmp, - .swp = NULL, + .swp = new_btree_iter_swap, }; while (iter->heap.nr > 1) { struct btree_iter_set *top = iter->heap.data, *i = top + 1; diff --git a/drivers/md/bcache/movinggc.c b/drivers/md/bcache/movinggc.c index 45ca134cbf02..d6c73dd8eb2b 100644 --- a/drivers/md/bcache/movinggc.c +++ b/drivers/md/bcache/movinggc.c @@ -190,6 +190,14 @@ static bool new_bucket_cmp(const void *l, const void *r, void __always_unused *a return GC_SECTORS_USED(*_l) >= GC_SECTORS_USED(*_r); } +static void new_bucket_swap(void *l, void *r, void __always_unused *args) +{ + struct bucket **_l = l; + struct bucket **_r = r; + + swap(*_l, *_r); +} + static unsigned int bucket_heap_top(struct cache *ca) { struct bucket *b; @@ -204,7 +212,7 @@ void bch_moving_gc(struct cache_set *c) unsigned long sectors_to_move, reserve_sectors; const struct min_heap_callbacks callbacks = { .less = new_bucket_cmp, - .swp = NULL, + .swp = new_bucket_swap, }; if (!c->copy_gc_enabled) -- 2.34.1 ^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [PATCH v2 1/3] Revert "bcache: update min_heap_callbacks to use default builtin swap" 2025-06-14 20:23 ` [PATCH v2 1/3] Revert "bcache: update min_heap_callbacks to use default builtin swap" Kuan-Wei Chiu @ 2025-06-15 5:51 ` Coly Li 0 siblings, 0 replies; 7+ messages in thread From: Coly Li @ 2025-06-15 5:51 UTC (permalink / raw) To: Kuan-Wei Chiu Cc: akpm, kent.overstreet, robertpang, linux-kernel, linux-bcache, jserv, stable On Sun, Jun 15, 2025 at 04:23:51AM +0800, Kuan-Wei Chiu wrote: > This reverts commit 3d8a9a1c35227c3f1b0bd132c9f0a80dbda07b65. > > Although removing the custom swap function simplified the code, this > change is part of a broader migration to the generic min_heap API that > introduced significant performance regressions in bcache. > > 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 is part of a series of changes to restore previous > performance by undoing the min_heap transition. > > Link: https://lore.kernel.org/lkml/CAJhEC05+0S69z+3+FB2Cd0hD+pCRyWTKLEOsc8BOmH73p1m+KQ@mail.gmail.com > 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@google.com> > Closes: https://lore.kernel.org/linux-bcache/CAJhEC06F_AtrPgw2-7CvCqZgeStgCtitbD-ryuPpXQA-JG5XXw@mail.gmail.com > Cc: stable@vger.kernel.org > Signed-off-by: Kuan-Wei Chiu <visitorckw@gmail.com> Acked-by: Coly Li <colyli@kernel.org> Thanks. > --- > drivers/md/bcache/alloc.c | 11 +++++++++-- > drivers/md/bcache/bset.c | 14 +++++++++++--- > drivers/md/bcache/extents.c | 10 +++++++++- > drivers/md/bcache/movinggc.c | 10 +++++++++- > 4 files changed, 38 insertions(+), 7 deletions(-) > > diff --git a/drivers/md/bcache/alloc.c b/drivers/md/bcache/alloc.c > index 8998e61efa40..da50f6661bae 100644 > --- a/drivers/md/bcache/alloc.c > +++ b/drivers/md/bcache/alloc.c > @@ -189,16 +189,23 @@ static inline bool new_bucket_min_cmp(const void *l, const void *r, void *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; > + > + swap(*lhs, *rhs); > +} > + > 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 = NULL, > + .swp = new_bucket_swap, > }; > const struct min_heap_callbacks bucket_min_cmp_callback = { > .less = new_bucket_min_cmp, > - .swp = NULL, > + .swp = new_bucket_swap, > }; > > ca->heap.nr = 0; > diff --git a/drivers/md/bcache/bset.c b/drivers/md/bcache/bset.c > index 68258a16e125..bd97d8626887 100644 > --- a/drivers/md/bcache/bset.c > +++ b/drivers/md/bcache/bset.c > @@ -1093,6 +1093,14 @@ static inline bool new_btree_iter_cmp(const void *l, const void *r, void __alway > return bkey_cmp(_l->k, _r->k) <= 0; > } > > +static inline void new_btree_iter_swap(void *iter1, void *iter2, void __always_unused *args) > +{ > + struct btree_iter_set *_iter1 = iter1; > + struct btree_iter_set *_iter2 = iter2; > + > + swap(*_iter1, *_iter2); > +} > + > static inline bool btree_iter_end(struct btree_iter *iter) > { > return !iter->heap.nr; > @@ -1103,7 +1111,7 @@ void bch_btree_iter_push(struct btree_iter *iter, struct bkey *k, > { > const struct min_heap_callbacks callbacks = { > .less = new_btree_iter_cmp, > - .swp = NULL, > + .swp = new_btree_iter_swap, > }; > > if (k != end) > @@ -1149,7 +1157,7 @@ static inline struct bkey *__bch_btree_iter_next(struct btree_iter *iter, > struct bkey *ret = NULL; > const struct min_heap_callbacks callbacks = { > .less = cmp, > - .swp = NULL, > + .swp = new_btree_iter_swap, > }; > > if (!btree_iter_end(iter)) { > @@ -1223,7 +1231,7 @@ static void btree_mergesort(struct btree_keys *b, struct bset *out, > : bch_ptr_invalid; > const struct min_heap_callbacks callbacks = { > .less = b->ops->sort_cmp, > - .swp = NULL, > + .swp = new_btree_iter_swap, > }; > > /* Heapify the iterator, using our comparison function */ > diff --git a/drivers/md/bcache/extents.c b/drivers/md/bcache/extents.c > index 4b84fda1530a..a7221e5dbe81 100644 > --- a/drivers/md/bcache/extents.c > +++ b/drivers/md/bcache/extents.c > @@ -266,12 +266,20 @@ static bool new_bch_extent_sort_cmp(const void *l, const void *r, void __always_ > return !(c ? c > 0 : _l->k < _r->k); > } > > +static inline void new_btree_iter_swap(void *iter1, void *iter2, void __always_unused *args) > +{ > + struct btree_iter_set *_iter1 = iter1; > + struct btree_iter_set *_iter2 = iter2; > + > + swap(*_iter1, *_iter2); > +} > + > static struct bkey *bch_extent_sort_fixup(struct btree_iter *iter, > struct bkey *tmp) > { > const struct min_heap_callbacks callbacks = { > .less = new_bch_extent_sort_cmp, > - .swp = NULL, > + .swp = new_btree_iter_swap, > }; > while (iter->heap.nr > 1) { > struct btree_iter_set *top = iter->heap.data, *i = top + 1; > diff --git a/drivers/md/bcache/movinggc.c b/drivers/md/bcache/movinggc.c > index 45ca134cbf02..d6c73dd8eb2b 100644 > --- a/drivers/md/bcache/movinggc.c > +++ b/drivers/md/bcache/movinggc.c > @@ -190,6 +190,14 @@ static bool new_bucket_cmp(const void *l, const void *r, void __always_unused *a > return GC_SECTORS_USED(*_l) >= GC_SECTORS_USED(*_r); > } > > +static void new_bucket_swap(void *l, void *r, void __always_unused *args) > +{ > + struct bucket **_l = l; > + struct bucket **_r = r; > + > + swap(*_l, *_r); > +} > + > static unsigned int bucket_heap_top(struct cache *ca) > { > struct bucket *b; > @@ -204,7 +212,7 @@ void bch_moving_gc(struct cache_set *c) > unsigned long sectors_to_move, reserve_sectors; > const struct min_heap_callbacks callbacks = { > .less = new_bucket_cmp, > - .swp = NULL, > + .swp = new_bucket_swap, > }; > > if (!c->copy_gc_enabled) > -- > 2.34.1 > -- Coly Li ^ permalink raw reply [flat|nested] 7+ messages in thread
* [PATCH v2 2/3] Revert "bcache: remove heap-related macros and switch to generic min_heap" 2025-06-14 20:23 [PATCH v2 0/3] bcache: Revert min_heap migration due to performance regression Kuan-Wei Chiu 2025-06-14 20:23 ` [PATCH v2 1/3] Revert "bcache: update min_heap_callbacks to use default builtin swap" Kuan-Wei Chiu @ 2025-06-14 20:23 ` Kuan-Wei Chiu 2025-06-15 5:51 ` Coly Li 2025-06-14 20:23 ` [PATCH v2 3/3] bcache: Remove unnecessary select MIN_HEAP Kuan-Wei Chiu 2 siblings, 1 reply; 7+ messages in thread From: Kuan-Wei Chiu @ 2025-06-14 20:23 UTC (permalink / raw) To: akpm, colyli, kent.overstreet, robertpang Cc: linux-kernel, linux-bcache, jserv, Kuan-Wei Chiu, stable 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. Link: https://lore.kernel.org/lkml/CAJhEC05+0S69z+3+FB2Cd0hD+pCRyWTKLEOsc8BOmH73p1m+KQ@mail.gmail.com 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@google.com> Closes: https://lore.kernel.org/linux-bcache/CAJhEC06F_AtrPgw2-7CvCqZgeStgCtitbD-ryuPpXQA-JG5XXw@mail.gmail.com Cc: stable@vger.kernel.org Signed-off-by: Kuan-Wei Chiu <visitorckw@gmail.com> --- drivers/md/bcache/alloc.c | 64 +++++------------- drivers/md/bcache/bcache.h | 2 +- drivers/md/bcache/bset.c | 124 ++++++++++++---------------------- drivers/md/bcache/bset.h | 40 ++++++----- drivers/md/bcache/btree.c | 69 ++++++++----------- drivers/md/bcache/extents.c | 53 ++++++--------- 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(-) diff --git a/drivers/md/bcache/alloc.c b/drivers/md/bcache/alloc.c index da50f6661bae..48ce750bf70a 100644 --- a/drivers/md/bcache/alloc.c +++ b/drivers/md/bcache/alloc.c @@ -164,68 +164,40 @@ static void bch_invalidate_one_bucket(struct cache *ca, struct bucket *b) * 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(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); bch_invalidate_one_bucket(ca, b); } diff --git a/drivers/md/bcache/bcache.h b/drivers/md/bcache/bcache.h index 785b0d9008fa..1d33e40d26ea 100644 --- a/drivers/md/bcache/bcache.h +++ b/drivers/md/bcache/bcache.h @@ -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 diff --git a/drivers/md/bcache/bset.c b/drivers/md/bcache/bset.c index bd97d8626887..463eb13bd0b2 100644 --- a/drivers/md/bcache/bset.c +++ b/drivers/md/bcache/bset.c @@ -54,11 +54,9 @@ void bch_dump_bucket(struct btree_keys *b) int __bch_count_data(struct btree_keys *b) { unsigned int ret = 0; - struct btree_iter iter; + struct btree_iter_stack iter; struct bkey *k; - min_heap_init(&iter.heap, NULL, MAX_BSETS); - if (b->ops->is_extents) for_each_key(b, k, &iter) ret += KEY_SIZE(k); @@ -69,11 +67,9 @@ void __bch_check_keys(struct btree_keys *b, const char *fmt, ...) { va_list args; struct bkey *k, *p = NULL; - struct btree_iter iter; + struct btree_iter_stack iter; const char *err; - min_heap_init(&iter.heap, NULL, MAX_BSETS); - for_each_key(b, k, &iter) { if (b->ops->is_extents) { err = "Keys out of order"; @@ -114,9 +110,9 @@ void __bch_check_keys(struct btree_keys *b, const char *fmt, ...) static void bch_btree_iter_next_check(struct btree_iter *iter) { - struct bkey *k = iter->heap.data->k, *next = bkey_next(k); + struct bkey *k = iter->data->k, *next = bkey_next(k); - if (next < iter->heap.data->end && + if (next < iter->data->end && bkey_cmp(k, iter->b->ops->is_extents ? &START_KEY(next) : next) > 0) { bch_dump_bucket(iter->b); @@ -883,14 +879,12 @@ unsigned int bch_btree_insert_key(struct btree_keys *b, struct bkey *k, unsigned int status = BTREE_INSERT_STATUS_NO_INSERT; struct bset *i = bset_tree_last(b)->data; struct bkey *m, *prev = NULL; - struct btree_iter iter; + struct btree_iter_stack iter; struct bkey preceding_key_on_stack = ZERO_KEY; struct bkey *preceding_key_p = &preceding_key_on_stack; BUG_ON(b->ops->is_extents && !KEY_SIZE(k)); - min_heap_init(&iter.heap, NULL, MAX_BSETS); - /* * If k has preceding key, preceding_key_p will be set to address * of k's preceding key; otherwise preceding_key_p will be set @@ -901,9 +895,9 @@ unsigned int bch_btree_insert_key(struct btree_keys *b, struct bkey *k, else preceding_key(k, &preceding_key_p); - m = bch_btree_iter_init(b, &iter, preceding_key_p); + m = bch_btree_iter_stack_init(b, &iter, preceding_key_p); - if (b->ops->insert_fixup(b, k, &iter, replace_key)) + if (b->ops->insert_fixup(b, k, &iter.iter, replace_key)) return status; status = BTREE_INSERT_STATUS_INSERT; @@ -1083,102 +1077,79 @@ struct bkey *__bch_bset_search(struct btree_keys *b, struct bset_tree *t, /* Btree iterator */ -typedef bool (new_btree_iter_cmp_fn)(const void *, const void *, void *); - -static inline bool new_btree_iter_cmp(const void *l, const void *r, void __always_unused *args) -{ - const struct btree_iter_set *_l = l; - const struct btree_iter_set *_r = r; - - return bkey_cmp(_l->k, _r->k) <= 0; -} +typedef bool (btree_iter_cmp_fn)(struct btree_iter_set, + struct btree_iter_set); -static inline void new_btree_iter_swap(void *iter1, void *iter2, void __always_unused *args) +static inline bool btree_iter_cmp(struct btree_iter_set l, + struct btree_iter_set r) { - struct btree_iter_set *_iter1 = iter1; - struct btree_iter_set *_iter2 = iter2; - - swap(*_iter1, *_iter2); + return bkey_cmp(l.k, r.k) > 0; } static inline bool btree_iter_end(struct btree_iter *iter) { - return !iter->heap.nr; + return !iter->used; } void bch_btree_iter_push(struct btree_iter *iter, struct bkey *k, struct bkey *end) { - const struct min_heap_callbacks callbacks = { - .less = new_btree_iter_cmp, - .swp = new_btree_iter_swap, - }; - if (k != end) - BUG_ON(!min_heap_push(&iter->heap, - &((struct btree_iter_set) { k, end }), - &callbacks, - NULL)); + BUG_ON(!heap_add(iter, + ((struct btree_iter_set) { k, end }), + btree_iter_cmp)); } -static struct bkey *__bch_btree_iter_init(struct btree_keys *b, - struct btree_iter *iter, - struct bkey *search, - struct bset_tree *start) +static struct bkey *__bch_btree_iter_stack_init(struct btree_keys *b, + struct btree_iter_stack *iter, + struct bkey *search, + struct bset_tree *start) { struct bkey *ret = NULL; - iter->heap.size = ARRAY_SIZE(iter->heap.preallocated); - iter->heap.nr = 0; + iter->iter.size = ARRAY_SIZE(iter->stack_data); + iter->iter.used = 0; #ifdef CONFIG_BCACHE_DEBUG - iter->b = b; + iter->iter.b = b; #endif for (; start <= bset_tree_last(b); start++) { ret = bch_bset_search(b, start, search); - bch_btree_iter_push(iter, ret, bset_bkey_last(start->data)); + bch_btree_iter_push(&iter->iter, ret, bset_bkey_last(start->data)); } return ret; } -struct bkey *bch_btree_iter_init(struct btree_keys *b, - struct btree_iter *iter, +struct bkey *bch_btree_iter_stack_init(struct btree_keys *b, + struct btree_iter_stack *iter, struct bkey *search) { - return __bch_btree_iter_init(b, iter, search, b->set); + return __bch_btree_iter_stack_init(b, iter, search, b->set); } static inline struct bkey *__bch_btree_iter_next(struct btree_iter *iter, - new_btree_iter_cmp_fn *cmp) + btree_iter_cmp_fn *cmp) { struct btree_iter_set b __maybe_unused; struct bkey *ret = NULL; - const struct min_heap_callbacks callbacks = { - .less = cmp, - .swp = new_btree_iter_swap, - }; if (!btree_iter_end(iter)) { bch_btree_iter_next_check(iter); - ret = iter->heap.data->k; - iter->heap.data->k = bkey_next(iter->heap.data->k); + ret = iter->data->k; + iter->data->k = bkey_next(iter->data->k); - if (iter->heap.data->k > iter->heap.data->end) { + if (iter->data->k > iter->data->end) { WARN_ONCE(1, "bset was corrupt!\n"); - iter->heap.data->k = iter->heap.data->end; + iter->data->k = iter->data->end; } - if (iter->heap.data->k == iter->heap.data->end) { - if (iter->heap.nr) { - b = min_heap_peek(&iter->heap)[0]; - min_heap_pop(&iter->heap, &callbacks, NULL); - } - } + if (iter->data->k == iter->data->end) + heap_pop(iter, b, cmp); else - min_heap_sift_down(&iter->heap, 0, &callbacks, NULL); + heap_sift(iter, 0, cmp); } return ret; @@ -1186,7 +1157,7 @@ static inline struct bkey *__bch_btree_iter_next(struct btree_iter *iter, struct bkey *bch_btree_iter_next(struct btree_iter *iter) { - return __bch_btree_iter_next(iter, new_btree_iter_cmp); + return __bch_btree_iter_next(iter, btree_iter_cmp); } @@ -1224,18 +1195,16 @@ static void btree_mergesort(struct btree_keys *b, struct bset *out, struct btree_iter *iter, bool fixup, bool remove_stale) { + int i; struct bkey *k, *last = NULL; BKEY_PADDED(k) tmp; bool (*bad)(struct btree_keys *, const struct bkey *) = remove_stale ? bch_ptr_bad : bch_ptr_invalid; - const struct min_heap_callbacks callbacks = { - .less = b->ops->sort_cmp, - .swp = new_btree_iter_swap, - }; /* Heapify the iterator, using our comparison function */ - min_heapify_all(&iter->heap, &callbacks, NULL); + for (i = iter->used / 2 - 1; i >= 0; --i) + heap_sift(iter, i, b->ops->sort_cmp); while (!btree_iter_end(iter)) { if (b->ops->sort_fixup && fixup) @@ -1324,11 +1293,10 @@ void bch_btree_sort_partial(struct btree_keys *b, unsigned int start, struct bset_sort_state *state) { size_t order = b->page_order, keys = 0; - struct btree_iter iter; + struct btree_iter_stack iter; int oldsize = bch_count_data(b); - min_heap_init(&iter.heap, NULL, MAX_BSETS); - __bch_btree_iter_init(b, &iter, NULL, &b->set[start]); + __bch_btree_iter_stack_init(b, &iter, NULL, &b->set[start]); if (start) { unsigned int i; @@ -1339,7 +1307,7 @@ void bch_btree_sort_partial(struct btree_keys *b, unsigned int start, order = get_order(__set_bytes(b->set->data, keys)); } - __btree_sort(b, &iter, start, order, false, state); + __btree_sort(b, &iter.iter, start, order, false, state); EBUG_ON(oldsize >= 0 && bch_count_data(b) != oldsize); } @@ -1355,13 +1323,11 @@ void bch_btree_sort_into(struct btree_keys *b, struct btree_keys *new, struct bset_sort_state *state) { uint64_t start_time = local_clock(); - struct btree_iter iter; - - min_heap_init(&iter.heap, NULL, MAX_BSETS); + struct btree_iter_stack iter; - bch_btree_iter_init(b, &iter, NULL); + bch_btree_iter_stack_init(b, &iter, NULL); - btree_mergesort(b, new->set->data, &iter, false, true); + btree_mergesort(b, new->set->data, &iter.iter, false, true); bch_time_stats_update(&state->time, start_time); diff --git a/drivers/md/bcache/bset.h b/drivers/md/bcache/bset.h index f79441acd4c1..011f6062c4c0 100644 --- a/drivers/md/bcache/bset.h +++ b/drivers/md/bcache/bset.h @@ -187,9 +187,8 @@ struct bset_tree { }; struct btree_keys_ops { - bool (*sort_cmp)(const void *l, - const void *r, - void *args); + bool (*sort_cmp)(struct btree_iter_set l, + struct btree_iter_set r); struct bkey *(*sort_fixup)(struct btree_iter *iter, struct bkey *tmp); bool (*insert_fixup)(struct btree_keys *b, @@ -313,17 +312,23 @@ enum { BTREE_INSERT_STATUS_FRONT_MERGE, }; -struct btree_iter_set { - struct bkey *k, *end; -}; - /* Btree key iteration */ struct btree_iter { + size_t size, used; #ifdef CONFIG_BCACHE_DEBUG struct btree_keys *b; #endif - MIN_HEAP_PREALLOCATED(struct btree_iter_set, btree_iter_heap, MAX_BSETS) heap; + struct btree_iter_set { + struct bkey *k, *end; + } data[]; +}; + +/* Fixed-size btree_iter that can be allocated on the stack */ + +struct btree_iter_stack { + struct btree_iter iter; + struct btree_iter_set stack_data[MAX_BSETS]; }; typedef bool (*ptr_filter_fn)(struct btree_keys *b, const struct bkey *k); @@ -335,9 +340,9 @@ struct bkey *bch_btree_iter_next_filter(struct btree_iter *iter, void bch_btree_iter_push(struct btree_iter *iter, struct bkey *k, struct bkey *end); -struct bkey *bch_btree_iter_init(struct btree_keys *b, - struct btree_iter *iter, - struct bkey *search); +struct bkey *bch_btree_iter_stack_init(struct btree_keys *b, + struct btree_iter_stack *iter, + struct bkey *search); struct bkey *__bch_bset_search(struct btree_keys *b, struct bset_tree *t, const struct bkey *search); @@ -352,13 +357,14 @@ static inline struct bkey *bch_bset_search(struct btree_keys *b, return search ? __bch_bset_search(b, t, search) : t->data->start; } -#define for_each_key_filter(b, k, iter, filter) \ - for (bch_btree_iter_init((b), (iter), NULL); \ - ((k) = bch_btree_iter_next_filter((iter), (b), filter));) +#define for_each_key_filter(b, k, stack_iter, filter) \ + for (bch_btree_iter_stack_init((b), (stack_iter), NULL); \ + ((k) = bch_btree_iter_next_filter(&((stack_iter)->iter), (b), \ + filter));) -#define for_each_key(b, k, iter) \ - for (bch_btree_iter_init((b), (iter), NULL); \ - ((k) = bch_btree_iter_next(iter));) +#define for_each_key(b, k, stack_iter) \ + for (bch_btree_iter_stack_init((b), (stack_iter), NULL); \ + ((k) = bch_btree_iter_next(&((stack_iter)->iter)));) /* Sorting */ diff --git a/drivers/md/bcache/btree.c b/drivers/md/bcache/btree.c index 1d0100677357..210b59007d98 100644 --- a/drivers/md/bcache/btree.c +++ b/drivers/md/bcache/btree.c @@ -148,19 +148,19 @@ void bch_btree_node_read_done(struct btree *b) { const char *err = "bad btree header"; struct bset *i = btree_bset_first(b); - struct btree_iter iter; + struct btree_iter *iter; /* * c->fill_iter can allocate an iterator with more memory space * than static MAX_BSETS. * See the comment arount cache_set->fill_iter. */ - iter.heap.data = mempool_alloc(&b->c->fill_iter, GFP_NOIO); - iter.heap.size = b->c->cache->sb.bucket_size / b->c->cache->sb.block_size; - iter.heap.nr = 0; + iter = mempool_alloc(&b->c->fill_iter, GFP_NOIO); + iter->size = b->c->cache->sb.bucket_size / b->c->cache->sb.block_size; + iter->used = 0; #ifdef CONFIG_BCACHE_DEBUG - iter.b = &b->keys; + iter->b = &b->keys; #endif if (!i->seq) @@ -198,7 +198,7 @@ void bch_btree_node_read_done(struct btree *b) if (i != b->keys.set[0].data && !i->keys) goto err; - bch_btree_iter_push(&iter, i->start, bset_bkey_last(i)); + bch_btree_iter_push(iter, i->start, bset_bkey_last(i)); b->written += set_blocks(i, block_bytes(b->c->cache)); } @@ -210,7 +210,7 @@ void bch_btree_node_read_done(struct btree *b) if (i->seq == b->keys.set[0].data->seq) goto err; - bch_btree_sort_and_fix_extents(&b->keys, &iter, &b->c->sort); + bch_btree_sort_and_fix_extents(&b->keys, iter, &b->c->sort); i = b->keys.set[0].data; err = "short btree key"; @@ -222,7 +222,7 @@ void bch_btree_node_read_done(struct btree *b) bch_bset_init_next(&b->keys, write_block(b), bset_magic(&b->c->cache->sb)); out: - mempool_free(iter.heap.data, &b->c->fill_iter); + mempool_free(iter, &b->c->fill_iter); return; err: set_btree_node_io_error(b); @@ -1306,11 +1306,9 @@ static bool btree_gc_mark_node(struct btree *b, struct gc_stat *gc) uint8_t stale = 0; unsigned int keys = 0, good_keys = 0; struct bkey *k; - struct btree_iter iter; + struct btree_iter_stack iter; struct bset_tree *t; - min_heap_init(&iter.heap, NULL, MAX_BSETS); - gc->nodes++; for_each_key_filter(&b->keys, k, &iter, bch_ptr_invalid) { @@ -1569,11 +1567,9 @@ static int btree_gc_rewrite_node(struct btree *b, struct btree_op *op, static unsigned int btree_gc_count_keys(struct btree *b) { struct bkey *k; - struct btree_iter iter; + struct btree_iter_stack iter; unsigned int ret = 0; - min_heap_init(&iter.heap, NULL, MAX_BSETS); - for_each_key_filter(&b->keys, k, &iter, bch_ptr_bad) ret += bkey_u64s(k); @@ -1612,18 +1608,18 @@ static int btree_gc_recurse(struct btree *b, struct btree_op *op, int ret = 0; bool should_rewrite; struct bkey *k; - struct btree_iter iter; + struct btree_iter_stack iter; struct gc_merge_info r[GC_MERGE_NODES]; struct gc_merge_info *i, *last = r + ARRAY_SIZE(r) - 1; - min_heap_init(&iter.heap, NULL, MAX_BSETS); - bch_btree_iter_init(&b->keys, &iter, &b->c->gc_done); + bch_btree_iter_stack_init(&b->keys, &iter, &b->c->gc_done); for (i = r; i < r + ARRAY_SIZE(r); i++) i->b = ERR_PTR(-EINTR); while (1) { - k = bch_btree_iter_next_filter(&iter, &b->keys, bch_ptr_bad); + k = bch_btree_iter_next_filter(&iter.iter, &b->keys, + bch_ptr_bad); if (k) { r->b = bch_btree_node_get(b->c, op, k, b->level - 1, true, b); @@ -1918,9 +1914,7 @@ static int bch_btree_check_recurse(struct btree *b, struct btree_op *op) { int ret = 0; struct bkey *k, *p = NULL; - struct btree_iter iter; - - min_heap_init(&iter.heap, NULL, MAX_BSETS); + struct btree_iter_stack iter; for_each_key_filter(&b->keys, k, &iter, bch_ptr_invalid) bch_initial_mark_key(b->c, b->level, k); @@ -1928,10 +1922,10 @@ static int bch_btree_check_recurse(struct btree *b, struct btree_op *op) bch_initial_mark_key(b->c, b->level + 1, &b->key); if (b->level) { - bch_btree_iter_init(&b->keys, &iter, NULL); + bch_btree_iter_stack_init(&b->keys, &iter, NULL); do { - k = bch_btree_iter_next_filter(&iter, &b->keys, + k = bch_btree_iter_next_filter(&iter.iter, &b->keys, bch_ptr_bad); if (k) { btree_node_prefetch(b, k); @@ -1959,7 +1953,7 @@ static int bch_btree_check_thread(void *arg) struct btree_check_info *info = arg; struct btree_check_state *check_state = info->state; struct cache_set *c = check_state->c; - struct btree_iter iter; + struct btree_iter_stack iter; struct bkey *k, *p; int cur_idx, prev_idx, skip_nr; @@ -1967,11 +1961,9 @@ static int bch_btree_check_thread(void *arg) cur_idx = prev_idx = 0; ret = 0; - min_heap_init(&iter.heap, NULL, MAX_BSETS); - /* root node keys are checked before thread created */ - 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; @@ -1989,7 +1981,7 @@ static int bch_btree_check_thread(void *arg) 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) @@ -2062,11 +2054,9 @@ int bch_btree_check(struct cache_set *c) int ret = 0; int i; struct bkey *k = NULL; - struct btree_iter iter; + struct btree_iter_stack iter; struct btree_check_state check_state; - min_heap_init(&iter.heap, NULL, MAX_BSETS); - /* check and mark root node keys */ for_each_key_filter(&c->root->keys, k, &iter, bch_ptr_invalid) bch_initial_mark_key(c, c->root->level, k); @@ -2560,12 +2550,11 @@ static int bch_btree_map_nodes_recurse(struct btree *b, struct btree_op *op, if (b->level) { struct bkey *k; - struct btree_iter iter; + struct btree_iter_stack iter; - min_heap_init(&iter.heap, NULL, MAX_BSETS); - bch_btree_iter_init(&b->keys, &iter, from); + bch_btree_iter_stack_init(&b->keys, &iter, from); - while ((k = bch_btree_iter_next_filter(&iter, &b->keys, + while ((k = bch_btree_iter_next_filter(&iter.iter, &b->keys, bch_ptr_bad))) { ret = bcache_btree(map_nodes_recurse, k, b, op, from, fn, flags); @@ -2594,12 +2583,12 @@ int bch_btree_map_keys_recurse(struct btree *b, struct btree_op *op, { int ret = MAP_CONTINUE; struct bkey *k; - struct btree_iter iter; + struct btree_iter_stack iter; - min_heap_init(&iter.heap, NULL, MAX_BSETS); - bch_btree_iter_init(&b->keys, &iter, from); + bch_btree_iter_stack_init(&b->keys, &iter, from); - while ((k = bch_btree_iter_next_filter(&iter, &b->keys, bch_ptr_bad))) { + while ((k = bch_btree_iter_next_filter(&iter.iter, &b->keys, + bch_ptr_bad))) { ret = !b->level ? fn(op, b, k) : bcache_btree(map_keys_recurse, k, diff --git a/drivers/md/bcache/extents.c b/drivers/md/bcache/extents.c index a7221e5dbe81..d626ffcbecb9 100644 --- a/drivers/md/bcache/extents.c +++ b/drivers/md/bcache/extents.c @@ -33,16 +33,15 @@ static void sort_key_next(struct btree_iter *iter, i->k = bkey_next(i->k); if (i->k == i->end) - *i = iter->heap.data[--iter->heap.nr]; + *i = iter->data[--iter->used]; } -static bool new_bch_key_sort_cmp(const void *l, const void *r, void *args) +static bool bch_key_sort_cmp(struct btree_iter_set l, + struct btree_iter_set r) { - struct btree_iter_set *_l = (struct btree_iter_set *)l; - struct btree_iter_set *_r = (struct btree_iter_set *)r; - int64_t c = bkey_cmp(_l->k, _r->k); + int64_t c = bkey_cmp(l.k, r.k); - return !(c ? c > 0 : _l->k < _r->k); + return c ? c > 0 : l.k < r.k; } static bool __ptr_invalid(struct cache_set *c, const struct bkey *k) @@ -239,7 +238,7 @@ static bool bch_btree_ptr_insert_fixup(struct btree_keys *bk, } const struct btree_keys_ops bch_btree_keys_ops = { - .sort_cmp = new_bch_key_sort_cmp, + .sort_cmp = bch_key_sort_cmp, .insert_fixup = bch_btree_ptr_insert_fixup, .key_invalid = bch_btree_ptr_invalid, .key_bad = bch_btree_ptr_bad, @@ -256,36 +255,22 @@ const struct btree_keys_ops bch_btree_keys_ops = { * Necessary for btree_sort_fixup() - if there are multiple keys that compare * equal in different sets, we have to process them newest to oldest. */ - -static bool new_bch_extent_sort_cmp(const void *l, const void *r, void __always_unused *args) -{ - struct btree_iter_set *_l = (struct btree_iter_set *)l; - struct btree_iter_set *_r = (struct btree_iter_set *)r; - int64_t c = bkey_cmp(&START_KEY(_l->k), &START_KEY(_r->k)); - - return !(c ? c > 0 : _l->k < _r->k); -} - -static inline void new_btree_iter_swap(void *iter1, void *iter2, void __always_unused *args) +static bool bch_extent_sort_cmp(struct btree_iter_set l, + struct btree_iter_set r) { - struct btree_iter_set *_iter1 = iter1; - struct btree_iter_set *_iter2 = iter2; + int64_t c = bkey_cmp(&START_KEY(l.k), &START_KEY(r.k)); - swap(*_iter1, *_iter2); + return c ? c > 0 : l.k < r.k; } static struct bkey *bch_extent_sort_fixup(struct btree_iter *iter, struct bkey *tmp) { - const struct min_heap_callbacks callbacks = { - .less = new_bch_extent_sort_cmp, - .swp = new_btree_iter_swap, - }; - while (iter->heap.nr > 1) { - struct btree_iter_set *top = iter->heap.data, *i = top + 1; - - if (iter->heap.nr > 2 && - !new_bch_extent_sort_cmp(&i[0], &i[1], NULL)) + while (iter->used > 1) { + struct btree_iter_set *top = iter->data, *i = top + 1; + + if (iter->used > 2 && + bch_extent_sort_cmp(i[0], i[1])) i++; if (bkey_cmp(top->k, &START_KEY(i->k)) <= 0) @@ -293,7 +278,7 @@ static struct bkey *bch_extent_sort_fixup(struct btree_iter *iter, if (!KEY_SIZE(i->k)) { sort_key_next(iter, i); - min_heap_sift_down(&iter->heap, i - top, &callbacks, NULL); + heap_sift(iter, i - top, bch_extent_sort_cmp); continue; } @@ -303,7 +288,7 @@ static struct bkey *bch_extent_sort_fixup(struct btree_iter *iter, else bch_cut_front(top->k, i->k); - min_heap_sift_down(&iter->heap, i - top, &callbacks, NULL); + heap_sift(iter, i - top, bch_extent_sort_cmp); } else { /* can't happen because of comparison func */ BUG_ON(!bkey_cmp(&START_KEY(top->k), &START_KEY(i->k))); @@ -313,7 +298,7 @@ static struct bkey *bch_extent_sort_fixup(struct btree_iter *iter, bch_cut_back(&START_KEY(i->k), tmp); bch_cut_front(i->k, top->k); - min_heap_sift_down(&iter->heap, 0, &callbacks, NULL); + heap_sift(iter, 0, bch_extent_sort_cmp); return tmp; } else { @@ -633,7 +618,7 @@ static bool bch_extent_merge(struct btree_keys *bk, } const struct btree_keys_ops bch_extent_keys_ops = { - .sort_cmp = new_bch_extent_sort_cmp, + .sort_cmp = bch_extent_sort_cmp, .sort_fixup = bch_extent_sort_fixup, .insert_fixup = bch_extent_insert_fixup, .key_invalid = bch_extent_invalid, diff --git a/drivers/md/bcache/movinggc.c b/drivers/md/bcache/movinggc.c index d6c73dd8eb2b..26a6a535ec32 100644 --- a/drivers/md/bcache/movinggc.c +++ b/drivers/md/bcache/movinggc.c @@ -182,27 +182,16 @@ err: if (!IS_ERR_OR_NULL(w->private)) closure_sync(&cl); } -static bool new_bucket_cmp(const void *l, const void *r, void __always_unused *args) +static bool bucket_cmp(struct bucket *l, struct bucket *r) { - struct bucket **_l = (struct bucket **)l; - struct bucket **_r = (struct bucket **)r; - - return GC_SECTORS_USED(*_l) >= GC_SECTORS_USED(*_r); -} - -static void new_bucket_swap(void *l, void *r, void __always_unused *args) -{ - struct bucket **_l = l; - struct bucket **_r = r; - - swap(*_l, *_r); + return GC_SECTORS_USED(l) < GC_SECTORS_USED(r); } static unsigned int bucket_heap_top(struct cache *ca) { struct bucket *b; - return (b = min_heap_peek(&ca->heap)[0]) ? GC_SECTORS_USED(b) : 0; + return (b = heap_peek(&ca->heap)) ? GC_SECTORS_USED(b) : 0; } void bch_moving_gc(struct cache_set *c) @@ -210,10 +199,6 @@ void bch_moving_gc(struct cache_set *c) struct cache *ca = c->cache; struct bucket *b; unsigned long sectors_to_move, reserve_sectors; - const struct min_heap_callbacks callbacks = { - .less = new_bucket_cmp, - .swp = new_bucket_swap, - }; if (!c->copy_gc_enabled) return; @@ -224,7 +209,7 @@ void bch_moving_gc(struct cache_set *c) reserve_sectors = ca->sb.bucket_size * fifo_used(&ca->free[RESERVE_MOVINGGC]); - ca->heap.nr = 0; + ca->heap.used = 0; for_each_bucket(b, ca) { if (GC_MARK(b) == GC_MARK_METADATA || @@ -233,31 +218,25 @@ void bch_moving_gc(struct cache_set *c) atomic_read(&b->pin)) continue; - if (!min_heap_full(&ca->heap)) { + if (!heap_full(&ca->heap)) { sectors_to_move += GC_SECTORS_USED(b); - min_heap_push(&ca->heap, &b, &callbacks, NULL); - } else if (!new_bucket_cmp(&b, min_heap_peek(&ca->heap), ca)) { + heap_add(&ca->heap, b, bucket_cmp); + } else if (bucket_cmp(b, heap_peek(&ca->heap))) { sectors_to_move -= bucket_heap_top(ca); sectors_to_move += GC_SECTORS_USED(b); ca->heap.data[0] = b; - min_heap_sift_down(&ca->heap, 0, &callbacks, NULL); + heap_sift(&ca->heap, 0, bucket_cmp); } } while (sectors_to_move > reserve_sectors) { - if (ca->heap.nr) { - b = min_heap_peek(&ca->heap)[0]; - min_heap_pop(&ca->heap, &callbacks, NULL); - } + heap_pop(&ca->heap, b, bucket_cmp); sectors_to_move -= GC_SECTORS_USED(b); } - while (ca->heap.nr) { - b = min_heap_peek(&ca->heap)[0]; - min_heap_pop(&ca->heap, &callbacks, NULL); + while (heap_pop(&ca->heap, b, bucket_cmp)) SET_GC_MOVE(b, 1); - } mutex_unlock(&c->bucket_lock); diff --git a/drivers/md/bcache/super.c b/drivers/md/bcache/super.c index 1efb768b2890..2ea490b9d370 100644 --- a/drivers/md/bcache/super.c +++ b/drivers/md/bcache/super.c @@ -1912,7 +1912,8 @@ struct cache_set *bch_cache_set_alloc(struct cache_sb *sb) INIT_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); diff --git a/drivers/md/bcache/sysfs.c b/drivers/md/bcache/sysfs.c index e8f696cb58c0..826b14cae4e5 100644 --- a/drivers/md/bcache/sysfs.c +++ b/drivers/md/bcache/sysfs.c @@ -660,9 +660,7 @@ static unsigned int bch_root_usage(struct cache_set *c) unsigned 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; diff --git a/drivers/md/bcache/util.h b/drivers/md/bcache/util.h index 539454d8e2d0..f61ab1bada6c 100644 --- a/drivers/md/bcache/util.h +++ b/drivers/md/bcache/util.h @@ -9,7 +9,6 @@ #include <linux/kernel.h> #include <linux/sched/clock.h> #include <linux/llist.h> -#include <linux/min_heap.h> #include <linux/ratelimit.h> #include <linux/vmalloc.h> #include <linux/workqueue.h> @@ -31,10 +30,16 @@ struct closure; #endif +#define DECLARE_HEAP(type, name) \ + struct { \ + size_t size, used; \ + type *data; \ + } name + #define init_heap(heap, _size, gfp) \ ({ \ size_t _bytes; \ - (heap)->nr = 0; \ + (heap)->used = 0; \ (heap)->size = (_size); \ _bytes = (heap)->size * sizeof(*(heap)->data); \ (heap)->data = kvmalloc(_bytes, (gfp) & GFP_KERNEL); \ @@ -47,6 +52,64 @@ do { \ (heap)->data = NULL; \ } while (0) +#define heap_swap(h, i, j) swap((h)->data[i], (h)->data[j]) + +#define heap_sift(h, i, cmp) \ +do { \ + size_t _r, _j = i; \ + \ + for (; _j * 2 + 1 < (h)->used; _j = _r) { \ + _r = _j * 2 + 1; \ + if (_r + 1 < (h)->used && \ + cmp((h)->data[_r], (h)->data[_r + 1])) \ + _r++; \ + \ + if (cmp((h)->data[_r], (h)->data[_j])) \ + break; \ + heap_swap(h, _r, _j); \ + } \ +} while (0) + +#define heap_sift_down(h, i, cmp) \ +do { \ + while (i) { \ + size_t p = (i - 1) / 2; \ + if (cmp((h)->data[i], (h)->data[p])) \ + break; \ + heap_swap(h, i, p); \ + i = p; \ + } \ +} while (0) + +#define heap_add(h, d, cmp) \ +({ \ + bool _r = !heap_full(h); \ + if (_r) { \ + size_t _i = (h)->used++; \ + (h)->data[_i] = d; \ + \ + heap_sift_down(h, _i, cmp); \ + heap_sift(h, _i, cmp); \ + } \ + _r; \ +}) + +#define heap_pop(h, d, cmp) \ +({ \ + bool _r = (h)->used; \ + if (_r) { \ + (d) = (h)->data[0]; \ + (h)->used--; \ + heap_swap(h, 0, (h)->used); \ + heap_sift(h, 0, cmp); \ + } \ + _r; \ +}) + +#define heap_peek(h) ((h)->used ? (h)->data[0] : NULL) + +#define heap_full(h) ((h)->used == (h)->size) + #define DECLARE_FIFO(type, name) \ struct { \ size_t front, back, size, mask; \ diff --git a/drivers/md/bcache/writeback.c b/drivers/md/bcache/writeback.c index 453efbbdc8ee..302e75f1fc4b 100644 --- a/drivers/md/bcache/writeback.c +++ b/drivers/md/bcache/writeback.c @@ -908,16 +908,15 @@ static int bch_dirty_init_thread(void *arg) struct 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 *arg) 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 bcache_device *d) int 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); -- 2.34.1 ^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [PATCH v2 2/3] Revert "bcache: remove heap-related macros and switch to generic min_heap" 2025-06-14 20:23 ` [PATCH v2 2/3] Revert "bcache: remove heap-related macros and switch to generic min_heap" Kuan-Wei Chiu @ 2025-06-15 5:51 ` Coly Li 0 siblings, 0 replies; 7+ messages in thread From: Coly Li @ 2025-06-15 5:51 UTC (permalink / raw) To: Kuan-Wei Chiu Cc: akpm, kent.overstreet, robertpang, linux-kernel, linux-bcache, jserv, stable On Sun, Jun 15, 2025 at 04:23:52AM +0800, Kuan-Wei Chiu wrote: > 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. > > Link: https://lore.kernel.org/lkml/CAJhEC05+0S69z+3+FB2Cd0hD+pCRyWTKLEOsc8BOmH73p1m+KQ@mail.gmail.com > 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@google.com> > Closes: https://lore.kernel.org/linux-bcache/CAJhEC06F_AtrPgw2-7CvCqZgeStgCtitbD-ryuPpXQA-JG5XXw@mail.gmail.com > Cc: stable@vger.kernel.org > Signed-off-by: Kuan-Wei Chiu <visitorckw@gmail.com> Acked-by: Coly Li <colyli@kernel.org> Thanks. > --- > drivers/md/bcache/alloc.c | 64 +++++------------- > drivers/md/bcache/bcache.h | 2 +- > drivers/md/bcache/bset.c | 124 ++++++++++++---------------------- > drivers/md/bcache/bset.h | 40 ++++++----- > drivers/md/bcache/btree.c | 69 ++++++++----------- > drivers/md/bcache/extents.c | 53 ++++++--------- > 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(-) > > diff --git a/drivers/md/bcache/alloc.c b/drivers/md/bcache/alloc.c > index da50f6661bae..48ce750bf70a 100644 > --- a/drivers/md/bcache/alloc.c > +++ b/drivers/md/bcache/alloc.c > @@ -164,68 +164,40 @@ static void bch_invalidate_one_bucket(struct cache *ca, struct bucket *b) > * 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(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); > > bch_invalidate_one_bucket(ca, b); > } > diff --git a/drivers/md/bcache/bcache.h b/drivers/md/bcache/bcache.h > index 785b0d9008fa..1d33e40d26ea 100644 > --- a/drivers/md/bcache/bcache.h > +++ b/drivers/md/bcache/bcache.h > @@ -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 > diff --git a/drivers/md/bcache/bset.c b/drivers/md/bcache/bset.c > index bd97d8626887..463eb13bd0b2 100644 > --- a/drivers/md/bcache/bset.c > +++ b/drivers/md/bcache/bset.c > @@ -54,11 +54,9 @@ void bch_dump_bucket(struct btree_keys *b) > int __bch_count_data(struct btree_keys *b) > { > unsigned int ret = 0; > - struct btree_iter iter; > + struct btree_iter_stack iter; > struct bkey *k; > > - min_heap_init(&iter.heap, NULL, MAX_BSETS); > - > if (b->ops->is_extents) > for_each_key(b, k, &iter) > ret += KEY_SIZE(k); > @@ -69,11 +67,9 @@ void __bch_check_keys(struct btree_keys *b, const char *fmt, ...) > { > va_list args; > struct bkey *k, *p = NULL; > - struct btree_iter iter; > + struct btree_iter_stack iter; > const char *err; > > - min_heap_init(&iter.heap, NULL, MAX_BSETS); > - > for_each_key(b, k, &iter) { > if (b->ops->is_extents) { > err = "Keys out of order"; > @@ -114,9 +110,9 @@ void __bch_check_keys(struct btree_keys *b, const char *fmt, ...) > > static void bch_btree_iter_next_check(struct btree_iter *iter) > { > - struct bkey *k = iter->heap.data->k, *next = bkey_next(k); > + struct bkey *k = iter->data->k, *next = bkey_next(k); > > - if (next < iter->heap.data->end && > + if (next < iter->data->end && > bkey_cmp(k, iter->b->ops->is_extents ? > &START_KEY(next) : next) > 0) { > bch_dump_bucket(iter->b); > @@ -883,14 +879,12 @@ unsigned int bch_btree_insert_key(struct btree_keys *b, struct bkey *k, > unsigned int status = BTREE_INSERT_STATUS_NO_INSERT; > struct bset *i = bset_tree_last(b)->data; > struct bkey *m, *prev = NULL; > - struct btree_iter iter; > + struct btree_iter_stack iter; > struct bkey preceding_key_on_stack = ZERO_KEY; > struct bkey *preceding_key_p = &preceding_key_on_stack; > > BUG_ON(b->ops->is_extents && !KEY_SIZE(k)); > > - min_heap_init(&iter.heap, NULL, MAX_BSETS); > - > /* > * If k has preceding key, preceding_key_p will be set to address > * of k's preceding key; otherwise preceding_key_p will be set > @@ -901,9 +895,9 @@ unsigned int bch_btree_insert_key(struct btree_keys *b, struct bkey *k, > else > preceding_key(k, &preceding_key_p); > > - m = bch_btree_iter_init(b, &iter, preceding_key_p); > + m = bch_btree_iter_stack_init(b, &iter, preceding_key_p); > > - if (b->ops->insert_fixup(b, k, &iter, replace_key)) > + if (b->ops->insert_fixup(b, k, &iter.iter, replace_key)) > return status; > > status = BTREE_INSERT_STATUS_INSERT; > @@ -1083,102 +1077,79 @@ struct bkey *__bch_bset_search(struct btree_keys *b, struct bset_tree *t, > > /* Btree iterator */ > > -typedef bool (new_btree_iter_cmp_fn)(const void *, const void *, void *); > - > -static inline bool new_btree_iter_cmp(const void *l, const void *r, void __always_unused *args) > -{ > - const struct btree_iter_set *_l = l; > - const struct btree_iter_set *_r = r; > - > - return bkey_cmp(_l->k, _r->k) <= 0; > -} > +typedef bool (btree_iter_cmp_fn)(struct btree_iter_set, > + struct btree_iter_set); > > -static inline void new_btree_iter_swap(void *iter1, void *iter2, void __always_unused *args) > +static inline bool btree_iter_cmp(struct btree_iter_set l, > + struct btree_iter_set r) > { > - struct btree_iter_set *_iter1 = iter1; > - struct btree_iter_set *_iter2 = iter2; > - > - swap(*_iter1, *_iter2); > + return bkey_cmp(l.k, r.k) > 0; > } > > static inline bool btree_iter_end(struct btree_iter *iter) > { > - return !iter->heap.nr; > + return !iter->used; > } > > void bch_btree_iter_push(struct btree_iter *iter, struct bkey *k, > struct bkey *end) > { > - const struct min_heap_callbacks callbacks = { > - .less = new_btree_iter_cmp, > - .swp = new_btree_iter_swap, > - }; > - > if (k != end) > - BUG_ON(!min_heap_push(&iter->heap, > - &((struct btree_iter_set) { k, end }), > - &callbacks, > - NULL)); > + BUG_ON(!heap_add(iter, > + ((struct btree_iter_set) { k, end }), > + btree_iter_cmp)); > } > > -static struct bkey *__bch_btree_iter_init(struct btree_keys *b, > - struct btree_iter *iter, > - struct bkey *search, > - struct bset_tree *start) > +static struct bkey *__bch_btree_iter_stack_init(struct btree_keys *b, > + struct btree_iter_stack *iter, > + struct bkey *search, > + struct bset_tree *start) > { > struct bkey *ret = NULL; > > - iter->heap.size = ARRAY_SIZE(iter->heap.preallocated); > - iter->heap.nr = 0; > + iter->iter.size = ARRAY_SIZE(iter->stack_data); > + iter->iter.used = 0; > > #ifdef CONFIG_BCACHE_DEBUG > - iter->b = b; > + iter->iter.b = b; > #endif > > for (; start <= bset_tree_last(b); start++) { > ret = bch_bset_search(b, start, search); > - bch_btree_iter_push(iter, ret, bset_bkey_last(start->data)); > + bch_btree_iter_push(&iter->iter, ret, bset_bkey_last(start->data)); > } > > return ret; > } > > -struct bkey *bch_btree_iter_init(struct btree_keys *b, > - struct btree_iter *iter, > +struct bkey *bch_btree_iter_stack_init(struct btree_keys *b, > + struct btree_iter_stack *iter, > struct bkey *search) > { > - return __bch_btree_iter_init(b, iter, search, b->set); > + return __bch_btree_iter_stack_init(b, iter, search, b->set); > } > > static inline struct bkey *__bch_btree_iter_next(struct btree_iter *iter, > - new_btree_iter_cmp_fn *cmp) > + btree_iter_cmp_fn *cmp) > { > struct btree_iter_set b __maybe_unused; > struct bkey *ret = NULL; > - const struct min_heap_callbacks callbacks = { > - .less = cmp, > - .swp = new_btree_iter_swap, > - }; > > if (!btree_iter_end(iter)) { > bch_btree_iter_next_check(iter); > > - ret = iter->heap.data->k; > - iter->heap.data->k = bkey_next(iter->heap.data->k); > + ret = iter->data->k; > + iter->data->k = bkey_next(iter->data->k); > > - if (iter->heap.data->k > iter->heap.data->end) { > + if (iter->data->k > iter->data->end) { > WARN_ONCE(1, "bset was corrupt!\n"); > - iter->heap.data->k = iter->heap.data->end; > + iter->data->k = iter->data->end; > } > > - if (iter->heap.data->k == iter->heap.data->end) { > - if (iter->heap.nr) { > - b = min_heap_peek(&iter->heap)[0]; > - min_heap_pop(&iter->heap, &callbacks, NULL); > - } > - } > + if (iter->data->k == iter->data->end) > + heap_pop(iter, b, cmp); > else > - min_heap_sift_down(&iter->heap, 0, &callbacks, NULL); > + heap_sift(iter, 0, cmp); > } > > return ret; > @@ -1186,7 +1157,7 @@ static inline struct bkey *__bch_btree_iter_next(struct btree_iter *iter, > > struct bkey *bch_btree_iter_next(struct btree_iter *iter) > { > - return __bch_btree_iter_next(iter, new_btree_iter_cmp); > + return __bch_btree_iter_next(iter, btree_iter_cmp); > > } > > @@ -1224,18 +1195,16 @@ static void btree_mergesort(struct btree_keys *b, struct bset *out, > struct btree_iter *iter, > bool fixup, bool remove_stale) > { > + int i; > struct bkey *k, *last = NULL; > BKEY_PADDED(k) tmp; > bool (*bad)(struct btree_keys *, const struct bkey *) = remove_stale > ? bch_ptr_bad > : bch_ptr_invalid; > - const struct min_heap_callbacks callbacks = { > - .less = b->ops->sort_cmp, > - .swp = new_btree_iter_swap, > - }; > > /* Heapify the iterator, using our comparison function */ > - min_heapify_all(&iter->heap, &callbacks, NULL); > + for (i = iter->used / 2 - 1; i >= 0; --i) > + heap_sift(iter, i, b->ops->sort_cmp); > > while (!btree_iter_end(iter)) { > if (b->ops->sort_fixup && fixup) > @@ -1324,11 +1293,10 @@ void bch_btree_sort_partial(struct btree_keys *b, unsigned int start, > struct bset_sort_state *state) > { > size_t order = b->page_order, keys = 0; > - struct btree_iter iter; > + struct btree_iter_stack iter; > int oldsize = bch_count_data(b); > > - min_heap_init(&iter.heap, NULL, MAX_BSETS); > - __bch_btree_iter_init(b, &iter, NULL, &b->set[start]); > + __bch_btree_iter_stack_init(b, &iter, NULL, &b->set[start]); > > if (start) { > unsigned int i; > @@ -1339,7 +1307,7 @@ void bch_btree_sort_partial(struct btree_keys *b, unsigned int start, > order = get_order(__set_bytes(b->set->data, keys)); > } > > - __btree_sort(b, &iter, start, order, false, state); > + __btree_sort(b, &iter.iter, start, order, false, state); > > EBUG_ON(oldsize >= 0 && bch_count_data(b) != oldsize); > } > @@ -1355,13 +1323,11 @@ void bch_btree_sort_into(struct btree_keys *b, struct btree_keys *new, > struct bset_sort_state *state) > { > uint64_t start_time = local_clock(); > - struct btree_iter iter; > - > - min_heap_init(&iter.heap, NULL, MAX_BSETS); > + struct btree_iter_stack iter; > > - bch_btree_iter_init(b, &iter, NULL); > + bch_btree_iter_stack_init(b, &iter, NULL); > > - btree_mergesort(b, new->set->data, &iter, false, true); > + btree_mergesort(b, new->set->data, &iter.iter, false, true); > > bch_time_stats_update(&state->time, start_time); > > diff --git a/drivers/md/bcache/bset.h b/drivers/md/bcache/bset.h > index f79441acd4c1..011f6062c4c0 100644 > --- a/drivers/md/bcache/bset.h > +++ b/drivers/md/bcache/bset.h > @@ -187,9 +187,8 @@ struct bset_tree { > }; > > struct btree_keys_ops { > - bool (*sort_cmp)(const void *l, > - const void *r, > - void *args); > + bool (*sort_cmp)(struct btree_iter_set l, > + struct btree_iter_set r); > struct bkey *(*sort_fixup)(struct btree_iter *iter, > struct bkey *tmp); > bool (*insert_fixup)(struct btree_keys *b, > @@ -313,17 +312,23 @@ enum { > BTREE_INSERT_STATUS_FRONT_MERGE, > }; > > -struct btree_iter_set { > - struct bkey *k, *end; > -}; > - > /* Btree key iteration */ > > struct btree_iter { > + size_t size, used; > #ifdef CONFIG_BCACHE_DEBUG > struct btree_keys *b; > #endif > - MIN_HEAP_PREALLOCATED(struct btree_iter_set, btree_iter_heap, MAX_BSETS) heap; > + struct btree_iter_set { > + struct bkey *k, *end; > + } data[]; > +}; > + > +/* Fixed-size btree_iter that can be allocated on the stack */ > + > +struct btree_iter_stack { > + struct btree_iter iter; > + struct btree_iter_set stack_data[MAX_BSETS]; > }; > > typedef bool (*ptr_filter_fn)(struct btree_keys *b, const struct bkey *k); > @@ -335,9 +340,9 @@ struct bkey *bch_btree_iter_next_filter(struct btree_iter *iter, > > void bch_btree_iter_push(struct btree_iter *iter, struct bkey *k, > struct bkey *end); > -struct bkey *bch_btree_iter_init(struct btree_keys *b, > - struct btree_iter *iter, > - struct bkey *search); > +struct bkey *bch_btree_iter_stack_init(struct btree_keys *b, > + struct btree_iter_stack *iter, > + struct bkey *search); > > struct bkey *__bch_bset_search(struct btree_keys *b, struct bset_tree *t, > const struct bkey *search); > @@ -352,13 +357,14 @@ static inline struct bkey *bch_bset_search(struct btree_keys *b, > return search ? __bch_bset_search(b, t, search) : t->data->start; > } > > -#define for_each_key_filter(b, k, iter, filter) \ > - for (bch_btree_iter_init((b), (iter), NULL); \ > - ((k) = bch_btree_iter_next_filter((iter), (b), filter));) > +#define for_each_key_filter(b, k, stack_iter, filter) \ > + for (bch_btree_iter_stack_init((b), (stack_iter), NULL); \ > + ((k) = bch_btree_iter_next_filter(&((stack_iter)->iter), (b), \ > + filter));) > > -#define for_each_key(b, k, iter) \ > - for (bch_btree_iter_init((b), (iter), NULL); \ > - ((k) = bch_btree_iter_next(iter));) > +#define for_each_key(b, k, stack_iter) \ > + for (bch_btree_iter_stack_init((b), (stack_iter), NULL); \ > + ((k) = bch_btree_iter_next(&((stack_iter)->iter)));) > > /* Sorting */ > > diff --git a/drivers/md/bcache/btree.c b/drivers/md/bcache/btree.c > index 1d0100677357..210b59007d98 100644 > --- a/drivers/md/bcache/btree.c > +++ b/drivers/md/bcache/btree.c > @@ -148,19 +148,19 @@ void bch_btree_node_read_done(struct btree *b) > { > const char *err = "bad btree header"; > struct bset *i = btree_bset_first(b); > - struct btree_iter iter; > + struct btree_iter *iter; > > /* > * c->fill_iter can allocate an iterator with more memory space > * than static MAX_BSETS. > * See the comment arount cache_set->fill_iter. > */ > - iter.heap.data = mempool_alloc(&b->c->fill_iter, GFP_NOIO); > - iter.heap.size = b->c->cache->sb.bucket_size / b->c->cache->sb.block_size; > - iter.heap.nr = 0; > + iter = mempool_alloc(&b->c->fill_iter, GFP_NOIO); > + iter->size = b->c->cache->sb.bucket_size / b->c->cache->sb.block_size; > + iter->used = 0; > > #ifdef CONFIG_BCACHE_DEBUG > - iter.b = &b->keys; > + iter->b = &b->keys; > #endif > > if (!i->seq) > @@ -198,7 +198,7 @@ void bch_btree_node_read_done(struct btree *b) > if (i != b->keys.set[0].data && !i->keys) > goto err; > > - bch_btree_iter_push(&iter, i->start, bset_bkey_last(i)); > + bch_btree_iter_push(iter, i->start, bset_bkey_last(i)); > > b->written += set_blocks(i, block_bytes(b->c->cache)); > } > @@ -210,7 +210,7 @@ void bch_btree_node_read_done(struct btree *b) > if (i->seq == b->keys.set[0].data->seq) > goto err; > > - bch_btree_sort_and_fix_extents(&b->keys, &iter, &b->c->sort); > + bch_btree_sort_and_fix_extents(&b->keys, iter, &b->c->sort); > > i = b->keys.set[0].data; > err = "short btree key"; > @@ -222,7 +222,7 @@ void bch_btree_node_read_done(struct btree *b) > bch_bset_init_next(&b->keys, write_block(b), > bset_magic(&b->c->cache->sb)); > out: > - mempool_free(iter.heap.data, &b->c->fill_iter); > + mempool_free(iter, &b->c->fill_iter); > return; > err: > set_btree_node_io_error(b); > @@ -1306,11 +1306,9 @@ static bool btree_gc_mark_node(struct btree *b, struct gc_stat *gc) > uint8_t stale = 0; > unsigned int keys = 0, good_keys = 0; > struct bkey *k; > - struct btree_iter iter; > + struct btree_iter_stack iter; > struct bset_tree *t; > > - min_heap_init(&iter.heap, NULL, MAX_BSETS); > - > gc->nodes++; > > for_each_key_filter(&b->keys, k, &iter, bch_ptr_invalid) { > @@ -1569,11 +1567,9 @@ static int btree_gc_rewrite_node(struct btree *b, struct btree_op *op, > static unsigned int btree_gc_count_keys(struct btree *b) > { > struct bkey *k; > - struct btree_iter iter; > + struct btree_iter_stack iter; > unsigned int ret = 0; > > - min_heap_init(&iter.heap, NULL, MAX_BSETS); > - > for_each_key_filter(&b->keys, k, &iter, bch_ptr_bad) > ret += bkey_u64s(k); > > @@ -1612,18 +1608,18 @@ static int btree_gc_recurse(struct btree *b, struct btree_op *op, > int ret = 0; > bool should_rewrite; > struct bkey *k; > - struct btree_iter iter; > + struct btree_iter_stack iter; > struct gc_merge_info r[GC_MERGE_NODES]; > struct gc_merge_info *i, *last = r + ARRAY_SIZE(r) - 1; > > - min_heap_init(&iter.heap, NULL, MAX_BSETS); > - bch_btree_iter_init(&b->keys, &iter, &b->c->gc_done); > + bch_btree_iter_stack_init(&b->keys, &iter, &b->c->gc_done); > > for (i = r; i < r + ARRAY_SIZE(r); i++) > i->b = ERR_PTR(-EINTR); > > while (1) { > - k = bch_btree_iter_next_filter(&iter, &b->keys, bch_ptr_bad); > + k = bch_btree_iter_next_filter(&iter.iter, &b->keys, > + bch_ptr_bad); > if (k) { > r->b = bch_btree_node_get(b->c, op, k, b->level - 1, > true, b); > @@ -1918,9 +1914,7 @@ static int bch_btree_check_recurse(struct btree *b, struct btree_op *op) > { > int ret = 0; > struct bkey *k, *p = NULL; > - struct btree_iter iter; > - > - min_heap_init(&iter.heap, NULL, MAX_BSETS); > + struct btree_iter_stack iter; > > for_each_key_filter(&b->keys, k, &iter, bch_ptr_invalid) > bch_initial_mark_key(b->c, b->level, k); > @@ -1928,10 +1922,10 @@ static int bch_btree_check_recurse(struct btree *b, struct btree_op *op) > bch_initial_mark_key(b->c, b->level + 1, &b->key); > > if (b->level) { > - bch_btree_iter_init(&b->keys, &iter, NULL); > + bch_btree_iter_stack_init(&b->keys, &iter, NULL); > > do { > - k = bch_btree_iter_next_filter(&iter, &b->keys, > + k = bch_btree_iter_next_filter(&iter.iter, &b->keys, > bch_ptr_bad); > if (k) { > btree_node_prefetch(b, k); > @@ -1959,7 +1953,7 @@ static int bch_btree_check_thread(void *arg) > struct btree_check_info *info = arg; > struct btree_check_state *check_state = info->state; > struct cache_set *c = check_state->c; > - struct btree_iter iter; > + struct btree_iter_stack iter; > struct bkey *k, *p; > int cur_idx, prev_idx, skip_nr; > > @@ -1967,11 +1961,9 @@ static int bch_btree_check_thread(void *arg) > cur_idx = prev_idx = 0; > ret = 0; > > - min_heap_init(&iter.heap, NULL, MAX_BSETS); > - > /* root node keys are checked before thread created */ > - 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; > @@ -1989,7 +1981,7 @@ static int bch_btree_check_thread(void *arg) > 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) > @@ -2062,11 +2054,9 @@ int bch_btree_check(struct cache_set *c) > int ret = 0; > int i; > struct bkey *k = NULL; > - struct btree_iter iter; > + struct btree_iter_stack iter; > struct btree_check_state check_state; > > - min_heap_init(&iter.heap, NULL, MAX_BSETS); > - > /* check and mark root node keys */ > for_each_key_filter(&c->root->keys, k, &iter, bch_ptr_invalid) > bch_initial_mark_key(c, c->root->level, k); > @@ -2560,12 +2550,11 @@ static int bch_btree_map_nodes_recurse(struct btree *b, struct btree_op *op, > > if (b->level) { > struct bkey *k; > - struct btree_iter iter; > + struct btree_iter_stack iter; > > - min_heap_init(&iter.heap, NULL, MAX_BSETS); > - bch_btree_iter_init(&b->keys, &iter, from); > + bch_btree_iter_stack_init(&b->keys, &iter, from); > > - while ((k = bch_btree_iter_next_filter(&iter, &b->keys, > + while ((k = bch_btree_iter_next_filter(&iter.iter, &b->keys, > bch_ptr_bad))) { > ret = bcache_btree(map_nodes_recurse, k, b, > op, from, fn, flags); > @@ -2594,12 +2583,12 @@ int bch_btree_map_keys_recurse(struct btree *b, struct btree_op *op, > { > int ret = MAP_CONTINUE; > struct bkey *k; > - struct btree_iter iter; > + struct btree_iter_stack iter; > > - min_heap_init(&iter.heap, NULL, MAX_BSETS); > - bch_btree_iter_init(&b->keys, &iter, from); > + bch_btree_iter_stack_init(&b->keys, &iter, from); > > - while ((k = bch_btree_iter_next_filter(&iter, &b->keys, bch_ptr_bad))) { > + while ((k = bch_btree_iter_next_filter(&iter.iter, &b->keys, > + bch_ptr_bad))) { > ret = !b->level > ? fn(op, b, k) > : bcache_btree(map_keys_recurse, k, > diff --git a/drivers/md/bcache/extents.c b/drivers/md/bcache/extents.c > index a7221e5dbe81..d626ffcbecb9 100644 > --- a/drivers/md/bcache/extents.c > +++ b/drivers/md/bcache/extents.c > @@ -33,16 +33,15 @@ static void sort_key_next(struct btree_iter *iter, > i->k = bkey_next(i->k); > > if (i->k == i->end) > - *i = iter->heap.data[--iter->heap.nr]; > + *i = iter->data[--iter->used]; > } > > -static bool new_bch_key_sort_cmp(const void *l, const void *r, void *args) > +static bool bch_key_sort_cmp(struct btree_iter_set l, > + struct btree_iter_set r) > { > - struct btree_iter_set *_l = (struct btree_iter_set *)l; > - struct btree_iter_set *_r = (struct btree_iter_set *)r; > - int64_t c = bkey_cmp(_l->k, _r->k); > + int64_t c = bkey_cmp(l.k, r.k); > > - return !(c ? c > 0 : _l->k < _r->k); > + return c ? c > 0 : l.k < r.k; > } > > static bool __ptr_invalid(struct cache_set *c, const struct bkey *k) > @@ -239,7 +238,7 @@ static bool bch_btree_ptr_insert_fixup(struct btree_keys *bk, > } > > const struct btree_keys_ops bch_btree_keys_ops = { > - .sort_cmp = new_bch_key_sort_cmp, > + .sort_cmp = bch_key_sort_cmp, > .insert_fixup = bch_btree_ptr_insert_fixup, > .key_invalid = bch_btree_ptr_invalid, > .key_bad = bch_btree_ptr_bad, > @@ -256,36 +255,22 @@ const struct btree_keys_ops bch_btree_keys_ops = { > * Necessary for btree_sort_fixup() - if there are multiple keys that compare > * equal in different sets, we have to process them newest to oldest. > */ > - > -static bool new_bch_extent_sort_cmp(const void *l, const void *r, void __always_unused *args) > -{ > - struct btree_iter_set *_l = (struct btree_iter_set *)l; > - struct btree_iter_set *_r = (struct btree_iter_set *)r; > - int64_t c = bkey_cmp(&START_KEY(_l->k), &START_KEY(_r->k)); > - > - return !(c ? c > 0 : _l->k < _r->k); > -} > - > -static inline void new_btree_iter_swap(void *iter1, void *iter2, void __always_unused *args) > +static bool bch_extent_sort_cmp(struct btree_iter_set l, > + struct btree_iter_set r) > { > - struct btree_iter_set *_iter1 = iter1; > - struct btree_iter_set *_iter2 = iter2; > + int64_t c = bkey_cmp(&START_KEY(l.k), &START_KEY(r.k)); > > - swap(*_iter1, *_iter2); > + return c ? c > 0 : l.k < r.k; > } > > static struct bkey *bch_extent_sort_fixup(struct btree_iter *iter, > struct bkey *tmp) > { > - const struct min_heap_callbacks callbacks = { > - .less = new_bch_extent_sort_cmp, > - .swp = new_btree_iter_swap, > - }; > - while (iter->heap.nr > 1) { > - struct btree_iter_set *top = iter->heap.data, *i = top + 1; > - > - if (iter->heap.nr > 2 && > - !new_bch_extent_sort_cmp(&i[0], &i[1], NULL)) > + while (iter->used > 1) { > + struct btree_iter_set *top = iter->data, *i = top + 1; > + > + if (iter->used > 2 && > + bch_extent_sort_cmp(i[0], i[1])) > i++; > > if (bkey_cmp(top->k, &START_KEY(i->k)) <= 0) > @@ -293,7 +278,7 @@ static struct bkey *bch_extent_sort_fixup(struct btree_iter *iter, > > if (!KEY_SIZE(i->k)) { > sort_key_next(iter, i); > - min_heap_sift_down(&iter->heap, i - top, &callbacks, NULL); > + heap_sift(iter, i - top, bch_extent_sort_cmp); > continue; > } > > @@ -303,7 +288,7 @@ static struct bkey *bch_extent_sort_fixup(struct btree_iter *iter, > else > bch_cut_front(top->k, i->k); > > - min_heap_sift_down(&iter->heap, i - top, &callbacks, NULL); > + heap_sift(iter, i - top, bch_extent_sort_cmp); > } else { > /* can't happen because of comparison func */ > BUG_ON(!bkey_cmp(&START_KEY(top->k), &START_KEY(i->k))); > @@ -313,7 +298,7 @@ static struct bkey *bch_extent_sort_fixup(struct btree_iter *iter, > > bch_cut_back(&START_KEY(i->k), tmp); > bch_cut_front(i->k, top->k); > - min_heap_sift_down(&iter->heap, 0, &callbacks, NULL); > + heap_sift(iter, 0, bch_extent_sort_cmp); > > return tmp; > } else { > @@ -633,7 +618,7 @@ static bool bch_extent_merge(struct btree_keys *bk, > } > > const struct btree_keys_ops bch_extent_keys_ops = { > - .sort_cmp = new_bch_extent_sort_cmp, > + .sort_cmp = bch_extent_sort_cmp, > .sort_fixup = bch_extent_sort_fixup, > .insert_fixup = bch_extent_insert_fixup, > .key_invalid = bch_extent_invalid, > diff --git a/drivers/md/bcache/movinggc.c b/drivers/md/bcache/movinggc.c > index d6c73dd8eb2b..26a6a535ec32 100644 > --- a/drivers/md/bcache/movinggc.c > +++ b/drivers/md/bcache/movinggc.c > @@ -182,27 +182,16 @@ err: if (!IS_ERR_OR_NULL(w->private)) > closure_sync(&cl); > } > > -static bool new_bucket_cmp(const void *l, const void *r, void __always_unused *args) > +static bool bucket_cmp(struct bucket *l, struct bucket *r) > { > - struct bucket **_l = (struct bucket **)l; > - struct bucket **_r = (struct bucket **)r; > - > - return GC_SECTORS_USED(*_l) >= GC_SECTORS_USED(*_r); > -} > - > -static void new_bucket_swap(void *l, void *r, void __always_unused *args) > -{ > - struct bucket **_l = l; > - struct bucket **_r = r; > - > - swap(*_l, *_r); > + return GC_SECTORS_USED(l) < GC_SECTORS_USED(r); > } > > static unsigned int bucket_heap_top(struct cache *ca) > { > struct bucket *b; > > - return (b = min_heap_peek(&ca->heap)[0]) ? GC_SECTORS_USED(b) : 0; > + return (b = heap_peek(&ca->heap)) ? GC_SECTORS_USED(b) : 0; > } > > void bch_moving_gc(struct cache_set *c) > @@ -210,10 +199,6 @@ void bch_moving_gc(struct cache_set *c) > struct cache *ca = c->cache; > struct bucket *b; > unsigned long sectors_to_move, reserve_sectors; > - const struct min_heap_callbacks callbacks = { > - .less = new_bucket_cmp, > - .swp = new_bucket_swap, > - }; > > if (!c->copy_gc_enabled) > return; > @@ -224,7 +209,7 @@ void bch_moving_gc(struct cache_set *c) > reserve_sectors = ca->sb.bucket_size * > fifo_used(&ca->free[RESERVE_MOVINGGC]); > > - ca->heap.nr = 0; > + ca->heap.used = 0; > > for_each_bucket(b, ca) { > if (GC_MARK(b) == GC_MARK_METADATA || > @@ -233,31 +218,25 @@ void bch_moving_gc(struct cache_set *c) > atomic_read(&b->pin)) > continue; > > - if (!min_heap_full(&ca->heap)) { > + if (!heap_full(&ca->heap)) { > sectors_to_move += GC_SECTORS_USED(b); > - min_heap_push(&ca->heap, &b, &callbacks, NULL); > - } else if (!new_bucket_cmp(&b, min_heap_peek(&ca->heap), ca)) { > + heap_add(&ca->heap, b, bucket_cmp); > + } else if (bucket_cmp(b, heap_peek(&ca->heap))) { > sectors_to_move -= bucket_heap_top(ca); > sectors_to_move += GC_SECTORS_USED(b); > > ca->heap.data[0] = b; > - min_heap_sift_down(&ca->heap, 0, &callbacks, NULL); > + heap_sift(&ca->heap, 0, bucket_cmp); > } > } > > while (sectors_to_move > reserve_sectors) { > - if (ca->heap.nr) { > - b = min_heap_peek(&ca->heap)[0]; > - min_heap_pop(&ca->heap, &callbacks, NULL); > - } > + heap_pop(&ca->heap, b, bucket_cmp); > sectors_to_move -= GC_SECTORS_USED(b); > } > > - while (ca->heap.nr) { > - b = min_heap_peek(&ca->heap)[0]; > - min_heap_pop(&ca->heap, &callbacks, NULL); > + while (heap_pop(&ca->heap, b, bucket_cmp)) > SET_GC_MOVE(b, 1); > - } > > mutex_unlock(&c->bucket_lock); > > diff --git a/drivers/md/bcache/super.c b/drivers/md/bcache/super.c > index 1efb768b2890..2ea490b9d370 100644 > --- a/drivers/md/bcache/super.c > +++ b/drivers/md/bcache/super.c > @@ -1912,7 +1912,8 @@ struct cache_set *bch_cache_set_alloc(struct cache_sb *sb) > INIT_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); > diff --git a/drivers/md/bcache/sysfs.c b/drivers/md/bcache/sysfs.c > index e8f696cb58c0..826b14cae4e5 100644 > --- a/drivers/md/bcache/sysfs.c > +++ b/drivers/md/bcache/sysfs.c > @@ -660,9 +660,7 @@ static unsigned int bch_root_usage(struct cache_set *c) > unsigned 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; > > diff --git a/drivers/md/bcache/util.h b/drivers/md/bcache/util.h > index 539454d8e2d0..f61ab1bada6c 100644 > --- a/drivers/md/bcache/util.h > +++ b/drivers/md/bcache/util.h > @@ -9,7 +9,6 @@ > #include <linux/kernel.h> > #include <linux/sched/clock.h> > #include <linux/llist.h> > -#include <linux/min_heap.h> > #include <linux/ratelimit.h> > #include <linux/vmalloc.h> > #include <linux/workqueue.h> > @@ -31,10 +30,16 @@ struct closure; > > #endif > > +#define DECLARE_HEAP(type, name) \ > + struct { \ > + size_t size, used; \ > + type *data; \ > + } name > + > #define init_heap(heap, _size, gfp) \ > ({ \ > size_t _bytes; \ > - (heap)->nr = 0; \ > + (heap)->used = 0; \ > (heap)->size = (_size); \ > _bytes = (heap)->size * sizeof(*(heap)->data); \ > (heap)->data = kvmalloc(_bytes, (gfp) & GFP_KERNEL); \ > @@ -47,6 +52,64 @@ do { \ > (heap)->data = NULL; \ > } while (0) > > +#define heap_swap(h, i, j) swap((h)->data[i], (h)->data[j]) > + > +#define heap_sift(h, i, cmp) \ > +do { \ > + size_t _r, _j = i; \ > + \ > + for (; _j * 2 + 1 < (h)->used; _j = _r) { \ > + _r = _j * 2 + 1; \ > + if (_r + 1 < (h)->used && \ > + cmp((h)->data[_r], (h)->data[_r + 1])) \ > + _r++; \ > + \ > + if (cmp((h)->data[_r], (h)->data[_j])) \ > + break; \ > + heap_swap(h, _r, _j); \ > + } \ > +} while (0) > + > +#define heap_sift_down(h, i, cmp) \ > +do { \ > + while (i) { \ > + size_t p = (i - 1) / 2; \ > + if (cmp((h)->data[i], (h)->data[p])) \ > + break; \ > + heap_swap(h, i, p); \ > + i = p; \ > + } \ > +} while (0) > + > +#define heap_add(h, d, cmp) \ > +({ \ > + bool _r = !heap_full(h); \ > + if (_r) { \ > + size_t _i = (h)->used++; \ > + (h)->data[_i] = d; \ > + \ > + heap_sift_down(h, _i, cmp); \ > + heap_sift(h, _i, cmp); \ > + } \ > + _r; \ > +}) > + > +#define heap_pop(h, d, cmp) \ > +({ \ > + bool _r = (h)->used; \ > + if (_r) { \ > + (d) = (h)->data[0]; \ > + (h)->used--; \ > + heap_swap(h, 0, (h)->used); \ > + heap_sift(h, 0, cmp); \ > + } \ > + _r; \ > +}) > + > +#define heap_peek(h) ((h)->used ? (h)->data[0] : NULL) > + > +#define heap_full(h) ((h)->used == (h)->size) > + > #define DECLARE_FIFO(type, name) \ > struct { \ > size_t front, back, size, mask; \ > diff --git a/drivers/md/bcache/writeback.c b/drivers/md/bcache/writeback.c > index 453efbbdc8ee..302e75f1fc4b 100644 > --- a/drivers/md/bcache/writeback.c > +++ b/drivers/md/bcache/writeback.c > @@ -908,16 +908,15 @@ static int bch_dirty_init_thread(void *arg) > struct 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 *arg) > 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 bcache_device *d) > int 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); > -- > 2.34.1 > -- Coly Li ^ permalink raw reply [flat|nested] 7+ messages in thread
* [PATCH v2 3/3] bcache: Remove unnecessary select MIN_HEAP 2025-06-14 20:23 [PATCH v2 0/3] bcache: Revert min_heap migration due to performance regression Kuan-Wei Chiu 2025-06-14 20:23 ` [PATCH v2 1/3] Revert "bcache: update min_heap_callbacks to use default builtin swap" Kuan-Wei Chiu 2025-06-14 20:23 ` [PATCH v2 2/3] Revert "bcache: remove heap-related macros and switch to generic min_heap" Kuan-Wei Chiu @ 2025-06-14 20:23 ` Kuan-Wei Chiu 2025-06-15 5:52 ` Coly Li 2 siblings, 1 reply; 7+ messages in thread From: Kuan-Wei Chiu @ 2025-06-14 20:23 UTC (permalink / raw) To: akpm, colyli, kent.overstreet, robertpang Cc: linux-kernel, linux-bcache, jserv, Kuan-Wei Chiu, stable After reverting the transition to the generic min heap library, bcache no longer depends on MIN_HEAP. The select entry can be removed to reduce code size and shrink the kernel's attack surface. This change effectively reverts the bcache-related part of commit 92a8b224b833 ("lib/min_heap: introduce non-inline versions of min heap API functions"). This is part of a series of changes to address a performance regression caused by the use of the generic min_heap implementation. 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. Link: https://lore.kernel.org/lkml/CAJhEC05+0S69z+3+FB2Cd0hD+pCRyWTKLEOsc8BOmH73p1m+KQ@mail.gmail.com 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@google.com> Closes: https://lore.kernel.org/linux-bcache/CAJhEC06F_AtrPgw2-7CvCqZgeStgCtitbD-ryuPpXQA-JG5XXw@mail.gmail.com Cc: stable@vger.kernel.org Signed-off-by: Kuan-Wei Chiu <visitorckw@gmail.com> --- drivers/md/bcache/Kconfig | 1 - 1 file changed, 1 deletion(-) diff --git a/drivers/md/bcache/Kconfig b/drivers/md/bcache/Kconfig index d4697e79d5a3..b2d10063d35f 100644 --- a/drivers/md/bcache/Kconfig +++ b/drivers/md/bcache/Kconfig @@ -5,7 +5,6 @@ config BCACHE select BLOCK_HOLDER_DEPRECATED if SYSFS select CRC64 select CLOSURES - select MIN_HEAP help Allows a block device to be used as cache for other devices; uses a btree for indexing and the layout is optimized for SSDs. -- 2.34.1 ^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [PATCH v2 3/3] bcache: Remove unnecessary select MIN_HEAP 2025-06-14 20:23 ` [PATCH v2 3/3] bcache: Remove unnecessary select MIN_HEAP Kuan-Wei Chiu @ 2025-06-15 5:52 ` Coly Li 0 siblings, 0 replies; 7+ messages in thread From: Coly Li @ 2025-06-15 5:52 UTC (permalink / raw) To: Kuan-Wei Chiu Cc: akpm, kent.overstreet, robertpang, linux-kernel, linux-bcache, jserv, stable On Sun, Jun 15, 2025 at 04:23:53AM +0800, Kuan-Wei Chiu wrote: > After reverting the transition to the generic min heap library, bcache > no longer depends on MIN_HEAP. The select entry can be removed to > reduce code size and shrink the kernel's attack surface. > > This change effectively reverts the bcache-related part of commit > 92a8b224b833 ("lib/min_heap: introduce non-inline versions of min heap > API functions"). > > This is part of a series of changes to address a performance > regression caused by the use of the generic min_heap implementation. > > 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. > > Link: https://lore.kernel.org/lkml/CAJhEC05+0S69z+3+FB2Cd0hD+pCRyWTKLEOsc8BOmH73p1m+KQ@mail.gmail.com > 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@google.com> > Closes: https://lore.kernel.org/linux-bcache/CAJhEC06F_AtrPgw2-7CvCqZgeStgCtitbD-ryuPpXQA-JG5XXw@mail.gmail.com > Cc: stable@vger.kernel.org > Signed-off-by: Kuan-Wei Chiu <visitorckw@gmail.com> Acked-by: Coly Li <colyli@kernel.org> Thanks. > --- > drivers/md/bcache/Kconfig | 1 - > 1 file changed, 1 deletion(-) > > diff --git a/drivers/md/bcache/Kconfig b/drivers/md/bcache/Kconfig > index d4697e79d5a3..b2d10063d35f 100644 > --- a/drivers/md/bcache/Kconfig > +++ b/drivers/md/bcache/Kconfig > @@ -5,7 +5,6 @@ config BCACHE > select BLOCK_HOLDER_DEPRECATED if SYSFS > select CRC64 > select CLOSURES > - select MIN_HEAP > help > Allows a block device to be used as cache for other devices; uses > a btree for indexing and the layout is optimized for SSDs. > -- > 2.34.1 > -- Coly Li ^ permalink raw reply [flat|nested] 7+ messages in thread
end of thread, other threads:[~2025-06-15 5:52 UTC | newest] Thread overview: 7+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2025-06-14 20:23 [PATCH v2 0/3] bcache: Revert min_heap migration due to performance regression Kuan-Wei Chiu 2025-06-14 20:23 ` [PATCH v2 1/3] Revert "bcache: update min_heap_callbacks to use default builtin swap" Kuan-Wei Chiu 2025-06-15 5:51 ` Coly Li 2025-06-14 20:23 ` [PATCH v2 2/3] Revert "bcache: remove heap-related macros and switch to generic min_heap" Kuan-Wei Chiu 2025-06-15 5:51 ` Coly Li 2025-06-14 20:23 ` [PATCH v2 3/3] bcache: Remove unnecessary select MIN_HEAP Kuan-Wei Chiu 2025-06-15 5:52 ` Coly Li
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox
all inboxes | Powered by JetHome®