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 #include <machine/critical.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 thread * 50 choosethread(void) 51 { 52 return (runq_choose(&runq)->ke_thread); 53 } 54 55 int 56 procrunnable(void) 57 { 58 return runq_check(&runq); 59 } 60 61 void 62 remrunqueue(struct thread *td) 63 { 64 runq_remove(&runq, td->td_kse); 65 } 66 67 void 68 setrunqueue(struct thread *td) 69 { 70 runq_add(&runq, td->td_kse); 71 } 72 73 /* Critical sections that prevent preemption. */ 74 void 75 critical_enter(void) 76 { 77 struct thread *td; 78 79 td = curthread; 80 if (td->td_critnest == 0) 81 cpu_critical_enter(); 82 td->td_critnest++; 83 } 84 85 void 86 critical_exit(void) 87 { 88 struct thread *td; 89 90 td = curthread; 91 if (td->td_critnest == 1) { 92 td->td_critnest = 0; 93 cpu_critical_exit(); 94 } else { 95 td->td_critnest--; 96 } 97 } 98 99 /* 100 * Clear the status bit of the queue corresponding to priority level pri, 101 * indicating that it is empty. 102 */ 103 static __inline void 104 runq_clrbit(struct runq *rq, int pri) 105 { 106 struct rqbits *rqb; 107 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); 114 } 115 116 /* 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. 119 */ 120 static __inline int 121 runq_findbit(struct runq *rq) 122 { 123 struct rqbits *rqb; 124 int pri; 125 int i; 126 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) + 131 (i << RQB_L2BPW); 132 CTR3(KTR_RUNQ, "runq_findbit: bits=%#x i=%d pri=%d", 133 rqb->rqb_bits[i], i, pri); 134 return (pri); 135 } 136 137 return (-1); 138 } 139 140 /* 141 * Set the status bit of the queue corresponding to priority level pri, 142 * indicating that it is non-empty. 143 */ 144 static __inline void 145 runq_setbit(struct runq *rq, int pri) 146 { 147 struct rqbits *rqb; 148 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); 155 } 156 157 #if defined(INVARIANT_SUPPORT) && defined(DIAGNOSTIC) 158 /* 159 * Return true if the specified process is already in the run queue. 160 */ 161 static __inline int 162 runq_findproc(struct runq *rq, struct kse *ke) 163 { 164 struct kse *ke2; 165 int i; 166 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) 170 if (ke2 == ke) 171 return 1; 172 return 0; 173 } 174 #endif 175 176 /* 177 * Add the process to the queue specified by its priority, and set the 178 * corresponding status bit. 179 */ 180 void 181 runq_add(struct runq *rq, struct kse *ke) 182 { 183 struct rqhead *rqh; 184 int pri; 185 186 #ifdef INVARIANTS 187 struct proc *p = ke->ke_proc; 188 #endif 189 if (ke->ke_flags & KEF_ONRUNQ) 190 return; 191 mtx_assert(&sched_lock, MA_OWNED); 192 KASSERT(p->p_stat == SRUN, ("runq_add: proc %p (%s) not SRUN", 193 p, p->p_comm)); 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)); 197 #endif 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; 206 } 207 208 /* 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 211 * queue structure. 212 */ 213 int 214 runq_check(struct runq *rq) 215 { 216 struct rqbits *rqb; 217 int i; 218 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); 224 return (1); 225 } 226 CTR0(KTR_RUNQ, "runq_check: empty"); 227 228 return (0); 229 } 230 231 /* 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. 235 */ 236 struct kse * 237 runq_choose(struct runq *rq) 238 { 239 struct rqhead *rqh; 240 struct kse *ke; 241 int pri; 242 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); 256 } 257 ke->ke_flags &= ~KEF_ONRUNQ; 258 return (ke); 259 } 260 CTR1(KTR_RUNQ, "runq_choose: idleproc pri=%d", pri); 261 262 return (PCPU_GET(idlethread)->td_kse); 263 } 264 265 /* 266 * Initialize a run structure. 267 */ 268 void 269 runq_init(struct runq *rq) 270 { 271 int i; 272 273 bzero(rq, sizeof *rq); 274 for (i = 0; i < RQ_NQS; i++) 275 TAILQ_INIT(&rq->rq_queues[i]); 276 } 277 278 /* 279 * Remove the process from the queue specified by its priority, and clear the 280 * corresponding status bit if the queue becomes empty. 281 */ 282 void 283 runq_remove(struct runq *rq, struct kse *ke) 284 { 285 struct rqhead *rqh; 286 int pri; 287 288 if (!(ke->ke_flags & KEF_ONRUNQ)) 289 return; 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); 300 } 301 ke->ke_flags &= ~KEF_ONRUNQ; 302 } 303