kern_switch.c revision 100913
116359Sasami/* 216359Sasami * Copyright (c) 2001 Jake Burkholder <jake@FreeBSD.org> 316359Sasami * All rights reserved. 416359Sasami * 516359Sasami * Redistribution and use in source and binary forms, with or without 625571Skato * modification, are permitted provided that the following conditions 716359Sasami * are met: 816359Sasami * 1. Redistributions of source code must retain the above copyright 916359Sasami * notice, this list of conditions and the following disclaimer. 1016359Sasami * 2. Redistributions in binary form must reproduce the above copyright 1116359Sasami * notice, this list of conditions and the following disclaimer in the 1216359Sasami * documentation and/or other materials provided with the distribution. 1316359Sasami * 1416359Sasami * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 1516359Sasami * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 1616359Sasami * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 1716359Sasami * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 1816359Sasami * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 1916359Sasami * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 2016359Sasami * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 2125088Skato * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 2225571Skato * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 2325088Skato * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 2425088Skato * SUCH DAMAGE. 2516359Sasami * 2616359Sasami * $FreeBSD: head/sys/kern/kern_switch.c 100913 2002-07-30 06:54:05Z tanimura $ 2716359Sasami */ 2816359Sasami 2916359Sasami/*** 3016359Sasami 3116359SasamiHere is the logic.. 3216359Sasami 3316359SasamiIf there are N processors, then there are at most N KSEs (kernel 3418846Sasamischedulable entities) working to process threads that belong to a 3516359SasamiKSEGOUP (kg). If there are X of these KSEs actually running at the 3616359Sasamimoment in question, then there are at most M (N-X) of these KSEs on 3716359Sasamithe run queue, as running KSEs are not on the queue. 3816359Sasami 3916359SasamiRunnable threads are queued off the KSEGROUP in priority order. 4016359SasamiIf there are M or more threads runnable, the top M threads 4125256Skato(by priority) are 'preassigned' to the M KSEs not running. The KSEs take 4216359Sasamitheir priority from those threads and are put on the run queue. 4316359Sasami 4420494SkatoThe last thread that had a priority high enough to have a KSE associated 4520494Skatowith it, AND IS ON THE RUN QUEUE is pointed to by 4620494Skatokg->kg_last_assigned. If no threads queued off the KSEGROUP have KSEs 4720494Skatoassigned as all the available KSEs are activly running, or because there 4820494Skatoare no threads queued, that pointer is NULL. 4920494Skato 5020494SkatoWhen a KSE is removed from the run queue to become runnable, we know 5116359Sasamiit was associated with the highest priority thread in the queue (at the head 5216359Sasamiof the queue). If it is also the last assigned we know M was 1 and must 5316359Sasaminow be 0. Since the thread is no longer queued that pointer must be 5416359Sasamiremoved from it. Since we know there were no more KSEs available, 5516359Sasami(M was 1 and is now 0) and since we are not FREEING our KSE 5616359Sasamibut using it, we know there are STILL no more KSEs available, we can prove 5716359Sasamithat the next thread in the ksegrp list will not have a KSE to assign to 5816359Sasamiit, so we can show that the pointer must be made 'invalid' (NULL). 5916359Sasami 6016359SasamiThe pointer exists so that when a new thread is made runnable, it can 6125088Skatohave its priority compared with the last assigned thread to see if 6225088Skatoit should 'steal' its KSE or not.. i.e. is it 'earlier' 6324112Skatoon the list than that thread or later.. If it's earlier, then the KSE is 6425088Skatoremoved from the last assigned (which is now not assigned a KSE) 6525088Skatoand reassigned to the new thread, which is placed earlier in the list. 6616359SasamiThe pointer is then backed up to the previous thread (which may or may not 6716359Sasamibe the new thread). 6816359Sasami 6916359SasamiWhen a thread sleeps or is removed, the KSE becomes available and if there 7025088Skatoare queued threads that are not assigned KSEs, the highest priority one of 7125088Skatothem is assigned the KSE, which is then placed back on the run queue at 7225088Skatothe approipriate place, and the kg->kg_last_assigned pointer is adjusted down 7316359Sasamito point to it. 7416359Sasami 7516359SasamiThe following diagram shows 2 KSEs and 3 threads from a single process. 7625088Skato 7725571Skato RUNQ: --->KSE---KSE--... (KSEs queued at priorities from threads) 7825571Skato \ \____ 7925571Skato \ \ 8025571Skato KSEGROUP---thread--thread--thread (queued in priority order) 8125571Skato \ / 8225571Skato \_______________/ 8325088Skato (last_assigned) 8425088Skato 8525088SkatoThe result of this scheme is that the M available KSEs are always 8625088Skatoqueued at the priorities they have inherrited from the M highest priority 8716359Sasamithreads for that KSEGROUP. If this situation changes, the KSEs are 8816359Sasamireassigned to keep this true. 8916359Sasami 9016359Sasami*/ 9116359Sasami 9216359Sasami#include <sys/param.h> 9316359Sasami#include <sys/systm.h> 9416359Sasami#include <sys/kernel.h> 9516359Sasami#include <sys/ktr.h> 9616359Sasami#include <sys/lock.h> 9716359Sasami#include <sys/mutex.h> 9816359Sasami#include <sys/proc.h> 9916359Sasami#include <sys/queue.h> 10016359Sasami#include <machine/critical.h> 10116359Sasami 10216359SasamiCTASSERT((RQB_BPW * RQB_LEN) == RQ_NQS); 10316359Sasami 10416359Sasami/* 10516359Sasami * Global run queue. 10616359Sasami */ 10724112Skatostatic struct runq runq; 10816359SasamiSYSINIT(runq, SI_SUB_RUN_QUEUE, SI_ORDER_FIRST, runq_init, &runq) 10916359Sasami 11016359Sasamistatic void runq_readjust(struct runq *rq, struct kse *ke); 11116359Sasami/************************************************************************ 11216359Sasami * Functions that manipulate runnability from a thread perspective. * 11316359Sasami ************************************************************************/ 11416359Sasami 11516359Sasami/* 11616359Sasami * Select the KSE that will be run next. From that find the thread, and x 11716359Sasami * remove it from the KSEGRP's run queue. If there is thread clustering, 11816359Sasami * this will be what does it. 11924112Skato */ 12016359Sasamistruct thread * 12116359Sasamichoosethread(void) 12225088Skato{ 12325088Skato struct kse *ke; 12425088Skato struct thread *td; 12525088Skato struct ksegrp *kg; 12625088Skato 12725088Skatoretry: 12816359Sasami if ((ke = runq_choose(&runq))) { 12916359Sasami td = ke->ke_thread; 13016359Sasami KASSERT((td->td_kse == ke), ("kse/thread mismatch")); 13116359Sasami kg = ke->ke_ksegrp; 13216359Sasami if (td->td_flags & TDF_UNBOUND) { 13316359Sasami TAILQ_REMOVE(&kg->kg_runq, td, td_runq); 13416359Sasami if (kg->kg_last_assigned == td) 13516359Sasami if (TAILQ_PREV(td, threadqueue, td_runq) 13616359Sasami != NULL) 13716359Sasami printf("Yo MAMA!\n"); 13816359Sasami kg->kg_last_assigned = TAILQ_PREV(td, 13916359Sasami threadqueue, td_runq); 14016359Sasami /* 14116359Sasami * If we have started running an upcall, 14216359Sasami * Then TDF_UNBOUND WAS set because the thread was 14316359Sasami * created without a KSE. Now that we have one, 14416359Sasami * and it is our time to run, we make sure 14516359Sasami * that BOUND semantics apply for the rest of 14616359Sasami * the journey to userland, and into the UTS. 14716359Sasami */ 14816359Sasami#ifdef NOTYET 14916359Sasami if (td->td_flags & TDF_UPCALLING) 15025256Skato tdf->td_flags &= ~TDF_UNBOUND; 15116359Sasami#endif 15216359Sasami } 15316359Sasami kg->kg_runnable--; 15416359Sasami CTR2(KTR_RUNQ, "choosethread: td=%p pri=%d", 15519551Sasami td, td->td_priority); 15616359Sasami } else { 15725256Skato /* Simulate runq_choose() having returned the idle thread */ 15825256Skato td = PCPU_GET(idlethread); 15916359Sasami CTR1(KTR_RUNQ, "choosethread: td=%p (idle)", td); 16016359Sasami } 16116359Sasami if (panicstr && ((td->td_proc->p_flag & P_SYSTEM) == 0 && 16216359Sasami (td->td_flags & TDF_INPANIC) == 0)) 16316359Sasami goto retry; 16425088Skato td->td_state = TDS_RUNNING; 16516359Sasami return (td); 16616359Sasami} 16716359Sasami 16816359Sasami/* 16916359Sasami * Given a KSE (now surplus), either assign a new runable thread to it 17016359Sasami * (and put it in the run queue) or put it in the ksegrp's idle KSE list. 17116359Sasami * Assumes the kse is not linked to any threads any more. (has been cleaned). 17216359Sasami */ 17316359Sasamivoid 17416359Sasamikse_reassign(struct kse *ke) 17516359Sasami{ 17616359Sasami struct ksegrp *kg; 17716359Sasami struct thread *td; 17816359Sasami 17916359Sasami kg = ke->ke_ksegrp; 18016359Sasami 18116359Sasami /* 18216359Sasami * Find the first unassigned thread 18316359Sasami * If there is a 'last assigned' then see what's next. 18416359Sasami * otherwise look at what is first. 18516359Sasami */ 18616359Sasami if ((td = kg->kg_last_assigned)) { 18717947Sasami td = TAILQ_NEXT(td, td_runq); 18817947Sasami } else { 18916359Sasami td = TAILQ_FIRST(&kg->kg_runq); 19016359Sasami } 19116359Sasami 19216359Sasami /* 19316359Sasami * If we found one assign it the kse, otherwise idle the kse. 19418095Sasami */ 19516359Sasami if (td) { 19616359Sasami kg->kg_last_assigned = td; 19716359Sasami td->td_kse = ke; 19816359Sasami ke->ke_thread = td; 19916359Sasami runq_add(&runq, ke); 20016359Sasami CTR2(KTR_RUNQ, "kse_reassign: ke%p -> td%p", ke, td); 20116359Sasami } else { 20216359Sasami ke->ke_state = KES_IDLE; 20316359Sasami ke->ke_thread = NULL; 20416359Sasami TAILQ_INSERT_HEAD(&kg->kg_iq, ke, ke_kgrlist); 20516359Sasami kg->kg_idle_kses++; 20616359Sasami CTR1(KTR_RUNQ, "kse_reassign: ke%p idled", ke); 20716359Sasami } 20816359Sasami} 20916359Sasami 21016359Sasamiint 21116359Sasamikserunnable(void) 21216359Sasami{ 21319122Sasami return runq_check(&runq); 21419122Sasami} 21516359Sasami 21616359Sasami/* 21716359Sasami * Remove a thread from its KSEGRP's run queue. 218 * This in turn may remove it from a KSE if it was already assigned 219 * to one, possibly causing a new thread to be assigned to the KSE 220 * and the KSE getting a new priority (unless it's a BOUND thread/KSE pair). 221 */ 222void 223remrunqueue(struct thread *td) 224{ 225 struct thread *td2, *td3; 226 struct ksegrp *kg; 227 struct kse *ke; 228 229 mtx_assert(&sched_lock, MA_OWNED); 230 KASSERT ((td->td_state == TDS_RUNQ), 231 ("remrunqueue: Bad state on run queue")); 232 kg = td->td_ksegrp; 233 ke = td->td_kse; 234 /* 235 * If it's a bound thread/KSE pair, take the shortcut. All non-KSE 236 * threads are BOUND. 237 */ 238 CTR1(KTR_RUNQ, "remrunqueue: td%p", td); 239 td->td_state = TDS_UNQUEUED; 240 kg->kg_runnable--; 241 if ((td->td_flags & TDF_UNBOUND) == 0) { 242 /* Bring its kse with it, leave the thread attached */ 243 runq_remove(&runq, ke); 244 ke->ke_state = KES_THREAD; 245 return; 246 } 247 if (ke) { 248 /* 249 * This thread has been assigned to a KSE. 250 * We need to dissociate it and try assign the 251 * KSE to the next available thread. Then, we should 252 * see if we need to move the KSE in the run queues. 253 */ 254 td2 = kg->kg_last_assigned; 255 KASSERT((td2 != NULL), ("last assigned has wrong value ")); 256 td->td_kse = NULL; 257 if ((td3 = TAILQ_NEXT(td2, td_runq))) { 258 KASSERT(td3 != td, ("td3 somehow matched td")); 259 /* 260 * Give the next unassigned thread to the KSE 261 * so the number of runnable KSEs remains 262 * constant. 263 */ 264 td3->td_kse = ke; 265 ke->ke_thread = td3; 266 kg->kg_last_assigned = td3; 267 runq_readjust(&runq, ke); 268 } else { 269 /* 270 * There is no unassigned thread. 271 * If we were the last assigned one, 272 * adjust the last assigned pointer back 273 * one, which may result in NULL. 274 */ 275 if (td == td2) { 276 kg->kg_last_assigned = 277 TAILQ_PREV(td, threadqueue, td_runq); 278 } 279 runq_remove(&runq, ke); 280 KASSERT((ke->ke_state != KES_IDLE), 281 ("kse already idle")); 282 ke->ke_state = KES_IDLE; 283 ke->ke_thread = NULL; 284 TAILQ_INSERT_HEAD(&kg->kg_iq, ke, ke_kgrlist); 285 kg->kg_idle_kses++; 286 } 287 } 288 TAILQ_REMOVE(&kg->kg_runq, td, td_runq); 289} 290 291void 292setrunqueue(struct thread *td) 293{ 294 struct kse *ke; 295 struct ksegrp *kg; 296 struct thread *td2; 297 struct thread *tda; 298 299 CTR1(KTR_RUNQ, "setrunqueue: td%p", td); 300 mtx_assert(&sched_lock, MA_OWNED); 301 KASSERT((td->td_state != TDS_RUNQ), ("setrunqueue: bad thread state")); 302 td->td_state = TDS_RUNQ; 303 kg = td->td_ksegrp; 304 kg->kg_runnable++; 305 if ((td->td_flags & TDF_UNBOUND) == 0) { 306 KASSERT((td->td_kse != NULL), 307 ("queueing BAD thread to run queue")); 308 /* 309 * Common path optimisation: Only one of everything 310 * and the KSE is always already attached. 311 * Totally ignore the ksegrp run queue. 312 */ 313 runq_add(&runq, td->td_kse); 314 return; 315 } 316 /* 317 * Ok, so we are threading with this thread. 318 * We don't have a KSE, see if we can get one.. 319 */ 320 tda = kg->kg_last_assigned; 321 if ((ke = td->td_kse) == NULL) { 322 /* 323 * We will need a KSE, see if there is one.. 324 * First look for a free one, before getting desperate. 325 * If we can't get one, our priority is not high enough.. 326 * that's ok.. 327 */ 328 if (kg->kg_idle_kses) { 329 /* 330 * There is a free one so it's ours for the asking.. 331 */ 332 ke = TAILQ_FIRST(&kg->kg_iq); 333 TAILQ_REMOVE(&kg->kg_iq, ke, ke_kgrlist); 334 ke->ke_state = KES_THREAD; 335 kg->kg_idle_kses--; 336 } else if (tda && (tda->td_priority > td->td_priority)) { 337 /* 338 * None free, but there is one we can commandeer. 339 */ 340 ke = tda->td_kse; 341 tda->td_kse = NULL; 342 ke->ke_thread = NULL; 343 tda = kg->kg_last_assigned = 344 TAILQ_PREV(tda, threadqueue, td_runq); 345 runq_remove(&runq, ke); 346 } 347 } else { 348 /* 349 * Temporarily disassociate so it looks like the other cases. 350 */ 351 ke->ke_thread = NULL; 352 td->td_kse = NULL; 353 } 354 355 /* 356 * Add the thread to the ksegrp's run queue at 357 * the appropriate place. 358 */ 359 TAILQ_FOREACH(td2, &kg->kg_runq, td_runq) { 360 if (td2->td_priority > td->td_priority) { 361 TAILQ_INSERT_BEFORE(td2, td, td_runq); 362 break; 363 } 364 } 365 if (td2 == NULL) { 366 /* We ran off the end of the TAILQ or it was empty. */ 367 TAILQ_INSERT_TAIL(&kg->kg_runq, td, td_runq); 368 } 369 370 /* 371 * If we have a ke to use, then put it on the run queue and 372 * If needed, readjust the last_assigned pointer. 373 */ 374 if (ke) { 375 if (tda == NULL) { 376 /* 377 * No pre-existing last assigned so whoever is first 378 * gets the KSE we brought in.. (maybe us) 379 */ 380 td2 = TAILQ_FIRST(&kg->kg_runq); 381 KASSERT((td2->td_kse == NULL), 382 ("unexpected ke present")); 383 td2->td_kse = ke; 384 ke->ke_thread = td2; 385 kg->kg_last_assigned = td2; 386 } else if (tda->td_priority > td->td_priority) { 387 /* 388 * It's ours, grab it, but last_assigned is past us 389 * so don't change it. 390 */ 391 td->td_kse = ke; 392 ke->ke_thread = td; 393 } else { 394 /* 395 * We are past last_assigned, so 396 * put the new kse on whatever is next, 397 * which may or may not be us. 398 */ 399 td2 = TAILQ_NEXT(tda, td_runq); 400 kg->kg_last_assigned = td2; 401 td2->td_kse = ke; 402 ke->ke_thread = td2; 403 } 404 runq_add(&runq, ke); 405 } 406} 407 408/************************************************************************ 409 * Critical section marker functions * 410 ************************************************************************/ 411/* Critical sections that prevent preemption. */ 412void 413critical_enter(void) 414{ 415 struct thread *td; 416 417 td = curthread; 418 if (td->td_critnest == 0) 419 cpu_critical_enter(); 420 td->td_critnest++; 421} 422 423void 424critical_exit(void) 425{ 426 struct thread *td; 427 428 td = curthread; 429 if (td->td_critnest == 1) { 430 td->td_critnest = 0; 431 cpu_critical_exit(); 432 } else { 433 td->td_critnest--; 434 } 435} 436 437 438/************************************************************************ 439 * SYSTEM RUN QUEUE manipulations and tests * 440 ************************************************************************/ 441/* 442 * Initialize a run structure. 443 */ 444void 445runq_init(struct runq *rq) 446{ 447 int i; 448 449 bzero(rq, sizeof *rq); 450 for (i = 0; i < RQ_NQS; i++) 451 TAILQ_INIT(&rq->rq_queues[i]); 452} 453 454/* 455 * Clear the status bit of the queue corresponding to priority level pri, 456 * indicating that it is empty. 457 */ 458static __inline void 459runq_clrbit(struct runq *rq, int pri) 460{ 461 struct rqbits *rqb; 462 463 rqb = &rq->rq_status; 464 CTR4(KTR_RUNQ, "runq_clrbit: bits=%#x %#x bit=%#x word=%d", 465 rqb->rqb_bits[RQB_WORD(pri)], 466 rqb->rqb_bits[RQB_WORD(pri)] & ~RQB_BIT(pri), 467 RQB_BIT(pri), RQB_WORD(pri)); 468 rqb->rqb_bits[RQB_WORD(pri)] &= ~RQB_BIT(pri); 469} 470 471/* 472 * Find the index of the first non-empty run queue. This is done by 473 * scanning the status bits, a set bit indicates a non-empty queue. 474 */ 475static __inline int 476runq_findbit(struct runq *rq) 477{ 478 struct rqbits *rqb; 479 int pri; 480 int i; 481 482 rqb = &rq->rq_status; 483 for (i = 0; i < RQB_LEN; i++) 484 if (rqb->rqb_bits[i]) { 485 pri = RQB_FFS(rqb->rqb_bits[i]) + (i << RQB_L2BPW); 486 CTR3(KTR_RUNQ, "runq_findbit: bits=%#x i=%d pri=%d", 487 rqb->rqb_bits[i], i, pri); 488 return (pri); 489 } 490 491 return (-1); 492} 493 494/* 495 * Set the status bit of the queue corresponding to priority level pri, 496 * indicating that it is non-empty. 497 */ 498static __inline void 499runq_setbit(struct runq *rq, int pri) 500{ 501 struct rqbits *rqb; 502 503 rqb = &rq->rq_status; 504 CTR4(KTR_RUNQ, "runq_setbit: bits=%#x %#x bit=%#x word=%d", 505 rqb->rqb_bits[RQB_WORD(pri)], 506 rqb->rqb_bits[RQB_WORD(pri)] | RQB_BIT(pri), 507 RQB_BIT(pri), RQB_WORD(pri)); 508 rqb->rqb_bits[RQB_WORD(pri)] |= RQB_BIT(pri); 509} 510 511/* 512 * Add the KSE to the queue specified by its priority, and set the 513 * corresponding status bit. 514 */ 515void 516runq_add(struct runq *rq, struct kse *ke) 517{ 518 struct rqhead *rqh; 519 int pri; 520 521 mtx_assert(&sched_lock, MA_OWNED); 522 KASSERT((ke->ke_thread != NULL), ("runq_add: No thread on KSE")); 523 KASSERT((ke->ke_thread->td_kse != NULL), 524 ("runq_add: No KSE on thread")); 525 KASSERT(ke->ke_state != KES_ONRUNQ, 526 ("runq_add: kse %p (%s) already in run queue", ke, 527 ke->ke_proc->p_comm)); 528 KASSERT(ke->ke_proc->p_sflag & PS_INMEM, 529 ("runq_add: process swapped out")); 530 pri = ke->ke_thread->td_priority / RQ_PPQ; 531 ke->ke_rqindex = pri; 532 runq_setbit(rq, pri); 533 rqh = &rq->rq_queues[pri]; 534 CTR4(KTR_RUNQ, "runq_add: p=%p pri=%d %d rqh=%p", 535 ke->ke_proc, ke->ke_thread->td_priority, pri, rqh); 536 TAILQ_INSERT_TAIL(rqh, ke, ke_procq); 537 ke->ke_ksegrp->kg_runq_kses++; 538 ke->ke_state = KES_ONRUNQ; 539} 540 541/* 542 * Return true if there are runnable processes of any priority on the run 543 * queue, false otherwise. Has no side effects, does not modify the run 544 * queue structure. 545 */ 546int 547runq_check(struct runq *rq) 548{ 549 struct rqbits *rqb; 550 int i; 551 552 rqb = &rq->rq_status; 553 for (i = 0; i < RQB_LEN; i++) 554 if (rqb->rqb_bits[i]) { 555 CTR2(KTR_RUNQ, "runq_check: bits=%#x i=%d", 556 rqb->rqb_bits[i], i); 557 return (1); 558 } 559 CTR0(KTR_RUNQ, "runq_check: empty"); 560 561 return (0); 562} 563 564/* 565 * Find and remove the highest priority process from the run queue. 566 * If there are no runnable processes, the per-cpu idle process is 567 * returned. Will not return NULL under any circumstances. 568 */ 569struct kse * 570runq_choose(struct runq *rq) 571{ 572 struct rqhead *rqh; 573 struct kse *ke; 574 int pri; 575 576 mtx_assert(&sched_lock, MA_OWNED); 577 while ((pri = runq_findbit(rq)) != -1) { 578 rqh = &rq->rq_queues[pri]; 579 ke = TAILQ_FIRST(rqh); 580 KASSERT(ke != NULL, ("runq_choose: no proc on busy queue")); 581 CTR3(KTR_RUNQ, 582 "runq_choose: pri=%d kse=%p rqh=%p", pri, ke, rqh); 583 TAILQ_REMOVE(rqh, ke, ke_procq); 584 ke->ke_ksegrp->kg_runq_kses--; 585 if (TAILQ_EMPTY(rqh)) { 586 CTR0(KTR_RUNQ, "runq_choose: empty"); 587 runq_clrbit(rq, pri); 588 } 589 590 ke->ke_state = KES_THREAD; 591 KASSERT((ke->ke_thread != NULL), 592 ("runq_choose: No thread on KSE")); 593 KASSERT((ke->ke_thread->td_kse != NULL), 594 ("runq_choose: No KSE on thread")); 595 KASSERT(ke->ke_proc->p_sflag & PS_INMEM, 596 ("runq_choose: process swapped out")); 597 return (ke); 598 } 599 CTR1(KTR_RUNQ, "runq_choose: idleproc pri=%d", pri); 600 601 return (NULL); 602} 603 604/* 605 * Remove the KSE from the queue specified by its priority, and clear the 606 * corresponding status bit if the queue becomes empty. 607 * Caller must set ke->ke_state afterwards. 608 */ 609void 610runq_remove(struct runq *rq, struct kse *ke) 611{ 612 struct rqhead *rqh; 613 int pri; 614 615 KASSERT((ke->ke_state == KES_ONRUNQ), ("KSE not on run queue")); 616 mtx_assert(&sched_lock, MA_OWNED); 617 KASSERT(ke->ke_proc->p_sflag & PS_INMEM, 618 ("runq_remove: process swapped out")); 619 pri = ke->ke_rqindex; 620 rqh = &rq->rq_queues[pri]; 621 CTR4(KTR_RUNQ, "runq_remove: p=%p pri=%d %d rqh=%p", 622 ke, ke->ke_thread->td_priority, pri, rqh); 623 KASSERT(ke != NULL, ("runq_remove: no proc on busy queue")); 624 TAILQ_REMOVE(rqh, ke, ke_procq); 625 if (TAILQ_EMPTY(rqh)) { 626 CTR0(KTR_RUNQ, "runq_remove: empty"); 627 runq_clrbit(rq, pri); 628 } 629 ke->ke_state = KES_THREAD; 630 ke->ke_ksegrp->kg_runq_kses--; 631} 632 633static void 634runq_readjust(struct runq *rq, struct kse *ke) 635{ 636 637 if (ke->ke_rqindex != (ke->ke_thread->td_priority / RQ_PPQ)) { 638 runq_remove(rq, ke); 639 runq_add(rq, ke); 640 } 641} 642 643#if 0 644void 645thread_sanity_check(struct thread *td) 646{ 647 struct proc *p; 648 struct ksegrp *kg; 649 struct kse *ke; 650 struct thread *td2; 651 unsigned int prevpri; 652 int saw_lastassigned; 653 int unassigned; 654 int assigned; 655 656 p = td->td_proc; 657 kg = td->td_ksegrp; 658 ke = td->td_kse; 659 660 if (kg != &p->p_ksegrp) { 661 panic ("wrong ksegrp"); 662 } 663 664 if (ke) { 665 if (ke != &p->p_kse) { 666 panic("wrong kse"); 667 } 668 if (ke->ke_thread != td) { 669 panic("wrong thread"); 670 } 671 } 672 673 if ((p->p_flag & P_KSES) == 0) { 674 if (ke == NULL) { 675 panic("non KSE thread lost kse"); 676 } 677 } else { 678 prevpri = 0; 679 saw_lastassigned = 0; 680 unassigned = 0; 681 assigned = 0; 682 TAILQ_FOREACH(td2, &kg->kg_runq, td_runq) { 683 if (td2->td_priority < prevpri) { 684 panic("thread runqueue unosorted"); 685 } 686 prevpri = td2->td_priority; 687 if (td2->td_kse) { 688 assigned++; 689 if (unassigned) { 690 panic("unassigned before assigned"); 691 } 692 if (kg->kg_last_assigned == NULL) { 693 panic("lastassigned corrupt"); 694 } 695 if (saw_lastassigned) { 696 panic("last assigned not last"); 697 } 698 if (td2->td_kse->ke_thread != td2) { 699 panic("mismatched kse/thread"); 700 } 701 } else { 702 unassigned++; 703 } 704 if (td2 == kg->kg_last_assigned) { 705 saw_lastassigned = 1; 706 if (td2->td_kse == NULL) { 707 panic("last assigned not assigned"); 708 } 709 } 710 } 711 if (kg->kg_last_assigned && (saw_lastassigned == 0)) { 712 panic("where on earth does lastassigned point?"); 713 } 714 FOREACH_THREAD_IN_GROUP(kg, td2) { 715 if (((td2->td_flags & TDF_UNBOUND) == 0) && 716 (td2->td_state == TDS_RUNQ)) { 717 assigned++; 718 if (td2->td_kse == NULL) { 719 panic ("BOUND thread with no KSE"); 720 } 721 } 722 } 723#if 0 724 if ((unassigned + assigned) != kg->kg_runnable) { 725 panic("wrong number in runnable"); 726 } 727#endif 728 } 729} 730#endif 731 732