* [PATCH v2 1/2] bpf: Replace sort_r_nonatomic() with sort_r() in check_dup_ids()
2026-09-10 16:52 [PATCH v2 0/2] lib/sort: Clean up sort_nonatomic() and sort_r_nonatomic() Kuan-Wei Chiu
@ 2026-09-10 16:52 ` Kuan-Wei Chiu
2026-09-11 8:36 ` Jiri Olsa
2026-09-10 16:52 ` [PATCH v2 2/2] Revert "lib/sort.c: add _nonatomic() variants with cond_resched()" Kuan-Wei Chiu
1 sibling, 1 reply; 4+ messages in thread
From: Kuan-Wei Chiu @ 2026-09-10 16:52 UTC (permalink / raw)
To: song, ast, daniel, andrii, eddyz87, memxor, kpsingh, matt,
rostedt, mhiramat, akpm
Cc: jolsa, ihor.solodrai, martin.lau, yonghong.song, emil,
mathieu.desnoyers, hch, jserv, eleanor15x, marscheng,
linux-kernel, bpf, Kuan-Wei Chiu
bpf_kprobe_multi_link_attach() in the same file has been using sort_r()
under the exact same limit (1U << 20) for 4 years without issues.
Switch check_dup_ids() from sort_r_nonatomic() to sort_r() to match it.
This removes the last in-tree user of sort_r_nonatomic(), allowing the
unused _nonatomic() sort variants to be dropped from the core library.
Signed-off-by: Kuan-Wei Chiu <visitorckw@gmail.com>
---
Build test only
kernel/trace/bpf_trace.c | 2 +-
1 file changed, 1 insertion(+), 1 deletion(-)
diff --git a/kernel/trace/bpf_trace.c b/kernel/trace/bpf_trace.c
index 29260951aa87..1d7e73ddbafb 100644
--- a/kernel/trace/bpf_trace.c
+++ b/kernel/trace/bpf_trace.c
@@ -3826,7 +3826,7 @@ static int check_dup_ids(u32 *ids, u64 *cookies, u32 cnt)
* and check it for duplicates. The ids and cookies arrays
* are left sorted.
*/
- sort_r_nonatomic(ids, cnt, sizeof(ids[0]), ids_cmp_r, ids_swap_r, data);
+ sort_r(ids, cnt, sizeof(ids[0]), ids_cmp_r, ids_swap_r, data);
for (int i = 1; i < cnt; i++) {
if (ids[i] == ids[i - 1]) {
--
2.55.0.1003.g10538fe699-goog
^ permalink raw reply [flat|nested] 4+ messages in thread* [PATCH v2 2/2] Revert "lib/sort.c: add _nonatomic() variants with cond_resched()"
2026-09-10 16:52 [PATCH v2 0/2] lib/sort: Clean up sort_nonatomic() and sort_r_nonatomic() Kuan-Wei Chiu
2026-09-10 16:52 ` [PATCH v2 1/2] bpf: Replace sort_r_nonatomic() with sort_r() in check_dup_ids() Kuan-Wei Chiu
@ 2026-09-10 16:52 ` Kuan-Wei Chiu
1 sibling, 0 replies; 4+ messages in thread
From: Kuan-Wei Chiu @ 2026-09-10 16:52 UTC (permalink / raw)
To: song, ast, daniel, andrii, eddyz87, memxor, kpsingh, matt,
rostedt, mhiramat, akpm
Cc: jolsa, ihor.solodrai, martin.lau, yonghong.song, emil,
mathieu.desnoyers, hch, jserv, eleanor15x, marscheng,
linux-kernel, bpf, Kuan-Wei Chiu
This reverts commit e2a33a2a3258794891cdd6ca4b1318da6594d157.
With no remaining users in the kernel tree, remove sort_nonatomic() and
sort_r_nonatomic() to clean up dead code. This effectively drops the
wrapper function __sort_r() and eliminates the may_schedule branch and
cond_resched() call from the inner loop of the core sorting routine,
slightly simplifying and optimizing the code.
Signed-off-by: Kuan-Wei Chiu <visitorckw@gmail.com>
---
Build test only
include/linux/sort.h | 11 -----
lib/sort.c | 110 ++++++++++++-------------------------------
2 files changed, 31 insertions(+), 90 deletions(-)
diff --git a/include/linux/sort.h b/include/linux/sort.h
index c01ef804a0eb..871775978af0 100644
--- a/include/linux/sort.h
+++ b/include/linux/sort.h
@@ -23,15 +23,4 @@ void sort(void *base, size_t num, size_t size,
cmp_func_t cmp_func,
swap_func_t swap_func);
-/* Versions that periodically call cond_resched(): */
-
-void sort_r_nonatomic(void *base, size_t num, size_t size,
- cmp_r_func_t cmp_func,
- swap_r_func_t swap_func,
- const void *priv);
-
-void sort_nonatomic(void *base, size_t num, size_t size,
- cmp_func_t cmp_func,
- swap_func_t swap_func);
-
#endif
diff --git a/lib/sort.c b/lib/sort.c
index 52363995ccc5..8e73dc55476b 100644
--- a/lib/sort.c
+++ b/lib/sort.c
@@ -186,13 +186,36 @@ static size_t parent(size_t i, unsigned int lsbit, size_t size)
return i / 2;
}
-#include <linux/sched.h>
-
-static void __sort_r(void *base, size_t num, size_t size,
- cmp_r_func_t cmp_func,
- swap_r_func_t swap_func,
- const void *priv,
- bool may_schedule)
+/**
+ * sort_r - sort an array of elements
+ * @base: pointer to data to sort
+ * @num: number of elements
+ * @size: size of each element
+ * @cmp_func: pointer to comparison function
+ * @swap_func: pointer to swap function or NULL
+ * @priv: third argument passed to comparison function
+ *
+ * This function does a heapsort on the given array. You may provide
+ * a swap_func function if you need to do something more than a memory
+ * copy (e.g. fix up pointers or auxiliary data), but the built-in swap
+ * avoids a slow retpoline and so is significantly faster.
+ *
+ * The comparison function must adhere to specific mathematical
+ * properties to ensure correct and stable sorting:
+ * - Antisymmetry: cmp_func(a, b) must return the opposite sign of
+ * cmp_func(b, a).
+ * - Transitivity: if cmp_func(a, b) <= 0 and cmp_func(b, c) <= 0, then
+ * cmp_func(a, c) <= 0.
+ *
+ * Sorting time is O(n log n) both on average and worst-case. While
+ * quicksort is slightly faster on average, it suffers from exploitable
+ * O(n*n) worst-case behavior and extra memory requirements that make
+ * it less suitable for kernel use.
+ */
+void sort_r(void *base, size_t num, size_t size,
+ cmp_r_func_t cmp_func,
+ swap_r_func_t swap_func,
+ const void *priv)
{
/* pre-scale counters for performance */
size_t n = num * size, a = (num/2) * size;
@@ -263,9 +286,6 @@ static void __sort_r(void *base, size_t num, size_t size,
b = parent(b, lsbit, size);
do_swap(base + b, base + c, size, swap_func, priv);
}
-
- if (may_schedule)
- cond_resched();
}
n -= size;
@@ -273,63 +293,8 @@ static void __sort_r(void *base, size_t num, size_t size,
if (n == size * 2 && do_cmp(base, base + size, cmp_func, priv) > 0)
do_swap(base, base + size, size, swap_func, priv);
}
-
-/**
- * sort_r - sort an array of elements
- * @base: pointer to data to sort
- * @num: number of elements
- * @size: size of each element
- * @cmp_func: pointer to comparison function
- * @swap_func: pointer to swap function or NULL
- * @priv: third argument passed to comparison function
- *
- * This function does a heapsort on the given array. You may provide
- * a swap_func function if you need to do something more than a memory
- * copy (e.g. fix up pointers or auxiliary data), but the built-in swap
- * avoids a slow retpoline and so is significantly faster.
- *
- * The comparison function must adhere to specific mathematical
- * properties to ensure correct and stable sorting:
- * - Antisymmetry: cmp_func(a, b) must return the opposite sign of
- * cmp_func(b, a).
- * - Transitivity: if cmp_func(a, b) <= 0 and cmp_func(b, c) <= 0, then
- * cmp_func(a, c) <= 0.
- *
- * Sorting time is O(n log n) both on average and worst-case. While
- * quicksort is slightly faster on average, it suffers from exploitable
- * O(n*n) worst-case behavior and extra memory requirements that make
- * it less suitable for kernel use.
- */
-void sort_r(void *base, size_t num, size_t size,
- cmp_r_func_t cmp_func,
- swap_r_func_t swap_func,
- const void *priv)
-{
- __sort_r(base, num, size, cmp_func, swap_func, priv, false);
-}
EXPORT_SYMBOL(sort_r);
-/**
- * sort_r_nonatomic - sort an array of elements, with cond_resched
- * @base: pointer to data to sort
- * @num: number of elements
- * @size: size of each element
- * @cmp_func: pointer to comparison function
- * @swap_func: pointer to swap function or NULL
- * @priv: third argument passed to comparison function
- *
- * Same as sort_r, but preferred for larger arrays as it does a periodic
- * cond_resched().
- */
-void sort_r_nonatomic(void *base, size_t num, size_t size,
- cmp_r_func_t cmp_func,
- swap_r_func_t swap_func,
- const void *priv)
-{
- __sort_r(base, num, size, cmp_func, swap_func, priv, true);
-}
-EXPORT_SYMBOL(sort_r_nonatomic);
-
void sort(void *base, size_t num, size_t size,
cmp_func_t cmp_func,
swap_func_t swap_func)
@@ -339,19 +304,6 @@ void sort(void *base, size_t num, size_t size,
.swap = swap_func,
};
- return __sort_r(base, num, size, _CMP_WRAPPER, SWAP_WRAPPER, &w, false);
+ return sort_r(base, num, size, _CMP_WRAPPER, SWAP_WRAPPER, &w);
}
EXPORT_SYMBOL(sort);
-
-void sort_nonatomic(void *base, size_t num, size_t size,
- cmp_func_t cmp_func,
- swap_func_t swap_func)
-{
- struct wrapper w = {
- .cmp = cmp_func,
- .swap = swap_func,
- };
-
- return __sort_r(base, num, size, _CMP_WRAPPER, SWAP_WRAPPER, &w, true);
-}
-EXPORT_SYMBOL(sort_nonatomic);
--
2.55.0.1003.g10538fe699-goog
^ permalink raw reply [flat|nested] 4+ messages in thread