2 * Copyright (c) 2001 Jake Burkholder <jake@FreeBSD.org>
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
8 * 1. Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in the
12 * documentation and/or other materials provided with the distribution.
14 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
15 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
16 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
17 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
18 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
19 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
20 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
21 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
22 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
23 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
29 #include <sys/param.h>
30 #include <sys/systm.h>
31 #include <sys/kernel.h>
34 #include <sys/mutex.h>
36 #include <sys/queue.h>
37 #include <machine/critical.h>
42 static struct runq runq;
43 SYSINIT(runq, SI_SUB_RUN_QUEUE, SI_ORDER_FIRST, runq_init, &runq)
46 * Wrappers which implement old interface; act on global run queue.
52 return (runq_choose(&runq)->ke_thread);
58 return runq_check(&runq);
62 remrunqueue(struct thread *td)
64 runq_remove(&runq, td->td_kse);
68 setrunqueue(struct thread *td)
70 runq_add(&runq, td->td_kse);
73 /* Critical sections that prevent preemption. */
80 if (td->td_critnest == 0)
91 if (td->td_critnest == 1) {
100 * Clear the status bit of the queue corresponding to priority level pri,
101 * indicating that it is empty.
104 runq_clrbit(struct runq *rq, int pri)
108 rqb = &rq->rq_status;
109 CTR4(KTR_RUNQ, "runq_clrbit: bits=%#x %#x bit=%#x word=%d",
110 rqb->rqb_bits[RQB_WORD(pri)],
111 rqb->rqb_bits[RQB_WORD(pri)] & ~RQB_BIT(pri),
112 RQB_BIT(pri), RQB_WORD(pri));
113 rqb->rqb_bits[RQB_WORD(pri)] &= ~RQB_BIT(pri);
117 * Find the index of the first non-empty run queue. This is done by
118 * scanning the status bits, a set bit indicates a non-empty queue.
121 runq_findbit(struct runq *rq)
127 rqb = &rq->rq_status;
128 for (i = 0; i < RQB_LEN; i++)
129 if (rqb->rqb_bits[i]) {
130 pri = (RQB_FFS(rqb->rqb_bits[i]) - 1) +
132 CTR3(KTR_RUNQ, "runq_findbit: bits=%#x i=%d pri=%d",
133 rqb->rqb_bits[i], i, pri);
141 * Set the status bit of the queue corresponding to priority level pri,
142 * indicating that it is non-empty.
145 runq_setbit(struct runq *rq, int pri)
149 rqb = &rq->rq_status;
150 CTR4(KTR_RUNQ, "runq_setbit: bits=%#x %#x bit=%#x word=%d",
151 rqb->rqb_bits[RQB_WORD(pri)],
152 rqb->rqb_bits[RQB_WORD(pri)] | RQB_BIT(pri),
153 RQB_BIT(pri), RQB_WORD(pri));
154 rqb->rqb_bits[RQB_WORD(pri)] |= RQB_BIT(pri);
157 #if defined(INVARIANT_SUPPORT) && defined(DIAGNOSTIC)
159 * Return true if the specified process is already in the run queue.
162 runq_findproc(struct runq *rq, struct kse *ke)
167 mtx_assert(&sched_lock, MA_OWNED);
168 for (i = 0; i < RQB_LEN; i++)
169 TAILQ_FOREACH(ke2, &rq->rq_queues[i], ke_procq)
177 * Add the process to the queue specified by its priority, and set the
178 * corresponding status bit.
181 runq_add(struct runq *rq, struct kse *ke)
187 struct proc *p = ke->ke_proc;
189 if (ke->ke_flags & KEF_ONRUNQ)
191 mtx_assert(&sched_lock, MA_OWNED);
192 KASSERT(p->p_stat == SRUN, ("runq_add: proc %p (%s) not SRUN",
194 #if defined(INVARIANTS) && defined(DIAGNOSTIC)
195 KASSERT(runq_findproc(rq, ke) == 0,
196 ("runq_add: proc %p (%s) already in run queue", ke, p->p_comm));
198 pri = ke->ke_thread->td_priority / RQ_PPQ;
199 ke->ke_rqindex = pri;
200 runq_setbit(rq, pri);
201 rqh = &rq->rq_queues[pri];
202 CTR4(KTR_RUNQ, "runq_add: p=%p pri=%d %d rqh=%p",
203 ke->ke_proc, ke->ke_thread->td_priority, pri, rqh);
204 TAILQ_INSERT_TAIL(rqh, ke, ke_procq);
205 ke->ke_flags |= KEF_ONRUNQ;
209 * Return true if there are runnable processes of any priority on the run
210 * queue, false otherwise. Has no side effects, does not modify the run
214 runq_check(struct runq *rq)
219 rqb = &rq->rq_status;
220 for (i = 0; i < RQB_LEN; i++)
221 if (rqb->rqb_bits[i]) {
222 CTR2(KTR_RUNQ, "runq_check: bits=%#x i=%d",
223 rqb->rqb_bits[i], i);
226 CTR0(KTR_RUNQ, "runq_check: empty");
232 * Find and remove the highest priority process from the run queue.
233 * If there are no runnable processes, the per-cpu idle process is
234 * returned. Will not return NULL under any circumstances.
237 runq_choose(struct runq *rq)
243 mtx_assert(&sched_lock, MA_OWNED);
244 if ((pri = runq_findbit(rq)) != -1) {
245 rqh = &rq->rq_queues[pri];
246 ke = TAILQ_FIRST(rqh);
247 KASSERT(ke != NULL, ("runq_choose: no proc on busy queue"));
248 KASSERT(ke->ke_proc->p_stat == SRUN,
249 ("runq_choose: process %d(%s) in state %d", ke->ke_proc->p_pid,
250 ke->ke_proc->p_comm, ke->ke_proc->p_stat));
251 CTR3(KTR_RUNQ, "runq_choose: pri=%d kse=%p rqh=%p", pri, ke, rqh);
252 TAILQ_REMOVE(rqh, ke, ke_procq);
253 if (TAILQ_EMPTY(rqh)) {
254 CTR0(KTR_RUNQ, "runq_choose: empty");
255 runq_clrbit(rq, pri);
257 ke->ke_flags &= ~KEF_ONRUNQ;
260 CTR1(KTR_RUNQ, "runq_choose: idleproc pri=%d", pri);
262 return (PCPU_GET(idlethread)->td_kse);
266 * Initialize a run structure.
269 runq_init(struct runq *rq)
273 bzero(rq, sizeof *rq);
274 for (i = 0; i < RQ_NQS; i++)
275 TAILQ_INIT(&rq->rq_queues[i]);
279 * Remove the process from the queue specified by its priority, and clear the
280 * corresponding status bit if the queue becomes empty.
283 runq_remove(struct runq *rq, struct kse *ke)
288 if (!(ke->ke_flags & KEF_ONRUNQ))
290 mtx_assert(&sched_lock, MA_OWNED);
291 pri = ke->ke_rqindex;
292 rqh = &rq->rq_queues[pri];
293 CTR4(KTR_RUNQ, "runq_remove: p=%p pri=%d %d rqh=%p",
294 ke, ke->ke_thread->td_priority, pri, rqh);
295 KASSERT(ke != NULL, ("runq_remove: no proc on busy queue"));
296 TAILQ_REMOVE(rqh, ke, ke_procq);
297 if (TAILQ_EMPTY(rqh)) {
298 CTR0(KTR_RUNQ, "runq_remove: empty");
299 runq_clrbit(rq, pri);
301 ke->ke_flags &= ~KEF_ONRUNQ;