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