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

[Richard Weinberger]

----- Ursprüngliche Mail -----
> Von: "Kuan-Wei Chiu" <visitorckw@xxxxxxxxx>
>> > 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.

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.

> 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