[PATCH 0/3] Enhance min heap API with non-inline functions and optimizations

[PATCH 0/3] Enhance min heap API with non-inline functions and optimizations

[Kuan-Wei Chiu]

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. 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

Kuan-Wei Chiu (3):
  lib/min_heap: Introduce non-inline versions of min heap API functions
  lib min_heap: Optimize min heap by prescaling counters for better
    performance
  Documentation/core-api: Add min heap API introduction

 Documentation/core-api/index.rst    |   1 +
 Documentation/core-api/min_heap.rst | 291 ++++++++++++++++++++++++++++
 drivers/md/bcache/Kconfig           |   1 +
 drivers/md/dm-vdo/Kconfig           |   1 +
 fs/bcachefs/Kconfig                 |   1 +
 include/linux/min_heap.h            | 202 ++++++++++++-------
 kernel/events/core.c                |   6 +-
 lib/Kconfig                         |   3 +
 lib/Kconfig.debug                   |   1 +
 lib/Makefile                        |   1 +
 lib/min_heap.c                      |  70 +++++++
 11 files changed, 508 insertions(+), 70 deletions(-)
 create mode 100644 Documentation/core-api/min_heap.rst
 create mode 100644 lib/min_heap.c

-- 
2.34.1

[PATCH 1/3] lib/min_heap: Introduce non-inline versions of min heap API functions

[Kuan-Wei Chiu]

All current min heap API functions are marked with '__always_inline'.
However, as the number of users increases, inlining these functions
everywhere leads to a significant increase in kernel size.

In performance-critical paths, such as when perf events are enabled and
min heap functions are called on every context switch, it is important
to retain the inline versions for optimal performance. To balance this,
the original inline functions are kept, and additional non-inline
versions of the functions have been added in lib/min_heap.c.

Link: https://lore.kernel.org/20240522161048.8d8bbc7b153b4ecd92c50666@linux-foundation.org
Suggested-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Kuan-Wei Chiu <visitorckw@gmail.com>
---


 drivers/md/bcache/Kconfig |   1 +
 drivers/md/dm-vdo/Kconfig |   1 +
 fs/bcachefs/Kconfig       |   1 +
 include/linux/min_heap.h  | 129 +++++++++++++++++++++++++-------------
 kernel/events/core.c      |   6 +-
 lib/Kconfig               |   3 +
 lib/Kconfig.debug         |   1 +
 lib/Makefile              |   1 +
 lib/min_heap.c            |  70 +++++++++++++++++++++
 9 files changed, 167 insertions(+), 46 deletions(-)
 create mode 100644 lib/min_heap.c

diff --git a/drivers/md/bcache/Kconfig b/drivers/md/bcache/Kconfig
index b2d10063d35f..d4697e79d5a3 100644
--- a/drivers/md/bcache/Kconfig
+++ b/drivers/md/bcache/Kconfig
@@ -5,6 +5,7 @@ config BCACHE
 	select BLOCK_HOLDER_DEPRECATED if SYSFS
 	select CRC64
 	select CLOSURES
+	select MIN_HEAP
 	help
 	Allows a block device to be used as cache for other devices; uses
 	a btree for indexing and the layout is optimized for SSDs.
diff --git a/drivers/md/dm-vdo/Kconfig b/drivers/md/dm-vdo/Kconfig
index 111ecd2c2a24..2400b2bc4bc7 100644
--- a/drivers/md/dm-vdo/Kconfig
+++ b/drivers/md/dm-vdo/Kconfig
@@ -7,6 +7,7 @@ config DM_VDO
 	select DM_BUFIO
 	select LZ4_COMPRESS
 	select LZ4_DECOMPRESS
+	select MIN_HEAP
 	help
 	  This device mapper target presents a block device with
 	  deduplication, compression and thin-provisioning.
diff --git a/fs/bcachefs/Kconfig b/fs/bcachefs/Kconfig
index 5bac803ea367..ab6c95b895b3 100644
--- a/fs/bcachefs/Kconfig
+++ b/fs/bcachefs/Kconfig
@@ -24,6 +24,7 @@ config BCACHEFS_FS
 	select XXHASH
 	select SRCU
 	select SYMBOLIC_ERRNAME
+	select MIN_HEAP
 	help
 	The bcachefs filesystem - a modern, copy on write filesystem, with
 	support for multiple devices, compression, checksumming, etc.
diff --git a/include/linux/min_heap.h b/include/linux/min_heap.h
index 43a7b9dcf15e..0abb21173979 100644
--- a/include/linux/min_heap.h
+++ b/include/linux/min_heap.h
@@ -40,7 +40,7 @@ struct min_heap_callbacks {
 
 /* Initialize a min-heap. */
 static __always_inline
-void __min_heap_init(min_heap_char *heap, void *data, int size)
+void __min_heap_init_inline(min_heap_char *heap, void *data, int size)
 {
 	heap->nr = 0;
 	heap->size = size;
@@ -50,33 +50,33 @@ void __min_heap_init(min_heap_char *heap, void *data, int size)
 		heap->data = heap->preallocated;
 }
 
-#define min_heap_init(_heap, _data, _size)	\
-	__min_heap_init((min_heap_char *)_heap, _data, _size)
+#define min_heap_init_inline(_heap, _data, _size)	\
+	__min_heap_init_inline((min_heap_char *)_heap, _data, _size)
 
 /* Get the minimum element from the heap. */
 static __always_inline
-void *__min_heap_peek(struct min_heap_char *heap)
+void *__min_heap_peek_inline(struct min_heap_char *heap)
 {
 	return heap->nr ? heap->data : NULL;
 }
 
-#define min_heap_peek(_heap)	\
-	(__minheap_cast(_heap) __min_heap_peek((min_heap_char *)_heap))
+#define min_heap_peek_inline(_heap)	\
+	(__minheap_cast(_heap) __min_heap_peek_inline((min_heap_char *)_heap))
 
 /* Check if the heap is full. */
 static __always_inline
-bool __min_heap_full(min_heap_char *heap)
+bool __min_heap_full_inline(min_heap_char *heap)
 {
 	return heap->nr == heap->size;
 }
 
-#define min_heap_full(_heap)	\
-	__min_heap_full((min_heap_char *)_heap)
+#define min_heap_full_inline(_heap)	\
+	__min_heap_full_inline((min_heap_char *)_heap)
 
 /* Sift the element at pos down the heap. */
 static __always_inline
-void __min_heap_sift_down(min_heap_char *heap, int pos, size_t elem_size,
-		const struct min_heap_callbacks *func, void *args)
+void __min_heap_sift_down_inline(min_heap_char *heap, int pos, size_t elem_size,
+				 const struct min_heap_callbacks *func, void *args)
 {
 	void *left, *right;
 	void *data = heap->data;
@@ -108,13 +108,14 @@ void __min_heap_sift_down(min_heap_char *heap, int pos, size_t elem_size,
 	}
 }
 
-#define min_heap_sift_down(_heap, _pos, _func, _args)	\
-	__min_heap_sift_down((min_heap_char *)_heap, _pos, __minheap_obj_size(_heap), _func, _args)
+#define min_heap_sift_down_inline(_heap, _pos, _func, _args)	\
+	__min_heap_sift_down_inline((min_heap_char *)_heap, _pos, __minheap_obj_size(_heap),	\
+				    _func, _args)
 
 /* Sift up ith element from the heap, O(log2(nr)). */
 static __always_inline
-void __min_heap_sift_up(min_heap_char *heap, size_t elem_size, size_t idx,
-		const struct min_heap_callbacks *func, void *args)
+void __min_heap_sift_up_inline(min_heap_char *heap, size_t elem_size, size_t idx,
+			       const struct min_heap_callbacks *func, void *args)
 {
 	void *data = heap->data;
 	size_t parent;
@@ -128,27 +129,28 @@ void __min_heap_sift_up(min_heap_char *heap, size_t elem_size, size_t idx,
 	}
 }
 
-#define min_heap_sift_up(_heap, _idx, _func, _args)	\
-	__min_heap_sift_up((min_heap_char *)_heap, __minheap_obj_size(_heap), _idx, _func, _args)
+#define min_heap_sift_up_inline(_heap, _idx, _func, _args)	\
+	__min_heap_sift_up_inline((min_heap_char *)_heap, __minheap_obj_size(_heap), _idx,	\
+				  _func, _args)
 
 /* Floyd's approach to heapification that is O(nr). */
 static __always_inline
-void __min_heapify_all(min_heap_char *heap, size_t elem_size,
-		const struct min_heap_callbacks *func, void *args)
+void __min_heapify_all_inline(min_heap_char *heap, size_t elem_size,
+			      const struct min_heap_callbacks *func, void *args)
 {
 	int i;
 
 	for (i = heap->nr / 2 - 1; i >= 0; i--)
-		__min_heap_sift_down(heap, i, elem_size, func, args);
+		__min_heap_sift_down_inline(heap, i, elem_size, func, args);
 }
 
-#define min_heapify_all(_heap, _func, _args)	\
-	__min_heapify_all((min_heap_char *)_heap, __minheap_obj_size(_heap), _func, _args)
+#define min_heapify_all_inline(_heap, _func, _args)	\
+	__min_heapify_all_inline((min_heap_char *)_heap, __minheap_obj_size(_heap), _func, _args)
 
 /* Remove minimum element from the heap, O(log2(nr)). */
 static __always_inline
-bool __min_heap_pop(min_heap_char *heap, size_t elem_size,
-		const struct min_heap_callbacks *func, void *args)
+bool __min_heap_pop_inline(min_heap_char *heap, size_t elem_size,
+			   const struct min_heap_callbacks *func, void *args)
 {
 	void *data = heap->data;
 
@@ -158,13 +160,13 @@ bool __min_heap_pop(min_heap_char *heap, size_t elem_size,
 	/* Place last element at the root (position 0) and then sift down. */
 	heap->nr--;
 	memcpy(data, data + (heap->nr * elem_size), elem_size);
-	__min_heap_sift_down(heap, 0, elem_size, func, args);
+	__min_heap_sift_down_inline(heap, 0, elem_size, func, args);
 
 	return true;
 }
 
-#define min_heap_pop(_heap, _func, _args)	\
-	__min_heap_pop((min_heap_char *)_heap, __minheap_obj_size(_heap), _func, _args)
+#define min_heap_pop_inline(_heap, _func, _args)	\
+	__min_heap_pop_inline((min_heap_char *)_heap, __minheap_obj_size(_heap), _func, _args)
 
 /*
  * Remove the minimum element and then push the given element. The
@@ -172,22 +174,21 @@ bool __min_heap_pop(min_heap_char *heap, size_t elem_size,
  * efficient than a pop followed by a push that does 2.
  */
 static __always_inline
-void __min_heap_pop_push(min_heap_char *heap,
-		const void *element, size_t elem_size,
-		const struct min_heap_callbacks *func,
-		void *args)
+void __min_heap_pop_push_inline(min_heap_char *heap, const void *element, size_t elem_size,
+				const struct min_heap_callbacks *func, void *args)
 {
 	memcpy(heap->data, element, elem_size);
-	__min_heap_sift_down(heap, 0, elem_size, func, args);
+	__min_heap_sift_down_inline(heap, 0, elem_size, func, args);
 }
 
-#define min_heap_pop_push(_heap, _element, _func, _args)	\
-	__min_heap_pop_push((min_heap_char *)_heap, _element, __minheap_obj_size(_heap), _func, _args)
+#define min_heap_pop_push_inline(_heap, _element, _func, _args)	\
+	__min_heap_pop_push_inline((min_heap_char *)_heap, _element, __minheap_obj_size(_heap),	\
+				   _func, _args)
 
 /* Push an element on to the heap, O(log2(nr)). */
 static __always_inline
-bool __min_heap_push(min_heap_char *heap, const void *element, size_t elem_size,
-		const struct min_heap_callbacks *func, void *args)
+bool __min_heap_push_inline(min_heap_char *heap, const void *element, size_t elem_size,
+			    const struct min_heap_callbacks *func, void *args)
 {
 	void *data = heap->data;
 	int pos;
@@ -201,18 +202,19 @@ bool __min_heap_push(min_heap_char *heap, const void *element, size_t elem_size,
 	heap->nr++;
 
 	/* Sift child at pos up. */
-	__min_heap_sift_up(heap, elem_size, pos, func, args);
+	__min_heap_sift_up_inline(heap, elem_size, pos, func, args);
 
 	return true;
 }
 
-#define min_heap_push(_heap, _element, _func, _args)	\
-	__min_heap_push((min_heap_char *)_heap, _element, __minheap_obj_size(_heap), _func, _args)
+#define min_heap_push_inline(_heap, _element, _func, _args)	\
+	__min_heap_push_inline((min_heap_char *)_heap, _element, __minheap_obj_size(_heap),	\
+			       _func, _args)
 
 /* Remove ith element from the heap, O(log2(nr)). */
 static __always_inline
-bool __min_heap_del(min_heap_char *heap, size_t elem_size, size_t idx,
-		const struct min_heap_callbacks *func, void *args)
+bool __min_heap_del_inline(min_heap_char *heap, size_t elem_size, size_t idx,
+			   const struct min_heap_callbacks *func, void *args)
 {
 	void *data = heap->data;
 
@@ -224,12 +226,53 @@ bool __min_heap_del(min_heap_char *heap, size_t elem_size, size_t idx,
 	if (idx == heap->nr)
 		return true;
 	func->swp(data + (idx * elem_size), data + (heap->nr * elem_size), args);
-	__min_heap_sift_up(heap, elem_size, idx, func, args);
-	__min_heap_sift_down(heap, idx, elem_size, func, args);
+	__min_heap_sift_up_inline(heap, elem_size, idx, func, args);
+	__min_heap_sift_down_inline(heap, idx, elem_size, func, args);
 
 	return true;
 }
 
+#define min_heap_del_inline(_heap, _idx, _func, _args)	\
+	__min_heap_del_inline((min_heap_char *)_heap, __minheap_obj_size(_heap), _idx,	\
+			      _func, _args)
+
+void __min_heap_init(min_heap_char *heap, void *data, int size);
+void *__min_heap_peek(struct min_heap_char *heap);
+bool __min_heap_full(min_heap_char *heap);
+void __min_heap_sift_down(min_heap_char *heap, int pos, size_t elem_size,
+			  const struct min_heap_callbacks *func, void *args);
+void __min_heap_sift_up(min_heap_char *heap, size_t elem_size, size_t idx,
+			const struct min_heap_callbacks *func, void *args);
+void __min_heapify_all(min_heap_char *heap, size_t elem_size,
+		       const struct min_heap_callbacks *func, void *args);
+bool __min_heap_pop(min_heap_char *heap, size_t elem_size,
+		    const struct min_heap_callbacks *func, void *args);
+void __min_heap_pop_push(min_heap_char *heap, const void *element, size_t elem_size,
+			 const struct min_heap_callbacks *func, void *args);
+bool __min_heap_push(min_heap_char *heap, const void *element, size_t elem_size,
+		     const struct min_heap_callbacks *func, void *args);
+bool __min_heap_del(min_heap_char *heap, size_t elem_size, size_t idx,
+		    const struct min_heap_callbacks *func, void *args);
+
+#define min_heap_init(_heap, _data, _size)	\
+	__min_heap_init((min_heap_char *)_heap, _data, _size)
+#define min_heap_peek(_heap)	\
+	(__minheap_cast(_heap) __min_heap_peek((min_heap_char *)_heap))
+#define min_heap_full(_heap)	\
+	__min_heap_full((min_heap_char *)_heap)
+#define min_heap_sift_down(_heap, _pos, _func, _args)	\
+	__min_heap_sift_down((min_heap_char *)_heap, _pos, __minheap_obj_size(_heap), _func, _args)
+#define min_heap_sift_up(_heap, _idx, _func, _args)	\
+	__min_heap_sift_up((min_heap_char *)_heap, __minheap_obj_size(_heap), _idx, _func, _args)
+#define min_heapify_all(_heap, _func, _args)	\
+	__min_heapify_all((min_heap_char *)_heap, __minheap_obj_size(_heap), _func, _args)
+#define min_heap_pop(_heap, _func, _args)	\
+	__min_heap_pop((min_heap_char *)_heap, __minheap_obj_size(_heap), _func, _args)
+#define min_heap_pop_push(_heap, _element, _func, _args)	\
+	__min_heap_pop_push((min_heap_char *)_heap, _element, __minheap_obj_size(_heap),	\
+			    _func, _args)
+#define min_heap_push(_heap, _element, _func, _args)	\
+	__min_heap_push((min_heap_char *)_heap, _element, __minheap_obj_size(_heap), _func, _args)
 #define min_heap_del(_heap, _idx, _func, _args)	\
 	__min_heap_del((min_heap_char *)_heap, __minheap_obj_size(_heap), _idx, _func, _args)
 
diff --git a/kernel/events/core.c b/kernel/events/core.c
index e3589c4287cb..cbf365e67f6e 100644
--- a/kernel/events/core.c
+++ b/kernel/events/core.c
@@ -3870,7 +3870,7 @@ static noinline int visit_groups_merge(struct perf_event_context *ctx,
 		perf_assert_pmu_disabled((*evt)->pmu_ctx->pmu);
 	}
 
-	min_heapify_all(&event_heap, &perf_min_heap, NULL);
+	min_heapify_all_inline(&event_heap, &perf_min_heap, NULL);
 
 	while (event_heap.nr) {
 		ret = func(*evt, data);
@@ -3879,9 +3879,9 @@ static noinline int visit_groups_merge(struct perf_event_context *ctx,
 
 		*evt = perf_event_groups_next(*evt, pmu);
 		if (*evt)
-			min_heap_sift_down(&event_heap, 0, &perf_min_heap, NULL);
+			min_heap_sift_down_inline(&event_heap, 0, &perf_min_heap, NULL);
 		else
-			min_heap_pop(&event_heap, &perf_min_heap, NULL);
+			min_heap_pop_inline(&event_heap, &perf_min_heap, NULL);
 	}
 
 	return 0;
diff --git a/lib/Kconfig b/lib/Kconfig
index b38849af6f13..037a84731b7d 100644
--- a/lib/Kconfig
+++ b/lib/Kconfig
@@ -777,3 +777,6 @@ config POLYNOMIAL
 
 config FIRMWARE_TABLE
 	bool
+
+config MIN_HEAP
+	bool
diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug
index 7315f643817a..a9b375cf9784 100644
--- a/lib/Kconfig.debug
+++ b/lib/Kconfig.debug
@@ -2279,6 +2279,7 @@ config TEST_LIST_SORT
 config TEST_MIN_HEAP
 	tristate "Min heap test"
 	depends on DEBUG_KERNEL || m
+	select MIN_HEAP
 	help
 	  Enable this to turn on min heap function tests. This test is
 	  executed only once during system boot (so affects only boot time),
diff --git a/lib/Makefile b/lib/Makefile
index 773adf88af41..e7ffee03e186 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -39,6 +39,7 @@ lib-y := ctype.o string.o vsprintf.o cmdline.o \
 
 lib-$(CONFIG_PRINTK) += dump_stack.o
 lib-$(CONFIG_SMP) += cpumask.o
+lib-$(CONFIG_MIN_HEAP) += min_heap.o
 
 lib-y	+= kobject.o klist.o
 obj-y	+= lockref.o
diff --git a/lib/min_heap.c b/lib/min_heap.c
new file mode 100644
index 000000000000..4485372ff3b1
--- /dev/null
+++ b/lib/min_heap.c
@@ -0,0 +1,70 @@
+// SPDX-License-Identifier: GPL-2.0
+#include <linux/export.h>
+#include <linux/min_heap.h>
+
+void __min_heap_init(min_heap_char *heap, void *data, int size)
+{
+	__min_heap_init_inline(heap, data, size);
+}
+EXPORT_SYMBOL(__min_heap_init);
+
+void *__min_heap_peek(struct min_heap_char *heap)
+{
+	return __min_heap_peek_inline(heap);
+}
+EXPORT_SYMBOL(__min_heap_peek);
+
+bool __min_heap_full(min_heap_char *heap)
+{
+	return __min_heap_full_inline(heap);
+}
+EXPORT_SYMBOL(__min_heap_full);
+
+void __min_heap_sift_down(min_heap_char *heap, int pos, size_t elem_size,
+			  const struct min_heap_callbacks *func, void *args)
+{
+	__min_heap_sift_down_inline(heap, pos, elem_size, func, args);
+}
+EXPORT_SYMBOL(__min_heap_sift_down);
+
+void __min_heap_sift_up(min_heap_char *heap, size_t elem_size, size_t idx,
+			const struct min_heap_callbacks *func, void *args)
+{
+	__min_heap_sift_up_inline(heap, elem_size, idx, func, args);
+}
+EXPORT_SYMBOL(__min_heap_sift_up);
+
+void __min_heapify_all(min_heap_char *heap, size_t elem_size,
+		       const struct min_heap_callbacks *func, void *args)
+{
+	__min_heapify_all_inline(heap, elem_size, func, args);
+}
+EXPORT_SYMBOL(__min_heapify_all);
+
+bool __min_heap_pop(min_heap_char *heap, size_t elem_size,
+		    const struct min_heap_callbacks *func, void *args)
+{
+	return __min_heap_pop_inline(heap, elem_size, func, args);
+}
+EXPORT_SYMBOL(__min_heap_pop);
+
+void __min_heap_pop_push(min_heap_char *heap, const void *element, size_t elem_size,
+			 const struct min_heap_callbacks *func, void *args)
+{
+	__min_heap_pop_push_inline(heap, element, elem_size, func, args);
+}
+EXPORT_SYMBOL(__min_heap_pop_push);
+
+bool __min_heap_push(min_heap_char *heap, const void *element, size_t elem_size,
+		     const struct min_heap_callbacks *func, void *args)
+{
+	return __min_heap_push_inline(heap, element, elem_size, func, args);
+}
+EXPORT_SYMBOL(__min_heap_push);
+
+bool __min_heap_del(min_heap_char *heap, size_t elem_size, size_t idx,
+		    const struct min_heap_callbacks *func, void *args)
+{
+	return __min_heap_del_inline(heap, elem_size, idx, func, args);
+}
+EXPORT_SYMBOL(__min_heap_del);
-- 
2.34.1

[PATCH 2/3] lib min_heap: Optimize min heap by prescaling counters for better performance

[Kuan-Wei Chiu]

Improve the efficiency of the min heap by prescaling counters,
eliminating the need to repeatedly compute 'index * element_size' when
accessing elements. By doing so, we avoid the overhead associated with
recalculating the byte offset for each heap operation.

However, with prescaling, the calculation for the parent element's
location is no longer as simple as '(i - 1) / 2'. To address this, we
copy the parent function from 'lib/sort.c', which calculates the parent
offset in a branchless manner without using any division instructions.

This optimization should result in a more efficient heap implementation
by reducing the computational overhead of finding parent and child
offsets.

Signed-off-by: Kuan-Wei Chiu <visitorckw@gmail.com>
---
Tested with test_min_heap module.

 include/linux/min_heap.h | 73 +++++++++++++++++++++++++++-------------
 1 file changed, 49 insertions(+), 24 deletions(-)

diff --git a/include/linux/min_heap.h b/include/linux/min_heap.h
index 0abb21173979..bee28d7b6efc 100644
--- a/include/linux/min_heap.h
+++ b/include/linux/min_heap.h
@@ -73,38 +73,61 @@ bool __min_heap_full_inline(min_heap_char *heap)
 #define min_heap_full_inline(_heap)	\
 	__min_heap_full_inline((min_heap_char *)_heap)
 
+/**
+ * parent - given the offset of the child, find the offset of the parent.
+ * @i: the offset of the heap element whose parent is sought.  Non-zero.
+ * @lsbit: a precomputed 1-bit mask, equal to "size & -size"
+ * @size: size of each element
+ *
+ * In terms of array indexes, the parent of element j = @i/@size is simply
+ * (j-1)/2.  But when working in byte offsets, we can't use implicit
+ * truncation of integer divides.
+ *
+ * Fortunately, we only need one bit of the quotient, not the full divide.
+ * @size has a least significant bit.  That bit will be clear if @i is
+ * an even multiple of @size, and set if it's an odd multiple.
+ *
+ * Logically, we're doing "if (i & lsbit) i -= size;", but since the
+ * branch is unpredictable, it's done with a bit of clever branch-free
+ * code instead.
+ */
+__attribute_const__ __always_inline
+static size_t parent(size_t i, unsigned int lsbit, size_t size)
+{
+	i -= size;
+	i -= size & -(i & lsbit);
+	return i / 2;
+}
+
 /* Sift the element at pos down the heap. */
 static __always_inline
 void __min_heap_sift_down_inline(min_heap_char *heap, int pos, size_t elem_size,
 				 const struct min_heap_callbacks *func, void *args)
 {
-	void *left, *right;
+	const unsigned long lsbit = elem_size & -elem_size;
 	void *data = heap->data;
-	void *root = data + pos * elem_size;
-	int i = pos, j;
+	/* pre-scale counters for performance */
+	size_t a = pos * elem_size;
+	size_t b, c, d;
+	size_t n = heap->nr * elem_size;
 
 	/* Find the sift-down path all the way to the leaves. */
-	for (;;) {
-		if (i * 2 + 2 >= heap->nr)
-			break;
-		left = data + (i * 2 + 1) * elem_size;
-		right = data + (i * 2 + 2) * elem_size;
-		i = func->less(left, right, args) ? i * 2 + 1 : i * 2 + 2;
-	}
+	for (b = a; c = 2 * b + elem_size, (d = c + elem_size) < n;)
+		b = func->less(data + c, data + d, args) ? c : d;
 
 	/* Special case for the last leaf with no sibling. */
-	if (i * 2 + 2 == heap->nr)
-		i = i * 2 + 1;
+	if (d == n)
+		b = c;
 
 	/* Backtrack to the correct location. */
-	while (i != pos && func->less(root, data + i * elem_size, args))
-		i = (i - 1) / 2;
+	while (b != a && func->less(data + a, data + b, args))
+		b = parent(b, lsbit, elem_size);
 
 	/* Shift the element into its correct place. */
-	j = i;
-	while (i != pos) {
-		i = (i - 1) / 2;
-		func->swp(data + i * elem_size, data + j * elem_size, args);
+	c = b;
+	while (b != a) {
+		b = parent(b, lsbit, elem_size);
+		func->swp(data + b, data + c, args);
 	}
 }
 
@@ -117,15 +140,17 @@ static __always_inline
 void __min_heap_sift_up_inline(min_heap_char *heap, size_t elem_size, size_t idx,
 			       const struct min_heap_callbacks *func, void *args)
 {
+	const unsigned long lsbit = elem_size & -elem_size;
 	void *data = heap->data;
-	size_t parent;
+	/* pre-scale counters for performance */
+	size_t a = idx * elem_size, b;
 
-	while (idx) {
-		parent = (idx - 1) / 2;
-		if (func->less(data + parent * elem_size, data + idx * elem_size, args))
+	while (a) {
+		b = parent(a, lsbit, elem_size);
+		if (func->less(data + b, data + a, args))
 			break;
-		func->swp(data + parent * elem_size, data + idx * elem_size, args);
-		idx = parent;
+		func->swp(data + a, data + b, args);
+		a = b;
 	}
 }
 
-- 
2.34.1

[PATCH 3/3] Documentation/core-api: Add min heap API introduction

[Kuan-Wei Chiu]

Introduce an overview of the min heap API, detailing its usage and
functionality. The documentation aims to provide developers with a
clear understanding of how to implement and utilize min heaps within
the Linux kernel, enhancing the overall accessibility of this data
structure.

Signed-off-by: Kuan-Wei Chiu <visitorckw@gmail.com>
---
 Documentation/core-api/index.rst    |   1 +
 Documentation/core-api/min_heap.rst | 291 ++++++++++++++++++++++++++++
 2 files changed, 292 insertions(+)
 create mode 100644 Documentation/core-api/min_heap.rst

diff --git a/Documentation/core-api/index.rst b/Documentation/core-api/index.rst
index 6a875743dd4b..563b8fc0002f 100644
--- a/Documentation/core-api/index.rst
+++ b/Documentation/core-api/index.rst
@@ -52,6 +52,7 @@ Library functionality that is used throughout the kernel.
    wrappers/atomic_bitops
    floating-point
    union_find
+   min_heap
 
 Low level entry and exit
 ========================
diff --git a/Documentation/core-api/min_heap.rst b/Documentation/core-api/min_heap.rst
new file mode 100644
index 000000000000..dd2cc5a32fd7
--- /dev/null
+++ b/Documentation/core-api/min_heap.rst
@@ -0,0 +1,291 @@
+.. SPDX-License-Identifier: GPL-2.0
+
+============
+Min Heap API
+============
+
+Introduction
+============
+
+The Min Heap API provides a set of functions and macros for managing min-heaps in the Linux kernel.
+A min-heap is a binary tree structure where the value of each node is less than or equal to the
+values of its children, ensuring that the smallest element is always at the root.
+
+This API supports efficient insertion, deletion, and access to the minimum element. It is optimized
+for use in systems with performance constraints and is suitable for scenarios where the minimum
+element needs to be accessed or updated frequently.
+
+This document provides a guide to the Min Heap API, detailing how to define and use min-heaps.
+Please note that users should not directly call functions with **__min_heap_*()** names, but should
+instead use the provided macro wrappers.
+
+In addition to the standard version of the functions, the API also includes a set of inline
+versions for performance-critical scenarios. These inline functions have the same names as their
+non-inline counterparts but include an **_inline** suffix. For example, **__min_heap_init_inline**
+and its corresponding macro wrapper **min_heap_init_inline**. As with the non-inline versions, it
+is important to use the macro wrappers for inline functions instead of directly calling the
+functions themselves.
+
+Data Structures
+===============
+
+Min-Heap Definition
+-------------------
+
+The core data structure for representing a min-heap is defined using the **MIN_HEAP_PREALLOCATED**
+and **DEFINE_MIN_HEAP** macros. These macros allow you to define a min-heap with a preallocated
+buffer or dynamically allocated memory.
+
+Example:
+
+.. code-block:: c
+
+    #define MIN_HEAP_PREALLOCATED(_type, _name, _nr)
+    struct _name {
+        int nr;         /* Number of elements in the heap */
+        int size;       /* Maximum number of elements that can be held */
+        _type *data;    /* Pointer to the heap data */
+        _type preallocated[_nr];  /* Static preallocated array */
+    }
+
+    #define DEFINE_MIN_HEAP(_type, _name) MIN_HEAP_PREALLOCATED(_type, _name, 0)
+
+A typical heap structure will include a counter for the number of elements (`nr`), the maximum
+capacity of the heap (`size`), and a pointer to an array of elements (`data`). Optionally, you can
+specify a static array for preallocated heap storage using **MIN_HEAP_PREALLOCATED**.
+
+Min Heap Callbacks
+------------------
+
+The **struct min_heap_callbacks** provides customization options for ordering
+elements in the heap and swapping them. It contains two function pointers:
+
+.. code-block:: c
+
+    struct min_heap_callbacks {
+        bool (*less)(const void *lhs, const void *rhs, void *args);
+        void (*swp)(void *lhs, void *rhs, void *args);
+    };
+
+- **less** is the comparison function used to establish the order of elements.
+- **swp** is a function for swapping elements in the heap.
+
+Macro Wrappers
+==============
+
+The following macro wrappers are provided for interacting with the heap in a user-friendly manner.
+Each macro corresponds to a function that operates on the heap, and they abstract away direct calls
+to internal functions.
+
+Each macro accepts various parameters that are detailed below.
+
+Heap Initialization
+--------------------
+
+.. code-block:: c
+
+    min_heap_init(heap, data, size);
+
+- **heap**: A pointer to the min-heap structure to be initialized.
+- **data**: A pointer to the buffer where the heap elements will be stored. If `NULL`, the preallocated buffer within the heap structure will be used.
+- **size**: The maximum number of elements the heap can hold.
+
+This macro initializes the heap, setting its initial state. If `data` is `NULL`, the preallocated
+memory inside the heap structure will be used for storage. Otherwise, the user-provided buffer is
+used. The operation is **O(1)**.
+
+**Inline Version:** min_heap_init_inline(heap, data, size)
+
+Accessing the Top Element
+-------------------------
+
+.. code-block:: c
+
+    element = min_heap_peek(heap);
+
+- **heap**: A pointer to the min-heap from which to retrieve the smallest element.
+
+This macro returns a pointer to the smallest element (the root) of the heap, or `NULL` if the heap
+is empty. The operation is **O(1)**.
+
+**Inline Version:** min_heap_peek_inline(heap)
+
+Heap Insertion
+--------------
+
+.. code-block:: c
+
+    success = min_heap_push(heap, element, callbacks, args);
+
+- **heap**: A pointer to the min-heap into which the element should be inserted.
+- **element**: A pointer to the element to be inserted into the heap.
+- **callbacks**: A pointer to a `struct min_heap_callbacks` providing the `less` and `swp` functions.
+- **args**: Optional arguments passed to the `less` and `swp` functions.
+
+This macro inserts an element into the heap. It returns `true` if the insertion was successful and
+`false` if the heap is full. The operation is **O(log n)**.
+
+**Inline Version:** min_heap_push_inline(heap, element, callbacks, args)
+
+Heap Removal
+------------
+
+.. code-block:: c
+
+    success = min_heap_pop(heap, callbacks, args);
+
+- **heap**: A pointer to the min-heap from which to remove the smallest element.
+- **callbacks**: A pointer to a `struct min_heap_callbacks` providing the `less` and `swp` functions.
+- **args**: Optional arguments passed to the `less` and `swp` functions.
+
+This macro removes the smallest element (the root) from the heap. It returns `true` if the element
+was successfully removed, or `false` if the heap is empty. The operation is **O(log n)**.
+
+**Inline Version:** min_heap_pop_inline(heap, callbacks, args)
+
+Heap Maintenance
+----------------
+
+You can use the following macros to maintain the heap's structure:
+
+.. code-block:: c
+
+    min_heap_sift_down(heap, pos, callbacks, args);
+
+- **heap**: A pointer to the min-heap.
+- **pos**: The index from which to start sifting down.
+- **callbacks**: A pointer to a `struct min_heap_callbacks` providing the `less` and `swp` functions.
+- **args**: Optional arguments passed to the `less` and `swp` functions.
+
+This macro restores the heap property by moving the element at the specified index (`pos`) down the
+heap until it is in the correct position. The operation is **O(log n)**.
+
+**Inline Version:** min_heap_sift_down_inline(heap, pos, callbacks, args)
+
+.. code-block:: c
+
+    min_heap_sift_up(heap, idx, callbacks, args);
+
+- **heap**: A pointer to the min-heap.
+- **idx**: The index of the element to sift up.
+- **callbacks**: A pointer to a `struct min_heap_callbacks` providing the `less` and `swp` functions.
+- **args**: Optional arguments passed to the `less` and `swp` functions.
+
+This macro restores the heap property by moving the element at the specified index (`idx`) up the
+heap. The operation is **O(log n)**.
+
+**Inline Version:** min_heap_sift_up_inline(heap, idx, callbacks, args)
+
+.. code-block:: c
+
+    min_heapify_all(heap, callbacks, args);
+
+- **heap**: A pointer to the min-heap.
+- **callbacks**: A pointer to a `struct min_heap_callbacks` providing the `less` and `swp` functions.
+- **args**: Optional arguments passed to the `less` and `swp` functions.
+
+This macro ensures that the entire heap satisfies the heap property. It is called when the heap is
+built from scratch or after many modifications. The  operation is **O(n)**.
+
+**Inline Version:** min_heapify_all_inline(heap, callbacks, args)
+
+Removing Specific Elements
+--------------------------
+
+.. code-block:: c
+
+    success = min_heap_del(heap, idx, callbacks, args);
+
+- **heap**: A pointer to the min-heap.
+- **idx**: The index of the element to delete.
+- **callbacks**: A pointer to a `struct min_heap_callbacks` providing the `less` and `swp` functions.
+- **args**: Optional arguments passed to the `less` and `swp` functions.
+
+This macro removes an element at the specified index (`idx`) from the heap and restores the heap
+property. The operation is **O(log n)**.
+
+**Inline Version:** min_heap_del_inline(heap, idx, callbacks, args)
+
+Other Utilities
+===============
+
+- **min_heap_full(heap)**: Checks whether the heap is full. Complexity: **O(1)**.
+
+.. code-block:: c
+
+    bool full = min_heap_full(heap);
+
+- `heap`: A pointer to the min-heap to check.
+
+This macro returns `true` if the heap is full, otherwise `false`.
+
+**Inline Version:** min_heap_full_inline(heap)
+
+- **min_heap_empty(heap)**: Checks whether the heap is empty. Complexity: **O(1)**.
+
+.. code-block:: c
+
+    bool empty = min_heap_empty(heap);
+
+- `heap`: A pointer to the min-heap to check.
+
+This macro returns `true` if the heap is empty, otherwise `false`.
+
+**Inline Version:** min_heap_empty_inline(heap)
+
+Example Usage
+=============
+
+An example usage of the min-heap API would involve defining a heap structure,
+initializing it, and inserting and removing elements as needed.
+
+.. code-block:: c
+
+    /* Define a preallocated heap for storing up to 10 elements */
+    MIN_HEAP_PREALLOCATED(int, my_heap, 10);
+
+    struct min_heap_callbacks callbacks = {
+        .less = my_less,  /* Custom comparison function */
+        .swp = my_swap,   /* Custom swap function */
+    };
+
+    /* Initialize the heap using the preallocated buffer */
+    min_heap_init(&my_heap, NULL, ARRAY_SIZE(my_heap.preallocated));
+
+    /* If we have an external buffer, we can use it instead */
+    int external_buffer[20];
+    min_heap_init(&my_heap, external_buffer, ARRAY_SIZE(external_buffer));
+
+    /* Insert elements into the heap */
+    int new_element = 5;
+    if (!min_heap_full(&my_heap)) {
+        min_heap_push(&my_heap, &new_element, &callbacks, NULL);
+    }
+
+    /* Peek at the minimum element (without removing it) */
+    int *min_element = min_heap_peek(&my_heap);
+
+    /* Replace the root of the heap with a new element */
+    int replacement_element = 3;
+    min_heap_pop_push(&my_heap, &replacement_element, &callbacks, NULL);
+
+    /* Reorder the heap by sifting down from a given position */
+    min_heap_sift_down(&my_heap, 0, &callbacks, NULL);
+
+    /* Remove the minimum element from the heap */
+    if (!min_heap_empty(&my_heap)) {
+        min_heap_pop(&my_heap, &callbacks, NULL);
+    }
+
+    /* Insert more elements into the heap */
+    new_element = 8;
+    if (!min_heap_full(&my_heap)) {
+        min_heap_push(&my_heap, &new_element, &callbacks, NULL);
+    }
+
+    /* Delete an element from the heap at a specific index */
+    int idx_to_delete = 2;
+    min_heap_del(&my_heap, idx_to_delete, &callbacks, NULL);
+
+    /* Ensure the entire heap maintains heap order */
+    min_heapify_all(&my_heap, &callbacks, NULL);
-- 
2.34.1

Re: [PATCH 0/3] Enhance min heap API with non-inline functions and optimizations

[Kent Overstreet]

On Mon, Oct 14, 2024 at 02:47:00AM GMT, Kuan-Wei Chiu wrote:
> 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. 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.

Nice, has it been tested - do you need a CI account?

I'd like to start seeing links to CI results in patch postings (and I
need to tweak the CI to add git fetch links, as well).

Coly, there's ktest tests for bcache that need to be updated - if you
wanted to take that on it'd be lovely to consolidate how our subsystems
are getting tested; I can give you a CI account as well.

> 
> Regards,
> Kuan-Wei
> 
> Kuan-Wei Chiu (3):
>   lib/min_heap: Introduce non-inline versions of min heap API functions
>   lib min_heap: Optimize min heap by prescaling counters for better
>     performance
>   Documentation/core-api: Add min heap API introduction
> 
>  Documentation/core-api/index.rst    |   1 +
>  Documentation/core-api/min_heap.rst | 291 ++++++++++++++++++++++++++++
>  drivers/md/bcache/Kconfig           |   1 +
>  drivers/md/dm-vdo/Kconfig           |   1 +
>  fs/bcachefs/Kconfig                 |   1 +
>  include/linux/min_heap.h            | 202 ++++++++++++-------
>  kernel/events/core.c                |   6 +-
>  lib/Kconfig                         |   3 +
>  lib/Kconfig.debug                   |   1 +
>  lib/Makefile                        |   1 +
>  lib/min_heap.c                      |  70 +++++++
>  11 files changed, 508 insertions(+), 70 deletions(-)
>  create mode 100644 Documentation/core-api/min_heap.rst
>  create mode 100644 lib/min_heap.c

Re: [PATCH 0/3] Enhance min heap API with non-inline functions and optimizations

[Kuan-Wei Chiu]

On Sun, Oct 13, 2024 at 07:05:38PM -0400, Kent Overstreet wrote:
> On Mon, Oct 14, 2024 at 02:47:00AM GMT, Kuan-Wei Chiu wrote:
> > 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. 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.
> 
> Nice, has it been tested - do you need a CI account?
> 
> I'd like to start seeing links to CI results in patch postings (and I
> need to tweak the CI to add git fetch links, as well).
>
It would be nice to have a CI account to test my patches. Is there any
guide available on how to use it?

Regards,
Kuan-Wei

> Coly, there's ktest tests for bcache that need to be updated - if you
> wanted to take that on it'd be lovely to consolidate how our subsystems
> are getting tested; I can give you a CI account as well.
> 
> > 
> > Regards,
> > Kuan-Wei
> > 
> > Kuan-Wei Chiu (3):
> >   lib/min_heap: Introduce non-inline versions of min heap API functions
> >   lib min_heap: Optimize min heap by prescaling counters for better
> >     performance
> >   Documentation/core-api: Add min heap API introduction
> > 
> >  Documentation/core-api/index.rst    |   1 +
> >  Documentation/core-api/min_heap.rst | 291 ++++++++++++++++++++++++++++
> >  drivers/md/bcache/Kconfig           |   1 +
> >  drivers/md/dm-vdo/Kconfig           |   1 +
> >  fs/bcachefs/Kconfig                 |   1 +
> >  include/linux/min_heap.h            | 202 ++++++++++++-------
> >  kernel/events/core.c                |   6 +-
> >  lib/Kconfig                         |   3 +
> >  lib/Kconfig.debug                   |   1 +
> >  lib/Makefile                        |   1 +
> >  lib/min_heap.c                      |  70 +++++++
> >  11 files changed, 508 insertions(+), 70 deletions(-)
> >  create mode 100644 Documentation/core-api/min_heap.rst
> >  create mode 100644 lib/min_heap.c
> 

Re: [PATCH 0/3] Enhance min heap API with non-inline functions and optimizations

[Coly Li]

> 2024年10月14日 07:05，Kent Overstreet <kent.overstreet@linux.dev> 写道：
> 
> On Mon, Oct 14, 2024 at 02:47:00AM GMT, Kuan-Wei Chiu wrote:
>> 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. 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.
> 
> Nice, has it been tested - do you need a CI account?
> 
> I'd like to start seeing links to CI results in patch postings (and I
> need to tweak the CI to add git fetch links, as well).
> 
> Coly, there's ktest tests for bcache that need to be updated - if you
> wanted to take that on it'd be lovely to consolidate how our subsystems
> are getting tested; I can give you a CI account as well.

Yes, please do. And let me take a look at the test cases for bcache part.

Thanks.

Coly Li

Re: [PATCH 0/3] Enhance min heap API with non-inline functions and optimizations

[Kent Overstreet]

On Mon, Oct 14, 2024 at 09:18:33AM GMT, Coly Li wrote:
> 
> 
> > 2024年10月14日 07:05，Kent Overstreet <kent.overstreet@linux.dev> 写道：
> > 
> > On Mon, Oct 14, 2024 at 02:47:00AM GMT, Kuan-Wei Chiu wrote:
> >> 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. 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.
> > 
> > Nice, has it been tested - do you need a CI account?
> > 
> > I'd like to start seeing links to CI results in patch postings (and I
> > need to tweak the CI to add git fetch links, as well).
> > 
> > Coly, there's ktest tests for bcache that need to be updated - if you
> > wanted to take that on it'd be lovely to consolidate how our subsystems
> > are getting tested; I can give you a CI account as well.
> 
> Yes, please do. And let me take a look at the test cases for bcache part.

Send me the username you want and your ssh pubkey

bcache tests are here:
https://evilpiepirate.org/git/ktest.git/tree/tests/bcache

they are _old_, and need a lot of updating - you'll probably want to hit
me up on IRC

Re: [PATCH 0/3] Enhance min heap API with non-inline functions and optimizations

[Kent Overstreet]

On Mon, Oct 14, 2024 at 07:27:06AM GMT, Kuan-Wei Chiu wrote:
> On Sun, Oct 13, 2024 at 07:05:38PM -0400, Kent Overstreet wrote:
> > On Mon, Oct 14, 2024 at 02:47:00AM GMT, Kuan-Wei Chiu wrote:
> > > 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. 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.
> > 
> > Nice, has it been tested - do you need a CI account?
> > 
> > I'd like to start seeing links to CI results in patch postings (and I
> > need to tweak the CI to add git fetch links, as well).
> >
> It would be nice to have a CI account to test my patches. Is there any
> guide available on how to use it?

I give you a config file to edit, it watches your git branch(es), you
watch dashboard

Re: [PATCH 1/3] lib/min_heap: Introduce non-inline versions of min heap API functions

[Peter Zijlstra]

On Mon, Oct 14, 2024 at 02:47:01AM +0800, Kuan-Wei Chiu wrote:
> All current min heap API functions are marked with '__always_inline'.
> However, as the number of users increases, inlining these functions
> everywhere leads to a significant increase in kernel size.
> 
> In performance-critical paths, such as when perf events are enabled and
> min heap functions are called on every context switch, it is important
> to retain the inline versions for optimal performance. To balance this,
> the original inline functions are kept, and additional non-inline
> versions of the functions have been added in lib/min_heap.c.

The reason it is all __always_inline is because then the whole
min_heap_callbacks thing can be constant propagated and the func->less()
etc calls become direct calls.

Doing out of line for this stuff, makes them indirect calls, and
indirect calls are super retarded expensive ever since spectre. But also
things like kCFI add significant cost to indirect calls.

Something that would be a trivial subtract instruction becomes this
giant mess of an indirect function call.

Given the whole min_heap thing is basically a ton of less() and swp()
calls, I really don't think this trade off makes any kind of sense.

Re: [PATCH 1/3] lib/min_heap: Introduce non-inline versions of min heap API functions

[Peter Zijlstra]

On Mon, Oct 14, 2024 at 10:13:58AM +0200, Peter Zijlstra wrote:
> On Mon, Oct 14, 2024 at 02:47:01AM +0800, Kuan-Wei Chiu wrote:
> > All current min heap API functions are marked with '__always_inline'.
> > However, as the number of users increases, inlining these functions
> > everywhere leads to a significant increase in kernel size.
> > 
> > In performance-critical paths, such as when perf events are enabled and
> > min heap functions are called on every context switch, it is important
> > to retain the inline versions for optimal performance. To balance this,
> > the original inline functions are kept, and additional non-inline
> > versions of the functions have been added in lib/min_heap.c.
> 
> The reason it is all __always_inline is because then the whole
> min_heap_callbacks thing can be constant propagated and the func->less()
> etc calls become direct calls.

Or better, they can get inlined too.

> Doing out of line for this stuff, makes them indirect calls, and
> indirect calls are super retarded expensive ever since spectre. But also
> things like kCFI add significant cost to indirect calls.
> 
> Something that would be a trivial subtract instruction becomes this
> giant mess of an indirect function call.
> 
> Given the whole min_heap thing is basically a ton of less() and swp()
> calls, I really don't think this trade off makes any kind of sense.

Re: [PATCH 3/3] Documentation/core-api: Add min heap API introduction

[Matthew Wilcox]

On Mon, Oct 14, 2024 at 02:47:03AM +0800, Kuan-Wei Chiu wrote:
> Introduce an overview of the min heap API, detailing its usage and
> functionality. The documentation aims to provide developers with a
> clear understanding of how to implement and utilize min heaps within
> the Linux kernel, enhancing the overall accessibility of this data
> structure.

Please format this text to 80 columns.  Just pass it through 'fmt'.

> +This API supports efficient insertion, deletion, and access to the minimum element. It is optimized
> +for use in systems with performance constraints and is suitable for scenarios where the minimum
> +element needs to be accessed or updated frequently.

All systems have "performance constraints".  I'm not sure what that
means in this context.

> +This document provides a guide to the Min Heap API, detailing how to define and use min-heaps.
> +Please note that users should not directly call functions with **__min_heap_*()** names, but should
> +instead use the provided macro wrappers.

You can always remove "Please note that".  It has no meaning.  Just say
"You should not call functions with **__min_heap_** prefixes; use the
functions documented here instead.

> +Min-Heap Definition
> +-------------------
> +
> +The core data structure for representing a min-heap is defined using the **MIN_HEAP_PREALLOCATED**
> +and **DEFINE_MIN_HEAP** macros. These macros allow you to define a min-heap with a preallocated
> +buffer or dynamically allocated memory.
> +
> +Example:
> +
> +.. code-block:: c
> +
> +    #define MIN_HEAP_PREALLOCATED(_type, _name, _nr)
> +    struct _name {
> +        int nr;         /* Number of elements in the heap */
> +        int size;       /* Maximum number of elements that can be held */
> +        _type *data;    /* Pointer to the heap data */
> +        _type preallocated[_nr];  /* Static preallocated array */
> +    }

This isn't an example of code the reader of this document would write
though, is it?  This looks like code already provided.  An example
should be something like:

MIN_HEAP_PREALLOCATED(struct page, my_pages, 23);

... or whatever would actually make sense.

Re: [PATCH 1/3] lib/min_heap: Introduce non-inline versions of min heap API functions

[Kuan-Wei Chiu]

On Mon, Oct 14, 2024 at 10:13:58AM +0200, Peter Zijlstra wrote:
> On Mon, Oct 14, 2024 at 02:47:01AM +0800, Kuan-Wei Chiu wrote:
> > All current min heap API functions are marked with '__always_inline'.
> > However, as the number of users increases, inlining these functions
> > everywhere leads to a significant increase in kernel size.
> > 
> > In performance-critical paths, such as when perf events are enabled and
> > min heap functions are called on every context switch, it is important
> > to retain the inline versions for optimal performance. To balance this,
> > the original inline functions are kept, and additional non-inline
> > versions of the functions have been added in lib/min_heap.c.
> 
> The reason it is all __always_inline is because then the whole
> min_heap_callbacks thing can be constant propagated and the func->less()
> etc calls become direct calls.
> 
> Doing out of line for this stuff, makes them indirect calls, and
> indirect calls are super retarded expensive ever since spectre. But also
> things like kCFI add significant cost to indirect calls.
> 
> Something that would be a trivial subtract instruction becomes this
> giant mess of an indirect function call.
>
Yes, I also learned from reading the lib/sort.c git log that indirect
function calls can become especially expensive when
CONFIG_MITIGATION_RETPOLINE is enabled.

I'm not an expert in bcache, bcachefs, or dm-vdo, but when Andrew
previously suggested moving these functions to lib/min_heap, Kent
expressed his support. This led me to believe that in bcache and
bcachefs (which are the primary users of min_heap), these indirect
function calls are considered acceptable. However, that's just my
assumption — I'll wait for Kent to chime in on this.

> Given the whole min_heap thing is basically a ton of less() and swp()
> calls, I really don't think this trade off makes any kind of sense.

As for your point about min_heap being full of less() and swp() calls,
we could handle swp() the same way it's done in lib/sort.c by providing
a built-in swap function, which would help avoid indirect function
calls in places other than fs/bcachefs/ec.c. However, for less(), it
seems there might not be a way around it.

Regards,
Kuan-Wei

Re: [PATCH 3/3] Documentation/core-api: Add min heap API introduction

[Kuan-Wei Chiu]

On Mon, Oct 14, 2024 at 09:55:56AM +0100, Matthew Wilcox wrote:
> On Mon, Oct 14, 2024 at 02:47:03AM +0800, Kuan-Wei Chiu wrote:
> > Introduce an overview of the min heap API, detailing its usage and
> > functionality. The documentation aims to provide developers with a
> > clear understanding of how to implement and utilize min heaps within
> > the Linux kernel, enhancing the overall accessibility of this data
> > structure.
> 
> Please format this text to 80 columns.  Just pass it through 'fmt'.
> 
> > +This API supports efficient insertion, deletion, and access to the minimum element. It is optimized
> > +for use in systems with performance constraints and is suitable for scenarios where the minimum
> > +element needs to be accessed or updated frequently.
> 
> All systems have "performance constraints".  I'm not sure what that
> means in this context.
> 
> > +This document provides a guide to the Min Heap API, detailing how to define and use min-heaps.
> > +Please note that users should not directly call functions with **__min_heap_*()** names, but should
> > +instead use the provided macro wrappers.
> 
> You can always remove "Please note that".  It has no meaning.  Just say
> "You should not call functions with **__min_heap_** prefixes; use the
> functions documented here instead.
> 
> > +Min-Heap Definition
> > +-------------------
> > +
> > +The core data structure for representing a min-heap is defined using the **MIN_HEAP_PREALLOCATED**
> > +and **DEFINE_MIN_HEAP** macros. These macros allow you to define a min-heap with a preallocated
> > +buffer or dynamically allocated memory.
> > +
> > +Example:
> > +
> > +.. code-block:: c
> > +
> > +    #define MIN_HEAP_PREALLOCATED(_type, _name, _nr)
> > +    struct _name {
> > +        int nr;         /* Number of elements in the heap */
> > +        int size;       /* Maximum number of elements that can be held */
> > +        _type *data;    /* Pointer to the heap data */
> > +        _type preallocated[_nr];  /* Static preallocated array */
> > +    }
> 
> This isn't an example of code the reader of this document would write
> though, is it?  This looks like code already provided.  An example
> should be something like:
> 
> MIN_HEAP_PREALLOCATED(struct page, my_pages, 23);
> 
> ... or whatever would actually make sense.

Thank you for the review. I'll wait for the decision on whether to keep
the non-inline API before sending a v2 patch to address these comments.

Regards,
Kuan-Wei

Re: [PATCH 1/3] lib/min_heap: Introduce non-inline versions of min heap API functions

[Kent Overstreet]

On Mon, Oct 14, 2024 at 05:41:23PM +0800, Kuan-Wei Chiu wrote:
> On Mon, Oct 14, 2024 at 10:13:58AM +0200, Peter Zijlstra wrote:
> > On Mon, Oct 14, 2024 at 02:47:01AM +0800, Kuan-Wei Chiu wrote:
> > > All current min heap API functions are marked with '__always_inline'.
> > > However, as the number of users increases, inlining these functions
> > > everywhere leads to a significant increase in kernel size.
> > > 
> > > In performance-critical paths, such as when perf events are enabled and
> > > min heap functions are called on every context switch, it is important
> > > to retain the inline versions for optimal performance. To balance this,
> > > the original inline functions are kept, and additional non-inline
> > > versions of the functions have been added in lib/min_heap.c.
> > 
> > The reason it is all __always_inline is because then the whole
> > min_heap_callbacks thing can be constant propagated and the func->less()
> > etc calls become direct calls.
> > 
> > Doing out of line for this stuff, makes them indirect calls, and
> > indirect calls are super retarded expensive ever since spectre. But also
> > things like kCFI add significant cost to indirect calls.
> > 
> > Something that would be a trivial subtract instruction becomes this
> > giant mess of an indirect function call.
> >
> Yes, I also learned from reading the lib/sort.c git log that indirect
> function calls can become especially expensive when
> CONFIG_MITIGATION_RETPOLINE is enabled.
> 
> I'm not an expert in bcache, bcachefs, or dm-vdo, but when Andrew
> previously suggested moving these functions to lib/min_heap, Kent
> expressed his support. This led me to believe that in bcache and
> bcachefs (which are the primary users of min_heap), these indirect
> function calls are considered acceptable. However, that's just my
> assumption — I'll wait for Kent to chime in on this.

yeah, I think we would prefer smaller codesize, by default.

it'd be well worth checking the code size difference on inlined vs. not,
and then the really think to do would be to provide optional _inlined()
helpers that we can switch to if/when a particular codepath shows up in
a profile

Re: [PATCH 1/3] lib/min_heap: Introduce non-inline versions of min heap API functions

[Peter Zijlstra]

On Wed, Oct 16, 2024 at 11:26:30PM -0400, Kent Overstreet wrote:

> yeah, I think we would prefer smaller codesize, by default.
> 
> it'd be well worth checking the code size difference on inlined vs. not,
> and then the really think to do would be to provide optional _inlined()
> helpers that we can switch to if/when a particular codepath shows up in
> a profile

Make sure to build with kCFI and IBT enabled when you do this and enjoy
seeing ec_stripes_heap_cmp turn into this:

00000000000027c0 <__cfi_ec_stripes_heap_cmp>:
    27c0:       b8 01 88 88 07          mov    $0x7888801,%eax
    27c5:       90                      nop
    27c6:       90                      nop
    27c7:       90                      nop
    27c8:       90                      nop
    27c9:       90                      nop
    27ca:       90                      nop
    27cb:       90                      nop
    27cc:       90                      nop
    27cd:       90                      nop
    27ce:       90                      nop
    27cf:       90                      nop

00000000000027d0 <ec_stripes_heap_cmp>:
    27d0:       f3 0f 1e fa             endbr64
    27d4:       e8 00 00 00 00          call   27d9 <ec_stripes_heap_cmp+0x9>   27d5: R_X86_64_PLT32    __fentry__-0x4
    27d9:       8b 47 08                mov    0x8(%rdi),%eax
    27dc:       3b 46 08                cmp    0x8(%rsi),%eax
    27df:       0f 92 c0                setb   %al
    27e2:       2e e9 00 00 00 00       cs jmp 27e8 <ec_stripes_heap_cmp+0x18>  27e4: R_X86_64_PLT32    __x86_return_thunk-0x4
    27e8:       0f 1f 84 00 00 00 00 00         nopl   0x0(%rax,%rax,1)
    27f0:       90                      nop
    27f1:       90                      nop
    27f2:       90                      nop
    27f3:       90                      nop
    27f4:       90                      nop


While I was there, you might want to do the below. It makes no sense
duplicating that thing.

---

diff --git a/fs/bcachefs/ec.c b/fs/bcachefs/ec.c
index 1587c6e1866a..3a6c34cf8a15 100644
--- a/fs/bcachefs/ec.c
+++ b/fs/bcachefs/ec.c
@@ -1048,6 +1048,11 @@ static inline void ec_stripes_heap_swap(void *l, void *r, void *h)
 	ec_stripes_heap_set_backpointer(_h, j);
 }
 
+static const struct min_heap_callbacks ec_stripes_callbacks = {
+	.less = ec_stripes_heap_cmp,
+	.swp = ec_stripes_heap_swap,
+};
+
 static void heap_verify_backpointer(struct bch_fs *c, size_t idx)
 {
 	ec_stripes_heap *h = &c->ec_stripes_heap;
@@ -1060,26 +1065,16 @@ static void heap_verify_backpointer(struct bch_fs *c, size_t idx)
 void bch2_stripes_heap_del(struct bch_fs *c,
 			   struct stripe *m, size_t idx)
 {
-	const struct min_heap_callbacks callbacks = {
-		.less = ec_stripes_heap_cmp,
-		.swp = ec_stripes_heap_swap,
-	};
-
 	mutex_lock(&c->ec_stripes_heap_lock);
 	heap_verify_backpointer(c, idx);
 
-	min_heap_del(&c->ec_stripes_heap, m->heap_idx, &callbacks, &c->ec_stripes_heap);
+	min_heap_del(&c->ec_stripes_heap, m->heap_idx, &ec_strips_callbacks, &c->ec_stripes_heap);
 	mutex_unlock(&c->ec_stripes_heap_lock);
 }
 
 void bch2_stripes_heap_insert(struct bch_fs *c,
 			      struct stripe *m, size_t idx)
 {
-	const struct min_heap_callbacks callbacks = {
-		.less = ec_stripes_heap_cmp,
-		.swp = ec_stripes_heap_swap,
-	};
-
 	mutex_lock(&c->ec_stripes_heap_lock);
 	BUG_ON(min_heap_full(&c->ec_stripes_heap));
 
@@ -1088,7 +1083,7 @@ void bch2_stripes_heap_insert(struct bch_fs *c,
 			.idx = idx,
 			.blocks_nonempty = m->blocks_nonempty,
 		}),
-		&callbacks,
+		&ec_stripes_callbacks,
 		&c->ec_stripes_heap);
 
 	heap_verify_backpointer(c, idx);
@@ -1098,10 +1093,6 @@ void bch2_stripes_heap_insert(struct bch_fs *c,
 void bch2_stripes_heap_update(struct bch_fs *c,
 			      struct stripe *m, size_t idx)
 {
-	const struct min_heap_callbacks callbacks = {
-		.less = ec_stripes_heap_cmp,
-		.swp = ec_stripes_heap_swap,
-	};
 	ec_stripes_heap *h = &c->ec_stripes_heap;
 	bool do_deletes;
 	size_t i;
@@ -1112,8 +1103,8 @@ void bch2_stripes_heap_update(struct bch_fs *c,
 	h->data[m->heap_idx].blocks_nonempty = m->blocks_nonempty;
 
 	i = m->heap_idx;
-	min_heap_sift_up(h,	i, &callbacks, &c->ec_stripes_heap);
-	min_heap_sift_down(h, i, &callbacks, &c->ec_stripes_heap);
+	min_heap_sift_up(  h, i, &ec_stripes_callbacks, &c->ec_stripes_heap);
+	min_heap_sift_down(h, i, &ec_stripes_callbacks, &c->ec_stripes_heap);
 
 	heap_verify_backpointer(c, idx);
 

Re: [PATCH 1/3] lib/min_heap: Introduce non-inline versions of min heap API functions

[Kent Overstreet]

On Thu, Oct 17, 2024 at 11:55:20AM +0200, Peter Zijlstra wrote:
> On Wed, Oct 16, 2024 at 11:26:30PM -0400, Kent Overstreet wrote:
> 
> > yeah, I think we would prefer smaller codesize, by default.
> > 
> > it'd be well worth checking the code size difference on inlined vs. not,
> > and then the really think to do would be to provide optional _inlined()
> > helpers that we can switch to if/when a particular codepath shows up in
> > a profile
> 
> Make sure to build with kCFI and IBT enabled when you do this and enjoy
> seeing ec_stripes_heap_cmp turn into this:

I wouldn't worry too much about the stripes heap, I'm going to replace
that with a persistent LRU.

After that it looks like the only heap left in bcachefs will be in the
clock code. Shame, they're one of my favorite data structures...

Re: [PATCH 1/3] lib/min_heap: Introduce non-inline versions of min heap API functions

[Kuan-Wei Chiu]

On Mon, Oct 14, 2024 at 10:13:58AM +0200, Peter Zijlstra wrote:
> On Mon, Oct 14, 2024 at 02:47:01AM +0800, Kuan-Wei Chiu wrote:
> > All current min heap API functions are marked with '__always_inline'.
> > However, as the number of users increases, inlining these functions
> > everywhere leads to a significant increase in kernel size.
> > 
> > In performance-critical paths, such as when perf events are enabled and
> > min heap functions are called on every context switch, it is important
> > to retain the inline versions for optimal performance. To balance this,
> > the original inline functions are kept, and additional non-inline
> > versions of the functions have been added in lib/min_heap.c.
> 
> The reason it is all __always_inline is because then the whole
> min_heap_callbacks thing can be constant propagated and the func->less()
> etc calls become direct calls.
> 
> Doing out of line for this stuff, makes them indirect calls, and
> indirect calls are super retarded expensive ever since spectre. But also
> things like kCFI add significant cost to indirect calls.
> 
> Something that would be a trivial subtract instruction becomes this
> giant mess of an indirect function call.
> 
> Given the whole min_heap thing is basically a ton of less() and swp()
> calls, I really don't think this trade off makes any kind of sense.

BTW, Regarding the concerns about the efficiency impact of indirect
function calls, should we also consider converting some calls to
sort()/list_sort() into inline function calls? The comparison functions
they require could lead to a significant number of indirect calls.

For instance, the comparison function passed to list_sort() in ubifs
calls cond_resched(), which implies that the linked list could be
lengthy, further increasing the likelihood of numerous indirect calls.

Regards,
Kuan-Wei