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