Skip to contentSkip to conversation

lib/list_sort: introduce list_sort_nonatomic() and remove dummy cmp() calls

PATCH In review Kuan-Wei Chiu 4 participants 12 messages Mar 15 – Mar 17

Subsystems (3)
lore
Share & tools
lore
#0 lore raw

PATCH 1/1 lib/list_sort: introduce list_sort_nonatomic() and remove dummy cmp() calls

Historically, list_sort() implemented a hack in merge_final():

    if (unlikely(!++count))
        cmp(priv, b, b);

This was designed specifically so that callers could periodically invoke cond_resched() within their comparison functions when merging highly unbalanced lists.

However, an audit of the kernel tree reveals that only fs/ubifs/ relies on this mechanism. For the vast majority of list_sort() users (such as block layer IO schedulers and file systems), this results in completely wasted function calls. In the worst-case scenario (merging an already sorted list where 'a' is exhausted quickly), this results in approximately (N/2)/256 unnecessary cmp() calls.

To clean up this API while ensuring behavior compatibility:
1. Introduce list_sort_nonatomic(), which explicitly calls cond_resched() internally when count overflows.
2. Remove the dummy cmp(priv, b, b) fallback for standard list_sort(), saving unnecessary function calls and improving determinism.
3. Convert the sole user (fs/ubifs/) to the new API.

Note that ubifs still maintains cond_resched() inside its own comparison functions. This patch does not alter the frequency or timing of those scheduling points, guaranteeing no regressions for ubifs, while benefiting all other kernel users.

---
 fs/ubifs/gc.c             |   4 +-
 fs/ubifs/replay.c         |   2 +-
 include/linux/list_sort.h |   3 +
 lib/list_sort.c           | 166 +++++++++++++++++++++-----------------
 4 files changed, 100 insertions(+), 75 deletions(-)
fs/ubifs/gc.c +2 -2
index 0bf08b7755b8..dcc5742210b0 100644
@@ -277,8 +277,8 @@ static int sort_nodes(struct ubifs_info *c, struct ubifs_scan_leb *sleb,
 	}
 
 	/* Sort data and non-data nodes */
-	list_sort(c, &sleb->nodes, &data_nodes_cmp);
-	list_sort(c, nondata, &nondata_nodes_cmp);
+	list_sort_nonatomic(c, &sleb->nodes, &data_nodes_cmp);
+	list_sort_nonatomic(c, nondata, &nondata_nodes_cmp);
 
 	err = dbg_check_data_nodes_order(c, &sleb->nodes);
 	if (err)
fs/ubifs/replay.c +1 -1
index a9a568f4a868..ad03dd106a54 100644
@@ -329,7 +329,7 @@ static int apply_replay_list(struct ubifs_info *c)
 	struct replay_entry *r;
 	int err;
 
-	list_sort(c, &c->replay_list, &replay_entries_cmp);
+	list_sort_nonatomic(c, &c->replay_list, &replay_entries_cmp);
 
 	list_for_each_entry(r, &c->replay_list, list) {
 		cond_resched();
include/linux/list_sort.h +3 -0
index 453105f74e05..f7af29073d48 100644
@@ -11,4 +11,7 @@ typedef int __attribute__((nonnull(2,3))) (*list_cmp_func_t)(void *,
 
 __attribute__((nonnull(2,3)))
 void list_sort(void *priv, struct list_head *head, list_cmp_func_t cmp);
+
+__attribute__((nonnull(2, 3)))
+void list_sort_nonatomic(void *priv, struct list_head *head, list_cmp_func_t cmp);
 #endif
lib/list_sort.c +94 -72

198 lines not on this page · raw message

Signature · 1 line
2.53.0.851.ga537e3e6e9-goog
#1 lore raw

----- Ursprüngliche Mail -----

Quoted 9 lines

Von: "Kuan-Wei Chiu" <[email protected]> Historically, list_sort() implemented a hack in merge_final():

   if (unlikely(!++count))
       cmp(priv, b, b);

This was designed specifically so that callers could periodically invoke cond_resched() within their comparison functions when merging highly unbalanced lists.

Quoted 6 lines

However, an audit of the kernel tree reveals that only fs/ubifs/ relies on this mechanism. For the vast majority of list_sort() users (such as block layer IO schedulers and file systems), this results in completely wasted function calls. In the worst-case scenario (merging an already sorted list where 'a' is exhausted quickly), this results in approximately (N/2)/256 unnecessary cmp() calls.

Why isn't this a problem for other users of list_sort()? Are the lists they sort guaranteed to be short?

Or did nobody test hard enough on slow machines without preempt? ;-)

Thanks,
//richard

#2 lore raw

Hi Richard,

Quoted 17 lines · Richard Weinberger

----- Ursprüngliche Mail -----

Quoted 9 lines

Von: "Kuan-Wei Chiu" <[email protected]> Historically, list_sort() implemented a hack in merge_final():

   if (unlikely(!++count))
       cmp(priv, b, b);

This was designed specifically so that callers could periodically invoke cond_resched() within their comparison functions when merging highly unbalanced lists.

Quoted 6 lines

However, an audit of the kernel tree reveals that only fs/ubifs/ relies on this mechanism. For the vast majority of list_sort() users (such as block layer IO schedulers and file systems), this results in completely wasted function calls. In the worst-case scenario (merging an already sorted list where 'a' is exhausted quickly), this results in approximately (N/2)/256 unnecessary cmp() calls.

Quoted 4 lines

Why isn't this a problem for other users of list_sort()? Are the lists they sort guaranteed to be short?

Or did nobody test hard enough on slow machines without preempt? ;-)

TBH, I don't really have a clear answer to that.

I tried to dig into the history. It turns out this mechanism was introduced 16 years ago in commit 835cc0c8477f ("lib: more scalable list_sort()"). The commit message explicitly mentioned both XFS and UBIFS as the intended users for this long-list workaround. However, looking at the tree back then, XFS never actually put a cond_resched() in their cmp() function. It seems UBIFS has been the sole user of this trick ever since. Given that it has been this way for 16 years, it seems other subsystems haven't really encountered any practical issues with it.

For UBIFS, this patch doesn't alter the frequency, timing, or behavior of the cond_resched() calls at all, so I am confident that this won't introduce any regressions.

Regards,
Kuan-Wei

#3 lore raw

----- Ursprüngliche Mail -----

Quoted 15 lines

Von: "Kuan-Wei Chiu" <[email protected]>

Quoted 11 lines
Quoted 6 lines

However, an audit of the kernel tree reveals that only fs/ubifs/ relies on this mechanism. For the vast majority of list_sort() users (such as block layer IO schedulers and file systems), this results in completely wasted function calls. In the worst-case scenario (merging an already sorted list where 'a' is exhausted quickly), this results in approximately (N/2)/256 unnecessary cmp() calls.

Why isn't this a problem for other users of list_sort()? Are the lists they sort guaranteed to be short?

Or did nobody test hard enough on slow machines without preempt? ;-)

TBH, I don't really have a clear answer to that.

Quoted 9 lines

I tried to dig into the history. It turns out this mechanism was introduced 16 years ago in commit 835cc0c8477f ("lib: more scalable list_sort()"). The commit message explicitly mentioned both XFS and UBIFS as the intended users for this long-list workaround. However, looking at the tree back then, XFS never actually put a cond_resched() in their cmp() function. It seems UBIFS has been the sole user of this trick ever since. Given that it has been this way for 16 years, it seems other subsystems haven't really encountered any practical issues with it.

Traditionally both UBI and UBIFS use cond_resched() heavily, my best guess is because their mostly used on tiny embedded systems where soft lockups are more likely.

Quoted 3 lines

For UBIFS, this patch doesn't alter the frequency, timing, or behavior of the cond_resched() calls at all, so I am confident that this won't introduce any regressions.

Sure. I just want to make sure I understand why UBIFS need special treatment.

Thanks,
//richard

#4 lore raw
In reply to Kuan-Wei Chiu
Quoted 9 lines · Kuan-Wei Chiu

I tried to dig into the history. It turns out this mechanism was introduced 16 years ago in commit 835cc0c8477f ("lib: more scalable list_sort()"). The commit message explicitly mentioned both XFS and UBIFS as the intended users for this long-list workaround. However, looking at the tree back then, XFS never actually put a cond_resched() in their cmp() function. It seems UBIFS has been the sole user of this trick ever since. Given that it has been this way for 16 years, it seems other subsystems haven't really encountered any practical issues with it.

.. or it wasn't even needed in the first place.

Quoted 3 lines

For UBIFS, this patch doesn't alter the frequency, timing, or behavior of the cond_resched() calls at all, so I am confident that this won't introduce any regressions.

I'd be tempted to drop the workaround and remove the cond_resched from ubifs given that entirely non-preemptible scheduling models are on their way out.

#5 lore raw

----- Ursprüngliche Mail -----

Quoted 7 lines
Quoted 3 lines

For UBIFS, this patch doesn't alter the frequency, timing, or behavior of the cond_resched() calls at all, so I am confident that this won't introduce any regressions.

I'd be tempted to drop the workaround and remove the cond_resched from ubifs given that entirely non-preemptible scheduling models are on their way out.

arm32 still has no preempt-lazy.
This is one of the biggest platforms where UBIFS is still used.

Thanks,
//richard

#6 lore raw
Quoted 11 lines · Richard Weinberger

----- Ursprüngliche Mail -----

Quoted 7 lines
Quoted 3 lines

For UBIFS, this patch doesn't alter the frequency, timing, or behavior of the cond_resched() calls at all, so I am confident that this won't introduce any regressions.

I'd be tempted to drop the workaround and remove the cond_resched from ubifs given that entirely non-preemptible scheduling models are on their way out.

arm32 still has no preempt-lazy.
This is one of the biggest platforms where UBIFS is still used.

Time to fix that if it wants to stay alive.

______________________________________________________
Linux MTD discussion mailing list
http://lists.infradead.org/mailman/listinfo/linux-mtd/

#7 lore raw
Quoted 6 lines · Christoph Hellwig
Quoted 5 lines · Richard Weinberger

----- Ursprüngliche Mail -----

Quoted 4 lines
Quoted 3 lines

For UBIFS, this patch doesn't alter the frequency, timing, or behavior of the cond_resched() calls at all, so I am confident that this won't introduce any regressions.

Quoted 9 lines
Quoted 6 lines
Quoted 3 lines

I'd be tempted to drop the workaround and remove the cond_resched from ubifs given that entirely non-preemptible scheduling models are on their way out.

arm32 still has no preempt-lazy.
This is one of the biggest platforms where UBIFS is still used.

Time to fix that if it wants to stay alive.

It seems that dropping cond_resched() right now would cause issues for UBIFS.

Given that, let's stick with current plan for now. If we reach a point in the future where it's safe to drop these scheduling points, we can always revisit this and remove then.

Regards,
Kuan-Wei

reviewer Reviewed-by on v1 1/1
#8 lore raw
In reply to Kuan-Wei Chiu
Quoted 27 lines · Kuan-Wei Chiu

Historically, list_sort() implemented a hack in merge_final():

     if (unlikely(!++count))
         cmp(priv, b, b);

This was designed specifically so that callers could periodically invoke cond_resched() within their comparison functions when merging highly unbalanced lists.

However, an audit of the kernel tree reveals that only fs/ubifs/ relies on this mechanism. For the vast majority of list_sort() users (such as block layer IO schedulers and file systems), this results in completely wasted function calls. In the worst-case scenario (merging an already sorted list where 'a' is exhausted quickly), this results in approximately (N/2)/256 unnecessary cmp() calls.

To clean up this API while ensuring behavior compatibility:
1. Introduce list_sort_nonatomic(), which explicitly calls cond_resched() internally when count overflows.
2. Remove the dummy cmp(priv, b, b) fallback for standard list_sort(), saving unnecessary function calls and improving determinism.
3. Convert the sole user (fs/ubifs/) to the new API.

Note that ubifs still maintains cond_resched() inside its own comparison functions. This patch does not alter the frequency or timing of those scheduling points, guaranteeing no regressions for ubifs, while benefiting all other kernel users.

Quoted 7 lines
---
  fs/ubifs/gc.c             |   4 +-
  fs/ubifs/replay.c         |   2 +-
  include/linux/list_sort.h |   3 +
  lib/list_sort.c           | 166 +++++++++++++++++++++-----------------
  4 files changed, 100 insertions(+), 75 deletions(-)

lgtm for UBIFS.

one small nit below.

Quoted 1 line

[...]

Quoted 37 lines
include/linux/list_sort.h +3 -0
index 453105f74e05..f7af29073d48 100644
@@ -11,4 +11,7 @@ typedef int __attribute__((nonnull(2,3))) (*list_cmp_func_t)(void *,
 
  __attribute__((nonnull(2,3)))
  void list_sort(void *priv, struct list_head *head, list_cmp_func_t cmp);
+
+__attribute__((nonnull(2, 3)))
+void list_sort_nonatomic(void *priv, struct list_head *head, list_cmp_func_t cmp);
  #endif
lib/list_sort.c +2 -1
index a310ecb7ccc0..788bfc26cf7b 100644
@@ -3,6 +3,7 @@
  #include <linux/export.h>
  #include <linux/list_sort.h>
  #include <linux/list.h>
+#include <linux/sched.h>
 
  /*
   * Returns a list organized in an intermediate format suited
@@ -47,7 +48,7 @@ static struct list_head *merge(void *priv, list_cmp_func_t cmp,
   */
  __attribute__((nonnull(2,3,4,5)))
  static void merge_final(void *priv, list_cmp_func_t cmp, struct list_head *head,
-			struct list_head *a, struct list_head *b)
+			struct list_head *a, struct list_head *b, bool may_schedule)
  {
  	struct list_head *tail = head;
  	u8 count = 0;
@@ -79,12 +80,11 @@ static void merge_final(void *priv, list_cmp_func_t cmp, struct list_head *head,
  		/*
  		 * If the merge is highly unbalanced (e.g. the input is
  		 * already sorted), this loop may run many iterations.

lib/list_sort.c static void merge_final(void *priv, list_cmp_func_t cmp, struct list_head *head, · line 87

Quoted 10 lines
lib/list_sort.c +4 -5
-		 * Continue callbacks to the client even though no
-		 * element comparison is needed, so the client's cmp()
-		 * routine can invoke cond_resched() periodically.
+		 * If may_schedule is true, periodically invoke cond_resched()
+		 * to avoid soft lockups.
  		 */
-		if (unlikely(!++count))
-			cmp(priv, b, b);
+		if (may_schedule && unlikely(!++count))
+			cond_resched();

The cond_resched() already has a judgment on whether to schedule out, so the 'count' could be removed?

Quoted 3 lines
lib/list_sort.c +0 -0
  		b->prev = tail;
  		tail = b;
  		b = b->next;
#9 lore raw

Hi Zhihao,

Quoted 36 lines · Zhihao Cheng
Quoted 27 lines · Kuan-Wei Chiu

Historically, list_sort() implemented a hack in merge_final():

     if (unlikely(!++count))
         cmp(priv, b, b);

This was designed specifically so that callers could periodically invoke cond_resched() within their comparison functions when merging highly unbalanced lists.

However, an audit of the kernel tree reveals that only fs/ubifs/ relies on this mechanism. For the vast majority of list_sort() users (such as block layer IO schedulers and file systems), this results in completely wasted function calls. In the worst-case scenario (merging an already sorted list where 'a' is exhausted quickly), this results in approximately (N/2)/256 unnecessary cmp() calls.

To clean up this API while ensuring behavior compatibility:
1. Introduce list_sort_nonatomic(), which explicitly calls cond_resched() internally when count overflows.
2. Remove the dummy cmp(priv, b, b) fallback for standard list_sort(), saving unnecessary function calls and improving determinism.
3. Convert the sole user (fs/ubifs/) to the new API.

Note that ubifs still maintains cond_resched() inside its own comparison functions. This patch does not alter the frequency or timing of those scheduling points, guaranteeing no regressions for ubifs, while benefiting all other kernel users.

Quoted 7 lines
---
  fs/ubifs/gc.c             |   4 +-
  fs/ubifs/replay.c         |   2 +-
  include/linux/list_sort.h |   3 +
  lib/list_sort.c           | 166 +++++++++++++++++++++-----------------
  4 files changed, 100 insertions(+), 75 deletions(-)
Quoted 3 lines

lgtm for UBIFS.

Thanks for your review!

Quoted 44 lines

one small nit below.

Quoted 1 line

[...]

Quoted 39 lines
include/linux/list_sort.h +3 -0
index 453105f74e05..f7af29073d48 100644
@@ -11,4 +11,7 @@ typedef int __attribute__((nonnull(2,3))) (*list_cmp_func_t)(void *,
  __attribute__((nonnull(2,3)))
  void list_sort(void *priv, struct list_head *head, list_cmp_func_t cmp);
+
+__attribute__((nonnull(2, 3)))
+void list_sort_nonatomic(void *priv, struct list_head *head, list_cmp_func_t cmp);
  #endif
lib/list_sort.c +3 -4
index a310ecb7ccc0..788bfc26cf7b 100644
@@ -3,6 +3,7 @@
  #include <linux/export.h>
  #include <linux/list_sort.h>
  #include <linux/list.h>
+#include <linux/sched.h>
  /*
   * Returns a list organized in an intermediate format suited
@@ -47,7 +48,7 @@ static struct list_head *merge(void *priv, list_cmp_func_t cmp,
   */
  __attribute__((nonnull(2,3,4,5)))
  static void merge_final(void *priv, list_cmp_func_t cmp, struct list_head *head,
-			struct list_head *a, struct list_head *b)
+			struct list_head *a, struct list_head *b, bool may_schedule)
  {
  	struct list_head *tail = head;
  	u8 count = 0;
@@ -79,12 +80,11 @@ static void merge_final(void *priv, list_cmp_func_t cmp, struct list_head *head,
  		/*
  		 * If the merge is highly unbalanced (e.g. the input is
  		 * already sorted), this loop may run many iterations.
-		 * Continue callbacks to the client even though no
-		 * element comparison is needed, so the client's cmp()
-		 * routine can invoke cond_resched() periodically.
+		 * If may_schedule is true, periodically invoke cond_resched()
Quoted 8 lines

lib/list_sort.c static void merge_final(void *priv, list_cmp_func_t cmp, struct list_head *head, · line 87

Quoted 6 lines
lib/list_sort.c +3 -2
+		 * to avoid soft lockups.
  		 */
-		if (unlikely(!++count))
-			cmp(priv, b, b);
+		if (may_schedule && unlikely(!++count))
+			cond_resched();

The cond_resched() already has a judgment on whether to schedule out, so the 'count' could be removed?

However, I think keeping the u8 count rate-limiter makes more sense here due to the overhead difference.

Evaluating unlikely(!++count) is essentially a single ALU instruction (register increment) and a zero-flag check, which has virtually zero cost. On the other hand, cond_resched() is a macro that does much more than a simple flag check. Depending on the kernel config, it often invokes __might_resched() (which reads current to check task_struct states, irq flags, etc.) and makes a call to __cond_resched(). Evaluating all of this heavy machinery on every single iteration of such a tight loop would probably introduce noticeable overhead.

Actually, your comment brings up another thought I wanted to discuss.

Since we are introducing list_sort_nonatomic(), I wonder if we should eventually move the cond_resched() out of UBIFS's cmp() functions entirely and handle it inside list_sort_nonatomic().

Right now, because the cmp() callback is inherently invoked at every step of the merge process, UBIFS ends up evaluating the cond_resched() macro every 3 or 4 pointer assignments during the main sort. While UBIFS needs to prevent soft lockups on huge lists, checking for resched at such a micro-granularity still feels excessive and likely leaves performance on the table.

I didn't make this change in the current patch because I don't have the proper UBIFS hardware/setup to benchmark the performance difference, and I wanted to keep the current scheduling frequency exactly the same to guarantee no regressions. But I'd love to hear your thoughts on whether reducing the frequency and moving it out of UBIFS's cmp() is something worth doing in the future.

Regards,
Kuan-Wei

reviewer
#10 lore raw
Quoted 116 lines · Kuan-Wei Chiu

Hi Zhihao,

Quoted 36 lines · Zhihao Cheng
Quoted 27 lines · Kuan-Wei Chiu

Historically, list_sort() implemented a hack in merge_final():

      if (unlikely(!++count))
          cmp(priv, b, b);

This was designed specifically so that callers could periodically invoke cond_resched() within their comparison functions when merging highly unbalanced lists.

However, an audit of the kernel tree reveals that only fs/ubifs/ relies on this mechanism. For the vast majority of list_sort() users (such as block layer IO schedulers and file systems), this results in completely wasted function calls. In the worst-case scenario (merging an already sorted list where 'a' is exhausted quickly), this results in approximately (N/2)/256 unnecessary cmp() calls.

To clean up this API while ensuring behavior compatibility:
1. Introduce list_sort_nonatomic(), which explicitly calls cond_resched() internally when count overflows.
2. Remove the dummy cmp(priv, b, b) fallback for standard list_sort(), saving unnecessary function calls and improving determinism.
3. Convert the sole user (fs/ubifs/) to the new API.

Note that ubifs still maintains cond_resched() inside its own comparison functions. This patch does not alter the frequency or timing of those scheduling points, guaranteeing no regressions for ubifs, while benefiting all other kernel users.

Quoted 7 lines
---
   fs/ubifs/gc.c             |   4 +-
   fs/ubifs/replay.c         |   2 +-
   include/linux/list_sort.h |   3 +
   lib/list_sort.c           | 166 +++++++++++++++++++++-----------------
   4 files changed, 100 insertions(+), 75 deletions(-)
Quoted 3 lines

lgtm for UBIFS.

Thanks for your review!

Quoted 44 lines

one small nit below.

Quoted 1 line

[...]

Quoted 39 lines
include/linux/list_sort.h +3 -0
index 453105f74e05..f7af29073d48 100644
@@ -11,4 +11,7 @@ typedef int __attribute__((nonnull(2,3))) (*list_cmp_func_t)(void *,
   __attribute__((nonnull(2,3)))
   void list_sort(void *priv, struct list_head *head, list_cmp_func_t cmp);
+
+__attribute__((nonnull(2, 3)))
+void list_sort_nonatomic(void *priv, struct list_head *head, list_cmp_func_t cmp);
   #endif
lib/list_sort.c +3 -4
index a310ecb7ccc0..788bfc26cf7b 100644
@@ -3,6 +3,7 @@
   #include <linux/export.h>
   #include <linux/list_sort.h>
   #include <linux/list.h>
+#include <linux/sched.h>
   /*
    * Returns a list organized in an intermediate format suited
@@ -47,7 +48,7 @@ static struct list_head *merge(void *priv, list_cmp_func_t cmp,
    */
   __attribute__((nonnull(2,3,4,5)))
   static void merge_final(void *priv, list_cmp_func_t cmp, struct list_head *head,
-			struct list_head *a, struct list_head *b)
+			struct list_head *a, struct list_head *b, bool may_schedule)
   {
   	struct list_head *tail = head;
   	u8 count = 0;
@@ -79,12 +80,11 @@ static void merge_final(void *priv, list_cmp_func_t cmp, struct list_head *head,
   		/*
   		 * If the merge is highly unbalanced (e.g. the input is
   		 * already sorted), this loop may run many iterations.
-		 * Continue callbacks to the client even though no
-		 * element comparison is needed, so the client's cmp()
-		 * routine can invoke cond_resched() periodically.
+		 * If may_schedule is true, periodically invoke cond_resched()
Quoted 8 lines

lib/list_sort.c static void merge_final(void *priv, list_cmp_func_t cmp, struct list_head *head, · line 87

Quoted 6 lines
lib/list_sort.c +3 -2
+		 * to avoid soft lockups.
   		 */
-		if (unlikely(!++count))
-			cmp(priv, b, b);
+		if (may_schedule && unlikely(!++count))
+			cond_resched();

The cond_resched() already has a judgment on whether to schedule out, so the 'count' could be removed?

However, I think keeping the u8 count rate-limiter makes more sense here due to the overhead difference.

Evaluating unlikely(!++count) is essentially a single ALU instruction (register increment) and a zero-flag check, which has virtually zero cost. On the other hand, cond_resched() is a macro that does much more than a simple flag check. Depending on the kernel config, it often invokes __might_resched() (which reads current to check task_struct states, irq flags, etc.) and makes a call to __cond_resched(). Evaluating all of this heavy machinery on every single iteration of such a tight loop would probably introduce noticeable overhead.

Actually, your comment brings up another thought I wanted to discuss.

Since we are introducing list_sort_nonatomic(), I wonder if we should eventually move the cond_resched() out of UBIFS's cmp() functions entirely and handle it inside list_sort_nonatomic().

Quoted 6 lines

Right now, because the cmp() callback is inherently invoked at every step of the merge process, UBIFS ends up evaluating the cond_resched() macro every 3 or 4 pointer assignments during the main sort. While UBIFS needs to prevent soft lockups on huge lists, checking for resched at such a micro-granularity still feels excessive and likely leaves performance on the table.

In my humble opinion, I don't think frequent 'cond_resched' calling will bring observable performance impact, and there are many examples in kernel hotspot paths(eg. blk_mq_prealloc_tag_set_tags/blk_rq_poll_completion/__blk_mq_alloc_rq_maps ...). For list_sort(), I prefer the aim of code cleanup is to make the code more readable. I am neutral on code cleanup for the current implementation of list_sort.

Quoted 12 lines

I didn't make this change in the current patch because I don't have the proper UBIFS hardware/setup to benchmark the performance difference, and I wanted to keep the current scheduling frequency exactly the same to guarantee no regressions. But I'd love to hear your thoughts on whether reducing the frequency and moving it out of UBIFS's cmp() is something worth doing in the future.

Regards,
Kuan-Wei
.

#11 lore raw

Hi Zhihao,

Quoted 124 lines · Zhihao Cheng
Quoted 116 lines · Kuan-Wei Chiu

Hi Zhihao,

Quoted 36 lines · Zhihao Cheng
Quoted 27 lines · Kuan-Wei Chiu

Historically, list_sort() implemented a hack in merge_final():

      if (unlikely(!++count))
          cmp(priv, b, b);

This was designed specifically so that callers could periodically invoke cond_resched() within their comparison functions when merging highly unbalanced lists.

However, an audit of the kernel tree reveals that only fs/ubifs/ relies on this mechanism. For the vast majority of list_sort() users (such as block layer IO schedulers and file systems), this results in completely wasted function calls. In the worst-case scenario (merging an already sorted list where 'a' is exhausted quickly), this results in approximately (N/2)/256 unnecessary cmp() calls.

To clean up this API while ensuring behavior compatibility:
1. Introduce list_sort_nonatomic(), which explicitly calls cond_resched() internally when count overflows.
2. Remove the dummy cmp(priv, b, b) fallback for standard list_sort(), saving unnecessary function calls and improving determinism.
3. Convert the sole user (fs/ubifs/) to the new API.

Note that ubifs still maintains cond_resched() inside its own comparison functions. This patch does not alter the frequency or timing of those scheduling points, guaranteeing no regressions for ubifs, while benefiting all other kernel users.

Quoted 7 lines
---
   fs/ubifs/gc.c             |   4 +-
   fs/ubifs/replay.c         |   2 +-
   include/linux/list_sort.h |   3 +
   lib/list_sort.c           | 166 +++++++++++++++++++++-----------------
   4 files changed, 100 insertions(+), 75 deletions(-)
Quoted 3 lines

lgtm for UBIFS.

Thanks for your review!

Quoted 44 lines

one small nit below.

Quoted 1 line

[...]

Quoted 39 lines
include/linux/list_sort.h +3 -0
index 453105f74e05..f7af29073d48 100644
@@ -11,4 +11,7 @@ typedef int __attribute__((nonnull(2,3))) (*list_cmp_func_t)(void *,
   __attribute__((nonnull(2,3)))
   void list_sort(void *priv, struct list_head *head, list_cmp_func_t cmp);
+
+__attribute__((nonnull(2, 3)))
+void list_sort_nonatomic(void *priv, struct list_head *head, list_cmp_func_t cmp);
   #endif
lib/list_sort.c +3 -4
index a310ecb7ccc0..788bfc26cf7b 100644
@@ -3,6 +3,7 @@
   #include <linux/export.h>
   #include <linux/list_sort.h>
   #include <linux/list.h>
+#include <linux/sched.h>
   /*
    * Returns a list organized in an intermediate format suited
@@ -47,7 +48,7 @@ static struct list_head *merge(void *priv, list_cmp_func_t cmp,
    */
   __attribute__((nonnull(2,3,4,5)))
   static void merge_final(void *priv, list_cmp_func_t cmp, struct list_head *head,
-			struct list_head *a, struct list_head *b)
+			struct list_head *a, struct list_head *b, bool may_schedule)
   {
   	struct list_head *tail = head;
   	u8 count = 0;
@@ -79,12 +80,11 @@ static void merge_final(void *priv, list_cmp_func_t cmp, struct list_head *head,
   		/*
   		 * If the merge is highly unbalanced (e.g. the input is
   		 * already sorted), this loop may run many iterations.
-		 * Continue callbacks to the client even though no
-		 * element comparison is needed, so the client's cmp()
-		 * routine can invoke cond_resched() periodically.
+		 * If may_schedule is true, periodically invoke cond_resched()
Quoted 8 lines

lib/list_sort.c static void merge_final(void *priv, list_cmp_func_t cmp, struct list_head *head, · line 87

Quoted 6 lines
lib/list_sort.c +3 -2
+		 * to avoid soft lockups.
   		 */
-		if (unlikely(!++count))
-			cmp(priv, b, b);
+		if (may_schedule && unlikely(!++count))
+			cond_resched();

The cond_resched() already has a judgment on whether to schedule out, so the 'count' could be removed?

However, I think keeping the u8 count rate-limiter makes more sense here due to the overhead difference.

Evaluating unlikely(!++count) is essentially a single ALU instruction (register increment) and a zero-flag check, which has virtually zero cost. On the other hand, cond_resched() is a macro that does much more than a simple flag check. Depending on the kernel config, it often invokes __might_resched() (which reads current to check task_struct states, irq flags, etc.) and makes a call to __cond_resched(). Evaluating all of this heavy machinery on every single iteration of such a tight loop would probably introduce noticeable overhead.

Actually, your comment brings up another thought I wanted to discuss.

Since we are introducing list_sort_nonatomic(), I wonder if we should eventually move the cond_resched() out of UBIFS's cmp() functions entirely and handle it inside list_sort_nonatomic().

Quoted 6 lines

Right now, because the cmp() callback is inherently invoked at every step of the merge process, UBIFS ends up evaluating the cond_resched() macro every 3 or 4 pointer assignments during the main sort. While UBIFS needs to prevent soft lockups on huge lists, checking for resched at such a micro-granularity still feels excessive and likely leaves performance on the table.

Quoted 7 lines

In my humble opinion, I don't think frequent 'cond_resched' calling will bring observable performance impact, and there are many examples in kernel hotspot paths(eg. blk_mq_prealloc_tag_set_tags/blk_rq_poll_completion/__blk_mq_alloc_rq_maps ...). For list_sort(), I prefer the aim of code cleanup is to make the code more readable. I am neutral on code cleanup for the current implementation of list_sort.

OK. Since this only affects UBIFS, if performance isn't a concern for UBIFS, I'll drop the !++count check in v2.

Additionally, I plan to remove cond_resched() from UBIFS's cmp() functions in v2 and move it directly into merge() and merge_final() inside list_sort. I think this will make the code much more readable compared to hiding the scheduling points inside the comparison callbacks.

Regards,
Kuan-Wei