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