Re: [PATCH v2 01/10] lib/min_heap: Introduce non-inline versions of min heap API functions

Kuan-Wei Chiu
2024-11-27T02:59:41Z

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