Re: [PATCH 6.12.y] Revert "bcache: remove heap-related macros and switch to generic min_heap"

[Greg KH <gregkh@linuxfoundation.org>]

On Thu, Jul 31, 2025 at 08:38:19PM +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
> Link: https://lkml.kernel.org/r/20250614202353.1632957-3-visitorckw@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")
> Signed-off-by: Kuan-Wei Chiu <visitorckw@gmail.com>
> Reported-by: Robert Pang <robertpang@google.com>
> Closes: https://lore.kernel.org/linux-bcache/CAJhEC06F_AtrPgw2-7CvCqZgeStgCtitbD-ryuPpXQA-JG5XXw@mail.gmail.com
> Acked-by: Coly Li <colyli@kernel.org>
> Cc: Ching-Chun (Jim) Huang <jserv@ccns.ncku.edu.tw>
> Cc: Kent Overstreet <kent.overstreet@linux.dev>
> Cc: <stable@vger.kernel.org>
> Signed-off-by: Andrew Morton <akpm@linux-foundation.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(-)


<formletter>

This is not the correct way to submit patches for inclusion in the
stable kernel tree.  Please read:
    https://www.kernel.org/doc/html/latest/process/stable-kernel-rules.html
for how to do this properly.

</formletter>