From 92a8b224b833e82d286d2100432adbac8cf8a2a1 Mon Sep 17 00:00:00 2001 From: Kuan-Wei Chiu Date: Sun, 20 Oct 2024 12:01:51 +0800 Subject: lib/min_heap: introduce non-inline versions of min heap API functions 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 --- fs/bcachefs/Kconfig | 1 + 1 file changed, 1 insertion(+) (limited to 'fs/bcachefs') diff --git a/fs/bcachefs/Kconfig b/fs/bcachefs/Kconfig index 5bac803ea367..ab6c95b895b3 100644 --- a/fs/bcachefs/Kconfig +++ b/fs/bcachefs/Kconfig @@ -24,6 +24,7 @@ config BCACHEFS_FS select XXHASH select SRCU select SYMBOLIC_ERRNAME + select MIN_HEAP help The bcachefs filesystem - a modern, copy on write filesystem, with support for multiple devices, compression, checksumming, etc. -- cgit v1.2.3 From 06ce25145bb864e5d948c4bc7e35bdb460a4e597 Mon Sep 17 00:00:00 2001 From: Kuan-Wei Chiu Date: Sun, 20 Oct 2024 12:01:58 +0800 Subject: bcachefs: clean up duplicate min_heap_callbacks declarations Refactor the bcachefs code to remove multiple redundant declarations of min_heap_callbacks, ensuring that each unique declaration appears only once. Link: https://lore.kernel.org/20241017095520.GV16066@noisy.programming.kicks-ass.net Link: https://lkml.kernel.org/r/20241020040200.939973-9-visitorckw@gmail.com Signed-off-by: Kuan-Wei Chiu Suggested-by: Peter Zijlstra 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 Signed-off-by: Andrew Morton --- fs/bcachefs/clock.c | 19 +++++-------------- fs/bcachefs/ec.c | 19 +++++-------------- 2 files changed, 10 insertions(+), 28 deletions(-) (limited to 'fs/bcachefs') diff --git a/fs/bcachefs/clock.c b/fs/bcachefs/clock.c index 1d6b691e8da6..1fcfcb5fd44f 100644 --- a/fs/bcachefs/clock.c +++ b/fs/bcachefs/clock.c @@ -22,13 +22,13 @@ static inline void io_timer_swp(void *l, void *r, void __always_unused *args) swap(*_l, *_r); } +static const struct min_heap_callbacks callbacks = { + .less = io_timer_cmp, + .swp = io_timer_swp, +}; + void bch2_io_timer_add(struct io_clock *clock, struct io_timer *timer) { - const struct min_heap_callbacks callbacks = { - .less = io_timer_cmp, - .swp = io_timer_swp, - }; - spin_lock(&clock->timer_lock); if (time_after_eq64((u64) atomic64_read(&clock->now), timer->expire)) { @@ -48,11 +48,6 @@ out: void bch2_io_timer_del(struct io_clock *clock, struct io_timer *timer) { - const struct min_heap_callbacks callbacks = { - .less = io_timer_cmp, - .swp = io_timer_swp, - }; - spin_lock(&clock->timer_lock); for (size_t i = 0; i < clock->timers.nr; i++) @@ -142,10 +137,6 @@ void bch2_kthread_io_clock_wait(struct io_clock *clock, static struct io_timer *get_expired_timer(struct io_clock *clock, u64 now) { struct io_timer *ret = NULL; - const struct min_heap_callbacks callbacks = { - .less = io_timer_cmp, - .swp = io_timer_swp, - }; if (clock->timers.nr && time_after_eq64(now, clock->timers.data[0]->expire)) { diff --git a/fs/bcachefs/ec.c b/fs/bcachefs/ec.c index 749dcf368841..6094afb0c6be 100644 --- a/fs/bcachefs/ec.c +++ b/fs/bcachefs/ec.c @@ -1057,6 +1057,11 @@ static inline void ec_stripes_heap_swap(void *l, void *r, void *h) ec_stripes_heap_set_backpointer(_h, j); } +static const struct min_heap_callbacks callbacks = { + .less = ec_stripes_heap_cmp, + .swp = ec_stripes_heap_swap, +}; + static void heap_verify_backpointer(struct bch_fs *c, size_t idx) { ec_stripes_heap *h = &c->ec_stripes_heap; @@ -1069,11 +1074,6 @@ static void heap_verify_backpointer(struct bch_fs *c, size_t idx) void bch2_stripes_heap_del(struct bch_fs *c, struct stripe *m, size_t idx) { - const struct min_heap_callbacks callbacks = { - .less = ec_stripes_heap_cmp, - .swp = ec_stripes_heap_swap, - }; - mutex_lock(&c->ec_stripes_heap_lock); heap_verify_backpointer(c, idx); @@ -1084,11 +1084,6 @@ void bch2_stripes_heap_del(struct bch_fs *c, void bch2_stripes_heap_insert(struct bch_fs *c, struct stripe *m, size_t idx) { - const struct min_heap_callbacks callbacks = { - .less = ec_stripes_heap_cmp, - .swp = ec_stripes_heap_swap, - }; - mutex_lock(&c->ec_stripes_heap_lock); BUG_ON(min_heap_full(&c->ec_stripes_heap)); @@ -1107,10 +1102,6 @@ void bch2_stripes_heap_insert(struct bch_fs *c, void bch2_stripes_heap_update(struct bch_fs *c, struct stripe *m, size_t idx) { - const struct min_heap_callbacks callbacks = { - .less = ec_stripes_heap_cmp, - .swp = ec_stripes_heap_swap, - }; ec_stripes_heap *h = &c->ec_stripes_heap; bool do_deletes; size_t i; -- cgit v1.2.3 From 75e849f3d0972e28d53fcfb540593c699a61c095 Mon Sep 17 00:00:00 2001 From: Kuan-Wei Chiu Date: Sun, 20 Oct 2024 12:01:59 +0800 Subject: bcachefs: update min_heap_callbacks to use default builtin swap Replace the swp function pointer in the min_heap_callbacks of bcachefs with NULL, allowing direct usage of the default builtin swap implementation. This modification simplifies the code and improves performance by removing unnecessary function indirection. Link: https://lkml.kernel.org/r/20241020040200.939973-10-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 --- fs/bcachefs/clock.c | 10 +--------- 1 file changed, 1 insertion(+), 9 deletions(-) (limited to 'fs/bcachefs') diff --git a/fs/bcachefs/clock.c b/fs/bcachefs/clock.c index 1fcfcb5fd44f..1f8e035d7119 100644 --- a/fs/bcachefs/clock.c +++ b/fs/bcachefs/clock.c @@ -14,17 +14,9 @@ static inline bool io_timer_cmp(const void *l, const void *r, void __always_unus return (*_l)->expire < (*_r)->expire; } -static inline void io_timer_swp(void *l, void *r, void __always_unused *args) -{ - struct io_timer **_l = (struct io_timer **)l; - struct io_timer **_r = (struct io_timer **)r; - - swap(*_l, *_r); -} - static const struct min_heap_callbacks callbacks = { .less = io_timer_cmp, - .swp = io_timer_swp, + .swp = NULL, }; void bch2_io_timer_add(struct io_clock *clock, struct io_timer *timer) -- cgit v1.2.3