[PATCH v3 0/2] lib/list_sort: Clean up list_sort() scheduling workarounds

[PATCH v3 0/2] lib/list_sort: Clean up list_sort() scheduling workarounds

[Kuan-Wei Chiu]

Historically, list_sort() included a hack in merge_final() that
periodically invoked dummy cmp(priv, b, b) calls when merging highly
unbalanced lists. This allowed the caller to invoke cond_resched()
within their comparison callbacks to avoid soft lockups. 

However, an audit of the kernel tree shows that fs/ubifs/ has been the
sole user of this mechanism. For all other generic list_sort() users,
this results in wasted function calls and unnecessary overhead in a
tight loop.

Recent discussions and code inspection confirmed that the lists being
sorted in UBIFS are bounded in size (a few thousand elements at most),
and the comparison functions are extremely lightweight. Therefore,
UBIFS does not actually need to rely on this mechanism.
---
Changes in v3:
- Abandoned the idea of introducing a new list_sort_nonatomic() API.
- Removed the dummy cmp() hack.
- Dropped the cond_resched() calls from UBIFS.
- Split the changes into a 2-patch series.
- Dropped Zhihao Cheng's Reviewed-by tag due to the fundamental change.

Changes in v2:
- Dropped the u8 count rate-limiter in merge() and merge_final().
- Removed cond_resched() calls from UBIFS comparison callbacks.

v2: https://lore.kernel.org/lkml/20260317165905.1482256-1-visitorckw@gmail.com/
v1: https://lore.kernel.org/lkml/20260315193900.218737-1-visitorckw@gmail.com/

Kuan-Wei Chiu (2):
  ubifs: Remove unnecessary cond_resched() from list_sort() compare
  lib/list_sort: Remove dummy cmp() calls to speed up merge_final()

 fs/ubifs/gc.c     | 2 --
 fs/ubifs/replay.c | 1 -
 lib/list_sort.c   | 9 ---------
 3 files changed, 12 deletions(-)

-- 
2.53.0.959.g497ff81fa9-goog


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

[PATCH v3 1/2] ubifs: Remove unnecessary cond_resched() from list_sort() compare

[Kuan-Wei Chiu]

Historically, UBIFS embedded cond_resched() calls inside its
list_sort() comparison callbacks (data_nodes_cmp, nondata_nodes_cmp,
and replay_entries_cmp) to prevent soft lockups when sorting long
lists.

However, further inspection by Richard Weinberger reveals that these
compare functions are extremely lightweight and do not perform any
blocking MTD I/O. Furthermore, the lists being sorted are strictly
bounded in size:
- In the GC case, the list contains at most the number of nodes that
  fit into a single LEB.
- In the replay case, the list spans across a few LEBs from the UBIFS
  journal, amounting to at most a few thousand elements.

Since the compare functions are called a few thousand times at most,
the overhead of frequent scheduling points is unjustified. Removing the
cond_resched() calls simplifies the comparison logic and reduces
unnecessary context switch checks during the sort.

Signed-off-by: Kuan-Wei Chiu <visitorckw@gmail.com>
---
 fs/ubifs/gc.c     | 2 --
 fs/ubifs/replay.c | 1 -
 2 files changed, 3 deletions(-)

diff --git a/fs/ubifs/gc.c b/fs/ubifs/gc.c
index 0bf08b7755b8..933c79b5cd6b 100644
--- a/fs/ubifs/gc.c
+++ b/fs/ubifs/gc.c
@@ -109,7 +109,6 @@ static int data_nodes_cmp(void *priv, const struct list_head *a,
 	struct ubifs_info *c = priv;
 	struct ubifs_scan_node *sa, *sb;
 
-	cond_resched();
 	if (a == b)
 		return 0;
 
@@ -153,7 +152,6 @@ static int nondata_nodes_cmp(void *priv, const struct list_head *a,
 	struct ubifs_info *c = priv;
 	struct ubifs_scan_node *sa, *sb;
 
-	cond_resched();
 	if (a == b)
 		return 0;
 
diff --git a/fs/ubifs/replay.c b/fs/ubifs/replay.c
index a9a568f4a868..263045e05cf1 100644
--- a/fs/ubifs/replay.c
+++ b/fs/ubifs/replay.c
@@ -305,7 +305,6 @@ static int replay_entries_cmp(void *priv, const struct list_head *a,
 	struct ubifs_info *c = priv;
 	struct replay_entry *ra, *rb;
 
-	cond_resched();
 	if (a == b)
 		return 0;
 
-- 
2.53.0.959.g497ff81fa9-goog


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

[PATCH v3 2/2] lib/list_sort: Remove dummy cmp() calls to speed up merge_final()

[Kuan-Wei Chiu]

Historically, list_sort() implemented a hack in merge_final():
    if (unlikely(!++count))
        cmp(priv, b, b);

This was introduced 16 years ago in commit 835cc0c8477f ("lib: more
scalable list_sort()") so that callers could periodically invoke
cond_resched() within their comparison functions when merging highly
unbalanced lists.

An audit of the kernel tree reveals that fs/ubifs/ was the sole user
of this mechanism. Recent discussions and inspections by Richard
Weinberger confirm that UBIFS lists are strictly bounded in size (a few
thousand elements at most), meaning it does not strictly rely on these
dummy callbacks to prevent soft lockups.

For the vast majority of list_sort() users (such as block layer IO
schedulers and file systems), this hack results in completely wasted
function calls. In the worst-case scenario (merging an already sorted
list where 'a' is exhausted quickly), it results in approximately
(N/2)/256 unnecessary cmp() invocations.

Remove the dummy cmp(priv, b, b) fallback from merge_final(). This
saves unnecessary function calls, avoids branching overhead in the
tight loop, and slightly speeds up the final merge step for all generic
list_sort() users.

Signed-off-by: Kuan-Wei Chiu <visitorckw@gmail.com>
---
 lib/list_sort.c | 9 ---------
 1 file changed, 9 deletions(-)

diff --git a/lib/list_sort.c b/lib/list_sort.c
index a310ecb7ccc0..e8ff17c9b2d0 100644
--- a/lib/list_sort.c
+++ b/lib/list_sort.c
@@ -76,15 +76,6 @@ static void merge_final(void *priv, list_cmp_func_t cmp, struct list_head *head,
 	/* Finish linking remainder of list b on to tail */
 	tail->next = b;
 	do {
-		/*
-		 * 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 (unlikely(!++count))
-			cmp(priv, b, b);
 		b->prev = tail;
 		tail = b;
 		b = b->next;
-- 
2.53.0.959.g497ff81fa9-goog


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

Re: [PATCH v3 0/2] lib/list_sort: Clean up list_sort() scheduling workarounds

[Andrew Morton]

On Fri, 20 Mar 2026 18:09:36 +0000 Kuan-Wei Chiu <visitorckw@gmail.com> wrote:

> Historically, list_sort() included a hack in merge_final() that
> periodically invoked dummy cmp(priv, b, b) calls when merging highly
> unbalanced lists. This allowed the caller to invoke cond_resched()
> within their comparison callbacks to avoid soft lockups. 
> 
> However, an audit of the kernel tree shows that fs/ubifs/ has been the
> sole user of this mechanism. For all other generic list_sort() users,
> this results in wasted function calls and unnecessary overhead in a
> tight loop.
> 
> Recent discussions and code inspection confirmed that the lists being
> sorted in UBIFS are bounded in size (a few thousand elements at most),
> and the comparison functions are extremely lightweight. Therefore,
> UBIFS does not actually need to rely on this mechanism.

Thanks.  AI review found a now-unused local, which I'll fix.

https://sashiko.dev/#/patchset/20260320180938.1827148-1-visitorckw@gmail.com

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

Re: [PATCH v3 1/2] ubifs: Remove unnecessary cond_resched() from list_sort() compare

[Zhihao Cheng]

在 2026/3/21 2:09, Kuan-Wei Chiu 写道:
> Historically, UBIFS embedded cond_resched() calls inside its
> list_sort() comparison callbacks (data_nodes_cmp, nondata_nodes_cmp,
> and replay_entries_cmp) to prevent soft lockups when sorting long
> lists.
> 
> However, further inspection by Richard Weinberger reveals that these
> compare functions are extremely lightweight and do not perform any
> blocking MTD I/O. Furthermore, the lists being sorted are strictly
> bounded in size:
> - In the GC case, the list contains at most the number of nodes that
>    fit into a single LEB.
> - In the replay case, the list spans across a few LEBs from the UBIFS
>    journal, amounting to at most a few thousand elements.
> 
> Since the compare functions are called a few thousand times at most,
> the overhead of frequent scheduling points is unjustified. Removing the
> cond_resched() calls simplifies the comparison logic and reduces
> unnecessary context switch checks during the sort.
> 
> Signed-off-by: Kuan-Wei Chiu <visitorckw@gmail.com>
> ---
>   fs/ubifs/gc.c     | 2 --
>   fs/ubifs/replay.c | 1 -
>   2 files changed, 3 deletions(-)

Reviewed-by: Zhihao Cheng <chengzhihao1@huawei.com>
> 
> diff --git a/fs/ubifs/gc.c b/fs/ubifs/gc.c
> index 0bf08b7755b8..933c79b5cd6b 100644
> --- a/fs/ubifs/gc.c
> +++ b/fs/ubifs/gc.c
> @@ -109,7 +109,6 @@ static int data_nodes_cmp(void *priv, const struct list_head *a,
>   	struct ubifs_info *c = priv;
>   	struct ubifs_scan_node *sa, *sb;
>   
> -	cond_resched();
>   	if (a == b)
>   		return 0;
>   
> @@ -153,7 +152,6 @@ static int nondata_nodes_cmp(void *priv, const struct list_head *a,
>   	struct ubifs_info *c = priv;
>   	struct ubifs_scan_node *sa, *sb;
>   
> -	cond_resched();
>   	if (a == b)
>   		return 0;
>   
> diff --git a/fs/ubifs/replay.c b/fs/ubifs/replay.c
> index a9a568f4a868..263045e05cf1 100644
> --- a/fs/ubifs/replay.c
> +++ b/fs/ubifs/replay.c
> @@ -305,7 +305,6 @@ static int replay_entries_cmp(void *priv, const struct list_head *a,
>   	struct ubifs_info *c = priv;
>   	struct replay_entry *ra, *rb;
>   
> -	cond_resched();
>   	if (a == b)
>   		return 0;
>   
> 


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

Re: [PATCH v3 2/2] lib/list_sort: Remove dummy cmp() calls to speed up merge_final()

[Christoph Hellwig]

Looks good assuming you get an ACK on the ubifs part:

Reviewed-by: Christoph Hellwig <hch@lst.de>


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

Re: [PATCH v3 1/2] ubifs: Remove unnecessary cond_resched() from list_sort() compare

[Richard Weinberger]

----- Ursprüngliche Mail -----
> Von: "Kuan-Wei Chiu" <visitorckw@gmail.com>
> An: "richard" <richard@nod.at>, "Andrew Morton" <akpm@linux-foundation.org>
> CC: "chengzhihao1" <chengzhihao1@huawei.com>, "Christoph Hellwig" <hch@infradead.org>, "jserv" <jserv@ccns.ncku.edu.tw>,
> "eleanor15x" <eleanor15x@gmail.com>, "marscheng" <marscheng@google.com>, "linux-mtd" <linux-mtd@lists.infradead.org>,
> "linux-kernel" <linux-kernel@vger.kernel.org>, "Kuan-Wei Chiu" <visitorckw@gmail.com>
> Gesendet: Freitag, 20. März 2026 19:09:37
> Betreff: [PATCH v3 1/2] ubifs: Remove unnecessary cond_resched() from list_sort() compare

> Historically, UBIFS embedded cond_resched() calls inside its
> list_sort() comparison callbacks (data_nodes_cmp, nondata_nodes_cmp,
> and replay_entries_cmp) to prevent soft lockups when sorting long
> lists.
> 
> However, further inspection by Richard Weinberger reveals that these
> compare functions are extremely lightweight and do not perform any
> blocking MTD I/O. Furthermore, the lists being sorted are strictly
> bounded in size:
> - In the GC case, the list contains at most the number of nodes that
>  fit into a single LEB.
> - In the replay case, the list spans across a few LEBs from the UBIFS
>  journal, amounting to at most a few thousand elements.
> 
> Since the compare functions are called a few thousand times at most,
> the overhead of frequent scheduling points is unjustified. Removing the
> cond_resched() calls simplifies the comparison logic and reduces
> unnecessary context switch checks during the sort.
> 
> Signed-off-by: Kuan-Wei Chiu <visitorckw@gmail.com>

Acked-by: Richard Weinberger <richard@nod.at>

Thanks,
//richard

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