Hi Kuan-Wei, On Wed, Nov 27, 2024 at 3:59 AM Kuan-Wei Chiu <visitorckw@xxxxxxxxx> 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 <visitorckw@xxxxxxxxx> 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@xxxxxxxxxxxxxxxxxxxx > > > Suggested-by: Andrew Morton <akpm@xxxxxxxxxxxxxxxxxxxx> > > > Signed-off-by: Kuan-Wei Chiu <visitorckw@xxxxxxxxx> > > > > 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 -- geert@xxxxxxxxxxxxxx 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
