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 27 28 #include <sys/cdefs.h> 29 __FBSDID("$FreeBSD$"); 30 31 #include "opt_sched.h" 32 33 #include <sys/param.h> 34 #include <sys/systm.h> 35 #include <sys/kdb.h> 36 #include <sys/kernel.h> 37 #include <sys/ktr.h> 38 #include <sys/lock.h> 39 #include <sys/mutex.h> 40 #include <sys/proc.h> 41 #include <sys/queue.h> 42 #include <sys/sched.h> 43 #include <sys/smp.h> 44 #include <sys/sysctl.h> 45 46 #include <machine/cpu.h> 47 48 /* Uncomment this to enable logging of critical_enter/exit. */ 49 #if 0 50 #define KTR_CRITICAL KTR_SCHED 51 #else 52 #define KTR_CRITICAL 0 53 #endif 54 55 #ifdef FULL_PREEMPTION 56 #ifndef PREEMPTION 57 #error "The FULL_PREEMPTION option requires the PREEMPTION option" 58 #endif 59 #endif 60 61 CTASSERT((RQB_BPW * RQB_LEN) == RQ_NQS); 62 63 /* 64 * kern.sched.preemption allows user space to determine if preemption support 65 * is compiled in or not. It is not currently a boot or runtime flag that 66 * can be changed. 67 */ 68 #ifdef PREEMPTION 69 static int kern_sched_preemption = 1; 70 #else 71 static int kern_sched_preemption = 0; 72 #endif 73 SYSCTL_INT(_kern_sched, OID_AUTO, preemption, CTLFLAG_RD, 74 &kern_sched_preemption, 0, "Kernel preemption enabled"); 75 76 /* 77 * Support for scheduler stats exported via kern.sched.stats. All stats may 78 * be reset with kern.sched.stats.reset = 1. Stats may be defined elsewhere 79 * with SCHED_STAT_DEFINE(). 80 */ 81 #ifdef SCHED_STATS 82 long sched_switch_stats[SWT_COUNT]; /* Switch reasons from mi_switch(). */ 83 84 SYSCTL_NODE(_kern_sched, OID_AUTO, stats, CTLFLAG_RW, 0, "switch stats"); 85 SCHED_STAT_DEFINE_VAR(uncategorized, &sched_switch_stats[SWT_NONE], ""); 86 SCHED_STAT_DEFINE_VAR(preempt, &sched_switch_stats[SWT_PREEMPT], ""); 87 SCHED_STAT_DEFINE_VAR(owepreempt, &sched_switch_stats[SWT_OWEPREEMPT], ""); 88 SCHED_STAT_DEFINE_VAR(turnstile, &sched_switch_stats[SWT_TURNSTILE], ""); 89 SCHED_STAT_DEFINE_VAR(sleepq, &sched_switch_stats[SWT_SLEEPQ], ""); 90 SCHED_STAT_DEFINE_VAR(sleepqtimo, &sched_switch_stats[SWT_SLEEPQTIMO], ""); 91 SCHED_STAT_DEFINE_VAR(relinquish, &sched_switch_stats[SWT_RELINQUISH], ""); 92 SCHED_STAT_DEFINE_VAR(needresched, &sched_switch_stats[SWT_NEEDRESCHED], ""); 93 SCHED_STAT_DEFINE_VAR(idle, &sched_switch_stats[SWT_IDLE], ""); 94 SCHED_STAT_DEFINE_VAR(iwait, &sched_switch_stats[SWT_IWAIT], ""); 95 SCHED_STAT_DEFINE_VAR(suspend, &sched_switch_stats[SWT_SUSPEND], ""); 96 SCHED_STAT_DEFINE_VAR(remotepreempt, &sched_switch_stats[SWT_REMOTEPREEMPT], 97 ""); 98 SCHED_STAT_DEFINE_VAR(remotewakeidle, &sched_switch_stats[SWT_REMOTEWAKEIDLE], 99 ""); 100 101 static int 102 sysctl_stats_reset(SYSCTL_HANDLER_ARGS) 103 { 104 struct sysctl_oid *p; 105 int error; 106 int val; 107 108 val = 0; 109 error = sysctl_handle_int(oidp, &val, 0, req); 110 if (error != 0 || req->newptr == NULL) 111 return (error); 112 if (val == 0) 113 return (0); 114 /* 115 * Traverse the list of children of _kern_sched_stats and reset each 116 * to 0. Skip the reset entry. 117 */ 118 SLIST_FOREACH(p, oidp->oid_parent, oid_link) { 119 if (p == oidp || p->oid_arg1 == NULL) 120 continue; 121 *(long *)p->oid_arg1 = 0; 122 } 123 return (0); 124 } 125 126 SYSCTL_PROC(_kern_sched_stats, OID_AUTO, reset, CTLTYPE_INT | CTLFLAG_WR, NULL, 127 0, sysctl_stats_reset, "I", "Reset scheduler statistics"); 128 #endif 129 130 /************************************************************************ 131 * Functions that manipulate runnability from a thread perspective. * 132 ************************************************************************/ 133 /* 134 * Select the thread that will be run next. 135 */ 136 struct thread * 137 choosethread(void) 138 { 139 struct thread *td; 140 141 retry: 142 td = sched_choose(); 143 144 /* 145 * If we are in panic, only allow system threads, 146 * plus the one we are running in, to be run. 147 */ 148 if (panicstr && ((td->td_proc->p_flag & P_SYSTEM) == 0 && 149 (td->td_flags & TDF_INPANIC) == 0)) { 150 /* note that it is no longer on the run queue */ 151 TD_SET_CAN_RUN(td); 152 goto retry; 153 } 154 155 TD_SET_RUNNING(td); 156 return (td); 157 } 158 159 /* 160 * Kernel thread preemption implementation. Critical sections mark 161 * regions of code in which preemptions are not allowed. 162 */ 163 void 164 critical_enter(void) 165 { 166 struct thread *td; 167 168 td = curthread; 169 td->td_critnest++; 170 CTR4(KTR_CRITICAL, "critical_enter by thread %p (%ld, %s) to %d", td, 171 (long)td->td_proc->p_pid, td->td_name, td->td_critnest); 172 } 173 174 void 175 critical_exit(void) 176 { 177 struct thread *td; 178 int flags; 179 180 td = curthread; 181 KASSERT(td->td_critnest != 0, 182 ("critical_exit: td_critnest == 0")); 183 184 if (td->td_critnest == 1) { 185 td->td_critnest = 0; 186 if (td->td_owepreempt) { 187 td->td_critnest = 1; 188 thread_lock(td); 189 td->td_critnest--; 190 flags = SW_INVOL | SW_PREEMPT; 191 if (TD_IS_IDLETHREAD(td)) 192 flags |= SWT_IDLE; 193 else 194 flags |= SWT_OWEPREEMPT; 195 mi_switch(flags, NULL); 196 thread_unlock(td); 197 } 198 } else 199 td->td_critnest--; 200 201 CTR4(KTR_CRITICAL, "critical_exit by thread %p (%ld, %s) to %d", td, 202 (long)td->td_proc->p_pid, td->td_name, td->td_critnest); 203 } 204 205 /************************************************************************ 206 * SYSTEM RUN QUEUE manipulations and tests * 207 ************************************************************************/ 208 /* 209 * Initialize a run structure. 210 */ 211 void 212 runq_init(struct runq *rq) 213 { 214 int i; 215 216 bzero(rq, sizeof *rq); 217 for (i = 0; i < RQ_NQS; i++) 218 TAILQ_INIT(&rq->rq_queues[i]); 219 } 220 221 /* 222 * Clear the status bit of the queue corresponding to priority level pri, 223 * indicating that it is empty. 224 */ 225 static __inline void 226 runq_clrbit(struct runq *rq, int pri) 227 { 228 struct rqbits *rqb; 229 230 rqb = &rq->rq_status; 231 CTR4(KTR_RUNQ, "runq_clrbit: bits=%#x %#x bit=%#x word=%d", 232 rqb->rqb_bits[RQB_WORD(pri)], 233 rqb->rqb_bits[RQB_WORD(pri)] & ~RQB_BIT(pri), 234 RQB_BIT(pri), RQB_WORD(pri)); 235 rqb->rqb_bits[RQB_WORD(pri)] &= ~RQB_BIT(pri); 236 } 237 238 /* 239 * Find the index of the first non-empty run queue. This is done by 240 * scanning the status bits, a set bit indicates a non-empty queue. 241 */ 242 static __inline int 243 runq_findbit(struct runq *rq) 244 { 245 struct rqbits *rqb; 246 int pri; 247 int i; 248 249 rqb = &rq->rq_status; 250 for (i = 0; i < RQB_LEN; i++) 251 if (rqb->rqb_bits[i]) { 252 pri = RQB_FFS(rqb->rqb_bits[i]) + (i << RQB_L2BPW); 253 CTR3(KTR_RUNQ, "runq_findbit: bits=%#x i=%d pri=%d", 254 rqb->rqb_bits[i], i, pri); 255 return (pri); 256 } 257 258 return (-1); 259 } 260 261 static __inline int 262 runq_findbit_from(struct runq *rq, u_char pri) 263 { 264 struct rqbits *rqb; 265 rqb_word_t mask; 266 int i; 267 268 /* 269 * Set the mask for the first word so we ignore priorities before 'pri'. 270 */ 271 mask = (rqb_word_t)-1 << (pri & (RQB_BPW - 1)); 272 rqb = &rq->rq_status; 273 again: 274 for (i = RQB_WORD(pri); i < RQB_LEN; mask = -1, i++) { 275 mask = rqb->rqb_bits[i] & mask; 276 if (mask == 0) 277 continue; 278 pri = RQB_FFS(mask) + (i << RQB_L2BPW); 279 CTR3(KTR_RUNQ, "runq_findbit_from: bits=%#x i=%d pri=%d", 280 mask, i, pri); 281 return (pri); 282 } 283 if (pri == 0) 284 return (-1); 285 /* 286 * Wrap back around to the beginning of the list just once so we 287 * scan the whole thing. 288 */ 289 pri = 0; 290 goto again; 291 } 292 293 /* 294 * Set the status bit of the queue corresponding to priority level pri, 295 * indicating that it is non-empty. 296 */ 297 static __inline void 298 runq_setbit(struct runq *rq, int pri) 299 { 300 struct rqbits *rqb; 301 302 rqb = &rq->rq_status; 303 CTR4(KTR_RUNQ, "runq_setbit: bits=%#x %#x bit=%#x word=%d", 304 rqb->rqb_bits[RQB_WORD(pri)], 305 rqb->rqb_bits[RQB_WORD(pri)] | RQB_BIT(pri), 306 RQB_BIT(pri), RQB_WORD(pri)); 307 rqb->rqb_bits[RQB_WORD(pri)] |= RQB_BIT(pri); 308 } 309 310 /* 311 * Add the thread to the queue specified by its priority, and set the 312 * corresponding status bit. 313 */ 314 void 315 runq_add(struct runq *rq, struct thread *td, int flags) 316 { 317 struct rqhead *rqh; 318 int pri; 319 320 pri = td->td_priority / RQ_PPQ; 321 td->td_rqindex = pri; 322 runq_setbit(rq, pri); 323 rqh = &rq->rq_queues[pri]; 324 CTR4(KTR_RUNQ, "runq_add: td=%p pri=%d %d rqh=%p", 325 td, td->td_priority, pri, rqh); 326 if (flags & SRQ_PREEMPTED) { 327 TAILQ_INSERT_HEAD(rqh, td, td_runq); 328 } else { 329 TAILQ_INSERT_TAIL(rqh, td, td_runq); 330 } 331 } 332 333 void 334 runq_add_pri(struct runq *rq, struct thread *td, u_char pri, int flags) 335 { 336 struct rqhead *rqh; 337 338 KASSERT(pri < RQ_NQS, ("runq_add_pri: %d out of range", pri)); 339 td->td_rqindex = pri; 340 runq_setbit(rq, pri); 341 rqh = &rq->rq_queues[pri]; 342 CTR4(KTR_RUNQ, "runq_add_pri: td=%p pri=%d idx=%d rqh=%p", 343 td, td->td_priority, pri, rqh); 344 if (flags & SRQ_PREEMPTED) { 345 TAILQ_INSERT_HEAD(rqh, td, td_runq); 346 } else { 347 TAILQ_INSERT_TAIL(rqh, td, td_runq); 348 } 349 } 350 /* 351 * Return true if there are runnable processes of any priority on the run 352 * queue, false otherwise. Has no side effects, does not modify the run 353 * queue structure. 354 */ 355 int 356 runq_check(struct runq *rq) 357 { 358 struct rqbits *rqb; 359 int i; 360 361 rqb = &rq->rq_status; 362 for (i = 0; i < RQB_LEN; i++) 363 if (rqb->rqb_bits[i]) { 364 CTR2(KTR_RUNQ, "runq_check: bits=%#x i=%d", 365 rqb->rqb_bits[i], i); 366 return (1); 367 } 368 CTR0(KTR_RUNQ, "runq_check: empty"); 369 370 return (0); 371 } 372 373 /* 374 * Find the highest priority process on the run queue. 375 */ 376 struct thread * 377 runq_choose_fuzz(struct runq *rq, int fuzz) 378 { 379 struct rqhead *rqh; 380 struct thread *td; 381 int pri; 382 383 while ((pri = runq_findbit(rq)) != -1) { 384 rqh = &rq->rq_queues[pri]; 385 /* fuzz == 1 is normal.. 0 or less are ignored */ 386 if (fuzz > 1) { 387 /* 388 * In the first couple of entries, check if 389 * there is one for our CPU as a preference. 390 */ 391 int count = fuzz; 392 int cpu = PCPU_GET(cpuid); 393 struct thread *td2; 394 td2 = td = TAILQ_FIRST(rqh); 395 396 while (count-- && td2) { 397 if (td2->td_lastcpu == cpu) { 398 td = td2; 399 break; 400 } 401 td2 = TAILQ_NEXT(td2, td_runq); 402 } 403 } else 404 td = TAILQ_FIRST(rqh); 405 KASSERT(td != NULL, ("runq_choose_fuzz: no proc on busy queue")); 406 CTR3(KTR_RUNQ, 407 "runq_choose_fuzz: pri=%d thread=%p rqh=%p", pri, td, rqh); 408 return (td); 409 } 410 CTR1(KTR_RUNQ, "runq_choose_fuzz: idleproc pri=%d", pri); 411 412 return (NULL); 413 } 414 415 /* 416 * Find the highest priority process on the run queue. 417 */ 418 struct thread * 419 runq_choose(struct runq *rq) 420 { 421 struct rqhead *rqh; 422 struct thread *td; 423 int pri; 424 425 while ((pri = runq_findbit(rq)) != -1) { 426 rqh = &rq->rq_queues[pri]; 427 td = TAILQ_FIRST(rqh); 428 KASSERT(td != NULL, ("runq_choose: no thread on busy queue")); 429 CTR3(KTR_RUNQ, 430 "runq_choose: pri=%d thread=%p rqh=%p", pri, td, rqh); 431 return (td); 432 } 433 CTR1(KTR_RUNQ, "runq_choose: idlethread pri=%d", pri); 434 435 return (NULL); 436 } 437 438 struct thread * 439 runq_choose_from(struct runq *rq, u_char idx) 440 { 441 struct rqhead *rqh; 442 struct thread *td; 443 int pri; 444 445 if ((pri = runq_findbit_from(rq, idx)) != -1) { 446 rqh = &rq->rq_queues[pri]; 447 td = TAILQ_FIRST(rqh); 448 KASSERT(td != NULL, ("runq_choose: no thread on busy queue")); 449 CTR4(KTR_RUNQ, 450 "runq_choose_from: pri=%d thread=%p idx=%d rqh=%p", 451 pri, td, td->td_rqindex, rqh); 452 return (td); 453 } 454 CTR1(KTR_RUNQ, "runq_choose_from: idlethread pri=%d", pri); 455 456 return (NULL); 457 } 458 /* 459 * Remove the thread from the queue specified by its priority, and clear the 460 * corresponding status bit if the queue becomes empty. 461 * Caller must set state afterwards. 462 */ 463 void 464 runq_remove(struct runq *rq, struct thread *td) 465 { 466 467 runq_remove_idx(rq, td, NULL); 468 } 469 470 void 471 runq_remove_idx(struct runq *rq, struct thread *td, u_char *idx) 472 { 473 struct rqhead *rqh; 474 u_char pri; 475 476 KASSERT(td->td_flags & TDF_INMEM, 477 ("runq_remove_idx: thread swapped out")); 478 pri = td->td_rqindex; 479 KASSERT(pri < RQ_NQS, ("runq_remove_idx: Invalid index %d\n", pri)); 480 rqh = &rq->rq_queues[pri]; 481 CTR4(KTR_RUNQ, "runq_remove_idx: td=%p, pri=%d %d rqh=%p", 482 td, td->td_priority, pri, rqh); 483 TAILQ_REMOVE(rqh, td, td_runq); 484 if (TAILQ_EMPTY(rqh)) { 485 CTR0(KTR_RUNQ, "runq_remove_idx: empty"); 486 runq_clrbit(rq, pri); 487 if (idx != NULL && *idx == pri) 488 *idx = (pri + 1) % RQ_NQS; 489 } 490 } 491