linux-stable.git/include/linux/min_heap.h, branch v6.13.7

lib min_heap: avoid indirect function call by providing default swap

2024-11-06T01:12:35+00:00

The non-inline min heap API can result in an indirect function call to the
custom swap function.  This becomes particularly costly when
CONFIG_MITIGATION_RETPOLINE is enabled, as indirect function calls are
expensive in this case.

To address this, copy the code from lib/sort.c and provide a default
builtin swap implementation that performs element swaps based on the
element size.  This change allows most users to avoid the overhead of
indirect function calls, improving efficiency.

Link: https://lkml.kernel.org/r/20241020040200.939973-4-visitorckw@gmail.com
Signed-off-by: Kuan-Wei Chiu 
Cc: Adrian Hunter 
Cc: Arnaldo Carvalho de Melo 
Cc: Ching-Chun (Jim) Huang 
Cc: Coly Li 
Cc: Ian Rogers 
Cc: Ingo Molnar 
Cc: Jiri Olsa 
Cc: Jonathan Corbet 
Cc: Kent Overstreet 
Cc: "Liang, Kan" 
Cc: Mark Rutland 
Cc: Matthew Sakai 
Cc: Matthew Wilcox (Oracle) 
Cc: Namhyung Kim 
Cc: Peter Zijlstra 
Signed-off-by: Andrew Morton

lib min_heap: optimize min heap by prescaling counters for better performance

2024-11-06T01:12:35+00:00

Improve the efficiency of the min heap by prescaling counters, eliminating
the need to repeatedly compute 'index * element_size' when accessing
elements.  By doing so, we avoid the overhead associated with
recalculating the byte offset for each heap operation.

However, with prescaling, the calculation for the parent element's
location is no longer as simple as '(i - 1) / 2'.  To address this, we
copy the parent function from 'lib/sort.c', which calculates the parent
offset in a branchless manner without using any division instructions.

This optimization should result in a more efficient heap implementation by
reducing the computational overhead of finding parent and child offsets.

Link: https://lkml.kernel.org/r/20241020040200.939973-3-visitorckw@gmail.com
Signed-off-by: Kuan-Wei Chiu 
Cc: Adrian Hunter 
Cc: Arnaldo Carvalho de Melo 
Cc: Ching-Chun (Jim) Huang 
Cc: Coly Li 
Cc: Ian Rogers 
Cc: Ingo Molnar 
Cc: Jiri Olsa 
Cc: Jonathan Corbet 
Cc: Kent Overstreet 
Cc: "Liang, Kan" 
Cc: Mark Rutland 
Cc: Matthew Sakai 
Cc: Matthew Wilcox (Oracle) 
Cc: Namhyung Kim 
Cc: Peter Zijlstra 
Signed-off-by: Andrew Morton

lib/min_heap: introduce non-inline versions of min heap API functions

2024-11-06T01:12:34+00:00

Patch series "Enhance min heap API with non-inline functions and
optimizations", v2.

Add non-inline versions of the min heap API functions in lib/min_heap.c
and updates all users outside of kernel/events/core.c to use these
non-inline versions.  To mitigate the performance impact of indirect
function calls caused by the non-inline versions of the swap and compare
functions, a builtin swap has been introduced that swaps elements based on
their size.  Additionally, it micro-optimizes the efficiency of the min
heap by pre-scaling the counter, following the same approach as in
lib/sort.c.  Documentation for the min heap API has also been added to the
core-api section.


This patch (of 10):

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://lkml.kernel.org/r/20241020040200.939973-1-visitorckw@gmail.com
Link: https://lore.kernel.org/20240522161048.8d8bbc7b153b4ecd92c50666@linux-foundation.org
Link: https://lkml.kernel.org/r/20241020040200.939973-2-visitorckw@gmail.com
Signed-off-by: Kuan-Wei Chiu 
Suggested-by: Andrew Morton 
Cc: Adrian Hunter 
Cc: Arnaldo Carvalho de Melo 
Cc: Ching-Chun (Jim) Huang 
Cc: Coly Li 
Cc: Ian Rogers 
Cc: Ingo Molnar 
Cc: Jiri Olsa 
Cc: Jonathan Corbet 
Cc: Kent Overstreet 
Cc: Kuan-Wei Chiu 
Cc: "Liang, Kan" 
Cc: Mark Rutland 
Cc: Matthew Sakai 
Cc: Matthew Wilcox (Oracle) 
Cc: Namhyung Kim 
Cc: Peter Zijlstra 
Signed-off-by: Andrew Morton

lib min_heap: update min_heap_push() to use min_heap_sift_up()

2024-06-25T05:24:59+00:00

Update min_heap_push() to use min_heap_sift_up() rather than its origin
inline version.

Link: https://lkml.kernel.org/r/20240524152958.919343-14-visitorckw@gmail.com
Signed-off-by: Kuan-Wei Chiu 
Reviewed-by: Ian Rogers 
Cc: Adrian Hunter 
Cc: Alexander Shishkin 
Cc: Arnaldo Carvalho de Melo 
Cc: Bagas Sanjaya 
Cc: Brian Foster 
Cc: Ching-Chun (Jim) Huang 
Cc: Coly Li 
Cc: Ingo Molnar 
Cc: Jiri Olsa 
Cc: Kent Overstreet 
Cc: Mark Rutland 
Cc: Matthew Sakai 
Cc: Namhyung Kim 
Cc: Peter Zijlstra 
Cc: Randy Dunlap 
Signed-off-by: Andrew Morton

lib min_heap: rename min_heapify() to min_heap_sift_down()

2024-06-25T05:24:59+00:00

After adding min_heap_sift_up(), the naming convention has been adjusted
to maintain consistency with the min_heap_sift_up().  Consequently,
min_heapify() has been renamed to min_heap_sift_down().

Link: https://lkml.kernel.org/CAP-5=fVcBAxt8Mw72=NCJPRJfjDaJcqk4rjbadgouAEAHz_q1A@mail.gmail.com
Link: https://lkml.kernel.org/r/20240524152958.919343-13-visitorckw@gmail.com
Signed-off-by: Kuan-Wei Chiu 
Reviewed-by: Ian Rogers 
Cc: Adrian Hunter 
Cc: Alexander Shishkin 
Cc: Arnaldo Carvalho de Melo 
Cc: Bagas Sanjaya 
Cc: Brian Foster 
Cc: Ching-Chun (Jim) Huang 
Cc: Coly Li 
Cc: Ingo Molnar 
Cc: Jiri Olsa 
Cc: Kent Overstreet 
Cc: Mark Rutland 
Cc: Matthew Sakai 
Cc: Namhyung Kim 
Cc: Peter Zijlstra 
Cc: Randy Dunlap 
Signed-off-by: Andrew Morton

lib min_heap: update min_heap_push() and min_heap_pop() to return bool values

2024-06-25T05:24:59+00:00

Modify the min_heap_push() and min_heap_pop() to return a boolean value. 
They now return false when the operation fails and true when it succeeds.

Link: https://lkml.kernel.org/r/20240524152958.919343-12-visitorckw@gmail.com
Signed-off-by: Kuan-Wei Chiu 
Reviewed-by: Ian Rogers 
Cc: Adrian Hunter 
Cc: Alexander Shishkin 
Cc: Arnaldo Carvalho de Melo 
Cc: Bagas Sanjaya 
Cc: Brian Foster 
Cc: Ching-Chun (Jim) Huang 
Cc: Coly Li 
Cc: Ingo Molnar 
Cc: Jiri Olsa 
Cc: Kent Overstreet 
Cc: Mark Rutland 
Cc: Matthew Sakai 
Cc: Namhyung Kim 
Cc: Peter Zijlstra 
Cc: Randy Dunlap 
Signed-off-by: Andrew Morton

lib min_heap: add min_heap_del()

2024-06-25T05:24:58+00:00

Add min_heap_del() to delete the element at index 'idx' in the heap.

Link: https://lkml.kernel.org/r/20240524152958.919343-11-visitorckw@gmail.com
Signed-off-by: Kuan-Wei Chiu 
Reviewed-by: Ian Rogers 
Cc: Adrian Hunter 
Cc: Alexander Shishkin 
Cc: Arnaldo Carvalho de Melo 
Cc: Bagas Sanjaya 
Cc: Brian Foster 
Cc: Ching-Chun (Jim) Huang 
Cc: Coly Li 
Cc: Ingo Molnar 
Cc: Jiri Olsa 
Cc: Kent Overstreet 
Cc: Mark Rutland 
Cc: Matthew Sakai 
Cc: Namhyung Kim 
Cc: Peter Zijlstra 
Cc: Randy Dunlap 
Signed-off-by: Andrew Morton

lib min_heap: add min_heap_sift_up()

2024-06-25T05:24:58+00:00

Add min_heap_sift_up() to sift up the element at index 'idx' in the
heap.

Link: https://lkml.kernel.org/r/20240524152958.919343-10-visitorckw@gmail.com
Signed-off-by: Kuan-Wei Chiu 
Reviewed-by: Ian Rogers 
Cc: Adrian Hunter 
Cc: Alexander Shishkin 
Cc: Arnaldo Carvalho de Melo 
Cc: Bagas Sanjaya 
Cc: Brian Foster 
Cc: Ching-Chun (Jim) Huang 
Cc: Coly Li 
Cc: Ingo Molnar 
Cc: Jiri Olsa 
Cc: Kent Overstreet 
Cc: Mark Rutland 
Cc: Matthew Sakai 
Cc: Namhyung Kim 
Cc: Peter Zijlstra 
Cc: Randy Dunlap 
Signed-off-by: Andrew Morton

lib min_heap: add args for min_heap_callbacks

2024-06-25T05:24:58+00:00

Add a third parameter 'args' for the 'less' and 'swp' functions in the
'struct min_heap_callbacks'.  This additional parameter allows these
comparison and swap functions to handle extra arguments when necessary.

Link: https://lkml.kernel.org/r/20240524152958.919343-9-visitorckw@gmail.com
Signed-off-by: Kuan-Wei Chiu 
Reviewed-by: Ian Rogers 
Cc: Adrian Hunter 
Cc: Alexander Shishkin 
Cc: Arnaldo Carvalho de Melo 
Cc: Bagas Sanjaya 
Cc: Brian Foster 
Cc: Ching-Chun (Jim) Huang 
Cc: Coly Li 
Cc: Ingo Molnar 
Cc: Jiri Olsa 
Cc: Kent Overstreet 
Cc: Mark Rutland 
Cc: Matthew Sakai 
Cc: Namhyung Kim 
Cc: Peter Zijlstra 
Cc: Randy Dunlap 
Signed-off-by: Andrew Morton

lib min_heap: add min_heap_full()

2024-06-25T05:24:58+00:00

Add min_heap_full() which returns a boolean value indicating whether the
heap has reached its maximum capacity.

Link: https://lkml.kernel.org/r/20240524152958.919343-8-visitorckw@gmail.com
Signed-off-by: Kuan-Wei Chiu 
Reviewed-by: Ian Rogers 
Cc: Adrian Hunter 
Cc: Alexander Shishkin 
Cc: Arnaldo Carvalho de Melo 
Cc: Bagas Sanjaya 
Cc: Brian Foster 
Cc: Ching-Chun (Jim) Huang 
Cc: Coly Li 
Cc: Ingo Molnar 
Cc: Jiri Olsa 
Cc: Kent Overstreet 
Cc: Mark Rutland 
Cc: Matthew Sakai 
Cc: Namhyung Kim 
Cc: Peter Zijlstra 
Cc: Randy Dunlap 
Signed-off-by: Andrew Morton