1 /* $NetBSD: kern_synch.c,v 1.158 2005/12/24 19:12:23 perry Exp $ */ 2 3 /*- 4 * Copyright (c) 1999, 2000, 2004 The NetBSD Foundation, Inc. 5 * All rights reserved. 6 * 7 * This code is derived from software contributed to The NetBSD Foundation 8 * by Jason R. Thorpe of the Numerical Aerospace Simulation Facility, 9 * NASA Ames Research Center. 10 * This code is derived from software contributed to The NetBSD Foundation 11 * by Charles M. Hannum. 12 * 13 * Redistribution and use in source and binary forms, with or without 14 * modification, are permitted provided that the following conditions 15 * are met: 16 * 1. Redistributions of source code must retain the above copyright 17 * notice, this list of conditions and the following disclaimer. 18 * 2. Redistributions in binary form must reproduce the above copyright 19 * notice, this list of conditions and the following disclaimer in the 20 * documentation and/or other materials provided with the distribution. 21 * 3. All advertising materials mentioning features or use of this software 22 * must display the following acknowledgement: 23 * This product includes software developed by the NetBSD 24 * Foundation, Inc. and its contributors. 25 * 4. Neither the name of The NetBSD Foundation nor the names of its 26 * contributors may be used to endorse or promote products derived 27 * from this software without specific prior written permission. 28 * 29 * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS 30 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 31 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 32 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS 33 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 34 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 35 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 36 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 37 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 38 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 39 * POSSIBILITY OF SUCH DAMAGE. 40 */ 41 42 /*- 43 * Copyright (c) 1982, 1986, 1990, 1991, 1993 44 * The Regents of the University of California. All rights reserved. 45 * (c) UNIX System Laboratories, Inc. 46 * All or some portions of this file are derived from material licensed 47 * to the University of California by American Telephone and Telegraph 48 * Co. or Unix System Laboratories, Inc. and are reproduced herein with 49 * the permission of UNIX System Laboratories, Inc. 50 * 51 * Redistribution and use in source and binary forms, with or without 52 * modification, are permitted provided that the following conditions 53 * are met: 54 * 1. Redistributions of source code must retain the above copyright 55 * notice, this list of conditions and the following disclaimer. 56 * 2. Redistributions in binary form must reproduce the above copyright 57 * notice, this list of conditions and the following disclaimer in the 58 * documentation and/or other materials provided with the distribution. 59 * 3. Neither the name of the University nor the names of its contributors 60 * may be used to endorse or promote products derived from this software 61 * without specific prior written permission. 62 * 63 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 64 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 65 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 66 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 67 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 68 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 69 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 70 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 71 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 72 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 73 * SUCH DAMAGE. 74 * 75 * @(#)kern_synch.c 8.9 (Berkeley) 5/19/95 76 */ 77 78 #include <sys/cdefs.h> 79 __KERNEL_RCSID(0, "$NetBSD: kern_synch.c,v 1.158 2005/12/24 19:12:23 perry Exp $"); 80 81 #include "opt_ddb.h" 82 #include "opt_ktrace.h" 83 #include "opt_kstack.h" 84 #include "opt_lockdebug.h" 85 #include "opt_multiprocessor.h" 86 #include "opt_perfctrs.h" 87 88 #include <sys/param.h> 89 #include <sys/systm.h> 90 #include <sys/callout.h> 91 #include <sys/proc.h> 92 #include <sys/kernel.h> 93 #include <sys/buf.h> 94 #if defined(PERFCTRS) 95 #include <sys/pmc.h> 96 #endif 97 #include <sys/signalvar.h> 98 #include <sys/resourcevar.h> 99 #include <sys/sched.h> 100 #include <sys/sa.h> 101 #include <sys/savar.h> 102 103 #include <uvm/uvm_extern.h> 104 105 #ifdef KTRACE 106 #include <sys/ktrace.h> 107 #endif 108 109 #include <machine/cpu.h> 110 111 int lbolt; /* once a second sleep address */ 112 int rrticks; /* number of hardclock ticks per roundrobin() */ 113 114 /* 115 * Sleep queues. 116 * 117 * We're only looking at 7 bits of the address; everything is 118 * aligned to 4, lots of things are aligned to greater powers 119 * of 2. Shift right by 8, i.e. drop the bottom 256 worth. 120 */ 121 #define SLPQUE_TABLESIZE 128 122 #define SLPQUE_LOOKUP(x) (((u_long)(x) >> 8) & (SLPQUE_TABLESIZE - 1)) 123 124 #define SLPQUE(ident) (&sched_slpque[SLPQUE_LOOKUP(ident)]) 125 126 /* 127 * The global scheduler state. 128 */ 129 struct prochd sched_qs[RUNQUE_NQS]; /* run queues */ 130 volatile u_int32_t sched_whichqs; /* bitmap of non-empty queues */ 131 struct slpque sched_slpque[SLPQUE_TABLESIZE]; /* sleep queues */ 132 133 struct simplelock sched_lock = SIMPLELOCK_INITIALIZER; 134 135 void schedcpu(void *); 136 void updatepri(struct lwp *); 137 void endtsleep(void *); 138 139 inline void sa_awaken(struct lwp *); 140 inline void awaken(struct lwp *); 141 142 struct callout schedcpu_ch = CALLOUT_INITIALIZER_SETFUNC(schedcpu, NULL); 143 static unsigned int schedcpu_ticks; 144 145 146 /* 147 * Force switch among equal priority processes every 100ms. 148 * Called from hardclock every hz/10 == rrticks hardclock ticks. 149 */ 150 /* ARGSUSED */ 151 void 152 roundrobin(struct cpu_info *ci) 153 { 154 struct schedstate_percpu *spc = &ci->ci_schedstate; 155 156 spc->spc_rrticks = rrticks; 157 158 if (curlwp != NULL) { 159 if (spc->spc_flags & SPCF_SEENRR) { 160 /* 161 * The process has already been through a roundrobin 162 * without switching and may be hogging the CPU. 163 * Indicate that the process should yield. 164 */ 165 spc->spc_flags |= SPCF_SHOULDYIELD; 166 } else 167 spc->spc_flags |= SPCF_SEENRR; 168 } 169 need_resched(curcpu()); 170 } 171 172 #define PPQ (128 / RUNQUE_NQS) /* priorities per queue */ 173 #define NICE_WEIGHT 2 /* priorities per nice level */ 174 175 #define ESTCPU_SHIFT 11 176 #define ESTCPU_MAX ((NICE_WEIGHT * PRIO_MAX - PPQ) << ESTCPU_SHIFT) 177 #define ESTCPULIM(e) min((e), ESTCPU_MAX) 178 179 /* 180 * Constants for digital decay and forget: 181 * 90% of (p_estcpu) usage in 5 * loadav time 182 * 95% of (p_pctcpu) usage in 60 seconds (load insensitive) 183 * Note that, as ps(1) mentions, this can let percentages 184 * total over 100% (I've seen 137.9% for 3 processes). 185 * 186 * Note that hardclock updates p_estcpu and p_cpticks independently. 187 * 188 * We wish to decay away 90% of p_estcpu in (5 * loadavg) seconds. 189 * That is, the system wants to compute a value of decay such 190 * that the following for loop: 191 * for (i = 0; i < (5 * loadavg); i++) 192 * p_estcpu *= decay; 193 * will compute 194 * p_estcpu *= 0.1; 195 * for all values of loadavg: 196 * 197 * Mathematically this loop can be expressed by saying: 198 * decay ** (5 * loadavg) ~= .1 199 * 200 * The system computes decay as: 201 * decay = (2 * loadavg) / (2 * loadavg + 1) 202 * 203 * We wish to prove that the system's computation of decay 204 * will always fulfill the equation: 205 * decay ** (5 * loadavg) ~= .1 206 * 207 * If we compute b as: 208 * b = 2 * loadavg 209 * then 210 * decay = b / (b + 1) 211 * 212 * We now need to prove two things: 213 * 1) Given factor ** (5 * loadavg) ~= .1, prove factor == b/(b+1) 214 * 2) Given b/(b+1) ** power ~= .1, prove power == (5 * loadavg) 215 * 216 * Facts: 217 * For x close to zero, exp(x) =~ 1 + x, since 218 * exp(x) = 0! + x**1/1! + x**2/2! + ... . 219 * therefore exp(-1/b) =~ 1 - (1/b) = (b-1)/b. 220 * For x close to zero, ln(1+x) =~ x, since 221 * ln(1+x) = x - x**2/2 + x**3/3 - ... -1 < x < 1 222 * therefore ln(b/(b+1)) = ln(1 - 1/(b+1)) =~ -1/(b+1). 223 * ln(.1) =~ -2.30 224 * 225 * Proof of (1): 226 * Solve (factor)**(power) =~ .1 given power (5*loadav): 227 * solving for factor, 228 * ln(factor) =~ (-2.30/5*loadav), or 229 * factor =~ exp(-1/((5/2.30)*loadav)) =~ exp(-1/(2*loadav)) = 230 * exp(-1/b) =~ (b-1)/b =~ b/(b+1). QED 231 * 232 * Proof of (2): 233 * Solve (factor)**(power) =~ .1 given factor == (b/(b+1)): 234 * solving for power, 235 * power*ln(b/(b+1)) =~ -2.30, or 236 * power =~ 2.3 * (b + 1) = 4.6*loadav + 2.3 =~ 5*loadav. QED 237 * 238 * Actual power values for the implemented algorithm are as follows: 239 * loadav: 1 2 3 4 240 * power: 5.68 10.32 14.94 19.55 241 */ 242 243 /* calculations for digital decay to forget 90% of usage in 5*loadav sec */ 244 #define loadfactor(loadav) (2 * (loadav)) 245 246 static fixpt_t 247 decay_cpu(fixpt_t loadfac, fixpt_t estcpu) 248 { 249 250 if (estcpu == 0) { 251 return 0; 252 } 253 254 #if !defined(_LP64) 255 /* avoid 64bit arithmetics. */ 256 #define FIXPT_MAX ((fixpt_t)((UINTMAX_C(1) << sizeof(fixpt_t) * CHAR_BIT) - 1)) 257 if (__predict_true(loadfac <= FIXPT_MAX / ESTCPU_MAX)) { 258 return estcpu * loadfac / (loadfac + FSCALE); 259 } 260 #endif /* !defined(_LP64) */ 261 262 return (uint64_t)estcpu * loadfac / (loadfac + FSCALE); 263 } 264 265 /* 266 * For all load averages >= 1 and max p_estcpu of (255 << ESTCPU_SHIFT), 267 * sleeping for at least seven times the loadfactor will decay p_estcpu to 268 * less than (1 << ESTCPU_SHIFT). 269 * 270 * note that our ESTCPU_MAX is actually much smaller than (255 << ESTCPU_SHIFT). 271 */ 272 static fixpt_t 273 decay_cpu_batch(fixpt_t loadfac, fixpt_t estcpu, unsigned int n) 274 { 275 276 if ((n << FSHIFT) >= 7 * loadfac) { 277 return 0; 278 } 279 280 while (estcpu != 0 && n > 1) { 281 estcpu = decay_cpu(loadfac, estcpu); 282 n--; 283 } 284 285 return estcpu; 286 } 287 288 /* decay 95% of `p_pctcpu' in 60 seconds; see CCPU_SHIFT before changing */ 289 fixpt_t ccpu = 0.95122942450071400909 * FSCALE; /* exp(-1/20) */ 290 291 /* 292 * If `ccpu' is not equal to `exp(-1/20)' and you still want to use the 293 * faster/more-accurate formula, you'll have to estimate CCPU_SHIFT below 294 * and possibly adjust FSHIFT in "param.h" so that (FSHIFT >= CCPU_SHIFT). 295 * 296 * To estimate CCPU_SHIFT for exp(-1/20), the following formula was used: 297 * 1 - exp(-1/20) ~= 0.0487 ~= 0.0488 == 1 (fixed pt, *11* bits). 298 * 299 * If you dont want to bother with the faster/more-accurate formula, you 300 * can set CCPU_SHIFT to (FSHIFT + 1) which will use a slower/less-accurate 301 * (more general) method of calculating the %age of CPU used by a process. 302 */ 303 #define CCPU_SHIFT 11 304 305 /* 306 * Recompute process priorities, every hz ticks. 307 */ 308 /* ARGSUSED */ 309 void 310 schedcpu(void *arg) 311 { 312 fixpt_t loadfac = loadfactor(averunnable.ldavg[0]); 313 struct lwp *l; 314 struct proc *p; 315 int s, minslp; 316 int clkhz; 317 318 schedcpu_ticks++; 319 320 proclist_lock_read(); 321 PROCLIST_FOREACH(p, &allproc) { 322 /* 323 * Increment time in/out of memory and sleep time 324 * (if sleeping). We ignore overflow; with 16-bit int's 325 * (remember them?) overflow takes 45 days. 326 */ 327 minslp = 2; 328 LIST_FOREACH(l, &p->p_lwps, l_sibling) { 329 l->l_swtime++; 330 if (l->l_stat == LSSLEEP || l->l_stat == LSSTOP || 331 l->l_stat == LSSUSPENDED) { 332 l->l_slptime++; 333 minslp = min(minslp, l->l_slptime); 334 } else 335 minslp = 0; 336 } 337 p->p_pctcpu = (p->p_pctcpu * ccpu) >> FSHIFT; 338 /* 339 * If the process has slept the entire second, 340 * stop recalculating its priority until it wakes up. 341 */ 342 if (minslp > 1) 343 continue; 344 s = splstatclock(); /* prevent state changes */ 345 /* 346 * p_pctcpu is only for ps. 347 */ 348 clkhz = stathz != 0 ? stathz : hz; 349 #if (FSHIFT >= CCPU_SHIFT) 350 p->p_pctcpu += (clkhz == 100)? 351 ((fixpt_t) p->p_cpticks) << (FSHIFT - CCPU_SHIFT): 352 100 * (((fixpt_t) p->p_cpticks) 353 << (FSHIFT - CCPU_SHIFT)) / clkhz; 354 #else 355 p->p_pctcpu += ((FSCALE - ccpu) * 356 (p->p_cpticks * FSCALE / clkhz)) >> FSHIFT; 357 #endif 358 p->p_cpticks = 0; 359 p->p_estcpu = decay_cpu(loadfac, p->p_estcpu); 360 splx(s); /* Done with the process CPU ticks update */ 361 SCHED_LOCK(s); 362 LIST_FOREACH(l, &p->p_lwps, l_sibling) { 363 if (l->l_slptime > 1) 364 continue; 365 resetpriority(l); 366 if (l->l_priority >= PUSER) { 367 if (l->l_stat == LSRUN && 368 (l->l_flag & L_INMEM) && 369 (l->l_priority / PPQ) != (l->l_usrpri / PPQ)) { 370 remrunqueue(l); 371 l->l_priority = l->l_usrpri; 372 setrunqueue(l); 373 } else 374 l->l_priority = l->l_usrpri; 375 } 376 } 377 SCHED_UNLOCK(s); 378 } 379 proclist_unlock_read(); 380 uvm_meter(); 381 wakeup((caddr_t)&lbolt); 382 callout_schedule(&schedcpu_ch, hz); 383 } 384 385 /* 386 * Recalculate the priority of a process after it has slept for a while. 387 */ 388 void 389 updatepri(struct lwp *l) 390 { 391 struct proc *p = l->l_proc; 392 fixpt_t loadfac; 393 394 SCHED_ASSERT_LOCKED(); 395 KASSERT(l->l_slptime > 1); 396 397 loadfac = loadfactor(averunnable.ldavg[0]); 398 399 l->l_slptime--; /* the first time was done in schedcpu */ 400 /* XXX NJWLWP */ 401 p->p_estcpu = decay_cpu_batch(loadfac, p->p_estcpu, l->l_slptime); 402 resetpriority(l); 403 } 404 405 /* 406 * During autoconfiguration or after a panic, a sleep will simply 407 * lower the priority briefly to allow interrupts, then return. 408 * The priority to be used (safepri) is machine-dependent, thus this 409 * value is initialized and maintained in the machine-dependent layers. 410 * This priority will typically be 0, or the lowest priority 411 * that is safe for use on the interrupt stack; it can be made 412 * higher to block network software interrupts after panics. 413 */ 414 int safepri; 415 416 /* 417 * General sleep call. Suspends the current process until a wakeup is 418 * performed on the specified identifier. The process will then be made 419 * runnable with the specified priority. Sleeps at most timo/hz seconds 420 * (0 means no timeout). If pri includes PCATCH flag, signals are checked 421 * before and after sleeping, else signals are not checked. Returns 0 if 422 * awakened, EWOULDBLOCK if the timeout expires. If PCATCH is set and a 423 * signal needs to be delivered, ERESTART is returned if the current system 424 * call should be restarted if possible, and EINTR is returned if the system 425 * call should be interrupted by the signal (return EINTR). 426 * 427 * The interlock is held until the scheduler_slock is acquired. The 428 * interlock will be locked before returning back to the caller 429 * unless the PNORELOCK flag is specified, in which case the 430 * interlock will always be unlocked upon return. 431 */ 432 int 433 ltsleep(volatile const void *ident, int priority, const char *wmesg, int timo, 434 volatile struct simplelock *interlock) 435 { 436 struct lwp *l = curlwp; 437 struct proc *p = l ? l->l_proc : NULL; 438 struct slpque *qp; 439 struct sadata_upcall *sau; 440 int sig, s; 441 int catch = priority & PCATCH; 442 int relock = (priority & PNORELOCK) == 0; 443 int exiterr = (priority & PNOEXITERR) == 0; 444 445 /* 446 * XXXSMP 447 * This is probably bogus. Figure out what the right 448 * thing to do here really is. 449 * Note that not sleeping if ltsleep is called with curlwp == NULL 450 * in the shutdown case is disgusting but partly necessary given 451 * how shutdown (barely) works. 452 */ 453 if (cold || (doing_shutdown && (panicstr || (l == NULL)))) { 454 /* 455 * After a panic, or during autoconfiguration, 456 * just give interrupts a chance, then just return; 457 * don't run any other procs or panic below, 458 * in case this is the idle process and already asleep. 459 */ 460 s = splhigh(); 461 splx(safepri); 462 splx(s); 463 if (interlock != NULL && relock == 0) 464 simple_unlock(interlock); 465 return (0); 466 } 467 468 KASSERT(p != NULL); 469 LOCK_ASSERT(interlock == NULL || simple_lock_held(interlock)); 470 471 #ifdef KTRACE 472 if (KTRPOINT(p, KTR_CSW)) 473 ktrcsw(l, 1, 0); 474 #endif 475 476 /* 477 * XXX We need to allocate the sadata_upcall structure here, 478 * XXX since we can't sleep while waiting for memory inside 479 * XXX sa_upcall(). It would be nice if we could safely 480 * XXX allocate the sadata_upcall structure on the stack, here. 481 */ 482 if (l->l_flag & L_SA) { 483 sau = sadata_upcall_alloc(0); 484 } else { 485 sau = NULL; 486 } 487 488 SCHED_LOCK(s); 489 490 #ifdef DIAGNOSTIC 491 if (ident == NULL) 492 panic("ltsleep: ident == NULL"); 493 if (l->l_stat != LSONPROC) 494 panic("ltsleep: l_stat %d != LSONPROC", l->l_stat); 495 if (l->l_back != NULL) 496 panic("ltsleep: p_back != NULL"); 497 #endif 498 499 l->l_wchan = ident; 500 l->l_wmesg = wmesg; 501 l->l_slptime = 0; 502 l->l_priority = priority & PRIMASK; 503 504 qp = SLPQUE(ident); 505 if (qp->sq_head == 0) 506 qp->sq_head = l; 507 else { 508 *qp->sq_tailp = l; 509 } 510 *(qp->sq_tailp = &l->l_forw) = 0; 511 512 if (timo) 513 callout_reset(&l->l_tsleep_ch, timo, endtsleep, l); 514 515 /* 516 * We can now release the interlock; the scheduler_slock 517 * is held, so a thread can't get in to do wakeup() before 518 * we do the switch. 519 * 520 * XXX We leave the code block here, after inserting ourselves 521 * on the sleep queue, because we might want a more clever 522 * data structure for the sleep queues at some point. 523 */ 524 if (interlock != NULL) 525 simple_unlock(interlock); 526 527 /* 528 * We put ourselves on the sleep queue and start our timeout 529 * before calling CURSIG, as we could stop there, and a wakeup 530 * or a SIGCONT (or both) could occur while we were stopped. 531 * A SIGCONT would cause us to be marked as SSLEEP 532 * without resuming us, thus we must be ready for sleep 533 * when CURSIG is called. If the wakeup happens while we're 534 * stopped, p->p_wchan will be 0 upon return from CURSIG. 535 */ 536 if (catch) { 537 l->l_flag |= L_SINTR; 538 if (((sig = CURSIG(l)) != 0) || 539 ((p->p_flag & P_WEXIT) && p->p_nlwps > 1)) { 540 if (l->l_wchan != NULL) 541 unsleep(l); 542 l->l_stat = LSONPROC; 543 SCHED_UNLOCK(s); 544 goto resume; 545 } 546 if (l->l_wchan == NULL) { 547 catch = 0; 548 SCHED_UNLOCK(s); 549 goto resume; 550 } 551 } else 552 sig = 0; 553 l->l_stat = LSSLEEP; 554 p->p_nrlwps--; 555 p->p_stats->p_ru.ru_nvcsw++; 556 SCHED_ASSERT_LOCKED(); 557 if (l->l_flag & L_SA) 558 sa_switch(l, sau, SA_UPCALL_BLOCKED); 559 else 560 mi_switch(l, NULL); 561 562 #if defined(DDB) && !defined(GPROF) 563 /* handy breakpoint location after process "wakes" */ 564 __asm(".globl bpendtsleep\nbpendtsleep:"); 565 #endif 566 /* 567 * p->p_nrlwps is incremented by whoever made us runnable again, 568 * either setrunnable() or awaken(). 569 */ 570 571 SCHED_ASSERT_UNLOCKED(); 572 splx(s); 573 574 resume: 575 KDASSERT(l->l_cpu != NULL); 576 KDASSERT(l->l_cpu == curcpu()); 577 l->l_cpu->ci_schedstate.spc_curpriority = l->l_usrpri; 578 579 l->l_flag &= ~L_SINTR; 580 if (l->l_flag & L_TIMEOUT) { 581 l->l_flag &= ~(L_TIMEOUT|L_CANCELLED); 582 if (sig == 0) { 583 #ifdef KTRACE 584 if (KTRPOINT(p, KTR_CSW)) 585 ktrcsw(l, 0, 0); 586 #endif 587 if (relock && interlock != NULL) 588 simple_lock(interlock); 589 return (EWOULDBLOCK); 590 } 591 } else if (timo) 592 callout_stop(&l->l_tsleep_ch); 593 594 if (catch) { 595 const int cancelled = l->l_flag & L_CANCELLED; 596 l->l_flag &= ~L_CANCELLED; 597 if (sig != 0 || (sig = CURSIG(l)) != 0 || cancelled) { 598 #ifdef KTRACE 599 if (KTRPOINT(p, KTR_CSW)) 600 ktrcsw(l, 0, 0); 601 #endif 602 if (relock && interlock != NULL) 603 simple_lock(interlock); 604 /* 605 * If this sleep was canceled, don't let the syscall 606 * restart. 607 */ 608 if (cancelled || 609 (SIGACTION(p, sig).sa_flags & SA_RESTART) == 0) 610 return (EINTR); 611 return (ERESTART); 612 } 613 } 614 615 #ifdef KTRACE 616 if (KTRPOINT(p, KTR_CSW)) 617 ktrcsw(l, 0, 0); 618 #endif 619 if (relock && interlock != NULL) 620 simple_lock(interlock); 621 622 /* XXXNJW this is very much a kluge. 623 * revisit. a better way of preventing looping/hanging syscalls like 624 * wait4() and _lwp_wait() from wedging an exiting process 625 * would be preferred. 626 */ 627 if (catch && ((p->p_flag & P_WEXIT) && p->p_nlwps > 1 && exiterr)) 628 return (EINTR); 629 return (0); 630 } 631 632 /* 633 * Implement timeout for tsleep. 634 * If process hasn't been awakened (wchan non-zero), 635 * set timeout flag and undo the sleep. If proc 636 * is stopped, just unsleep so it will remain stopped. 637 */ 638 void 639 endtsleep(void *arg) 640 { 641 struct lwp *l; 642 int s; 643 644 l = (struct lwp *)arg; 645 SCHED_LOCK(s); 646 if (l->l_wchan) { 647 if (l->l_stat == LSSLEEP) 648 setrunnable(l); 649 else 650 unsleep(l); 651 l->l_flag |= L_TIMEOUT; 652 } 653 SCHED_UNLOCK(s); 654 } 655 656 /* 657 * Remove a process from its wait queue 658 */ 659 void 660 unsleep(struct lwp *l) 661 { 662 struct slpque *qp; 663 struct lwp **hp; 664 665 SCHED_ASSERT_LOCKED(); 666 667 if (l->l_wchan) { 668 hp = &(qp = SLPQUE(l->l_wchan))->sq_head; 669 while (*hp != l) 670 hp = &(*hp)->l_forw; 671 *hp = l->l_forw; 672 if (qp->sq_tailp == &l->l_forw) 673 qp->sq_tailp = hp; 674 l->l_wchan = 0; 675 } 676 } 677 678 inline void 679 sa_awaken(struct lwp *l) 680 { 681 682 SCHED_ASSERT_LOCKED(); 683 684 if (l == l->l_savp->savp_lwp && l->l_flag & L_SA_YIELD) 685 l->l_flag &= ~L_SA_IDLE; 686 } 687 688 /* 689 * Optimized-for-wakeup() version of setrunnable(). 690 */ 691 inline void 692 awaken(struct lwp *l) 693 { 694 695 SCHED_ASSERT_LOCKED(); 696 697 if (l->l_proc->p_sa) 698 sa_awaken(l); 699 700 if (l->l_slptime > 1) 701 updatepri(l); 702 l->l_slptime = 0; 703 l->l_stat = LSRUN; 704 l->l_proc->p_nrlwps++; 705 /* 706 * Since curpriority is a user priority, p->p_priority 707 * is always better than curpriority on the last CPU on 708 * which it ran. 709 * 710 * XXXSMP See affinity comment in resched_proc(). 711 */ 712 if (l->l_flag & L_INMEM) { 713 setrunqueue(l); 714 KASSERT(l->l_cpu != NULL); 715 need_resched(l->l_cpu); 716 } else 717 sched_wakeup(&proc0); 718 } 719 720 #if defined(MULTIPROCESSOR) || defined(LOCKDEBUG) 721 void 722 sched_unlock_idle(void) 723 { 724 725 simple_unlock(&sched_lock); 726 } 727 728 void 729 sched_lock_idle(void) 730 { 731 732 simple_lock(&sched_lock); 733 } 734 #endif /* MULTIPROCESSOR || LOCKDEBUG */ 735 736 /* 737 * Make all processes sleeping on the specified identifier runnable. 738 */ 739 740 void 741 wakeup(volatile const void *ident) 742 { 743 int s; 744 745 SCHED_ASSERT_UNLOCKED(); 746 747 SCHED_LOCK(s); 748 sched_wakeup(ident); 749 SCHED_UNLOCK(s); 750 } 751 752 void 753 sched_wakeup(volatile const void *ident) 754 { 755 struct slpque *qp; 756 struct lwp *l, **q; 757 758 SCHED_ASSERT_LOCKED(); 759 760 qp = SLPQUE(ident); 761 restart: 762 for (q = &qp->sq_head; (l = *q) != NULL; ) { 763 #ifdef DIAGNOSTIC 764 if (l->l_back || (l->l_stat != LSSLEEP && 765 l->l_stat != LSSTOP && l->l_stat != LSSUSPENDED)) 766 panic("wakeup"); 767 #endif 768 if (l->l_wchan == ident) { 769 l->l_wchan = 0; 770 *q = l->l_forw; 771 if (qp->sq_tailp == &l->l_forw) 772 qp->sq_tailp = q; 773 if (l->l_stat == LSSLEEP) { 774 awaken(l); 775 goto restart; 776 } 777 } else 778 q = &l->l_forw; 779 } 780 } 781 782 /* 783 * Make the highest priority process first in line on the specified 784 * identifier runnable. 785 */ 786 void 787 wakeup_one(volatile const void *ident) 788 { 789 struct slpque *qp; 790 struct lwp *l, **q; 791 struct lwp *best_sleepp, **best_sleepq; 792 struct lwp *best_stopp, **best_stopq; 793 int s; 794 795 best_sleepp = best_stopp = NULL; 796 best_sleepq = best_stopq = NULL; 797 798 SCHED_LOCK(s); 799 800 qp = SLPQUE(ident); 801 802 for (q = &qp->sq_head; (l = *q) != NULL; q = &l->l_forw) { 803 #ifdef DIAGNOSTIC 804 if (l->l_back || (l->l_stat != LSSLEEP && 805 l->l_stat != LSSTOP && l->l_stat != LSSUSPENDED)) 806 panic("wakeup_one"); 807 #endif 808 if (l->l_wchan == ident) { 809 if (l->l_stat == LSSLEEP) { 810 if (best_sleepp == NULL || 811 l->l_priority < best_sleepp->l_priority) { 812 best_sleepp = l; 813 best_sleepq = q; 814 } 815 } else { 816 if (best_stopp == NULL || 817 l->l_priority < best_stopp->l_priority) { 818 best_stopp = l; 819 best_stopq = q; 820 } 821 } 822 } 823 } 824 825 /* 826 * Consider any SSLEEP process higher than the highest priority SSTOP 827 * process. 828 */ 829 if (best_sleepp != NULL) { 830 l = best_sleepp; 831 q = best_sleepq; 832 } else { 833 l = best_stopp; 834 q = best_stopq; 835 } 836 837 if (l != NULL) { 838 l->l_wchan = NULL; 839 *q = l->l_forw; 840 if (qp->sq_tailp == &l->l_forw) 841 qp->sq_tailp = q; 842 if (l->l_stat == LSSLEEP) 843 awaken(l); 844 } 845 SCHED_UNLOCK(s); 846 } 847 848 /* 849 * General yield call. Puts the current process back on its run queue and 850 * performs a voluntary context switch. Should only be called when the 851 * current process explicitly requests it (eg sched_yield(2) in compat code). 852 */ 853 void 854 yield(void) 855 { 856 struct lwp *l = curlwp; 857 int s; 858 859 SCHED_LOCK(s); 860 l->l_priority = l->l_usrpri; 861 l->l_stat = LSRUN; 862 setrunqueue(l); 863 l->l_proc->p_stats->p_ru.ru_nvcsw++; 864 mi_switch(l, NULL); 865 SCHED_ASSERT_UNLOCKED(); 866 splx(s); 867 } 868 869 /* 870 * General preemption call. Puts the current process back on its run queue 871 * and performs an involuntary context switch. 872 * The 'more' ("more work to do") argument is boolean. Returning to userspace 873 * preempt() calls pass 0. "Voluntary" preemptions in e.g. uiomove() pass 1. 874 * This will be used to indicate to the SA subsystem that the LWP is 875 * not yet finished in the kernel. 876 */ 877 878 void 879 preempt(int more) 880 { 881 struct lwp *l = curlwp; 882 int r, s; 883 884 SCHED_LOCK(s); 885 l->l_priority = l->l_usrpri; 886 l->l_stat = LSRUN; 887 setrunqueue(l); 888 l->l_proc->p_stats->p_ru.ru_nivcsw++; 889 r = mi_switch(l, NULL); 890 SCHED_ASSERT_UNLOCKED(); 891 splx(s); 892 if ((l->l_flag & L_SA) != 0 && r != 0 && more == 0) 893 sa_preempt(l); 894 } 895 896 /* 897 * The machine independent parts of context switch. 898 * Must be called at splsched() (no higher!) and with 899 * the sched_lock held. 900 * Switch to "new" if non-NULL, otherwise let cpu_switch choose 901 * the next lwp. 902 * 903 * Returns 1 if another process was actually run. 904 */ 905 int 906 mi_switch(struct lwp *l, struct lwp *newl) 907 { 908 struct schedstate_percpu *spc; 909 struct rlimit *rlim; 910 long s, u; 911 struct timeval tv; 912 int hold_count; 913 struct proc *p = l->l_proc; 914 int retval; 915 916 SCHED_ASSERT_LOCKED(); 917 918 /* 919 * Release the kernel_lock, as we are about to yield the CPU. 920 * The scheduler lock is still held until cpu_switch() 921 * selects a new process and removes it from the run queue. 922 */ 923 hold_count = KERNEL_LOCK_RELEASE_ALL(); 924 925 KDASSERT(l->l_cpu != NULL); 926 KDASSERT(l->l_cpu == curcpu()); 927 928 spc = &l->l_cpu->ci_schedstate; 929 930 #if defined(LOCKDEBUG) || defined(DIAGNOSTIC) 931 spinlock_switchcheck(); 932 #endif 933 #ifdef LOCKDEBUG 934 simple_lock_switchcheck(); 935 #endif 936 937 /* 938 * Compute the amount of time during which the current 939 * process was running. 940 */ 941 microtime(&tv); 942 u = p->p_rtime.tv_usec + 943 (tv.tv_usec - spc->spc_runtime.tv_usec); 944 s = p->p_rtime.tv_sec + (tv.tv_sec - spc->spc_runtime.tv_sec); 945 if (u < 0) { 946 u += 1000000; 947 s--; 948 } else if (u >= 1000000) { 949 u -= 1000000; 950 s++; 951 } 952 p->p_rtime.tv_usec = u; 953 p->p_rtime.tv_sec = s; 954 955 /* 956 * Check if the process exceeds its CPU resource allocation. 957 * If over max, kill it. In any case, if it has run for more 958 * than 10 minutes, reduce priority to give others a chance. 959 */ 960 rlim = &p->p_rlimit[RLIMIT_CPU]; 961 if (s >= rlim->rlim_cur) { 962 /* 963 * XXXSMP: we're inside the scheduler lock perimeter; 964 * use sched_psignal. 965 */ 966 if (s >= rlim->rlim_max) 967 sched_psignal(p, SIGKILL); 968 else { 969 sched_psignal(p, SIGXCPU); 970 if (rlim->rlim_cur < rlim->rlim_max) 971 rlim->rlim_cur += 5; 972 } 973 } 974 if (autonicetime && s > autonicetime && p->p_ucred->cr_uid && 975 p->p_nice == NZERO) { 976 p->p_nice = autoniceval + NZERO; 977 resetpriority(l); 978 } 979 980 /* 981 * Process is about to yield the CPU; clear the appropriate 982 * scheduling flags. 983 */ 984 spc->spc_flags &= ~SPCF_SWITCHCLEAR; 985 986 #ifdef KSTACK_CHECK_MAGIC 987 kstack_check_magic(l); 988 #endif 989 990 /* 991 * If we are using h/w performance counters, save context. 992 */ 993 #if PERFCTRS 994 if (PMC_ENABLED(p)) 995 pmc_save_context(p); 996 #endif 997 998 /* 999 * Switch to the new current process. When we 1000 * run again, we'll return back here. 1001 */ 1002 uvmexp.swtch++; 1003 if (newl == NULL) { 1004 retval = cpu_switch(l, NULL); 1005 } else { 1006 remrunqueue(newl); 1007 cpu_switchto(l, newl); 1008 retval = 0; 1009 } 1010 1011 /* 1012 * If we are using h/w performance counters, restore context. 1013 */ 1014 #if PERFCTRS 1015 if (PMC_ENABLED(p)) 1016 pmc_restore_context(p); 1017 #endif 1018 1019 /* 1020 * Make sure that MD code released the scheduler lock before 1021 * resuming us. 1022 */ 1023 SCHED_ASSERT_UNLOCKED(); 1024 1025 /* 1026 * We're running again; record our new start time. We might 1027 * be running on a new CPU now, so don't use the cache'd 1028 * schedstate_percpu pointer. 1029 */ 1030 KDASSERT(l->l_cpu != NULL); 1031 KDASSERT(l->l_cpu == curcpu()); 1032 microtime(&l->l_cpu->ci_schedstate.spc_runtime); 1033 1034 /* 1035 * Reacquire the kernel_lock now. We do this after we've 1036 * released the scheduler lock to avoid deadlock, and before 1037 * we reacquire the interlock. 1038 */ 1039 KERNEL_LOCK_ACQUIRE_COUNT(hold_count); 1040 1041 return retval; 1042 } 1043 1044 /* 1045 * Initialize the (doubly-linked) run queues 1046 * to be empty. 1047 */ 1048 void 1049 rqinit() 1050 { 1051 int i; 1052 1053 for (i = 0; i < RUNQUE_NQS; i++) 1054 sched_qs[i].ph_link = sched_qs[i].ph_rlink = 1055 (struct lwp *)&sched_qs[i]; 1056 } 1057 1058 static inline void 1059 resched_proc(struct lwp *l, u_char pri) 1060 { 1061 struct cpu_info *ci; 1062 1063 /* 1064 * XXXSMP 1065 * Since l->l_cpu persists across a context switch, 1066 * this gives us *very weak* processor affinity, in 1067 * that we notify the CPU on which the process last 1068 * ran that it should try to switch. 1069 * 1070 * This does not guarantee that the process will run on 1071 * that processor next, because another processor might 1072 * grab it the next time it performs a context switch. 1073 * 1074 * This also does not handle the case where its last 1075 * CPU is running a higher-priority process, but every 1076 * other CPU is running a lower-priority process. There 1077 * are ways to handle this situation, but they're not 1078 * currently very pretty, and we also need to weigh the 1079 * cost of moving a process from one CPU to another. 1080 * 1081 * XXXSMP 1082 * There is also the issue of locking the other CPU's 1083 * sched state, which we currently do not do. 1084 */ 1085 ci = (l->l_cpu != NULL) ? l->l_cpu : curcpu(); 1086 if (pri < ci->ci_schedstate.spc_curpriority) 1087 need_resched(ci); 1088 } 1089 1090 /* 1091 * Change process state to be runnable, 1092 * placing it on the run queue if it is in memory, 1093 * and awakening the swapper if it isn't in memory. 1094 */ 1095 void 1096 setrunnable(struct lwp *l) 1097 { 1098 struct proc *p = l->l_proc; 1099 1100 SCHED_ASSERT_LOCKED(); 1101 1102 switch (l->l_stat) { 1103 case 0: 1104 case LSRUN: 1105 case LSONPROC: 1106 case LSZOMB: 1107 case LSDEAD: 1108 default: 1109 panic("setrunnable: lwp %p state was %d", l, l->l_stat); 1110 case LSSTOP: 1111 /* 1112 * If we're being traced (possibly because someone attached us 1113 * while we were stopped), check for a signal from the debugger. 1114 */ 1115 if ((p->p_flag & P_TRACED) != 0 && p->p_xstat != 0) { 1116 sigaddset(&p->p_sigctx.ps_siglist, p->p_xstat); 1117 CHECKSIGS(p); 1118 } 1119 case LSSLEEP: 1120 unsleep(l); /* e.g. when sending signals */ 1121 break; 1122 1123 case LSIDL: 1124 break; 1125 case LSSUSPENDED: 1126 break; 1127 } 1128 1129 if (l->l_proc->p_sa) 1130 sa_awaken(l); 1131 1132 l->l_stat = LSRUN; 1133 p->p_nrlwps++; 1134 1135 if (l->l_flag & L_INMEM) 1136 setrunqueue(l); 1137 1138 if (l->l_slptime > 1) 1139 updatepri(l); 1140 l->l_slptime = 0; 1141 if ((l->l_flag & L_INMEM) == 0) 1142 sched_wakeup((caddr_t)&proc0); 1143 else 1144 resched_proc(l, l->l_priority); 1145 } 1146 1147 /* 1148 * Compute the priority of a process when running in user mode. 1149 * Arrange to reschedule if the resulting priority is better 1150 * than that of the current process. 1151 */ 1152 void 1153 resetpriority(struct lwp *l) 1154 { 1155 unsigned int newpriority; 1156 struct proc *p = l->l_proc; 1157 1158 SCHED_ASSERT_LOCKED(); 1159 1160 newpriority = PUSER + (p->p_estcpu >> ESTCPU_SHIFT) + 1161 NICE_WEIGHT * (p->p_nice - NZERO); 1162 newpriority = min(newpriority, MAXPRI); 1163 l->l_usrpri = newpriority; 1164 resched_proc(l, l->l_usrpri); 1165 } 1166 1167 /* 1168 * Recompute priority for all LWPs in a process. 1169 */ 1170 void 1171 resetprocpriority(struct proc *p) 1172 { 1173 struct lwp *l; 1174 1175 LIST_FOREACH(l, &p->p_lwps, l_sibling) 1176 resetpriority(l); 1177 } 1178 1179 /* 1180 * We adjust the priority of the current process. The priority of a process 1181 * gets worse as it accumulates CPU time. The CPU usage estimator (p_estcpu) 1182 * is increased here. The formula for computing priorities (in kern_synch.c) 1183 * will compute a different value each time p_estcpu increases. This can 1184 * cause a switch, but unless the priority crosses a PPQ boundary the actual 1185 * queue will not change. The CPU usage estimator ramps up quite quickly 1186 * when the process is running (linearly), and decays away exponentially, at 1187 * a rate which is proportionally slower when the system is busy. The basic 1188 * principle is that the system will 90% forget that the process used a lot 1189 * of CPU time in 5 * loadav seconds. This causes the system to favor 1190 * processes which haven't run much recently, and to round-robin among other 1191 * processes. 1192 */ 1193 1194 void 1195 schedclock(struct lwp *l) 1196 { 1197 struct proc *p = l->l_proc; 1198 int s; 1199 1200 p->p_estcpu = ESTCPULIM(p->p_estcpu + (1 << ESTCPU_SHIFT)); 1201 SCHED_LOCK(s); 1202 resetpriority(l); 1203 SCHED_UNLOCK(s); 1204 1205 if (l->l_priority >= PUSER) 1206 l->l_priority = l->l_usrpri; 1207 } 1208 1209 void 1210 suspendsched() 1211 { 1212 struct lwp *l; 1213 int s; 1214 1215 /* 1216 * Convert all non-P_SYSTEM LSSLEEP or LSRUN processes to 1217 * LSSUSPENDED. 1218 */ 1219 proclist_lock_read(); 1220 SCHED_LOCK(s); 1221 LIST_FOREACH(l, &alllwp, l_list) { 1222 if ((l->l_proc->p_flag & P_SYSTEM) != 0) 1223 continue; 1224 1225 switch (l->l_stat) { 1226 case LSRUN: 1227 l->l_proc->p_nrlwps--; 1228 if ((l->l_flag & L_INMEM) != 0) 1229 remrunqueue(l); 1230 /* FALLTHROUGH */ 1231 case LSSLEEP: 1232 l->l_stat = LSSUSPENDED; 1233 break; 1234 case LSONPROC: 1235 /* 1236 * XXX SMP: we need to deal with processes on 1237 * others CPU ! 1238 */ 1239 break; 1240 default: 1241 break; 1242 } 1243 } 1244 SCHED_UNLOCK(s); 1245 proclist_unlock_read(); 1246 } 1247 1248 /* 1249 * scheduler_fork_hook: 1250 * 1251 * Inherit the parent's scheduler history. 1252 */ 1253 void 1254 scheduler_fork_hook(struct proc *parent, struct proc *child) 1255 { 1256 1257 child->p_estcpu = child->p_estcpu_inherited = parent->p_estcpu; 1258 child->p_forktime = schedcpu_ticks; 1259 } 1260 1261 /* 1262 * scheduler_wait_hook: 1263 * 1264 * Chargeback parents for the sins of their children. 1265 */ 1266 void 1267 scheduler_wait_hook(struct proc *parent, struct proc *child) 1268 { 1269 fixpt_t loadfac = loadfactor(averunnable.ldavg[0]); 1270 fixpt_t estcpu; 1271 1272 /* XXX Only if parent != init?? */ 1273 1274 estcpu = decay_cpu_batch(loadfac, child->p_estcpu_inherited, 1275 schedcpu_ticks - child->p_forktime); 1276 if (child->p_estcpu > estcpu) { 1277 parent->p_estcpu = 1278 ESTCPULIM(parent->p_estcpu + child->p_estcpu - estcpu); 1279 } 1280 } 1281 1282 /* 1283 * Low-level routines to access the run queue. Optimised assembler 1284 * routines can override these. 1285 */ 1286 1287 #ifndef __HAVE_MD_RUNQUEUE 1288 1289 /* 1290 * On some architectures, it's faster to use a MSB ordering for the priorites 1291 * than the traditional LSB ordering. 1292 */ 1293 #ifdef __HAVE_BIGENDIAN_BITOPS 1294 #define RQMASK(n) (0x80000000 >> (n)) 1295 #else 1296 #define RQMASK(n) (0x00000001 << (n)) 1297 #endif 1298 1299 /* 1300 * The primitives that manipulate the run queues. whichqs tells which 1301 * of the 32 queues qs have processes in them. Setrunqueue puts processes 1302 * into queues, remrunqueue removes them from queues. The running process is 1303 * on no queue, other processes are on a queue related to p->p_priority, 1304 * divided by 4 actually to shrink the 0-127 range of priorities into the 32 1305 * available queues. 1306 */ 1307 1308 #ifdef RQDEBUG 1309 static void 1310 checkrunqueue(int whichq, struct lwp *l) 1311 { 1312 const struct prochd * const rq = &sched_qs[whichq]; 1313 struct lwp *l2; 1314 int found = 0; 1315 int die = 0; 1316 int empty = 1; 1317 for (l2 = rq->ph_link; l2 != (void*) rq; l2 = l2->l_forw) { 1318 if (l2->l_stat != LSRUN) { 1319 printf("checkrunqueue[%d]: lwp %p state (%d) " 1320 " != LSRUN\n", whichq, l2, l2->l_stat); 1321 } 1322 if (l2->l_back->l_forw != l2) { 1323 printf("checkrunqueue[%d]: lwp %p back-qptr (%p) " 1324 "corrupt %p\n", whichq, l2, l2->l_back, 1325 l2->l_back->l_forw); 1326 die = 1; 1327 } 1328 if (l2->l_forw->l_back != l2) { 1329 printf("checkrunqueue[%d]: lwp %p forw-qptr (%p) " 1330 "corrupt %p\n", whichq, l2, l2->l_forw, 1331 l2->l_forw->l_back); 1332 die = 1; 1333 } 1334 if (l2 == l) 1335 found = 1; 1336 empty = 0; 1337 } 1338 if (empty && (sched_whichqs & RQMASK(whichq)) != 0) { 1339 printf("checkrunqueue[%d]: bit set for empty run-queue %p\n", 1340 whichq, rq); 1341 die = 1; 1342 } else if (!empty && (sched_whichqs & RQMASK(whichq)) == 0) { 1343 printf("checkrunqueue[%d]: bit clear for non-empty " 1344 "run-queue %p\n", whichq, rq); 1345 die = 1; 1346 } 1347 if (l != NULL && (sched_whichqs & RQMASK(whichq)) == 0) { 1348 printf("checkrunqueue[%d]: bit clear for active lwp %p\n", 1349 whichq, l); 1350 die = 1; 1351 } 1352 if (l != NULL && empty) { 1353 printf("checkrunqueue[%d]: empty run-queue %p with " 1354 "active lwp %p\n", whichq, rq, l); 1355 die = 1; 1356 } 1357 if (l != NULL && !found) { 1358 printf("checkrunqueue[%d]: lwp %p not in runqueue %p!", 1359 whichq, l, rq); 1360 die = 1; 1361 } 1362 if (die) 1363 panic("checkrunqueue: inconsistency found"); 1364 } 1365 #endif /* RQDEBUG */ 1366 1367 void 1368 setrunqueue(struct lwp *l) 1369 { 1370 struct prochd *rq; 1371 struct lwp *prev; 1372 const int whichq = l->l_priority / PPQ; 1373 1374 #ifdef RQDEBUG 1375 checkrunqueue(whichq, NULL); 1376 #endif 1377 #ifdef DIAGNOSTIC 1378 if (l->l_back != NULL || l->l_wchan != NULL || l->l_stat != LSRUN) 1379 panic("setrunqueue"); 1380 #endif 1381 sched_whichqs |= RQMASK(whichq); 1382 rq = &sched_qs[whichq]; 1383 prev = rq->ph_rlink; 1384 l->l_forw = (struct lwp *)rq; 1385 rq->ph_rlink = l; 1386 prev->l_forw = l; 1387 l->l_back = prev; 1388 #ifdef RQDEBUG 1389 checkrunqueue(whichq, l); 1390 #endif 1391 } 1392 1393 void 1394 remrunqueue(struct lwp *l) 1395 { 1396 struct lwp *prev, *next; 1397 const int whichq = l->l_priority / PPQ; 1398 #ifdef RQDEBUG 1399 checkrunqueue(whichq, l); 1400 #endif 1401 #ifdef DIAGNOSTIC 1402 if (((sched_whichqs & RQMASK(whichq)) == 0)) 1403 panic("remrunqueue: bit %d not set", whichq); 1404 #endif 1405 prev = l->l_back; 1406 l->l_back = NULL; 1407 next = l->l_forw; 1408 prev->l_forw = next; 1409 next->l_back = prev; 1410 if (prev == next) 1411 sched_whichqs &= ~RQMASK(whichq); 1412 #ifdef RQDEBUG 1413 checkrunqueue(whichq, NULL); 1414 #endif 1415 } 1416 1417 #undef RQMASK 1418 #endif /* !defined(__HAVE_MD_RUNQUEUE) */ 1419