kern_switch.c revision 72376
1194676Sthompsa/* 2194676Sthompsa * Copyright (c) 1999 Peter Wemm <peter@FreeBSD.org> 3194676Sthompsa * All rights reserved. 4194676Sthompsa * Copyright (c) 2001 Jake Burkholder <jake@FreeBSD.org> 5194676Sthompsa * All rights reserved. 6194676Sthompsa * 7194676Sthompsa * Redistribution and use in source and binary forms, with or without 8194676Sthompsa * modification, are permitted provided that the following conditions 9194676Sthompsa * are met: 10194676Sthompsa * 1. Redistributions of source code must retain the above copyright 11194676Sthompsa * notice, this list of conditions and the following disclaimer. 12194676Sthompsa * 2. Redistributions in binary form must reproduce the above copyright 13194676Sthompsa * notice, this list of conditions and the following disclaimer in the 14194676Sthompsa * documentation and/or other materials provided with the distribution. 15194676Sthompsa * 16194676Sthompsa * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 17194676Sthompsa * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 18194676Sthompsa * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 19194676Sthompsa * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 20194676Sthompsa * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 21194676Sthompsa * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 22194676Sthompsa * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 23194676Sthompsa * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 24194676Sthompsa * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 25194676Sthompsa * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 26194676Sthompsa * SUCH DAMAGE. 27194676Sthompsa * 28194676Sthompsa * $FreeBSD: head/sys/kern/kern_switch.c 72376 2001-02-12 00:20:08Z jake $ 29194676Sthompsa */ 30195560Sthompsa 31195560Sthompsa#include <sys/param.h> 32195560Sthompsa#include <sys/systm.h> 33195560Sthompsa#include <sys/kernel.h> 34195560Sthompsa#include <sys/ktr.h> 35194676Sthompsa#include <sys/mutex.h> 36194676Sthompsa#include <sys/proc.h> 37194676Sthompsa#include <sys/queue.h> 38194676Sthompsa 39194676Sthompsa/* 40194676Sthompsa * Global run queue. 41194676Sthompsa */ 42194676Sthompsastatic struct runq runq; 43194676SthompsaSYSINIT(runq, SI_SUB_RUN_QUEUE, SI_ORDER_FIRST, runq_init, &runq) 44194676Sthompsa 45194676Sthompsa/* 46194676Sthompsa * Wrappers which implement old interface; act on global run queue. 47194676Sthompsa */ 48194676Sthompsa 49194676Sthompsastruct proc * 50194676Sthompsachooseproc(void) 51194676Sthompsa{ 52194676Sthompsa return runq_choose(&runq); 53194676Sthompsa} 54194676Sthompsa 55194676Sthompsaint 56194676Sthompsaprocrunnable(void) 57194676Sthompsa{ 58194676Sthompsa return runq_check(&runq); 59194676Sthompsa} 60194676Sthompsa 61194676Sthompsavoid 62194676Sthompsaremrunqueue(struct proc *p) 63194676Sthompsa{ 64194676Sthompsa runq_remove(&runq, p); 65194676Sthompsa} 66194676Sthompsa 67194676Sthompsavoid 68194676Sthompsasetrunqueue(struct proc *p) 69194676Sthompsa{ 70194676Sthompsa runq_add(&runq, p); 71194676Sthompsa} 72194676Sthompsa 73194676Sthompsa/* 74194676Sthompsa * Clear the status bit of the queue corresponding to priority level pri, 75194676Sthompsa * indicating that it is empty. 76194676Sthompsa */ 77194676Sthompsastatic __inline void 78194676Sthompsarunq_clrbit(struct runq *rq, int pri) 79194676Sthompsa{ 80194676Sthompsa struct rqbits *rqb; 81194676Sthompsa 82194676Sthompsa rqb = &rq->rq_status; 83194676Sthompsa CTR4(KTR_RUNQ, "runq_clrbit: bits=%#x %#x bit=%#x word=%d", 84194676Sthompsa rqb->rqb_bits[RQB_WORD(pri)], 85194676Sthompsa rqb->rqb_bits[RQB_WORD(pri)] & ~RQB_BIT(pri), 86194676Sthompsa RQB_BIT(pri), RQB_WORD(pri)); 87194676Sthompsa rqb->rqb_bits[RQB_WORD(pri)] &= ~RQB_BIT(pri); 88194676Sthompsa} 89194676Sthompsa 90194676Sthompsa/* 91194676Sthompsa * Find the index of the first non-empty run queue. This is done by 92194676Sthompsa * scanning the status bits, a set bit indicates a non-empty queue. 93194676Sthompsa */ 94194676Sthompsastatic __inline int 95194676Sthompsarunq_findbit(struct runq *rq) 96194676Sthompsa{ 97194676Sthompsa struct rqbits *rqb; 98194676Sthompsa int pri; 99194676Sthompsa int i; 100194676Sthompsa 101194676Sthompsa rqb = &rq->rq_status; 102194676Sthompsa for (i = 0; i < RQB_LEN; i++) 103194676Sthompsa if (rqb->rqb_bits[i]) { 104194676Sthompsa pri = (RQB_FFS(rqb->rqb_bits[i]) - 1) + 105194676Sthompsa (i << RQB_L2BPW); 106194676Sthompsa CTR3(KTR_RUNQ, "runq_findbit: bits=%#x i=%d pri=%d", 107194676Sthompsa rqb->rqb_bits[i], i, pri); 108194676Sthompsa return (pri); 109194676Sthompsa } 110194676Sthompsa 111194676Sthompsa return (-1); 112194676Sthompsa} 113194676Sthompsa 114194676Sthompsa/* 115194676Sthompsa * Set the status bit of the queue corresponding to priority level pri, 116194676Sthompsa * indicating that it is non-empty. 117194676Sthompsa */ 118194676Sthompsastatic __inline void 119194676Sthompsarunq_setbit(struct runq *rq, int pri) 120194676Sthompsa{ 121194676Sthompsa struct rqbits *rqb; 122194676Sthompsa 123194676Sthompsa rqb = &rq->rq_status; 124194676Sthompsa CTR4(KTR_RUNQ, "runq_setbit: bits=%#x %#x bit=%#x word=%d", 125194676Sthompsa rqb->rqb_bits[RQB_WORD(pri)], 126194676Sthompsa rqb->rqb_bits[RQB_WORD(pri)] | RQB_BIT(pri), 127194676Sthompsa RQB_BIT(pri), RQB_WORD(pri)); 128194676Sthompsa rqb->rqb_bits[RQB_WORD(pri)] |= RQB_BIT(pri); 129194676Sthompsa} 130194676Sthompsa 131194676Sthompsa/* 132194676Sthompsa * Add the process to the queue specified by its priority, and set the 133194676Sthompsa * corresponding status bit. 134194676Sthompsa */ 135194676Sthompsavoid 136194676Sthompsarunq_add(struct runq *rq, struct proc *p) 137194676Sthompsa{ 138194676Sthompsa struct rqhead *rqh; 139194676Sthompsa int pri; 140194676Sthompsa 141194676Sthompsa mtx_assert(&sched_lock, MA_OWNED); 142194676Sthompsa KASSERT(p->p_stat == SRUN, ("runq_add: proc %p (%s) not SRUN", 143194676Sthompsa p, p->p_comm)); 144194676Sthompsa pri = p->p_pri.pri_level / RQ_PPQ; 145194676Sthompsa p->p_rqindex = pri; 146194676Sthompsa runq_setbit(rq, pri); 147194676Sthompsa rqh = &rq->rq_queues[pri]; 148194676Sthompsa CTR4(KTR_RUNQ, "runq_add: p=%p pri=%d %d rqh=%p", 149194676Sthompsa p, p->p_pri.pri_level, pri, rqh); 150194676Sthompsa TAILQ_INSERT_TAIL(rqh, p, p_procq); 151194676Sthompsa} 152194676Sthompsa 153194676Sthompsa/* 154194676Sthompsa * Return true if there are runnable processes of any priority on the run 155194676Sthompsa * queue, false otherwise. Has no side effects, does not modify the run 156194676Sthompsa * queue structure. 157194676Sthompsa */ 158194676Sthompsaint 159194676Sthompsarunq_check(struct runq *rq) 160194676Sthompsa{ 161194676Sthompsa struct rqbits *rqb; 162194676Sthompsa int i; 163194676Sthompsa 164194676Sthompsa rqb = &rq->rq_status; 165194676Sthompsa for (i = 0; i < RQB_LEN; i++) 166194676Sthompsa if (rqb->rqb_bits[i]) { 167194676Sthompsa CTR2(KTR_RUNQ, "runq_check: bits=%#x i=%d", 168194676Sthompsa rqb->rqb_bits[i], i); 169194676Sthompsa return (1); 170194676Sthompsa } 171194676Sthompsa CTR0(KTR_RUNQ, "runq_check: empty"); 172194676Sthompsa 173194676Sthompsa return (0); 174194676Sthompsa} 175194676Sthompsa 176194676Sthompsa/* 177194676Sthompsa * Find and remove the highest priority process from the run queue. 178194676Sthompsa * If there are no runnable processes, the per-cpu idle process is 179194676Sthompsa * returned. Will not return NULL under any circumstances. 180194676Sthompsa */ 181194676Sthompsastruct proc * 182194676Sthompsarunq_choose(struct runq *rq) 183194676Sthompsa{ 184195560Sthompsa struct rqhead *rqh; 185195560Sthompsa struct proc *p; 186195560Sthompsa int pri; 187195560Sthompsa 188195560Sthompsa mtx_assert(&sched_lock, MA_OWNED); 189195560Sthompsa if ((pri = runq_findbit(rq)) != -1) { 190195560Sthompsa rqh = &rq->rq_queues[pri]; 191195560Sthompsa p = TAILQ_FIRST(rqh); 192195560Sthompsa CTR3(KTR_RUNQ, "runq_choose: pri=%d p=%p rqh=%p", pri, p, rqh); 193195560Sthompsa TAILQ_REMOVE(rqh, p, p_procq); 194195560Sthompsa if (TAILQ_EMPTY(rqh)) { 195195560Sthompsa CTR0(KTR_RUNQ, "runq_choose: empty"); 196195560Sthompsa runq_clrbit(rq, pri); 197195560Sthompsa } 198195560Sthompsa return (p); 199195560Sthompsa } 200195560Sthompsa CTR1(KTR_RUNQ, "runq_choose: idleproc pri=%d", pri); 201195560Sthompsa 202195560Sthompsa return (PCPU_GET(idleproc)); 203195560Sthompsa} 204195560Sthompsa 205195560Sthompsa/* 206195560Sthompsa * Initialize a run structure. 207195560Sthompsa */ 208195560Sthompsavoid 209195560Sthompsarunq_init(struct runq *rq) 210195560Sthompsa{ 211194676Sthompsa int i; 212194676Sthompsa 213194676Sthompsa for (i = 0; i < RQ_NQS; i++) 214194676Sthompsa TAILQ_INIT(&rq->rq_queues[i]); 215194676Sthompsa} 216194676Sthompsa 217194676Sthompsa/* 218194676Sthompsa * Remove the process from the queue specified by its priority, and clear the 219194676Sthompsa * corresponding status bit if the queue becomes empty. 220194676Sthompsa */ 221194676Sthompsavoid 222195560Sthompsarunq_remove(struct runq *rq, struct proc *p) 223194676Sthompsa{ 224194676Sthompsa struct rqhead *rqh; 225195560Sthompsa int pri; 226194676Sthompsa 227194676Sthompsa mtx_assert(&sched_lock, MA_OWNED); 228195560Sthompsa pri = p->p_rqindex; 229194676Sthompsa rqh = &rq->rq_queues[pri]; 230194676Sthompsa CTR4(KTR_RUNQ, "runq_remove: p=%p pri=%d %d rqh=%p", 231195560Sthompsa p, p->p_pri.pri_level, pri, rqh); 232194676Sthompsa KASSERT(p != NULL, ("runq_remove: no proc on busy queue")); 233194676Sthompsa TAILQ_REMOVE(rqh, p, p_procq); 234194676Sthompsa if (TAILQ_EMPTY(rqh)) { 235194676Sthompsa CTR0(KTR_RUNQ, "runq_remove: empty"); 236194676Sthompsa runq_clrbit(rq, pri); 237194676Sthompsa } 238194676Sthompsa} 239194676Sthompsa