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

[Kuan-Wei Chiu <visitorckw@gmail.com>]

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