kern_switch.c revision 72376
150027Speter/* 250027Speter * Copyright (c) 1999 Peter Wemm <peter@FreeBSD.org> 350027Speter * All rights reserved. 472376Sjake * Copyright (c) 2001 Jake Burkholder <jake@FreeBSD.org> 572376Sjake * All rights reserved. 650027Speter * 750027Speter * Redistribution and use in source and binary forms, with or without 850027Speter * modification, are permitted provided that the following conditions 950027Speter * are met: 1050027Speter * 1. Redistributions of source code must retain the above copyright 1150027Speter * notice, this list of conditions and the following disclaimer. 1250027Speter * 2. Redistributions in binary form must reproduce the above copyright 1350027Speter * notice, this list of conditions and the following disclaimer in the 1450027Speter * documentation and/or other materials provided with the distribution. 1550027Speter * 1650027Speter * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 1750027Speter * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 1850027Speter * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 1950027Speter * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 2050027Speter * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 2150027Speter * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 2250027Speter * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 2350027Speter * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 2450027Speter * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 2550027Speter * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 2650027Speter * SUCH DAMAGE. 2750027Speter * 2850027Speter * $FreeBSD: head/sys/kern/kern_switch.c 72376 2001-02-12 00:20:08Z jake $ 2950027Speter */ 3050027Speter 3150027Speter#include <sys/param.h> 3250027Speter#include <sys/systm.h> 3350027Speter#include <sys/kernel.h> 3465557Sjasone#include <sys/ktr.h> 3567365Sjhb#include <sys/mutex.h> 3650027Speter#include <sys/proc.h> 3750027Speter#include <sys/queue.h> 3850027Speter 3950027Speter/* 4072376Sjake * Global run queue. 4150027Speter */ 4272376Sjakestatic struct runq runq; 4372376SjakeSYSINIT(runq, SI_SUB_RUN_QUEUE, SI_ORDER_FIRST, runq_init, &runq) 4450027Speter 4550027Speter/* 4672376Sjake * Wrappers which implement old interface; act on global run queue. 4750027Speter */ 4872376Sjake 4972376Sjakestruct proc * 5072376Sjakechooseproc(void) 5150027Speter{ 5272376Sjake return runq_choose(&runq); 5372376Sjake} 5450027Speter 5572376Sjakeint 5672376Sjakeprocrunnable(void) 5772376Sjake{ 5872376Sjake return runq_check(&runq); 5950027Speter} 6050027Speter 6150027Spetervoid 6272376Sjakeremrunqueue(struct proc *p) 6372376Sjake{ 6472376Sjake runq_remove(&runq, p); 6572376Sjake} 6672376Sjake 6772376Sjakevoid 6850027Spetersetrunqueue(struct proc *p) 6950027Speter{ 7072376Sjake runq_add(&runq, p); 7172376Sjake} 7250027Speter 7372376Sjake/* 7472376Sjake * Clear the status bit of the queue corresponding to priority level pri, 7572376Sjake * indicating that it is empty. 7672376Sjake */ 7772376Sjakestatic __inline void 7872376Sjakerunq_clrbit(struct runq *rq, int pri) 7972376Sjake{ 8072376Sjake struct rqbits *rqb; 8165557Sjasone 8272376Sjake rqb = &rq->rq_status; 8372376Sjake CTR4(KTR_RUNQ, "runq_clrbit: bits=%#x %#x bit=%#x word=%d", 8472376Sjake rqb->rqb_bits[RQB_WORD(pri)], 8572376Sjake rqb->rqb_bits[RQB_WORD(pri)] & ~RQB_BIT(pri), 8672376Sjake RQB_BIT(pri), RQB_WORD(pri)); 8772376Sjake rqb->rqb_bits[RQB_WORD(pri)] &= ~RQB_BIT(pri); 8850027Speter} 8950027Speter 9050027Speter/* 9172376Sjake * Find the index of the first non-empty run queue. This is done by 9272376Sjake * scanning the status bits, a set bit indicates a non-empty queue. 9350027Speter */ 9472376Sjakestatic __inline int 9572376Sjakerunq_findbit(struct runq *rq) 9672376Sjake{ 9772376Sjake struct rqbits *rqb; 9872376Sjake int pri; 9972376Sjake int i; 10072376Sjake 10172376Sjake rqb = &rq->rq_status; 10272376Sjake for (i = 0; i < RQB_LEN; i++) 10372376Sjake if (rqb->rqb_bits[i]) { 10472376Sjake pri = (RQB_FFS(rqb->rqb_bits[i]) - 1) + 10572376Sjake (i << RQB_L2BPW); 10672376Sjake CTR3(KTR_RUNQ, "runq_findbit: bits=%#x i=%d pri=%d", 10772376Sjake rqb->rqb_bits[i], i, pri); 10872376Sjake return (pri); 10972376Sjake } 11072376Sjake 11172376Sjake return (-1); 11272376Sjake} 11372376Sjake 11472376Sjake/* 11572376Sjake * Set the status bit of the queue corresponding to priority level pri, 11672376Sjake * indicating that it is non-empty. 11772376Sjake */ 11872376Sjakestatic __inline void 11972376Sjakerunq_setbit(struct runq *rq, int pri) 12072376Sjake{ 12172376Sjake struct rqbits *rqb; 12272376Sjake 12372376Sjake rqb = &rq->rq_status; 12472376Sjake CTR4(KTR_RUNQ, "runq_setbit: bits=%#x %#x bit=%#x word=%d", 12572376Sjake rqb->rqb_bits[RQB_WORD(pri)], 12672376Sjake rqb->rqb_bits[RQB_WORD(pri)] | RQB_BIT(pri), 12772376Sjake RQB_BIT(pri), RQB_WORD(pri)); 12872376Sjake rqb->rqb_bits[RQB_WORD(pri)] |= RQB_BIT(pri); 12972376Sjake} 13072376Sjake 13172376Sjake/* 13272376Sjake * Add the process to the queue specified by its priority, and set the 13372376Sjake * corresponding status bit. 13472376Sjake */ 13550027Spetervoid 13672376Sjakerunq_add(struct runq *rq, struct proc *p) 13750027Speter{ 13872376Sjake struct rqhead *rqh; 13972376Sjake int pri; 14050027Speter 14165557Sjasone mtx_assert(&sched_lock, MA_OWNED); 14272376Sjake KASSERT(p->p_stat == SRUN, ("runq_add: proc %p (%s) not SRUN", 14372376Sjake p, p->p_comm)); 14472376Sjake pri = p->p_pri.pri_level / RQ_PPQ; 14572376Sjake p->p_rqindex = pri; 14672376Sjake runq_setbit(rq, pri); 14772376Sjake rqh = &rq->rq_queues[pri]; 14872376Sjake CTR4(KTR_RUNQ, "runq_add: p=%p pri=%d %d rqh=%p", 14972376Sjake p, p->p_pri.pri_level, pri, rqh); 15072376Sjake TAILQ_INSERT_TAIL(rqh, p, p_procq); 15150027Speter} 15250027Speter 15350027Speter/* 15472376Sjake * Return true if there are runnable processes of any priority on the run 15572376Sjake * queue, false otherwise. Has no side effects, does not modify the run 15672376Sjake * queue structure. 15750027Speter */ 15872376Sjakeint 15972376Sjakerunq_check(struct runq *rq) 16050027Speter{ 16172376Sjake struct rqbits *rqb; 16272376Sjake int i; 16372376Sjake 16472376Sjake rqb = &rq->rq_status; 16572376Sjake for (i = 0; i < RQB_LEN; i++) 16672376Sjake if (rqb->rqb_bits[i]) { 16772376Sjake CTR2(KTR_RUNQ, "runq_check: bits=%#x i=%d", 16872376Sjake rqb->rqb_bits[i], i); 16972376Sjake return (1); 17072376Sjake } 17172376Sjake CTR0(KTR_RUNQ, "runq_check: empty"); 17272376Sjake 17372376Sjake return (0); 17450027Speter} 17550027Speter 17650027Speter/* 17772376Sjake * Find and remove the highest priority process from the run queue. 17872376Sjake * If there are no runnable processes, the per-cpu idle process is 17972376Sjake * returned. Will not return NULL under any circumstances. 18050027Speter */ 18150027Speterstruct proc * 18272376Sjakerunq_choose(struct runq *rq) 18350027Speter{ 18472376Sjake struct rqhead *rqh; 18550027Speter struct proc *p; 18672376Sjake int pri; 18750027Speter 18865557Sjasone mtx_assert(&sched_lock, MA_OWNED); 18972376Sjake if ((pri = runq_findbit(rq)) != -1) { 19072376Sjake rqh = &rq->rq_queues[pri]; 19172376Sjake p = TAILQ_FIRST(rqh); 19272376Sjake CTR3(KTR_RUNQ, "runq_choose: pri=%d p=%p rqh=%p", pri, p, rqh); 19372376Sjake TAILQ_REMOVE(rqh, p, p_procq); 19472376Sjake if (TAILQ_EMPTY(rqh)) { 19572376Sjake CTR0(KTR_RUNQ, "runq_choose: empty"); 19672376Sjake runq_clrbit(rq, pri); 19750027Speter } 19872376Sjake return (p); 19950027Speter } 20072376Sjake CTR1(KTR_RUNQ, "runq_choose: idleproc pri=%d", pri); 20172376Sjake 20272376Sjake return (PCPU_GET(idleproc)); 20350027Speter} 20472376Sjake 20572376Sjake/* 20672376Sjake * Initialize a run structure. 20772376Sjake */ 20872376Sjakevoid 20972376Sjakerunq_init(struct runq *rq) 21072376Sjake{ 21172376Sjake int i; 21272376Sjake 21372376Sjake for (i = 0; i < RQ_NQS; i++) 21472376Sjake TAILQ_INIT(&rq->rq_queues[i]); 21572376Sjake} 21672376Sjake 21772376Sjake/* 21872376Sjake * Remove the process from the queue specified by its priority, and clear the 21972376Sjake * corresponding status bit if the queue becomes empty. 22072376Sjake */ 22172376Sjakevoid 22272376Sjakerunq_remove(struct runq *rq, struct proc *p) 22372376Sjake{ 22472376Sjake struct rqhead *rqh; 22572376Sjake int pri; 22672376Sjake 22772376Sjake mtx_assert(&sched_lock, MA_OWNED); 22872376Sjake pri = p->p_rqindex; 22972376Sjake rqh = &rq->rq_queues[pri]; 23072376Sjake CTR4(KTR_RUNQ, "runq_remove: p=%p pri=%d %d rqh=%p", 23172376Sjake p, p->p_pri.pri_level, pri, rqh); 23272376Sjake KASSERT(p != NULL, ("runq_remove: no proc on busy queue")); 23372376Sjake TAILQ_REMOVE(rqh, p, p_procq); 23472376Sjake if (TAILQ_EMPTY(rqh)) { 23572376Sjake CTR0(KTR_RUNQ, "runq_remove: empty"); 23672376Sjake runq_clrbit(rq, pri); 23772376Sjake } 23872376Sjake} 239