kern_switch.c revision 135181
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/*** 28Here is the logic.. 29 30If there are N processors, then there are at most N KSEs (kernel 31schedulable entities) working to process threads that belong to a 32KSEGROUP (kg). If there are X of these KSEs actually running at the 33moment in question, then there are at most M (N-X) of these KSEs on 34the run queue, as running KSEs are not on the queue. 35 36Runnable threads are queued off the KSEGROUP in priority order. 37If there are M or more threads runnable, the top M threads 38(by priority) are 'preassigned' to the M KSEs not running. The KSEs take 39their priority from those threads and are put on the run queue. 40 41The last thread that had a priority high enough to have a KSE associated 42with it, AND IS ON THE RUN QUEUE is pointed to by 43kg->kg_last_assigned. If no threads queued off the KSEGROUP have KSEs 44assigned as all the available KSEs are activly running, or because there 45are no threads queued, that pointer is NULL. 46 47When a KSE is removed from the run queue to become runnable, we know 48it was associated with the highest priority thread in the queue (at the head 49of the queue). If it is also the last assigned we know M was 1 and must 50now be 0. Since the thread is no longer queued that pointer must be 51removed from it. Since we know there were no more KSEs available, 52(M was 1 and is now 0) and since we are not FREEING our KSE 53but using it, we know there are STILL no more KSEs available, we can prove 54that the next thread in the ksegrp list will not have a KSE to assign to 55it, so we can show that the pointer must be made 'invalid' (NULL). 56 57The pointer exists so that when a new thread is made runnable, it can 58have its priority compared with the last assigned thread to see if 59it should 'steal' its KSE or not.. i.e. is it 'earlier' 60on the list than that thread or later.. If it's earlier, then the KSE is 61removed from the last assigned (which is now not assigned a KSE) 62and reassigned to the new thread, which is placed earlier in the list. 63The pointer is then backed up to the previous thread (which may or may not 64be the new thread). 65 66When a thread sleeps or is removed, the KSE becomes available and if there 67are queued threads that are not assigned KSEs, the highest priority one of 68them is assigned the KSE, which is then placed back on the run queue at 69the approipriate place, and the kg->kg_last_assigned pointer is adjusted down 70to point to it. 71 72The following diagram shows 2 KSEs and 3 threads from a single process. 73 74 RUNQ: --->KSE---KSE--... (KSEs queued at priorities from threads) 75 \ \____ 76 \ \ 77 KSEGROUP---thread--thread--thread (queued in priority order) 78 \ / 79 \_______________/ 80 (last_assigned) 81 82The result of this scheme is that the M available KSEs are always 83queued at the priorities they have inherrited from the M highest priority 84threads for that KSEGROUP. If this situation changes, the KSEs are 85reassigned to keep this true. 86***/ 87 88#include <sys/cdefs.h> 89__FBSDID("$FreeBSD: head/sys/kern/kern_switch.c 135181 2004-09-13 23:02:52Z julian $"); 90 91#include "opt_sched.h" 92 93#ifndef KERN_SWITCH_INCLUDE 94#include <sys/param.h> 95#include <sys/systm.h> 96#include <sys/kdb.h> 97#include <sys/kernel.h> 98#include <sys/ktr.h> 99#include <sys/lock.h> 100#include <sys/mutex.h> 101#include <sys/proc.h> 102#include <sys/queue.h> 103#include <sys/sched.h> 104#else /* KERN_SWITCH_INCLUDE */ 105#if defined(SMP) && (defined(__i386__) || defined(__amd64__)) 106#include <sys/smp.h> 107#endif 108#include <machine/critical.h> 109#if defined(SMP) && defined(SCHED_4BSD) 110#include <sys/sysctl.h> 111#endif 112 113#ifdef FULL_PREEMPTION 114#ifndef PREEMPTION 115#error "The FULL_PREEMPTION option requires the PREEMPTION option" 116#endif 117#endif 118 119CTASSERT((RQB_BPW * RQB_LEN) == RQ_NQS); 120 121#define td_kse td_sched 122 123/************************************************************************ 124 * Functions that manipulate runnability from a thread perspective. * 125 ************************************************************************/ 126/* 127 * Select the KSE that will be run next. From that find the thread, and 128 * remove it from the KSEGRP's run queue. If there is thread clustering, 129 * this will be what does it. 130 */ 131struct thread * 132choosethread(void) 133{ 134 struct kse *ke; 135 struct thread *td; 136 struct ksegrp *kg; 137 138#if defined(SMP) && (defined(__i386__) || defined(__amd64__)) 139 if (smp_active == 0 && PCPU_GET(cpuid) != 0) { 140 /* Shutting down, run idlethread on AP's */ 141 td = PCPU_GET(idlethread); 142 ke = td->td_kse; 143 CTR1(KTR_RUNQ, "choosethread: td=%p (idle)", td); 144 ke->ke_flags |= KEF_DIDRUN; 145 TD_SET_RUNNING(td); 146 return (td); 147 } 148#endif 149 150retry: 151 ke = sched_choose(); 152 if (ke) { 153 td = ke->ke_thread; 154 KASSERT((td->td_kse == ke), ("kse/thread mismatch")); 155 kg = ke->ke_ksegrp; 156 if (td->td_proc->p_flag & P_HADTHREADS) { 157 if (kg->kg_last_assigned == td) { 158 kg->kg_last_assigned = TAILQ_PREV(td, 159 threadqueue, td_runq); 160 } 161 TAILQ_REMOVE(&kg->kg_runq, td, td_runq); 162 kg->kg_runnable--; 163 } 164 CTR2(KTR_RUNQ, "choosethread: td=%p pri=%d", 165 td, td->td_priority); 166 } else { 167 /* Simulate runq_choose() having returned the idle thread */ 168 td = PCPU_GET(idlethread); 169 ke = td->td_kse; 170 CTR1(KTR_RUNQ, "choosethread: td=%p (idle)", td); 171 } 172 ke->ke_flags |= KEF_DIDRUN; 173 174 /* 175 * If we are in panic, only allow system threads, 176 * plus the one we are running in, to be run. 177 */ 178 if (panicstr && ((td->td_proc->p_flag & P_SYSTEM) == 0 && 179 (td->td_flags & TDF_INPANIC) == 0)) { 180 /* note that it is no longer on the run queue */ 181 TD_SET_CAN_RUN(td); 182 goto retry; 183 } 184 185 TD_SET_RUNNING(td); 186 return (td); 187} 188 189/* 190 * Given a surplus system slot, try assign a new runnable thread to it. 191 * Called from: 192 * sched_thread_exit() (local) 193 * sched_switch() (local) 194 * sched_thread_exit() (local) 195 * remrunqueue() (local) 196 */ 197static void 198slot_fill(struct ksegrp *kg) 199{ 200 struct thread *td; 201 202 mtx_assert(&sched_lock, MA_OWNED); 203 while (kg->kg_avail_opennings > 0) { 204 /* 205 * Find the first unassigned thread 206 */ 207 if ((td = kg->kg_last_assigned) != NULL) 208 td = TAILQ_NEXT(td, td_runq); 209 else 210 td = TAILQ_FIRST(&kg->kg_runq); 211 212 /* 213 * If we found one, send it to the system scheduler. 214 */ 215 if (td) { 216 kg->kg_last_assigned = td; 217 kg->kg_avail_opennings--; 218 sched_add(td, SRQ_BORING); 219 CTR2(KTR_RUNQ, "slot_fill: td%p -> kg%p", td, kg); 220 } else { 221 /* no threads to use up the slots. quit now */ 222 break; 223 } 224 } 225} 226 227#ifdef SCHED_4BSD 228/* 229 * Remove a thread from its KSEGRP's run queue. 230 * This in turn may remove it from a KSE if it was already assigned 231 * to one, possibly causing a new thread to be assigned to the KSE 232 * and the KSE getting a new priority. 233 */ 234static void 235remrunqueue(struct thread *td) 236{ 237 struct thread *td2, *td3; 238 struct ksegrp *kg; 239 struct kse *ke; 240 241 mtx_assert(&sched_lock, MA_OWNED); 242 KASSERT((TD_ON_RUNQ(td)), ("remrunqueue: Bad state on run queue")); 243 kg = td->td_ksegrp; 244 ke = td->td_kse; 245 CTR1(KTR_RUNQ, "remrunqueue: td%p", td); 246 TD_SET_CAN_RUN(td); 247 /* 248 * If it is not a threaded process, take the shortcut. 249 */ 250 if ((td->td_proc->p_flag & P_HADTHREADS) == 0) { 251 /* remve from sys run queue and free up a slot */ 252 sched_rem(td); 253 kg->kg_avail_opennings++; 254 ke->ke_state = KES_THREAD; 255 return; 256 } 257 td3 = TAILQ_PREV(td, threadqueue, td_runq); 258 TAILQ_REMOVE(&kg->kg_runq, td, td_runq); 259 kg->kg_runnable--; 260 if (ke->ke_state == KES_ONRUNQ) { 261 /* 262 * This thread has been assigned to the system run queue. 263 * We need to dissociate it and try assign the 264 * KSE to the next available thread. Then, we should 265 * see if we need to move the KSE in the run queues. 266 */ 267 sched_rem(td); 268 kg->kg_avail_opennings++; 269 ke->ke_state = KES_THREAD; 270 td2 = kg->kg_last_assigned; 271 KASSERT((td2 != NULL), ("last assigned has wrong value")); 272 if (td2 == td) 273 kg->kg_last_assigned = td3; 274 /* slot_fill(kg); */ /* will replace it with another */ 275 } 276} 277#endif 278 279/* 280 * Change the priority of a thread that is on the run queue. 281 */ 282void 283adjustrunqueue( struct thread *td, int newpri) 284{ 285 struct ksegrp *kg; 286 struct kse *ke; 287 288 mtx_assert(&sched_lock, MA_OWNED); 289 KASSERT((TD_ON_RUNQ(td)), ("adjustrunqueue: Bad state on run queue")); 290 291 ke = td->td_kse; 292 CTR1(KTR_RUNQ, "adjustrunqueue: td%p", td); 293 /* 294 * If it is not a threaded process, take the shortcut. 295 */ 296 if ((td->td_proc->p_flag & P_HADTHREADS) == 0) { 297 /* We only care about the kse in the run queue. */ 298 td->td_priority = newpri; 299 if (ke->ke_rqindex != (newpri / RQ_PPQ)) { 300 sched_rem(td); 301 sched_add(td, SRQ_BORING); 302 } 303 return; 304 } 305 306 /* It is a threaded process */ 307 kg = td->td_ksegrp; 308 TD_SET_CAN_RUN(td); 309 if (ke->ke_state == KES_ONRUNQ) { 310 if (kg->kg_last_assigned == td) { 311 kg->kg_last_assigned = 312 TAILQ_PREV(td, threadqueue, td_runq); 313 } 314 sched_rem(td); 315 kg->kg_avail_opennings++; 316 } 317 TAILQ_REMOVE(&kg->kg_runq, td, td_runq); 318 kg->kg_runnable--; 319 td->td_priority = newpri; 320 setrunqueue(td, SRQ_BORING); 321} 322int limitcount; 323void 324setrunqueue(struct thread *td, int flags) 325{ 326 struct ksegrp *kg; 327 struct thread *td2; 328 struct thread *tda; 329 int count; 330 331 CTR3(KTR_RUNQ, "setrunqueue: td:%p kg:%p pid:%d", 332 td, td->td_ksegrp, td->td_proc->p_pid); 333 mtx_assert(&sched_lock, MA_OWNED); 334 KASSERT((td->td_inhibitors == 0), 335 ("setrunqueue: trying to run inhibitted thread")); 336 KASSERT((TD_CAN_RUN(td) || TD_IS_RUNNING(td)), 337 ("setrunqueue: bad thread state")); 338 TD_SET_RUNQ(td); 339 kg = td->td_ksegrp; 340 if ((td->td_proc->p_flag & P_HADTHREADS) == 0) { 341 /* 342 * Common path optimisation: Only one of everything 343 * and the KSE is always already attached. 344 * Totally ignore the ksegrp run queue. 345 */ 346 if (kg->kg_avail_opennings != 1) { 347 if (limitcount < 1) { 348 limitcount++; 349 printf("pid %d: corrected slot count (%d->1)\n", 350 td->td_proc->p_pid, kg->kg_avail_opennings); 351 352 } 353 kg->kg_avail_opennings = 1; 354 } 355 kg->kg_avail_opennings--; 356 sched_add(td, flags); 357 return; 358 } 359 360 tda = kg->kg_last_assigned; 361 if ((kg->kg_avail_opennings <= 0) && 362 (tda && (tda->td_priority > td->td_priority))) { 363 /* 364 * None free, but there is one we can commandeer. 365 */ 366 CTR2(KTR_RUNQ, 367 "setrunqueue: kg:%p: take slot from td: %p", kg, tda); 368 sched_rem(tda); 369 tda = kg->kg_last_assigned = 370 TAILQ_PREV(tda, threadqueue, td_runq); 371 kg->kg_avail_opennings++; 372 } 373 374 /* 375 * Add the thread to the ksegrp's run queue at 376 * the appropriate place. 377 */ 378 count = 0; 379 TAILQ_FOREACH(td2, &kg->kg_runq, td_runq) { 380 if (td2->td_priority > td->td_priority) { 381 kg->kg_runnable++; 382 TAILQ_INSERT_BEFORE(td2, td, td_runq); 383 break; 384 } 385 /* XXX Debugging hack */ 386 if (++count > 10000) { 387 printf("setrunqueue(): corrupt kq_runq, td= %p\n", td); 388 panic("deadlock in setrunqueue"); 389 } 390 } 391 if (td2 == NULL) { 392 /* We ran off the end of the TAILQ or it was empty. */ 393 kg->kg_runnable++; 394 TAILQ_INSERT_TAIL(&kg->kg_runq, td, td_runq); 395 } 396 397 /* 398 * If we have a slot to use, then put the thread on the system 399 * run queue and if needed, readjust the last_assigned pointer. 400 */ 401 if (kg->kg_avail_opennings > 0) { 402 if (tda == NULL) { 403 /* 404 * No pre-existing last assigned so whoever is first 405 * gets the KSE we brought in.. (maybe us) 406 */ 407 td2 = TAILQ_FIRST(&kg->kg_runq); 408 kg->kg_last_assigned = td2; 409 } else if (tda->td_priority > td->td_priority) { 410 td2 = td; 411 } else { 412 /* 413 * We are past last_assigned, so 414 * gave the next slot to whatever is next, 415 * which may or may not be us. 416 */ 417 td2 = TAILQ_NEXT(tda, td_runq); 418 kg->kg_last_assigned = td2; 419 } 420 kg->kg_avail_opennings--; 421 sched_add(td2, flags); 422 } else { 423 CTR3(KTR_RUNQ, "setrunqueue: held: td%p kg%p pid%d", 424 td, td->td_ksegrp, td->td_proc->p_pid); 425 } 426} 427 428/* 429 * Kernel thread preemption implementation. Critical sections mark 430 * regions of code in which preemptions are not allowed. 431 */ 432void 433critical_enter(void) 434{ 435 struct thread *td; 436 437 td = curthread; 438 if (td->td_critnest == 0) 439 cpu_critical_enter(td); 440 td->td_critnest++; 441} 442 443void 444critical_exit(void) 445{ 446 struct thread *td; 447 448 td = curthread; 449 KASSERT(td->td_critnest != 0, 450 ("critical_exit: td_critnest == 0")); 451 if (td->td_critnest == 1) { 452#ifdef PREEMPTION 453 mtx_assert(&sched_lock, MA_NOTOWNED); 454 if (td->td_pflags & TDP_OWEPREEMPT) { 455 mtx_lock_spin(&sched_lock); 456 mi_switch(SW_INVOL, NULL); 457 mtx_unlock_spin(&sched_lock); 458 } 459#endif 460 td->td_critnest = 0; 461 cpu_critical_exit(td); 462 } else { 463 td->td_critnest--; 464 } 465} 466 467/* 468 * This function is called when a thread is about to be put on run queue 469 * because it has been made runnable or its priority has been adjusted. It 470 * determines if the new thread should be immediately preempted to. If so, 471 * it switches to it and eventually returns true. If not, it returns false 472 * so that the caller may place the thread on an appropriate run queue. 473 */ 474int 475maybe_preempt(struct thread *td) 476{ 477#ifdef PREEMPTION 478 struct thread *ctd; 479 int cpri, pri; 480#endif 481 482 mtx_assert(&sched_lock, MA_OWNED); 483#ifdef PREEMPTION 484 /* 485 * The new thread should not preempt the current thread if any of the 486 * following conditions are true: 487 * 488 * - The current thread has a higher (numerically lower) or 489 * equivalent priority. Note that this prevents curthread from 490 * trying to preempt to itself. 491 * - It is too early in the boot for context switches (cold is set). 492 * - The current thread has an inhibitor set or is in the process of 493 * exiting. In this case, the current thread is about to switch 494 * out anyways, so there's no point in preempting. If we did, 495 * the current thread would not be properly resumed as well, so 496 * just avoid that whole landmine. 497 * - If the new thread's priority is not a realtime priority and 498 * the current thread's priority is not an idle priority and 499 * FULL_PREEMPTION is disabled. 500 * 501 * If all of these conditions are false, but the current thread is in 502 * a nested critical section, then we have to defer the preemption 503 * until we exit the critical section. Otherwise, switch immediately 504 * to the new thread. 505 */ 506 ctd = curthread; 507 KASSERT ((ctd->td_kse != NULL && ctd->td_kse->ke_thread == ctd), 508 ("thread has no (or wrong) sched-private part.")); 509 KASSERT((td->td_inhibitors == 0), 510 ("maybe_preempt: trying to run inhibitted thread")); 511 pri = td->td_priority; 512 cpri = ctd->td_priority; 513 if (pri >= cpri || cold /* || dumping */ || TD_IS_INHIBITED(ctd) || 514 td->td_kse->ke_state != KES_THREAD) 515 return (0); 516#ifndef FULL_PREEMPTION 517 if (!(pri >= PRI_MIN_ITHD && pri <= PRI_MAX_ITHD) && 518 !(cpri >= PRI_MIN_IDLE)) 519 return (0); 520#endif 521 if (ctd->td_critnest > 1) { 522 CTR1(KTR_PROC, "maybe_preempt: in critical section %d", 523 ctd->td_critnest); 524 ctd->td_pflags |= TDP_OWEPREEMPT; 525 return (0); 526 } 527 528 /* 529 * Our thread state says that we are already on a run queue, so 530 * update our state as if we had been dequeued by choosethread(). 531 */ 532 MPASS(TD_ON_RUNQ(td)); 533 TD_SET_RUNNING(td); 534 CTR3(KTR_PROC, "preempting to thread %p (pid %d, %s)\n", td, 535 td->td_proc->p_pid, td->td_proc->p_comm); 536 mi_switch(SW_INVOL, td); 537 return (1); 538#else 539 return (0); 540#endif 541} 542 543#if 0 544#ifndef PREEMPTION 545/* XXX: There should be a non-static version of this. */ 546static void 547printf_caddr_t(void *data) 548{ 549 printf("%s", (char *)data); 550} 551static char preempt_warning[] = 552 "WARNING: Kernel preemption is disabled, expect reduced performance.\n"; 553SYSINIT(preempt_warning, SI_SUB_COPYRIGHT, SI_ORDER_ANY, printf_caddr_t, 554 preempt_warning) 555#endif 556#endif 557 558/************************************************************************ 559 * SYSTEM RUN QUEUE manipulations and tests * 560 ************************************************************************/ 561/* 562 * Initialize a run structure. 563 */ 564void 565runq_init(struct runq *rq) 566{ 567 int i; 568 569 bzero(rq, sizeof *rq); 570 for (i = 0; i < RQ_NQS; i++) 571 TAILQ_INIT(&rq->rq_queues[i]); 572} 573 574/* 575 * Clear the status bit of the queue corresponding to priority level pri, 576 * indicating that it is empty. 577 */ 578static __inline void 579runq_clrbit(struct runq *rq, int pri) 580{ 581 struct rqbits *rqb; 582 583 rqb = &rq->rq_status; 584 CTR4(KTR_RUNQ, "runq_clrbit: bits=%#x %#x bit=%#x word=%d", 585 rqb->rqb_bits[RQB_WORD(pri)], 586 rqb->rqb_bits[RQB_WORD(pri)] & ~RQB_BIT(pri), 587 RQB_BIT(pri), RQB_WORD(pri)); 588 rqb->rqb_bits[RQB_WORD(pri)] &= ~RQB_BIT(pri); 589} 590 591/* 592 * Find the index of the first non-empty run queue. This is done by 593 * scanning the status bits, a set bit indicates a non-empty queue. 594 */ 595static __inline int 596runq_findbit(struct runq *rq) 597{ 598 struct rqbits *rqb; 599 int pri; 600 int i; 601 602 rqb = &rq->rq_status; 603 for (i = 0; i < RQB_LEN; i++) 604 if (rqb->rqb_bits[i]) { 605 pri = RQB_FFS(rqb->rqb_bits[i]) + (i << RQB_L2BPW); 606 CTR3(KTR_RUNQ, "runq_findbit: bits=%#x i=%d pri=%d", 607 rqb->rqb_bits[i], i, pri); 608 return (pri); 609 } 610 611 return (-1); 612} 613 614/* 615 * Set the status bit of the queue corresponding to priority level pri, 616 * indicating that it is non-empty. 617 */ 618static __inline void 619runq_setbit(struct runq *rq, int pri) 620{ 621 struct rqbits *rqb; 622 623 rqb = &rq->rq_status; 624 CTR4(KTR_RUNQ, "runq_setbit: bits=%#x %#x bit=%#x word=%d", 625 rqb->rqb_bits[RQB_WORD(pri)], 626 rqb->rqb_bits[RQB_WORD(pri)] | RQB_BIT(pri), 627 RQB_BIT(pri), RQB_WORD(pri)); 628 rqb->rqb_bits[RQB_WORD(pri)] |= RQB_BIT(pri); 629} 630 631/* 632 * Add the KSE to the queue specified by its priority, and set the 633 * corresponding status bit. 634 */ 635void 636runq_add(struct runq *rq, struct kse *ke) 637{ 638 struct rqhead *rqh; 639 int pri; 640 641 pri = ke->ke_thread->td_priority / RQ_PPQ; 642 ke->ke_rqindex = pri; 643 runq_setbit(rq, pri); 644 rqh = &rq->rq_queues[pri]; 645 CTR5(KTR_RUNQ, "runq_add: td=%p ke=%p pri=%d %d rqh=%p", 646 ke->ke_thread, ke, ke->ke_thread->td_priority, pri, rqh); 647 TAILQ_INSERT_TAIL(rqh, ke, ke_procq); 648} 649 650/* 651 * Return true if there are runnable processes of any priority on the run 652 * queue, false otherwise. Has no side effects, does not modify the run 653 * queue structure. 654 */ 655int 656runq_check(struct runq *rq) 657{ 658 struct rqbits *rqb; 659 int i; 660 661 rqb = &rq->rq_status; 662 for (i = 0; i < RQB_LEN; i++) 663 if (rqb->rqb_bits[i]) { 664 CTR2(KTR_RUNQ, "runq_check: bits=%#x i=%d", 665 rqb->rqb_bits[i], i); 666 return (1); 667 } 668 CTR0(KTR_RUNQ, "runq_check: empty"); 669 670 return (0); 671} 672 673#if defined(SMP) && defined(SCHED_4BSD) 674int runq_fuzz = 1; 675SYSCTL_INT(_kern_sched, OID_AUTO, runq_fuzz, CTLFLAG_RW, &runq_fuzz, 0, ""); 676#endif 677 678/* 679 * Find the highest priority process on the run queue. 680 */ 681struct kse * 682runq_choose(struct runq *rq) 683{ 684 struct rqhead *rqh; 685 struct kse *ke; 686 int pri; 687 688 mtx_assert(&sched_lock, MA_OWNED); 689 while ((pri = runq_findbit(rq)) != -1) { 690 rqh = &rq->rq_queues[pri]; 691#if defined(SMP) && defined(SCHED_4BSD) 692 /* fuzz == 1 is normal.. 0 or less are ignored */ 693 if (runq_fuzz > 1) { 694 /* 695 * In the first couple of entries, check if 696 * there is one for our CPU as a preference. 697 */ 698 int count = runq_fuzz; 699 int cpu = PCPU_GET(cpuid); 700 struct kse *ke2; 701 ke2 = ke = TAILQ_FIRST(rqh); 702 703 while (count-- && ke2) { 704 if (ke->ke_thread->td_lastcpu == cpu) { 705 ke = ke2; 706 break; 707 } 708 ke2 = TAILQ_NEXT(ke2, ke_procq); 709 } 710 } else 711#endif 712 ke = TAILQ_FIRST(rqh); 713 KASSERT(ke != NULL, ("runq_choose: no proc on busy queue")); 714 CTR3(KTR_RUNQ, 715 "runq_choose: pri=%d kse=%p rqh=%p", pri, ke, rqh); 716 return (ke); 717 } 718 CTR1(KTR_RUNQ, "runq_choose: idleproc pri=%d", pri); 719 720 return (NULL); 721} 722 723/* 724 * Remove the KSE from the queue specified by its priority, and clear the 725 * corresponding status bit if the queue becomes empty. 726 * Caller must set ke->ke_state afterwards. 727 */ 728void 729runq_remove(struct runq *rq, struct kse *ke) 730{ 731 struct rqhead *rqh; 732 int pri; 733 734 KASSERT(ke->ke_proc->p_sflag & PS_INMEM, 735 ("runq_remove: process swapped out")); 736 pri = ke->ke_rqindex; 737 rqh = &rq->rq_queues[pri]; 738 CTR5(KTR_RUNQ, "runq_remove: td=%p, ke=%p pri=%d %d rqh=%p", 739 ke->ke_thread, ke, ke->ke_thread->td_priority, pri, rqh); 740 KASSERT(ke != NULL, ("runq_remove: no proc on busy queue")); 741 TAILQ_REMOVE(rqh, ke, ke_procq); 742 if (TAILQ_EMPTY(rqh)) { 743 CTR0(KTR_RUNQ, "runq_remove: empty"); 744 runq_clrbit(rq, pri); 745 } 746} 747 748/****** functions that are temporarily here ***********/ 749#include <vm/uma.h> 750#define RANGEOF(type, start, end) (offsetof(type, end) - offsetof(type, start)) 751extern struct mtx kse_zombie_lock; 752 753/* 754 * Allocate scheduler specific per-process resources. 755 * The thread and ksegrp have already been linked in. 756 * In this case just set the default concurrency value. 757 * 758 * Called from: 759 * proc_init() (UMA init method) 760 */ 761void 762sched_newproc(struct proc *p, struct ksegrp *kg, struct thread *td) 763{ 764 765 /* This can go in sched_fork */ 766 sched_init_concurrency(kg); 767} 768 769/* 770 * Called by the uma process fini routine.. 771 * undo anything we may have done in the uma_init method. 772 * Panic if it's not all 1:1:1:1 773 * Called from: 774 * proc_fini() (UMA method) 775 */ 776void 777sched_destroyproc(struct proc *p) 778{ 779 780 /* this function slated for destruction */ 781 KASSERT((p->p_numthreads == 1), ("Cached proc with > 1 thread ")); 782 KASSERT((p->p_numksegrps == 1), ("Cached proc with > 1 ksegrp ")); 783} 784 785#define RANGEOF(type, start, end) (offsetof(type, end) - offsetof(type, start)) 786/* 787 * thread is being either created or recycled. 788 * Fix up the per-scheduler resources associated with it. 789 * Called from: 790 * sched_fork_thread() 791 * thread_dtor() (*may go away) 792 * thread_init() (*may go away) 793 */ 794void 795sched_newthread(struct thread *td) 796{ 797 struct td_sched *ke; 798 799 ke = (struct td_sched *) (td + 1); 800 bzero(ke, sizeof(*ke)); 801 td->td_sched = ke; 802 ke->ke_thread = td; 803 ke->ke_oncpu = NOCPU; 804 ke->ke_state = KES_THREAD; 805} 806 807/* 808 * Set up an initial concurrency of 1 809 * and set the given thread (if given) to be using that 810 * concurrency slot. 811 * May be used "offline"..before the ksegrp is attached to the world 812 * and thus wouldn't need schedlock in that case. 813 * Called from: 814 * thr_create() 815 * proc_init() (UMA) via sched_newproc() 816 */ 817void 818sched_init_concurrency(struct ksegrp *kg) 819{ 820 821 kg->kg_concurrency = 1; 822 kg->kg_avail_opennings = 1; 823} 824 825/* 826 * Change the concurrency of an existing ksegrp to N 827 * Called from: 828 * kse_create() 829 * kse_exit() 830 * thread_exit() 831 * thread_single() 832 */ 833void 834sched_set_concurrency(struct ksegrp *kg, int concurrency) 835{ 836 837 /* Handle the case for a declining concurrency */ 838 kg->kg_avail_opennings += (concurrency - kg->kg_concurrency); 839 kg->kg_concurrency = concurrency; 840} 841 842/* 843 * Called from thread_exit() for all exiting thread 844 * 845 * Not to be confused with sched_exit_thread() 846 * that is only called from thread_exit() for threads exiting 847 * without the rest of the process exiting because it is also called from 848 * sched_exit() and we wouldn't want to call it twice. 849 * XXX This can probably be fixed. 850 */ 851void 852sched_thread_exit(struct thread *td) 853{ 854 855 td->td_ksegrp->kg_avail_opennings++; 856 slot_fill(td->td_ksegrp); 857} 858 859#endif /* KERN_SWITCH_INCLUDE */ 860