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