sys/kern/kern_synch.c

   1 /*-
   2  * Copyright (c) 1982, 1986, 1990, 1991, 1993
   3  *      The Regents of the University of California.  All rights reserved.
   4  * (c) UNIX System Laboratories, Inc.
   5  * All or some portions of this file are derived from material licensed
   6  * to the University of California by American Telephone and Telegraph
   7  * Co. or Unix System Laboratories, Inc. and are reproduced herein with
   8  * the permission of UNIX System Laboratories, Inc.
   9  *
  10  * Redistribution and use in source and binary forms, with or without
  11  * modification, are permitted provided that the following conditions
  12  * are met:
  13  * 1. Redistributions of source code must retain the above copyright
  14  *    notice, this list of conditions and the following disclaimer.
  15  * 2. Redistributions in binary form must reproduce the above copyright
  16  *    notice, this list of conditions and the following disclaimer in the
  17  *    documentation and/or other materials provided with the distribution.
  18  * 3. All advertising materials mentioning features or use of this software
  19  *    must display the following acknowledgement:
  20  *      This product includes software developed by the University of
  21  *      California, Berkeley and its contributors.
  22  * 4. Neither the name of the University nor the names of its contributors
  23  *    may be used to endorse or promote products derived from this software
  24  *    without specific prior written permission.
  25  *
  26  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  27  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  28  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  29  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  30  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  31  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  32  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  33  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  34  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  35  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  36  * SUCH DAMAGE.
  37  *
  38  *      @(#)kern_synch.c        8.9 (Berkeley) 5/19/95
  39  * $FreeBSD: src/sys/kern/kern_synch.c,v 1.87.2.6 2002/10/13 07:29:53 kbyanc Exp $
  40  * $DragonFly: src/sys/kern/kern_synch.c,v 1.14 2003/07/03 17:24:02 dillon Exp $
  41  */
  42
  43 #include "opt_ktrace.h"
  44
  45 #include <sys/param.h>
  46 #include <sys/systm.h>
  47 #include <sys/proc.h>
  48 #include <sys/kernel.h>
  49 #include <sys/signalvar.h>
  50 #include <sys/resourcevar.h>
  51 #include <sys/vmmeter.h>
  52 #include <sys/sysctl.h>
  53 #include <sys/thread2.h>
  54 #ifdef KTRACE
  55 #include <sys/uio.h>
  56 #include <sys/ktrace.h>
  57 #endif
  58 #include <sys/xwait.h>
  59
  60 #include <machine/cpu.h>
  61 #include <machine/ipl.h>
  62 #include <machine/smp.h>
  63
  64 static void sched_setup __P((void *dummy));
  65 SYSINIT(sched_setup, SI_SUB_KICK_SCHEDULER, SI_ORDER_FIRST, sched_setup, NULL)
  66
  67 int     hogticks;
  68 int     lbolt;
  69 int     sched_quantum;          /* Roundrobin scheduling quantum in ticks. */
  70 int     ncpus;
  71
  72 static struct callout loadav_callout;
  73
  74 struct loadavg averunnable =
  75         { {0, 0, 0}, FSCALE };  /* load average, of runnable procs */
  76 /*
  77  * Constants for averages over 1, 5, and 15 minutes
  78  * when sampling at 5 second intervals.
  79  */
  80 static fixpt_t cexp[3] = {
  81         0.9200444146293232 * FSCALE,    /* exp(-1/12) */
  82         0.9834714538216174 * FSCALE,    /* exp(-1/60) */
  83         0.9944598480048967 * FSCALE,    /* exp(-1/180) */
  84 };
  85
  86 static void     endtsleep __P((void *));
  87 static void     loadav __P((void *arg));
  88 static void     maybe_resched __P((struct proc *chk));
  89 static void     roundrobin __P((void *arg));
  90 static void     schedcpu __P((void *arg));
  91 static void     updatepri __P((struct proc *p));
  92
  93 static int
  94 sysctl_kern_quantum(SYSCTL_HANDLER_ARGS)
  95 {
  96         int error, new_val;
  97
  98         new_val = sched_quantum * tick;
  99         error = sysctl_handle_int(oidp, &new_val, 0, req);
 100         if (error != 0 || req->newptr == NULL)
 101                 return (error);
 102         if (new_val < tick)
 103                 return (EINVAL);
 104         sched_quantum = new_val / tick;
 105         hogticks = 2 * sched_quantum;
 106         return (0);
 107 }
 108
 109 SYSCTL_PROC(_kern, OID_AUTO, quantum, CTLTYPE_INT|CTLFLAG_RW,
 110         0, sizeof sched_quantum, sysctl_kern_quantum, "I", "");
 111
 112 /*
 113  * Arrange to reschedule if necessary by checking to see if the current
 114  * process is on the highest priority user scheduling queue.  This may
 115  * be run from an interrupt so we have to follow any preemption chains
 116  * back to the original process.
 117  */
 118 static void
 119 maybe_resched(struct proc *chk)
 120 {
 121         struct proc *cur = lwkt_preempted_proc();
 122
 123         if (cur == NULL)
 124                 return;
 125
 126         /*
 127          * Check the user queue (realtime, normal, idle).  Lower numbers
 128          * indicate higher priority queues.  Lower numbers are also better
 129          * for p_priority.
 130          */
 131         if (chk->p_rtprio.type < cur->p_rtprio.type) {
 132                 need_resched();
 133         } else if (chk->p_rtprio.type == cur->p_rtprio.type) {
 134                 if (chk->p_rtprio.type == RTP_PRIO_NORMAL) {
 135                         if (chk->p_priority / PPQ < cur->p_priority / PPQ)
 136                                 need_resched();
 137                 } else {
 138                         if (chk->p_rtprio.prio < cur->p_rtprio.prio)
 139                                 need_resched();
 140                 }
 141         }
 142 }
 143
 144 int
 145 roundrobin_interval(void)
 146 {
 147         return (sched_quantum);
 148 }
 149
 150 /*
 151  * Force switch among equal priority processes every 100ms.
 152  */
 153 /* ARGSUSED */
 154 static void
 155 roundrobin(arg)
 156         void *arg;
 157 {
 158 #ifndef SMP
 159         struct proc *p = curproc; /* XXX */
 160 #endif
 161
 162 #ifdef SMP
 163         need_resched();
 164         forward_roundrobin();
 165 #else
 166         if (p == 0 || RTP_PRIO_NEED_RR(p->p_rtprio.type))
 167                 need_resched();
 168 #endif
 169
 170         timeout(roundrobin, NULL, sched_quantum);
 171 }
 172
 173 /*
 174  * Constants for digital decay and forget:
 175  *      90% of (p_estcpu) usage in 5 * loadav time
 176  *      95% of (p_pctcpu) usage in 60 seconds (load insensitive)
 177  *          Note that, as ps(1) mentions, this can let percentages
 178  *          total over 100% (I've seen 137.9% for 3 processes).
 179  *
 180  * Note that schedclock() updates p_estcpu and p_cpticks asynchronously.
 181  *
 182  * We wish to decay away 90% of p_estcpu in (5 * loadavg) seconds.
 183  * That is, the system wants to compute a value of decay such
 184  * that the following for loop:
 185  *      for (i = 0; i < (5 * loadavg); i++)
 186  *              p_estcpu *= decay;
 187  * will compute
 188  *      p_estcpu *= 0.1;
 189  * for all values of loadavg:
 190  *
 191  * Mathematically this loop can be expressed by saying:
 192  *      decay ** (5 * loadavg) ~= .1
 193  *
 194  * The system computes decay as:
 195  *      decay = (2 * loadavg) / (2 * loadavg + 1)
 196  *
 197  * We wish to prove that the system's computation of decay
 198  * will always fulfill the equation:
 199  *      decay ** (5 * loadavg) ~= .1
 200  *
 201  * If we compute b as:
 202  *      b = 2 * loadavg
 203  * then
 204  *      decay = b / (b + 1)
 205  *
 206  * We now need to prove two things:
 207  *      1) Given factor ** (5 * loadavg) ~= .1, prove factor == b/(b+1)
 208  *      2) Given b/(b+1) ** power ~= .1, prove power == (5 * loadavg)
 209  *
 210  * Facts:
 211  *         For x close to zero, exp(x) =~ 1 + x, since
 212  *              exp(x) = 0! + x**1/1! + x**2/2! + ... .
 213  *              therefore exp(-1/b) =~ 1 - (1/b) = (b-1)/b.
 214  *         For x close to zero, ln(1+x) =~ x, since
 215  *              ln(1+x) = x - x**2/2 + x**3/3 - ...     -1 < x < 1
 216  *              therefore ln(b/(b+1)) = ln(1 - 1/(b+1)) =~ -1/(b+1).
 217  *         ln(.1) =~ -2.30
 218  *
 219  * Proof of (1):
 220  *    Solve (factor)**(power) =~ .1 given power (5*loadav):
 221  *      solving for factor,
 222  *      ln(factor) =~ (-2.30/5*loadav), or
 223  *      factor =~ exp(-1/((5/2.30)*loadav)) =~ exp(-1/(2*loadav)) =
 224  *          exp(-1/b) =~ (b-1)/b =~ b/(b+1).                    QED
 225  *
 226  * Proof of (2):
 227  *    Solve (factor)**(power) =~ .1 given factor == (b/(b+1)):
 228  *      solving for power,
 229  *      power*ln(b/(b+1)) =~ -2.30, or
 230  *      power =~ 2.3 * (b + 1) = 4.6*loadav + 2.3 =~ 5*loadav.  QED
 231  *
 232  * Actual power values for the implemented algorithm are as follows:
 233  *      loadav: 1       2       3       4
 234  *      power:  5.68    10.32   14.94   19.55
 235  */
 236
 237 /* calculations for digital decay to forget 90% of usage in 5*loadav sec */
 238 #define loadfactor(loadav)      (2 * (loadav))
 239 #define decay_cpu(loadfac, cpu) (((loadfac) * (cpu)) / ((loadfac) + FSCALE))
 240
 241 /* decay 95% of `p_pctcpu' in 60 seconds; see CCPU_SHIFT before changing */
 242 static fixpt_t  ccpu = 0.95122942450071400909 * FSCALE; /* exp(-1/20) */
 243 SYSCTL_INT(_kern, OID_AUTO, ccpu, CTLFLAG_RD, &ccpu, 0, "");
 244
 245 /* kernel uses `FSCALE', userland (SHOULD) use kern.fscale */
 246 static int      fscale __unused = FSCALE;
 247 SYSCTL_INT(_kern, OID_AUTO, fscale, CTLFLAG_RD, 0, FSCALE, "");
 248
 249 /*
 250  * If `ccpu' is not equal to `exp(-1/20)' and you still want to use the
 251  * faster/more-accurate formula, you'll have to estimate CCPU_SHIFT below
 252  * and possibly adjust FSHIFT in "param.h" so that (FSHIFT >= CCPU_SHIFT).
 253  *
 254  * To estimate CCPU_SHIFT for exp(-1/20), the following formula was used:
 255  *      1 - exp(-1/20) ~= 0.0487 ~= 0.0488 == 1 (fixed pt, *11* bits).
 256  *
 257  * If you don't want to bother with the faster/more-accurate formula, you
 258  * can set CCPU_SHIFT to (FSHIFT + 1) which will use a slower/less-accurate
 259  * (more general) method of calculating the %age of CPU used by a process.
 260  */
 261 #define CCPU_SHIFT      11
 262
 263 /*
 264  * Recompute process priorities, every hz ticks.
 265  */
 266 /* ARGSUSED */
 267 static void
 268 schedcpu(void *arg)
 269 {
 270         fixpt_t loadfac = loadfactor(averunnable.ldavg[0]);
 271         struct proc *p;
 272         struct proc *curp;
 273         int realstathz, s;
 274
 275         curp = lwkt_preempted_proc(); /* YYY temporary hack */
 276
 277         realstathz = stathz ? stathz : hz;
 278         LIST_FOREACH(p, &allproc, p_list) {
 279                 /*
 280                  * Increment time in/out of memory and sleep time
 281                  * (if sleeping).  We ignore overflow; with 16-bit int's
 282                  * (remember them?) overflow takes 45 days.
 283                  */
 284                 p->p_swtime++;
 285                 if (p->p_stat == SSLEEP || p->p_stat == SSTOP)
 286                         p->p_slptime++;
 287                 p->p_pctcpu = (p->p_pctcpu * ccpu) >> FSHIFT;
 288                 /*
 289                  * If the process has slept the entire second,
 290                  * stop recalculating its priority until it wakes up.
 291                  */
 292                 if (p->p_slptime > 1)
 293                         continue;
 294                 s = splhigh();  /* prevent state changes and protect run queue */
 295                 /*
 296                  * p_pctcpu is only for ps.
 297                  */
 298 #if     (FSHIFT >= CCPU_SHIFT)
 299                 p->p_pctcpu += (realstathz == 100)?
 300                         ((fixpt_t) p->p_cpticks) << (FSHIFT - CCPU_SHIFT):
 301                         100 * (((fixpt_t) p->p_cpticks)
 302                                 << (FSHIFT - CCPU_SHIFT)) / realstathz;
 303 #else
 304                 p->p_pctcpu += ((FSCALE - ccpu) *
 305                         (p->p_cpticks * FSCALE / realstathz)) >> FSHIFT;
 306 #endif
 307                 p->p_cpticks = 0;
 308                 p->p_estcpu = decay_cpu(loadfac, p->p_estcpu);
 309                 resetpriority(p);
 310                 splx(s);
 311         }
 312         wakeup((caddr_t)&lbolt);
 313         timeout(schedcpu, (void *)0, hz);
 314 }
 315
 316 /*
 317  * Recalculate the priority of a process after it has slept for a while.
 318  * For all load averages >= 1 and max p_estcpu of 255, sleeping for at
 319  * least six times the loadfactor will decay p_estcpu to zero.
 320  */
 321 static void
 322 updatepri(struct proc *p)
 323 {
 324         unsigned int newcpu = p->p_estcpu;
 325         fixpt_t loadfac = loadfactor(averunnable.ldavg[0]);
 326
 327         if (p->p_slptime > 5 * loadfac) {
 328                 p->p_estcpu = 0;
 329         } else {
 330                 p->p_slptime--; /* the first time was done in schedcpu */
 331                 while (newcpu && --p->p_slptime)
 332                         newcpu = decay_cpu(loadfac, newcpu);
 333                 p->p_estcpu = newcpu;
 334         }
 335         resetpriority(p);
 336 }
 337
 338 /*
 339  * We're only looking at 7 bits of the address; everything is
 340  * aligned to 4, lots of things are aligned to greater powers
 341  * of 2.  Shift right by 8, i.e. drop the bottom 256 worth.
 342  */
 343 #define TABLESIZE       128
 344 static TAILQ_HEAD(slpquehead, thread) slpque[TABLESIZE];
 345 #define LOOKUP(x)       (((intptr_t)(x) >> 8) & (TABLESIZE - 1))
 346
 347 /*
 348  * During autoconfiguration or after a panic, a sleep will simply
 349  * lower the priority briefly to allow interrupts, then return.
 350  * The priority to be used (safepri) is machine-dependent, thus this
 351  * value is initialized and maintained in the machine-dependent layers.
 352  * This priority will typically be 0, or the lowest priority
 353  * that is safe for use on the interrupt stack; it can be made
 354  * higher to block network software interrupts after panics.
 355  */
 356 int safepri;
 357
 358 void
 359 sleepinit(void)
 360 {
 361         int i;
 362
 363         sched_quantum = hz/10;
 364         hogticks = 2 * sched_quantum;
 365         for (i = 0; i < TABLESIZE; i++)
 366                 TAILQ_INIT(&slpque[i]);
 367 }
 368
 369 /*
 370  * General sleep call.  Suspends the current process until a wakeup is
 371  * performed on the specified identifier.  The process will then be made
 372  * runnable with the specified priority.  Sleeps at most timo/hz seconds
 373  * (0 means no timeout).  If pri includes PCATCH flag, signals are checked
 374  * before and after sleeping, else signals are not checked.  Returns 0 if
 375  * awakened, EWOULDBLOCK if the timeout expires.  If PCATCH is set and a
 376  * signal needs to be delivered, ERESTART is returned if the current system
 377  * call should be restarted if possible, and EINTR is returned if the system
 378  * call should be interrupted by the signal (return EINTR).
 379  *
 380  * If the process has P_CURPROC set mi_switch() will not re-queue it to
 381  * the userland scheduler queues because we are in a SSLEEP state.  If
 382  * we are not the current process then we have to remove ourselves from
 383  * the scheduler queues.
 384  *
 385  * YYY priority now unused
 386  */
 387 int
 388 tsleep(ident, priority, wmesg, timo)
 389         void *ident;
 390         int priority, timo;
 391         const char *wmesg;
 392 {
 393         struct thread *td = curthread;
 394         struct proc *p = td->td_proc;           /* may be NULL */
 395         int s, sig = 0, catch = priority & PCATCH;
 396         int id = LOOKUP(ident);
 397         struct callout_handle thandle;
 398
 399         /*
 400          * NOTE: removed KTRPOINT, it could cause races due to blocking
 401          * even in stable.  Just scrap it for now.
 402          */
 403         s = splhigh();
 404
 405         if (cold || panicstr) {
 406                 /*
 407                  * After a panic, or during autoconfiguration,
 408                  * just give interrupts a chance, then just return;
 409                  * don't run any other procs or panic below,
 410                  * in case this is the idle process and already asleep.
 411                  */
 412                 splx(safepri);
 413                 splx(s);
 414                 return (0);
 415         }
 416         KASSERT(ident != NULL, ("tsleep: no ident"));
 417         KASSERT(p == NULL || p->p_stat == SRUN, ("tsleep %p %s %d",
 418                 ident, wmesg, p->p_stat));
 419
 420         crit_enter();
 421         td->td_wchan = ident;
 422         td->td_wmesg = wmesg;
 423         if (p)
 424                 p->p_slptime = 0;
 425         lwkt_deschedule_self();
 426         TAILQ_INSERT_TAIL(&slpque[id], td, td_threadq);
 427         if (timo)
 428                 thandle = timeout(endtsleep, (void *)td, timo);
 429         /*
 430          * We put ourselves on the sleep queue and start our timeout
 431          * before calling CURSIG, as we could stop there, and a wakeup
 432          * or a SIGCONT (or both) could occur while we were stopped.
 433          * A SIGCONT would cause us to be marked as SSLEEP
 434          * without resuming us, thus we must be ready for sleep
 435          * when CURSIG is called.  If the wakeup happens while we're
 436          * stopped, p->p_wchan will be 0 upon return from CURSIG.
 437          */
 438         if (p) {
 439                 if (catch) {
 440                         p->p_flag |= P_SINTR;
 441                         if ((sig = CURSIG(p))) {
 442                                 if (td->td_wchan) {
 443                                         unsleep(td);
 444                                         lwkt_schedule_self();
 445                                 }
 446                                 p->p_stat = SRUN;
 447                                 goto resume;
 448                         }
 449                         if (p->p_wchan == NULL) {
 450                                 catch = 0;
 451                                 goto resume;
 452                         }
 453                 } else {
 454                         sig = 0;
 455                 }
 456
 457                 /*
 458                  * If we are not the current process we have to remove ourself
 459                  * from the run queue.
 460                  */
 461                 KASSERT(p->p_stat == SRUN, ("PSTAT NOT SRUN %d %d", p->p_pid, p->p_stat));
 462                 /*
 463                  * If this is the current 'user' process schedule another one.
 464                  */
 465                 clrrunnable(p, SSLEEP);
 466                 p->p_stats->p_ru.ru_nvcsw++;
 467                 mi_switch();
 468                 KASSERT(p->p_stat == SRUN, ("tsleep: stat not srun"));
 469         } else {
 470                 lwkt_switch();
 471         }
 472 resume:
 473         crit_exit();
 474         if (p)
 475                 p->p_flag &= ~P_SINTR;
 476         splx(s);
 477         if (td->td_flags & TDF_TIMEOUT) {
 478                 td->td_flags &= ~TDF_TIMEOUT;
 479                 if (sig == 0)
 480                         return (EWOULDBLOCK);
 481         } else if (timo) {
 482                 untimeout(endtsleep, (void *)td, thandle);
 483         }
 484         if (p) {
 485                 if (catch && (sig != 0 || (sig = CURSIG(p)))) {
 486                         if (SIGISMEMBER(p->p_sigacts->ps_sigintr, sig))
 487                                 return (EINTR);
 488                         return (ERESTART);
 489                 }
 490         }
 491         return (0);
 492 }
 493
 494 #if 0
 495
 496 /*
 497  * General sleep call.  Suspends the current process until a wakeup is
 498  * performed on the specified xwait structure.  The process will then be made
 499  * runnable with the specified priority.  Sleeps at most timo/hz seconds
 500  * (0 means no timeout).  If pri includes PCATCH flag, signals are checked
 501  * before and after sleeping, else signals are not checked.  Returns 0 if
 502  * awakened, EWOULDBLOCK if the timeout expires.  If PCATCH is set and a
 503  * signal needs to be delivered, ERESTART is returned if the current system
 504  * call should be restarted if possible, and EINTR is returned if the system
 505  * call should be interrupted by the signal (return EINTR).
 506  *
 507  * If the passed generation number is different from the generation number
 508  * in the xwait, return immediately.
 509  */
 510 int
 511 xsleep(struct xwait *w, int priority, const char *wmesg, int timo, int *gen)
 512 {
 513         struct thread *td = curthread;
 514         struct proc *p = td->td_proc;
 515         int s, sig, catch = priority & PCATCH;
 516         struct callout_handle thandle;
 517
 518 #ifdef KTRACE
 519         if (KTRPOINT(td, KTR_CSW))
 520                 ktrcsw(p->p_tracep, 1, 0);
 521 #endif
 522         s = splhigh();
 523
 524         if (cold || panicstr) {
 525                 /*
 526                  * After a panic, or during autoconfiguration,
 527                  * just give interrupts a chance, then just return;
 528                  * don't run any other procs or panic below,
 529                  * in case this is the idle process and already asleep.
 530                  */
 531                 splx(safepri);
 532                 splx(s);
 533                 return (0);
 534         }
 535         KASSERT(p != NULL, ("xsleep1"));
 536         KASSERT(w != NULL && p->p_stat == SRUN, ("xsleep"));
 537
 538         /*
 539          * If the generation number does not match we return immediately.
 540          */
 541         if (*gen != w->gen) {
 542                 *gen = w->gen;
 543                 splx(s);
 544 #ifdef KTRACE
 545                 if (KTRPOINT(td, KTR_CSW))
 546                         ktrcsw(p->p_tracep, 0, 0);
 547 #endif
 548                 return(0);
 549         }
 550
 551         p->p_wchan = w;
 552         p->p_wmesg = wmesg;
 553         p->p_slptime = 0;
 554         p->p_flag |= P_XSLEEP;
 555         TAILQ_INSERT_TAIL(&w->waitq, p, p_procq);
 556         if (timo)
 557                 thandle = timeout(endtsleep, (void *)p, timo);
 558         /*
 559          * We put ourselves on the sleep queue and start our timeout
 560          * before calling CURSIG, as we could stop there, and a wakeup
 561          * or a SIGCONT (or both) could occur while we were stopped.
 562          * A SIGCONT would cause us to be marked as SSLEEP
 563          * without resuming us, thus we must be ready for sleep
 564          * when CURSIG is called.  If the wakeup happens while we're
 565          * stopped, p->p_wchan will be 0 upon return from CURSIG.
 566          */
 567         if (catch) {
 568                 p->p_flag |= P_SINTR;
 569                 if ((sig = CURSIG(p))) {
 570                         if (p->p_wchan) {
 571                                 unsleep(p);
 572                                 lwkt_schedule_self();
 573                         }
 574                         p->p_stat = SRUN;
 575                         goto resume;
 576                 }
 577                 if (p->p_wchan == NULL) {
 578                         catch = 0;
 579                         goto resume;
 580                 }
 581         } else {
 582                 sig = 0;
 583         }
 584         clrrunnable(p, SSLEEP);
 585         p->p_stats->p_ru.ru_nvcsw++;
 586         mi_switch();
 587 resume:
 588         *gen = w->gen;  /* update generation number */
 589         splx(s);
 590         p->p_flag &= ~P_SINTR;
 591         if (p->p_flag & P_TIMEOUT) {
 592                 p->p_flag &= ~P_TIMEOUT;
 593                 if (sig == 0) {
 594 #ifdef KTRACE
 595                         if (KTRPOINT(td, KTR_CSW))
 596                                 ktrcsw(p->p_tracep, 0, 0);
 597 #endif
 598                         return (EWOULDBLOCK);
 599                 }
 600         } else if (timo)
 601                 untimeout(endtsleep, (void *)p, thandle);
 602         if (catch && (sig != 0 || (sig = CURSIG(p)))) {
 603 #ifdef KTRACE
 604                 if (KTRPOINT(td, KTR_CSW))
 605                         ktrcsw(p->p_tracep, 0, 0);
 606 #endif
 607                 if (SIGISMEMBER(p->p_sigacts->ps_sigintr, sig))
 608                         return (EINTR);
 609                 return (ERESTART);
 610         }
 611 #ifdef KTRACE
 612         if (KTRPOINT(td, KTR_CSW))
 613                 ktrcsw(p->p_tracep, 0, 0);
 614 #endif
 615         return (0);
 616 }
 617
 618 #endif
 619
 620 /*
 621  * Implement the timeout for tsleep.  We interlock against
 622  * wchan when setting TDF_TIMEOUT.  For processes we remove
 623  * the sleep if the process is stopped rather then sleeping,
 624  * so it remains stopped.
 625  */
 626 static void
 627 endtsleep(void *arg)
 628 {
 629         thread_t td = arg;
 630         struct proc *p;
 631         int s;
 632
 633         s = splhigh();
 634         if (td->td_wchan) {
 635                 td->td_flags |= TDF_TIMEOUT;
 636                 if ((p = td->td_proc) != NULL) {
 637                         if (p->p_stat == SSLEEP)
 638                                 setrunnable(p);
 639                         else
 640                                 unsleep(td);
 641                 } else {
 642                         unsleep(td);
 643                         lwkt_schedule(td);
 644                 }
 645         }
 646         splx(s);
 647 }
 648
 649 /*
 650  * Remove a process from its wait queue
 651  */
 652 void
 653 unsleep(struct thread *td)
 654 {
 655         int s;
 656
 657         s = splhigh();
 658         if (td->td_wchan) {
 659 #if 0
 660                 if (p->p_flag & P_XSLEEP) {
 661                         struct xwait *w = p->p_wchan;
 662                         TAILQ_REMOVE(&w->waitq, p, p_procq);
 663                         p->p_flag &= ~P_XSLEEP;
 664                 } else
 665 #endif
 666                 TAILQ_REMOVE(&slpque[LOOKUP(td->td_wchan)], td, td_threadq);
 667                 td->td_wchan = NULL;
 668         }
 669         splx(s);
 670 }
 671
 672 #if 0
 673 /*
 674  * Make all processes sleeping on the explicit lock structure runnable.
 675  */
 676 void
 677 xwakeup(struct xwait *w)
 678 {
 679         struct proc *p;
 680         int s;
 681
 682         s = splhigh();
 683         ++w->gen;
 684         while ((p = TAILQ_FIRST(&w->waitq)) != NULL) {
 685                 TAILQ_REMOVE(&w->waitq, p, p_procq);
 686                 KASSERT(p->p_wchan == w && (p->p_flag & P_XSLEEP),
 687                     ("xwakeup: wchan mismatch for %p (%p/%p) %08x", p, p->p_wchan, w, p->p_flag & P_XSLEEP));
 688                 p->p_wchan = NULL;
 689                 p->p_flag &= ~P_XSLEEP;
 690                 if (p->p_stat == SSLEEP) {
 691                         /* OPTIMIZED EXPANSION OF setrunnable(p); */
 692                         if (p->p_slptime > 1)
 693                                 updatepri(p);
 694                         p->p_slptime = 0;
 695                         p->p_stat = SRUN;
 696                         if (p->p_flag & P_INMEM) {
 697                                 setrunqueue(p);
 698                                 maybe_resched(p);
 699                         } else {
 700                                 p->p_flag |= P_SWAPINREQ;
 701                                 wakeup((caddr_t)&proc0);
 702                         }
 703                 }
 704         }
 705         splx(s);
 706 }
 707 #endif
 708
 709 /*
 710  * Make all processes sleeping on the specified identifier runnable.
 711  */
 712 static void
 713 _wakeup(void *ident, int count)
 714 {
 715         struct slpquehead *qp;
 716         struct thread *td;
 717         struct thread *ntd;
 718         struct proc *p;
 719         int s;
 720         int id = LOOKUP(ident);
 721
 722         s = splhigh();
 723         qp = &slpque[id];
 724 restart:
 725         for (td = TAILQ_FIRST(qp); td != NULL; td = ntd) {
 726                 ntd = TAILQ_NEXT(td, td_threadq);
 727                 if (td->td_wchan == ident) {
 728                         TAILQ_REMOVE(qp, td, td_threadq);
 729                         td->td_wchan = NULL;
 730                         if ((p = td->td_proc) != NULL && p->p_stat == SSLEEP) {
 731                                 /* OPTIMIZED EXPANSION OF setrunnable(p); */
 732                                 if (p->p_slptime > 1)
 733                                         updatepri(p);
 734                                 p->p_slptime = 0;
 735                                 p->p_stat = SRUN;
 736                                 if (p->p_flag & P_INMEM) {
 737                                         setrunqueue(p);
 738                                         maybe_resched(p);
 739                                 } else {
 740                                         p->p_flag |= P_SWAPINREQ;
 741                                         wakeup((caddr_t)&proc0);
 742                                 }
 743                                 /* END INLINE EXPANSION */
 744                         } else if (p == NULL) {
 745                                 lwkt_schedule(td);
 746                         }
 747                         if (--count == 0)
 748                                 break;
 749                         goto restart;
 750                 }
 751         }
 752         splx(s);
 753 }
 754
 755 void
 756 wakeup(void *ident)
 757 {
 758     _wakeup(ident, 0);
 759 }
 760
 761 void
 762 wakeup_one(void *ident)
 763 {
 764     _wakeup(ident, 1);
 765 }
 766
 767 /*
 768  * Release the P_CURPROC designation on a process in order to allow the
 769  * userland scheduler to schedule another one.  This places a runnable
 770  * process back on the userland scheduler's run queue.
 771  *
 772  * Note that losing P_CURPROC does not effect LWKT scheduling, you can
 773  * still tsleep/wakeup after having lost P_CURPROC, but userret() will
 774  * not return to user mode until it gets it back.
 775  */
 776 static __inline
 777 void
 778 _relscurproc(struct proc *p)
 779 {
 780         struct proc *np;
 781
 782         crit_enter();
 783         if (p->p_flag & P_CURPROC) {
 784                 p->p_flag &= ~P_CURPROC;
 785                 lwkt_deschedule_self();
 786                 if (p->p_stat == SRUN && (p->p_flag & P_INMEM)) {
 787                         setrunqueue(p);
 788                 }
 789                 if ((np = chooseproc()) != NULL) {
 790                         np->p_flag |= P_CURPROC;
 791                         lwkt_schedule(np->p_thread);
 792                 } else {
 793                         KKASSERT(mycpu->gd_uprocscheduled == 1);
 794                         mycpu->gd_uprocscheduled = 0;
 795                 }
 796         }
 797         crit_exit();
 798 }
 799
 800 void
 801 relscurproc(struct proc *p)
 802 {
 803         _relscurproc(p);
 804 }
 805
 806 /*
 807  * The machine independent parts of mi_switch().
 808  * Must be called at splstatclock() or higher.
 809  */
 810 void
 811 mi_switch()
 812 {
 813         struct thread *td = curthread;
 814         struct proc *p = td->td_proc;   /* XXX */
 815         struct rlimit *rlim;
 816         int x;
 817         u_int64_t ttime;
 818
 819         /*
 820          * XXX this spl is almost unnecessary.  It is partly to allow for
 821          * sloppy callers that don't do it (issignal() via CURSIG() is the
 822          * main offender).  It is partly to work around a bug in the i386
 823          * cpu_switch() (the ipl is not preserved).  We ran for years
 824          * without it.  I think there was only a interrupt latency problem.
 825          * The main caller, tsleep(), does an splx() a couple of instructions
 826          * after calling here.  The buggy caller, issignal(), usually calls
 827          * here at spl0() and sometimes returns at splhigh().  The process
 828          * then runs for a little too long at splhigh().  The ipl gets fixed
 829          * when the process returns to user mode (or earlier).
 830          *
 831          * It would probably be better to always call here at spl0(). Callers
 832          * are prepared to give up control to another process, so they must
 833          * be prepared to be interrupted.  The clock stuff here may not
 834          * actually need splstatclock().
 835          */
 836         x = splstatclock();
 837         clear_resched();
 838
 839         /*
 840          * If the process being switched out is the 'current' process then
 841          * we have to lose the P_CURPROC designation and choose a new
 842          * process.  If the process is not being LWKT managed and it is in
 843          * SRUN we have to setrunqueue it.
 844          */
 845         _relscurproc(p);
 846
 847 #ifdef SIMPLELOCK_DEBUG
 848         if (p->p_simple_locks)
 849                 printf("sleep: holding simple lock\n");
 850 #endif
 851
 852         /*
 853          * Check if the process exceeds its cpu resource allocation.
 854          * If over max, kill it.  Time spent in interrupts is not
 855          * included.  YYY 64 bit match is expensive.  Ick.
 856          */
 857         ttime = td->td_sticks + td->td_uticks;
 858         if (p->p_stat != SZOMB && p->p_limit->p_cpulimit != RLIM_INFINITY &&
 859             ttime > p->p_limit->p_cpulimit) {
 860                 rlim = &p->p_rlimit[RLIMIT_CPU];
 861                 if (ttime / (rlim_t)1000000 >= rlim->rlim_max) {
 862                         killproc(p, "exceeded maximum CPU limit");
 863                 } else {
 864                         psignal(p, SIGXCPU);
 865                         if (rlim->rlim_cur < rlim->rlim_max) {
 866                                 /* XXX: we should make a private copy */
 867                                 rlim->rlim_cur += 5;
 868                         }
 869                 }
 870         }
 871
 872         /*
 873          * Pick a new current process and record its start time.
 874          * YYY lwkt_switch() will run the heavy weight process restoration
 875          * code, which removes the target thread and process from their
 876          * respective run queues to temporarily mimic 5.x behavior.
 877          * YYY the userland scheduler should pick only one user process
 878          * at a time to run per cpu.
 879          */
 880         mycpu->gd_cnt.v_swtch++;
 881         lwkt_switch();
 882
 883         splx(x);
 884 }
 885
 886 /*
 887  * Change process state to be runnable,
 888  * placing it on the run queue if it is in memory,
 889  * and awakening the swapper if it isn't in memory.
 890  */
 891 void
 892 setrunnable(struct proc *p)
 893 {
 894         int s;
 895
 896         s = splhigh();
 897         switch (p->p_stat) {
 898         case 0:
 899         case SRUN:
 900         case SZOMB:
 901         default:
 902                 panic("setrunnable");
 903         case SSTOP:
 904         case SSLEEP:
 905                 unsleep(p->p_thread);   /* e.g. when sending signals */
 906                 break;
 907
 908         case SIDL:
 909                 break;
 910         }
 911         p->p_stat = SRUN;
 912         if (p->p_flag & P_INMEM)
 913                 setrunqueue(p);
 914         splx(s);
 915         if (p->p_slptime > 1)
 916                 updatepri(p);
 917         p->p_slptime = 0;
 918         if ((p->p_flag & P_INMEM) == 0) {
 919                 p->p_flag |= P_SWAPINREQ;
 920                 wakeup((caddr_t)&proc0);
 921         } else {
 922                 maybe_resched(p);
 923         }
 924 }
 925
 926 /*
 927  * Change the process state to NOT be runnable, removing it from the run
 928  * queue.  If P_CURPROC is not set and we are in SRUN the process is on the
 929  * run queue (If P_INMEM is not set then it isn't because it is swapped).
 930  */
 931 void
 932 clrrunnable(struct proc *p, int stat)
 933 {
 934         int s;
 935
 936         s = splhigh();
 937         switch(p->p_stat) {
 938         case SRUN:
 939                 if ((p->p_flag & (P_INMEM|P_CURPROC)) == P_INMEM)
 940                         remrunqueue(p);
 941                 break;
 942         default:
 943                 break;
 944         }
 945         p->p_stat = stat;
 946         splx(s);
 947 }
 948
 949 /*
 950  * yield / synchronous reschedule
 951  *
 952  * Simply calling mi_switch() has the effect we want.  mi_switch will
 953  * deschedule the current thread, make sure the current process is on
 954  * the run queue, and then choose and reschedule another process.
 955  */
 956 void
 957 uio_yield()
 958 {
 959         struct proc *p = curproc;
 960         int s;
 961
 962         s = splhigh();
 963 #if 0
 964         KKASSERT(p->p_stat == SRUN);
 965         if ((p->p_flag & (P_INMEM|P_CURPROC)) == (P_INMEM|P_CURPROC))
 966                 setrunqueue(p);
 967         lwkt_deschedule_self();
 968 #endif
 969         p->p_stats->p_ru.ru_nivcsw++;
 970         mi_switch();
 971         splx(s);
 972 }
 973
 974 /*
 975  * Compute the priority of a process when running in user mode.
 976  * Arrange to reschedule if the resulting priority is better
 977  * than that of the current process.
 978  *
 979  * YYY real time / idle procs do not use p_priority XXX
 980  */
 981 void
 982 resetpriority(struct proc *p)
 983 {
 984         unsigned int newpriority;
 985         int opq;
 986         int npq;
 987
 988         if (p->p_rtprio.type != RTP_PRIO_NORMAL)
 989                 return;
 990         newpriority = PUSER + p->p_estcpu / INVERSE_ESTCPU_WEIGHT +
 991             NICE_WEIGHT * p->p_nice;
 992         newpriority = min(newpriority, MAXPRI);
 993         npq = newpriority / PPQ;
 994         crit_enter();
 995         opq = p->p_priority / PPQ;
 996         if (p->p_stat == SRUN && (p->p_flag & (P_CURPROC|P_INMEM)) == P_INMEM
 997             && opq != npq) {
 998                 /*
 999                  * We have to move the process to another queue
1000                  */
1001                 remrunqueue(p);
1002                 p->p_priority = newpriority;
1003                 setrunqueue(p);
1004         } else {
1005                 /*
1006                  * Not on a queue or is on the same queue, we can just
1007                  * set the priority.
1008                  * YYY P_INMEM?
1009                  */
1010                 p->p_priority = newpriority;
1011         }
1012         crit_exit();
1013         maybe_resched(p);
1014 }
1015
1016 /*
1017  * Compute a tenex style load average of a quantity on
1018  * 1, 5 and 15 minute intervals.
1019  */
1020 static void
1021 loadav(void *arg)
1022 {
1023         int i, nrun;
1024         struct loadavg *avg;
1025         struct proc *p;
1026
1027         avg = &averunnable;
1028         nrun = 0;
1029         LIST_FOREACH(p, &allproc, p_list) {
1030                 switch (p->p_stat) {
1031                 case SRUN:
1032                 case SIDL:
1033                         nrun++;
1034                 }
1035         }
1036         for (i = 0; i < 3; i++)
1037                 avg->ldavg[i] = (cexp[i] * avg->ldavg[i] +
1038                     nrun * FSCALE * (FSCALE - cexp[i])) >> FSHIFT;
1039
1040         /*
1041          * Schedule the next update to occur after 5 seconds, but add a
1042          * random variation to avoid synchronisation with processes that
1043          * run at regular intervals.
1044          */
1045         callout_reset(&loadav_callout, hz * 4 + (int)(random() % (hz * 2 + 1)),
1046             loadav, NULL);
1047 }
1048
1049 /* ARGSUSED */
1050 static void
1051 sched_setup(dummy)
1052         void *dummy;
1053 {
1054
1055         callout_init(&loadav_callout);
1056
1057         /* Kick off timeout driven events by calling first time. */
1058         roundrobin(NULL);
1059         schedcpu(NULL);
1060         loadav(NULL);
1061 }
1062
1063 /*
1064  * We adjust the priority of the current process.  The priority of
1065  * a process gets worse as it accumulates CPU time.  The cpu usage
1066  * estimator (p_estcpu) is increased here.  resetpriority() will
1067  * compute a different priority each time p_estcpu increases by
1068  * INVERSE_ESTCPU_WEIGHT
1069  * (until MAXPRI is reached).  The cpu usage estimator ramps up
1070  * quite quickly when the process is running (linearly), and decays
1071  * away exponentially, at a rate which is proportionally slower when
1072  * the system is busy.  The basic principle is that the system will
1073  * 90% forget that the process used a lot of CPU time in 5 * loadav
1074  * seconds.  This causes the system to favor processes which haven't
1075  * run much recently, and to round-robin among other processes.
1076  */
1077 void
1078 schedclock(p)
1079         struct proc *p;
1080 {
1081
1082         p->p_cpticks++;
1083         p->p_estcpu = ESTCPULIM(p->p_estcpu + 1);
1084         if ((p->p_estcpu % INVERSE_ESTCPU_WEIGHT) == 0)
1085                 resetpriority(p);
1086 }