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 - * 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) - -#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 - * 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) - -#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 - * 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 -#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) - -#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 #include -#include #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 - * 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) - -#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 #include #include +#include #include #include #include @@ -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,35 @@ /************************************************************************ * SYSTEM RUN QUEUE manipulations and tests * ************************************************************************/ +_Static_assert(RQSW_BPW == (1 << RQSW_L2BPW), + "RQSW_L2BPW and RQSW_BPW / 'rqsw_t' mismatch"); +_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 +289,96 @@ { 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)); } /* - * 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 uintptr_t +runq_sw_set_not_empty_op(int idx, int sw_idx, rqsw_t sw_bit, rqsw_t *swp) { - struct rqbits *rqb; - int pri; - int i; + rqsw_t old_sw __unused = *swp; - 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); + *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); } - -static __inline int -runq_findbit_from(struct runq *rq, u_char pri) +static inline void +runq_sw_set_not_empty(struct runq *rq, int idx) { - struct rqbits *rqb; - rqb_word_t mask; - int i; - - /* - * 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; + (void)runq_sw_apply(rq, idx, &runq_sw_set_not_empty_op); } /* - * 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 uintptr_t +runq_sw_set_empty_op(int idx, int sw_idx, rqsw_t sw_bit, rqsw_t *swp) { - struct rqbits *rqb; + rqsw_t old_sw __unused = *swp; - 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); + *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); +} +static inline void +runq_sw_set_empty(struct runq *rq, int idx) +{ + (void)runq_sw_apply(rq, idx, &runq_sw_set_empty_op); +} + +/* + * Returns whether the status words indicate that some queue is empty. + */ +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); +} +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 +388,183 @@ 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 upper 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); +} + +/* Make sure it has an external definition. */ +extern inline struct thread * +runq_first_thread_range(struct runq *const rq, const int lvl_min, + const int lvl_max) +{ + struct thread *td = NULL; + + (void)runq_findq(rq, lvl_min, lvl_max, runq_first_thread_pred, &td); + return (td); +} + +static inline struct thread * +runq_first_thread(struct runq *const rq) +{ + + return (runq_first_thread_range(rq, 0, RQ_NQS - 1)); } /* - * Find the highest priority process on the run queue. + * Return true if there are some processes of any priority on the run queue, + * false otherwise. Has no side effects. */ -struct thread * -runq_choose_fuzz(struct runq *rq, int fuzz) +bool +runq_not_empty(struct runq *rq) { - struct rqhead *rqh; - struct thread *td; - int pri; + struct thread *const td = runq_first_thread(rq); - 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); - - 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); + 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 +573,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 #include #include +#include #include #include #include @@ -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); } @@ -1682,7 +1684,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 #include #include +#include #include #include #include @@ -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); @@ -2600,7 +2605,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); @@ -2655,24 +2660,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 - * 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) - -#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 - * 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) - -#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 #include #include /* XXX. */ -#include #include #include #include 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,74 @@ #ifndef _RUNQ_H_ #define _RUNQ_H_ -#include - -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 . */ -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. */ +#if defined(_LP64) +#define RQSW_L2BPW (6) /* Log2(sizeof(rqsw_t) * NBBY)). */ +#elif defined(_ILP32) +#define RQSW_L2BPW (5) /* Log2(sizeof(rqsw_t) * NBBY)). */ +#else +#error Not _LP64 nor _ILP32! +#endif +/* + * That RQSW_BPW and RQSW_L2BPW are consistent is checked by a static assertion. + */ + +/* Number of status words to cover RQ_NQS queues. */ +#define RQSW_NB (howmany(RQ_NQS, RQSW_BPW)) +#define RQSW_IDX(idx) ((idx) >> RQSW_L2BPW) +#define RQSW_BIT_IDX(idx) ((idx) & (RQSW_BPW - 1)) +#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_L2BPW) + (bit_idx)) +#define RQSW_FIRST_QUEUE_IDX(word_idx, word) \ + RQSW_TO_QUEUE_IDX(word_idx, RQSW_BSF(word)) + + +#ifdef _KERNEL +#include /* 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 +104,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 /* 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.