linux-kernel - [PATCH 0/8] Fix bcache regression with equality-aware heap APIs

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 for Android: free password hash cracker in your pocket

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

Message-Id: <20250610215516.1513296-1-visitorckw@gmail.com>
Date: Wed, 11 Jun 2025 05:55:08 +0800
From: Kuan-Wei Chiu <visitorckw@...il.com>
To: corbet@....net,
	colyli@...nel.org,
	kent.overstreet@...ux.dev,
	akpm@...ux-foundation.org,
	robertpang@...gle.com
Cc: linux-kernel@...r.kernel.org,
	linux-doc@...r.kernel.org,
	linux-bcache@...r.kernel.org,
	jserv@...s.ncku.edu.tw,
	Kuan-Wei Chiu <visitorckw@...il.com>,
	stable@...r.kernel.org
Subject: [PATCH 0/8] Fix bcache regression with equality-aware heap APIs

This patch series introduces equality-aware variants of the min heap
API that use a top-down heapify strategy to improve performance when
many elements are equal under the comparison function. It also updates
the documentation accordingly and modifies bcache to use the new APIs
to fix a performance regression caused by the switch to the generic min
heap library.

In particular, invalidate_buckets_lru() in bcache suffered from
increased comparison overhead due to the bottom-up strategy introduced
in commit 866898efbb25 ("bcache: remove heap-related macros and switch
to generic min_heap"). The regression is addressed by switching to the
equality-aware variants and using the inline versions to avoid function
call overhead in this hot path.

Cc: stable@...r.kernel.org
---

To avoid duplicated effort and expedite resolution, Robert kindly
agreed that I should submit my already-completed series instead. Many
thanks to him for his cooperation and support.

Kuan-Wei Chiu (8):
  lib min_heap: Add equal-elements-aware sift_down variant
  lib min_heap: Add typedef for sift_down function pointer
  lib min_heap: add eqaware variant of min_heapify_all()
  lib min_heap: add eqaware variant of min_heap_pop()
  lib min_heap: add eqaware variant of min_heap_pop_push()
  lib min_heap: add eqaware variant of min_heap_del()
  Documentation/core-api: min_heap: Document _eqaware variants of
    min-heap APIs
  bcache: Fix the tail IO latency regression by using equality-aware min
    heap API

 Documentation/core-api/min_heap.rst |  20 +++++
 drivers/md/bcache/alloc.c           |  15 ++--
 include/linux/min_heap.h            | 131 +++++++++++++++++++++++-----
 lib/min_heap.c                      |  23 +++--
 4 files changed, 154 insertions(+), 35 deletions(-)

-- 
2.34.1