linux.git/drivers/md/bcache/alloc.c, branch v6.12.80

Revert "bcache: remove heap-related macros and switch to generic min_heap"

2025-08-15T10:14:10+00:00

commit 48fd7ebe00c1cdc782b42576548b25185902f64c upstream.

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 
Reported-by: Robert Pang 
Closes: https://lore.kernel.org/linux-bcache/CAJhEC06F_AtrPgw2-7CvCqZgeStgCtitbD-ryuPpXQA-JG5XXw@mail.gmail.com
Acked-by: Coly Li 
Cc: Ching-Chun (Jim) Huang 
Cc: Kent Overstreet 
Cc: 
Signed-off-by: Andrew Morton 
Signed-off-by: Kuan-Wei Chiu 
Signed-off-by: Greg Kroah-Hartman

bcache: remove heap-related macros and switch to generic min_heap

2024-06-25T05:25:00+00:00

Drop the heap-related macros from bcache and replacing them with the
generic min_heap implementation from include/linux.  By doing so, code
readability is improved by using functions instead of macros.  Moreover,
the min_heap implementation in include/linux adopts a bottom-up variation
compared to the textbook version currently used in bcache.  This bottom-up
variation allows for approximately 50% reduction in the number of
comparison operations during heap siftdown, without changing the number of
swaps, thus making it more efficient.

Link: https://lkml.kernel.org/ioyfizrzq7w7mjrqcadtzsfgpuntowtjdw5pgn4qhvsdp4mqqg@nrlek5vmisbu
Link: https://lkml.kernel.org/r/20240524152958.919343-16-visitorckw@gmail.com
Signed-off-by: Kuan-Wei Chiu 
Reviewed-by: Ian Rogers 
Acked-by: Coly Li 
Cc: Adrian Hunter 
Cc: Alexander Shishkin 
Cc: Arnaldo Carvalho de Melo 
Cc: Bagas Sanjaya 
Cc: Brian Foster 
Cc: Ching-Chun (Jim) Huang 
Cc: Ingo Molnar 
Cc: Jiri Olsa 
Cc: Kent Overstreet 
Cc: Mark Rutland 
Cc: Matthew Sakai 
Cc: Namhyung Kim 
Cc: Peter Zijlstra 
Cc: Randy Dunlap 
Signed-off-by: Andrew Morton

bcache: code cleanup in __bch_bucket_alloc_set()

2024-05-28T12:55:59+00:00

In __bch_bucket_alloc_set() the lines after lable 'err:' indeed do
nothing useful after multiple cache devices are removed from bcache
code. This cleanup patch drops the useless code to save a bit CPU
cycles.

Signed-off-by: Coly Li 
Link: https://lore.kernel.org/r/20240528120914.28705-4-colyli@suse.de
Signed-off-by: Jens Axboe

bcache: allow allocator to invalidate bucket in gc

2024-05-28T12:55:59+00:00

Currently, if the gc is running, when the allocator found free_inc
is empty, allocator has to wait the gc finish. Before that, the
IO is blocked.

But actually, there would be some buckets is reclaimable before gc,
and gc will never mark this kind of bucket to be unreclaimable.

So we can put these buckets into free_inc in gc running to avoid
IO being blocked.

Signed-off-by: Dongsheng Yang 
Signed-off-by: Mingzhe Zou 
Signed-off-by: Coly Li 
Link: https://lore.kernel.org/r/20240528120914.28705-2-colyli@suse.de
Signed-off-by: Jens Axboe

block: decouple REQ_OP_SECURE_ERASE from REQ_OP_DISCARD

2022-04-18T01:49:59+00:00

Secure erase is a very different operation from discard in that it is
a data integrity operation vs hint.  Fully split the limits and helper
infrastructure to make the separation more clear.

Signed-off-by: Christoph Hellwig 
Reviewed-by: Martin K. Petersen 
Acked-by: Christoph Böhmwalder  [drbd]
Acked-by: Ryusuke Konishi  [nifs2]
Acked-by: Jaegeuk Kim  [f2fs]
Acked-by: Coly Li  [bcache]
Acked-by: David Sterba  [btrfs]
Acked-by: Chao Yu 
Reviewed-by: Chaitanya Kulkarni 
Link: https://lore.kernel.org/r/20220415045258.199825-27-hch@lst.de
Signed-off-by: Jens Axboe

bcache: remove PTR_CACHE

2021-04-11T14:37:55+00:00

Remove the PTR_CACHE inline and replace it with a direct dereference
of c->cache.

(Coly Li: fix the typo from PTR_BUCKET to PTR_CACHE in commit log)

Signed-off-by: Christoph Hellwig 
Signed-off-by: Coly Li 
Link: https://lore.kernel.org/r/20210411134316.80274-3-colyli@suse.de
Signed-off-by: Jens Axboe

bcache: remove embedded struct cache_sb from struct cache_set

2020-10-02T20:25:30+00:00

Since bcache code was merged into mainline kerrnel, each cache set only
as one single cache in it. The multiple caches framework is here but the
code is far from completed. Considering the multiple copies of cached
data can also be stored on e.g. md raid1 devices, it is unnecessary to
support multiple caches in one cache set indeed.

The previous preparation patches fix the dependencies of explicitly
making a cache set only have single cache. Now we don't have to maintain
an embedded partial super block in struct cache_set, the in-memory super
block can be directly referenced from struct cache.

This patch removes the embedded struct cache_sb from struct cache_set,
and fixes all locations where the superb lock was referenced from this
removed super block by referencing the in-memory super block of struct
cache.

Signed-off-by: Coly Li 
Reviewed-by: Hannes Reinecke 
Signed-off-by: Jens Axboe

bcache: check and set sync status on cache's in-memory super block

2020-10-02T20:25:30+00:00

Currently the cache's sync status is checked and set on cache set's in-
memory partial super block. After removing the embedded struct cache_sb
from cache set and reference cache's in-memory super block from struct
cache_set, the sync status can set and check directly on cache's super
block.

This patch checks and sets the cache sync status directly on cache's
in-memory super block. This is a preparation for later removing embedded
struct cache_sb from struct cache_set.

Signed-off-by: Coly Li 
Reviewed-by: Hannes Reinecke 
Signed-off-by: Jens Axboe

bcache: remove for_each_cache()

2020-10-02T20:25:29+00:00

Since now each cache_set explicitly has single cache, for_each_cache()
is unnecessary. This patch removes this macro, and update all locations
where it is used, and makes sure all code logic still being consistent.

Signed-off-by: Coly Li 
Reviewed-by: Hannes Reinecke 
Signed-off-by: Jens Axboe

bcache: explicitly make cache_set only have single cache

2020-10-02T20:25:29+00:00

Currently although the bcache code has a framework for multiple caches
in a cache set, but indeed the multiple caches never completed and users
use md raid1 for multiple copies of the cached data.

This patch does the following change in struct cache_set, to explicitly
make a cache_set only have single cache,
- Change pointer array "*cache[MAX_CACHES_PER_SET]" to a single pointer
  "*cache".
- Remove pointer array "*cache_by_alloc[MAX_CACHES_PER_SET]".
- Remove "caches_loaded".

Now the code looks as exactly what it does in practic: only one cache is
used in the cache set.

Signed-off-by: Coly Li 
Signed-off-by: Jens Axboe