linux-kernel - [PATCH v2 0/3] bcache: Revert min_heap migration due to performance regression

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [thread-next>] [day] [month] [year] [list]

Message-Id: <20250614202353.1632957-1-visitorckw@gmail.com>
Date: Sun, 15 Jun 2025 04:23:50 +0800
From: Kuan-Wei Chiu <visitorckw@...il.com>
To: akpm@...ux-foundation.org,
	colyli@...nel.org,
	kent.overstreet@...ux.dev,
	robertpang@...gle.com
Cc: linux-kernel@...r.kernel.org,
	linux-bcache@...r.kernel.org,
	jserv@...s.ncku.edu.tw,
	Kuan-Wei Chiu <visitorckw@...il.com>
Subject: [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/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