linux-kernel - [PATCH v2 00/10] Enhance min heap API with non-inline functions and optimizations

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: <20241020040200.939973-1-visitorckw@gmail.com>
Date: Sun, 20 Oct 2024 12:01:50 +0800
From: Kuan-Wei Chiu <visitorckw@...il.com>
To: colyli@...e.de,
	kent.overstreet@...ux.dev,
	msakai@...hat.com,
	corbet@....net,
	peterz@...radead.org,
	mingo@...hat.com,
	acme@...nel.org,
	namhyung@...nel.org,
	akpm@...ux-foundation.org
Cc: mark.rutland@....com,
	alexander.shishkin@...ux.intel.com,
	jolsa@...nel.org,
	irogers@...gle.com,
	adrian.hunter@...el.com,
	kan.liang@...ux.intel.com,
	willy@...radead.org,
	jserv@...s.ncku.edu.tw,
	linux-kernel@...r.kernel.org,
	linux-bcache@...r.kernel.org,
	dm-devel@...ts.linux.dev,
	linux-bcachefs@...r.kernel.org,
	linux-perf-users@...r.kernel.org,
	linux-doc@...r.kernel.org,
	Kuan-Wei Chiu <visitorckw@...il.com>
Subject: [PATCH v2 00/10] Enhance min heap API with non-inline functions and optimizations

Add non-inline versions of the min heap API functions in lib/min_heap.c
and updates all users outside of kernel/events/core.c to use these
non-inline versions. To mitigate the performance impact of indirect
function calls caused by the non-inline versions of the swap and
compare functions, a builtin swap has been introduced that swaps
elements based on their size. Additionally, it micro-optimizes the
efficiency of the min heap by pre-scaling the counter, following the
same approach as in lib/sort.c. Documentation for the min heap API has
also been added to the core-api section.

Regards,
Kuan-Wei

---

Changes in v2:
- Added a builtin swap to reduce the performance impact of indirect
  function calls.
- Cleaned up duplicate min_heap_callbacks in bcachefs.
- Wrapped documentation at 80 columns.
- Updated Example Usage.
- Included documentation explaining that NULL can be passed to the
  swp in min_heap_callbacks to use the builtin swap.

v1: https://lore.kernel.org/lkml/20241013184703.659652-1-visitorckw@gmail.com

Kuan-Wei Chiu (10):
  lib/min_heap: Introduce non-inline versions of min heap API functions
  lib min_heap: Optimize min heap by prescaling counters for better
    performance
  lib min_heap: Avoid indirect function call by providing default swap
  lib/test_min_heap: Update min_heap_callbacks to use default builtin
    swap
  perf/core: Update min_heap_callbacks to use default builtin swap
  dm vdo: Update min_heap_callbacks to use default builtin swap
  bcache: Update min_heap_callbacks to use default builtin swap
  bcachefs: Clean up duplicate min_heap_callbacks declarations
  bcachefs: Update min_heap_callbacks to use default builtin swap
  Documentation/core-api: Add min heap API introduction

 Documentation/core-api/index.rst    |   1 +
 Documentation/core-api/min_heap.rst | 300 +++++++++++++++++++++++
 drivers/md/bcache/Kconfig           |   1 +
 drivers/md/bcache/alloc.c           |  11 +-
 drivers/md/bcache/bset.c            |  14 +-
 drivers/md/bcache/extents.c         |  10 +-
 drivers/md/bcache/movinggc.c        |  10 +-
 drivers/md/dm-vdo/Kconfig           |   1 +
 drivers/md/dm-vdo/repair.c          |   2 +-
 drivers/md/dm-vdo/slab-depot.c      |  10 +-
 fs/bcachefs/Kconfig                 |   1 +
 fs/bcachefs/clock.c                 |  25 +-
 fs/bcachefs/ec.c                    |  19 +-
 include/linux/min_heap.h            | 357 ++++++++++++++++++++++------
 kernel/events/core.c                |  15 +-
 lib/Kconfig                         |   3 +
 lib/Kconfig.debug                   |   1 +
 lib/Makefile                        |   1 +
 lib/min_heap.c                      |  70 ++++++
 lib/test_min_heap.c                 |  16 +-
 20 files changed, 694 insertions(+), 174 deletions(-)
 create mode 100644 Documentation/core-api/min_heap.rst
 create mode 100644 lib/min_heap.c

-- 
2.34.1