1 /* 2 * Copyright (c) 1999 Peter Wemm <peter@FreeBSD.org> 3 * All rights reserved. 4 * Copyright (c) 2001 Jake Burkholder <jake@FreeBSD.org> 5 * All rights reserved. 6 * 7 * Redistribution and use in source and binary forms, with or without 8 * modification, are permitted provided that the following conditions 9 * are met: 10 * 1. Redistributions of source code must retain the above copyright 11 * notice, this list of conditions and the following disclaimer. 12 * 2. Redistributions in binary form must reproduce the above copyright 13 * notice, this list of conditions and the following disclaimer in the 14 * documentation and/or other materials provided with the distribution. 15 * 16 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 17 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 19 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 20 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 21 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 22 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 23 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 24 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 25 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 26 * SUCH DAMAGE. 27 * 28 * $FreeBSD$ 29 */ 30 31 #include <sys/param.h> 32 #include <sys/systm.h> 33 #include <sys/kernel.h> 34 #include <sys/ktr.h> 35 #include <sys/mutex.h> 36 #include <sys/proc.h> 37 #include <sys/queue.h> 38 39 /* 40 * Global run queue. 41 */ 42 static struct runq runq; 43 SYSINIT(runq, SI_SUB_RUN_QUEUE, SI_ORDER_FIRST, runq_init, &runq) 44 45 /* 46 * Wrappers which implement old interface; act on global run queue. 47 */ 48 49 struct proc * 50 chooseproc(void) 51 { 52 return runq_choose(&runq); 53 } 54 55 int 56 procrunnable(void) 57 { 58 return runq_check(&runq); 59 } 60 61 void 62 remrunqueue(struct proc *p) 63 { 64 runq_remove(&runq, p); 65 } 66 67 void 68 setrunqueue(struct proc *p) 69 { 70 runq_add(&runq, p); 71 } 72 73 /* 74 * Clear the status bit of the queue corresponding to priority level pri, 75 * indicating that it is empty. 76 */ 77 static __inline void 78 runq_clrbit(struct runq *rq, int pri) 79 { 80 struct rqbits *rqb; 81 82 rqb = &rq->rq_status; 83 CTR4(KTR_RUNQ, "runq_clrbit: bits=%#x %#x bit=%#x word=%d", 84 rqb->rqb_bits[RQB_WORD(pri)], 85 rqb->rqb_bits[RQB_WORD(pri)] & ~RQB_BIT(pri), 86 RQB_BIT(pri), RQB_WORD(pri)); 87 rqb->rqb_bits[RQB_WORD(pri)] &= ~RQB_BIT(pri); 88 } 89 90 /* 91 * Find the index of the first non-empty run queue. This is done by 92 * scanning the status bits, a set bit indicates a non-empty queue. 93 */ 94 static __inline int 95 runq_findbit(struct runq *rq) 96 { 97 struct rqbits *rqb; 98 int pri; 99 int i; 100 101 rqb = &rq->rq_status; 102 for (i = 0; i < RQB_LEN; i++) 103 if (rqb->rqb_bits[i]) { 104 pri = (RQB_FFS(rqb->rqb_bits[i]) - 1) + 105 (i << RQB_L2BPW); 106 CTR3(KTR_RUNQ, "runq_findbit: bits=%#x i=%d pri=%d", 107 rqb->rqb_bits[i], i, pri); 108 return (pri); 109 } 110 111 return (-1); 112 } 113 114 /* 115 * Set the status bit of the queue corresponding to priority level pri, 116 * indicating that it is non-empty. 117 */ 118 static __inline void 119 runq_setbit(struct runq *rq, int pri) 120 { 121 struct rqbits *rqb; 122 123 rqb = &rq->rq_status; 124 CTR4(KTR_RUNQ, "runq_setbit: bits=%#x %#x bit=%#x word=%d", 125 rqb->rqb_bits[RQB_WORD(pri)], 126 rqb->rqb_bits[RQB_WORD(pri)] | RQB_BIT(pri), 127 RQB_BIT(pri), RQB_WORD(pri)); 128 rqb->rqb_bits[RQB_WORD(pri)] |= RQB_BIT(pri); 129 } 130 131 #ifdef INVARIANT_SUPPORT 132 /* 133 * Return true if the specified process is already in the run queue. 134 */ 135 static __inline int 136 runq_find(struct runq *rq, struct proc *p) 137 { 138 struct proc *p2; 139 int i; 140 141 mtx_assert(&sched_lock, MA_OWNED); 142 for (i = 0; i < RQB_LEN; i++) 143 TAILQ_FOREACH(p2, &rq->rq_queues[i], p_procq) 144 if (p2 == p) 145 return 1; 146 return 0; 147 } 148 #endif 149 150 /* 151 * Add the process to the queue specified by its priority, and set the 152 * corresponding status bit. 153 */ 154 void 155 runq_add(struct runq *rq, struct proc *p) 156 { 157 struct rqhead *rqh; 158 int pri; 159 160 mtx_assert(&sched_lock, MA_OWNED); 161 KASSERT(p->p_stat == SRUN, ("runq_add: proc %p (%s) not SRUN", 162 p, p->p_comm)); 163 KASSERT(runq_find(rq, p) == 0, 164 ("runq_add: proc %p (%s) already in run queue", p, p->p_comm)); 165 pri = p->p_pri.pri_level / RQ_PPQ; 166 p->p_rqindex = pri; 167 runq_setbit(rq, pri); 168 rqh = &rq->rq_queues[pri]; 169 CTR4(KTR_RUNQ, "runq_add: p=%p pri=%d %d rqh=%p", 170 p, p->p_pri.pri_level, pri, rqh); 171 TAILQ_INSERT_TAIL(rqh, p, p_procq); 172 } 173 174 /* 175 * Return true if there are runnable processes of any priority on the run 176 * queue, false otherwise. Has no side effects, does not modify the run 177 * queue structure. 178 */ 179 int 180 runq_check(struct runq *rq) 181 { 182 struct rqbits *rqb; 183 int i; 184 185 rqb = &rq->rq_status; 186 for (i = 0; i < RQB_LEN; i++) 187 if (rqb->rqb_bits[i]) { 188 CTR2(KTR_RUNQ, "runq_check: bits=%#x i=%d", 189 rqb->rqb_bits[i], i); 190 return (1); 191 } 192 CTR0(KTR_RUNQ, "runq_check: empty"); 193 194 return (0); 195 } 196 197 /* 198 * Find and remove the highest priority process from the run queue. 199 * If there are no runnable processes, the per-cpu idle process is 200 * returned. Will not return NULL under any circumstances. 201 */ 202 struct proc * 203 runq_choose(struct runq *rq) 204 { 205 struct rqhead *rqh; 206 struct proc *p; 207 int pri; 208 209 mtx_assert(&sched_lock, MA_OWNED); 210 if ((pri = runq_findbit(rq)) != -1) { 211 rqh = &rq->rq_queues[pri]; 212 p = TAILQ_FIRST(rqh); 213 KASSERT(p != NULL, ("runq_choose: no proc on busy queue")); 214 KASSERT(p->p_stat == SRUN, 215 ("runq_chose: process %d(%s) in state %d", p->p_pid, 216 p->p_comm, p->p_stat)); 217 CTR3(KTR_RUNQ, "runq_choose: pri=%d p=%p rqh=%p", pri, p, rqh); 218 TAILQ_REMOVE(rqh, p, p_procq); 219 if (TAILQ_EMPTY(rqh)) { 220 CTR0(KTR_RUNQ, "runq_choose: empty"); 221 runq_clrbit(rq, pri); 222 } 223 return (p); 224 } 225 CTR1(KTR_RUNQ, "runq_choose: idleproc pri=%d", pri); 226 227 return (PCPU_GET(idleproc)); 228 } 229 230 /* 231 * Initialize a run structure. 232 */ 233 void 234 runq_init(struct runq *rq) 235 { 236 int i; 237 238 bzero(rq, sizeof *rq); 239 for (i = 0; i < RQ_NQS; i++) 240 TAILQ_INIT(&rq->rq_queues[i]); 241 } 242 243 /* 244 * Remove the process from the queue specified by its priority, and clear the 245 * corresponding status bit if the queue becomes empty. 246 */ 247 void 248 runq_remove(struct runq *rq, struct proc *p) 249 { 250 struct rqhead *rqh; 251 int pri; 252 253 mtx_assert(&sched_lock, MA_OWNED); 254 pri = p->p_rqindex; 255 rqh = &rq->rq_queues[pri]; 256 CTR4(KTR_RUNQ, "runq_remove: p=%p pri=%d %d rqh=%p", 257 p, p->p_pri.pri_level, pri, rqh); 258 KASSERT(p != NULL, ("runq_remove: no proc on busy queue")); 259 TAILQ_REMOVE(rqh, p, p_procq); 260 if (TAILQ_EMPTY(rqh)) { 261 CTR0(KTR_RUNQ, "runq_remove: empty"); 262 runq_clrbit(rq, pri); 263 } 264 } 265