Hi Geert,

On Tue, Nov 26, 2024 at 02:27:09PM +0100, Geert Uytterhoeven wrote:

Hi Kuan-Wei,

On Sun, Oct 20, 2024 at 6:02 AM Kuan-Wei Chiu visitorckw@gmail.com 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 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-founda... Suggested-by: Andrew Morton akpm@linux-foundation.org Signed-off-by: Kuan-Wei Chiu visitorckw@gmail.com

Thanks for your patch, which is now commit 92a8b224b833e82d ("lib/min_heap: introduce non-inline versions of min heap API functions") upstream.

...

--- a/include/linux/min_heap.h +++ b/include/linux/min_heap.h

...

@@ -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)
  

Casting macro parameters without any further checks prevents the compiler from detecting silly mistakes. Would it be possible to add safety-nets here and below, using e.g. container_of() or typeof() checks?

IIUC, the concern is that passing a pointer that is not of type min_heap might lead to compiler errors being missed. To address this, one possible solution could be to expand the members of struct min_heap into individual parameters for the function.

diff --git a/include/linux/min_heap.h b/include/linux/min_heap.h index e781727c8916..ebd577003f0b 100644 --- a/include/linux/min_heap.h +++ b/include/linux/min_heap.h @@ -207,18 +207,20 @@ static size_t parent(size_t i, unsigned int lsbit, size_t size)

/* Initialize a min-heap. */ static __always_inline -void __min_heap_init_inline(min_heap_char *heap, void *data, int size) +void __min_heap_init_inline(int *heap_nr, int *heap_size, void **heap_data, + void *heap_preallocated, void *data, int size) { - heap->nr = 0; - heap->size = size; + *heap_nr = 0; + *heap_size = size; if (data) - heap->data = data; + *heap_data = data; else - heap->data = heap->preallocated; + *heap_data = heap_preallocated; }

#define min_heap_init_inline(_heap, _data, _size) \ - __min_heap_init_inline((min_heap_char *)_heap, _data, _size) + __min_heap_init_inline(&(_heap)->nr, &(_heap)->size, (void**)&(_heap)->data, \ + &(_heap)->preallocated, _data, _size)

/* Get the minimum element from the heap. */ static __always_inline

Alternatively, we could use container_of() for type safety.

diff --git a/include/linux/min_heap.h b/include/linux/min_heap.h index e781727c8916..fb96b1b82fb0 100644 --- a/include/linux/min_heap.h +++ b/include/linux/min_heap.h @@ -218,7 +218,7 @@ void __min_heap_init_inline(min_heap_char *heap, void *data, int size) }

#define min_heap_init_inline(_heap, _data, _size) \ - __min_heap_init_inline((min_heap_char *)_heap, _data, _size) + __min_heap_init_inline(container_of(&(_heap)->nr, min_heap_char, nr), _data, _size)

/* Get the minimum element from the heap. */ static __always_inline

The first approach has better readability, while the second minimizes the changes needed. Please let me know your thoughts.

...

--- a/lib/Kconfig +++ b/lib/Kconfig @@ -777,3 +777,6 @@ config POLYNOMIAL

config FIRMWARE_TABLE bool

+config MIN_HEAP

•   bool
  

Perhaps tristate? See also below.

...

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

Ideally, tests should not select functionality, to prevent increasing the attack vector by merely enabling (modular) tests.

Makes sense. Thanks for catching this.

In this particular case, just using "depends on MIN_HEAP" is not an option, as MIN_HEAP is not user-visible, and thus cannot be enabled by the user on its own. However, making MIN_HEAP tristate could be a first step for the modular case.

The builtin case is harder to fix, as e.g.

    depends on MIN_HEAP || COMPILE_TEST
    select MIN_HEAP if COMPILE_TEST

would still trigger a recursive dependency error.

Alternatively, the test could just keep on using the inline variants, unless CONFIG_MIN_HEAP=y? Or event test both for the latter?

I think that having min_heap_test continue using the inline variants might be the simplest solution?

Regards, Kuan-Wei

...

    help
      Enable this to turn on min heap function tests. This test is
      executed only once during system boot (so affects only boot time),

Gr{oetje,eeting}s,

                    Geert

-- Geert Uytterhoeven -- There's lots of Linux beyond ia32 -- geert@linux-m68k.org

In personal conversations with technical people, I call myself a hacker. But when I'm talking to journalists I just say "programmer" or something like that. -- Linus Torvalds