1 /* $NetBSD: kern_synch.c,v 1.160 2005/12/27 04:06:46 chs 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.160 2005/12/27 04:06:46 chs 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 uint32_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 #ifdef LOCKDEBUG 931 spinlock_switchcheck(); 932 simple_lock_switchcheck(); 933 #endif 934 935 /* 936 * Compute the amount of time during which the current 937 * process was running. 938 */ 939 microtime(&tv); 940 u = p->p_rtime.tv_usec + 941 (tv.tv_usec - spc->spc_runtime.tv_usec); 942 s = p->p_rtime.tv_sec + (tv.tv_sec - spc->spc_runtime.tv_sec); 943 if (u < 0) { 944 u += 1000000; 945 s--; 946 } else if (u >= 1000000) { 947 u -= 1000000; 948 s++; 949 } 950 p->p_rtime.tv_usec = u; 951 p->p_rtime.tv_sec = s; 952 953 /* 954 * Check if the process exceeds its CPU resource allocation. 955 * If over max, kill it. In any case, if it has run for more 956 * than 10 minutes, reduce priority to give others a chance. 957 */ 958 rlim = &p->p_rlimit[RLIMIT_CPU]; 959 if (s >= rlim->rlim_cur) { 960 /* 961 * XXXSMP: we're inside the scheduler lock perimeter; 962 * use sched_psignal. 963 */ 964 if (s >= rlim->rlim_max) 965 sched_psignal(p, SIGKILL); 966 else { 967 sched_psignal(p, SIGXCPU); 968 if (rlim->rlim_cur < rlim->rlim_max) 969 rlim->rlim_cur += 5; 970 } 971 } 972 if (autonicetime && s > autonicetime && p->p_ucred->cr_uid && 973 p->p_nice == NZERO) { 974 p->p_nice = autoniceval + NZERO; 975 resetpriority(l); 976 } 977 978 /* 979 * Process is about to yield the CPU; clear the appropriate 980 * scheduling flags. 981 */ 982 spc->spc_flags &= ~SPCF_SWITCHCLEAR; 983 984 #ifdef KSTACK_CHECK_MAGIC 985 kstack_check_magic(l); 986 #endif 987 988 /* 989 * If we are using h/w performance counters, save context. 990 */ 991 #if PERFCTRS 992 if (PMC_ENABLED(p)) 993 pmc_save_context(p); 994 #endif 995 996 /* 997 * Switch to the new current process. When we 998 * run again, we'll return back here. 999 */ 1000 uvmexp.swtch++; 1001 if (newl == NULL) { 1002 retval = cpu_switch(l, NULL); 1003 } else { 1004 remrunqueue(newl); 1005 cpu_switchto(l, newl); 1006 retval = 0; 1007 } 1008 1009 /* 1010 * If we are using h/w performance counters, restore context. 1011 */ 1012 #if PERFCTRS 1013 if (PMC_ENABLED(p)) 1014 pmc_restore_context(p); 1015 #endif 1016 1017 /* 1018 * Make sure that MD code released the scheduler lock before 1019 * resuming us. 1020 */ 1021 SCHED_ASSERT_UNLOCKED(); 1022 1023 /* 1024 * We're running again; record our new start time. We might 1025 * be running on a new CPU now, so don't use the cache'd 1026 * schedstate_percpu pointer. 1027 */ 1028 KDASSERT(l->l_cpu != NULL); 1029 KDASSERT(l->l_cpu == curcpu()); 1030 microtime(&l->l_cpu->ci_schedstate.spc_runtime); 1031 1032 /* 1033 * Reacquire the kernel_lock now. We do this after we've 1034 * released the scheduler lock to avoid deadlock, and before 1035 * we reacquire the interlock. 1036 */ 1037 KERNEL_LOCK_ACQUIRE_COUNT(hold_count); 1038 1039 return retval; 1040 } 1041 1042 /* 1043 * Initialize the (doubly-linked) run queues 1044 * to be empty. 1045 */ 1046 void 1047 rqinit() 1048 { 1049 int i; 1050 1051 for (i = 0; i < RUNQUE_NQS; i++) 1052 sched_qs[i].ph_link = sched_qs[i].ph_rlink = 1053 (struct lwp *)&sched_qs[i]; 1054 } 1055 1056 static inline void 1057 resched_proc(struct lwp *l, u_char pri) 1058 { 1059 struct cpu_info *ci; 1060 1061 /* 1062 * XXXSMP 1063 * Since l->l_cpu persists across a context switch, 1064 * this gives us *very weak* processor affinity, in 1065 * that we notify the CPU on which the process last 1066 * ran that it should try to switch. 1067 * 1068 * This does not guarantee that the process will run on 1069 * that processor next, because another processor might 1070 * grab it the next time it performs a context switch. 1071 * 1072 * This also does not handle the case where its last 1073 * CPU is running a higher-priority process, but every 1074 * other CPU is running a lower-priority process. There 1075 * are ways to handle this situation, but they're not 1076 * currently very pretty, and we also need to weigh the 1077 * cost of moving a process from one CPU to another. 1078 * 1079 * XXXSMP 1080 * There is also the issue of locking the other CPU's 1081 * sched state, which we currently do not do. 1082 */ 1083 ci = (l->l_cpu != NULL) ? l->l_cpu : curcpu(); 1084 if (pri < ci->ci_schedstate.spc_curpriority) 1085 need_resched(ci); 1086 } 1087 1088 /* 1089 * Change process state to be runnable, 1090 * placing it on the run queue if it is in memory, 1091 * and awakening the swapper if it isn't in memory. 1092 */ 1093 void 1094 setrunnable(struct lwp *l) 1095 { 1096 struct proc *p = l->l_proc; 1097 1098 SCHED_ASSERT_LOCKED(); 1099 1100 switch (l->l_stat) { 1101 case 0: 1102 case LSRUN: 1103 case LSONPROC: 1104 case LSZOMB: 1105 case LSDEAD: 1106 default: 1107 panic("setrunnable: lwp %p state was %d", l, l->l_stat); 1108 case LSSTOP: 1109 /* 1110 * If we're being traced (possibly because someone attached us 1111 * while we were stopped), check for a signal from the debugger. 1112 */ 1113 if ((p->p_flag & P_TRACED) != 0 && p->p_xstat != 0) { 1114 sigaddset(&p->p_sigctx.ps_siglist, p->p_xstat); 1115 CHECKSIGS(p); 1116 } 1117 case LSSLEEP: 1118 unsleep(l); /* e.g. when sending signals */ 1119 break; 1120 1121 case LSIDL: 1122 break; 1123 case LSSUSPENDED: 1124 break; 1125 } 1126 1127 if (l->l_proc->p_sa) 1128 sa_awaken(l); 1129 1130 l->l_stat = LSRUN; 1131 p->p_nrlwps++; 1132 1133 if (l->l_flag & L_INMEM) 1134 setrunqueue(l); 1135 1136 if (l->l_slptime > 1) 1137 updatepri(l); 1138 l->l_slptime = 0; 1139 if ((l->l_flag & L_INMEM) == 0) 1140 sched_wakeup((caddr_t)&proc0); 1141 else 1142 resched_proc(l, l->l_priority); 1143 } 1144 1145 /* 1146 * Compute the priority of a process when running in user mode. 1147 * Arrange to reschedule if the resulting priority is better 1148 * than that of the current process. 1149 */ 1150 void 1151 resetpriority(struct lwp *l) 1152 { 1153 unsigned int newpriority; 1154 struct proc *p = l->l_proc; 1155 1156 SCHED_ASSERT_LOCKED(); 1157 1158 newpriority = PUSER + (p->p_estcpu >> ESTCPU_SHIFT) + 1159 NICE_WEIGHT * (p->p_nice - NZERO); 1160 newpriority = min(newpriority, MAXPRI); 1161 l->l_usrpri = newpriority; 1162 resched_proc(l, l->l_usrpri); 1163 } 1164 1165 /* 1166 * Recompute priority for all LWPs in a process. 1167 */ 1168 void 1169 resetprocpriority(struct proc *p) 1170 { 1171 struct lwp *l; 1172 1173 LIST_FOREACH(l, &p->p_lwps, l_sibling) 1174 resetpriority(l); 1175 } 1176 1177 /* 1178 * We adjust the priority of the current process. The priority of a process 1179 * gets worse as it accumulates CPU time. The CPU usage estimator (p_estcpu) 1180 * is increased here. The formula for computing priorities (in kern_synch.c) 1181 * will compute a different value each time p_estcpu increases. This can 1182 * cause a switch, but unless the priority crosses a PPQ boundary the actual 1183 * queue will not change. The CPU usage estimator ramps up quite quickly 1184 * when the process is running (linearly), and decays away exponentially, at 1185 * a rate which is proportionally slower when the system is busy. The basic 1186 * principle is that the system will 90% forget that the process used a lot 1187 * of CPU time in 5 * loadav seconds. This causes the system to favor 1188 * processes which haven't run much recently, and to round-robin among other 1189 * processes. 1190 */ 1191 1192 void 1193 schedclock(struct lwp *l) 1194 { 1195 struct proc *p = l->l_proc; 1196 int s; 1197 1198 p->p_estcpu = ESTCPULIM(p->p_estcpu + (1 << ESTCPU_SHIFT)); 1199 SCHED_LOCK(s); 1200 resetpriority(l); 1201 SCHED_UNLOCK(s); 1202 1203 if (l->l_priority >= PUSER) 1204 l->l_priority = l->l_usrpri; 1205 } 1206 1207 void 1208 suspendsched() 1209 { 1210 struct lwp *l; 1211 int s; 1212 1213 /* 1214 * Convert all non-P_SYSTEM LSSLEEP or LSRUN processes to 1215 * LSSUSPENDED. 1216 */ 1217 proclist_lock_read(); 1218 SCHED_LOCK(s); 1219 LIST_FOREACH(l, &alllwp, l_list) { 1220 if ((l->l_proc->p_flag & P_SYSTEM) != 0) 1221 continue; 1222 1223 switch (l->l_stat) { 1224 case LSRUN: 1225 l->l_proc->p_nrlwps--; 1226 if ((l->l_flag & L_INMEM) != 0) 1227 remrunqueue(l); 1228 /* FALLTHROUGH */ 1229 case LSSLEEP: 1230 l->l_stat = LSSUSPENDED; 1231 break; 1232 case LSONPROC: 1233 /* 1234 * XXX SMP: we need to deal with processes on 1235 * others CPU ! 1236 */ 1237 break; 1238 default: 1239 break; 1240 } 1241 } 1242 SCHED_UNLOCK(s); 1243 proclist_unlock_read(); 1244 } 1245 1246 /* 1247 * scheduler_fork_hook: 1248 * 1249 * Inherit the parent's scheduler history. 1250 */ 1251 void 1252 scheduler_fork_hook(struct proc *parent, struct proc *child) 1253 { 1254 1255 child->p_estcpu = child->p_estcpu_inherited = parent->p_estcpu; 1256 child->p_forktime = schedcpu_ticks; 1257 } 1258 1259 /* 1260 * scheduler_wait_hook: 1261 * 1262 * Chargeback parents for the sins of their children. 1263 */ 1264 void 1265 scheduler_wait_hook(struct proc *parent, struct proc *child) 1266 { 1267 fixpt_t loadfac = loadfactor(averunnable.ldavg[0]); 1268 fixpt_t estcpu; 1269 1270 /* XXX Only if parent != init?? */ 1271 1272 estcpu = decay_cpu_batch(loadfac, child->p_estcpu_inherited, 1273 schedcpu_ticks - child->p_forktime); 1274 if (child->p_estcpu > estcpu) { 1275 parent->p_estcpu = 1276 ESTCPULIM(parent->p_estcpu + child->p_estcpu - estcpu); 1277 } 1278 } 1279 1280 /* 1281 * Low-level routines to access the run queue. Optimised assembler 1282 * routines can override these. 1283 */ 1284 1285 #ifndef __HAVE_MD_RUNQUEUE 1286 1287 /* 1288 * On some architectures, it's faster to use a MSB ordering for the priorites 1289 * than the traditional LSB ordering. 1290 */ 1291 #ifdef __HAVE_BIGENDIAN_BITOPS 1292 #define RQMASK(n) (0x80000000 >> (n)) 1293 #else 1294 #define RQMASK(n) (0x00000001 << (n)) 1295 #endif 1296 1297 /* 1298 * The primitives that manipulate the run queues. whichqs tells which 1299 * of the 32 queues qs have processes in them. Setrunqueue puts processes 1300 * into queues, remrunqueue removes them from queues. The running process is 1301 * on no queue, other processes are on a queue related to p->p_priority, 1302 * divided by 4 actually to shrink the 0-127 range of priorities into the 32 1303 * available queues. 1304 */ 1305 1306 #ifdef RQDEBUG 1307 static void 1308 checkrunqueue(int whichq, struct lwp *l) 1309 { 1310 const struct prochd * const rq = &sched_qs[whichq]; 1311 struct lwp *l2; 1312 int found = 0; 1313 int die = 0; 1314 int empty = 1; 1315 for (l2 = rq->ph_link; l2 != (void*) rq; l2 = l2->l_forw) { 1316 if (l2->l_stat != LSRUN) { 1317 printf("checkrunqueue[%d]: lwp %p state (%d) " 1318 " != LSRUN\n", whichq, l2, l2->l_stat); 1319 } 1320 if (l2->l_back->l_forw != l2) { 1321 printf("checkrunqueue[%d]: lwp %p back-qptr (%p) " 1322 "corrupt %p\n", whichq, l2, l2->l_back, 1323 l2->l_back->l_forw); 1324 die = 1; 1325 } 1326 if (l2->l_forw->l_back != l2) { 1327 printf("checkrunqueue[%d]: lwp %p forw-qptr (%p) " 1328 "corrupt %p\n", whichq, l2, l2->l_forw, 1329 l2->l_forw->l_back); 1330 die = 1; 1331 } 1332 if (l2 == l) 1333 found = 1; 1334 empty = 0; 1335 } 1336 if (empty && (sched_whichqs & RQMASK(whichq)) != 0) { 1337 printf("checkrunqueue[%d]: bit set for empty run-queue %p\n", 1338 whichq, rq); 1339 die = 1; 1340 } else if (!empty && (sched_whichqs & RQMASK(whichq)) == 0) { 1341 printf("checkrunqueue[%d]: bit clear for non-empty " 1342 "run-queue %p\n", whichq, rq); 1343 die = 1; 1344 } 1345 if (l != NULL && (sched_whichqs & RQMASK(whichq)) == 0) { 1346 printf("checkrunqueue[%d]: bit clear for active lwp %p\n", 1347 whichq, l); 1348 die = 1; 1349 } 1350 if (l != NULL && empty) { 1351 printf("checkrunqueue[%d]: empty run-queue %p with " 1352 "active lwp %p\n", whichq, rq, l); 1353 die = 1; 1354 } 1355 if (l != NULL && !found) { 1356 printf("checkrunqueue[%d]: lwp %p not in runqueue %p!", 1357 whichq, l, rq); 1358 die = 1; 1359 } 1360 if (die) 1361 panic("checkrunqueue: inconsistency found"); 1362 } 1363 #endif /* RQDEBUG */ 1364 1365 void 1366 setrunqueue(struct lwp *l) 1367 { 1368 struct prochd *rq; 1369 struct lwp *prev; 1370 const int whichq = l->l_priority / PPQ; 1371 1372 #ifdef RQDEBUG 1373 checkrunqueue(whichq, NULL); 1374 #endif 1375 #ifdef DIAGNOSTIC 1376 if (l->l_back != NULL || l->l_wchan != NULL || l->l_stat != LSRUN) 1377 panic("setrunqueue"); 1378 #endif 1379 sched_whichqs |= RQMASK(whichq); 1380 rq = &sched_qs[whichq]; 1381 prev = rq->ph_rlink; 1382 l->l_forw = (struct lwp *)rq; 1383 rq->ph_rlink = l; 1384 prev->l_forw = l; 1385 l->l_back = prev; 1386 #ifdef RQDEBUG 1387 checkrunqueue(whichq, l); 1388 #endif 1389 } 1390 1391 void 1392 remrunqueue(struct lwp *l) 1393 { 1394 struct lwp *prev, *next; 1395 const int whichq = l->l_priority / PPQ; 1396 #ifdef RQDEBUG 1397 checkrunqueue(whichq, l); 1398 #endif 1399 #ifdef DIAGNOSTIC 1400 if (((sched_whichqs & RQMASK(whichq)) == 0)) 1401 panic("remrunqueue: bit %d not set", whichq); 1402 #endif 1403 prev = l->l_back; 1404 l->l_back = NULL; 1405 next = l->l_forw; 1406 prev->l_forw = next; 1407 next->l_back = prev; 1408 if (prev == next) 1409 sched_whichqs &= ~RQMASK(whichq); 1410 #ifdef RQDEBUG 1411 checkrunqueue(whichq, NULL); 1412 #endif 1413 } 1414 1415 #undef RQMASK 1416 #endif /* !defined(__HAVE_MD_RUNQUEUE) */ 1417