sched_ule: Fix selecting lowest priority thread early in corner case

[olce]

Summary

When transferring a thread with near 100% CPU statistics (but not 100%;
up to 57.5/59≈97.46%) to a CPU where the enqueue offset is ahead of at
least 2 from the dequeue one, which requires peculiar conditions to
happen (transfer triggered by a bind request or cpuset change, or during
balancing if a thread or more existed from a brief amount of time on the
origin CPU), the transferred thread can get placed after the dequeue
offset, effectively making it appear as a high priority one unduly,
causing latency increase for other threads.

The change here was missed when changing the enqueue and dequeue offsets
update mechanism to recover pre-256-queue-runqueue ULE anti-starvation
and fairness behavior. That change opened up the possibility that these
two offsets are apart by more than one.

Fixes: 6792f3411f6d ("sched_ule: Recover previous nice and anti-starvation behaviors")
MFC after: 2 weeks
Sponsored by: The FreeBSD Foundation

[olce]

Good commit this time.

[olce]

Although it looks improbable, it might be the cause of the observed latency problem at Netflix.

[ali_mashtizadeh.com]

We may have hit this one but that's not the one I'm testing a patch for right now. If it looks good in our setup I'll share it. It's a bit more of a fundamental scheduler change that we may or may not want to have enabled by default.

Do you have your tree for the stuff from your talk because, I'd like to compare notes. I had a few other odd behaviors I found. Some of them I didn't fix yet but couldn't tell if you did from your talk.

[ali_mashtizadeh.com]

Also can someone with access on review make a sched group?

[markj]

sys/kern/sched_ule.c

507

Why does "pri" need to be an int?

556

This cast is unneeded, I believe, all of the operands here will undergo integer promotion before the result is computed.

560

You might add a little helper macro or function to normalize the index, since you're doing that three times here and the result isn't terribly easy to read.

[olce]

Simplify.

[olce]

sys/kern/sched_ule.c

507

For a similar reason as for idx. pri is used in the initial computation of idx, which involves adding an offset and then a modulo. Adding the offset may cause a computation done on 8-bit to wraparound, causing a wrong mathematical result.

But arithmetic operators actually do the usual arithmetic conversions even when operands have same type, so this in fact unnecessary, going to undo this chunk.

556

Had a moment of doubt because I didn't think that the mere use of +/- would trigger arithmetic conversions (and hence, integer promotions), but that is explicitly written in the standard, and Godbolt confirms that in practice, so I'll just remove it.

[minsoochoo0122_proton.me]

For now I don't have enough time to visit this, so I'll take a look at this later. If I don't give any comment by Saturday evening, you can commit this.

[minsoochoo0122_proton.me]

Wouldn't this clamp threads with different priorities to the same index (tdq->tdq_ts_deq_off - 1)?

Is there any way that we can ensure tdq_ts_deq_off is always behind tdq_ts_off + MODULO and replace the whole thing as MPASS() instead?

[minsoochoo0122_proton.me]

In D57829#1330688, @minsoochoo0122_proton.me wrote:

Wouldn't this clamp threads with different priorities to the same index (tdq->tdq_ts_deq_off - 1)?

Is there any way that we can ensure tdq_ts_deq_off is always behind tdq_ts_off + MODULO and replace the whole thing as MPASS() instead?

Forget what I said above, we cannot do that under current design. I think clamping is fine if 1) it only happens to a few lowest priorities and 2) this situation doesn't happen often.

I think the current runq design is good for 4BSD, but it sometimes fails to address cases like this for ULE. A future improvement can be making the circular queue long enough so this doesn't happen, but it requires refactoring runq code as well both on 4BSD and ULE side.

Hence, LGTM:)