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

Hi Kuan-Wei,

On Wed, Nov 27, 2024 at 3:59 AM Kuan-Wei Chiu <[email protected]> wrote:
> On Tue, Nov 26, 2024 at 02:27:09PM +0100, Geert Uytterhoeven wrote:
> > On Sun, Oct 20, 2024 at 6:02 AM Kuan-Wei Chiu <[email protected]> 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/[email protected]
> > > Suggested-by: Andrew Morton <[email protected]>
> > > Signed-off-by: Kuan-Wei Chiu <[email protected]>
> >
> > 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,

Exactly.

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

Which means all functions and users must be updated now, and possibly
again in the future (when there is ever a need to change the struct).

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

container_of() is a well-known idiom in the Linux kernel, so I would go
for this solution, for min_heap_init_inline() and all other functions
currently using such a cast.

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

As lib/min_heap.c contains just wrappers around the inline functions,
that would be fine for me.  If/when lib/min_heap.c gains more
functionality, tests for that can be added to lib/test_min_heap.c
inside an #ifdef CONFIG_MIN_HEAP/#endif block.

Thanks!

Gr{oetje,eeting}s,

                        Geert

-- 
Geert Uytterhoeven -- There's lots of Linux beyond ia32 -- [email protected]

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