The branch main has been updated by olce:
URL:
https://cgit.FreeBSD.org/src/commit/?id=7e2502e3dec989ea31e5300ade759a721718548d
commit 7e2502e3dec989ea31e5300ade759a721718548d
Author: Olivier Certner <o...@freebsd.org>
AuthorDate: 2024-04-23 11:33:02 +0000
Commit: Olivier Certner <o...@freebsd.org>
CommitDate: 2025-06-18 02:07:58 +0000
runq: More macros; Better and more consistent naming
Most existing macros have ambiguous names regarding which index they
operate on (queue, word, bit?), so have been renamed to improve clarity.
Use the 'RQSW_' prefix for all macros related to status words, and
change the status word type name accordingly.
Rename RQB_FFS() to RQSW_BSF() to remove confusion about the return
value (ffs*() return bit indices starting at 1, or 0 if the input is 0,
whereas BSF on x86 returns 0-based indices, which is what the current
code assumes). While here, add a check (under INVARIANTS) that
RQSW_BSF() isn't called with 0 as an argument.
Also, rename 'rqb_bits_t' to the more concise 'rqsw_t', 'struct rqbits'
to 'struct rq_status', its 'rqb_bits' field to 'rq_sw' (it designates an
array of words, not bits), and the type 'rqhead' to 'rq_queue'
Add macros computing a queue index from a status word index and a bit in
order to factorize code. If the precise index of the bit is known,
callers can use RQSW_TO_QUEUE_IDX() to get the corresponding queue
index, whereas if they want the one corresponding to the first
(least-significant): set bit in a given status word (corresponding to
the non-empty queue with lower index in the status word), they can use
RQSW_FIRST_QUEUE_IDX() instead.
Add RQSW_BIT_IDX(), which computes the correspond bit's index in the
corresponding status word. This allows more code factorization (even if
most uses will be eliminated in a later commit) and makes what is
computed clearer.
Reviewed by: kib
MFC after: 1 month
Event: Kitchener-Waterloo Hackathon 202506
Sponsored by: The FreeBSD Foundation
Differential Revision: https://reviews.freebsd.org/D45387
---
sys/kern/kern_switch.c | 114 ++++++++++++++++++++++++-------------------------
sys/kern/sched_4bsd.c | 2 +-
sys/kern/sched_ule.c | 56 ++++++++++++------------
sys/sys/runq.h | 40 ++++++++++-------
4 files changed, 111 insertions(+), 101 deletions(-)
diff --git a/sys/kern/kern_switch.c b/sys/kern/kern_switch.c
index 906efca4bb51..9e63709d0acc 100644
--- a/sys/kern/kern_switch.c
+++ b/sys/kern/kern_switch.c
@@ -281,15 +281,15 @@ runq_init(struct runq *rq)
static __inline void
runq_clrbit(struct runq *rq, int idx)
{
- struct rqbits *rqb;
+ struct rq_status *rqs;
CHECK_IDX(idx);
- rqb = &rq->rq_status;
+ rqs = &rq->rq_status;
CTR4(KTR_RUNQ, "runq_clrbit: bits=%#x %#x bit=%#x word=%d",
- rqb->rqb_bits[RQB_WORD(idx)],
- rqb->rqb_bits[RQB_WORD(idx)] & ~RQB_BIT(idx),
- RQB_BIT(idx), RQB_WORD(idx));
- rqb->rqb_bits[RQB_WORD(idx)] &= ~RQB_BIT(idx);
+ rqs->rq_sw[RQSW_IDX(idx)],
+ rqs->rq_sw[RQSW_IDX(idx)] & ~RQSW_BIT(idx),
+ RQSW_BIT(idx), RQSW_IDX(idx));
+ rqs->rq_sw[RQSW_IDX(idx)] &= ~RQSW_BIT(idx);
}
/*
@@ -299,16 +299,16 @@ runq_clrbit(struct runq *rq, int idx)
static __inline int
runq_findbit(struct runq *rq)
{
- struct rqbits *rqb;
+ struct rq_status *rqs;
int idx;
- rqb = &rq->rq_status;
- for (int i = 0; i < RQB_LEN; i++)
- if (rqb->rqb_bits[i] != 0) {
- idx = RQB_FFS(rqb->rqb_bits[i]) + i * RQB_BPW;
+ rqs = &rq->rq_status;
+ for (int i = 0; i < RQSW_NB; i++)
+ if (rqs->rq_sw[i] != 0) {
+ idx = RQSW_FIRST_QUEUE_IDX(i, rqs->rq_sw[i]);
CHECK_IDX(idx);
CTR3(KTR_RUNQ, "runq_findbit: bits=%#x i=%d idx=%d",
- rqb->rqb_bits[i], i, idx);
+ rqs->rq_sw[i], i, idx);
return (idx);
}
@@ -318,20 +318,20 @@ runq_findbit(struct runq *rq)
static __inline int
runq_findbit_from(struct runq *rq, int idx)
{
- struct rqbits *rqb;
- rqb_word_t mask;
+ struct rq_status *rqs;
+ rqsw_t mask;
int i;
CHECK_IDX(idx);
/* Set the mask for the first word so we ignore indices before 'idx'. */
- mask = (rqb_word_t)-1 << (idx & (RQB_BPW - 1));
- rqb = &rq->rq_status;
+ mask = (rqsw_t)-1 << RQSW_BIT_IDX(idx);
+ rqs = &rq->rq_status;
again:
- for (i = RQB_WORD(idx); i < RQB_LEN; mask = -1, i++) {
- mask = rqb->rqb_bits[i] & mask;
+ for (i = RQSW_IDX(idx); i < RQSW_NB; mask = -1, i++) {
+ mask = rqs->rq_sw[i] & mask;
if (mask == 0)
continue;
- idx = RQB_FFS(mask) + i * RQB_BPW;
+ idx = RQSW_FIRST_QUEUE_IDX(i, mask);
CTR3(KTR_RUNQ, "runq_findbit_from: bits=%#x i=%d idx=%d",
mask, i, idx);
return (idx);
@@ -353,15 +353,15 @@ again:
static __inline void
runq_setbit(struct runq *rq, int idx)
{
- struct rqbits *rqb;
+ struct rq_status *rqs;
CHECK_IDX(idx);
- rqb = &rq->rq_status;
+ rqs = &rq->rq_status;
CTR4(KTR_RUNQ, "runq_setbit: bits=%#x %#x bit=%#x word=%d",
- rqb->rqb_bits[RQB_WORD(idx)],
- rqb->rqb_bits[RQB_WORD(idx)] | RQB_BIT(idx),
- RQB_BIT(idx), RQB_WORD(idx));
- rqb->rqb_bits[RQB_WORD(idx)] |= RQB_BIT(idx);
+ rqs->rq_sw[RQSW_IDX(idx)],
+ rqs->rq_sw[RQSW_IDX(idx)] | RQSW_BIT(idx),
+ RQSW_BIT(idx), RQSW_IDX(idx));
+ rqs->rq_sw[RQSW_IDX(idx)] |= RQSW_BIT(idx);
}
/*
@@ -372,13 +372,13 @@ void
runq_add(struct runq *rq, struct thread *td, int flags)
{
- runq_add_idx(rq, td, RQ_PRI_TO_IDX(td->td_priority), flags);
+ runq_add_idx(rq, td, RQ_PRI_TO_QUEUE_IDX(td->td_priority), flags);
}
void
runq_add_idx(struct runq *rq, struct thread *td, int idx, int flags)
{
- struct rqhead *rqh;
+ struct rq_queue *rqq;
/*
* runq_setbit() asserts 'idx' is non-negative and below 'RQ_NQS', and
@@ -387,13 +387,13 @@ runq_add_idx(struct runq *rq, struct thread *td, int idx,
int flags)
*/
td->td_rqindex = idx;
runq_setbit(rq, idx);
- rqh = &rq->rq_queues[idx];
- CTR4(KTR_RUNQ, "runq_add_idx: td=%p pri=%d idx=%d rqh=%p",
- td, td->td_priority, idx, rqh);
+ rqq = &rq->rq_queues[idx];
+ CTR4(KTR_RUNQ, "runq_add_idx: td=%p pri=%d idx=%d rqq=%p",
+ td, td->td_priority, idx, rqq);
if (flags & SRQ_PREEMPTED)
- TAILQ_INSERT_HEAD(rqh, td, td_runq);
+ TAILQ_INSERT_HEAD(rqq, td, td_runq);
else
- TAILQ_INSERT_TAIL(rqh, td, td_runq);
+ TAILQ_INSERT_TAIL(rqq, td, td_runq);
}
/*
@@ -403,13 +403,13 @@ runq_add_idx(struct runq *rq, struct thread *td, int idx,
int flags)
bool
runq_not_empty(struct runq *rq)
{
- struct rqbits *rqb;
+ struct rq_status *rqs;
- rqb = &rq->rq_status;
- for (int i = 0; i < RQB_LEN; i++)
- if (rqb->rqb_bits[i] != 0) {
+ rqs = &rq->rq_status;
+ for (int i = 0; i < RQSW_NB; i++)
+ if (rqs->rq_sw[i] != 0) {
CTR2(KTR_RUNQ, "runq_not_empty: bits=%#x i=%d",
- rqb->rqb_bits[i], i);
+ rqs->rq_sw[i], i);
return (true);
}
CTR0(KTR_RUNQ, "runq_not_empty: empty");
@@ -423,13 +423,13 @@ runq_not_empty(struct runq *rq)
struct thread *
runq_choose_fuzz(struct runq *rq, int fuzz)
{
- struct rqhead *rqh;
+ struct rq_queue *rqq;
struct thread *td;
int idx;
idx = runq_findbit(rq);
if (idx != -1) {
- rqh = &rq->rq_queues[idx];
+ rqq = &rq->rq_queues[idx];
/* fuzz == 1 is normal.. 0 or less are ignored */
if (fuzz > 1) {
/*
@@ -439,7 +439,7 @@ runq_choose_fuzz(struct runq *rq, int fuzz)
int count = fuzz;
int cpu = PCPU_GET(cpuid);
struct thread *td2;
- td2 = td = TAILQ_FIRST(rqh);
+ td2 = td = TAILQ_FIRST(rqq);
while (count-- && td2) {
if (td2->td_lastcpu == cpu) {
@@ -449,10 +449,10 @@ runq_choose_fuzz(struct runq *rq, int fuzz)
td2 = TAILQ_NEXT(td2, td_runq);
}
} else
- td = TAILQ_FIRST(rqh);
+ td = TAILQ_FIRST(rqq);
KASSERT(td != NULL, ("runq_choose_fuzz: no proc on busy
queue"));
CTR3(KTR_RUNQ,
- "runq_choose_fuzz: idx=%d thread=%p rqh=%p", idx, td, rqh);
+ "runq_choose_fuzz: idx=%d thread=%p rqq=%p", idx, td, rqq);
return (td);
}
CTR1(KTR_RUNQ, "runq_choose_fuzz: idleproc idx=%d", idx);
@@ -466,17 +466,17 @@ runq_choose_fuzz(struct runq *rq, int fuzz)
struct thread *
runq_choose(struct runq *rq)
{
- struct rqhead *rqh;
+ struct rq_queue *rqq;
struct thread *td;
int idx;
idx = runq_findbit(rq);
if (idx != -1) {
- rqh = &rq->rq_queues[idx];
- td = TAILQ_FIRST(rqh);
+ rqq = &rq->rq_queues[idx];
+ td = TAILQ_FIRST(rqq);
KASSERT(td != NULL, ("runq_choose: no thread on busy queue"));
CTR3(KTR_RUNQ,
- "runq_choose: idx=%d thread=%p rqh=%p", idx, td, rqh);
+ "runq_choose: idx=%d thread=%p rqq=%p", idx, td, rqq);
return (td);
}
CTR1(KTR_RUNQ, "runq_choose: idlethread idx=%d", idx);
@@ -487,17 +487,17 @@ runq_choose(struct runq *rq)
struct thread *
runq_choose_from(struct runq *rq, int from_idx)
{
- struct rqhead *rqh;
+ struct rq_queue *rqq;
struct thread *td;
int idx;
if ((idx = runq_findbit_from(rq, from_idx)) != -1) {
- rqh = &rq->rq_queues[idx];
- td = TAILQ_FIRST(rqh);
+ rqq = &rq->rq_queues[idx];
+ td = TAILQ_FIRST(rqq);
KASSERT(td != NULL, ("runq_choose: no thread on busy queue"));
CTR4(KTR_RUNQ,
- "runq_choose_from: idx=%d thread=%p idx=%d rqh=%p",
- idx, td, td->td_rqindex, rqh);
+ "runq_choose_from: idx=%d thread=%p idx=%d rqq=%p",
+ idx, td, td->td_rqindex, rqq);
return (td);
}
CTR1(KTR_RUNQ, "runq_choose_from: idlethread idx=%d", idx);
@@ -513,17 +513,17 @@ runq_choose_from(struct runq *rq, int from_idx)
bool
runq_remove(struct runq *rq, struct thread *td)
{
- struct rqhead *rqh;
+ struct rq_queue *rqq;
int idx;
KASSERT(td->td_flags & TDF_INMEM, ("runq_remove: Thread swapped out"));
idx = td->td_rqindex;
CHECK_IDX(idx);
- rqh = &rq->rq_queues[idx];
- CTR4(KTR_RUNQ, "runq_remove: td=%p pri=%d idx=%d rqh=%p",
- td, td->td_priority, idx, rqh);
- TAILQ_REMOVE(rqh, td, td_runq);
- if (TAILQ_EMPTY(rqh)) {
+ rqq = &rq->rq_queues[idx];
+ CTR4(KTR_RUNQ, "runq_remove: td=%p pri=%d idx=%d rqq=%p",
+ td, td->td_priority, idx, rqq);
+ TAILQ_REMOVE(rqq, td, td_runq);
+ if (TAILQ_EMPTY(rqq)) {
runq_clrbit(rq, idx);
CTR1(KTR_RUNQ, "runq_remove: queue at idx=%d now empty", idx);
return (true);
diff --git a/sys/kern/sched_4bsd.c b/sys/kern/sched_4bsd.c
index ef49832da017..d15f5d68fbec 100644
--- a/sys/kern/sched_4bsd.c
+++ b/sys/kern/sched_4bsd.c
@@ -873,7 +873,7 @@ sched_priority(struct thread *td, u_char prio)
if (td->td_priority == prio)
return;
td->td_priority = prio;
- if (TD_ON_RUNQ(td) && td->td_rqindex != RQ_PRI_TO_IDX(prio)) {
+ if (TD_ON_RUNQ(td) && td->td_rqindex != RQ_PRI_TO_QUEUE_IDX(prio)) {
sched_rem(td);
sched_add(td, SRQ_BORING | SRQ_HOLDTD);
}
diff --git a/sys/kern/sched_ule.c b/sys/kern/sched_ule.c
index cd508d12395e..1cec38597952 100644
--- a/sys/kern/sched_ule.c
+++ b/sys/kern/sched_ule.c
@@ -387,20 +387,20 @@ SDT_PROBE_DEFINE2(sched, , , surrender, "struct thread *",
static void
runq_print(struct runq *rq)
{
- struct rqhead *rqh;
+ struct rq_queue *rqq;
struct thread *td;
int pri;
int j;
int i;
- for (i = 0; i < RQB_LEN; i++) {
+ for (i = 0; i < RQSW_NB; i++) {
printf("\t\trunq bits %d 0x%zx\n",
- i, rq->rq_status.rqb_bits[i]);
- for (j = 0; j < RQB_BPW; j++)
- if (rq->rq_status.rqb_bits[i] & (1ul << j)) {
- pri = j + i * RQB_BPW;
- rqh = &rq->rq_queues[pri];
- TAILQ_FOREACH(td, rqh, td_runq) {
+ i, rq->rq_status.rq_sw[i]);
+ for (j = 0; j < RQSW_BPW; j++)
+ if (rq->rq_status.rq_sw[i] & (1ul << j)) {
+ pri = RQSW_TO_QUEUE_IDX(i, j);
+ rqq = &rq->rq_queues[pri];
+ TAILQ_FOREACH(td, rqq, td_runq) {
printf("\t\t\ttd %p(%s) priority %d
rqindex %d pri %d\n",
td, td->td_name, td->td_priority,
td->td_rqindex, pri);
@@ -1190,26 +1190,26 @@ tdq_notify(struct tdq *tdq, int lowpri)
static struct thread *
runq_steal_from(struct runq *rq, int cpu, u_char start)
{
- struct rqbits *rqb;
- struct rqhead *rqh;
+ struct rq_status *rqs;
+ struct rq_queue *rqq;
struct thread *td, *first;
int bit;
int i;
- rqb = &rq->rq_status;
- bit = start & (RQB_BPW -1);
+ rqs = &rq->rq_status;
+ bit = RQSW_BIT_IDX(start);
first = NULL;
again:
- for (i = RQB_WORD(start); i < RQB_LEN; bit = 0, i++) {
- if (rqb->rqb_bits[i] == 0)
+ for (i = RQSW_IDX(start); i < RQSW_NB; bit = 0, i++) {
+ if (rqs->rq_sw[i] == 0)
continue;
if (bit == 0)
- bit = RQB_FFS(rqb->rqb_bits[i]);
- for (; bit < RQB_BPW; bit++) {
- if ((rqb->rqb_bits[i] & (1ul << bit)) == 0)
+ bit = RQSW_BSF(rqs->rq_sw[i]);
+ for (; bit < RQSW_BPW; bit++) {
+ if ((rqs->rq_sw[i] & (1ul << bit)) == 0)
continue;
- rqh = &rq->rq_queues[bit + i * RQB_BPW];
- TAILQ_FOREACH(td, rqh, td_runq) {
+ 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))
@@ -1236,21 +1236,21 @@ again:
static struct thread *
runq_steal(struct runq *rq, int cpu)
{
- struct rqhead *rqh;
- struct rqbits *rqb;
+ struct rq_queue *rqq;
+ struct rq_status *rqs;
struct thread *td;
int word;
int bit;
- rqb = &rq->rq_status;
- for (word = 0; word < RQB_LEN; word++) {
- if (rqb->rqb_bits[word] == 0)
+ rqs = &rq->rq_status;
+ for (word = 0; word < RQSW_NB; word++) {
+ if (rqs->rq_sw[word] == 0)
continue;
- for (bit = 0; bit < RQB_BPW; bit++) {
- if ((rqb->rqb_bits[word] & (1ul << bit)) == 0)
+ for (bit = 0; bit < RQSW_BPW; bit++) {
+ if ((rqs->rq_sw[word] & (1ul << bit)) == 0)
continue;
- rqh = &rq->rq_queues[bit + word * RQB_BPW];
- TAILQ_FOREACH(td, rqh, td_runq)
+ 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);
diff --git a/sys/sys/runq.h b/sys/sys/runq.h
index 030b4bb370a8..80a1fad0a089 100644
--- a/sys/sys/runq.h
+++ b/sys/sys/runq.h
@@ -47,16 +47,26 @@
/*
* Deduced from the above parameters and machine ones.
*/
-typedef unsigned long rqb_word_t; /* runq's status words type. */
-
#define RQ_NQS (howmany(RQ_MAX_PRIO + 1, RQ_PPQ)) /* Number of run
queues. */
-#define RQ_PRI_TO_IDX(pri) ((pri) / RQ_PPQ) /* Priority to queue
index. */
-
-#define RQB_BPW (sizeof(rqb_word_t) * NBBY) /* Bits per runq word. */
-#define RQB_LEN (howmany(RQ_NQS, RQB_BPW)) /* Words to cover RQ_NQS
queues. */
-#define RQB_WORD(idx) ((idx) / RQB_BPW)
-#define RQB_BIT(idx) (1ul << ((idx) % RQB_BPW))
-#define RQB_FFS(word) (ffsl((long)(word)) - 1) /* Assumes
two-complement. */
+#define RQ_PRI_TO_QUEUE_IDX(pri) ((pri) / RQ_PPQ) /* Priority to queue
index. */
+
+typedef unsigned long rqsw_t; /* runq's status words type. */
+#define RQSW_BPW (sizeof(rqsw_t) * NBBY) /* Bits per runq word.
*/
+
+/* Number of status words to cover RQ_NQS queues. */
+#define RQSW_NB (howmany(RQ_NQS, RQSW_BPW))
+#define RQSW_IDX(idx) ((idx) / RQSW_BPW)
+#define RQSW_BIT_IDX(idx) ((idx) % RQSW_BPW)
+#define RQSW_BIT(idx) (1ul << RQSW_BIT_IDX(idx))
+#define RQSW_BSF(word) __extension__ ({
\
+ int _res = ffsl((long)(word)); /* Assumes two-complement. */ \
+ MPASS(_res > 0); \
+ _res - 1; \
+})
+#define RQSW_TO_QUEUE_IDX(word_idx, bit_idx)
\
+ (((word_idx) * RQSW_BPW) + (bit_idx))
+#define RQSW_FIRST_QUEUE_IDX(word_idx, word)
\
+ RQSW_TO_QUEUE_IDX(word_idx, RQSW_BSF(word))
#ifdef _KERNEL
@@ -66,16 +76,16 @@ typedef unsigned long rqb_word_t; /* runq's
status words type. */
struct thread;
/*
- * Head of run queues.
+ * The queue for a given index as a list of threads.
*/
-TAILQ_HEAD(rqhead, thread);
+TAILQ_HEAD(rq_queue, thread);
/*
* Bit array which maintains the status of a run queue. When a queue is
* non-empty the bit corresponding to the queue number will be set.
*/
-struct rqbits {
- rqb_word_t rqb_bits[RQB_LEN];
+struct rq_status {
+ rqsw_t rq_sw[RQSW_NB];
};
/*
@@ -83,8 +93,8 @@ struct rqbits {
* are placed, and a structure to maintain the status of each queue.
*/
struct runq {
- struct rqbits rq_status;
- struct rqhead rq_queues[RQ_NQS];
+ struct rq_status rq_status;
+ struct rq_queue rq_queues[RQ_NQS];
};
void runq_add(struct runq *, struct thread *, int _flags);
