Skip to content

bcache: Revert min_heap migration due to performance regression

Kuan-Wei Chiu linux-bcache lkml stable 1 version Applied

Status from this message: [merged mm-hotfixes-stable] bcache-remove-unnecessary-select-min_heap.patch removed from -mm tree

Get series with b4
b4 am [email protected]

Versions newest first

  1. v2 Latest3 patches 3 repliesApplied 3/3

Changes in v2 from the cover letter

- Drop the proposed new min_heap API approach.
- Replace with full reverts of the min_heap-related changes in bcache.

Patches in v2 All 3 applied

#Subject and filesSizeRepliesApplied
1/3Revert "bcache: update min_heap_callbacks to use default builtin swap"drivers/md/bcache/alloc.c drivers/md/bcache/bset.c drivers/md/bcache/extents.c +1 more+38 -71 replyApplied
2/3Revert "bcache: remove heap-related macros and switch to generic min_heap"drivers/md/bcache/alloc.c drivers/md/bcache/bcache.h drivers/md/bcache/bset.c +8 more+217 -2631 replyApplied
3/3bcache: Remove unnecessary select MIN_HEAPdrivers/md/bcache/Kconfig+0 -11 replyApplied

Reviews trailers per patch

All 3 patches have a Reviewed-by or Acked-by.

PatchColy Li
1/3A-b
2/3A-b
3/3A-b

Trailers given in replies are filled; those carried in the patches from earlier versions are outlined with dashes.

Read the v2 thread

Cover letter [PATCH v2 0/3] bcache: Revert min_heap migration due to performance regression

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/[email protected]

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(-)
Signature · 1 line
2.34.1