The branch main has been updated by olce:
URL:
https://cgit.FreeBSD.org/src/commit/?id=f4be333bc56759d33dca49ab4d19eaf22134e844
commit f4be333bc56759d33dca49ab4d19eaf22134e844
Author: Olivier Certner <o...@freebsd.org>
AuthorDate: 2024-04-29 00:55:40 +0000
Commit: Olivier Certner <o...@freebsd.org>
CommitDate: 2025-06-18 02:08:01 +0000
sched_ule: Re-implement stealing on top of runq common-code
Stop using internal knowledge of runqueues. Remove duplicate
boilerplate parts.
Concretely, runq_steal() and runq_steal_from() are now implemented on
top of runq_findq().
Besides considerably simplifying the code, this change also brings an
algorithmic improvement since, previously, set bits in the runqueue's
status words were found by testing each bit individually in a loop
instead of using ffsl()/bsfl() (except for the first set bit per status
word).
This change also makes it more apparent that runq_steal_from() treats
the first thread with highest priority specifically (which runq_steal()
does not).
MFC after: 1 month
Event: Kitchener-Waterloo Hackathon 202506
Sponsored by: The FreeBSD Foundation
Differential Revision: https://reviews.freebsd.org/D45388
---
sys/kern/sched_ule.c | 124 ++++++++++++++++++++++++++++-----------------------
1 file changed, 68 insertions(+), 56 deletions(-)
diff --git a/sys/kern/sched_ule.c b/sys/kern/sched_ule.c
index c23d00fd6049..5c7665eb7add 100644
--- a/sys/kern/sched_ule.c
+++ b/sys/kern/sched_ule.c
@@ -1183,51 +1183,68 @@ tdq_notify(struct tdq *tdq, int lowpri)
ipi_cpu(cpu, IPI_PREEMPT);
}
-/*
- * Steals load from a timeshare queue. Honors the rotating queue head
- * index.
- */
-static struct thread *
-runq_steal_from(struct runq *rq, int cpu, u_char start)
+struct runq_steal_pred_data {
+ struct thread *td;
+ struct thread *first;
+ int cpu;
+ bool use_first_last;
+};
+
+static bool
+runq_steal_pred(const int idx, struct rq_queue *const q, void *const data)
{
- struct rq_status *rqs;
- struct rq_queue *rqq;
- struct thread *td, *first;
- int bit;
- int i;
+ struct runq_steal_pred_data *const d = data;
+ struct thread *td;
- rqs = &rq->rq_status;
- bit = RQSW_BIT_IDX(start);
- first = NULL;
-again:
- for (i = RQSW_IDX(start); i < RQSW_NB; bit = 0, i++) {
- if (rqs->rq_sw[i] == 0)
+ TAILQ_FOREACH(td, q, td_runq) {
+ if (d->use_first_last && d->first == NULL) {
+ d->first = td;
continue;
- if (bit == 0)
- bit = RQSW_BSF(rqs->rq_sw[i]);
- for (; bit < RQSW_BPW; bit++) {
- if ((rqs->rq_sw[i] & (1ul << bit)) == 0)
- continue;
- rqq = &rq->rq_queues[RQSW_TO_QUEUE_IDX(i, bit)];
- TAILQ_FOREACH(td, rqq, td_runq) {
- if (first) {
- if (THREAD_CAN_MIGRATE(td) &&
- THREAD_CAN_SCHED(td, cpu))
- return (td);
- } else
- first = td;
- }
+ }
+
+ if (THREAD_CAN_MIGRATE(td) && THREAD_CAN_SCHED(td, d->cpu)) {
+ d->td = td;
+ return (true);
}
}
- if (start != 0) {
- start = 0;
- goto again;
+
+ return (false);
+}
+
+/*
+ * Steals load from a timeshare queue. Honors the rotating queue head
+ * index.
+ */
+static inline struct thread *
+runq_steal_from(struct runq *const rq, int cpu, int start_idx)
+{
+ struct runq_steal_pred_data data = {
+ .td = NULL,
+ .first = NULL,
+ .cpu = cpu,
+ .use_first_last = true
+ };
+ int idx;
+
+ idx = runq_findq(rq, start_idx, RQ_NQS - 1, &runq_steal_pred, &data);
+ if (idx != -1)
+ goto found;
+
+ MPASS(data.td == NULL);
+ if (start_idx != 0) {
+ idx = runq_findq(rq, 0, start_idx - 1, &runq_steal_pred, &data);
+ if (idx != -1)
+ goto found;
}
- if (first && THREAD_CAN_MIGRATE(first) &&
- THREAD_CAN_SCHED(first, cpu))
- return (first);
+ MPASS(idx == -1 && data.td == NULL);
+ if (data.first != NULL && THREAD_CAN_MIGRATE(data.first) &&
+ THREAD_CAN_SCHED(data.first, cpu))
+ return (data.first);
return (NULL);
+found:
+ MPASS(data.td != NULL);
+ return (data.td);
}
/*
@@ -1236,26 +1253,21 @@ again:
static struct thread *
runq_steal(struct runq *rq, int cpu)
{
- struct rq_queue *rqq;
- struct rq_status *rqs;
- struct thread *td;
- int word;
- int bit;
-
- rqs = &rq->rq_status;
- for (word = 0; word < RQSW_NB; word++) {
- if (rqs->rq_sw[word] == 0)
- continue;
- for (bit = 0; bit < RQSW_BPW; bit++) {
- if ((rqs->rq_sw[word] & (1ul << bit)) == 0)
- continue;
- rqq = &rq->rq_queues[RQSW_TO_QUEUE_IDX(word, bit)];
- TAILQ_FOREACH(td, rqq, td_runq)
- if (THREAD_CAN_MIGRATE(td) &&
- THREAD_CAN_SCHED(td, cpu))
- return (td);
- }
+ struct runq_steal_pred_data data = {
+ .td = NULL,
+ .first = NULL,
+ .cpu = cpu,
+ .use_first_last = false
+ };
+ int idx;
+
+ idx = runq_findq(rq, 0, RQ_NQS - 1, &runq_steal_pred, &data);
+ if (idx != -1) {
+ MPASS(data.td != NULL);
+ return (data.td);
}
+
+ MPASS(data.td == NULL);
return (NULL);
}
