kern_switch.c revision 108338
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 108338 2002-12-28 01:23:07Z 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 <sys/sched.h> 101#include <machine/critical.h> 102 103CTASSERT((RQB_BPW * RQB_LEN) == RQ_NQS); 104 105void panc(char *string1, char *string2); 106 107#if 0 108static void runq_readjust(struct runq *rq, struct kse *ke); 109#endif 110/************************************************************************ 111 * Functions that manipulate runnability from a thread perspective. * 112 ************************************************************************/ 113/* 114 * Select the KSE that will be run next. From that find the thread, and x 115 * remove it from the KSEGRP's run queue. If there is thread clustering, 116 * this will be what does it. 117 */ 118struct thread * 119choosethread(void) 120{ 121 struct kse *ke; 122 struct thread *td; 123 struct ksegrp *kg; 124 125retry: 126 if ((ke = sched_choose())) { 127 td = ke->ke_thread; 128 KASSERT((td->td_kse == ke), ("kse/thread mismatch")); 129 kg = ke->ke_ksegrp; 130 if (TD_IS_UNBOUND(td)) { 131 TAILQ_REMOVE(&kg->kg_runq, td, td_runq); 132 if (kg->kg_last_assigned == td) { 133 kg->kg_last_assigned = TAILQ_PREV(td, 134 threadqueue, td_runq); 135 } 136 } 137 kg->kg_runnable--; 138 CTR2(KTR_RUNQ, "choosethread: td=%p pri=%d", 139 td, td->td_priority); 140 } else { 141 /* Simulate runq_choose() having returned the idle thread */ 142 td = PCPU_GET(idlethread); 143 ke = td->td_kse; 144 CTR1(KTR_RUNQ, "choosethread: td=%p (idle)", td); 145 } 146 ke->ke_flags |= KEF_DIDRUN; 147 148 /* 149 * Only allow non system threads to run in panic 150 * if they are the one we are tracing. (I think.. [JRE]) 151 */ 152 if (panicstr && ((td->td_proc->p_flag & P_SYSTEM) == 0 && 153 (td->td_flags & TDF_INPANIC) == 0)) 154 goto retry; 155 156 TD_SET_RUNNING(td); 157 return (td); 158} 159 160/* 161 * Given a KSE (now surplus or at least loanable), either assign a new 162 * runable thread to it (and put it in the run queue) or put it in 163 * the ksegrp's idle KSE list. 164 * Or maybe give it back to its owner if it's been loaned. 165 * Assumes that the original thread is either not runnable or 166 * already on the run queue 167 */ 168void 169kse_reassign(struct kse *ke) 170{ 171 struct ksegrp *kg; 172 struct thread *td; 173 struct thread *owner; 174 struct thread *original; 175 int loaned; 176 177 KASSERT((ke->ke_owner), ("reassigning KSE with no owner")); 178 KASSERT((ke->ke_thread && TD_IS_INHIBITED(ke->ke_thread)), 179 ("reassigning KSE with no or runnable thread")); 180 mtx_assert(&sched_lock, MA_OWNED); 181 kg = ke->ke_ksegrp; 182 owner = ke->ke_owner; 183 loaned = TD_LENDER(owner); 184 original = ke->ke_thread; 185 186 if (TD_CAN_UNBIND(original) && (original->td_standin)) { 187 KASSERT((owner == original), 188 ("Early thread borrowing?")); 189 /* 190 * The outgoing thread is "threaded" and has never 191 * scheduled an upcall. 192 * decide whether this is a short or long term event 193 * and thus whether or not to schedule an upcall. 194 * if it is a short term event, just suspend it in 195 * a way that takes its KSE with it. 196 * Select the events for which we want to schedule upcalls. 197 * For now it's just sleep. 198 * Other threads that still have not fired an upcall 199 * are held to their KSE using the temorary Binding. 200 */ 201 if (TD_ON_SLEEPQ(original)) { 202 /* 203 * An bound thread that can still unbind itself 204 * has been scheduled out. 205 * If it is sleeping, then we need to schedule an 206 * upcall. 207 * XXXKSE eventually almost any inhibition could do. 208 */ 209 original->td_flags &= ~TDF_CAN_UNBIND; 210 original->td_flags |= TDF_UNBOUND; 211 thread_schedule_upcall(original, ke); 212 owner = ke->ke_owner; 213 loaned = 1; 214 } 215 } 216 217 /* 218 * If the current thread was borrowing, then make things consistent 219 * by giving it back to the owner for the moment. The original thread 220 * must be unbound and have already used its chance for 221 * firing off an upcall. Threads that have not yet made an upcall 222 * can not borrow KSEs. 223 */ 224 if (loaned) { 225 KASSERT((original->td_standin == NULL), 226 ("kse_reassign: borrower still has standin thread")); 227 TD_CLR_LOAN(owner); 228 ke->ke_thread = owner; 229 original->td_kse = NULL; /* give it amnesia */ 230 /* 231 * Upcalling threads have lower priority than all 232 * in-kernel threads, However threads that have loaned out 233 * their KSE and are NOT upcalling have the priority that 234 * they have. In other words, only look for other work if 235 * the owner is not runnable, OR is upcalling. 236 */ 237 if (TD_CAN_RUN(owner) && 238 ((owner->td_flags & TDF_UPCALLING) == 0)) { 239 setrunnable(owner); 240 CTR2(KTR_RUNQ, "kse_reassign: ke%p -> td%p (give back)", 241 ke, owner); 242 return; 243 } 244 } 245 246 /* 247 * Either the owner is not runnable, or is an upcall. 248 * Find the first unassigned thread 249 * If there is a 'last assigned' then see what's next. 250 * otherwise look at what is first. 251 */ 252 if ((td = kg->kg_last_assigned)) { 253 td = TAILQ_NEXT(td, td_runq); 254 } else { 255 td = TAILQ_FIRST(&kg->kg_runq); 256 } 257 258 /* 259 * If we found one assign it the kse, otherwise idle the kse. 260 */ 261 if (td) { 262 /* 263 * Assign the new thread to the KSE. 264 * and make the KSE runnable again, 265 */ 266 if (TD_IS_BOUND(owner)) { 267 /* 268 * If there is a reason to keep the previous 269 * owner, do so. 270 */ 271 TD_SET_LOAN(owner); 272 } else { 273 /* otherwise, cut it free */ 274 ke->ke_owner = td; 275 owner->td_kse = NULL; 276 } 277 kg->kg_last_assigned = td; 278 td->td_kse = ke; 279 ke->ke_thread = td; 280 sched_add(ke); 281 CTR2(KTR_RUNQ, "kse_reassign: ke%p -> td%p", ke, td); 282 return; 283 } 284 285 /* 286 * Now handle any waiting upcall. 287 * Since we didn't make them runnable before. 288 */ 289 if (TD_CAN_RUN(owner)) { 290 setrunnable(owner); 291 CTR2(KTR_RUNQ, "kse_reassign: ke%p -> td%p (give back)", 292 ke, owner); 293 return; 294 } 295 296 /* 297 * It is possible that this is the last thread in the group 298 * because the KSE is being shut down or the process 299 * is exiting. 300 */ 301 if (TD_IS_EXITING(owner) || (ke->ke_flags & KEF_EXIT)) { 302 ke->ke_thread = NULL; 303 owner->td_kse = NULL; 304 kse_unlink(ke); 305 return; 306 } 307 308 /* 309 * At this stage all we know is that the owner 310 * is the same as the 'active' thread in the KSE 311 * and that it is 312 * Presently NOT loaned out. 313 * Put it on the loanable queue. Make it fifo 314 * so that long term sleepers donate their KSE's first. 315 */ 316 KASSERT((TD_IS_BOUND(owner)), ("kse_reassign: UNBOUND lender")); 317 ke->ke_state = KES_THREAD; 318 ke->ke_flags |= KEF_ONLOANQ; 319 TAILQ_INSERT_TAIL(&kg->kg_lq, ke, ke_kgrlist); 320 kg->kg_loan_kses++; 321 CTR1(KTR_RUNQ, "kse_reassign: ke%p on loan queue", ke); 322 return; 323} 324 325#if 0 326/* 327 * Remove a thread from its KSEGRP's run queue. 328 * This in turn may remove it from a KSE if it was already assigned 329 * to one, possibly causing a new thread to be assigned to the KSE 330 * and the KSE getting a new priority (unless it's a BOUND thread/KSE pair). 331 */ 332static void 333remrunqueue(struct thread *td) 334{ 335 struct thread *td2, *td3; 336 struct ksegrp *kg; 337 struct kse *ke; 338 339 mtx_assert(&sched_lock, MA_OWNED); 340 KASSERT ((TD_ON_RUNQ(td)), ("remrunqueue: Bad state on run queue")); 341 kg = td->td_ksegrp; 342 ke = td->td_kse; 343 /* 344 * If it's a bound thread/KSE pair, take the shortcut. All non-KSE 345 * threads are BOUND. 346 */ 347 CTR1(KTR_RUNQ, "remrunqueue: td%p", td); 348 kg->kg_runnable--; 349 TD_SET_CAN_RUN(td); 350 if (TD_IS_BOUND(td)) { 351 /* Bring its kse with it, leave the thread attached */ 352 sched_rem(ke); 353 ke->ke_state = KES_THREAD; 354 return; 355 } 356 td3 = TAILQ_PREV(td, threadqueue, td_runq); 357 TAILQ_REMOVE(&kg->kg_runq, td, td_runq); 358 if (ke) { 359 /* 360 * This thread has been assigned to a KSE. 361 * We need to dissociate it and try assign the 362 * KSE to the next available thread. Then, we should 363 * see if we need to move the KSE in the run queues. 364 */ 365 sched_rem(ke); 366 ke->ke_state = KES_THREAD; 367 td2 = kg->kg_last_assigned; 368 KASSERT((td2 != NULL), ("last assigned has wrong value ")); 369 if (td2 == td) 370 kg->kg_last_assigned = td3; 371 kse_reassign(ke); 372 } 373} 374#endif 375 376/* 377 * Change the priority of a thread that is on the run queue. 378 */ 379void 380adjustrunqueue( struct thread *td, int newpri) 381{ 382 struct ksegrp *kg; 383 struct kse *ke; 384 385 mtx_assert(&sched_lock, MA_OWNED); 386 KASSERT ((TD_ON_RUNQ(td)), ("adjustrunqueue: Bad state on run queue")); 387 /* 388 * If it's a bound thread/KSE pair, take the shortcut. All non-KSE 389 * threads are BOUND. 390 */ 391 ke = td->td_kse; 392 CTR1(KTR_RUNQ, "adjustrunqueue: td%p", td); 393 if (TD_IS_BOUND(td)) { 394 /* We only care about the kse in the run queue. */ 395 td->td_priority = newpri; 396 if (ke->ke_rqindex != (newpri / RQ_PPQ)) { 397 sched_rem(ke); 398 sched_add(ke); 399 } 400 return; 401 } 402 /* 403 * An unbound thread. This is not optimised yet. 404 */ 405 kg = td->td_ksegrp; 406 kg->kg_runnable--; 407 TD_SET_CAN_RUN(td); 408 if (ke) { 409 if (kg->kg_last_assigned == td) { 410 kg->kg_last_assigned = 411 TAILQ_PREV(td, threadqueue, td_runq); 412 } 413 sched_rem(ke); 414 } 415 TAILQ_REMOVE(&kg->kg_runq, td, td_runq); 416 td->td_priority = newpri; 417 setrunqueue(td); 418} 419 420void 421setrunqueue(struct thread *td) 422{ 423 struct kse *ke; 424 struct ksegrp *kg; 425 struct thread *td2; 426 struct thread *tda; 427 428 CTR1(KTR_RUNQ, "setrunqueue: td%p", td); 429 mtx_assert(&sched_lock, MA_OWNED); 430 KASSERT((TD_CAN_RUN(td) || TD_IS_RUNNING(td)), 431 ("setrunqueue: bad thread state")); 432 TD_SET_RUNQ(td); 433 kg = td->td_ksegrp; 434 kg->kg_runnable++; 435 if ((td->td_proc->p_flag & P_KSES) == 0) { 436 /* 437 * Common path optimisation: Only one of everything 438 * and the KSE is always already attached. 439 * Totally ignore the ksegrp run queue. 440 */ 441 sched_add(td->td_kse); 442 return; 443 } 444 /* 445 * If the process is threaded but the thread is bound then 446 * there is still a little extra to do re. KSE loaning. 447 */ 448 if (TD_IS_BOUND(td)) { 449 KASSERT((td->td_kse != NULL), 450 ("queueing BAD thread to run queue")); 451 ke = td->td_kse; 452 KASSERT((ke->ke_owner == ke->ke_thread), 453 ("setrunqueue: Hey KSE loaned out")); 454 if (ke->ke_flags & KEF_ONLOANQ) { 455 ke->ke_flags &= ~KEF_ONLOANQ; 456 TAILQ_REMOVE(&kg->kg_lq, ke, ke_kgrlist); 457 kg->kg_loan_kses--; 458 } 459 sched_add(td->td_kse); 460 return; 461 } 462 463 /* 464 * Ok, so we are threading with this thread. 465 * We don't have a KSE, see if we can get one.. 466 */ 467 tda = kg->kg_last_assigned; 468 if ((ke = td->td_kse) == NULL) { 469 /* 470 * We will need a KSE, see if there is one.. 471 * First look for a free one, before getting desperate. 472 * If we can't get one, our priority is not high enough.. 473 * that's ok.. 474 */ 475 if (kg->kg_loan_kses) { 476 /* 477 * Failing that see if we can borrow one. 478 */ 479 ke = TAILQ_FIRST(&kg->kg_lq); 480 TAILQ_REMOVE(&kg->kg_lq, ke, ke_kgrlist); 481 ke->ke_flags &= ~KEF_ONLOANQ; 482 ke->ke_state = KES_THREAD; 483 TD_SET_LOAN(ke->ke_owner); 484 ke->ke_thread = NULL; 485 kg->kg_loan_kses--; 486 } else if (tda && (tda->td_priority > td->td_priority)) { 487 /* 488 * None free, but there is one we can commandeer. 489 */ 490 ke = tda->td_kse; 491 tda->td_kse = NULL; 492 ke->ke_thread = NULL; 493 tda = kg->kg_last_assigned = 494 TAILQ_PREV(tda, threadqueue, td_runq); 495 sched_rem(ke); 496 } 497 } else { 498 /* 499 * Temporarily disassociate so it looks like the other cases. 500 * If the owner wasn't lending before, then it is now.. 501 */ 502 if (!TD_LENDER(ke->ke_owner)) { 503 TD_SET_LOAN(ke->ke_owner); 504 } 505 ke->ke_thread = NULL; 506 td->td_kse = NULL; 507 } 508 509 /* 510 * Add the thread to the ksegrp's run queue at 511 * the appropriate place. 512 */ 513 TAILQ_FOREACH(td2, &kg->kg_runq, td_runq) { 514 if (td2->td_priority > td->td_priority) { 515 TAILQ_INSERT_BEFORE(td2, td, td_runq); 516 break; 517 } 518 } 519 if (td2 == NULL) { 520 /* We ran off the end of the TAILQ or it was empty. */ 521 TAILQ_INSERT_TAIL(&kg->kg_runq, td, td_runq); 522 } 523 524 /* 525 * If we have a ke to use, then put it on the run queue and 526 * If needed, readjust the last_assigned pointer. 527 */ 528 if (ke) { 529 if (tda == NULL) { 530 /* 531 * No pre-existing last assigned so whoever is first 532 * gets the KSE we brought in.. (maybe us) 533 */ 534 td2 = TAILQ_FIRST(&kg->kg_runq); 535 KASSERT((td2->td_kse == NULL), 536 ("unexpected ke present")); 537 td2->td_kse = ke; 538 ke->ke_thread = td2; 539 kg->kg_last_assigned = td2; 540 } else if (tda->td_priority > td->td_priority) { 541 /* 542 * It's ours, grab it, but last_assigned is past us 543 * so don't change it. 544 */ 545 td->td_kse = ke; 546 ke->ke_thread = td; 547 } else { 548 /* 549 * We are past last_assigned, so 550 * put the new kse on whatever is next, 551 * which may or may not be us. 552 */ 553 td2 = TAILQ_NEXT(tda, td_runq); 554 kg->kg_last_assigned = td2; 555 td2->td_kse = ke; 556 ke->ke_thread = td2; 557 } 558 sched_add(ke); 559 } 560} 561 562/************************************************************************ 563 * Critical section marker functions * 564 ************************************************************************/ 565/* Critical sections that prevent preemption. */ 566void 567critical_enter(void) 568{ 569 struct thread *td; 570 571 td = curthread; 572 if (td->td_critnest == 0) 573 cpu_critical_enter(); 574 td->td_critnest++; 575} 576 577void 578critical_exit(void) 579{ 580 struct thread *td; 581 582 td = curthread; 583 if (td->td_critnest == 1) { 584 td->td_critnest = 0; 585 cpu_critical_exit(); 586 } else { 587 td->td_critnest--; 588 } 589} 590 591 592/************************************************************************ 593 * SYSTEM RUN QUEUE manipulations and tests * 594 ************************************************************************/ 595/* 596 * Initialize a run structure. 597 */ 598void 599runq_init(struct runq *rq) 600{ 601 int i; 602 603 bzero(rq, sizeof *rq); 604 for (i = 0; i < RQ_NQS; i++) 605 TAILQ_INIT(&rq->rq_queues[i]); 606} 607 608/* 609 * Clear the status bit of the queue corresponding to priority level pri, 610 * indicating that it is empty. 611 */ 612static __inline void 613runq_clrbit(struct runq *rq, int pri) 614{ 615 struct rqbits *rqb; 616 617 rqb = &rq->rq_status; 618 CTR4(KTR_RUNQ, "runq_clrbit: bits=%#x %#x bit=%#x word=%d", 619 rqb->rqb_bits[RQB_WORD(pri)], 620 rqb->rqb_bits[RQB_WORD(pri)] & ~RQB_BIT(pri), 621 RQB_BIT(pri), RQB_WORD(pri)); 622 rqb->rqb_bits[RQB_WORD(pri)] &= ~RQB_BIT(pri); 623} 624 625/* 626 * Find the index of the first non-empty run queue. This is done by 627 * scanning the status bits, a set bit indicates a non-empty queue. 628 */ 629static __inline int 630runq_findbit(struct runq *rq) 631{ 632 struct rqbits *rqb; 633 int pri; 634 int i; 635 636 rqb = &rq->rq_status; 637 for (i = 0; i < RQB_LEN; i++) 638 if (rqb->rqb_bits[i]) { 639 pri = RQB_FFS(rqb->rqb_bits[i]) + (i << RQB_L2BPW); 640 CTR3(KTR_RUNQ, "runq_findbit: bits=%#x i=%d pri=%d", 641 rqb->rqb_bits[i], i, pri); 642 return (pri); 643 } 644 645 return (-1); 646} 647 648/* 649 * Set the status bit of the queue corresponding to priority level pri, 650 * indicating that it is non-empty. 651 */ 652static __inline void 653runq_setbit(struct runq *rq, int pri) 654{ 655 struct rqbits *rqb; 656 657 rqb = &rq->rq_status; 658 CTR4(KTR_RUNQ, "runq_setbit: bits=%#x %#x bit=%#x word=%d", 659 rqb->rqb_bits[RQB_WORD(pri)], 660 rqb->rqb_bits[RQB_WORD(pri)] | RQB_BIT(pri), 661 RQB_BIT(pri), RQB_WORD(pri)); 662 rqb->rqb_bits[RQB_WORD(pri)] |= RQB_BIT(pri); 663} 664 665/* 666 * Add the KSE to the queue specified by its priority, and set the 667 * corresponding status bit. 668 */ 669void 670runq_add(struct runq *rq, struct kse *ke) 671{ 672 struct rqhead *rqh; 673 int pri; 674 675 pri = ke->ke_thread->td_priority / RQ_PPQ; 676 ke->ke_rqindex = pri; 677 runq_setbit(rq, pri); 678 rqh = &rq->rq_queues[pri]; 679 CTR4(KTR_RUNQ, "runq_add: p=%p pri=%d %d rqh=%p", 680 ke->ke_proc, ke->ke_thread->td_priority, pri, rqh); 681 TAILQ_INSERT_TAIL(rqh, ke, ke_procq); 682} 683 684/* 685 * Return true if there are runnable processes of any priority on the run 686 * queue, false otherwise. Has no side effects, does not modify the run 687 * queue structure. 688 */ 689int 690runq_check(struct runq *rq) 691{ 692 struct rqbits *rqb; 693 int i; 694 695 rqb = &rq->rq_status; 696 for (i = 0; i < RQB_LEN; i++) 697 if (rqb->rqb_bits[i]) { 698 CTR2(KTR_RUNQ, "runq_check: bits=%#x i=%d", 699 rqb->rqb_bits[i], i); 700 return (1); 701 } 702 CTR0(KTR_RUNQ, "runq_check: empty"); 703 704 return (0); 705} 706 707/* 708 * Find the highest priority process on the run queue. 709 */ 710struct kse * 711runq_choose(struct runq *rq) 712{ 713 struct rqhead *rqh; 714 struct kse *ke; 715 int pri; 716 717 mtx_assert(&sched_lock, MA_OWNED); 718 while ((pri = runq_findbit(rq)) != -1) { 719 rqh = &rq->rq_queues[pri]; 720 ke = TAILQ_FIRST(rqh); 721 KASSERT(ke != NULL, ("runq_choose: no proc on busy queue")); 722 CTR3(KTR_RUNQ, 723 "runq_choose: pri=%d kse=%p rqh=%p", pri, ke, rqh); 724 return (ke); 725 } 726 CTR1(KTR_RUNQ, "runq_choose: idleproc pri=%d", pri); 727 728 return (NULL); 729} 730 731/* 732 * Remove the KSE from the queue specified by its priority, and clear the 733 * corresponding status bit if the queue becomes empty. 734 * Caller must set ke->ke_state afterwards. 735 */ 736void 737runq_remove(struct runq *rq, struct kse *ke) 738{ 739 struct rqhead *rqh; 740 int pri; 741 742 KASSERT(ke->ke_proc->p_sflag & PS_INMEM, 743 ("runq_remove: process swapped out")); 744 pri = ke->ke_rqindex; 745 rqh = &rq->rq_queues[pri]; 746 CTR4(KTR_RUNQ, "runq_remove: p=%p pri=%d %d rqh=%p", 747 ke, ke->ke_thread->td_priority, pri, rqh); 748 KASSERT(ke != NULL, ("runq_remove: no proc on busy queue")); 749 TAILQ_REMOVE(rqh, ke, ke_procq); 750 if (TAILQ_EMPTY(rqh)) { 751 CTR0(KTR_RUNQ, "runq_remove: empty"); 752 runq_clrbit(rq, pri); 753 } 754} 755 756#if 0 757void 758panc(char *string1, char *string2) 759{ 760 printf("%s", string1); 761 Debugger(string2); 762} 763 764void 765thread_sanity_check(struct thread *td, char *string) 766{ 767 struct proc *p; 768 struct ksegrp *kg; 769 struct kse *ke; 770 struct thread *td2 = NULL; 771 unsigned int prevpri; 772 int saw_lastassigned = 0; 773 int unassigned = 0; 774 int assigned = 0; 775 776 p = td->td_proc; 777 kg = td->td_ksegrp; 778 ke = td->td_kse; 779 780 781 if (ke) { 782 if (p != ke->ke_proc) { 783 panc(string, "wrong proc"); 784 } 785 if (ke->ke_thread != td) { 786 panc(string, "wrong thread"); 787 } 788 } 789 790 if ((p->p_flag & P_KSES) == 0) { 791 if (ke == NULL) { 792 panc(string, "non KSE thread lost kse"); 793 } 794 } else { 795 prevpri = 0; 796 saw_lastassigned = 0; 797 unassigned = 0; 798 assigned = 0; 799 TAILQ_FOREACH(td2, &kg->kg_runq, td_runq) { 800 if (td2->td_priority < prevpri) { 801 panc(string, "thread runqueue unosorted"); 802 } 803 if ((td2->td_state == TDS_RUNQ) && 804 td2->td_kse && 805 (td2->td_kse->ke_state != KES_ONRUNQ)) { 806 panc(string, "KSE wrong state"); 807 } 808 prevpri = td2->td_priority; 809 if (td2->td_kse) { 810 assigned++; 811 if (unassigned) { 812 panc(string, "unassigned before assigned"); 813 } 814 if (kg->kg_last_assigned == NULL) { 815 panc(string, "lastassigned corrupt"); 816 } 817 if (saw_lastassigned) { 818 panc(string, "last assigned not last"); 819 } 820 if (td2->td_kse->ke_thread != td2) { 821 panc(string, "mismatched kse/thread"); 822 } 823 } else { 824 unassigned++; 825 } 826 if (td2 == kg->kg_last_assigned) { 827 saw_lastassigned = 1; 828 if (td2->td_kse == NULL) { 829 panc(string, "last assigned not assigned"); 830 } 831 } 832 } 833 if (kg->kg_last_assigned && (saw_lastassigned == 0)) { 834 panc(string, "where on earth does lastassigned point?"); 835 } 836 FOREACH_THREAD_IN_GROUP(kg, td2) { 837 if (((td2->td_flags & TDF_UNBOUND) == 0) && 838 (TD_ON_RUNQ(td2))) { 839 assigned++; 840 if (td2->td_kse == NULL) { 841 panc(string, "BOUND thread with no KSE"); 842 } 843 } 844 } 845#if 0 846 if ((unassigned + assigned) != kg->kg_runnable) { 847 panc(string, "wrong number in runnable"); 848 } 849#endif 850 } 851 if (assigned == 12345) { 852 printf("%p %p %p %p %p %d, %d", 853 td, td2, ke, kg, p, assigned, saw_lastassigned); 854 } 855} 856#endif 857 858