Skip to contentSkip to conversation

lib/list_sort: introduce list_sort_nonatomic() and clean up scheduling workarounds

PATCH Superseded Kuan-Wei Chiu 3 participants 4 messages Mar 17 – Mar 19

Subsystems (3)

v2 of 3 Superseded Latest is v3 →

lore
Share & tools
lore
#0 lore raw

PATCH v2 1/1 lib/list_sort: introduce list_sort_nonatomic() and clean up scheduling workarounds

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), it results in approximately (N/2)/256 unnecessary cmp() calls.

To clean up this API, eliminate the overhead for generic users, and consolidate the scheduling logic:
1. Introduce list_sort_nonatomic(), which explicitly calls cond_resched() within its inner merge loops.
2. Remove the dummy cmp(priv, b, b) fallback from standard list_sort(), saving unnecessary function calls and improving determinism for all other subsystems.
3. Convert the sole user (fs/ubifs/) to the new API and completely remove cond_resched() from UBIFS's comparison callbacks, unpolluting its comparison logic.

This change leaves the generic list_sort() completely free of scheduling hacks, simplifies UBIFS's callbacks, and ensures that legacy long-list sorting workloads remain safe from soft lockups on non-preemptible kernels.

---
Changes in v2:
- Drop the 'count' rate-limiter for cond_resched().
- Remove cond_resched() from UBIFS comparison callbacks.

 fs/ubifs/gc.c             |   6 +-
 fs/ubifs/replay.c         |   3 +-
 include/linux/list_sort.h |   3 +
 lib/list_sort.c           | 174 ++++++++++++++++++++++----------------
 4 files changed, 106 insertions(+), 80 deletions(-)
fs/ubifs/gc.c +2 -4
index 0bf08b7755b8..54fac33224fa 100644
@@ -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;
 
@@ -277,8 +275,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 -2
index a9a568f4a868..c639394e60ac 100644
@@ -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;
 
@@ -329,7 +328,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 +100 -74

220 lines not on this page · raw message

Signature · 1 line
2.53.0.851.ga537e3e6e9-goog
#1 lore raw
Quoted 26 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), it results in approximately (N/2)/256 unnecessary cmp() calls.

To clean up this API, eliminate the overhead for generic users, and consolidate the scheduling logic:
1. Introduce list_sort_nonatomic(), which explicitly calls cond_resched() within its inner merge loops.
2. Remove the dummy cmp(priv, b, b) fallback from standard list_sort(), saving unnecessary function calls and improving determinism for all other subsystems.
3. Convert the sole user (fs/ubifs/) to the new API and completely remove cond_resched() from UBIFS's comparison callbacks, unpolluting its comparison logic.

Quoted 4 lines

This change leaves the generic list_sort() completely free of scheduling hacks, simplifies UBIFS's callbacks, and ensures that legacy long-list sorting workloads remain safe from soft lockups on non-preemptible kernels.

As said before we really should not add the extra nonatomic API and just do the right thing, and drop the cond_resched in ubifs in a prep patch.

#2 lore raw

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

Quoted 9 lines

Von: "Christoph Hellwig" <[email protected]>

Quoted 4 lines

This change leaves the generic list_sort() completely free of scheduling hacks, simplifies UBIFS's callbacks, and ensures that legacy long-list sorting workloads remain safe from soft lockups on non-preemptible kernels.

As said before we really should not add the extra nonatomic API and just do the right thing, and drop the cond_resched in ubifs in a prep patch.

I think you are right. After inspecting UBIFS's usage of list_sort() I feel more confident that we can remove the calls to cond_resched() from the compare functions.

The compare functions are rather cheap, they don't do (blocking) MTD io.
In the GC case each list contains at most as many UBIFS nodes you can stuff into a single LEB.
The replay case is a little different, the replay list can contain elements from multiple LEBs. But the UBIFS journal is limited to a few LEBs, so the list is likely always at most a few thousand elements long.
So, we always talk about calling the compare functions a few thousand times, not millions times.

Thanks,
//richard

#3 lore raw
Quoted 15 lines · Richard Weinberger

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

Quoted 9 lines

Von: "Christoph Hellwig" <[email protected]>

Quoted 4 lines

This change leaves the generic list_sort() completely free of scheduling hacks, simplifies UBIFS's callbacks, and ensures that legacy long-list sorting workloads remain safe from soft lockups on non-preemptible kernels.

As said before we really should not add the extra nonatomic API and just do the right thing, and drop the cond_resched in ubifs in a prep patch.

I think you are right. After inspecting UBIFS's usage of list_sort() I feel more confident that we can remove the calls to cond_resched() from the compare functions.

Quoted 11 lines

The compare functions are rather cheap, they don't do (blocking) MTD io.
In the GC case each list contains at most as many UBIFS nodes you can stuff into a single LEB.
The replay case is a little different, the replay list can contain elements from multiple LEBs. But the UBIFS journal is limited to a few LEBs, so the list is likely always at most a few thousand elements long.
So, we always talk about calling the compare functions a few thousand times, not millions times.

Great, thanks for verifying this.

I'll prepare a v3 to drop the cond_resched() calls from UBIFS's cmp(), and remove the if(!++count) from list_sort().

Regards,
Kuan-Wei