kern_switch.c revision 131927
11638Srgrimes/* 250476Speter * Copyright (c) 2001 Jake Burkholder <jake@FreeBSD.org> 31638Srgrimes * All rights reserved. 43470Srgrimes * 53470Srgrimes * Redistribution and use in source and binary forms, with or without 61638Srgrimes * modification, are permitted provided that the following conditions 774942Sru * are met: 823559Swosch * 1. Redistributions of source code must retain the above copyright 91638Srgrimes * notice, this list of conditions and the following disclaimer. 1023559Swosch * 2. Redistributions in binary form must reproduce the above copyright 1123559Swosch * notice, this list of conditions and the following disclaimer in the 1223559Swosch * documentation and/or other materials provided with the distribution. 1323559Swosch * 1423559Swosch * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 1523559Swosch * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 1623559Swosch * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 1723559Swosch * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 1823559Swosch * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 1923559Swosch * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 2023559Swosch * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 2123559Swosch * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 2223559Swosch * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 2323559Swosch * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 2423559Swosch * SUCH DAMAGE. 2523559Swosch */ 2623559Swosch 271638Srgrimes/*** 281638SrgrimesHere is the logic.. 291638Srgrimes 3023578SwoschIf there are N processors, then there are at most N KSEs (kernel 3123578Swoschschedulable entities) working to process threads that belong to a 3223578SwoschKSEGROUP (kg). If there are X of these KSEs actually running at the 331638Srgrimesmoment in question, then there are at most M (N-X) of these KSEs on 341638Srgrimesthe run queue, as running KSEs are not on the queue. 351638Srgrimes 361638SrgrimesRunnable threads are queued off the KSEGROUP in priority order. 371638SrgrimesIf there are M or more threads runnable, the top M threads 381638Srgrimes(by priority) are 'preassigned' to the M KSEs not running. The KSEs take 391638Srgrimestheir priority from those threads and are put on the run queue. 401638Srgrimes 411638SrgrimesThe last thread that had a priority high enough to have a KSE associated 421638Srgrimeswith it, AND IS ON THE RUN QUEUE is pointed to by 431638Srgrimeskg->kg_last_assigned. If no threads queued off the KSEGROUP have KSEs 441638Srgrimesassigned as all the available KSEs are activly running, or because there 451638Srgrimesare no threads queued, that pointer is NULL. 461638Srgrimes 471638SrgrimesWhen a KSE is removed from the run queue to become runnable, we know 481638Srgrimesit was associated with the highest priority thread in the queue (at the head 491638Srgrimesof the queue). If it is also the last assigned we know M was 1 and must 501638Srgrimesnow be 0. Since the thread is no longer queued that pointer must be 511638Srgrimesremoved from it. Since we know there were no more KSEs available, 521638Srgrimes(M was 1 and is now 0) and since we are not FREEING our KSE 531638Srgrimesbut using it, we know there are STILL no more KSEs available, we can prove 541638Srgrimesthat the next thread in the ksegrp list will not have a KSE to assign to 551638Srgrimesit, so we can show that the pointer must be made 'invalid' (NULL). 561638Srgrimes 571638SrgrimesThe pointer exists so that when a new thread is made runnable, it can 581638Srgrimeshave its priority compared with the last assigned thread to see if 591638Srgrimesit should 'steal' its KSE or not.. i.e. is it 'earlier' 601638Srgrimeson the list than that thread or later.. If it's earlier, then the KSE is 611638Srgrimesremoved from the last assigned (which is now not assigned a KSE) 621638Srgrimesand reassigned to the new thread, which is placed earlier in the list. 631638SrgrimesThe pointer is then backed up to the previous thread (which may or may not 641638Srgrimesbe the new thread). 651638Srgrimes 661638SrgrimesWhen a thread sleeps or is removed, the KSE becomes available and if there 671638Srgrimesare queued threads that are not assigned KSEs, the highest priority one of 681638Srgrimesthem is assigned the KSE, which is then placed back on the run queue at 691638Srgrimesthe approipriate place, and the kg->kg_last_assigned pointer is adjusted down 701638Srgrimesto point to it. 711638Srgrimes 721638SrgrimesThe following diagram shows 2 KSEs and 3 threads from a single process. 731638Srgrimes 741638Srgrimes RUNQ: --->KSE---KSE--... (KSEs queued at priorities from threads) 751638Srgrimes \ \____ 761638Srgrimes \ \ 771638Srgrimes KSEGROUP---thread--thread--thread (queued in priority order) 781638Srgrimes \ / 791638Srgrimes \_______________/ 801638Srgrimes (last_assigned) 811638Srgrimes 821638SrgrimesThe result of this scheme is that the M available KSEs are always 831638Srgrimesqueued at the priorities they have inherrited from the M highest priority 841638Srgrimesthreads for that KSEGROUP. If this situation changes, the KSEs are 851638Srgrimesreassigned to keep this true. 861638Srgrimes***/ 871638Srgrimes 881638Srgrimes#include <sys/cdefs.h> 891638Srgrimes__FBSDID("$FreeBSD: head/sys/kern/kern_switch.c 131927 2004-07-10 21:36:01Z marcel $"); 901638Srgrimes 911638Srgrimes#include "opt_full_preemption.h" 921638Srgrimes 9383075Sru#include <sys/param.h> 941638Srgrimes#include <sys/systm.h> 9583075Sru#include <sys/kdb.h> 9683075Sru#include <sys/kernel.h> 971638Srgrimes#include <sys/ktr.h> 9883075Sru#include <sys/lock.h> 9983075Sru#include <sys/mutex.h> 10083075Sru#include <sys/proc.h> 1011638Srgrimes#include <sys/queue.h> 1021638Srgrimes#include <sys/sched.h> 1031638Srgrimes#if defined(SMP) && (defined(__i386__) || defined(__amd64__)) 1041638Srgrimes#include <sys/smp.h> 1051638Srgrimes#endif 1061638Srgrimes#include <machine/critical.h> 1071638Srgrimes 1081638SrgrimesCTASSERT((RQB_BPW * RQB_LEN) == RQ_NQS); 1091638Srgrimes 1101638Srgrimesvoid panc(char *string1, char *string2); 1111638Srgrimes 1121638Srgrimes#if 0 1131638Srgrimesstatic void runq_readjust(struct runq *rq, struct kse *ke); 1141638Srgrimes#endif 11574942Sru/************************************************************************ 1161638Srgrimes * Functions that manipulate runnability from a thread perspective. * 11758494Sru ************************************************************************/ 1181638Srgrimes/* 1191638Srgrimes * Select the KSE that will be run next. From that find the thread, and 1201638Srgrimes * remove it from the KSEGRP's run queue. If there is thread clustering, 12174942Sru * this will be what does it. 12274942Sru */ 1231638Srgrimesstruct thread * 1241638Srgrimeschoosethread(void) 1251638Srgrimes{ 1261638Srgrimes struct kse *ke; 1271638Srgrimes struct thread *td; 1281638Srgrimes struct ksegrp *kg; 1291638Srgrimes 1301638Srgrimes#if defined(SMP) && (defined(__i386__) || defined(__amd64__)) 1311638Srgrimes if (smp_active == 0 && PCPU_GET(cpuid) != 0) { 1321638Srgrimes /* Shutting down, run idlethread on AP's */ 1331638Srgrimes td = PCPU_GET(idlethread); 1341638Srgrimes ke = td->td_kse; 1351638Srgrimes CTR1(KTR_RUNQ, "choosethread: td=%p (idle)", td); 1361638Srgrimes ke->ke_flags |= KEF_DIDRUN; 1371638Srgrimes TD_SET_RUNNING(td); 1381638Srgrimes return (td); 1391638Srgrimes } 1401638Srgrimes#endif 1411638Srgrimes 1421638Srgrimesretry: 1431638Srgrimes ke = sched_choose(); 1441638Srgrimes if (ke) { 1451638Srgrimes td = ke->ke_thread; 1461638Srgrimes KASSERT((td->td_kse == ke), ("kse/thread mismatch")); 1471638Srgrimes kg = ke->ke_ksegrp; 1481638Srgrimes if (td->td_proc->p_flag & P_SA) { 1491638Srgrimes if (kg->kg_last_assigned == td) { 1501638Srgrimes kg->kg_last_assigned = TAILQ_PREV(td, 1511638Srgrimes threadqueue, td_runq); 1521638Srgrimes } 1531638Srgrimes TAILQ_REMOVE(&kg->kg_runq, td, td_runq); 1541638Srgrimes } 1551638Srgrimes kg->kg_runnable--; 1561638Srgrimes CTR2(KTR_RUNQ, "choosethread: td=%p pri=%d", 1571638Srgrimes td, td->td_priority); 1581638Srgrimes } else { 1591638Srgrimes /* Simulate runq_choose() having returned the idle thread */ 1601638Srgrimes td = PCPU_GET(idlethread); 1611638Srgrimes ke = td->td_kse; 1621638Srgrimes CTR1(KTR_RUNQ, "choosethread: td=%p (idle)", td); 1631638Srgrimes } 1641638Srgrimes ke->ke_flags |= KEF_DIDRUN; 1651638Srgrimes 1661638Srgrimes /* 1671638Srgrimes * If we are in panic, only allow system threads, 1681638Srgrimes * plus the one we are running in, to be run. 1691638Srgrimes */ 1701638Srgrimes if (panicstr && ((td->td_proc->p_flag & P_SYSTEM) == 0 && 1711638Srgrimes (td->td_flags & TDF_INPANIC) == 0)) { 1721638Srgrimes /* note that it is no longer on the run queue */ 1731638Srgrimes TD_SET_CAN_RUN(td); 1741638Srgrimes goto retry; 1751638Srgrimes } 1761638Srgrimes 1771638Srgrimes TD_SET_RUNNING(td); 1781638Srgrimes return (td); 1791638Srgrimes} 1801638Srgrimes 1811638Srgrimes/* 1821638Srgrimes * Given a surplus KSE, either assign a new runable thread to it 1831638Srgrimes * (and put it in the run queue) or put it in the ksegrp's idle KSE list. 1841638Srgrimes * Assumes that the original thread is not runnable. 1851638Srgrimes */ 1861638Srgrimesvoid 1871638Srgrimeskse_reassign(struct kse *ke) 1881638Srgrimes{ 1891638Srgrimes struct ksegrp *kg; 1901638Srgrimes struct thread *td; 1911638Srgrimes struct thread *original; 1921638Srgrimes 19316437Sphk mtx_assert(&sched_lock, MA_OWNED); 19416437Sphk original = ke->ke_thread; 19516437Sphk KASSERT(original == NULL || TD_IS_INHIBITED(original), 1961638Srgrimes ("reassigning KSE with runnable thread")); 1971638Srgrimes kg = ke->ke_ksegrp; 1981638Srgrimes if (original) 19988055Sru original->td_kse = NULL; 20088055Sru 20188055Sru /* 20288055Sru * Find the first unassigned thread 20388055Sru */ 2041638Srgrimes if ((td = kg->kg_last_assigned) != NULL) 2051638Srgrimes td = TAILQ_NEXT(td, td_runq); 2061638Srgrimes else 2071638Srgrimes td = TAILQ_FIRST(&kg->kg_runq); 2081638Srgrimes 2091638Srgrimes /* 2101638Srgrimes * If we found one, assign it the kse, otherwise idle the kse. 2111638Srgrimes */ 2121638Srgrimes if (td) { 2131638Srgrimes kg->kg_last_assigned = td; 2141638Srgrimes td->td_kse = ke; 2151638Srgrimes ke->ke_thread = td; 2161638Srgrimes sched_add(td); 2171638Srgrimes CTR2(KTR_RUNQ, "kse_reassign: ke%p -> td%p", ke, td); 2181638Srgrimes return; 2191638Srgrimes } 2201638Srgrimes 2211638Srgrimes ke->ke_state = KES_IDLE; 2221638Srgrimes ke->ke_thread = NULL; 22374942Sru TAILQ_INSERT_TAIL(&kg->kg_iq, ke, ke_kgrlist); 22474942Sru kg->kg_idle_kses++; 2251638Srgrimes CTR1(KTR_RUNQ, "kse_reassign: ke%p on idle queue", ke); 2261638Srgrimes return; 2271638Srgrimes} 2281638Srgrimes 22994424Sru#if 0 23094424Sru/* 23194424Sru * Remove a thread from its KSEGRP's run queue. 23294424Sru * This in turn may remove it from a KSE if it was already assigned 23394424Sru * to one, possibly causing a new thread to be assigned to the KSE 23475083Sru * and the KSE getting a new priority. 23575083Sru */ 23675083Srustatic void 23753965Smharoremrunqueue(struct thread *td) 23894424Sru{ 23994424Sru struct thread *td2, *td3; 2401638Srgrimes struct ksegrp *kg; 2411638Srgrimes struct kse *ke; 2421638Srgrimes 2431638Srgrimes mtx_assert(&sched_lock, MA_OWNED); 2441638Srgrimes KASSERT((TD_ON_RUNQ(td)), ("remrunqueue: Bad state on run queue")); 2451638Srgrimes kg = td->td_ksegrp; 2461638Srgrimes ke = td->td_kse; 24714701Sbde CTR1(KTR_RUNQ, "remrunqueue: td%p", td); 24814701Sbde kg->kg_runnable--; 24914701Sbde TD_SET_CAN_RUN(td); 25014701Sbde /* 2511638Srgrimes * If it is not a threaded process, take the shortcut. 25214701Sbde */ 25314701Sbde if ((td->td_proc->p_flag & P_SA) == 0) { 25414701Sbde /* Bring its kse with it, leave the thread attached */ 25514701Sbde sched_rem(td); 25614701Sbde ke->ke_state = KES_THREAD; 25714701Sbde return; 25814701Sbde } 25914701Sbde td3 = TAILQ_PREV(td, threadqueue, td_runq); 2601638Srgrimes TAILQ_REMOVE(&kg->kg_runq, td, td_runq); 2611638Srgrimes if (ke) { 2621638Srgrimes /* 2631638Srgrimes * This thread has been assigned to a KSE. 2641638Srgrimes * We need to dissociate it and try assign the 2651638Srgrimes * KSE to the next available thread. Then, we should 2661638Srgrimes * see if we need to move the KSE in the run queues. 2671638Srgrimes */ 26875284Sru sched_rem(td); 26975284Sru ke->ke_state = KES_THREAD; 27075284Sru td2 = kg->kg_last_assigned; 27175284Sru KASSERT((td2 != NULL), ("last assigned has wrong value")); 27275284Sru if (td2 == td) 27374942Sru kg->kg_last_assigned = td3; 27474942Sru kse_reassign(ke); 2751638Srgrimes } 2761638Srgrimes} 2771638Srgrimes#endif 2781638Srgrimes 2791638Srgrimes/* 2801638Srgrimes * Change the priority of a thread that is on the run queue. 2811638Srgrimes */ 2821638Srgrimesvoid 2831638Srgrimesadjustrunqueue( struct thread *td, int newpri) 2841638Srgrimes{ 2851638Srgrimes struct ksegrp *kg; 28658494Sru struct kse *ke; 2871638Srgrimes 2881638Srgrimes mtx_assert(&sched_lock, MA_OWNED); 2891638Srgrimes KASSERT((TD_ON_RUNQ(td)), ("adjustrunqueue: Bad state on run queue")); 2901638Srgrimes 2911638Srgrimes ke = td->td_kse; 2921638Srgrimes CTR1(KTR_RUNQ, "adjustrunqueue: td%p", td); 2931638Srgrimes /* 2941638Srgrimes * If it is not a threaded process, take the shortcut. 2951638Srgrimes */ 2961638Srgrimes if ((td->td_proc->p_flag & P_SA) == 0) { 2971638Srgrimes /* We only care about the kse in the run queue. */ 2981638Srgrimes td->td_priority = newpri; 2991638Srgrimes if (ke->ke_rqindex != (newpri / RQ_PPQ)) { 3001638Srgrimes sched_rem(td); 3011638Srgrimes sched_add(td); 3021638Srgrimes } 3031638Srgrimes return; 3041638Srgrimes } 3051638Srgrimes 3061638Srgrimes /* It is a threaded process */ 3071638Srgrimes kg = td->td_ksegrp; 3081638Srgrimes kg->kg_runnable--; 3091638Srgrimes TD_SET_CAN_RUN(td); 3101638Srgrimes if (ke) { 3111638Srgrimes if (kg->kg_last_assigned == td) { 3121638Srgrimes kg->kg_last_assigned = 3131638Srgrimes TAILQ_PREV(td, threadqueue, td_runq); 3141638Srgrimes } 3151638Srgrimes sched_rem(td); 3161638Srgrimes } 3171638Srgrimes TAILQ_REMOVE(&kg->kg_runq, td, td_runq); 3181638Srgrimes td->td_priority = newpri; 3191638Srgrimes setrunqueue(td); 3201638Srgrimes} 3211638Srgrimes 3221638Srgrimesvoid 3231638Srgrimessetrunqueue(struct thread *td) 3241638Srgrimes{ 3251638Srgrimes struct kse *ke; 3261638Srgrimes struct ksegrp *kg; 32774942Sru struct thread *td2; 3281638Srgrimes struct thread *tda; 3291638Srgrimes 3301638Srgrimes CTR1(KTR_RUNQ, "setrunqueue: td%p", td); 3311638Srgrimes mtx_assert(&sched_lock, MA_OWNED); 3321638Srgrimes KASSERT((TD_CAN_RUN(td) || TD_IS_RUNNING(td)), 3331638Srgrimes ("setrunqueue: bad thread state")); 33474942Sru TD_SET_RUNQ(td); 33574942Sru kg = td->td_ksegrp; 3361638Srgrimes kg->kg_runnable++; 3371638Srgrimes if ((td->td_proc->p_flag & P_SA) == 0) { 3381638Srgrimes /* 3391638Srgrimes * Common path optimisation: Only one of everything 3401638Srgrimes * and the KSE is always already attached. 341 * Totally ignore the ksegrp run queue. 342 */ 343 sched_add(td); 344 return; 345 } 346 347 tda = kg->kg_last_assigned; 348 if ((ke = td->td_kse) == NULL) { 349 if (kg->kg_idle_kses) { 350 /* 351 * There is a free one so it's ours for the asking.. 352 */ 353 ke = TAILQ_FIRST(&kg->kg_iq); 354 TAILQ_REMOVE(&kg->kg_iq, ke, ke_kgrlist); 355 ke->ke_state = KES_THREAD; 356 kg->kg_idle_kses--; 357 } else if (tda && (tda->td_priority > td->td_priority)) { 358 /* 359 * None free, but there is one we can commandeer. 360 */ 361 ke = tda->td_kse; 362 sched_rem(tda); 363 tda->td_kse = NULL; 364 ke->ke_thread = NULL; 365 tda = kg->kg_last_assigned = 366 TAILQ_PREV(tda, threadqueue, td_runq); 367 } 368 } else { 369 /* 370 * Temporarily disassociate so it looks like the other cases. 371 */ 372 ke->ke_thread = NULL; 373 td->td_kse = NULL; 374 } 375 376 /* 377 * Add the thread to the ksegrp's run queue at 378 * the appropriate place. 379 */ 380 TAILQ_FOREACH(td2, &kg->kg_runq, td_runq) { 381 if (td2->td_priority > td->td_priority) { 382 TAILQ_INSERT_BEFORE(td2, td, td_runq); 383 break; 384 } 385 } 386 if (td2 == NULL) { 387 /* We ran off the end of the TAILQ or it was empty. */ 388 TAILQ_INSERT_TAIL(&kg->kg_runq, td, td_runq); 389 } 390 391 /* 392 * If we have a ke to use, then put it on the run queue and 393 * If needed, readjust the last_assigned pointer. 394 */ 395 if (ke) { 396 if (tda == NULL) { 397 /* 398 * No pre-existing last assigned so whoever is first 399 * gets the KSE we brought in.. (maybe us) 400 */ 401 td2 = TAILQ_FIRST(&kg->kg_runq); 402 KASSERT((td2->td_kse == NULL), 403 ("unexpected ke present")); 404 td2->td_kse = ke; 405 ke->ke_thread = td2; 406 kg->kg_last_assigned = td2; 407 } else if (tda->td_priority > td->td_priority) { 408 /* 409 * It's ours, grab it, but last_assigned is past us 410 * so don't change it. 411 */ 412 td->td_kse = ke; 413 ke->ke_thread = td; 414 } else { 415 /* 416 * We are past last_assigned, so 417 * put the new kse on whatever is next, 418 * which may or may not be us. 419 */ 420 td2 = TAILQ_NEXT(tda, td_runq); 421 kg->kg_last_assigned = td2; 422 td2->td_kse = ke; 423 ke->ke_thread = td2; 424 } 425 sched_add(ke->ke_thread); 426 } 427} 428 429/* 430 * Kernel thread preemption implementation. Critical sections mark 431 * regions of code in which preemptions are not allowed. 432 */ 433void 434critical_enter(void) 435{ 436 struct thread *td; 437 438 td = curthread; 439 if (td->td_critnest == 0) 440 cpu_critical_enter(); 441 td->td_critnest++; 442} 443 444void 445critical_exit(void) 446{ 447 struct thread *td; 448 449 td = curthread; 450 KASSERT(td->td_critnest != 0, 451 ("critical_exit: td_critnest == 0")); 452 if (td->td_critnest == 1) { 453#ifdef PREEMPTION 454 if (td->td_flags & TDF_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(); 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) priority. 489 * - It is too early in the boot for context switches (cold is set). 490 * - The current thread has an inhibitor set or is in the process of 491 * exiting. In this case, the current thread is about to switch 492 * out anyways, so there's no point in preempting. If we did, 493 * the current thread would not be properly resumed as well, so 494 * just avoid that whole landmine. 495 * - If the new thread's priority is not a realtime priority and 496 * the current thread's priority is not an idle priority and 497 * FULL_PREEMPTION is disabled. 498 * 499 * If all of these conditions are false, but the current thread is in 500 * a nested critical section, then we have to defer the preemption 501 * until we exit the critical section. Otherwise, switch immediately 502 * to the new thread. 503 */ 504 ctd = curthread; 505 pri = td->td_priority; 506 cpri = ctd->td_priority; 507 if (pri >= cpri || cold /* || dumping */ || TD_IS_INHIBITED(ctd) || 508 td->td_kse->ke_state != KES_THREAD) 509 return (0); 510#ifndef FULL_PREEMPTION 511 if (!(pri >= PRI_MIN_ITHD && pri <= PRI_MAX_ITHD) && 512 !(cpri >= PRI_MIN_IDLE)) 513 return (0); 514#endif 515 if (ctd->td_critnest > 1) { 516 CTR1(KTR_PROC, "maybe_preempt: in critical section %d", 517 ctd->td_critnest); 518 ctd->td_flags |= TDF_OWEPREEMPT; 519 return (0); 520 } 521 522 /* 523 * Our thread state says that we are already on a run queue, so 524 * update our state as if we had been dequeued by choosethread(). 525 */ 526 MPASS(TD_ON_RUNQ(td)); 527 TD_SET_RUNNING(td); 528 CTR3(KTR_PROC, "preempting to thread %p (pid %d, %s)\n", td, 529 td->td_proc->p_pid, td->td_proc->p_comm); 530 mi_switch(SW_INVOL, td); 531 return (1); 532#else 533 return (0); 534#endif 535} 536 537#ifndef PREEMPTION 538/* XXX: There should be a non-static version of this. */ 539static void 540printf_caddr_t(void *data) 541{ 542 printf("%s", (char *)data); 543} 544static char preempt_warning[] = 545 "WARNING: Kernel preemption is disabled, expect reduced performance.\n"; 546SYSINIT(preempt_warning, SI_SUB_COPYRIGHT, SI_ORDER_ANY, printf_caddr_t, 547 preempt_warning) 548#endif 549 550/************************************************************************ 551 * SYSTEM RUN QUEUE manipulations and tests * 552 ************************************************************************/ 553/* 554 * Initialize a run structure. 555 */ 556void 557runq_init(struct runq *rq) 558{ 559 int i; 560 561 bzero(rq, sizeof *rq); 562 for (i = 0; i < RQ_NQS; i++) 563 TAILQ_INIT(&rq->rq_queues[i]); 564} 565 566/* 567 * Clear the status bit of the queue corresponding to priority level pri, 568 * indicating that it is empty. 569 */ 570static __inline void 571runq_clrbit(struct runq *rq, int pri) 572{ 573 struct rqbits *rqb; 574 575 rqb = &rq->rq_status; 576 CTR4(KTR_RUNQ, "runq_clrbit: bits=%#x %#x bit=%#x word=%d", 577 rqb->rqb_bits[RQB_WORD(pri)], 578 rqb->rqb_bits[RQB_WORD(pri)] & ~RQB_BIT(pri), 579 RQB_BIT(pri), RQB_WORD(pri)); 580 rqb->rqb_bits[RQB_WORD(pri)] &= ~RQB_BIT(pri); 581} 582 583/* 584 * Find the index of the first non-empty run queue. This is done by 585 * scanning the status bits, a set bit indicates a non-empty queue. 586 */ 587static __inline int 588runq_findbit(struct runq *rq) 589{ 590 struct rqbits *rqb; 591 int pri; 592 int i; 593 594 rqb = &rq->rq_status; 595 for (i = 0; i < RQB_LEN; i++) 596 if (rqb->rqb_bits[i]) { 597 pri = RQB_FFS(rqb->rqb_bits[i]) + (i << RQB_L2BPW); 598 CTR3(KTR_RUNQ, "runq_findbit: bits=%#x i=%d pri=%d", 599 rqb->rqb_bits[i], i, pri); 600 return (pri); 601 } 602 603 return (-1); 604} 605 606/* 607 * Set the status bit of the queue corresponding to priority level pri, 608 * indicating that it is non-empty. 609 */ 610static __inline void 611runq_setbit(struct runq *rq, int pri) 612{ 613 struct rqbits *rqb; 614 615 rqb = &rq->rq_status; 616 CTR4(KTR_RUNQ, "runq_setbit: bits=%#x %#x bit=%#x word=%d", 617 rqb->rqb_bits[RQB_WORD(pri)], 618 rqb->rqb_bits[RQB_WORD(pri)] | RQB_BIT(pri), 619 RQB_BIT(pri), RQB_WORD(pri)); 620 rqb->rqb_bits[RQB_WORD(pri)] |= RQB_BIT(pri); 621} 622 623/* 624 * Add the KSE to the queue specified by its priority, and set the 625 * corresponding status bit. 626 */ 627void 628runq_add(struct runq *rq, struct kse *ke) 629{ 630 struct rqhead *rqh; 631 int pri; 632 633 pri = ke->ke_thread->td_priority / RQ_PPQ; 634 ke->ke_rqindex = pri; 635 runq_setbit(rq, pri); 636 rqh = &rq->rq_queues[pri]; 637 CTR4(KTR_RUNQ, "runq_add: p=%p pri=%d %d rqh=%p", 638 ke->ke_proc, ke->ke_thread->td_priority, pri, rqh); 639 TAILQ_INSERT_TAIL(rqh, ke, ke_procq); 640} 641 642/* 643 * Return true if there are runnable processes of any priority on the run 644 * queue, false otherwise. Has no side effects, does not modify the run 645 * queue structure. 646 */ 647int 648runq_check(struct runq *rq) 649{ 650 struct rqbits *rqb; 651 int i; 652 653 rqb = &rq->rq_status; 654 for (i = 0; i < RQB_LEN; i++) 655 if (rqb->rqb_bits[i]) { 656 CTR2(KTR_RUNQ, "runq_check: bits=%#x i=%d", 657 rqb->rqb_bits[i], i); 658 return (1); 659 } 660 CTR0(KTR_RUNQ, "runq_check: empty"); 661 662 return (0); 663} 664 665/* 666 * Find the highest priority process on the run queue. 667 */ 668struct kse * 669runq_choose(struct runq *rq) 670{ 671 struct rqhead *rqh; 672 struct kse *ke; 673 int pri; 674 675 mtx_assert(&sched_lock, MA_OWNED); 676 while ((pri = runq_findbit(rq)) != -1) { 677 rqh = &rq->rq_queues[pri]; 678 ke = TAILQ_FIRST(rqh); 679 KASSERT(ke != NULL, ("runq_choose: no proc on busy queue")); 680 CTR3(KTR_RUNQ, 681 "runq_choose: pri=%d kse=%p rqh=%p", pri, ke, rqh); 682 return (ke); 683 } 684 CTR1(KTR_RUNQ, "runq_choose: idleproc pri=%d", pri); 685 686 return (NULL); 687} 688 689/* 690 * Remove the KSE from the queue specified by its priority, and clear the 691 * corresponding status bit if the queue becomes empty. 692 * Caller must set ke->ke_state afterwards. 693 */ 694void 695runq_remove(struct runq *rq, struct kse *ke) 696{ 697 struct rqhead *rqh; 698 int pri; 699 700 KASSERT(ke->ke_proc->p_sflag & PS_INMEM, 701 ("runq_remove: process swapped out")); 702 pri = ke->ke_rqindex; 703 rqh = &rq->rq_queues[pri]; 704 CTR4(KTR_RUNQ, "runq_remove: p=%p pri=%d %d rqh=%p", 705 ke, ke->ke_thread->td_priority, pri, rqh); 706 KASSERT(ke != NULL, ("runq_remove: no proc on busy queue")); 707 TAILQ_REMOVE(rqh, ke, ke_procq); 708 if (TAILQ_EMPTY(rqh)) { 709 CTR0(KTR_RUNQ, "runq_remove: empty"); 710 runq_clrbit(rq, pri); 711 } 712} 713 714#if 0 715void 716panc(char *string1, char *string2) 717{ 718 printf("%s", string1); 719 kdb_enter(string2); 720} 721 722void 723thread_sanity_check(struct thread *td, char *string) 724{ 725 struct proc *p; 726 struct ksegrp *kg; 727 struct kse *ke; 728 struct thread *td2 = NULL; 729 unsigned int prevpri; 730 int saw_lastassigned = 0; 731 int unassigned = 0; 732 int assigned = 0; 733 734 p = td->td_proc; 735 kg = td->td_ksegrp; 736 ke = td->td_kse; 737 738 739 if (ke) { 740 if (p != ke->ke_proc) { 741 panc(string, "wrong proc"); 742 } 743 if (ke->ke_thread != td) { 744 panc(string, "wrong thread"); 745 } 746 } 747 748 if ((p->p_flag & P_SA) == 0) { 749 if (ke == NULL) { 750 panc(string, "non KSE thread lost kse"); 751 } 752 } else { 753 prevpri = 0; 754 saw_lastassigned = 0; 755 unassigned = 0; 756 assigned = 0; 757 TAILQ_FOREACH(td2, &kg->kg_runq, td_runq) { 758 if (td2->td_priority < prevpri) { 759 panc(string, "thread runqueue unosorted"); 760 } 761 if ((td2->td_state == TDS_RUNQ) && 762 td2->td_kse && 763 (td2->td_kse->ke_state != KES_ONRUNQ)) { 764 panc(string, "KSE wrong state"); 765 } 766 prevpri = td2->td_priority; 767 if (td2->td_kse) { 768 assigned++; 769 if (unassigned) { 770 panc(string, "unassigned before assigned"); 771 } 772 if (kg->kg_last_assigned == NULL) { 773 panc(string, "lastassigned corrupt"); 774 } 775 if (saw_lastassigned) { 776 panc(string, "last assigned not last"); 777 } 778 if (td2->td_kse->ke_thread != td2) { 779 panc(string, "mismatched kse/thread"); 780 } 781 } else { 782 unassigned++; 783 } 784 if (td2 == kg->kg_last_assigned) { 785 saw_lastassigned = 1; 786 if (td2->td_kse == NULL) { 787 panc(string, "last assigned not assigned"); 788 } 789 } 790 } 791 if (kg->kg_last_assigned && (saw_lastassigned == 0)) { 792 panc(string, "where on earth does lastassigned point?"); 793 } 794#if 0 795 FOREACH_THREAD_IN_GROUP(kg, td2) { 796 if (((td2->td_flags & TDF_UNBOUND) == 0) && 797 (TD_ON_RUNQ(td2))) { 798 assigned++; 799 if (td2->td_kse == NULL) { 800 panc(string, "BOUND thread with no KSE"); 801 } 802 } 803 } 804#endif 805#if 0 806 if ((unassigned + assigned) != kg->kg_runnable) { 807 panc(string, "wrong number in runnable"); 808 } 809#endif 810 } 811 if (assigned == 12345) { 812 printf("%p %p %p %p %p %d, %d", 813 td, td2, ke, kg, p, assigned, saw_lastassigned); 814 } 815} 816#endif 817 818