D45387.diff
No OneTemporary
Actions

Size

40 KB

Referenced Files

None

Subscribers

None

D45387.diff
View Options

	diff --git a/sys/amd64/include/runq.h b/sys/amd64/include/runq.h
	deleted file mode 100644
	--- a/sys/amd64/include/runq.h
	+++ /dev/null
	@@ -1,46 +0,0 @@
	-/*-
	- * SPDX-License-Identifier: BSD-2-Clause
	- *
	- * Copyright (c) 2001 Jake Burkholder <jake@FreeBSD.org>
	- * All rights reserved.
	- *
	- * Redistribution and use in source and binary forms, with or without
	- * modification, are permitted provided that the following conditions
	- * are met:
	- * 1. Redistributions of source code must retain the above copyright
	- * notice, this list of conditions and the following disclaimer.
	- * 2. Redistributions in binary form must reproduce the above copyright
	- * notice, this list of conditions and the following disclaimer in the
	- * documentation and/or other materials provided with the distribution.
	- *
	- * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
	- * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
	- * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
	- * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
	- * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
	- * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
	- * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
	- * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
	- * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
	- * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
	- * SUCH DAMAGE.
	- */
	-
	-#ifndef _MACHINE_RUNQ_H_
	-#define _MACHINE_RUNQ_H_
	-
	-#define RQB_LEN (1) /* Number of priority status words. */
	-#define RQB_L2BPW (6) /* Log2(sizeof(rqb_word_t) * NBBY)). */
	-#define RQB_BPW (1<<RQB_L2BPW) /* Bits in an rqb_word_t. */
	-
	-#define RQB_BIT(pri) (1ul << ((pri) & (RQB_BPW - 1)))
	-#define RQB_WORD(pri) ((pri) >> RQB_L2BPW)
	-
	-#define RQB_FFS(word) (bsfq(word))
	-
	-/*
	- * Type of run queue status word.
	- */
	-typedef u_int64_t rqb_word_t;
	-
	-#endif
	diff --git a/sys/arm/include/runq.h b/sys/arm/include/runq.h
	deleted file mode 100644
	--- a/sys/arm/include/runq.h
	+++ /dev/null
	@@ -1,46 +0,0 @@
	-/*-
	- * SPDX-License-Identifier: BSD-2-Clause
	- *
	- * Copyright (c) 2001 Jake Burkholder <jake@FreeBSD.org>
	- * All rights reserved.
	- *
	- * Redistribution and use in source and binary forms, with or without
	- * modification, are permitted provided that the following conditions
	- * are met:
	- * 1. Redistributions of source code must retain the above copyright
	- * notice, this list of conditions and the following disclaimer.
	- * 2. Redistributions in binary form must reproduce the above copyright
	- * notice, this list of conditions and the following disclaimer in the
	- * documentation and/or other materials provided with the distribution.
	- *
	- * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
	- * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
	- * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
	- * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
	- * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
	- * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
	- * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
	- * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
	- * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
	- * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
	- * SUCH DAMAGE.
	- */
	-
	-#ifndef _MACHINE_RUNQ_H_
	-#define _MACHINE_RUNQ_H_
	-
	-#define RQB_LEN (2) /* Number of priority status words. */
	-#define RQB_L2BPW (5) /* Log2(sizeof(rqb_word_t) * NBBY)). */
	-#define RQB_BPW (1<<RQB_L2BPW) /* Bits in an rqb_word_t. */
	-
	-#define RQB_BIT(pri) (1 << ((pri) & (RQB_BPW - 1)))
	-#define RQB_WORD(pri) ((pri) >> RQB_L2BPW)
	-
	-#define RQB_FFS(word) (ffs(word) - 1)
	-
	-/*
	- * Type of run queue status word.
	- */
	-typedef u_int32_t rqb_word_t;
	-
	-#endif
	diff --git a/sys/arm64/include/runq.h b/sys/arm64/include/runq.h
	deleted file mode 100644
	--- a/sys/arm64/include/runq.h
	+++ /dev/null
	@@ -1,50 +0,0 @@
	-/*-
	- * Copyright (c) 2001 Jake Burkholder <jake@FreeBSD.org>
	- * All rights reserved.
	- *
	- * Redistribution and use in source and binary forms, with or without
	- * modification, are permitted provided that the following conditions
	- * are met:
	- * 1. Redistributions of source code must retain the above copyright
	- * notice, this list of conditions and the following disclaimer.
	- * 2. Redistributions in binary form must reproduce the above copyright
	- * notice, this list of conditions and the following disclaimer in the
	- * documentation and/or other materials provided with the distribution.
	- *
	- * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
	- * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
	- * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
	- * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
	- * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
	- * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
	- * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
	- * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
	- * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
	- * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
	- * SUCH DAMAGE.
	- */
	-
	-#ifdef __arm__
	-#include <arm/runq.h>
	-#else /* !__arm__ */
	-
	-#ifndef _MACHINE_RUNQ_H_
	-#define _MACHINE_RUNQ_H_
	-
	-#define RQB_LEN (1) /* Number of priority status words. */
	-#define RQB_L2BPW (6) /* Log2(sizeof(rqb_word_t) * NBBY)). */
	-#define RQB_BPW (1<<RQB_L2BPW) /* Bits in an rqb_word_t. */
	-
	-#define RQB_BIT(pri) (1ul << ((pri) & (RQB_BPW - 1)))
	-#define RQB_WORD(pri) ((pri) >> RQB_L2BPW)
	-
	-#define RQB_FFS(word) (ffsl(word) - 1)
	-
	-/*
	- * Type of run queue status word.
	- */
	-typedef unsigned long rqb_word_t;
	-
	-#endif
	-
	-#endif /* !__arm__ */
	diff --git a/sys/dev/usb/usb_process.h b/sys/dev/usb/usb_process.h
	--- a/sys/dev/usb/usb_process.h
	+++ b/sys/dev/usb/usb_process.h
	@@ -31,7 +31,6 @@
	#ifndef USB_GLOBAL_INCLUDE_FILE
	#include <sys/interrupt.h>
	#include <sys/priority.h>
	-#include <sys/runq.h>
	#endif

	/* defines */
	diff --git a/sys/i386/include/runq.h b/sys/i386/include/runq.h
	deleted file mode 100644
	--- a/sys/i386/include/runq.h
	+++ /dev/null
	@@ -1,46 +0,0 @@
	-/*-
	- * SPDX-License-Identifier: BSD-2-Clause
	- *
	- * Copyright (c) 2001 Jake Burkholder <jake@FreeBSD.org>
	- * All rights reserved.
	- *
	- * Redistribution and use in source and binary forms, with or without
	- * modification, are permitted provided that the following conditions
	- * are met:
	- * 1. Redistributions of source code must retain the above copyright
	- * notice, this list of conditions and the following disclaimer.
	- * 2. Redistributions in binary form must reproduce the above copyright
	- * notice, this list of conditions and the following disclaimer in the
	- * documentation and/or other materials provided with the distribution.
	- *
	- * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
	- * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
	- * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
	- * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
	- * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
	- * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
	- * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
	- * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
	- * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
	- * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
	- * SUCH DAMAGE.
	- */
	-
	-#ifndef _MACHINE_RUNQ_H_
	-#define _MACHINE_RUNQ_H_
	-
	-#define RQB_LEN (2) /* Number of priority status words. */
	-#define RQB_L2BPW (5) /* Log2(sizeof(rqb_word_t) * NBBY)). */
	-#define RQB_BPW (1<<RQB_L2BPW) /* Bits in an rqb_word_t. */
	-
	-#define RQB_BIT(pri) (1 << ((pri) & (RQB_BPW - 1)))
	-#define RQB_WORD(pri) ((pri) >> RQB_L2BPW)
	-
	-#define RQB_FFS(word) (ffs(word) - 1)
	-
	-/*
	- * Type of run queue status word.
	- */
	-typedef u_int32_t rqb_word_t;
	-
	-#endif
	diff --git a/sys/kern/kern_switch.c b/sys/kern/kern_switch.c
	--- a/sys/kern/kern_switch.c
	+++ b/sys/kern/kern_switch.c
	@@ -38,6 +38,7 @@
	#include <sys/mutex.h>
	#include <sys/proc.h>
	#include <sys/queue.h>
	+#include <sys/runq.h>
	#include <sys/sched.h>
	#include <sys/smp.h>
	#include <sys/sysctl.h>
	@@ -57,8 +58,6 @@
	#endif
	#endif

	-CTASSERT((RQB_BPW * RQB_LEN) == RQ_NQS);
	-
	/*
	* kern.sched.preemption allows user space to determine if preemption support
	* is compiled in or not. It is not currently a boot or runtime flag that
	@@ -253,6 +252,33 @@
	/************************************************************************
	* SYSTEM RUN QUEUE manipulations and tests *
	************************************************************************/
	+_Static_assert(RQ_NQS <= 256,
	+ "'td_rqindex' must be turned into a bigger unsigned type");
	+/* A macro instead of a function to get the proper calling function's name. */
	+#define CHECK_IDX(idx) ({ \
	+ __typeof(idx) _idx __unused = (idx); \
	+ KASSERT(0 <= _idx && _idx < RQ_NQS, \
	+ ("%s: %s out of range: %d", __func__, __STRING(idx), _idx)); \
	+})
	+
	+/* Status words' individual bit manipulators' internals. */
	+typedef uintptr_t runq_sw_op(int idx, int sw_idx, rqsw_t sw_bit,
	+ rqsw_t *swp);
	+static inline uintptr_t runq_sw_apply(struct runq *rq, int idx,
	+ runq_sw_op *op);
	+
	+static inline uintptr_t runq_sw_set_not_empty_op(int idx, int sw_idx,
	+ rqsw_t sw_bit, rqsw_t *swp);
	+static inline uintptr_t runq_sw_set_empty_op(int idx, int sw_idx,
	+ rqsw_t sw_bit, rqsw_t *swp);
	+static inline uintptr_t runq_sw_is_empty_op(int idx, int sw_idx,
	+ rqsw_t sw_bit, rqsw_t *swp);
	+
	+/* Status words' individual bit manipulators. */
	+static inline void runq_sw_set_not_empty(struct runq *rq, int idx);
	+static inline void runq_sw_set_empty(struct runq *rq, int idx);
	+static inline bool runq_sw_is_empty(struct runq *rq, int idx);
	+
	/*
	* Initialize a run structure.
	*/
	@@ -261,98 +287,103 @@
	{
	int i;

	- bzero(rq, sizeof *rq);
	+ bzero(rq, sizeof(*rq));
	for (i = 0; i < RQ_NQS; i++)
	TAILQ_INIT(&rq->rq_queues[i]);
	}

	/*
	- * Clear the status bit of the queue corresponding to priority level pri,
	- * indicating that it is empty.
	+ * Helper to implement functions operating on a particular status word bit.
	+ *
	+ * The operator is passed the initial 'idx', the corresponding status word index
	+ * in 'rq_status' in 'sw_idx', a status word with only that bit set in 'sw_bit'
	+ * and a pointer to the corresponding status word in 'swp'.
	*/
	-static __inline void
	-runq_clrbit(struct runq *rq, int pri)
	+static inline uintptr_t
	+runq_sw_apply(struct runq rq, int idx, runq_sw_op op)
	{
	- struct rqbits *rqb;
	+ rqsw_t *swp;
	+ rqsw_t sw_bit;
	+ int sw_idx;

	- rqb = &rq->rq_status;
	- CTR4(KTR_RUNQ, "runq_clrbit: bits=%#x %#x bit=%#x word=%d",
	- rqb->rqb_bits[RQB_WORD(pri)],
	- rqb->rqb_bits[RQB_WORD(pri)] & ~RQB_BIT(pri),
	- RQB_BIT(pri), RQB_WORD(pri));
	- rqb->rqb_bits[RQB_WORD(pri)] &= ~RQB_BIT(pri);
	+ CHECK_IDX(idx);
	+
	+ sw_idx = RQSW_IDX(idx);
	+ sw_bit = RQSW_BIT(idx);
	+ swp = &rq->rq_status.rq_sw[sw_idx];
	+
	+ return (op(idx, sw_idx, sw_bit, swp));
	+}
	+
	+static inline uintptr_t
	+runq_sw_set_not_empty_op(int idx, int sw_idx, rqsw_t sw_bit, rqsw_t *swp)
	+{
	+ rqsw_t old_sw __unused = *swp;
	+
	+ *swp \|= sw_bit;
	+ CTR4(KTR_RUNQ, "runq_sw_set_not_empty: idx=%d sw_idx=%d bits=%#x->%#x",
	+ idx, sw_idx, old_sw, *swp);
	+ return (0);
	}

	/*
	- * Find the index of the first non-empty run queue. This is done by
	- * scanning the status bits, a set bit indicates a non-empty queue.
	+ * Modify the status words to indicate that some queue is not empty.
	+ *
	+ * Sets the status bit corresponding to the queue at index 'idx'.
	*/
	-static __inline int
	-runq_findbit(struct runq *rq)
	+static inline void
	+runq_sw_set_not_empty(struct runq *rq, int idx)
	{
	- struct rqbits *rqb;
	- int pri;
	- int i;

	- rqb = &rq->rq_status;
	- for (i = 0; i < RQB_LEN; i++)
	- if (rqb->rqb_bits[i]) {
	- pri = RQB_FFS(rqb->rqb_bits[i]) + (i << RQB_L2BPW);
	- CTR3(KTR_RUNQ, "runq_findbit: bits=%#x i=%d pri=%d",
	- rqb->rqb_bits[i], i, pri);
	- return (pri);
	- }
	-
	- return (-1);
	+ (void)runq_sw_apply(rq, idx, &runq_sw_set_not_empty_op);
	}

	-static __inline int
	-runq_findbit_from(struct runq *rq, u_char pri)
	+static inline uintptr_t
	+runq_sw_set_empty_op(int idx, int sw_idx, rqsw_t sw_bit, rqsw_t *swp)
	{
	- struct rqbits *rqb;
	- rqb_word_t mask;
	- int i;
	+ rqsw_t old_sw __unused = *swp;

	- /*
	- * Set the mask for the first word so we ignore priorities before 'pri'.
	- */
	- mask = (rqb_word_t)-1 << (pri & (RQB_BPW - 1));
	- rqb = &rq->rq_status;
	-again:
	- for (i = RQB_WORD(pri); i < RQB_LEN; mask = -1, i++) {
	- mask = rqb->rqb_bits[i] & mask;
	- if (mask == 0)
	- continue;
	- pri = RQB_FFS(mask) + (i << RQB_L2BPW);
	- CTR3(KTR_RUNQ, "runq_findbit_from: bits=%#x i=%d pri=%d",
	- mask, i, pri);
	- return (pri);
	- }
	- if (pri == 0)
	- return (-1);
	- /*
	- * Wrap back around to the beginning of the list just once so we
	- * scan the whole thing.
	- */
	- pri = 0;
	- goto again;
	+ *swp &= ~sw_bit;
	+ CTR4(KTR_RUNQ, "runq_sw_set_empty: idx=%d sw_idx=%d bits=%#x->%#x",
	+ idx, sw_idx, old_sw, *swp);
	+ return (0);
	}

	/*
	- * Set the status bit of the queue corresponding to priority level pri,
	- * indicating that it is non-empty.
	+ * Modify the status words to indicate that some queue is empty.
	+ *
	+ * Clears the status bit corresponding to the queue at index 'idx'.
	*/
	-static __inline void
	-runq_setbit(struct runq *rq, int pri)
	+static inline void
	+runq_sw_set_empty(struct runq *rq, int idx)
	{
	- struct rqbits *rqb;

	- rqb = &rq->rq_status;
	- CTR4(KTR_RUNQ, "runq_setbit: bits=%#x %#x bit=%#x word=%d",
	- rqb->rqb_bits[RQB_WORD(pri)],
	- rqb->rqb_bits[RQB_WORD(pri)] \| RQB_BIT(pri),
	- RQB_BIT(pri), RQB_WORD(pri));
	- rqb->rqb_bits[RQB_WORD(pri)] \|= RQB_BIT(pri);
	+ (void)runq_sw_apply(rq, idx, &runq_sw_set_empty_op);
	+}
	+
	+static inline uintptr_t
	+runq_sw_is_empty_op(int idx, int sw_idx, rqsw_t sw_bit, rqsw_t *swp)
	+{
	+ return ((*swp & sw_bit) == 0);
	+}
	+
	+/*
	+ * Returns whether the status words indicate that some queue is empty.
	+ */
	+static inline bool
	+runq_sw_is_empty(struct runq *rq, int idx)
	+{
	+ return (runq_sw_apply(rq, idx, &runq_sw_is_empty_op));
	+}
	+
	+/*
	+ * Returns whether a particular queue is empty.
	+ */
	+bool
	+runq_is_queue_empty(struct runq *rq, int idx)
	+{
	+
	+ return (runq_sw_is_empty(rq, idx));
	}

	/*
	@@ -362,102 +393,186 @@
	void
	runq_add(struct runq rq, struct thread td, int flags)
	{
	- struct rqhead *rqh;
	- int pri;

	- pri = td->td_priority / RQ_PPQ;
	- td->td_rqindex = pri;
	- runq_setbit(rq, pri);
	- rqh = &rq->rq_queues[pri];
	- CTR4(KTR_RUNQ, "runq_add: td=%p pri=%d %d rqh=%p",
	- td, td->td_priority, pri, rqh);
	- if (flags & SRQ_PREEMPTED) {
	- TAILQ_INSERT_HEAD(rqh, td, td_runq);
	- } else {
	- TAILQ_INSERT_TAIL(rqh, td, td_runq);
	- }
	+ runq_add_idx(rq, td, RQ_PRI_TO_QUEUE_IDX(td->td_priority), flags);
	}

	void
	-runq_add_pri(struct runq rq, struct thread td, u_char pri, int flags)
	+runq_add_idx(struct runq rq, struct thread td, int idx, int flags)
	{
	- struct rqhead *rqh;
	+ struct rq_queue *rqq;

	- KASSERT(pri < RQ_NQS, ("runq_add_pri: %d out of range", pri));
	- td->td_rqindex = pri;
	- runq_setbit(rq, pri);
	- rqh = &rq->rq_queues[pri];
	- CTR4(KTR_RUNQ, "runq_add_pri: td=%p pri=%d idx=%d rqh=%p",
	- td, td->td_priority, pri, rqh);
	- if (flags & SRQ_PREEMPTED) {
	- TAILQ_INSERT_HEAD(rqh, td, td_runq);
	- } else {
	- TAILQ_INSERT_TAIL(rqh, td, td_runq);
	- }
	+ /*
	+ * runq_sw_*() functions assert that 'idx' is non-negative and below
	+ * 'RQ_NQS', and a static assert earlier in this file ensures that
	+ * 'RQ_NQS' is no more than 256.
	+ */
	+ td->td_rqindex = idx;
	+ runq_sw_set_not_empty(rq, idx);
	+ 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(rqq, td, td_runq);
	+ else
	+ TAILQ_INSERT_TAIL(rqq, td, td_runq);
	}
	+
	/*
	- * Return true if there are runnable processes of any priority on the run
	- * queue, false otherwise. Has no side effects, does not modify the run
	- * queue structure.
	+ * Remove the thread from the queue specified by its priority, and clear the
	+ * corresponding status bit if the queue becomes empty.
	+ *
	+ * Returns whether the corresponding queue is empty after removal.
	+ */
	+bool
	+runq_remove(struct runq rq, struct thread td)
	+{
	+ struct rq_queue *rqq;
	+ int idx;
	+
	+ KASSERT(td->td_flags & TDF_INMEM, ("runq_remove: Thread swapped out"));
	+ idx = td->td_rqindex;
	+ CHECK_IDX(idx);
	+ 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_sw_set_empty(rq, idx);
	+ CTR1(KTR_RUNQ, "runq_remove: queue at idx=%d now empty", idx);
	+ return (true);
	+ }
	+ return (false);
	+}
	+
	+static inline int
	+runq_findq_status_word(struct runq *const rq, const int w_idx,
	+ const rqsw_t w, runq_pred_t const pred, void const pred_data)
	+{
	+ struct rq_queue *q;
	+ rqsw_t tw = w;
	+ int idx, b_idx;
	+
	+ while (tw != 0) {
	+ b_idx = RQSW_BSF(tw);
	+ idx = RQSW_TO_QUEUE_IDX(w_idx, b_idx);
	+ q = &rq->rq_queues[idx];
	+ KASSERT(!TAILQ_EMPTY(q),
	+ ("runq_findq(): No thread on non-empty queue with idx=%d",
	+ idx));
	+ if (pred(idx, q, pred_data))
	+ return (idx);
	+ tw &= ~RQSW_BIT(idx);
	+ }
	+
	+ return (-1);
	+}
	+
	+/*
	+ * Find in the passed range (bounds included) the index of the first (i.e.,
	+ * having lower index) non-empty queue that passes pred().
	+ *
	+ * Considered queues are those with index 'lvl_min' up to 'lvl_max' (bounds
	+ * included). If no queue matches, returns -1.
	+ *
	+ * This is done by scanning the status words (a set bit indicates a non-empty
	+ * queue) and calling pred() with corresponding queue indices. pred() must
	+ * return whether the corresponding queue is accepted. It is passed private
	+ * data through 'pred_data', which can be used both for extra input and output.
	*/
	int
	-runq_check(struct runq *rq)
	+runq_findq(struct runq *const rq, const int lvl_min, const int lvl_max,
	+ runq_pred_t const pred, void const pred_data)
	{
	- struct rqbits *rqb;
	- int i;
	+ rqsw_t const (*const rqsw)[RQSW_NB] = &rq->rq_status.rq_sw;
	+ rqsw_t w;
	+ int i, last, idx;

	- rqb = &rq->rq_status;
	- for (i = 0; i < RQB_LEN; i++)
	- if (rqb->rqb_bits[i]) {
	- CTR2(KTR_RUNQ, "runq_check: bits=%#x i=%d",
	- rqb->rqb_bits[i], i);
	- return (1);
	- }
	- CTR0(KTR_RUNQ, "runq_check: empty");
	+ CHECK_IDX(lvl_min);
	+ CHECK_IDX(lvl_max);
	+ KASSERT(lvl_min <= lvl_max,
	+ ("lvl_min: %d > lvl_max: %d!", lvl_min, lvl_max));

	- return (0);
	+ i = RQSW_IDX(lvl_min);
	+ last = RQSW_IDX(lvl_max);
	+ /* Clear bits for runqueues below 'lvl_min'. */
	+ w = (*rqsw)[i] & ~(RQSW_BIT(lvl_min) - 1);
	+ if (i == last)
	+ goto last_mask;
	+ idx = runq_findq_status_word(rq, i, w, pred, pred_data);
	+ if (idx != -1)
	+ goto return_idx;
	+
	+ for (++i; i < last; ++i) {
	+ w = (*rqsw)[i];
	+ idx = runq_findq_status_word(rq, i, w, pred, pred_data);
	+ if (idx != -1)
	+ goto return_idx;
	+ }
	+
	+ MPASS(i == last);
	+ w = (*rqsw)[i];
	+last_mask:
	+ /* Clear bits for runqueues above 'lvl_max'. */
	+ w &= (RQSW_BIT(lvl_max) - 1) \| RQSW_BIT(lvl_max);
	+ idx = runq_findq_status_word(rq, i, w, pred, pred_data);
	+ if (idx != -1)
	+ goto return_idx;
	+ return (-1);
	+return_idx:
	+ CTR4(KTR_RUNQ, "runq_findq: bits=%#x->%#x i=%d idx=%d",
	+ (*rqsw)[i], w, i, idx);
	+ return (idx);
	+}
	+
	+static bool
	+runq_first_thread_pred(const int idx, struct rq_queue const q, void const data)
	+{
	+ struct thread **const tdp = data;
	+ struct thread *const td = TAILQ_FIRST(q);
	+
	+ *tdp = td;
	+ return (true);
	}

	/*
	- * Find the highest priority process on the run queue.
	+ * Inline this function for the benefit of this file's internal uses, but make
	+ * sure it has an external definition as it is exported.
	*/
	-struct thread *
	-runq_choose_fuzz(struct runq *rq, int fuzz)
	+extern inline struct thread *
	+runq_first_thread_range(struct runq *const rq, const int lvl_min,
	+ const int lvl_max)
	{
	- struct rqhead *rqh;
	- struct thread *td;
	- int pri;
	+ struct thread *td = NULL;

	- while ((pri = runq_findbit(rq)) != -1) {
	- rqh = &rq->rq_queues[pri];
	- /* fuzz == 1 is normal.. 0 or less are ignored */
	- if (fuzz > 1) {
	- /*
	- * In the first couple of entries, check if
	- * there is one for our CPU as a preference.
	- */
	- int count = fuzz;
	- int cpu = PCPU_GET(cpuid);
	- struct thread *td2;
	- td2 = td = TAILQ_FIRST(rqh);
	+ (void)runq_findq(rq, lvl_min, lvl_max, runq_first_thread_pred, &td);
	+ return (td);
	+}

	- while (count-- && td2) {
	- if (td2->td_lastcpu == cpu) {
	- td = td2;
	- break;
	- }
	- td2 = TAILQ_NEXT(td2, td_runq);
	- }
	- } else
	- td = TAILQ_FIRST(rqh);
	- KASSERT(td != NULL, ("runq_choose_fuzz: no proc on busy queue"));
	- CTR3(KTR_RUNQ,
	- "runq_choose_fuzz: pri=%d thread=%p rqh=%p", pri, td, rqh);
	- return (td);
	+static inline struct thread *
	+runq_first_thread(struct runq *const rq)
	+{
	+
	+ return (runq_first_thread_range(rq, 0, RQ_NQS - 1));
	+}
	+
	+/*
	+ * Return true if there are some processes of any priority on the run queue,
	+ * false otherwise. Has no side effects.
	+ */
	+bool
	+runq_not_empty(struct runq *rq)
	+{
	+ struct thread *const td = runq_first_thread(rq);
	+
	+ if (td != NULL) {
	+ CTR2(KTR_RUNQ, "runq_not_empty: idx=%d, td=%p",
	+ td->td_rqindex, td);
	+ return (true);
	}
	- CTR1(KTR_RUNQ, "runq_choose_fuzz: idleproc pri=%d", pri);

	- return (NULL);
	+ CTR0(KTR_RUNQ, "runq_not_empty: empty");
	+ return (false);
	}

	/*
	@@ -466,73 +581,85 @@
	struct thread *
	runq_choose(struct runq *rq)
	{
	- struct rqhead *rqh;
	struct thread *td;
	- int pri;

	- while ((pri = runq_findbit(rq)) != -1) {
	- rqh = &rq->rq_queues[pri];
	- td = TAILQ_FIRST(rqh);
	- KASSERT(td != NULL, ("runq_choose: no thread on busy queue"));
	- CTR3(KTR_RUNQ,
	- "runq_choose: pri=%d thread=%p rqh=%p", pri, td, rqh);
	+ td = runq_first_thread(rq);
	+ if (td != NULL) {
	+ CTR2(KTR_RUNQ, "runq_choose: idx=%d td=%p", td->td_rqindex, td);
	return (td);
	}
	- CTR1(KTR_RUNQ, "runq_choose: idlethread pri=%d", pri);

	+ CTR0(KTR_RUNQ, "runq_choose: idlethread");
	+ return (NULL);
	+}
	+
	+struct runq_fuzz_pred_data {
	+ int fuzz;
	+ struct thread *td;
	+};
	+
	+static bool
	+runq_fuzz_pred(const int idx, struct rq_queue const q, void const data)
	+{
	+ struct runq_fuzz_pred_data *const d = data;
	+ const int fuzz = d->fuzz;
	+ struct thread *td;
	+
	+ td = TAILQ_FIRST(q);
	+
	+ if (fuzz > 1) {
	+ /*
	+ * In the first couple of entries, check if
	+ * there is one for our CPU as a preference.
	+ */
	+ struct thread *td2 = td;
	+ int count = fuzz;
	+ int cpu = PCPU_GET(cpuid);
	+
	+ while (count-- != 0 && td2 != NULL) {
	+ if (td2->td_lastcpu == cpu) {
	+ td = td2;
	+ break;
	+ }
	+ td2 = TAILQ_NEXT(td2, td_runq);
	+ }
	+ }
	+
	+ d->td = td;
	+ return (true);
	+}
	+
	+/*
	+ * Find the highest priority process on the run queue.
	+ */
	+struct thread *
	+runq_choose_fuzz(struct runq *rq, int fuzz)
	+{
	+ struct runq_fuzz_pred_data data = {
	+ .fuzz = fuzz,
	+ .td = NULL
	+ };
	+ int idx;
	+
	+ idx = runq_findq(rq, 0, RQ_NQS - 1, runq_fuzz_pred, &data);
	+ if (idx != -1) {
	+ MPASS(data.td != NULL);
	+ CTR2(KTR_RUNQ, "runq_choose_fuzz: idx=%d td=%p", idx, data.td);
	+ return (data.td);
	+ }
	+
	+ MPASS(data.td == NULL);
	+ CTR0(KTR_RUNQ, "runq_choose_fuzz: idlethread");
	return (NULL);
	}

	struct thread *
	-runq_choose_from(struct runq *rq, u_char idx)
	+runq_choose_from(struct runq *const rq, int from_idx)
	{
	- struct rqhead *rqh;
	struct thread *td;
	- int pri;

	- if ((pri = runq_findbit_from(rq, idx)) != -1) {
	- rqh = &rq->rq_queues[pri];
	- td = TAILQ_FIRST(rqh);
	- KASSERT(td != NULL, ("runq_choose: no thread on busy queue"));
	- CTR4(KTR_RUNQ,
	- "runq_choose_from: pri=%d thread=%p idx=%d rqh=%p",
	- pri, td, td->td_rqindex, rqh);
	+ td = runq_first_thread_range(rq, from_idx, RQ_NQS - 1);
	+ if (td != NULL \|\| from_idx == 0)
	return (td);
	- }
	- CTR1(KTR_RUNQ, "runq_choose_from: idlethread pri=%d", pri);
	-
	- return (NULL);
	-}
	-/*
	- * Remove the thread from the queue specified by its priority, and clear the
	- * corresponding status bit if the queue becomes empty.
	- * Caller must set state afterwards.
	- */
	-void
	-runq_remove(struct runq rq, struct thread td)
	-{
	-
	- runq_remove_idx(rq, td, NULL);
	-}
	-
	-void
	-runq_remove_idx(struct runq rq, struct thread td, u_char *idx)
	-{
	- struct rqhead *rqh;
	- u_char pri;
	-
	- KASSERT(td->td_flags & TDF_INMEM,
	- ("runq_remove_idx: thread swapped out"));
	- pri = td->td_rqindex;
	- KASSERT(pri < RQ_NQS, ("runq_remove_idx: Invalid index %d\n", pri));
	- rqh = &rq->rq_queues[pri];
	- CTR4(KTR_RUNQ, "runq_remove_idx: td=%p, pri=%d %d rqh=%p",
	- td, td->td_priority, pri, rqh);
	- TAILQ_REMOVE(rqh, td, td_runq);
	- if (TAILQ_EMPTY(rqh)) {
	- CTR0(KTR_RUNQ, "runq_remove_idx: empty");
	- runq_clrbit(rq, pri);
	- if (idx != NULL && *idx == pri)
	- *idx = (pri + 1) % RQ_NQS;
	- }
	+ return (runq_first_thread_range(rq, 0, from_idx - 1));
	}
	diff --git a/sys/kern/sched_4bsd.c b/sys/kern/sched_4bsd.c
	--- a/sys/kern/sched_4bsd.c
	+++ b/sys/kern/sched_4bsd.c
	@@ -48,6 +48,7 @@
	#include <sys/mutex.h>
	#include <sys/proc.h>
	#include <sys/resourcevar.h>
	+#include <sys/runq.h>
	#include <sys/sched.h>
	#include <sys/sdt.h>
	#include <sys/smp.h>
	@@ -683,13 +684,14 @@
	/* Nothing needed. */
	}

	-int
	+bool
	sched_runnable(void)
	{
	#ifdef SMP
	- return runq_check(&runq) + runq_check(&runq_pcpu[PCPU_GET(cpuid)]);
	+ return (runq_not_empty(&runq) \|\|
	+ runq_not_empty(&runq_pcpu[PCPU_GET(cpuid)]));
	#else
	- return runq_check(&runq);
	+ return (runq_not_empty(&runq));
	#endif
	}

	@@ -871,7 +873,7 @@
	if (td->td_priority == prio)
	return;
	td->td_priority = prio;
	- if (TD_ON_RUNQ(td) && td->td_rqindex != (prio / RQ_PPQ)) {
	+ if (TD_ON_RUNQ(td) && td->td_rqindex != RQ_PRI_TO_QUEUE_IDX(prio)) {
	sched_rem(td);
	sched_add(td, SRQ_BORING \| SRQ_HOLDTD);
	}
	@@ -1679,7 +1681,7 @@
	for (;;) {
	mtx_assert(&Giant, MA_NOTOWNED);

	- while (sched_runnable() == 0) {
	+ while (!sched_runnable()) {
	cpu_idle(stat->idlecalls + stat->oldidlecalls > 64);
	stat->idlecalls++;
	}
	diff --git a/sys/kern/sched_ule.c b/sys/kern/sched_ule.c
	--- a/sys/kern/sched_ule.c
	+++ b/sys/kern/sched_ule.c
	@@ -52,6 +52,7 @@
	#include <sys/proc.h>
	#include <sys/resource.h>
	#include <sys/resourcevar.h>
	+#include <sys/runq.h>
	#include <sys/sched.h>
	#include <sys/sdt.h>
	#include <sys/smp.h>
	@@ -386,20 +387,20 @@
	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_L2BPW);
	- 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);
	@@ -513,14 +514,14 @@
	pri = (unsigned char)(pri - 1) % RQ_NQS;
	} else
	pri = tdq->tdq_ridx;
	- runq_add_pri(ts->ts_runq, td, pri, flags);
	+ runq_add_idx(ts->ts_runq, td, pri, flags);
	return;
	} else
	ts->ts_runq = &tdq->tdq_idle;
	runq_add(ts->ts_runq, td, flags);
	}

	-/*
	+/*
	* Remove a thread from a run-queue. This typically happens when a thread
	* is selected to run. Running threads are not on the queue and the
	* transferable count does not reflect them.
	@@ -529,6 +530,7 @@
	tdq_runq_rem(struct tdq tdq, struct thread td)
	{
	struct td_sched *ts;
	+ bool queue_empty;

	ts = td_get_sched(td);
	TDQ_LOCK_ASSERT(tdq, MA_OWNED);
	@@ -539,13 +541,16 @@
	tdq->tdq_transferable--;
	ts->ts_flags &= ~TSF_XFERABLE;
	}
	- if (ts->ts_runq == &tdq->tdq_timeshare) {
	- if (tdq->tdq_idx != tdq->tdq_ridx)
	- runq_remove_idx(ts->ts_runq, td, &tdq->tdq_ridx);
	- else
	- runq_remove_idx(ts->ts_runq, td, NULL);
	- } else
	- runq_remove(ts->ts_runq, td);
	+ queue_empty = runq_remove(ts->ts_runq, td);
	+ /*
	+ * If thread has a batch priority and the queue from which it was
	+ * removed is now empty, advance the batch's queue removal index if it
	+ * lags with respect to the batch's queue insertion index.
	+ */
	+ if (queue_empty && PRI_MIN_BATCH <= td->td_priority &&
	+ td->td_priority <= PRI_MAX_BATCH &&
	+ tdq->tdq_idx != tdq->tdq_ridx && tdq->tdq_ridx == td->td_rqindex)
	+ tdq->tdq_ridx = (tdq->tdq_ridx + 1) % RQ_NQS;
	}

	/*
	@@ -1185,26 +1190,26 @@
	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_L2BPW)];
	- 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))
	@@ -1231,21 +1236,21 @@
	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_L2BPW)];
	- 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);
	@@ -2597,7 +2602,7 @@
	*/
	if (tdq->tdq_idx == tdq->tdq_ridx) {
	tdq->tdq_idx = (tdq->tdq_idx + 1) % RQ_NQS;
	- if (TAILQ_EMPTY(&tdq->tdq_timeshare.rq_queues[tdq->tdq_ridx]))
	+ if (runq_is_queue_empty(&tdq->tdq_timeshare, tdq->tdq_ridx))
	tdq->tdq_ridx = tdq->tdq_idx;
	}
	ts = td_get_sched(td);
	@@ -2652,24 +2657,20 @@
	* Return whether the current CPU has runnable tasks. Used for in-kernel
	* cooperative idle threads.
	*/
	-int
	+bool
	sched_runnable(void)
	{
	struct tdq *tdq;
	- int load;
	-
	- load = 1;

	tdq = TDQ_SELF();
	if ((curthread->td_flags & TDF_IDLETD) != 0) {
	if (TDQ_LOAD(tdq) > 0)
	- goto out;
	+ return (true);
	} else
	if (TDQ_LOAD(tdq) - 1 > 0)
	- goto out;
	- load = 0;
	-out:
	- return (load);
	+ return (true);
	+
	+ return (false);
	}

	/*
	diff --git a/sys/powerpc/include/runq.h b/sys/powerpc/include/runq.h
	deleted file mode 100644
	--- a/sys/powerpc/include/runq.h
	+++ /dev/null
	@@ -1,55 +0,0 @@
	-/*-
	- * SPDX-License-Identifier: BSD-2-Clause
	- *
	- * Copyright (c) 2001 Jake Burkholder <jake@FreeBSD.org>
	- * All rights reserved.
	- *
	- * Redistribution and use in source and binary forms, with or without
	- * modification, are permitted provided that the following conditions
	- * are met:
	- * 1. Redistributions of source code must retain the above copyright
	- * notice, this list of conditions and the following disclaimer.
	- * 2. Redistributions in binary form must reproduce the above copyright
	- * notice, this list of conditions and the following disclaimer in the
	- * documentation and/or other materials provided with the distribution.
	- *
	- * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
	- * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
	- * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
	- * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
	- * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
	- * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
	- * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
	- * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
	- * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
	- * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
	- * SUCH DAMAGE.
	- */
	-
	-#ifndef _MACHINE_RUNQ_H_
	-#define _MACHINE_RUNQ_H_
	-
	-#ifdef __powerpc64__
	-#define RQB_LEN (1UL) /* Number of priority status words. */
	-#define RQB_L2BPW (6UL) /* Log2(sizeof(rqb_word_t) * NBBY)). */
	-#else
	-#define RQB_LEN (2) /* Number of priority status words. */
	-#define RQB_L2BPW (5) /* Log2(sizeof(rqb_word_t) * NBBY)). */
	-#endif
	-#define RQB_BPW (1UL<<RQB_L2BPW) /* Bits in an rqb_word_t. */
	-
	-#define RQB_BIT(pri) (1UL << ((pri) & (RQB_BPW - 1)))
	-#define RQB_WORD(pri) ((pri) >> RQB_L2BPW)
	-
	-#define RQB_FFS(word) (ffsl(word) - 1)
	-
	-/*
	- * Type of run queue status word.
	- */
	-#ifdef __powerpc64__
	-typedef u_int64_t rqb_word_t;
	-#else
	-typedef u_int32_t rqb_word_t;
	-#endif
	-
	-#endif
	diff --git a/sys/riscv/include/runq.h b/sys/riscv/include/runq.h
	deleted file mode 100644
	--- a/sys/riscv/include/runq.h
	+++ /dev/null
	@@ -1,44 +0,0 @@
	-/*-
	- * Copyright (c) 2001 Jake Burkholder <jake@FreeBSD.org>
	- * All rights reserved.
	- *
	- * Redistribution and use in source and binary forms, with or without
	- * modification, are permitted provided that the following conditions
	- * are met:
	- * 1. Redistributions of source code must retain the above copyright
	- * notice, this list of conditions and the following disclaimer.
	- * 2. Redistributions in binary form must reproduce the above copyright
	- * notice, this list of conditions and the following disclaimer in the
	- * documentation and/or other materials provided with the distribution.
	- *
	- * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
	- * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
	- * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
	- * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
	- * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
	- * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
	- * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
	- * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
	- * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
	- * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
	- * SUCH DAMAGE.
	- */
	-
	-#ifndef _MACHINE_RUNQ_H_
	-#define _MACHINE_RUNQ_H_
	-
	-#define RQB_LEN (1) /* Number of priority status words. */
	-#define RQB_L2BPW (6) /* Log2(sizeof(rqb_word_t) * NBBY)). */
	-#define RQB_BPW (1<<RQB_L2BPW) /* Bits in an rqb_word_t. */
	-
	-#define RQB_BIT(pri) (1ul << ((pri) & (RQB_BPW - 1)))
	-#define RQB_WORD(pri) ((pri) >> RQB_L2BPW)
	-
	-#define RQB_FFS(word) (ffsl(word) - 1)
	-
	-/*
	- * Type of run queue status word.
	- */
	-typedef unsigned long rqb_word_t;
	-
	-#endif
	diff --git a/sys/sys/proc.h b/sys/sys/proc.h
	--- a/sys/sys/proc.h
	+++ b/sys/sys/proc.h
	@@ -53,7 +53,6 @@
	#include <sys/osd.h>
	#include <sys/priority.h>
	#include <sys/rtprio.h> /* XXX. */
	-#include <sys/runq.h>
	#include <sys/resource.h>
	#include <sys/sigio.h>
	#include <sys/signal.h>
	diff --git a/sys/sys/runq.h b/sys/sys/runq.h
	--- a/sys/sys/runq.h
	+++ b/sys/sys/runq.h
	@@ -29,28 +29,64 @@
	#ifndef _RUNQ_H_
	#define _RUNQ_H_

	-#include <machine/runq.h>
	-
	-struct thread;
	-
	/*
	* Run queue parameters.
	*/

	-#define RQ_NQS (64) /* Number of run queues. */
	-#define RQ_PPQ (4) /* Priorities per queue. */
	+#define RQ_MAX_PRIO (255) /* Maximum priority (minimum is 0). */
	+#define RQ_PPQ (4) /* Priorities per queue. */

	/*
	- * Head of run queues.
	+ * Convenience macros from <sys/param.h>.
	*/
	-TAILQ_HEAD(rqhead, thread);
	+#ifndef NBBY
	+#define NBBY 8
	+#endif
	+#ifndef howmany
	+#define howmany(x, y) (((x)+((y)-1))/(y))
	+#endif
	+
	+/*
	+ * Deduced from the above parameters and machine ones.
	+ */
	+#define RQ_NQS (howmany(RQ_MAX_PRIO + 1, RQ_PPQ)) /* Number of run queues. */
	+#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) ({ \
	+ 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
	+#include <sys/types.h> /* For bool. */
	+
	+struct thread;
	+
	+/*
	+ * The queue for a given index as a list of threads.
	+ */
	+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];
	};

	/*
	@@ -58,18 +94,31 @@
	* 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);
	-void runq_add_pri(struct runq , struct thread , u_char, int);
	-int runq_check(struct runq *);
	-struct thread runq_choose(struct runq );
	-struct thread runq_choose_from(struct runq , u_char);
	-struct thread runq_choose_fuzz(struct runq , int);
	void runq_init(struct runq *);
	-void runq_remove(struct runq , struct thread );
	-void runq_remove_idx(struct runq , struct thread , u_char *);
	+bool runq_is_queue_empty(struct runq *, int _idx);
	+void runq_add(struct runq , struct thread , int _flags);
	+void runq_add_idx(struct runq , struct thread , int _idx, int _flags);
	+bool runq_remove(struct runq , struct thread );
	+
	+/*
	+ * Implementation helpers for common and scheduler-specific runq_choose*()
	+ * functions.
	+ */
	+typedef bool runq_pred_t(int _idx, struct rq_queue , void _data);
	+int runq_findq(struct runq *const rq, const int lvl_min,
	+ const int lvl_max,
	+ runq_pred_t const pred, void const pred_data);
	+struct thread runq_first_thread_range(struct runq const rq,
	+ const int lvl_min, const int lvl_max);
	+
	+bool runq_not_empty(struct runq *);
	+struct thread runq_choose(struct runq );
	+struct thread runq_choose_fuzz(struct runq , int _fuzz);
	+struct thread runq_choose_from(struct runq , int _idx);
	+#endif /* _KERNEL */

	#endif
	diff --git a/sys/sys/sched.h b/sys/sys/sched.h
	--- a/sys/sys/sched.h
	+++ b/sys/sys/sched.h
	@@ -63,6 +63,9 @@
	#define _SCHED_H_

	#ifdef _KERNEL
	+
	+#include <sys/types.h> /* For bool. */
	+
	/*
	* General scheduling info.
	*
	@@ -74,7 +77,7 @@
	*/
	int sched_load(void);
	int sched_rr_interval(void);
	-int sched_runnable(void);
	+bool sched_runnable(void);

	/*
	* Proc related scheduling hooks.

File Metadata

Mime Type: text/plain
Expires: Sun, Sep 22, 11:41 AM (21 h, 34 m)
Storage Engine: blob
Storage Format: Raw Data
Storage Handle: 12448684
Default Alt Text: D45387.diff (40 KB)

D45387.diffNo OneTemporaryActions

D45387.diffView Options

File Metadata

Event Timeline

D45387.diff
No OneTemporary
Actions

D45387.diff
View Options