kern_switch.c revision 93264
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: head/sys/kern/kern_switch.c 93264 2002-03-27 05:39:23Z dillon $ 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 */ 41static struct runq runq; 42SYSINIT(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 48struct thread * 49choosethread(void) 50{ 51 return (runq_choose(&runq)->ke_thread); 52} 53 54int 55procrunnable(void) 56{ 57 return runq_check(&runq); 58} 59 60void 61remrunqueue(struct thread *td) 62{ 63 runq_remove(&runq, td->td_kse); 64} 65 66void 67setrunqueue(struct thread *td) 68{ 69 runq_add(&runq, td->td_kse); 70} 71 72/* Critical sections that prevent preemption. */ 73void 74critical_enter(void) 75{ 76 struct thread *td; 77 78 td = curthread; 79 if (td->td_critnest == 0) 80 cpu_critical_enter(); 81 td->td_critnest++; 82} 83 84void 85critical_exit(void) 86{ 87 struct thread *td; 88 89 td = curthread; 90 if (td->td_critnest == 1) { 91 td->td_critnest = 0; 92 cpu_critical_exit(); 93 } else { 94 td->td_critnest--; 95 } 96} 97 98/* 99 * Clear the status bit of the queue corresponding to priority level pri, 100 * indicating that it is empty. 101 */ 102static __inline void 103runq_clrbit(struct runq *rq, int pri) 104{ 105 struct rqbits *rqb; 106 107 rqb = &rq->rq_status; 108 CTR4(KTR_RUNQ, "runq_clrbit: bits=%#x %#x bit=%#x word=%d", 109 rqb->rqb_bits[RQB_WORD(pri)], 110 rqb->rqb_bits[RQB_WORD(pri)] & ~RQB_BIT(pri), 111 RQB_BIT(pri), RQB_WORD(pri)); 112 rqb->rqb_bits[RQB_WORD(pri)] &= ~RQB_BIT(pri); 113} 114 115/* 116 * Find the index of the first non-empty run queue. This is done by 117 * scanning the status bits, a set bit indicates a non-empty queue. 118 */ 119static __inline int 120runq_findbit(struct runq *rq) 121{ 122 struct rqbits *rqb; 123 int pri; 124 int i; 125 126 rqb = &rq->rq_status; 127 for (i = 0; i < RQB_LEN; i++) 128 if (rqb->rqb_bits[i]) { 129 pri = (RQB_FFS(rqb->rqb_bits[i]) - 1) + 130 (i << RQB_L2BPW); 131 CTR3(KTR_RUNQ, "runq_findbit: bits=%#x i=%d pri=%d", 132 rqb->rqb_bits[i], i, pri); 133 return (pri); 134 } 135 136 return (-1); 137} 138 139/* 140 * Set the status bit of the queue corresponding to priority level pri, 141 * indicating that it is non-empty. 142 */ 143static __inline void 144runq_setbit(struct runq *rq, int pri) 145{ 146 struct rqbits *rqb; 147 148 rqb = &rq->rq_status; 149 CTR4(KTR_RUNQ, "runq_setbit: bits=%#x %#x bit=%#x word=%d", 150 rqb->rqb_bits[RQB_WORD(pri)], 151 rqb->rqb_bits[RQB_WORD(pri)] | RQB_BIT(pri), 152 RQB_BIT(pri), RQB_WORD(pri)); 153 rqb->rqb_bits[RQB_WORD(pri)] |= RQB_BIT(pri); 154} 155 156#if defined(INVARIANT_SUPPORT) && defined(DIAGNOSTIC) 157/* 158 * Return true if the specified process is already in the run queue. 159 */ 160static __inline int 161runq_findproc(struct runq *rq, struct kse *ke) 162{ 163 struct kse *ke2; 164 int i; 165 166 mtx_assert(&sched_lock, MA_OWNED); 167 for (i = 0; i < RQB_LEN; i++) 168 TAILQ_FOREACH(ke2, &rq->rq_queues[i], ke_procq) 169 if (ke2 == ke) 170 return 1; 171 return 0; 172} 173#endif 174 175/* 176 * Add the process to the queue specified by its priority, and set the 177 * corresponding status bit. 178 */ 179void 180runq_add(struct runq *rq, struct kse *ke) 181{ 182 struct rqhead *rqh; 183 int pri; 184 185#ifdef INVARIANTS 186 struct proc *p = ke->ke_proc; 187#endif 188 if (ke->ke_flags & KEF_ONRUNQ) 189 return; 190 mtx_assert(&sched_lock, MA_OWNED); 191 KASSERT(p->p_stat == SRUN, ("runq_add: proc %p (%s) not SRUN", 192 p, p->p_comm)); 193#if defined(INVARIANTS) && defined(DIAGNOSTIC) 194 KASSERT(runq_findproc(rq, ke) == 0, 195 ("runq_add: proc %p (%s) already in run queue", ke, p->p_comm)); 196#endif 197 pri = ke->ke_thread->td_priority / RQ_PPQ; 198 ke->ke_rqindex = pri; 199 runq_setbit(rq, pri); 200 rqh = &rq->rq_queues[pri]; 201 CTR4(KTR_RUNQ, "runq_add: p=%p pri=%d %d rqh=%p", 202 ke->ke_proc, ke->ke_thread->td_priority, pri, rqh); 203 TAILQ_INSERT_TAIL(rqh, ke, ke_procq); 204 ke->ke_flags |= KEF_ONRUNQ; 205} 206 207/* 208 * Return true if there are runnable processes of any priority on the run 209 * queue, false otherwise. Has no side effects, does not modify the run 210 * queue structure. 211 */ 212int 213runq_check(struct runq *rq) 214{ 215 struct rqbits *rqb; 216 int i; 217 218 rqb = &rq->rq_status; 219 for (i = 0; i < RQB_LEN; i++) 220 if (rqb->rqb_bits[i]) { 221 CTR2(KTR_RUNQ, "runq_check: bits=%#x i=%d", 222 rqb->rqb_bits[i], i); 223 return (1); 224 } 225 CTR0(KTR_RUNQ, "runq_check: empty"); 226 227 return (0); 228} 229 230/* 231 * Find and remove the highest priority process from the run queue. 232 * If there are no runnable processes, the per-cpu idle process is 233 * returned. Will not return NULL under any circumstances. 234 */ 235struct kse * 236runq_choose(struct runq *rq) 237{ 238 struct rqhead *rqh; 239 struct kse *ke; 240 int pri; 241 242 mtx_assert(&sched_lock, MA_OWNED); 243 if ((pri = runq_findbit(rq)) != -1) { 244 rqh = &rq->rq_queues[pri]; 245 ke = TAILQ_FIRST(rqh); 246 KASSERT(ke != NULL, ("runq_choose: no proc on busy queue")); 247 KASSERT(ke->ke_proc->p_stat == SRUN, 248 ("runq_choose: process %d(%s) in state %d", ke->ke_proc->p_pid, 249 ke->ke_proc->p_comm, ke->ke_proc->p_stat)); 250 CTR3(KTR_RUNQ, "runq_choose: pri=%d kse=%p rqh=%p", pri, ke, rqh); 251 TAILQ_REMOVE(rqh, ke, ke_procq); 252 if (TAILQ_EMPTY(rqh)) { 253 CTR0(KTR_RUNQ, "runq_choose: empty"); 254 runq_clrbit(rq, pri); 255 } 256 ke->ke_flags &= ~KEF_ONRUNQ; 257 return (ke); 258 } 259 CTR1(KTR_RUNQ, "runq_choose: idleproc pri=%d", pri); 260 261 return (PCPU_GET(idlethread)->td_kse); 262} 263 264/* 265 * Initialize a run structure. 266 */ 267void 268runq_init(struct runq *rq) 269{ 270 int i; 271 272 bzero(rq, sizeof *rq); 273 for (i = 0; i < RQ_NQS; i++) 274 TAILQ_INIT(&rq->rq_queues[i]); 275} 276 277/* 278 * Remove the process from the queue specified by its priority, and clear the 279 * corresponding status bit if the queue becomes empty. 280 */ 281void 282runq_remove(struct runq *rq, struct kse *ke) 283{ 284 struct rqhead *rqh; 285 int pri; 286 287 if (!(ke->ke_flags & KEF_ONRUNQ)) 288 return; 289 mtx_assert(&sched_lock, MA_OWNED); 290 pri = ke->ke_rqindex; 291 rqh = &rq->rq_queues[pri]; 292 CTR4(KTR_RUNQ, "runq_remove: p=%p pri=%d %d rqh=%p", 293 ke, ke->ke_thread->td_priority, pri, rqh); 294 KASSERT(ke != NULL, ("runq_remove: no proc on busy queue")); 295 TAILQ_REMOVE(rqh, ke, ke_procq); 296 if (TAILQ_EMPTY(rqh)) { 297 CTR0(KTR_RUNQ, "runq_remove: empty"); 298 runq_clrbit(rq, pri); 299 } 300 ke->ke_flags &= ~KEF_ONRUNQ; 301} 302