Home | History | Annotate | Line # | Download | only in kern
kern_synch.c revision 1.148.2.1
      1  1.148.2.1       riz /*	$NetBSD: kern_synch.c,v 1.148.2.1 2005/10/21 17:39:40 riz Exp $	*/
      2       1.63   thorpej 
      3       1.63   thorpej /*-
      4      1.148   mycroft  * Copyright (c) 1999, 2000, 2004 The NetBSD Foundation, Inc.
      5       1.63   thorpej  * All rights reserved.
      6       1.63   thorpej  *
      7       1.63   thorpej  * This code is derived from software contributed to The NetBSD Foundation
      8       1.63   thorpej  * by Jason R. Thorpe of the Numerical Aerospace Simulation Facility,
      9       1.63   thorpej  * NASA Ames Research Center.
     10      1.148   mycroft  * This code is derived from software contributed to The NetBSD Foundation
     11      1.148   mycroft  * by Charles M. Hannum.
     12       1.63   thorpej  *
     13       1.63   thorpej  * Redistribution and use in source and binary forms, with or without
     14       1.63   thorpej  * modification, are permitted provided that the following conditions
     15       1.63   thorpej  * are met:
     16       1.63   thorpej  * 1. Redistributions of source code must retain the above copyright
     17       1.63   thorpej  *    notice, this list of conditions and the following disclaimer.
     18       1.63   thorpej  * 2. Redistributions in binary form must reproduce the above copyright
     19       1.63   thorpej  *    notice, this list of conditions and the following disclaimer in the
     20       1.63   thorpej  *    documentation and/or other materials provided with the distribution.
     21       1.63   thorpej  * 3. All advertising materials mentioning features or use of this software
     22       1.63   thorpej  *    must display the following acknowledgement:
     23       1.63   thorpej  *	This product includes software developed by the NetBSD
     24       1.63   thorpej  *	Foundation, Inc. and its contributors.
     25       1.63   thorpej  * 4. Neither the name of The NetBSD Foundation nor the names of its
     26       1.63   thorpej  *    contributors may be used to endorse or promote products derived
     27       1.63   thorpej  *    from this software without specific prior written permission.
     28       1.63   thorpej  *
     29       1.63   thorpej  * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
     30       1.63   thorpej  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
     31       1.63   thorpej  * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
     32       1.63   thorpej  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
     33       1.63   thorpej  * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
     34       1.63   thorpej  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
     35       1.63   thorpej  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
     36       1.63   thorpej  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
     37       1.63   thorpej  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
     38       1.63   thorpej  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
     39       1.63   thorpej  * POSSIBILITY OF SUCH DAMAGE.
     40       1.63   thorpej  */
     41       1.26       cgd 
     42       1.26       cgd /*-
     43       1.26       cgd  * Copyright (c) 1982, 1986, 1990, 1991, 1993
     44       1.26       cgd  *	The Regents of the University of California.  All rights reserved.
     45       1.26       cgd  * (c) UNIX System Laboratories, Inc.
     46       1.26       cgd  * All or some portions of this file are derived from material licensed
     47       1.26       cgd  * to the University of California by American Telephone and Telegraph
     48       1.26       cgd  * Co. or Unix System Laboratories, Inc. and are reproduced herein with
     49       1.26       cgd  * the permission of UNIX System Laboratories, Inc.
     50       1.26       cgd  *
     51       1.26       cgd  * Redistribution and use in source and binary forms, with or without
     52       1.26       cgd  * modification, are permitted provided that the following conditions
     53       1.26       cgd  * are met:
     54       1.26       cgd  * 1. Redistributions of source code must retain the above copyright
     55       1.26       cgd  *    notice, this list of conditions and the following disclaimer.
     56       1.26       cgd  * 2. Redistributions in binary form must reproduce the above copyright
     57       1.26       cgd  *    notice, this list of conditions and the following disclaimer in the
     58       1.26       cgd  *    documentation and/or other materials provided with the distribution.
     59      1.136       agc  * 3. Neither the name of the University nor the names of its contributors
     60       1.26       cgd  *    may be used to endorse or promote products derived from this software
     61       1.26       cgd  *    without specific prior written permission.
     62       1.26       cgd  *
     63       1.26       cgd  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
     64       1.26       cgd  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
     65       1.26       cgd  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
     66       1.26       cgd  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
     67       1.26       cgd  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
     68       1.26       cgd  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
     69       1.26       cgd  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
     70       1.26       cgd  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
     71       1.26       cgd  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
     72       1.26       cgd  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
     73       1.26       cgd  * SUCH DAMAGE.
     74       1.26       cgd  *
     75       1.50      fvdl  *	@(#)kern_synch.c	8.9 (Berkeley) 5/19/95
     76       1.26       cgd  */
     77      1.106     lukem 
     78      1.106     lukem #include <sys/cdefs.h>
     79  1.148.2.1       riz __KERNEL_RCSID(0, "$NetBSD: kern_synch.c,v 1.148.2.1 2005/10/21 17:39:40 riz Exp $");
     80       1.48       mrg 
     81       1.52  jonathan #include "opt_ddb.h"
     82       1.51   thorpej #include "opt_ktrace.h"
     83      1.109      yamt #include "opt_kstack.h"
     84       1.82   thorpej #include "opt_lockdebug.h"
     85       1.83   thorpej #include "opt_multiprocessor.h"
     86      1.110    briggs #include "opt_perfctrs.h"
     87       1.26       cgd 
     88       1.26       cgd #include <sys/param.h>
     89       1.26       cgd #include <sys/systm.h>
     90       1.68   thorpej #include <sys/callout.h>
     91       1.26       cgd #include <sys/proc.h>
     92       1.26       cgd #include <sys/kernel.h>
     93       1.26       cgd #include <sys/buf.h>
     94      1.111    briggs #if defined(PERFCTRS)
     95      1.110    briggs #include <sys/pmc.h>
     96      1.111    briggs #endif
     97       1.26       cgd #include <sys/signalvar.h>
     98       1.26       cgd #include <sys/resourcevar.h>
     99       1.55      ross #include <sys/sched.h>
    100      1.122   thorpej #include <sys/sa.h>
    101      1.122   thorpej #include <sys/savar.h>
    102       1.47       mrg 
    103       1.47       mrg #include <uvm/uvm_extern.h>
    104       1.47       mrg 
    105       1.26       cgd #ifdef KTRACE
    106       1.26       cgd #include <sys/ktrace.h>
    107       1.26       cgd #endif
    108       1.26       cgd 
    109       1.26       cgd #include <machine/cpu.h>
    110       1.34  christos 
    111       1.26       cgd int	lbolt;			/* once a second sleep address */
    112       1.88  sommerfe int	rrticks;		/* number of hardclock ticks per roundrobin() */
    113       1.26       cgd 
    114       1.73   thorpej /*
    115       1.73   thorpej  * The global scheduler state.
    116       1.73   thorpej  */
    117       1.73   thorpej struct prochd sched_qs[RUNQUE_NQS];	/* run queues */
    118       1.73   thorpej __volatile u_int32_t sched_whichqs;	/* bitmap of non-empty queues */
    119       1.73   thorpej struct slpque sched_slpque[SLPQUE_TABLESIZE]; /* sleep queues */
    120       1.73   thorpej 
    121       1.83   thorpej struct simplelock sched_lock = SIMPLELOCK_INITIALIZER;
    122       1.83   thorpej 
    123       1.77   thorpej void schedcpu(void *);
    124      1.122   thorpej void updatepri(struct lwp *);
    125       1.77   thorpej void endtsleep(void *);
    126       1.34  christos 
    127      1.139        cl __inline void sa_awaken(struct lwp *);
    128      1.122   thorpej __inline void awaken(struct lwp *);
    129       1.63   thorpej 
    130      1.143      yamt struct callout schedcpu_ch = CALLOUT_INITIALIZER_SETFUNC(schedcpu, NULL);
    131       1.68   thorpej 
    132      1.122   thorpej 
    133      1.122   thorpej 
    134       1.26       cgd /*
    135       1.26       cgd  * Force switch among equal priority processes every 100ms.
    136       1.88  sommerfe  * Called from hardclock every hz/10 == rrticks hardclock ticks.
    137       1.26       cgd  */
    138       1.26       cgd /* ARGSUSED */
    139       1.26       cgd void
    140       1.89  sommerfe roundrobin(struct cpu_info *ci)
    141       1.26       cgd {
    142       1.89  sommerfe 	struct schedstate_percpu *spc = &ci->ci_schedstate;
    143       1.26       cgd 
    144       1.88  sommerfe 	spc->spc_rrticks = rrticks;
    145      1.130   nathanw 
    146      1.122   thorpej 	if (curlwp != NULL) {
    147       1.73   thorpej 		if (spc->spc_flags & SPCF_SEENRR) {
    148       1.69   thorpej 			/*
    149       1.69   thorpej 			 * The process has already been through a roundrobin
    150       1.69   thorpej 			 * without switching and may be hogging the CPU.
    151       1.69   thorpej 			 * Indicate that the process should yield.
    152       1.69   thorpej 			 */
    153       1.73   thorpej 			spc->spc_flags |= SPCF_SHOULDYIELD;
    154       1.69   thorpej 		} else
    155       1.73   thorpej 			spc->spc_flags |= SPCF_SEENRR;
    156       1.69   thorpej 	}
    157       1.87   thorpej 	need_resched(curcpu());
    158       1.26       cgd }
    159       1.26       cgd 
    160       1.26       cgd /*
    161       1.26       cgd  * Constants for digital decay and forget:
    162       1.26       cgd  *	90% of (p_estcpu) usage in 5 * loadav time
    163       1.26       cgd  *	95% of (p_pctcpu) usage in 60 seconds (load insensitive)
    164       1.26       cgd  *          Note that, as ps(1) mentions, this can let percentages
    165       1.26       cgd  *          total over 100% (I've seen 137.9% for 3 processes).
    166       1.26       cgd  *
    167       1.26       cgd  * Note that hardclock updates p_estcpu and p_cpticks independently.
    168       1.26       cgd  *
    169       1.26       cgd  * We wish to decay away 90% of p_estcpu in (5 * loadavg) seconds.
    170       1.26       cgd  * That is, the system wants to compute a value of decay such
    171       1.26       cgd  * that the following for loop:
    172       1.26       cgd  * 	for (i = 0; i < (5 * loadavg); i++)
    173       1.26       cgd  * 		p_estcpu *= decay;
    174       1.26       cgd  * will compute
    175       1.26       cgd  * 	p_estcpu *= 0.1;
    176       1.26       cgd  * for all values of loadavg:
    177       1.26       cgd  *
    178       1.26       cgd  * Mathematically this loop can be expressed by saying:
    179       1.26       cgd  * 	decay ** (5 * loadavg) ~= .1
    180       1.26       cgd  *
    181       1.26       cgd  * The system computes decay as:
    182       1.26       cgd  * 	decay = (2 * loadavg) / (2 * loadavg + 1)
    183       1.26       cgd  *
    184       1.26       cgd  * We wish to prove that the system's computation of decay
    185       1.26       cgd  * will always fulfill the equation:
    186       1.26       cgd  * 	decay ** (5 * loadavg) ~= .1
    187       1.26       cgd  *
    188       1.26       cgd  * If we compute b as:
    189       1.26       cgd  * 	b = 2 * loadavg
    190       1.26       cgd  * then
    191       1.26       cgd  * 	decay = b / (b + 1)
    192       1.26       cgd  *
    193       1.26       cgd  * We now need to prove two things:
    194       1.26       cgd  *	1) Given factor ** (5 * loadavg) ~= .1, prove factor == b/(b+1)
    195       1.26       cgd  *	2) Given b/(b+1) ** power ~= .1, prove power == (5 * loadavg)
    196      1.130   nathanw  *
    197       1.26       cgd  * Facts:
    198       1.26       cgd  *         For x close to zero, exp(x) =~ 1 + x, since
    199       1.26       cgd  *              exp(x) = 0! + x**1/1! + x**2/2! + ... .
    200       1.26       cgd  *              therefore exp(-1/b) =~ 1 - (1/b) = (b-1)/b.
    201       1.26       cgd  *         For x close to zero, ln(1+x) =~ x, since
    202       1.26       cgd  *              ln(1+x) = x - x**2/2 + x**3/3 - ...     -1 < x < 1
    203       1.26       cgd  *              therefore ln(b/(b+1)) = ln(1 - 1/(b+1)) =~ -1/(b+1).
    204       1.26       cgd  *         ln(.1) =~ -2.30
    205       1.26       cgd  *
    206       1.26       cgd  * Proof of (1):
    207       1.26       cgd  *    Solve (factor)**(power) =~ .1 given power (5*loadav):
    208       1.26       cgd  *	solving for factor,
    209       1.26       cgd  *      ln(factor) =~ (-2.30/5*loadav), or
    210       1.26       cgd  *      factor =~ exp(-1/((5/2.30)*loadav)) =~ exp(-1/(2*loadav)) =
    211       1.26       cgd  *          exp(-1/b) =~ (b-1)/b =~ b/(b+1).                    QED
    212       1.26       cgd  *
    213       1.26       cgd  * Proof of (2):
    214       1.26       cgd  *    Solve (factor)**(power) =~ .1 given factor == (b/(b+1)):
    215       1.26       cgd  *	solving for power,
    216       1.26       cgd  *      power*ln(b/(b+1)) =~ -2.30, or
    217       1.26       cgd  *      power =~ 2.3 * (b + 1) = 4.6*loadav + 2.3 =~ 5*loadav.  QED
    218       1.26       cgd  *
    219       1.26       cgd  * Actual power values for the implemented algorithm are as follows:
    220       1.26       cgd  *      loadav: 1       2       3       4
    221       1.26       cgd  *      power:  5.68    10.32   14.94   19.55
    222       1.26       cgd  */
    223       1.26       cgd 
    224       1.26       cgd /* calculations for digital decay to forget 90% of usage in 5*loadav sec */
    225       1.26       cgd #define	loadfactor(loadav)	(2 * (loadav))
    226       1.26       cgd #define	decay_cpu(loadfac, cpu)	(((loadfac) * (cpu)) / ((loadfac) + FSCALE))
    227       1.26       cgd 
    228       1.26       cgd /* decay 95% of `p_pctcpu' in 60 seconds; see CCPU_SHIFT before changing */
    229       1.26       cgd fixpt_t	ccpu = 0.95122942450071400909 * FSCALE;		/* exp(-1/20) */
    230       1.26       cgd 
    231       1.26       cgd /*
    232       1.26       cgd  * If `ccpu' is not equal to `exp(-1/20)' and you still want to use the
    233       1.26       cgd  * faster/more-accurate formula, you'll have to estimate CCPU_SHIFT below
    234       1.26       cgd  * and possibly adjust FSHIFT in "param.h" so that (FSHIFT >= CCPU_SHIFT).
    235       1.26       cgd  *
    236       1.26       cgd  * To estimate CCPU_SHIFT for exp(-1/20), the following formula was used:
    237       1.26       cgd  *	1 - exp(-1/20) ~= 0.0487 ~= 0.0488 == 1 (fixed pt, *11* bits).
    238       1.26       cgd  *
    239       1.26       cgd  * If you dont want to bother with the faster/more-accurate formula, you
    240       1.26       cgd  * can set CCPU_SHIFT to (FSHIFT + 1) which will use a slower/less-accurate
    241       1.26       cgd  * (more general) method of calculating the %age of CPU used by a process.
    242       1.26       cgd  */
    243       1.26       cgd #define	CCPU_SHIFT	11
    244       1.26       cgd 
    245       1.26       cgd /*
    246       1.26       cgd  * Recompute process priorities, every hz ticks.
    247       1.26       cgd  */
    248       1.26       cgd /* ARGSUSED */
    249       1.26       cgd void
    250       1.77   thorpej schedcpu(void *arg)
    251       1.26       cgd {
    252       1.71  augustss 	fixpt_t loadfac = loadfactor(averunnable.ldavg[0]);
    253      1.122   thorpej 	struct lwp *l;
    254       1.71  augustss 	struct proc *p;
    255      1.122   thorpej 	int s, minslp;
    256       1.71  augustss 	unsigned int newcpu;
    257       1.66      ross 	int clkhz;
    258       1.26       cgd 
    259       1.62   thorpej 	proclist_lock_read();
    260      1.145      yamt 	PROCLIST_FOREACH(p, &allproc) {
    261       1.26       cgd 		/*
    262       1.26       cgd 		 * Increment time in/out of memory and sleep time
    263       1.26       cgd 		 * (if sleeping).  We ignore overflow; with 16-bit int's
    264       1.26       cgd 		 * (remember them?) overflow takes 45 days.
    265       1.26       cgd 		 */
    266      1.122   thorpej 		minslp = 2;
    267      1.122   thorpej 		LIST_FOREACH(l, &p->p_lwps, l_sibling) {
    268      1.122   thorpej 			l->l_swtime++;
    269      1.130   nathanw 			if (l->l_stat == LSSLEEP || l->l_stat == LSSTOP ||
    270      1.122   thorpej 			    l->l_stat == LSSUSPENDED) {
    271      1.122   thorpej 				l->l_slptime++;
    272      1.122   thorpej 				minslp = min(minslp, l->l_slptime);
    273      1.122   thorpej 			} else
    274      1.122   thorpej 				minslp = 0;
    275      1.122   thorpej 		}
    276       1.26       cgd 		p->p_pctcpu = (p->p_pctcpu * ccpu) >> FSHIFT;
    277       1.26       cgd 		/*
    278       1.26       cgd 		 * If the process has slept the entire second,
    279       1.26       cgd 		 * stop recalculating its priority until it wakes up.
    280       1.26       cgd 		 */
    281      1.122   thorpej 		if (minslp > 1)
    282       1.26       cgd 			continue;
    283       1.26       cgd 		s = splstatclock();	/* prevent state changes */
    284       1.26       cgd 		/*
    285       1.26       cgd 		 * p_pctcpu is only for ps.
    286       1.26       cgd 		 */
    287       1.66      ross 		clkhz = stathz != 0 ? stathz : hz;
    288       1.26       cgd #if	(FSHIFT >= CCPU_SHIFT)
    289       1.66      ross 		p->p_pctcpu += (clkhz == 100)?
    290       1.26       cgd 			((fixpt_t) p->p_cpticks) << (FSHIFT - CCPU_SHIFT):
    291       1.26       cgd                 	100 * (((fixpt_t) p->p_cpticks)
    292       1.66      ross 				<< (FSHIFT - CCPU_SHIFT)) / clkhz;
    293       1.26       cgd #else
    294       1.26       cgd 		p->p_pctcpu += ((FSCALE - ccpu) *
    295       1.66      ross 			(p->p_cpticks * FSCALE / clkhz)) >> FSHIFT;
    296       1.26       cgd #endif
    297       1.26       cgd 		p->p_cpticks = 0;
    298       1.55      ross 		newcpu = (u_int)decay_cpu(loadfac, p->p_estcpu);
    299       1.55      ross 		p->p_estcpu = newcpu;
    300      1.120        pk 		splx(s);	/* Done with the process CPU ticks update */
    301      1.120        pk 		SCHED_LOCK(s);
    302      1.122   thorpej 		LIST_FOREACH(l, &p->p_lwps, l_sibling) {
    303      1.122   thorpej 			if (l->l_slptime > 1)
    304      1.122   thorpej 				continue;
    305      1.122   thorpej 			resetpriority(l);
    306      1.122   thorpej 			if (l->l_priority >= PUSER) {
    307      1.122   thorpej 				if (l->l_stat == LSRUN &&
    308      1.122   thorpej 				    (l->l_flag & L_INMEM) &&
    309      1.122   thorpej 				    (l->l_priority / PPQ) != (l->l_usrpri / PPQ)) {
    310      1.122   thorpej 					remrunqueue(l);
    311      1.122   thorpej 					l->l_priority = l->l_usrpri;
    312      1.122   thorpej 					setrunqueue(l);
    313      1.122   thorpej 				} else
    314      1.122   thorpej 					l->l_priority = l->l_usrpri;
    315      1.122   thorpej 			}
    316       1.26       cgd 		}
    317      1.120        pk 		SCHED_UNLOCK(s);
    318       1.26       cgd 	}
    319       1.61   thorpej 	proclist_unlock_read();
    320       1.47       mrg 	uvm_meter();
    321       1.67      fvdl 	wakeup((caddr_t)&lbolt);
    322      1.143      yamt 	callout_schedule(&schedcpu_ch, hz);
    323       1.26       cgd }
    324       1.26       cgd 
    325       1.26       cgd /*
    326       1.26       cgd  * Recalculate the priority of a process after it has slept for a while.
    327       1.26       cgd  * For all load averages >= 1 and max p_estcpu of 255, sleeping for at
    328       1.26       cgd  * least six times the loadfactor will decay p_estcpu to zero.
    329       1.26       cgd  */
    330       1.26       cgd void
    331      1.122   thorpej updatepri(struct lwp *l)
    332       1.26       cgd {
    333      1.122   thorpej 	struct proc *p = l->l_proc;
    334       1.83   thorpej 	unsigned int newcpu;
    335       1.83   thorpej 	fixpt_t loadfac;
    336       1.83   thorpej 
    337       1.83   thorpej 	SCHED_ASSERT_LOCKED();
    338       1.83   thorpej 
    339       1.83   thorpej 	newcpu = p->p_estcpu;
    340       1.83   thorpej 	loadfac = loadfactor(averunnable.ldavg[0]);
    341       1.26       cgd 
    342      1.122   thorpej 	if (l->l_slptime > 5 * loadfac)
    343      1.122   thorpej 		p->p_estcpu = 0; /* XXX NJWLWP */
    344       1.26       cgd 	else {
    345      1.122   thorpej 		l->l_slptime--;	/* the first time was done in schedcpu */
    346      1.122   thorpej 		while (newcpu && --l->l_slptime)
    347       1.26       cgd 			newcpu = (int) decay_cpu(loadfac, newcpu);
    348       1.55      ross 		p->p_estcpu = newcpu;
    349       1.26       cgd 	}
    350      1.122   thorpej 	resetpriority(l);
    351       1.26       cgd }
    352       1.26       cgd 
    353       1.26       cgd /*
    354       1.26       cgd  * During autoconfiguration or after a panic, a sleep will simply
    355       1.26       cgd  * lower the priority briefly to allow interrupts, then return.
    356       1.26       cgd  * The priority to be used (safepri) is machine-dependent, thus this
    357       1.26       cgd  * value is initialized and maintained in the machine-dependent layers.
    358       1.26       cgd  * This priority will typically be 0, or the lowest priority
    359       1.26       cgd  * that is safe for use on the interrupt stack; it can be made
    360       1.26       cgd  * higher to block network software interrupts after panics.
    361       1.26       cgd  */
    362       1.26       cgd int safepri;
    363       1.26       cgd 
    364       1.26       cgd /*
    365       1.26       cgd  * General sleep call.  Suspends the current process until a wakeup is
    366       1.26       cgd  * performed on the specified identifier.  The process will then be made
    367       1.26       cgd  * runnable with the specified priority.  Sleeps at most timo/hz seconds
    368       1.26       cgd  * (0 means no timeout).  If pri includes PCATCH flag, signals are checked
    369       1.26       cgd  * before and after sleeping, else signals are not checked.  Returns 0 if
    370       1.26       cgd  * awakened, EWOULDBLOCK if the timeout expires.  If PCATCH is set and a
    371       1.26       cgd  * signal needs to be delivered, ERESTART is returned if the current system
    372       1.26       cgd  * call should be restarted if possible, and EINTR is returned if the system
    373       1.26       cgd  * call should be interrupted by the signal (return EINTR).
    374       1.77   thorpej  *
    375      1.103  jdolecek  * The interlock is held until the scheduler_slock is acquired.  The
    376       1.77   thorpej  * interlock will be locked before returning back to the caller
    377       1.77   thorpej  * unless the PNORELOCK flag is specified, in which case the
    378       1.77   thorpej  * interlock will always be unlocked upon return.
    379       1.26       cgd  */
    380       1.26       cgd int
    381      1.125      yamt ltsleep(const void *ident, int priority, const char *wmesg, int timo,
    382       1.77   thorpej     __volatile struct simplelock *interlock)
    383       1.26       cgd {
    384      1.122   thorpej 	struct lwp *l = curlwp;
    385      1.123  christos 	struct proc *p = l ? l->l_proc : NULL;
    386       1.71  augustss 	struct slpque *qp;
    387  1.148.2.1       riz 	struct sadata_upcall *sau;
    388       1.77   thorpej 	int sig, s;
    389       1.77   thorpej 	int catch = priority & PCATCH;
    390       1.77   thorpej 	int relock = (priority & PNORELOCK) == 0;
    391      1.122   thorpej 	int exiterr = (priority & PNOEXITERR) == 0;
    392       1.26       cgd 
    393       1.77   thorpej 	/*
    394       1.77   thorpej 	 * XXXSMP
    395       1.77   thorpej 	 * This is probably bogus.  Figure out what the right
    396       1.77   thorpej 	 * thing to do here really is.
    397      1.130   nathanw 	 * Note that not sleeping if ltsleep is called with curlwp == NULL
    398       1.78  sommerfe 	 * in the shutdown case is disgusting but partly necessary given
    399       1.78  sommerfe 	 * how shutdown (barely) works.
    400       1.77   thorpej 	 */
    401      1.122   thorpej 	if (cold || (doing_shutdown && (panicstr || (l == NULL)))) {
    402       1.26       cgd 		/*
    403       1.26       cgd 		 * After a panic, or during autoconfiguration,
    404       1.26       cgd 		 * just give interrupts a chance, then just return;
    405       1.26       cgd 		 * don't run any other procs or panic below,
    406       1.26       cgd 		 * in case this is the idle process and already asleep.
    407       1.26       cgd 		 */
    408       1.42       cgd 		s = splhigh();
    409       1.26       cgd 		splx(safepri);
    410       1.26       cgd 		splx(s);
    411       1.77   thorpej 		if (interlock != NULL && relock == 0)
    412       1.77   thorpej 			simple_unlock(interlock);
    413       1.26       cgd 		return (0);
    414       1.26       cgd 	}
    415       1.78  sommerfe 
    416      1.102   thorpej 	KASSERT(p != NULL);
    417      1.105       chs 	LOCK_ASSERT(interlock == NULL || simple_lock_held(interlock));
    418       1.42       cgd 
    419       1.42       cgd #ifdef KTRACE
    420       1.42       cgd 	if (KTRPOINT(p, KTR_CSW))
    421      1.132      fvdl 		ktrcsw(p, 1, 0);
    422       1.42       cgd #endif
    423       1.77   thorpej 
    424  1.148.2.1       riz 	/*
    425  1.148.2.1       riz 	 * XXX We need to allocate the sadata_upcall structure here,
    426  1.148.2.1       riz 	 * XXX since we can't sleep while waiting for memory inside
    427  1.148.2.1       riz 	 * XXX sa_upcall().  It would be nice if we could safely
    428  1.148.2.1       riz 	 * XXX allocate the sadata_upcall structure on the stack, here.
    429  1.148.2.1       riz 	 */
    430  1.148.2.1       riz 	if (l->l_flag & L_SA) {
    431  1.148.2.1       riz 		sau = sadata_upcall_alloc(0);
    432  1.148.2.1       riz 	} else {
    433  1.148.2.1       riz 		sau = NULL;
    434  1.148.2.1       riz 	}
    435  1.148.2.1       riz 
    436       1.83   thorpej 	SCHED_LOCK(s);
    437       1.42       cgd 
    438       1.26       cgd #ifdef DIAGNOSTIC
    439       1.64   thorpej 	if (ident == NULL)
    440       1.77   thorpej 		panic("ltsleep: ident == NULL");
    441      1.122   thorpej 	if (l->l_stat != LSONPROC)
    442      1.122   thorpej 		panic("ltsleep: l_stat %d != LSONPROC", l->l_stat);
    443      1.122   thorpej 	if (l->l_back != NULL)
    444       1.77   thorpej 		panic("ltsleep: p_back != NULL");
    445       1.26       cgd #endif
    446       1.77   thorpej 
    447      1.122   thorpej 	l->l_wchan = ident;
    448      1.122   thorpej 	l->l_wmesg = wmesg;
    449      1.122   thorpej 	l->l_slptime = 0;
    450      1.122   thorpej 	l->l_priority = priority & PRIMASK;
    451       1.77   thorpej 
    452       1.73   thorpej 	qp = SLPQUE(ident);
    453       1.26       cgd 	if (qp->sq_head == 0)
    454      1.122   thorpej 		qp->sq_head = l;
    455      1.122   thorpej 	else {
    456      1.122   thorpej 		*qp->sq_tailp = l;
    457      1.122   thorpej 	}
    458      1.122   thorpej 	*(qp->sq_tailp = &l->l_forw) = 0;
    459       1.77   thorpej 
    460       1.26       cgd 	if (timo)
    461      1.122   thorpej 		callout_reset(&l->l_tsleep_ch, timo, endtsleep, l);
    462       1.77   thorpej 
    463       1.77   thorpej 	/*
    464       1.77   thorpej 	 * We can now release the interlock; the scheduler_slock
    465       1.77   thorpej 	 * is held, so a thread can't get in to do wakeup() before
    466       1.77   thorpej 	 * we do the switch.
    467       1.77   thorpej 	 *
    468       1.77   thorpej 	 * XXX We leave the code block here, after inserting ourselves
    469       1.77   thorpej 	 * on the sleep queue, because we might want a more clever
    470       1.77   thorpej 	 * data structure for the sleep queues at some point.
    471       1.77   thorpej 	 */
    472       1.77   thorpej 	if (interlock != NULL)
    473       1.77   thorpej 		simple_unlock(interlock);
    474       1.77   thorpej 
    475       1.26       cgd 	/*
    476       1.26       cgd 	 * We put ourselves on the sleep queue and start our timeout
    477       1.26       cgd 	 * before calling CURSIG, as we could stop there, and a wakeup
    478       1.26       cgd 	 * or a SIGCONT (or both) could occur while we were stopped.
    479       1.26       cgd 	 * A SIGCONT would cause us to be marked as SSLEEP
    480       1.26       cgd 	 * without resuming us, thus we must be ready for sleep
    481       1.26       cgd 	 * when CURSIG is called.  If the wakeup happens while we're
    482       1.26       cgd 	 * stopped, p->p_wchan will be 0 upon return from CURSIG.
    483       1.26       cgd 	 */
    484       1.26       cgd 	if (catch) {
    485      1.122   thorpej 		l->l_flag |= L_SINTR;
    486      1.137    itojun 		if (((sig = CURSIG(l)) != 0) ||
    487      1.137    itojun 		    ((p->p_flag & P_WEXIT) && p->p_nlwps > 1)) {
    488      1.122   thorpej 			if (l->l_wchan != NULL)
    489      1.122   thorpej 				unsleep(l);
    490      1.122   thorpej 			l->l_stat = LSONPROC;
    491       1.83   thorpej 			SCHED_UNLOCK(s);
    492       1.26       cgd 			goto resume;
    493       1.26       cgd 		}
    494      1.122   thorpej 		if (l->l_wchan == NULL) {
    495       1.26       cgd 			catch = 0;
    496       1.83   thorpej 			SCHED_UNLOCK(s);
    497       1.26       cgd 			goto resume;
    498       1.26       cgd 		}
    499       1.26       cgd 	} else
    500       1.26       cgd 		sig = 0;
    501      1.122   thorpej 	l->l_stat = LSSLEEP;
    502      1.122   thorpej 	p->p_nrlwps--;
    503       1.26       cgd 	p->p_stats->p_ru.ru_nvcsw++;
    504       1.83   thorpej 	SCHED_ASSERT_LOCKED();
    505      1.122   thorpej 	if (l->l_flag & L_SA)
    506  1.148.2.1       riz 		sa_switch(l, sau, SA_UPCALL_BLOCKED);
    507      1.122   thorpej 	else
    508      1.122   thorpej 		mi_switch(l, NULL);
    509       1.83   thorpej 
    510      1.104       chs #if	defined(DDB) && !defined(GPROF)
    511       1.26       cgd 	/* handy breakpoint location after process "wakes" */
    512      1.140    kleink 	__asm(".globl bpendtsleep\nbpendtsleep:");
    513       1.26       cgd #endif
    514      1.122   thorpej 	/*
    515      1.122   thorpej 	 * p->p_nrlwps is incremented by whoever made us runnable again,
    516      1.122   thorpej 	 * either setrunnable() or awaken().
    517      1.122   thorpej 	 */
    518       1.77   thorpej 
    519       1.83   thorpej 	SCHED_ASSERT_UNLOCKED();
    520       1.83   thorpej 	splx(s);
    521       1.83   thorpej 
    522       1.77   thorpej  resume:
    523      1.122   thorpej 	KDASSERT(l->l_cpu != NULL);
    524      1.122   thorpej 	KDASSERT(l->l_cpu == curcpu());
    525      1.122   thorpej 	l->l_cpu->ci_schedstate.spc_curpriority = l->l_usrpri;
    526      1.122   thorpej 
    527      1.122   thorpej 	l->l_flag &= ~L_SINTR;
    528      1.122   thorpej 	if (l->l_flag & L_TIMEOUT) {
    529      1.135      matt 		l->l_flag &= ~(L_TIMEOUT|L_CANCELLED);
    530       1.26       cgd 		if (sig == 0) {
    531       1.26       cgd #ifdef KTRACE
    532       1.26       cgd 			if (KTRPOINT(p, KTR_CSW))
    533      1.132      fvdl 				ktrcsw(p, 0, 0);
    534       1.26       cgd #endif
    535       1.77   thorpej 			if (relock && interlock != NULL)
    536       1.77   thorpej 				simple_lock(interlock);
    537       1.26       cgd 			return (EWOULDBLOCK);
    538       1.26       cgd 		}
    539       1.26       cgd 	} else if (timo)
    540      1.122   thorpej 		callout_stop(&l->l_tsleep_ch);
    541      1.135      matt 
    542      1.135      matt 	if (catch) {
    543      1.135      matt 		const int cancelled = l->l_flag & L_CANCELLED;
    544      1.135      matt 		l->l_flag &= ~L_CANCELLED;
    545      1.135      matt 		if (sig != 0 || (sig = CURSIG(l)) != 0 || cancelled) {
    546       1.26       cgd #ifdef KTRACE
    547      1.135      matt 			if (KTRPOINT(p, KTR_CSW))
    548      1.135      matt 				ktrcsw(p, 0, 0);
    549       1.26       cgd #endif
    550      1.135      matt 			if (relock && interlock != NULL)
    551      1.135      matt 				simple_lock(interlock);
    552      1.135      matt 			/*
    553      1.135      matt 			 * If this sleep was canceled, don't let the syscall
    554      1.135      matt 			 * restart.
    555      1.135      matt 			 */
    556      1.135      matt 			if (cancelled ||
    557      1.135      matt 			    (SIGACTION(p, sig).sa_flags & SA_RESTART) == 0)
    558      1.135      matt 				return (EINTR);
    559      1.135      matt 			return (ERESTART);
    560      1.135      matt 		}
    561       1.26       cgd 	}
    562      1.126        pk 
    563      1.126        pk #ifdef KTRACE
    564      1.126        pk 	if (KTRPOINT(p, KTR_CSW))
    565      1.132      fvdl 		ktrcsw(p, 0, 0);
    566      1.126        pk #endif
    567      1.126        pk 	if (relock && interlock != NULL)
    568      1.126        pk 		simple_lock(interlock);
    569      1.126        pk 
    570      1.122   thorpej 	/* XXXNJW this is very much a kluge.
    571      1.130   nathanw 	 * revisit. a better way of preventing looping/hanging syscalls like
    572      1.122   thorpej 	 * wait4() and _lwp_wait() from wedging an exiting process
    573      1.122   thorpej 	 * would be preferred.
    574      1.122   thorpej 	 */
    575      1.137    itojun 	if (catch && ((p->p_flag & P_WEXIT) && p->p_nlwps > 1 && exiterr))
    576      1.122   thorpej 		return (EINTR);
    577       1.26       cgd 	return (0);
    578       1.26       cgd }
    579       1.26       cgd 
    580       1.26       cgd /*
    581       1.26       cgd  * Implement timeout for tsleep.
    582       1.26       cgd  * If process hasn't been awakened (wchan non-zero),
    583       1.26       cgd  * set timeout flag and undo the sleep.  If proc
    584       1.26       cgd  * is stopped, just unsleep so it will remain stopped.
    585       1.26       cgd  */
    586       1.26       cgd void
    587       1.77   thorpej endtsleep(void *arg)
    588       1.26       cgd {
    589      1.122   thorpej 	struct lwp *l;
    590       1.26       cgd 	int s;
    591       1.26       cgd 
    592      1.122   thorpej 	l = (struct lwp *)arg;
    593       1.83   thorpej 	SCHED_LOCK(s);
    594      1.122   thorpej 	if (l->l_wchan) {
    595      1.122   thorpej 		if (l->l_stat == LSSLEEP)
    596      1.122   thorpej 			setrunnable(l);
    597       1.26       cgd 		else
    598      1.122   thorpej 			unsleep(l);
    599      1.122   thorpej 		l->l_flag |= L_TIMEOUT;
    600       1.26       cgd 	}
    601       1.83   thorpej 	SCHED_UNLOCK(s);
    602       1.26       cgd }
    603       1.26       cgd 
    604       1.26       cgd /*
    605       1.26       cgd  * Remove a process from its wait queue
    606       1.26       cgd  */
    607       1.26       cgd void
    608      1.122   thorpej unsleep(struct lwp *l)
    609       1.26       cgd {
    610       1.71  augustss 	struct slpque *qp;
    611      1.122   thorpej 	struct lwp **hp;
    612       1.26       cgd 
    613       1.83   thorpej 	SCHED_ASSERT_LOCKED();
    614       1.83   thorpej 
    615      1.122   thorpej 	if (l->l_wchan) {
    616      1.122   thorpej 		hp = &(qp = SLPQUE(l->l_wchan))->sq_head;
    617      1.122   thorpej 		while (*hp != l)
    618      1.122   thorpej 			hp = &(*hp)->l_forw;
    619      1.122   thorpej 		*hp = l->l_forw;
    620      1.122   thorpej 		if (qp->sq_tailp == &l->l_forw)
    621       1.26       cgd 			qp->sq_tailp = hp;
    622      1.122   thorpej 		l->l_wchan = 0;
    623       1.26       cgd 	}
    624       1.26       cgd }
    625       1.26       cgd 
    626      1.139        cl __inline void
    627      1.139        cl sa_awaken(struct lwp *l)
    628      1.139        cl {
    629      1.147     perry 
    630      1.139        cl 	SCHED_ASSERT_LOCKED();
    631      1.139        cl 
    632      1.142        cl 	if (l == l->l_savp->savp_lwp && l->l_flag & L_SA_YIELD)
    633      1.139        cl 		l->l_flag &= ~L_SA_IDLE;
    634      1.139        cl }
    635      1.139        cl 
    636       1.26       cgd /*
    637       1.63   thorpej  * Optimized-for-wakeup() version of setrunnable().
    638       1.63   thorpej  */
    639       1.63   thorpej __inline void
    640      1.122   thorpej awaken(struct lwp *l)
    641       1.63   thorpej {
    642       1.63   thorpej 
    643       1.83   thorpej 	SCHED_ASSERT_LOCKED();
    644      1.130   nathanw 
    645      1.139        cl 	if (l->l_proc->p_sa)
    646      1.139        cl 		sa_awaken(l);
    647      1.139        cl 
    648      1.122   thorpej 	if (l->l_slptime > 1)
    649      1.122   thorpej 		updatepri(l);
    650      1.122   thorpej 	l->l_slptime = 0;
    651      1.122   thorpej 	l->l_stat = LSRUN;
    652      1.122   thorpej 	l->l_proc->p_nrlwps++;
    653       1.93    bouyer 	/*
    654       1.93    bouyer 	 * Since curpriority is a user priority, p->p_priority
    655      1.119   thorpej 	 * is always better than curpriority on the last CPU on
    656      1.119   thorpej 	 * which it ran.
    657      1.118   thorpej 	 *
    658      1.119   thorpej 	 * XXXSMP See affinity comment in resched_proc().
    659       1.93    bouyer 	 */
    660      1.122   thorpej 	if (l->l_flag & L_INMEM) {
    661      1.122   thorpej 		setrunqueue(l);
    662      1.122   thorpej 		KASSERT(l->l_cpu != NULL);
    663      1.122   thorpej 		need_resched(l->l_cpu);
    664       1.93    bouyer 	} else
    665       1.93    bouyer 		sched_wakeup(&proc0);
    666       1.83   thorpej }
    667       1.83   thorpej 
    668       1.83   thorpej #if defined(MULTIPROCESSOR) || defined(LOCKDEBUG)
    669       1.83   thorpej void
    670       1.83   thorpej sched_unlock_idle(void)
    671       1.83   thorpej {
    672       1.83   thorpej 
    673       1.83   thorpej 	simple_unlock(&sched_lock);
    674       1.63   thorpej }
    675       1.63   thorpej 
    676       1.83   thorpej void
    677       1.83   thorpej sched_lock_idle(void)
    678       1.83   thorpej {
    679       1.83   thorpej 
    680       1.83   thorpej 	simple_lock(&sched_lock);
    681       1.83   thorpej }
    682       1.83   thorpej #endif /* MULTIPROCESSOR || LOCKDEBUG */
    683       1.83   thorpej 
    684       1.63   thorpej /*
    685       1.26       cgd  * Make all processes sleeping on the specified identifier runnable.
    686       1.26       cgd  */
    687       1.83   thorpej 
    688       1.26       cgd void
    689      1.125      yamt wakeup(const void *ident)
    690       1.26       cgd {
    691       1.83   thorpej 	int s;
    692       1.83   thorpej 
    693       1.83   thorpej 	SCHED_ASSERT_UNLOCKED();
    694       1.83   thorpej 
    695       1.83   thorpej 	SCHED_LOCK(s);
    696       1.83   thorpej 	sched_wakeup(ident);
    697       1.83   thorpej 	SCHED_UNLOCK(s);
    698       1.83   thorpej }
    699       1.83   thorpej 
    700       1.83   thorpej void
    701      1.125      yamt sched_wakeup(const void *ident)
    702       1.83   thorpej {
    703       1.71  augustss 	struct slpque *qp;
    704      1.122   thorpej 	struct lwp *l, **q;
    705       1.26       cgd 
    706       1.83   thorpej 	SCHED_ASSERT_LOCKED();
    707       1.77   thorpej 
    708       1.73   thorpej 	qp = SLPQUE(ident);
    709       1.77   thorpej  restart:
    710      1.122   thorpej 	for (q = &qp->sq_head; (l = *q) != NULL; ) {
    711       1.26       cgd #ifdef DIAGNOSTIC
    712      1.130   nathanw 		if (l->l_back || (l->l_stat != LSSLEEP &&
    713      1.122   thorpej 		    l->l_stat != LSSTOP && l->l_stat != LSSUSPENDED))
    714       1.26       cgd 			panic("wakeup");
    715       1.26       cgd #endif
    716      1.122   thorpej 		if (l->l_wchan == ident) {
    717      1.122   thorpej 			l->l_wchan = 0;
    718      1.122   thorpej 			*q = l->l_forw;
    719      1.122   thorpej 			if (qp->sq_tailp == &l->l_forw)
    720       1.26       cgd 				qp->sq_tailp = q;
    721      1.122   thorpej 			if (l->l_stat == LSSLEEP) {
    722      1.122   thorpej 				awaken(l);
    723       1.26       cgd 				goto restart;
    724       1.26       cgd 			}
    725       1.26       cgd 		} else
    726      1.122   thorpej 			q = &l->l_forw;
    727       1.63   thorpej 	}
    728       1.63   thorpej }
    729       1.63   thorpej 
    730       1.63   thorpej /*
    731       1.63   thorpej  * Make the highest priority process first in line on the specified
    732       1.63   thorpej  * identifier runnable.
    733       1.63   thorpej  */
    734       1.63   thorpej void
    735      1.125      yamt wakeup_one(const void *ident)
    736       1.63   thorpej {
    737       1.63   thorpej 	struct slpque *qp;
    738      1.122   thorpej 	struct lwp *l, **q;
    739      1.122   thorpej 	struct lwp *best_sleepp, **best_sleepq;
    740      1.122   thorpej 	struct lwp *best_stopp, **best_stopq;
    741       1.63   thorpej 	int s;
    742       1.63   thorpej 
    743       1.63   thorpej 	best_sleepp = best_stopp = NULL;
    744       1.63   thorpej 	best_sleepq = best_stopq = NULL;
    745       1.63   thorpej 
    746       1.83   thorpej 	SCHED_LOCK(s);
    747       1.77   thorpej 
    748       1.73   thorpej 	qp = SLPQUE(ident);
    749       1.77   thorpej 
    750      1.122   thorpej 	for (q = &qp->sq_head; (l = *q) != NULL; q = &l->l_forw) {
    751       1.63   thorpej #ifdef DIAGNOSTIC
    752      1.130   nathanw 		if (l->l_back || (l->l_stat != LSSLEEP &&
    753      1.122   thorpej 		    l->l_stat != LSSTOP && l->l_stat != LSSUSPENDED))
    754       1.63   thorpej 			panic("wakeup_one");
    755       1.63   thorpej #endif
    756      1.122   thorpej 		if (l->l_wchan == ident) {
    757      1.122   thorpej 			if (l->l_stat == LSSLEEP) {
    758       1.63   thorpej 				if (best_sleepp == NULL ||
    759      1.122   thorpej 				    l->l_priority < best_sleepp->l_priority) {
    760      1.122   thorpej 					best_sleepp = l;
    761       1.63   thorpej 					best_sleepq = q;
    762       1.63   thorpej 				}
    763       1.63   thorpej 			} else {
    764       1.63   thorpej 				if (best_stopp == NULL ||
    765      1.122   thorpej 				    l->l_priority < best_stopp->l_priority) {
    766      1.122   thorpej 				    	best_stopp = l;
    767       1.63   thorpej 					best_stopq = q;
    768       1.63   thorpej 				}
    769       1.63   thorpej 			}
    770       1.63   thorpej 		}
    771       1.63   thorpej 	}
    772       1.63   thorpej 
    773       1.63   thorpej 	/*
    774       1.63   thorpej 	 * Consider any SSLEEP process higher than the highest priority SSTOP
    775       1.63   thorpej 	 * process.
    776       1.63   thorpej 	 */
    777       1.63   thorpej 	if (best_sleepp != NULL) {
    778      1.122   thorpej 		l = best_sleepp;
    779       1.63   thorpej 		q = best_sleepq;
    780       1.63   thorpej 	} else {
    781      1.122   thorpej 		l = best_stopp;
    782       1.63   thorpej 		q = best_stopq;
    783       1.63   thorpej 	}
    784       1.63   thorpej 
    785      1.122   thorpej 	if (l != NULL) {
    786      1.122   thorpej 		l->l_wchan = NULL;
    787      1.122   thorpej 		*q = l->l_forw;
    788      1.122   thorpej 		if (qp->sq_tailp == &l->l_forw)
    789       1.63   thorpej 			qp->sq_tailp = q;
    790      1.122   thorpej 		if (l->l_stat == LSSLEEP)
    791      1.122   thorpej 			awaken(l);
    792       1.26       cgd 	}
    793       1.83   thorpej 	SCHED_UNLOCK(s);
    794      1.117  gmcgarry }
    795      1.117  gmcgarry 
    796      1.117  gmcgarry /*
    797      1.117  gmcgarry  * General yield call.  Puts the current process back on its run queue and
    798      1.117  gmcgarry  * performs a voluntary context switch.  Should only be called when the
    799      1.117  gmcgarry  * current process explicitly requests it (eg sched_yield(2) in compat code).
    800      1.117  gmcgarry  */
    801      1.117  gmcgarry void
    802      1.117  gmcgarry yield(void)
    803      1.117  gmcgarry {
    804      1.122   thorpej 	struct lwp *l = curlwp;
    805      1.117  gmcgarry 	int s;
    806      1.117  gmcgarry 
    807      1.117  gmcgarry 	SCHED_LOCK(s);
    808      1.122   thorpej 	l->l_priority = l->l_usrpri;
    809      1.122   thorpej 	l->l_stat = LSRUN;
    810      1.122   thorpej 	setrunqueue(l);
    811      1.122   thorpej 	l->l_proc->p_stats->p_ru.ru_nvcsw++;
    812      1.122   thorpej 	mi_switch(l, NULL);
    813      1.117  gmcgarry 	SCHED_ASSERT_UNLOCKED();
    814      1.117  gmcgarry 	splx(s);
    815       1.69   thorpej }
    816       1.69   thorpej 
    817       1.69   thorpej /*
    818       1.69   thorpej  * General preemption call.  Puts the current process back on its run queue
    819       1.69   thorpej  * and performs an involuntary context switch.  If a process is supplied,
    820       1.69   thorpej  * we switch to that process.  Otherwise, we use the normal process selection
    821       1.69   thorpej  * criteria.
    822       1.69   thorpej  */
    823      1.122   thorpej 
    824       1.69   thorpej void
    825      1.122   thorpej preempt(int more)
    826       1.69   thorpej {
    827      1.122   thorpej 	struct lwp *l = curlwp;
    828      1.122   thorpej 	int r, s;
    829       1.69   thorpej 
    830       1.83   thorpej 	SCHED_LOCK(s);
    831      1.122   thorpej 	l->l_priority = l->l_usrpri;
    832      1.122   thorpej 	l->l_stat = LSRUN;
    833      1.122   thorpej 	setrunqueue(l);
    834      1.122   thorpej 	l->l_proc->p_stats->p_ru.ru_nivcsw++;
    835      1.122   thorpej 	r = mi_switch(l, NULL);
    836       1.83   thorpej 	SCHED_ASSERT_UNLOCKED();
    837       1.69   thorpej 	splx(s);
    838      1.122   thorpej 	if ((l->l_flag & L_SA) != 0 && r != 0 && more == 0)
    839      1.122   thorpej 		sa_preempt(l);
    840       1.69   thorpej }
    841       1.69   thorpej 
    842       1.69   thorpej /*
    843       1.72   thorpej  * The machine independent parts of context switch.
    844       1.86   thorpej  * Must be called at splsched() (no higher!) and with
    845       1.86   thorpej  * the sched_lock held.
    846      1.122   thorpej  * Switch to "new" if non-NULL, otherwise let cpu_switch choose
    847      1.122   thorpej  * the next lwp.
    848      1.130   nathanw  *
    849      1.122   thorpej  * Returns 1 if another process was actually run.
    850       1.26       cgd  */
    851      1.122   thorpej int
    852      1.122   thorpej mi_switch(struct lwp *l, struct lwp *newl)
    853       1.26       cgd {
    854       1.76   thorpej 	struct schedstate_percpu *spc;
    855       1.71  augustss 	struct rlimit *rlim;
    856       1.71  augustss 	long s, u;
    857       1.26       cgd 	struct timeval tv;
    858      1.144      yamt 	int hold_count;
    859      1.122   thorpej 	struct proc *p = l->l_proc;
    860      1.122   thorpej 	int retval;
    861       1.26       cgd 
    862       1.83   thorpej 	SCHED_ASSERT_LOCKED();
    863       1.83   thorpej 
    864       1.90  sommerfe 	/*
    865       1.90  sommerfe 	 * Release the kernel_lock, as we are about to yield the CPU.
    866       1.90  sommerfe 	 * The scheduler lock is still held until cpu_switch()
    867       1.90  sommerfe 	 * selects a new process and removes it from the run queue.
    868       1.90  sommerfe 	 */
    869      1.144      yamt 	hold_count = KERNEL_LOCK_RELEASE_ALL();
    870       1.85  sommerfe 
    871      1.122   thorpej 	KDASSERT(l->l_cpu != NULL);
    872      1.122   thorpej 	KDASSERT(l->l_cpu == curcpu());
    873      1.113  gmcgarry 
    874      1.122   thorpej 	spc = &l->l_cpu->ci_schedstate;
    875       1.76   thorpej 
    876       1.82   thorpej #if defined(LOCKDEBUG) || defined(DIAGNOSTIC)
    877       1.82   thorpej 	spinlock_switchcheck();
    878       1.82   thorpej #endif
    879       1.54       chs #ifdef LOCKDEBUG
    880       1.81   thorpej 	simple_lock_switchcheck();
    881       1.50      fvdl #endif
    882       1.81   thorpej 
    883       1.26       cgd 	/*
    884       1.26       cgd 	 * Compute the amount of time during which the current
    885      1.113  gmcgarry 	 * process was running.
    886       1.26       cgd 	 */
    887       1.26       cgd 	microtime(&tv);
    888      1.130   nathanw 	u = p->p_rtime.tv_usec +
    889      1.122   thorpej 	    (tv.tv_usec - spc->spc_runtime.tv_usec);
    890       1.73   thorpej 	s = p->p_rtime.tv_sec + (tv.tv_sec - spc->spc_runtime.tv_sec);
    891       1.26       cgd 	if (u < 0) {
    892       1.26       cgd 		u += 1000000;
    893       1.26       cgd 		s--;
    894       1.26       cgd 	} else if (u >= 1000000) {
    895       1.26       cgd 		u -= 1000000;
    896       1.26       cgd 		s++;
    897       1.26       cgd 	}
    898      1.114  gmcgarry 	p->p_rtime.tv_usec = u;
    899      1.114  gmcgarry 	p->p_rtime.tv_sec = s;
    900       1.26       cgd 
    901       1.26       cgd 	/*
    902      1.141       wiz 	 * Check if the process exceeds its CPU resource allocation.
    903       1.26       cgd 	 * If over max, kill it.  In any case, if it has run for more
    904       1.26       cgd 	 * than 10 minutes, reduce priority to give others a chance.
    905       1.26       cgd 	 */
    906       1.26       cgd 	rlim = &p->p_rlimit[RLIMIT_CPU];
    907       1.26       cgd 	if (s >= rlim->rlim_cur) {
    908      1.100  sommerfe 		/*
    909      1.100  sommerfe 		 * XXXSMP: we're inside the scheduler lock perimeter;
    910      1.100  sommerfe 		 * use sched_psignal.
    911      1.100  sommerfe 		 */
    912       1.26       cgd 		if (s >= rlim->rlim_max)
    913      1.100  sommerfe 			sched_psignal(p, SIGKILL);
    914       1.26       cgd 		else {
    915      1.100  sommerfe 			sched_psignal(p, SIGXCPU);
    916       1.26       cgd 			if (rlim->rlim_cur < rlim->rlim_max)
    917       1.26       cgd 				rlim->rlim_cur += 5;
    918       1.26       cgd 		}
    919       1.26       cgd 	}
    920       1.77   thorpej 	if (autonicetime && s > autonicetime && p->p_ucred->cr_uid &&
    921       1.77   thorpej 	    p->p_nice == NZERO) {
    922       1.39        ws 		p->p_nice = autoniceval + NZERO;
    923      1.122   thorpej 		resetpriority(l);
    924       1.26       cgd 	}
    925       1.69   thorpej 
    926       1.69   thorpej 	/*
    927       1.69   thorpej 	 * Process is about to yield the CPU; clear the appropriate
    928       1.69   thorpej 	 * scheduling flags.
    929       1.69   thorpej 	 */
    930       1.73   thorpej 	spc->spc_flags &= ~SPCF_SWITCHCLEAR;
    931      1.109      yamt 
    932      1.109      yamt #ifdef KSTACK_CHECK_MAGIC
    933      1.124      yamt 	kstack_check_magic(l);
    934      1.109      yamt #endif
    935       1.26       cgd 
    936      1.113  gmcgarry 	/*
    937      1.114  gmcgarry 	 * If we are using h/w performance counters, save context.
    938      1.113  gmcgarry 	 */
    939      1.114  gmcgarry #if PERFCTRS
    940      1.114  gmcgarry 	if (PMC_ENABLED(p))
    941      1.114  gmcgarry 		pmc_save_context(p);
    942      1.110    briggs #endif
    943      1.113  gmcgarry 
    944      1.113  gmcgarry 	/*
    945      1.114  gmcgarry 	 * Switch to the new current process.  When we
    946      1.114  gmcgarry 	 * run again, we'll return back here.
    947      1.113  gmcgarry 	 */
    948      1.114  gmcgarry 	uvmexp.swtch++;
    949      1.122   thorpej 	if (newl == NULL) {
    950      1.122   thorpej 		retval = cpu_switch(l, NULL);
    951      1.122   thorpej 	} else {
    952      1.122   thorpej 		remrunqueue(newl);
    953      1.122   thorpej 		cpu_switchto(l, newl);
    954      1.122   thorpej 		retval = 0;
    955      1.122   thorpej 	}
    956      1.110    briggs 
    957      1.110    briggs 	/*
    958      1.114  gmcgarry 	 * If we are using h/w performance counters, restore context.
    959       1.26       cgd 	 */
    960      1.114  gmcgarry #if PERFCTRS
    961      1.114  gmcgarry 	if (PMC_ENABLED(p))
    962      1.114  gmcgarry 		pmc_restore_context(p);
    963      1.114  gmcgarry #endif
    964      1.110    briggs 
    965      1.110    briggs 	/*
    966      1.114  gmcgarry 	 * Make sure that MD code released the scheduler lock before
    967      1.114  gmcgarry 	 * resuming us.
    968      1.110    briggs 	 */
    969      1.114  gmcgarry 	SCHED_ASSERT_UNLOCKED();
    970       1.83   thorpej 
    971       1.83   thorpej 	/*
    972       1.76   thorpej 	 * We're running again; record our new start time.  We might
    973       1.76   thorpej 	 * be running on a new CPU now, so don't use the cache'd
    974       1.76   thorpej 	 * schedstate_percpu pointer.
    975       1.76   thorpej 	 */
    976      1.122   thorpej 	KDASSERT(l->l_cpu != NULL);
    977      1.122   thorpej 	KDASSERT(l->l_cpu == curcpu());
    978      1.122   thorpej 	microtime(&l->l_cpu->ci_schedstate.spc_runtime);
    979       1.85  sommerfe 
    980       1.90  sommerfe 	/*
    981       1.90  sommerfe 	 * Reacquire the kernel_lock now.  We do this after we've
    982       1.90  sommerfe 	 * released the scheduler lock to avoid deadlock, and before
    983       1.90  sommerfe 	 * we reacquire the interlock.
    984       1.90  sommerfe 	 */
    985      1.144      yamt 	KERNEL_LOCK_ACQUIRE_COUNT(hold_count);
    986      1.122   thorpej 
    987      1.122   thorpej 	return retval;
    988       1.26       cgd }
    989       1.26       cgd 
    990       1.26       cgd /*
    991       1.26       cgd  * Initialize the (doubly-linked) run queues
    992       1.26       cgd  * to be empty.
    993       1.26       cgd  */
    994       1.26       cgd void
    995       1.26       cgd rqinit()
    996       1.26       cgd {
    997       1.71  augustss 	int i;
    998       1.26       cgd 
    999       1.73   thorpej 	for (i = 0; i < RUNQUE_NQS; i++)
   1000       1.73   thorpej 		sched_qs[i].ph_link = sched_qs[i].ph_rlink =
   1001      1.122   thorpej 		    (struct lwp *)&sched_qs[i];
   1002       1.26       cgd }
   1003       1.26       cgd 
   1004      1.119   thorpej static __inline void
   1005      1.122   thorpej resched_proc(struct lwp *l, u_char pri)
   1006      1.119   thorpej {
   1007      1.119   thorpej 	struct cpu_info *ci;
   1008      1.119   thorpej 
   1009      1.119   thorpej 	/*
   1010      1.119   thorpej 	 * XXXSMP
   1011      1.122   thorpej 	 * Since l->l_cpu persists across a context switch,
   1012      1.119   thorpej 	 * this gives us *very weak* processor affinity, in
   1013      1.119   thorpej 	 * that we notify the CPU on which the process last
   1014      1.119   thorpej 	 * ran that it should try to switch.
   1015      1.119   thorpej 	 *
   1016      1.119   thorpej 	 * This does not guarantee that the process will run on
   1017      1.119   thorpej 	 * that processor next, because another processor might
   1018      1.119   thorpej 	 * grab it the next time it performs a context switch.
   1019      1.119   thorpej 	 *
   1020      1.119   thorpej 	 * This also does not handle the case where its last
   1021      1.119   thorpej 	 * CPU is running a higher-priority process, but every
   1022      1.119   thorpej 	 * other CPU is running a lower-priority process.  There
   1023      1.119   thorpej 	 * are ways to handle this situation, but they're not
   1024      1.119   thorpej 	 * currently very pretty, and we also need to weigh the
   1025      1.119   thorpej 	 * cost of moving a process from one CPU to another.
   1026      1.119   thorpej 	 *
   1027      1.119   thorpej 	 * XXXSMP
   1028      1.119   thorpej 	 * There is also the issue of locking the other CPU's
   1029      1.119   thorpej 	 * sched state, which we currently do not do.
   1030      1.119   thorpej 	 */
   1031      1.122   thorpej 	ci = (l->l_cpu != NULL) ? l->l_cpu : curcpu();
   1032      1.121   thorpej 	if (pri < ci->ci_schedstate.spc_curpriority)
   1033      1.119   thorpej 		need_resched(ci);
   1034      1.119   thorpej }
   1035      1.119   thorpej 
   1036       1.26       cgd /*
   1037       1.26       cgd  * Change process state to be runnable,
   1038       1.26       cgd  * placing it on the run queue if it is in memory,
   1039       1.26       cgd  * and awakening the swapper if it isn't in memory.
   1040       1.26       cgd  */
   1041       1.26       cgd void
   1042      1.122   thorpej setrunnable(struct lwp *l)
   1043       1.26       cgd {
   1044      1.122   thorpej 	struct proc *p = l->l_proc;
   1045       1.26       cgd 
   1046       1.83   thorpej 	SCHED_ASSERT_LOCKED();
   1047       1.83   thorpej 
   1048      1.122   thorpej 	switch (l->l_stat) {
   1049       1.26       cgd 	case 0:
   1050      1.122   thorpej 	case LSRUN:
   1051      1.122   thorpej 	case LSONPROC:
   1052      1.122   thorpej 	case LSZOMB:
   1053      1.122   thorpej 	case LSDEAD:
   1054       1.26       cgd 	default:
   1055      1.127      matt 		panic("setrunnable: lwp %p state was %d", l, l->l_stat);
   1056      1.122   thorpej 	case LSSTOP:
   1057       1.33   mycroft 		/*
   1058       1.33   mycroft 		 * If we're being traced (possibly because someone attached us
   1059       1.33   mycroft 		 * while we were stopped), check for a signal from the debugger.
   1060       1.33   mycroft 		 */
   1061       1.53   mycroft 		if ((p->p_flag & P_TRACED) != 0 && p->p_xstat != 0) {
   1062       1.99  jdolecek 			sigaddset(&p->p_sigctx.ps_siglist, p->p_xstat);
   1063      1.101   thorpej 			CHECKSIGS(p);
   1064       1.53   mycroft 		}
   1065      1.122   thorpej 	case LSSLEEP:
   1066      1.122   thorpej 		unsleep(l);		/* e.g. when sending signals */
   1067       1.26       cgd 		break;
   1068       1.26       cgd 
   1069      1.122   thorpej 	case LSIDL:
   1070      1.122   thorpej 		break;
   1071      1.122   thorpej 	case LSSUSPENDED:
   1072       1.26       cgd 		break;
   1073       1.26       cgd 	}
   1074      1.139        cl 
   1075      1.139        cl 	if (l->l_proc->p_sa)
   1076      1.139        cl 		sa_awaken(l);
   1077      1.139        cl 
   1078      1.122   thorpej 	l->l_stat = LSRUN;
   1079      1.122   thorpej 	p->p_nrlwps++;
   1080      1.122   thorpej 
   1081      1.122   thorpej 	if (l->l_flag & L_INMEM)
   1082      1.122   thorpej 		setrunqueue(l);
   1083      1.122   thorpej 
   1084      1.122   thorpej 	if (l->l_slptime > 1)
   1085      1.122   thorpej 		updatepri(l);
   1086      1.122   thorpej 	l->l_slptime = 0;
   1087      1.122   thorpej 	if ((l->l_flag & L_INMEM) == 0)
   1088       1.83   thorpej 		sched_wakeup((caddr_t)&proc0);
   1089      1.119   thorpej 	else
   1090      1.122   thorpej 		resched_proc(l, l->l_priority);
   1091       1.26       cgd }
   1092       1.26       cgd 
   1093       1.26       cgd /*
   1094       1.26       cgd  * Compute the priority of a process when running in user mode.
   1095       1.26       cgd  * Arrange to reschedule if the resulting priority is better
   1096       1.26       cgd  * than that of the current process.
   1097       1.26       cgd  */
   1098       1.26       cgd void
   1099      1.122   thorpej resetpriority(struct lwp *l)
   1100       1.26       cgd {
   1101       1.71  augustss 	unsigned int newpriority;
   1102      1.122   thorpej 	struct proc *p = l->l_proc;
   1103       1.26       cgd 
   1104       1.83   thorpej 	SCHED_ASSERT_LOCKED();
   1105       1.83   thorpej 
   1106      1.130   nathanw 	newpriority = PUSER + p->p_estcpu +
   1107      1.122   thorpej 			NICE_WEIGHT * (p->p_nice - NZERO);
   1108       1.26       cgd 	newpriority = min(newpriority, MAXPRI);
   1109      1.122   thorpej 	l->l_usrpri = newpriority;
   1110      1.122   thorpej 	resched_proc(l, l->l_usrpri);
   1111      1.122   thorpej }
   1112      1.122   thorpej 
   1113      1.130   nathanw /*
   1114      1.122   thorpej  * Recompute priority for all LWPs in a process.
   1115      1.122   thorpej  */
   1116      1.122   thorpej void
   1117      1.122   thorpej resetprocpriority(struct proc *p)
   1118      1.122   thorpej {
   1119      1.122   thorpej 	struct lwp *l;
   1120      1.122   thorpej 
   1121      1.122   thorpej 	LIST_FOREACH(l, &p->p_lwps, l_sibling)
   1122      1.122   thorpej 	    resetpriority(l);
   1123       1.55      ross }
   1124       1.55      ross 
   1125       1.55      ross /*
   1126       1.56      ross  * We adjust the priority of the current process.  The priority of a process
   1127      1.141       wiz  * gets worse as it accumulates CPU time.  The CPU usage estimator (p_estcpu)
   1128       1.56      ross  * is increased here.  The formula for computing priorities (in kern_synch.c)
   1129       1.56      ross  * will compute a different value each time p_estcpu increases. This can
   1130       1.56      ross  * cause a switch, but unless the priority crosses a PPQ boundary the actual
   1131      1.141       wiz  * queue will not change.  The CPU usage estimator ramps up quite quickly
   1132       1.56      ross  * when the process is running (linearly), and decays away exponentially, at
   1133       1.56      ross  * a rate which is proportionally slower when the system is busy.  The basic
   1134       1.80   nathanw  * principle is that the system will 90% forget that the process used a lot
   1135       1.56      ross  * of CPU time in 5 * loadav seconds.  This causes the system to favor
   1136       1.56      ross  * processes which haven't run much recently, and to round-robin among other
   1137       1.56      ross  * processes.
   1138       1.55      ross  */
   1139       1.55      ross 
   1140       1.55      ross void
   1141      1.122   thorpej schedclock(struct lwp *l)
   1142       1.55      ross {
   1143      1.122   thorpej 	struct proc *p = l->l_proc;
   1144       1.83   thorpej 	int s;
   1145       1.77   thorpej 
   1146       1.55      ross 	p->p_estcpu = ESTCPULIM(p->p_estcpu + 1);
   1147       1.83   thorpej 	SCHED_LOCK(s);
   1148      1.122   thorpej 	resetpriority(l);
   1149       1.83   thorpej 	SCHED_UNLOCK(s);
   1150      1.130   nathanw 
   1151      1.122   thorpej 	if (l->l_priority >= PUSER)
   1152      1.122   thorpej 		l->l_priority = l->l_usrpri;
   1153       1.26       cgd }
   1154       1.94    bouyer 
   1155       1.94    bouyer void
   1156       1.94    bouyer suspendsched()
   1157       1.94    bouyer {
   1158      1.122   thorpej 	struct lwp *l;
   1159       1.97     enami 	int s;
   1160       1.94    bouyer 
   1161       1.94    bouyer 	/*
   1162      1.130   nathanw 	 * Convert all non-P_SYSTEM LSSLEEP or LSRUN processes to
   1163      1.122   thorpej 	 * LSSUSPENDED.
   1164       1.94    bouyer 	 */
   1165       1.95   thorpej 	proclist_lock_read();
   1166       1.95   thorpej 	SCHED_LOCK(s);
   1167      1.122   thorpej 	LIST_FOREACH(l, &alllwp, l_list) {
   1168      1.122   thorpej 		if ((l->l_proc->p_flag & P_SYSTEM) != 0)
   1169       1.94    bouyer 			continue;
   1170      1.122   thorpej 
   1171      1.122   thorpej 		switch (l->l_stat) {
   1172      1.122   thorpej 		case LSRUN:
   1173      1.122   thorpej 			l->l_proc->p_nrlwps--;
   1174      1.122   thorpej 			if ((l->l_flag & L_INMEM) != 0)
   1175      1.122   thorpej 				remrunqueue(l);
   1176       1.97     enami 			/* FALLTHROUGH */
   1177      1.122   thorpej 		case LSSLEEP:
   1178      1.122   thorpej 			l->l_stat = LSSUSPENDED;
   1179       1.97     enami 			break;
   1180      1.122   thorpej 		case LSONPROC:
   1181       1.97     enami 			/*
   1182       1.97     enami 			 * XXX SMP: we need to deal with processes on
   1183       1.97     enami 			 * others CPU !
   1184       1.97     enami 			 */
   1185       1.97     enami 			break;
   1186       1.97     enami 		default:
   1187       1.97     enami 			break;
   1188       1.94    bouyer 		}
   1189       1.94    bouyer 	}
   1190       1.94    bouyer 	SCHED_UNLOCK(s);
   1191       1.97     enami 	proclist_unlock_read();
   1192       1.94    bouyer }
   1193      1.113  gmcgarry 
   1194      1.113  gmcgarry /*
   1195      1.113  gmcgarry  * Low-level routines to access the run queue.  Optimised assembler
   1196      1.113  gmcgarry  * routines can override these.
   1197      1.113  gmcgarry  */
   1198      1.113  gmcgarry 
   1199      1.113  gmcgarry #ifndef __HAVE_MD_RUNQUEUE
   1200      1.115  nisimura 
   1201      1.130   nathanw /*
   1202      1.134      matt  * On some architectures, it's faster to use a MSB ordering for the priorites
   1203      1.134      matt  * than the traditional LSB ordering.
   1204      1.134      matt  */
   1205      1.134      matt #ifdef __HAVE_BIGENDIAN_BITOPS
   1206      1.134      matt #define	RQMASK(n) (0x80000000 >> (n))
   1207      1.134      matt #else
   1208      1.134      matt #define	RQMASK(n) (0x00000001 << (n))
   1209      1.134      matt #endif
   1210      1.134      matt 
   1211      1.134      matt /*
   1212      1.115  nisimura  * The primitives that manipulate the run queues.  whichqs tells which
   1213      1.115  nisimura  * of the 32 queues qs have processes in them.  Setrunqueue puts processes
   1214      1.115  nisimura  * into queues, remrunqueue removes them from queues.  The running process is
   1215      1.115  nisimura  * on no queue, other processes are on a queue related to p->p_priority,
   1216      1.115  nisimura  * divided by 4 actually to shrink the 0-127 range of priorities into the 32
   1217      1.115  nisimura  * available queues.
   1218      1.130   nathanw  */
   1219      1.113  gmcgarry 
   1220      1.146      matt #ifdef RQDEBUG
   1221      1.146      matt static void
   1222      1.146      matt checkrunqueue(int whichq, struct lwp *l)
   1223      1.146      matt {
   1224      1.146      matt 	const struct prochd * const rq = &sched_qs[whichq];
   1225      1.146      matt 	struct lwp *l2;
   1226      1.146      matt 	int found = 0;
   1227      1.146      matt 	int die = 0;
   1228      1.146      matt 	int empty = 1;
   1229      1.146      matt 	for (l2 = rq->ph_link; l2 != (void*) rq; l2 = l2->l_forw) {
   1230      1.146      matt 		if (l2->l_stat != LSRUN) {
   1231      1.146      matt 			printf("checkrunqueue[%d]: lwp %p state (%d) "
   1232      1.146      matt 			    " != LSRUN\n", whichq, l2, l2->l_stat);
   1233      1.146      matt 		}
   1234      1.146      matt 		if (l2->l_back->l_forw != l2) {
   1235      1.146      matt 			printf("checkrunqueue[%d]: lwp %p back-qptr (%p) "
   1236      1.146      matt 			    "corrupt %p\n", whichq, l2, l2->l_back,
   1237      1.146      matt 			    l2->l_back->l_forw);
   1238      1.146      matt 			die = 1;
   1239      1.146      matt 		}
   1240      1.146      matt 		if (l2->l_forw->l_back != l2) {
   1241      1.146      matt 			printf("checkrunqueue[%d]: lwp %p forw-qptr (%p) "
   1242      1.146      matt 			    "corrupt %p\n", whichq, l2, l2->l_forw,
   1243      1.146      matt 			    l2->l_forw->l_back);
   1244      1.146      matt 			die = 1;
   1245      1.146      matt 		}
   1246      1.146      matt 		if (l2 == l)
   1247      1.146      matt 			found = 1;
   1248      1.146      matt 		empty = 0;
   1249      1.146      matt 	}
   1250      1.146      matt 	if (empty && (sched_whichqs & RQMASK(whichq)) != 0) {
   1251      1.146      matt 		printf("checkrunqueue[%d]: bit set for empty run-queue %p\n",
   1252      1.146      matt 		    whichq, rq);
   1253      1.146      matt 		die = 1;
   1254      1.146      matt 	} else if (!empty && (sched_whichqs & RQMASK(whichq)) == 0) {
   1255      1.146      matt 		printf("checkrunqueue[%d]: bit clear for non-empty "
   1256      1.146      matt 		    "run-queue %p\n", whichq, rq);
   1257      1.146      matt 		die = 1;
   1258      1.146      matt 	}
   1259      1.146      matt 	if (l != NULL && (sched_whichqs & RQMASK(whichq)) == 0) {
   1260      1.146      matt 		printf("checkrunqueue[%d]: bit clear for active lwp %p\n",
   1261      1.146      matt 		    whichq, l);
   1262      1.146      matt 		die = 1;
   1263      1.146      matt 	}
   1264      1.146      matt 	if (l != NULL && empty) {
   1265      1.146      matt 		printf("checkrunqueue[%d]: empty run-queue %p with "
   1266      1.146      matt 		    "active lwp %p\n", whichq, rq, l);
   1267      1.146      matt 		die = 1;
   1268      1.146      matt 	}
   1269      1.146      matt 	if (l != NULL && !found) {
   1270      1.146      matt 		printf("checkrunqueue[%d]: lwp %p not in runqueue %p!",
   1271      1.146      matt 		    whichq, l, rq);
   1272      1.146      matt 		die = 1;
   1273      1.146      matt 	}
   1274      1.146      matt 	if (die)
   1275      1.146      matt 		panic("checkrunqueue: inconsistency found");
   1276      1.146      matt }
   1277      1.146      matt #endif /* RQDEBUG */
   1278      1.146      matt 
   1279      1.113  gmcgarry void
   1280      1.122   thorpej setrunqueue(struct lwp *l)
   1281      1.113  gmcgarry {
   1282      1.113  gmcgarry 	struct prochd *rq;
   1283      1.122   thorpej 	struct lwp *prev;
   1284      1.134      matt 	const int whichq = l->l_priority / 4;
   1285      1.113  gmcgarry 
   1286      1.146      matt #ifdef RQDEBUG
   1287      1.146      matt 	checkrunqueue(whichq, NULL);
   1288      1.146      matt #endif
   1289      1.113  gmcgarry #ifdef DIAGNOSTIC
   1290      1.122   thorpej 	if (l->l_back != NULL || l->l_wchan != NULL || l->l_stat != LSRUN)
   1291      1.113  gmcgarry 		panic("setrunqueue");
   1292      1.113  gmcgarry #endif
   1293      1.134      matt 	sched_whichqs |= RQMASK(whichq);
   1294      1.113  gmcgarry 	rq = &sched_qs[whichq];
   1295      1.113  gmcgarry 	prev = rq->ph_rlink;
   1296      1.122   thorpej 	l->l_forw = (struct lwp *)rq;
   1297      1.122   thorpej 	rq->ph_rlink = l;
   1298      1.122   thorpej 	prev->l_forw = l;
   1299      1.122   thorpej 	l->l_back = prev;
   1300      1.146      matt #ifdef RQDEBUG
   1301      1.146      matt 	checkrunqueue(whichq, l);
   1302      1.146      matt #endif
   1303      1.113  gmcgarry }
   1304      1.113  gmcgarry 
   1305      1.113  gmcgarry void
   1306      1.122   thorpej remrunqueue(struct lwp *l)
   1307      1.113  gmcgarry {
   1308      1.122   thorpej 	struct lwp *prev, *next;
   1309      1.134      matt 	const int whichq = l->l_priority / 4;
   1310      1.146      matt #ifdef RQDEBUG
   1311      1.146      matt 	checkrunqueue(whichq, l);
   1312      1.146      matt #endif
   1313      1.113  gmcgarry #ifdef DIAGNOSTIC
   1314      1.134      matt 	if (((sched_whichqs & RQMASK(whichq)) == 0))
   1315      1.146      matt 		panic("remrunqueue: bit %d not set", whichq);
   1316      1.113  gmcgarry #endif
   1317      1.122   thorpej 	prev = l->l_back;
   1318      1.122   thorpej 	l->l_back = NULL;
   1319      1.122   thorpej 	next = l->l_forw;
   1320      1.122   thorpej 	prev->l_forw = next;
   1321      1.122   thorpej 	next->l_back = prev;
   1322      1.113  gmcgarry 	if (prev == next)
   1323      1.134      matt 		sched_whichqs &= ~RQMASK(whichq);
   1324      1.146      matt #ifdef RQDEBUG
   1325      1.146      matt 	checkrunqueue(whichq, NULL);
   1326      1.146      matt #endif
   1327      1.113  gmcgarry }
   1328      1.113  gmcgarry 
   1329      1.134      matt #undef RQMASK
   1330      1.134      matt #endif /* !defined(__HAVE_MD_RUNQUEUE) */
   1331