[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
> 

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

[Will Deacon]

On Thu, Jul 30, 2026 at 06:12:15PM +0000, Kuan-Wei Chiu wrote:
> 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);

Makes sense to me. Nicolin, did you choose the nonatomic version
specifically?

Will

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

[Nicolin Chen]

On Sun, Aug 02, 2026 at 10:23:48AM +0100, Will Deacon wrote:
> On Thu, Jul 30, 2026 at 06:12:15PM +0000, Kuan-Wei Chiu wrote:
> > @@ -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);
> 
> Makes sense to me. Nicolin, did you choose the nonatomic version
> specifically?

It's probably rare to have a large multi-stream array, so I think
sort() would be fine.

Nicolin

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

[Robin Murphy]

On 02/08/2026 6:45 pm, Nicolin Chen wrote:
> On Sun, Aug 02, 2026 at 10:23:48AM +0100, Will Deacon wrote:
>> On Thu, Jul 30, 2026 at 06:12:15PM +0000, Kuan-Wei Chiu wrote:
>>> @@ -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);
>>
>> Makes sense to me. Nicolin, did you choose the nonatomic version
>> specifically?
> 
> It's probably rare to have a large multi-stream array, so I think
> sort() would be fine.

Yeah, probably 99% of the time the size of this array will be 1. An 
exceptional value of "large" might be something like 64 for a massive 
(non-PCI) DMA engine with separate read and write IDs per channel for no 
good reason.

If and when someone ever were to report RCU stalls here then we can 
first ask them what the heck their client device is... and unless and 
until then I wouldn't think it's worth worrying about.

Thanks,
Robin.

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

[Pranjal Shrivastava]

On Mon, Aug 03, 2026 at 01:35:52PM +0100, Robin Murphy wrote:
> On 02/08/2026 6:45 pm, Nicolin Chen wrote:
> > On Sun, Aug 02, 2026 at 10:23:48AM +0100, Will Deacon wrote:
> > > On Thu, Jul 30, 2026 at 06:12:15PM +0000, Kuan-Wei Chiu wrote:
> > > > @@ -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);
> > > 
> > > Makes sense to me. Nicolin, did you choose the nonatomic version
> > > specifically?
> > 
> > It's probably rare to have a large multi-stream array, so I think
> > sort() would be fine.
> 
> Yeah, probably 99% of the time the size of this array will be 1. An
> exceptional value of "large" might be something like 64 for a massive
> (non-PCI) DMA engine with separate read and write IDs per channel for no
> good reason.
> 
> If and when someone ever were to report RCU stalls here then we can first
> ask them what the heck their client device is... and unless and until then I
> wouldn't think it's worth worrying about.
> 

+1. Agreed, it should be fine to use sort() here..

> Thanks,
> Robin.
> 

Thanks,
Praan