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