kern_switch.c revision 88088
150027Speter/* 272376Sjake * Copyright (c) 2001 Jake Burkholder <jake@FreeBSD.org> 372376Sjake * All rights reserved. 450027Speter * 550027Speter * Redistribution and use in source and binary forms, with or without 650027Speter * modification, are permitted provided that the following conditions 750027Speter * are met: 850027Speter * 1. Redistributions of source code must retain the above copyright 950027Speter * notice, this list of conditions and the following disclaimer. 1050027Speter * 2. Redistributions in binary form must reproduce the above copyright 1150027Speter * notice, this list of conditions and the following disclaimer in the 1250027Speter * documentation and/or other materials provided with the distribution. 1350027Speter * 1450027Speter * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 1550027Speter * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 1650027Speter * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 1750027Speter * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 1850027Speter * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 1950027Speter * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 2050027Speter * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 2150027Speter * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 2250027Speter * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 2350027Speter * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 2450027Speter * SUCH DAMAGE. 2550027Speter * 2650027Speter * $FreeBSD: head/sys/kern/kern_switch.c 88088 2001-12-18 00:27:18Z jhb $ 2750027Speter */ 2850027Speter 2950027Speter#include <sys/param.h> 3050027Speter#include <sys/systm.h> 3150027Speter#include <sys/kernel.h> 3265557Sjasone#include <sys/ktr.h> 3374914Sjhb#include <sys/lock.h> 3467365Sjhb#include <sys/mutex.h> 3550027Speter#include <sys/proc.h> 3650027Speter#include <sys/queue.h> 3750027Speter 3850027Speter/* 3972376Sjake * Global run queue. 4050027Speter */ 4172376Sjakestatic struct runq runq; 4272376SjakeSYSINIT(runq, SI_SUB_RUN_QUEUE, SI_ORDER_FIRST, runq_init, &runq) 4350027Speter 4450027Speter/* 4572376Sjake * Wrappers which implement old interface; act on global run queue. 4650027Speter */ 4772376Sjake 4883366Sjulianstruct thread * 4983366Sjulianchoosethread(void) 5050027Speter{ 5183366Sjulian return (runq_choose(&runq)->ke_thread); 5272376Sjake} 5350027Speter 5472376Sjakeint 5572376Sjakeprocrunnable(void) 5672376Sjake{ 5772376Sjake return runq_check(&runq); 5850027Speter} 5950027Speter 6050027Spetervoid 6183366Sjulianremrunqueue(struct thread *td) 6272376Sjake{ 6383366Sjulian runq_remove(&runq, td->td_kse); 6472376Sjake} 6572376Sjake 6672376Sjakevoid 6783366Sjuliansetrunqueue(struct thread *td) 6850027Speter{ 6983366Sjulian runq_add(&runq, td->td_kse); 7072376Sjake} 7150027Speter 7288088Sjhb/* Critical sections that prevent preemption. */ 7388088Sjhbvoid 7488088Sjhbcritical_enter(void) 7588088Sjhb{ 7688088Sjhb struct thread *td; 7788088Sjhb 7888088Sjhb td = curthread; 7988088Sjhb if (td->td_critnest == 0) 8088088Sjhb td->td_savecrit = cpu_critical_enter(); 8188088Sjhb td->td_critnest++; 8288088Sjhb} 8388088Sjhb 8488088Sjhbvoid 8588088Sjhbcritical_exit(void) 8688088Sjhb{ 8788088Sjhb struct thread *td; 8888088Sjhb 8988088Sjhb td = curthread; 9088088Sjhb if (td->td_critnest == 1) { 9188088Sjhb td->td_critnest = 0; 9288088Sjhb cpu_critical_exit(td->td_savecrit); 9388088Sjhb } else 9488088Sjhb td->td_critnest--; 9588088Sjhb} 9688088Sjhb 9772376Sjake/* 9872376Sjake * Clear the status bit of the queue corresponding to priority level pri, 9972376Sjake * indicating that it is empty. 10072376Sjake */ 10172376Sjakestatic __inline void 10272376Sjakerunq_clrbit(struct runq *rq, int pri) 10372376Sjake{ 10472376Sjake struct rqbits *rqb; 10565557Sjasone 10672376Sjake rqb = &rq->rq_status; 10772376Sjake CTR4(KTR_RUNQ, "runq_clrbit: bits=%#x %#x bit=%#x word=%d", 10872376Sjake rqb->rqb_bits[RQB_WORD(pri)], 10972376Sjake rqb->rqb_bits[RQB_WORD(pri)] & ~RQB_BIT(pri), 11072376Sjake RQB_BIT(pri), RQB_WORD(pri)); 11172376Sjake rqb->rqb_bits[RQB_WORD(pri)] &= ~RQB_BIT(pri); 11250027Speter} 11350027Speter 11450027Speter/* 11572376Sjake * Find the index of the first non-empty run queue. This is done by 11672376Sjake * scanning the status bits, a set bit indicates a non-empty queue. 11750027Speter */ 11872376Sjakestatic __inline int 11972376Sjakerunq_findbit(struct runq *rq) 12072376Sjake{ 12172376Sjake struct rqbits *rqb; 12272376Sjake int pri; 12372376Sjake int i; 12472376Sjake 12572376Sjake rqb = &rq->rq_status; 12672376Sjake for (i = 0; i < RQB_LEN; i++) 12772376Sjake if (rqb->rqb_bits[i]) { 12872376Sjake pri = (RQB_FFS(rqb->rqb_bits[i]) - 1) + 12972376Sjake (i << RQB_L2BPW); 13072376Sjake CTR3(KTR_RUNQ, "runq_findbit: bits=%#x i=%d pri=%d", 13172376Sjake rqb->rqb_bits[i], i, pri); 13272376Sjake return (pri); 13372376Sjake } 13472376Sjake 13572376Sjake return (-1); 13672376Sjake} 13772376Sjake 13872376Sjake/* 13972376Sjake * Set the status bit of the queue corresponding to priority level pri, 14072376Sjake * indicating that it is non-empty. 14172376Sjake */ 14272376Sjakestatic __inline void 14372376Sjakerunq_setbit(struct runq *rq, int pri) 14472376Sjake{ 14572376Sjake struct rqbits *rqb; 14672376Sjake 14772376Sjake rqb = &rq->rq_status; 14872376Sjake CTR4(KTR_RUNQ, "runq_setbit: bits=%#x %#x bit=%#x word=%d", 14972376Sjake rqb->rqb_bits[RQB_WORD(pri)], 15072376Sjake rqb->rqb_bits[RQB_WORD(pri)] | RQB_BIT(pri), 15172376Sjake RQB_BIT(pri), RQB_WORD(pri)); 15272376Sjake rqb->rqb_bits[RQB_WORD(pri)] |= RQB_BIT(pri); 15372376Sjake} 15472376Sjake 15574113Sdes#ifdef INVARIANT_SUPPORT 15672376Sjake/* 15774113Sdes * Return true if the specified process is already in the run queue. 15874113Sdes */ 15974113Sdesstatic __inline int 16083366Sjulianrunq_find(struct runq *rq, struct kse *ke) 16174113Sdes{ 16283366Sjulian struct kse *ke2; 16374113Sdes int i; 16474113Sdes 16574113Sdes mtx_assert(&sched_lock, MA_OWNED); 16674113Sdes for (i = 0; i < RQB_LEN; i++) 16783366Sjulian TAILQ_FOREACH(ke2, &rq->rq_queues[i], ke_procq) 16883366Sjulian if (ke2 == ke) 16974113Sdes return 1; 17074113Sdes return 0; 17174113Sdes} 17274113Sdes#endif 17374113Sdes 17474113Sdes/* 17572376Sjake * Add the process to the queue specified by its priority, and set the 17672376Sjake * corresponding status bit. 17772376Sjake */ 17850027Spetervoid 17983366Sjulianrunq_add(struct runq *rq, struct kse *ke) 18050027Speter{ 18172376Sjake struct rqhead *rqh; 18272376Sjake int pri; 18350027Speter 18483366Sjulian struct ksegrp *kg = ke->ke_ksegrp; 18583366Sjulian#ifdef INVARIANTS 18683366Sjulian struct proc *p = ke->ke_proc; 18783366Sjulian#endif 18883366Sjulian if (ke->ke_flags & KEF_ONRUNQ) 18983366Sjulian return; 19065557Sjasone mtx_assert(&sched_lock, MA_OWNED); 19172376Sjake KASSERT(p->p_stat == SRUN, ("runq_add: proc %p (%s) not SRUN", 19272376Sjake p, p->p_comm)); 19383366Sjulian KASSERT(runq_find(rq, ke) == 0, 19483366Sjulian ("runq_add: proc %p (%s) already in run queue", ke, p->p_comm)); 19583366Sjulian pri = kg->kg_pri.pri_level / RQ_PPQ; 19683366Sjulian ke->ke_rqindex = pri; 19772376Sjake runq_setbit(rq, pri); 19872376Sjake rqh = &rq->rq_queues[pri]; 19972376Sjake CTR4(KTR_RUNQ, "runq_add: p=%p pri=%d %d rqh=%p", 20083601Sjlemon ke->ke_proc, kg->kg_pri.pri_level, pri, rqh); 20183366Sjulian TAILQ_INSERT_TAIL(rqh, ke, ke_procq); 20283366Sjulian ke->ke_flags |= KEF_ONRUNQ; 20350027Speter} 20450027Speter 20550027Speter/* 20672376Sjake * Return true if there are runnable processes of any priority on the run 20772376Sjake * queue, false otherwise. Has no side effects, does not modify the run 20872376Sjake * queue structure. 20950027Speter */ 21072376Sjakeint 21172376Sjakerunq_check(struct runq *rq) 21250027Speter{ 21372376Sjake struct rqbits *rqb; 21472376Sjake int i; 21572376Sjake 21672376Sjake rqb = &rq->rq_status; 21772376Sjake for (i = 0; i < RQB_LEN; i++) 21872376Sjake if (rqb->rqb_bits[i]) { 21972376Sjake CTR2(KTR_RUNQ, "runq_check: bits=%#x i=%d", 22072376Sjake rqb->rqb_bits[i], i); 22172376Sjake return (1); 22272376Sjake } 22372376Sjake CTR0(KTR_RUNQ, "runq_check: empty"); 22472376Sjake 22572376Sjake return (0); 22650027Speter} 22750027Speter 22850027Speter/* 22972376Sjake * Find and remove the highest priority process from the run queue. 23072376Sjake * If there are no runnable processes, the per-cpu idle process is 23172376Sjake * returned. Will not return NULL under any circumstances. 23250027Speter */ 23383366Sjulianstruct kse * 23472376Sjakerunq_choose(struct runq *rq) 23550027Speter{ 23672376Sjake struct rqhead *rqh; 23783366Sjulian struct kse *ke; 23872376Sjake int pri; 23950027Speter 24065557Sjasone mtx_assert(&sched_lock, MA_OWNED); 24172376Sjake if ((pri = runq_findbit(rq)) != -1) { 24272376Sjake rqh = &rq->rq_queues[pri]; 24383366Sjulian ke = TAILQ_FIRST(rqh); 24483366Sjulian KASSERT(ke != NULL, ("runq_choose: no proc on busy queue")); 24583366Sjulian KASSERT(ke->ke_proc->p_stat == SRUN, 24683366Sjulian ("runq_choose: process %d(%s) in state %d", ke->ke_proc->p_pid, 24783366Sjulian ke->ke_proc->p_comm, ke->ke_proc->p_stat)); 24883366Sjulian CTR3(KTR_RUNQ, "runq_choose: pri=%d kse=%p rqh=%p", pri, ke, rqh); 24983366Sjulian TAILQ_REMOVE(rqh, ke, ke_procq); 25072376Sjake if (TAILQ_EMPTY(rqh)) { 25172376Sjake CTR0(KTR_RUNQ, "runq_choose: empty"); 25272376Sjake runq_clrbit(rq, pri); 25350027Speter } 25483366Sjulian ke->ke_flags &= ~KEF_ONRUNQ; 25583366Sjulian return (ke); 25650027Speter } 25772376Sjake CTR1(KTR_RUNQ, "runq_choose: idleproc pri=%d", pri); 25872376Sjake 25983366Sjulian return (PCPU_GET(idlethread)->td_kse); 26050027Speter} 26172376Sjake 26272376Sjake/* 26372376Sjake * Initialize a run structure. 26472376Sjake */ 26572376Sjakevoid 26672376Sjakerunq_init(struct runq *rq) 26772376Sjake{ 26872376Sjake int i; 26972376Sjake 27072977Sjake bzero(rq, sizeof *rq); 27172376Sjake for (i = 0; i < RQ_NQS; i++) 27272376Sjake TAILQ_INIT(&rq->rq_queues[i]); 27372376Sjake} 27472376Sjake 27572376Sjake/* 27672376Sjake * Remove the process from the queue specified by its priority, and clear the 27772376Sjake * corresponding status bit if the queue becomes empty. 27872376Sjake */ 27972376Sjakevoid 28083366Sjulianrunq_remove(struct runq *rq, struct kse *ke) 28172376Sjake{ 28283366Sjulian#ifdef KTR 28383366Sjulian struct ksegrp *kg = ke->ke_ksegrp; 28483366Sjulian#endif 28572376Sjake struct rqhead *rqh; 28672376Sjake int pri; 28772376Sjake 28883366Sjulian if (!(ke->ke_flags & KEF_ONRUNQ)) 28983366Sjulian return; 29072376Sjake mtx_assert(&sched_lock, MA_OWNED); 29183366Sjulian pri = ke->ke_rqindex; 29272376Sjake rqh = &rq->rq_queues[pri]; 29372376Sjake CTR4(KTR_RUNQ, "runq_remove: p=%p pri=%d %d rqh=%p", 29483366Sjulian ke, kg->kg_pri.pri_level, pri, rqh); 29583366Sjulian KASSERT(ke != NULL, ("runq_remove: no proc on busy queue")); 29683366Sjulian TAILQ_REMOVE(rqh, ke, ke_procq); 29772376Sjake if (TAILQ_EMPTY(rqh)) { 29872376Sjake CTR0(KTR_RUNQ, "runq_remove: empty"); 29972376Sjake runq_clrbit(rq, pri); 30072376Sjake } 30183366Sjulian ke->ke_flags &= ~KEF_ONRUNQ; 30272376Sjake} 303