kern_switch.c revision 83366
11573Srgrimes/* 21573Srgrimes * Copyright (c) 2001 Jake Burkholder <jake@FreeBSD.org> 31573Srgrimes * All rights reserved. 41573Srgrimes * 51573Srgrimes * Redistribution and use in source and binary forms, with or without 61573Srgrimes * modification, are permitted provided that the following conditions 71573Srgrimes * are met: 81573Srgrimes * 1. Redistributions of source code must retain the above copyright 91573Srgrimes * notice, this list of conditions and the following disclaimer. 101573Srgrimes * 2. Redistributions in binary form must reproduce the above copyright 111573Srgrimes * notice, this list of conditions and the following disclaimer in the 121573Srgrimes * documentation and/or other materials provided with the distribution. 131573Srgrimes * 141573Srgrimes * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 151573Srgrimes * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 161573Srgrimes * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 171573Srgrimes * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 181573Srgrimes * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 191573Srgrimes * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 201573Srgrimes * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 211573Srgrimes * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 221573Srgrimes * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 231573Srgrimes * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 241573Srgrimes * SUCH DAMAGE. 251573Srgrimes * 261573Srgrimes * $FreeBSD: head/sys/kern/kern_switch.c 83366 2001-09-12 08:38:13Z julian $ 271573Srgrimes */ 281573Srgrimes 291573Srgrimes#include <sys/param.h> 301573Srgrimes#include <sys/systm.h> 311573Srgrimes#include <sys/kernel.h> 321573Srgrimes#include <sys/ktr.h> 331573Srgrimes#include <sys/lock.h> 341573Srgrimes#include <sys/mutex.h> 351573Srgrimes#include <sys/proc.h> 361573Srgrimes#include <sys/queue.h> 371573Srgrimes 381573Srgrimes/* 391573Srgrimes * Global run queue. 401573Srgrimes */ 411573Srgrimesstatic struct runq runq; 428870SrgrimesSYSINIT(runq, SI_SUB_RUN_QUEUE, SI_ORDER_FIRST, runq_init, &runq) 431573Srgrimes 441573Srgrimes/* 451573Srgrimes * Wrappers which implement old interface; act on global run queue. 461573Srgrimes */ 471573Srgrimes 481573Srgrimesstruct thread * 491573Srgrimeschoosethread(void) 501573Srgrimes{ 511573Srgrimes return (runq_choose(&runq)->ke_thread); 521573Srgrimes} 531573Srgrimes 541573Srgrimesint 551573Srgrimesprocrunnable(void) 561573Srgrimes{ 571573Srgrimes return runq_check(&runq); 581573Srgrimes} 591573Srgrimes 601573Srgrimesvoid 611573Srgrimesremrunqueue(struct thread *td) 621573Srgrimes{ 631573Srgrimes runq_remove(&runq, td->td_kse); 641573Srgrimes} 651573Srgrimes 661573Srgrimesvoid 671573Srgrimessetrunqueue(struct thread *td) 681573Srgrimes{ 691573Srgrimes runq_add(&runq, td->td_kse); 701573Srgrimes} 711573Srgrimes 721573Srgrimes/* 731573Srgrimes * Clear the status bit of the queue corresponding to priority level pri, 741573Srgrimes * indicating that it is empty. 751573Srgrimes */ 761573Srgrimesstatic __inline void 771573Srgrimesrunq_clrbit(struct runq *rq, int pri) 781573Srgrimes{ 791573Srgrimes struct rqbits *rqb; 801573Srgrimes 811573Srgrimes rqb = &rq->rq_status; 821573Srgrimes CTR4(KTR_RUNQ, "runq_clrbit: bits=%#x %#x bit=%#x word=%d", 831573Srgrimes rqb->rqb_bits[RQB_WORD(pri)], 841573Srgrimes rqb->rqb_bits[RQB_WORD(pri)] & ~RQB_BIT(pri), 851573Srgrimes RQB_BIT(pri), RQB_WORD(pri)); 861573Srgrimes rqb->rqb_bits[RQB_WORD(pri)] &= ~RQB_BIT(pri); 871573Srgrimes} 881573Srgrimes 891573Srgrimes/* 901573Srgrimes * Find the index of the first non-empty run queue. This is done by 911573Srgrimes * scanning the status bits, a set bit indicates a non-empty queue. 921573Srgrimes */ 931573Srgrimesstatic __inline int 941573Srgrimesrunq_findbit(struct runq *rq) 951573Srgrimes{ 961573Srgrimes struct rqbits *rqb; 971573Srgrimes int pri; 981573Srgrimes int i; 991573Srgrimes 1001573Srgrimes rqb = &rq->rq_status; 1011573Srgrimes for (i = 0; i < RQB_LEN; i++) 1021573Srgrimes if (rqb->rqb_bits[i]) { 1031573Srgrimes pri = (RQB_FFS(rqb->rqb_bits[i]) - 1) + 1041573Srgrimes (i << RQB_L2BPW); 1051573Srgrimes CTR3(KTR_RUNQ, "runq_findbit: bits=%#x i=%d pri=%d", 1061573Srgrimes rqb->rqb_bits[i], i, pri); 1071573Srgrimes return (pri); 1081573Srgrimes } 1091573Srgrimes 1101573Srgrimes return (-1); 1111573Srgrimes} 1121573Srgrimes 1131573Srgrimes/* 1141573Srgrimes * Set the status bit of the queue corresponding to priority level pri, 1151573Srgrimes * indicating that it is non-empty. 1161573Srgrimes */ 1171573Srgrimesstatic __inline void 1181573Srgrimesrunq_setbit(struct runq *rq, int pri) 1191573Srgrimes{ 1201573Srgrimes struct rqbits *rqb; 1211573Srgrimes 1221573Srgrimes rqb = &rq->rq_status; 1231573Srgrimes CTR4(KTR_RUNQ, "runq_setbit: bits=%#x %#x bit=%#x word=%d", 1241573Srgrimes rqb->rqb_bits[RQB_WORD(pri)], 1251573Srgrimes rqb->rqb_bits[RQB_WORD(pri)] | RQB_BIT(pri), 1261573Srgrimes RQB_BIT(pri), RQB_WORD(pri)); 1271573Srgrimes rqb->rqb_bits[RQB_WORD(pri)] |= RQB_BIT(pri); 1281573Srgrimes} 1291573Srgrimes 1301573Srgrimes#ifdef INVARIANT_SUPPORT 1311573Srgrimes/* 1321573Srgrimes * Return true if the specified process is already in the run queue. 1331573Srgrimes */ 1341573Srgrimesstatic __inline int 1351573Srgrimesrunq_find(struct runq *rq, struct kse *ke) 1361573Srgrimes{ 1371573Srgrimes struct kse *ke2; 1381573Srgrimes int i; 1391573Srgrimes 1401573Srgrimes mtx_assert(&sched_lock, MA_OWNED); 1411573Srgrimes for (i = 0; i < RQB_LEN; i++) 1421573Srgrimes TAILQ_FOREACH(ke2, &rq->rq_queues[i], ke_procq) 1431573Srgrimes if (ke2 == ke) 1441573Srgrimes return 1; 1451573Srgrimes return 0; 1461573Srgrimes} 1471573Srgrimes#endif 1481573Srgrimes 1491573Srgrimes/* 1501573Srgrimes * Add the process to the queue specified by its priority, and set the 1511573Srgrimes * corresponding status bit. 1521573Srgrimes */ 1531573Srgrimesvoid 1541573Srgrimesrunq_add(struct runq *rq, struct kse *ke) 1551573Srgrimes{ 1561573Srgrimes struct rqhead *rqh; 1571573Srgrimes int pri; 1581573Srgrimes 1591573Srgrimes struct ksegrp *kg = ke->ke_ksegrp; 1601573Srgrimes#ifdef INVARIANTS 1611573Srgrimes struct proc *p = ke->ke_proc; 1621573Srgrimes#endif 1631573Srgrimes if (ke->ke_flags & KEF_ONRUNQ) 1641573Srgrimes return; 1651573Srgrimes mtx_assert(&sched_lock, MA_OWNED); 1661573Srgrimes KASSERT(p->p_stat == SRUN, ("runq_add: proc %p (%s) not SRUN", 1671573Srgrimes p, p->p_comm)); 1681573Srgrimes KASSERT(runq_find(rq, ke) == 0, 1691573Srgrimes ("runq_add: proc %p (%s) already in run queue", ke, p->p_comm)); 1701573Srgrimes pri = kg->kg_pri.pri_level / RQ_PPQ; 1711573Srgrimes ke->ke_rqindex = pri; 1721573Srgrimes runq_setbit(rq, pri); 1731573Srgrimes rqh = &rq->rq_queues[pri]; 1741573Srgrimes CTR4(KTR_RUNQ, "runq_add: p=%p pri=%d %d rqh=%p", 1751573Srgrimes p, kg->kg_pri.pri_level, pri, rqh); 1761573Srgrimes TAILQ_INSERT_TAIL(rqh, ke, ke_procq); 1771573Srgrimes ke->ke_flags |= KEF_ONRUNQ; 1781573Srgrimes} 1791573Srgrimes 1801573Srgrimes/* 1811573Srgrimes * Return true if there are runnable processes of any priority on the run 1821573Srgrimes * queue, false otherwise. Has no side effects, does not modify the run 1831573Srgrimes * queue structure. 1841573Srgrimes */ 1851573Srgrimesint 1861573Srgrimesrunq_check(struct runq *rq) 1871573Srgrimes{ 1881573Srgrimes struct rqbits *rqb; 1891573Srgrimes int i; 1901573Srgrimes 1911573Srgrimes rqb = &rq->rq_status; 1921573Srgrimes for (i = 0; i < RQB_LEN; i++) 1931573Srgrimes if (rqb->rqb_bits[i]) { 1941573Srgrimes CTR2(KTR_RUNQ, "runq_check: bits=%#x i=%d", 1951573Srgrimes rqb->rqb_bits[i], i); 1961573Srgrimes return (1); 1971573Srgrimes } 1981573Srgrimes CTR0(KTR_RUNQ, "runq_check: empty"); 1991573Srgrimes 2001573Srgrimes return (0); 2011573Srgrimes} 2021573Srgrimes 2031573Srgrimes/* 2041573Srgrimes * Find and remove the highest priority process from the run queue. 2051573Srgrimes * If there are no runnable processes, the per-cpu idle process is 2061573Srgrimes * returned. Will not return NULL under any circumstances. 2071573Srgrimes */ 2081573Srgrimesstruct kse * 2091573Srgrimesrunq_choose(struct runq *rq) 2101573Srgrimes{ 2111573Srgrimes struct rqhead *rqh; 2121573Srgrimes struct kse *ke; 2131573Srgrimes int pri; 2141573Srgrimes 2151573Srgrimes mtx_assert(&sched_lock, MA_OWNED); 2161573Srgrimes if ((pri = runq_findbit(rq)) != -1) { 2171573Srgrimes rqh = &rq->rq_queues[pri]; 2181573Srgrimes ke = TAILQ_FIRST(rqh); 2191573Srgrimes KASSERT(ke != NULL, ("runq_choose: no proc on busy queue")); 2201573Srgrimes KASSERT(ke->ke_proc->p_stat == SRUN, 2211573Srgrimes ("runq_choose: process %d(%s) in state %d", ke->ke_proc->p_pid, 2221573Srgrimes ke->ke_proc->p_comm, ke->ke_proc->p_stat)); 2231573Srgrimes CTR3(KTR_RUNQ, "runq_choose: pri=%d kse=%p rqh=%p", pri, ke, rqh); 2241573Srgrimes TAILQ_REMOVE(rqh, ke, ke_procq); 2251573Srgrimes if (TAILQ_EMPTY(rqh)) { 2261573Srgrimes CTR0(KTR_RUNQ, "runq_choose: empty"); 2271573Srgrimes runq_clrbit(rq, pri); 2281573Srgrimes } 2291573Srgrimes ke->ke_flags &= ~KEF_ONRUNQ; 2301573Srgrimes return (ke); 2311573Srgrimes } 2321573Srgrimes CTR1(KTR_RUNQ, "runq_choose: idleproc pri=%d", pri); 2331573Srgrimes 2341573Srgrimes return (PCPU_GET(idlethread)->td_kse); 2351573Srgrimes} 2361573Srgrimes 2371573Srgrimes/* 2381573Srgrimes * Initialize a run structure. 2391573Srgrimes */ 2401573Srgrimesvoid 2411573Srgrimesrunq_init(struct runq *rq) 2421573Srgrimes{ 2431573Srgrimes int i; 2441573Srgrimes 2451573Srgrimes bzero(rq, sizeof *rq); 2461573Srgrimes for (i = 0; i < RQ_NQS; i++) 2471573Srgrimes TAILQ_INIT(&rq->rq_queues[i]); 2481573Srgrimes} 2491573Srgrimes 2501573Srgrimes/* 2511573Srgrimes * Remove the process from the queue specified by its priority, and clear the 2521573Srgrimes * corresponding status bit if the queue becomes empty. 2531573Srgrimes */ 2541573Srgrimesvoid 2551573Srgrimesrunq_remove(struct runq *rq, struct kse *ke) 2561573Srgrimes{ 2571573Srgrimes#ifdef KTR 2581573Srgrimes struct ksegrp *kg = ke->ke_ksegrp; 2591573Srgrimes#endif 2601573Srgrimes struct rqhead *rqh; 2611573Srgrimes int pri; 2621573Srgrimes 2631573Srgrimes if (!(ke->ke_flags & KEF_ONRUNQ)) 2641573Srgrimes return; 2651573Srgrimes mtx_assert(&sched_lock, MA_OWNED); 2661573Srgrimes pri = ke->ke_rqindex; 2671573Srgrimes rqh = &rq->rq_queues[pri]; 2681573Srgrimes CTR4(KTR_RUNQ, "runq_remove: p=%p pri=%d %d rqh=%p", 2691573Srgrimes ke, kg->kg_pri.pri_level, pri, rqh); 2701573Srgrimes KASSERT(ke != NULL, ("runq_remove: no proc on busy queue")); 2711573Srgrimes TAILQ_REMOVE(rqh, ke, ke_procq); 2721573Srgrimes if (TAILQ_EMPTY(rqh)) { 2731573Srgrimes CTR0(KTR_RUNQ, "runq_remove: empty"); 2741573Srgrimes runq_clrbit(rq, pri); 2751573Srgrimes } 2761573Srgrimes ke->ke_flags &= ~KEF_ONRUNQ; 2771573Srgrimes} 2781573Srgrimes