git: a6587ae0f46d - main - sched_ule: Fix selecting lowest priority thread early in corner case

The branch main has been updated by olce:

URL: https://cgit.FreeBSD.org/src/commit/?id=a6587ae0f46dba4e47fa92c831f55288ec181734

commit a6587ae0f46dba4e47fa92c831f55288ec181734
Author:     Olivier Certner <olce@FreeBSD.org>
AuthorDate: 2026-06-16 21:06:36 +0000
Commit:     Olivier Certner <olce@FreeBSD.org>
CommitDate: 2026-07-20 02:18:45 +0000

    sched_ule: Fix selecting lowest priority thread early in corner case
    
    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.
    
    Reviewed by:    markj
    Discussed with: Minsoo Choo <minsoo@minsoo.io>
    Fixes:          6792f3411f6d ("sched_ule: Recover previous nice and anti-starvation behaviors")
    MFC after:      2 weeks
    Sponsored by:   The FreeBSD Foundation
    Differential Revision:  https://reviews.freebsd.org/D57829
---
 sys/kern/sched_ule.c | 45 ++++++++++++++++++++++++++++++++++++---------
 1 file changed, 36 insertions(+), 9 deletions(-)

diff --git a/sys/kern/sched_ule.c b/sys/kern/sched_ule.c
index cf0baabfda86..a9fe49b11ff7 100644
--- a/sys/kern/sched_ule.c
+++ b/sys/kern/sched_ule.c
@@ -484,6 +484,17 @@ sched_shouldpreempt(int pri, int cpri, int remote)
 	return (0);
 }
 
+static inline int
+normalize_ts_off(int offset)
+{
+	/*
+	 * Adding RQ_TS_POL_MODULO before taking the modulo is to ensure the
+	 * dividend is positive (we want a positive result).
+	 */
+	MPASS(offset >= -RQ_TS_POL_MODULO);
+	return ((offset + RQ_TS_POL_MODULO) % RQ_TS_POL_MODULO);
+}
+
 /*
  * Add a thread to the actual run-queue.  Keeps transferable counts up to
  * date with what is actually on the run-queue.  Selects the correct
@@ -517,18 +528,34 @@ tdq_runq_add(struct tdq *tdq, struct thread *td, int flags)
 			/* Current queue from which processes are being run. */
 			idx = tdq->tdq_ts_deq_off;
 		else {
-			idx = (RQ_PRI_TO_QUEUE_IDX(pri) - RQ_TS_POL_MIN +
-			    tdq->tdq_ts_off) % RQ_TS_POL_MODULO;
+			idx = normalize_ts_off(
+			    /* Offset corresponding to priority. */
+			    RQ_PRI_TO_QUEUE_IDX(pri) - RQ_TS_POL_MIN +
+			    /* Insertion offset. */
+			    tdq->tdq_ts_off);
 			/*
-			 * We avoid enqueuing low priority threads in the queue
-			 * that we are still draining, effectively shortening
-			 * the runqueue by one queue.
+			 * We avoid enqueuing low priority threads in the queues
+			 * we still have to drain.  This effectively shortens
+			 * the runqueue by a few queues (see update of
+			 * 'tdq_ts_deq_off' in sched_clock()).
+			 *
+			 * The expressions that include differences below are
+			 * measuring the "distance" from the dequeue offset to
+			 * either 'idx' or the insertion offset modulo
+			 * RQ_TS_POL_MODULO.  Thanks to the arithmetic operators
+			 * always performing the usual arithmetic conversions,
+			 * all operands are promoted to integers, which is
+			 * necessary to accomodate corner cases (else
+			 * we would have to be conditional on whether the first
+			 * term is greater or lower than the second, in the
+			 * second case correcting the result with UCHAR_MAX %
+			 * RQ_TS_POL_MODULO).
 			 */
 			if (tdq->tdq_ts_deq_off != tdq->tdq_ts_off &&
-			    idx == tdq->tdq_ts_deq_off)
-				/* Ensure the dividend is positive. */
-				idx = (idx - 1 + RQ_TS_POL_MODULO) %
-				    RQ_TS_POL_MODULO;
+			    normalize_ts_off(idx - tdq->tdq_ts_deq_off) <
+			    normalize_ts_off(tdq->tdq_ts_off -
+			    tdq->tdq_ts_deq_off))
+				idx = normalize_ts_off(tdq->tdq_ts_deq_off - 1);
 		}
 		/* Absolute queue index. */
 		idx += RQ_TS_POL_MIN;