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.1On 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.
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
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
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
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);
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...
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.
© 2016 - 2024 Red Hat, Inc.