[PATCH 0/2] lib/sort: Clean up sort_nonatomic() and sort_r_nonatomic()

[PATCH 0/2] lib/sort: Clean up sort_nonatomic() and sort_r_nonatomic()

[Kuan-Wei Chiu]

Remove the sort_nonatomic() and sort_r_nonatomic() APIs from the kernel
library.

Currently, the arm-smmu-v3 driver is the sole in-tree user of 
sort_nonatomic(). Because the array size being sorted is small in
practice, there is no real risk of triggering a soft lockup. Therefore,
the periodic cond_resched() calls provided by the _nonatomic variant
are unnecessary.

With the only in-tree user updated, the _nonatomic APIs are no longer
needed anywhere in the kernel. Removing them effectively drops the
wrapper function and eliminates the may_schedule branch from the
innermost loop of the core sorting logic, slightly simplifying the code.

Kuan-Wei Chiu (2):
  iommu/arm-smmu-v3: Replace sort_nonatomic() with sort()
  Revert "lib/sort.c: add _nonatomic() variants with cond_resched()"

 drivers/iommu/arm/arm-smmu-v3/arm-smmu-v3.c |   6 +-
 include/linux/sort.h                        |  11 --
 lib/sort.c                                  | 110 ++++++--------------
 3 files changed, 34 insertions(+), 93 deletions(-)

-- 
2.55.0.508.g3f0d502094-goog

[PATCH 1/2] iommu/arm-smmu-v3: Replace sort_nonatomic() with sort()

[Kuan-Wei Chiu]

The number of master->num_streams per master device is typically very
small in practice. Sorting this array takes a very small amount of
time, so there is no practical risk of triggering a soft lockup that
would necessitate calling cond_resched() during the sort.

Replace sort_nonatomic() with the standard sort(). Since this is the
only remaining in-tree caller of sort_nonatomic(), this change paves
the way to eventually remove the unused sort_nonatomic() API from the
core library.

Signed-off-by: Kuan-Wei Chiu <visitorckw@gmail.com>
---
Build-tested only.

I'm not really familiar with this driver or smmu internals.
Based on my limited knowledge, master->num_streams should be small
enough to safely switch from sort_nonatomic() to sort(), but I could be
wrong. 

Please review carefully and let me know if there are any cases where
num_streams could actually be large enough to cause issues.

 drivers/iommu/arm/arm-smmu-v3/arm-smmu-v3.c | 6 +++---
 1 file changed, 3 insertions(+), 3 deletions(-)

diff --git a/drivers/iommu/arm/arm-smmu-v3/arm-smmu-v3.c b/drivers/iommu/arm/arm-smmu-v3/arm-smmu-v3.c
index a10affb483a4..dcb6be2df95e 100644
--- a/drivers/iommu/arm/arm-smmu-v3/arm-smmu-v3.c
+++ b/drivers/iommu/arm/arm-smmu-v3/arm-smmu-v3.c
@@ -4047,9 +4047,9 @@ static int arm_smmu_insert_master(struct arm_smmu_device *smmu,
 	}
 
 	/* Put the ids into order for sorted to_merge/to_unref arrays */
-	sort_nonatomic(master->streams, master->num_streams,
-		       sizeof(master->streams[0]), arm_smmu_stream_id_cmp,
-		       NULL);
+	sort(master->streams, master->num_streams,
+	     sizeof(master->streams[0]), arm_smmu_stream_id_cmp,
+	     NULL);
 
 	mutex_lock(&smmu->streams_mutex);
 	for (i = 0; i < fwspec->num_ids; i++) {
-- 
2.55.0.508.g3f0d502094-goog

[PATCH 2/2] Revert "lib/sort.c: add _nonatomic() variants with cond_resched()"

[Kuan-Wei Chiu]

This reverts commit e2a33a2a3258794891cdd6ca4b1318da6594d157.

After replacing the only in-tree user of sort_nonatomic() in the
arm-smmu-v3 driver with the standard sort(), the _nonatomic() variants
are no longer used anywhere in the kernel.

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>
---
 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.508.g3f0d502094-goog

Re: [PATCH 0/2] lib/sort: Clean up sort_nonatomic() and sort_r_nonatomic()

[Kuan-Wei Chiu]

+Cc maintainers/reviewers of kernel/trace/bpf_trace.c

On Thu, Jul 30, 2026 at 06:12:14PM +0000, Kuan-Wei Chiu wrote:
> Remove the sort_nonatomic() and sort_r_nonatomic() APIs from the kernel
> library.
> 
> Currently, the arm-smmu-v3 driver is the sole in-tree user of 
> sort_nonatomic(). Because the array size being sorted is small in

I just realized that I missed another in-tree user: sort_r_nonatomic()
is actually being used in kernel/trace/bpf_trace.c.

Looking at the bpf code, the array size there is bounded by
MAX_TRACING_MULTI_CNT, which is set to (1u << 20). I guess sorting an
array of this size in a single go could potentially cause scheduling
latency spikes on certain configurations if we don't yield the cpu.

Because of this, it seems my proposal to completely remove
sort_r_nonatomic() and sort_nonatomic() from the core library was
premature.

Please let me know if you think otherwise, or if there is any
alternative approach for check_dup_ids() that would allow us to safely
drop sort_r_nonatomic(). Otherwise, please disregard this series.

Regards,
Kuan-Wei

> practice, there is no real risk of triggering a soft lockup. Therefore,
> the periodic cond_resched() calls provided by the _nonatomic variant
> are unnecessary.
> 
> With the only in-tree user updated, the _nonatomic APIs are no longer
> needed anywhere in the kernel. Removing them effectively drops the
> wrapper function and eliminates the may_schedule branch from the
> innermost loop of the core sorting logic, slightly simplifying the code.
> 
> Kuan-Wei Chiu (2):
>   iommu/arm-smmu-v3: Replace sort_nonatomic() with sort()
>   Revert "lib/sort.c: add _nonatomic() variants with cond_resched()"
> 
>  drivers/iommu/arm/arm-smmu-v3/arm-smmu-v3.c |   6 +-
>  include/linux/sort.h                        |  11 --
>  lib/sort.c                                  | 110 ++++++--------------
>  3 files changed, 34 insertions(+), 93 deletions(-)
> 
> -- 
> 2.55.0.508.g3f0d502094-goog
>