lib/list_sort: introduce list_sort_nonatomic() and remove dummy cmp() calls
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
@@ -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
@@ -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
@@ -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
Richard Weinberger
maintainer----- Ursprüngliche Mail -----
Quoted 9 lines
Von: "Kuan-Wei Chiu" <[email protected]> Historically,
list_sort()implemented a hack inmerge_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 oflist_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 unnecessarycmp()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
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 inmerge_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 oflist_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 unnecessarycmp()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
Richard Weinberger
maintainer----- 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 oflist_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 unnecessarycmp()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 scalablelist_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 acond_resched()in theircmp()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
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 scalablelist_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 acond_resched()in theircmp()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.
Richard Weinberger
maintainer----- 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_reschedfrom 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
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_reschedfrom 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/
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_reschedfrom 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
Quoted 27 lines · Kuan-Wei Chiu
Historically,
list_sort()implemented a hack inmerge_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 oflist_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 unnecessarycmp()calls.To clean up this API while ensuring behavior compatibility:
1. Introducelist_sort_nonatomic(), which explicitly callscond_resched()internally when count overflows.
2. Remove the dummycmp(priv, b, b)fallback for standardlist_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
Signed-off-by Kuan-Wei Chiu <[email protected]>--- 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@@ -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@@ -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
-0b->prev = tail; tail = b; b = b->next;
Hi Zhihao,
Quoted 36 lines · Zhihao Cheng
Quoted 27 lines · Kuan-Wei Chiu
Historically,
list_sort()implemented a hack inmerge_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 oflist_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 unnecessarycmp()calls.To clean up this API while ensuring behavior compatibility:
1. Introducelist_sort_nonatomic(), which explicitly callscond_resched()internally when count overflows.
2. Remove the dummycmp(priv, b, b)fallback for standardlist_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
Signed-off-by Kuan-Wei Chiu <[email protected]>--- 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.
Reviewed-by Zhihao Cheng <[email protected]>
Thanks for your review!
Quoted 44 lines
one small nit below.
Quoted 1 line
[...]
Quoted 39 lines
include/linux/list_sort.h +3
-0@@ -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@@ -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
Zhihao Cheng
reviewerQuoted 116 lines · Kuan-Wei Chiu
Hi Zhihao,
Quoted 36 lines · Zhihao Cheng
Quoted 27 lines · Kuan-Wei Chiu
Historically,
list_sort()implemented a hack inmerge_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 oflist_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 unnecessarycmp()calls.To clean up this API while ensuring behavior compatibility:
1. Introducelist_sort_nonatomic(), which explicitly callscond_resched()internally when count overflows.
2. Remove the dummycmp(priv, b, b)fallback for standardlist_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
Signed-off-by Kuan-Wei Chiu <[email protected]>--- 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.
Reviewed-by Zhihao Cheng <[email protected]>Thanks for your review!
Quoted 44 lines
one small nit below.
Quoted 1 line
[...]
Quoted 39 lines
include/linux/list_sort.h +3
-0@@ -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@@ -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 checktask_structstates, 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 thecond_resched()out of UBIFS'scmp()functions entirely and handle it insidelist_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 thecond_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
.
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 inmerge_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 oflist_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 unnecessarycmp()calls.To clean up this API while ensuring behavior compatibility:
1. Introducelist_sort_nonatomic(), which explicitly callscond_resched()internally when count overflows.
2. Remove the dummycmp(priv, b, b)fallback for standardlist_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
Signed-off-by Kuan-Wei Chiu <[email protected]>--- 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.
Reviewed-by Zhihao Cheng <[email protected]>Thanks for your review!
Quoted 44 lines
one small nit below.
Quoted 1 line
[...]
Quoted 39 lines
include/linux/list_sort.h +3
-0@@ -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@@ -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 checktask_structstates, 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 thecond_resched()out of UBIFS'scmp()functions entirely and handle it insidelist_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 thecond_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 ...). Forlist_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 oflist_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