kern_switch.c revision 104695
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 * $FreeBSD: head/sys/kern/kern_switch.c 104695 2002-10-09 02:33:36Z julian $ 27 */ 28 29/*** 30 31Here is the logic.. 32 33If there are N processors, then there are at most N KSEs (kernel 34schedulable entities) working to process threads that belong to a 35KSEGOUP (kg). If there are X of these KSEs actually running at the 36moment in question, then there are at most M (N-X) of these KSEs on 37the run queue, as running KSEs are not on the queue. 38 39Runnable threads are queued off the KSEGROUP in priority order. 40If there are M or more threads runnable, the top M threads 41(by priority) are 'preassigned' to the M KSEs not running. The KSEs take 42their priority from those threads and are put on the run queue. 43 44The last thread that had a priority high enough to have a KSE associated 45with it, AND IS ON THE RUN QUEUE is pointed to by 46kg->kg_last_assigned. If no threads queued off the KSEGROUP have KSEs 47assigned as all the available KSEs are activly running, or because there 48are no threads queued, that pointer is NULL. 49 50When a KSE is removed from the run queue to become runnable, we know 51it was associated with the highest priority thread in the queue (at the head 52of the queue). If it is also the last assigned we know M was 1 and must 53now be 0. Since the thread is no longer queued that pointer must be 54removed from it. Since we know there were no more KSEs available, 55(M was 1 and is now 0) and since we are not FREEING our KSE 56but using it, we know there are STILL no more KSEs available, we can prove 57that the next thread in the ksegrp list will not have a KSE to assign to 58it, so we can show that the pointer must be made 'invalid' (NULL). 59 60The pointer exists so that when a new thread is made runnable, it can 61have its priority compared with the last assigned thread to see if 62it should 'steal' its KSE or not.. i.e. is it 'earlier' 63on the list than that thread or later.. If it's earlier, then the KSE is 64removed from the last assigned (which is now not assigned a KSE) 65and reassigned to the new thread, which is placed earlier in the list. 66The pointer is then backed up to the previous thread (which may or may not 67be the new thread). 68 69When a thread sleeps or is removed, the KSE becomes available and if there 70are queued threads that are not assigned KSEs, the highest priority one of 71them is assigned the KSE, which is then placed back on the run queue at 72the approipriate place, and the kg->kg_last_assigned pointer is adjusted down 73to point to it. 74 75The following diagram shows 2 KSEs and 3 threads from a single process. 76 77 RUNQ: --->KSE---KSE--... (KSEs queued at priorities from threads) 78 \ \____ 79 \ \ 80 KSEGROUP---thread--thread--thread (queued in priority order) 81 \ / 82 \_______________/ 83 (last_assigned) 84 85The result of this scheme is that the M available KSEs are always 86queued at the priorities they have inherrited from the M highest priority 87threads for that KSEGROUP. If this situation changes, the KSEs are 88reassigned to keep this true. 89 90*/ 91 92#include <sys/param.h> 93#include <sys/systm.h> 94#include <sys/kernel.h> 95#include <sys/ktr.h> 96#include <sys/lock.h> 97#include <sys/mutex.h> 98#include <sys/proc.h> 99#include <sys/queue.h> 100#include <machine/critical.h> 101 102CTASSERT((RQB_BPW * RQB_LEN) == RQ_NQS); 103 104/* 105 * Global run queue. 106 */ 107static struct runq runq; 108SYSINIT(runq, SI_SUB_RUN_QUEUE, SI_ORDER_FIRST, runq_init, &runq) 109 110void panc(char *string1, char *string2); 111 112#if 0 113static void runq_readjust(struct runq *rq, struct kse *ke); 114#endif 115/************************************************************************ 116 * Functions that manipulate runnability from a thread perspective. * 117 ************************************************************************/ 118 119/* 120 * Select the KSE that will be run next. From that find the thread, and x 121 * remove it from the KSEGRP's run queue. If there is thread clustering, 122 * this will be what does it. 123 */ 124struct thread * 125choosethread(void) 126{ 127 struct kse *ke; 128 struct thread *td; 129 struct ksegrp *kg; 130 131retry: 132 if ((ke = runq_choose(&runq))) { 133 td = ke->ke_thread; 134 KASSERT((td->td_kse == ke), ("kse/thread mismatch")); 135 kg = ke->ke_ksegrp; 136 if (td->td_flags & TDF_UNBOUND) { 137 TAILQ_REMOVE(&kg->kg_runq, td, td_runq); 138 if (kg->kg_last_assigned == td) { 139 if (TAILQ_PREV(td, threadqueue, td_runq) 140 != NULL) 141 printf("Yo MAMA!\n"); 142 kg->kg_last_assigned = TAILQ_PREV(td, 143 threadqueue, td_runq); 144 } 145 /* 146 * If we have started running an upcall, 147 * Then TDF_UNBOUND WAS set because the thread was 148 * created without a KSE. Now that we have one, 149 * and it is our time to run, we make sure 150 * that BOUND semantics apply for the rest of 151 * the journey to userland, and into the UTS. 152 */ 153#ifdef NOTYET 154 if (td->td_flags & TDF_UPCALLING) 155 tdf->td_flags &= ~TDF_UNBOUND; 156#endif 157 } 158 kg->kg_runnable--; 159 CTR2(KTR_RUNQ, "choosethread: td=%p pri=%d", 160 td, td->td_priority); 161 } else { 162 /* Simulate runq_choose() having returned the idle thread */ 163 td = PCPU_GET(idlethread); 164 ke = td->td_kse; 165 CTR1(KTR_RUNQ, "choosethread: td=%p (idle)", td); 166 } 167 ke->ke_flags |= KEF_DIDRUN; 168 if (panicstr && ((td->td_proc->p_flag & P_SYSTEM) == 0 && 169 (td->td_flags & TDF_INPANIC) == 0)) 170 goto retry; 171 TD_SET_RUNNING(td); 172 return (td); 173} 174 175/* 176 * Given a KSE (now surplus or at least loanable), either assign a new 177 * runable thread to it 178 * (and put it in the run queue) or put it in the ksegrp's idle KSE list. 179 * Or aybe give it back to its owner if it's been loaned. 180 */ 181void 182kse_reassign(struct kse *ke) 183{ 184 struct ksegrp *kg; 185 struct thread *td; 186 struct thread *owner; 187 struct thread *original; 188 189 mtx_assert(&sched_lock, MA_OWNED); 190 kg = ke->ke_ksegrp; 191 owner = ke->ke_bound; 192 original = ke->ke_thread; 193 KASSERT(!(owner && ((owner->td_kse != ke) || 194 (owner->td_flags & TDF_UNBOUND))), 195 ("kse_reassign: bad thread bound state")); 196 197 /* 198 * Find the first unassigned thread 199 * If there is a 'last assigned' then see what's next. 200 * otherwise look at what is first. 201 */ 202 if ((td = kg->kg_last_assigned)) { 203 td = TAILQ_NEXT(td, td_runq); 204 } else { 205 td = TAILQ_FIRST(&kg->kg_runq); 206 } 207 208 /* 209 * If we found one assign it the kse, otherwise idle the kse. 210 */ 211 if (td) { 212 /* 213 * If the original is bound to us we can only be lent out so 214 * make a loan, otherwise we just drop the 215 * original thread. 216 */ 217 if (original) { 218 if (((original->td_flags & TDF_UNBOUND) == 0)) { 219 /* 220 * Put the owner on the side 221 */ 222 ke->ke_bound = original; 223 TD_SET_LOAN(original); 224 } else { 225 original->td_kse = NULL; 226 } 227 } 228 kg->kg_last_assigned = td; 229 td->td_kse = ke; 230 ke->ke_thread = td; 231 runq_add(&runq, ke); 232 /* 233 * if we have already borrowed this, 234 * just pass it to the new thread, 235 * otherwise, enact the loan. 236 */ 237 CTR2(KTR_RUNQ, "kse_reassign: ke%p -> td%p", ke, td); 238 return; 239 } 240 if (owner) { /* already loaned out */ 241 /* effectivly unloan it */ 242 TD_CLR_LOAN(owner); 243 ke->ke_thread = owner; 244 ke->ke_bound = NULL; 245 if (original) 246 original->td_kse = NULL; 247 original = owner; 248 249 if (TD_CAN_RUN(owner)) { 250 /* 251 * If the owner thread is now runnable, run it.. 252 * Let it have its KSE back. 253 */ 254 setrunqueue(owner); 255 CTR2(KTR_RUNQ, "kse_reassign: ke%p -> td%p (give back)", 256 ke, owner); 257 return; 258 } 259 } 260 /* 261 * Presetly NOT loaned out. 262 * If we are bound, we go on the loanable queue 263 * otherwise onto the free queue. 264 */ 265 if (original) { 266 if (((original->td_flags & TDF_UNBOUND) == 0)) { 267 ke->ke_state = KES_THREAD; 268 ke->ke_flags |= KEF_ONLOANQ; 269 ke->ke_bound = NULL; 270 TAILQ_INSERT_HEAD(&kg->kg_lq, ke, ke_kgrlist); 271 kg->kg_loan_kses++; 272 CTR1(KTR_RUNQ, "kse_reassign: ke%p on loan queue", ke); 273 return; 274 } else { 275 original->td_kse = NULL; 276 } 277 } 278 ke->ke_state = KES_IDLE; 279 ke->ke_thread = NULL; 280 TAILQ_INSERT_HEAD(&kg->kg_iq, ke, ke_kgrlist); 281 kg->kg_idle_kses++; 282 CTR1(KTR_RUNQ, "kse_reassign: ke%p idled", ke); 283} 284 285int 286kserunnable(void) 287{ 288 return runq_check(&runq); 289} 290 291/* 292 * Remove a thread from its KSEGRP's run queue. 293 * This in turn may remove it from a KSE if it was already assigned 294 * to one, possibly causing a new thread to be assigned to the KSE 295 * and the KSE getting a new priority (unless it's a BOUND thread/KSE pair). 296 */ 297void 298remrunqueue(struct thread *td) 299{ 300 struct thread *td2, *td3; 301 struct ksegrp *kg; 302 struct kse *ke; 303 304 mtx_assert(&sched_lock, MA_OWNED); 305 KASSERT ((TD_ON_RUNQ(td)), ("remrunqueue: Bad state on run queue")); 306 kg = td->td_ksegrp; 307 ke = td->td_kse; 308 /* 309 * If it's a bound thread/KSE pair, take the shortcut. All non-KSE 310 * threads are BOUND. 311 */ 312 CTR1(KTR_RUNQ, "remrunqueue: td%p", td); 313 kg->kg_runnable--; 314 TD_SET_CAN_RUN(td); 315 if ((td->td_flags & TDF_UNBOUND) == 0) { 316 /* Bring its kse with it, leave the thread attached */ 317 runq_remove(&runq, ke); 318 ke->ke_state = KES_THREAD; 319 return; 320 } 321 td3 = TAILQ_PREV(td, threadqueue, td_runq); 322 TAILQ_REMOVE(&kg->kg_runq, td, td_runq); 323 if (ke) { 324 /* 325 * This thread has been assigned to a KSE. 326 * We need to dissociate it and try assign the 327 * KSE to the next available thread. Then, we should 328 * see if we need to move the KSE in the run queues. 329 */ 330 td2 = kg->kg_last_assigned; 331 KASSERT((td2 != NULL), ("last assigned has wrong value ")); 332 if (td2 == td) 333 kg->kg_last_assigned = td3; 334 td->td_kse = NULL; 335 ke->ke_thread = NULL; 336 kse_reassign(ke); 337 } 338} 339 340void 341setrunqueue(struct thread *td) 342{ 343 struct kse *ke; 344 struct ksegrp *kg; 345 struct thread *td2; 346 struct thread *tda; 347 348 CTR1(KTR_RUNQ, "setrunqueue: td%p", td); 349 mtx_assert(&sched_lock, MA_OWNED); 350 KASSERT((TD_CAN_RUN(td) || TD_IS_RUNNING(td)), 351 ("setrunqueue: bad thread state")); 352 TD_SET_RUNQ(td); 353 kg = td->td_ksegrp; 354 kg->kg_runnable++; 355 if ((td->td_proc->p_flag & P_KSES) == 0) { 356 /* 357 * Common path optimisation: Only one of everything 358 * and the KSE is always already attached. 359 * Totally ignore the ksegrp run queue. 360 */ 361 runq_add(&runq, td->td_kse); 362 return; 363 } 364 if ((td->td_flags & TDF_UNBOUND) == 0) { 365 KASSERT((td->td_kse != NULL), 366 ("queueing BAD thread to run queue")); 367 ke = td->td_kse; 368 ke->ke_bound = NULL; 369 if (ke->ke_flags & KEF_ONLOANQ) { 370 ke->ke_flags &= ~KEF_ONLOANQ; 371 TAILQ_REMOVE(&kg->kg_lq, ke, ke_kgrlist); 372 kg->kg_loan_kses--; 373 } 374 runq_add(&runq, td->td_kse); 375 return; 376 } 377 378 /* 379 * Ok, so we are threading with this thread. 380 * We don't have a KSE, see if we can get one.. 381 */ 382 tda = kg->kg_last_assigned; 383 if ((ke = td->td_kse) == NULL) { 384 /* 385 * We will need a KSE, see if there is one.. 386 * First look for a free one, before getting desperate. 387 * If we can't get one, our priority is not high enough.. 388 * that's ok.. 389 */ 390 if (kg->kg_idle_kses) { 391 /* 392 * There is a free one so it's ours for the asking.. 393 */ 394 ke = TAILQ_FIRST(&kg->kg_iq); 395 TAILQ_REMOVE(&kg->kg_iq, ke, ke_kgrlist); 396 ke->ke_state = KES_THREAD; 397 kg->kg_idle_kses--; 398 } else if (kg->kg_loan_kses) { 399 /* 400 * Failing that see if we can borrow one. 401 */ 402 ke = TAILQ_FIRST(&kg->kg_lq); 403 TAILQ_REMOVE(&kg->kg_lq, ke, ke_kgrlist); 404 ke->ke_flags &= ~KEF_ONLOANQ; 405 ke->ke_state = KES_THREAD; 406 TD_SET_LOAN(ke->ke_thread); 407 ke->ke_bound = ke->ke_thread; 408 ke->ke_thread = NULL; 409 kg->kg_loan_kses--; 410 } else if (tda && (tda->td_priority > td->td_priority)) { 411 /* 412 * None free, but there is one we can commandeer. 413 */ 414 ke = tda->td_kse; 415 tda->td_kse = NULL; 416 ke->ke_thread = NULL; 417 tda = kg->kg_last_assigned = 418 TAILQ_PREV(tda, threadqueue, td_runq); 419 runq_remove(&runq, ke); 420 } 421 } else { 422 /* 423 * Temporarily disassociate so it looks like the other cases. 424 */ 425 ke->ke_thread = NULL; 426 td->td_kse = NULL; 427 } 428 429 /* 430 * Add the thread to the ksegrp's run queue at 431 * the appropriate place. 432 */ 433 TAILQ_FOREACH(td2, &kg->kg_runq, td_runq) { 434 if (td2->td_priority > td->td_priority) { 435 TAILQ_INSERT_BEFORE(td2, td, td_runq); 436 break; 437 } 438 } 439 if (td2 == NULL) { 440 /* We ran off the end of the TAILQ or it was empty. */ 441 TAILQ_INSERT_TAIL(&kg->kg_runq, td, td_runq); 442 } 443 444 /* 445 * If we have a ke to use, then put it on the run queue and 446 * If needed, readjust the last_assigned pointer. 447 */ 448 if (ke) { 449 if (tda == NULL) { 450 /* 451 * No pre-existing last assigned so whoever is first 452 * gets the KSE we brought in.. (maybe us) 453 */ 454 td2 = TAILQ_FIRST(&kg->kg_runq); 455 KASSERT((td2->td_kse == NULL), 456 ("unexpected ke present")); 457 td2->td_kse = ke; 458 ke->ke_thread = td2; 459 kg->kg_last_assigned = td2; 460 } else if (tda->td_priority > td->td_priority) { 461 /* 462 * It's ours, grab it, but last_assigned is past us 463 * so don't change it. 464 */ 465 td->td_kse = ke; 466 ke->ke_thread = td; 467 } else { 468 /* 469 * We are past last_assigned, so 470 * put the new kse on whatever is next, 471 * which may or may not be us. 472 */ 473 td2 = TAILQ_NEXT(tda, td_runq); 474 kg->kg_last_assigned = td2; 475 td2->td_kse = ke; 476 ke->ke_thread = td2; 477 } 478 runq_add(&runq, ke); 479 } 480} 481 482/************************************************************************ 483 * Critical section marker functions * 484 ************************************************************************/ 485/* Critical sections that prevent preemption. */ 486void 487critical_enter(void) 488{ 489 struct thread *td; 490 491 td = curthread; 492 if (td->td_critnest == 0) 493 cpu_critical_enter(); 494 td->td_critnest++; 495} 496 497void 498critical_exit(void) 499{ 500 struct thread *td; 501 502 td = curthread; 503 if (td->td_critnest == 1) { 504 td->td_critnest = 0; 505 cpu_critical_exit(); 506 } else { 507 td->td_critnest--; 508 } 509} 510 511 512/************************************************************************ 513 * SYSTEM RUN QUEUE manipulations and tests * 514 ************************************************************************/ 515/* 516 * Initialize a run structure. 517 */ 518void 519runq_init(struct runq *rq) 520{ 521 int i; 522 523 bzero(rq, sizeof *rq); 524 for (i = 0; i < RQ_NQS; i++) 525 TAILQ_INIT(&rq->rq_queues[i]); 526} 527 528/* 529 * Clear the status bit of the queue corresponding to priority level pri, 530 * indicating that it is empty. 531 */ 532static __inline void 533runq_clrbit(struct runq *rq, int pri) 534{ 535 struct rqbits *rqb; 536 537 rqb = &rq->rq_status; 538 CTR4(KTR_RUNQ, "runq_clrbit: bits=%#x %#x bit=%#x word=%d", 539 rqb->rqb_bits[RQB_WORD(pri)], 540 rqb->rqb_bits[RQB_WORD(pri)] & ~RQB_BIT(pri), 541 RQB_BIT(pri), RQB_WORD(pri)); 542 rqb->rqb_bits[RQB_WORD(pri)] &= ~RQB_BIT(pri); 543} 544 545/* 546 * Find the index of the first non-empty run queue. This is done by 547 * scanning the status bits, a set bit indicates a non-empty queue. 548 */ 549static __inline int 550runq_findbit(struct runq *rq) 551{ 552 struct rqbits *rqb; 553 int pri; 554 int i; 555 556 rqb = &rq->rq_status; 557 for (i = 0; i < RQB_LEN; i++) 558 if (rqb->rqb_bits[i]) { 559 pri = RQB_FFS(rqb->rqb_bits[i]) + (i << RQB_L2BPW); 560 CTR3(KTR_RUNQ, "runq_findbit: bits=%#x i=%d pri=%d", 561 rqb->rqb_bits[i], i, pri); 562 return (pri); 563 } 564 565 return (-1); 566} 567 568/* 569 * Set the status bit of the queue corresponding to priority level pri, 570 * indicating that it is non-empty. 571 */ 572static __inline void 573runq_setbit(struct runq *rq, int pri) 574{ 575 struct rqbits *rqb; 576 577 rqb = &rq->rq_status; 578 CTR4(KTR_RUNQ, "runq_setbit: bits=%#x %#x bit=%#x word=%d", 579 rqb->rqb_bits[RQB_WORD(pri)], 580 rqb->rqb_bits[RQB_WORD(pri)] | RQB_BIT(pri), 581 RQB_BIT(pri), RQB_WORD(pri)); 582 rqb->rqb_bits[RQB_WORD(pri)] |= RQB_BIT(pri); 583} 584 585/* 586 * Add the KSE to the queue specified by its priority, and set the 587 * corresponding status bit. 588 */ 589void 590runq_add(struct runq *rq, struct kse *ke) 591{ 592 struct rqhead *rqh; 593 int pri; 594 595 mtx_assert(&sched_lock, MA_OWNED); 596 KASSERT((ke->ke_thread != NULL), ("runq_add: No thread on KSE")); 597 KASSERT((ke->ke_thread->td_kse != NULL), 598 ("runq_add: No KSE on thread")); 599 KASSERT(ke->ke_state != KES_ONRUNQ, 600 ("runq_add: kse %p (%s) already in run queue", ke, 601 ke->ke_proc->p_comm)); 602 KASSERT(ke->ke_proc->p_sflag & PS_INMEM, 603 ("runq_add: process swapped out")); 604 pri = ke->ke_thread->td_priority / RQ_PPQ; 605 ke->ke_rqindex = pri; 606 runq_setbit(rq, pri); 607 rqh = &rq->rq_queues[pri]; 608 CTR4(KTR_RUNQ, "runq_add: p=%p pri=%d %d rqh=%p", 609 ke->ke_proc, ke->ke_thread->td_priority, pri, rqh); 610 TAILQ_INSERT_TAIL(rqh, ke, ke_procq); 611 ke->ke_ksegrp->kg_runq_kses++; 612 ke->ke_state = KES_ONRUNQ; 613} 614 615/* 616 * Return true if there are runnable processes of any priority on the run 617 * queue, false otherwise. Has no side effects, does not modify the run 618 * queue structure. 619 */ 620int 621runq_check(struct runq *rq) 622{ 623 struct rqbits *rqb; 624 int i; 625 626 rqb = &rq->rq_status; 627 for (i = 0; i < RQB_LEN; i++) 628 if (rqb->rqb_bits[i]) { 629 CTR2(KTR_RUNQ, "runq_check: bits=%#x i=%d", 630 rqb->rqb_bits[i], i); 631 return (1); 632 } 633 CTR0(KTR_RUNQ, "runq_check: empty"); 634 635 return (0); 636} 637 638/* 639 * Find and remove the highest priority process from the run queue. 640 * If there are no runnable processes, the per-cpu idle process is 641 * returned. Will not return NULL under any circumstances. 642 */ 643struct kse * 644runq_choose(struct runq *rq) 645{ 646 struct rqhead *rqh; 647 struct kse *ke; 648 int pri; 649 650 mtx_assert(&sched_lock, MA_OWNED); 651 while ((pri = runq_findbit(rq)) != -1) { 652 rqh = &rq->rq_queues[pri]; 653 ke = TAILQ_FIRST(rqh); 654 KASSERT(ke != NULL, ("runq_choose: no proc on busy queue")); 655 CTR3(KTR_RUNQ, 656 "runq_choose: pri=%d kse=%p rqh=%p", pri, ke, rqh); 657 TAILQ_REMOVE(rqh, ke, ke_procq); 658 ke->ke_ksegrp->kg_runq_kses--; 659 if (TAILQ_EMPTY(rqh)) { 660 CTR0(KTR_RUNQ, "runq_choose: empty"); 661 runq_clrbit(rq, pri); 662 } 663 664 ke->ke_state = KES_THREAD; 665 KASSERT((ke->ke_thread != NULL), 666 ("runq_choose: No thread on KSE")); 667 KASSERT((ke->ke_thread->td_kse != NULL), 668 ("runq_choose: No KSE on thread")); 669 KASSERT(ke->ke_proc->p_sflag & PS_INMEM, 670 ("runq_choose: process swapped out")); 671 return (ke); 672 } 673 CTR1(KTR_RUNQ, "runq_choose: idleproc pri=%d", pri); 674 675 return (NULL); 676} 677 678/* 679 * Remove the KSE from the queue specified by its priority, and clear the 680 * corresponding status bit if the queue becomes empty. 681 * Caller must set ke->ke_state afterwards. 682 */ 683void 684runq_remove(struct runq *rq, struct kse *ke) 685{ 686 struct rqhead *rqh; 687 int pri; 688 689 KASSERT((ke->ke_state == KES_ONRUNQ), ("KSE not on run queue")); 690 mtx_assert(&sched_lock, MA_OWNED); 691 KASSERT(ke->ke_proc->p_sflag & PS_INMEM, 692 ("runq_remove: process swapped out")); 693 pri = ke->ke_rqindex; 694 rqh = &rq->rq_queues[pri]; 695 CTR4(KTR_RUNQ, "runq_remove: p=%p pri=%d %d rqh=%p", 696 ke, ke->ke_thread->td_priority, pri, rqh); 697 KASSERT(ke != NULL, ("runq_remove: no proc on busy queue")); 698 TAILQ_REMOVE(rqh, ke, ke_procq); 699 if (TAILQ_EMPTY(rqh)) { 700 CTR0(KTR_RUNQ, "runq_remove: empty"); 701 runq_clrbit(rq, pri); 702 } 703 ke->ke_state = KES_THREAD; 704 ke->ke_ksegrp->kg_runq_kses--; 705} 706 707#if 0 708static void 709runq_readjust(struct runq *rq, struct kse *ke) 710{ 711 712 if (ke->ke_rqindex != (ke->ke_thread->td_priority / RQ_PPQ)) { 713 runq_remove(rq, ke); 714 runq_add(rq, ke); 715 } 716} 717#endif 718 719#if 0 720void 721panc(char *string1, char *string2) 722{ 723 printf("%s", string1); 724 Debugger(string2); 725} 726 727void 728thread_sanity_check(struct thread *td, char *string) 729{ 730 struct proc *p; 731 struct ksegrp *kg; 732 struct kse *ke; 733 struct thread *td2 = NULL; 734 unsigned int prevpri; 735 int saw_lastassigned = 0; 736 int unassigned = 0; 737 int assigned = 0; 738 739 p = td->td_proc; 740 kg = td->td_ksegrp; 741 ke = td->td_kse; 742 743 744 if (ke) { 745 if (p != ke->ke_proc) { 746 panc(string, "wrong proc"); 747 } 748 if (ke->ke_thread != td) { 749 panc(string, "wrong thread"); 750 } 751 } 752 753 if ((p->p_flag & P_KSES) == 0) { 754 if (ke == NULL) { 755 panc(string, "non KSE thread lost kse"); 756 } 757 } else { 758 prevpri = 0; 759 saw_lastassigned = 0; 760 unassigned = 0; 761 assigned = 0; 762 TAILQ_FOREACH(td2, &kg->kg_runq, td_runq) { 763 if (td2->td_priority < prevpri) { 764 panc(string, "thread runqueue unosorted"); 765 } 766 if ((td2->td_state == TDS_RUNQ) && 767 td2->td_kse && 768 (td2->td_kse->ke_state != KES_ONRUNQ)) { 769 panc(string, "KSE wrong state"); 770 } 771 prevpri = td2->td_priority; 772 if (td2->td_kse) { 773 assigned++; 774 if (unassigned) { 775 panc(string, "unassigned before assigned"); 776 } 777 if (kg->kg_last_assigned == NULL) { 778 panc(string, "lastassigned corrupt"); 779 } 780 if (saw_lastassigned) { 781 panc(string, "last assigned not last"); 782 } 783 if (td2->td_kse->ke_thread != td2) { 784 panc(string, "mismatched kse/thread"); 785 } 786 } else { 787 unassigned++; 788 } 789 if (td2 == kg->kg_last_assigned) { 790 saw_lastassigned = 1; 791 if (td2->td_kse == NULL) { 792 panc(string, "last assigned not assigned"); 793 } 794 } 795 } 796 if (kg->kg_last_assigned && (saw_lastassigned == 0)) { 797 panc(string, "where on earth does lastassigned point?"); 798 } 799 FOREACH_THREAD_IN_GROUP(kg, td2) { 800 if (((td2->td_flags & TDF_UNBOUND) == 0) && 801 (TD_ON_RUNQ(td2))) { 802 assigned++; 803 if (td2->td_kse == NULL) { 804 panc(string, "BOUND thread with no KSE"); 805 } 806 } 807 } 808#if 0 809 if ((unassigned + assigned) != kg->kg_runnable) { 810 panc(string, "wrong number in runnable"); 811 } 812#endif 813 } 814 if (assigned == 12345) { 815 printf("%p %p %p %p %p %d, %d", 816 td, td2, ke, kg, p, assigned, saw_lastassigned); 817 } 818} 819#endif 820 821