Re: [PATCH] lib/list_sort: introduce list_sort_nonatomic() and remove dummy cmp() calls

[Kuan-Wei Chiu <visitorckw@gmail.com>]

Hi Richard,

On Mon, Mar 16, 2026 at 08:25:57AM +0100, Richard Weinberger wrote:
> ----- Ursprüngliche Mail -----
> > Von: "Kuan-Wei Chiu" <visitorckw@gmail.com>
> > 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.
> 
> 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