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.82 2007/03/12 21:08:15 corecode 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/signal2.h>
  51 #include <sys/resourcevar.h>
  52 #include <sys/vmmeter.h>
  53 #include <sys/sysctl.h>
  54 #include <sys/lock.h>
  55 #ifdef KTRACE
  56 #include <sys/uio.h>
  57 #include <sys/ktrace.h>
  58 #endif
  59 #include <sys/xwait.h>
  60 #include <sys/ktr.h>
  61
  62 #include <sys/thread2.h>
  63 #include <sys/spinlock2.h>
  64
  65 #include <machine/cpu.h>
  66 #include <machine/smp.h>
  67
  68 TAILQ_HEAD(tslpque, thread);
  69
  70 static void sched_setup (void *dummy);
  71 SYSINIT(sched_setup, SI_SUB_KICK_SCHEDULER, SI_ORDER_FIRST, sched_setup, NULL)
  72
  73 int     hogticks;
  74 int     lbolt;
  75 int     lbolt_syncer;
  76 int     sched_quantum;          /* Roundrobin scheduling quantum in ticks. */
  77 int     ncpus;
  78 int     ncpus2, ncpus2_shift, ncpus2_mask;
  79 int     safepri;
  80
  81 static struct callout loadav_callout;
  82 static struct callout schedcpu_callout;
  83 MALLOC_DEFINE(M_TSLEEP, "tslpque", "tsleep queues");
  84
  85 #if !defined(KTR_TSLEEP)
  86 #define KTR_TSLEEP      KTR_ALL
  87 #endif
  88 KTR_INFO_MASTER(tsleep);
  89 KTR_INFO(KTR_TSLEEP, tsleep, tsleep_beg, 0, "tsleep enter", 0);
  90 KTR_INFO(KTR_TSLEEP, tsleep, tsleep_end, 0, "tsleep exit", 0);
  91 KTR_INFO(KTR_TSLEEP, tsleep, wakeup_beg, 0, "wakeup enter", 0);
  92 KTR_INFO(KTR_TSLEEP, tsleep, wakeup_end, 0, "wakeup exit", 0);
  93 #define logtsleep(name) KTR_LOG(tsleep_ ## name)
  94
  95 struct loadavg averunnable =
  96         { {0, 0, 0}, FSCALE };  /* load average, of runnable procs */
  97 /*
  98  * Constants for averages over 1, 5, and 15 minutes
  99  * when sampling at 5 second intervals.
 100  */
 101 static fixpt_t cexp[3] = {
 102         0.9200444146293232 * FSCALE,    /* exp(-1/12) */
 103         0.9834714538216174 * FSCALE,    /* exp(-1/60) */
 104         0.9944598480048967 * FSCALE,    /* exp(-1/180) */
 105 };
 106
 107 static void     endtsleep (void *);
 108 static void     unsleep_and_wakeup_thread(struct thread *td);
 109 static void     loadav (void *arg);
 110 static void     schedcpu (void *arg);
 111
 112 /*
 113  * Adjust the scheduler quantum.  The quantum is specified in microseconds.
 114  * Note that 'tick' is in microseconds per tick.
 115  */
 116 static int
 117 sysctl_kern_quantum(SYSCTL_HANDLER_ARGS)
 118 {
 119         int error, new_val;
 120
 121         new_val = sched_quantum * tick;
 122         error = sysctl_handle_int(oidp, &new_val, 0, req);
 123         if (error != 0 || req->newptr == NULL)
 124                 return (error);
 125         if (new_val < tick)
 126                 return (EINVAL);
 127         sched_quantum = new_val / tick;
 128         hogticks = 2 * sched_quantum;
 129         return (0);
 130 }
 131
 132 SYSCTL_PROC(_kern, OID_AUTO, quantum, CTLTYPE_INT|CTLFLAG_RW,
 133         0, sizeof sched_quantum, sysctl_kern_quantum, "I", "");
 134
 135 /*
 136  * If `ccpu' is not equal to `exp(-1/20)' and you still want to use the
 137  * faster/more-accurate formula, you'll have to estimate CCPU_SHIFT below
 138  * and possibly adjust FSHIFT in "param.h" so that (FSHIFT >= CCPU_SHIFT).
 139  *
 140  * To estimate CCPU_SHIFT for exp(-1/20), the following formula was used:
 141  *     1 - exp(-1/20) ~= 0.0487 ~= 0.0488 == 1 (fixed pt, *11* bits).
 142  *
 143  * If you don't want to bother with the faster/more-accurate formula, you
 144  * can set CCPU_SHIFT to (FSHIFT + 1) which will use a slower/less-accurate
 145  * (more general) method of calculating the %age of CPU used by a process.
 146  *
 147  * decay 95% of `lwp_pctcpu' in 60 seconds; see CCPU_SHIFT before changing
 148  */
 149 #define CCPU_SHIFT      11
 150
 151 static fixpt_t ccpu = 0.95122942450071400909 * FSCALE; /* exp(-1/20) */
 152 SYSCTL_INT(_kern, OID_AUTO, ccpu, CTLFLAG_RD, &ccpu, 0, "");
 153
 154 /*
 155  * kernel uses `FSCALE', userland (SHOULD) use kern.fscale
 156  */
 157 int     fscale __unused = FSCALE;       /* exported to systat */
 158 SYSCTL_INT(_kern, OID_AUTO, fscale, CTLFLAG_RD, 0, FSCALE, "");
 159
 160 /*
 161  * Recompute process priorities, once a second.
 162  *
 163  * Since the userland schedulers are typically event oriented, if the
 164  * estcpu calculation at wakeup() time is not sufficient to make a
 165  * process runnable relative to other processes in the system we have
 166  * a 1-second recalc to help out.
 167  *
 168  * This code also allows us to store sysclock_t data in the process structure
 169  * without fear of an overrun, since sysclock_t are guarenteed to hold
 170  * several seconds worth of count.
 171  *
 172  * WARNING!  callouts can preempt normal threads.  However, they will not
 173  * preempt a thread holding a spinlock so we *can* safely use spinlocks.
 174  */
 175 static int schedcpu_stats(struct proc *p, void *data __unused);
 176 static int schedcpu_resource(struct proc *p, void *data __unused);
 177
 178 static void
 179 schedcpu(void *arg)
 180 {
 181         allproc_scan(schedcpu_stats, NULL);
 182         allproc_scan(schedcpu_resource, NULL);
 183         wakeup((caddr_t)&lbolt);
 184         wakeup((caddr_t)&lbolt_syncer);
 185         callout_reset(&schedcpu_callout, hz, schedcpu, NULL);
 186 }
 187
 188 /*
 189  * General process statistics once a second
 190  */
 191 static int
 192 schedcpu_stats(struct proc *p, void *data __unused)
 193 {
 194         struct lwp *lp;
 195
 196         crit_enter();
 197         p->p_swtime++;
 198         FOREACH_LWP_IN_PROC(lp, p) {
 199                 if (lp->lwp_stat == LSSLEEP)
 200                         lp->lwp_slptime++;
 201
 202                 /*
 203                  * Only recalculate processes that are active or have slept
 204                  * less then 2 seconds.  The schedulers understand this.
 205                  */
 206                 if (lp->lwp_slptime <= 1) {
 207                         p->p_usched->recalculate(lp);
 208                 } else {
 209                         lp->lwp_pctcpu = (lp->lwp_pctcpu * ccpu) >> FSHIFT;
 210                 }
 211         }
 212         crit_exit();
 213         return(0);
 214 }
 215
 216 /*
 217  * Resource checks.  XXX break out since ksignal/killproc can block,
 218  * limiting us to one process killed per second.  There is probably
 219  * a better way.
 220  */
 221 static int
 222 schedcpu_resource(struct proc *p, void *data __unused)
 223 {
 224         u_int64_t ttime;
 225         struct lwp *lp;
 226
 227         crit_enter();
 228         if (p->p_stat == SIDL ||
 229             p->p_stat == SZOMB ||
 230             p->p_limit == NULL
 231         ) {
 232                 crit_exit();
 233                 return(0);
 234         }
 235
 236         ttime = 0;
 237         FOREACH_LWP_IN_PROC(lp, p) {
 238                 ttime += lp->lwp_thread->td_sticks;
 239                 ttime += lp->lwp_thread->td_uticks;
 240         }
 241
 242         switch(plimit_testcpulimit(p->p_limit, ttime)) {
 243         case PLIMIT_TESTCPU_KILL:
 244                 killproc(p, "exceeded maximum CPU limit");
 245                 break;
 246         case PLIMIT_TESTCPU_XCPU:
 247                 if ((p->p_flag & P_XCPU) == 0) {
 248                         p->p_flag |= P_XCPU;
 249                         ksignal(p, SIGXCPU);
 250                 }
 251                 break;
 252         default:
 253                 break;
 254         }
 255         crit_exit();
 256         return(0);
 257 }
 258
 259 /*
 260  * This is only used by ps.  Generate a cpu percentage use over
 261  * a period of one second.
 262  *
 263  * MPSAFE
 264  */
 265 void
 266 updatepcpu(struct lwp *lp, int cpticks, int ttlticks)
 267 {
 268         fixpt_t acc;
 269         int remticks;
 270
 271         acc = (cpticks << FSHIFT) / ttlticks;
 272         if (ttlticks >= ESTCPUFREQ) {
 273                 lp->lwp_pctcpu = acc;
 274         } else {
 275                 remticks = ESTCPUFREQ - ttlticks;
 276                 lp->lwp_pctcpu = (acc * ttlticks + lp->lwp_pctcpu * remticks) /
 277                                 ESTCPUFREQ;
 278         }
 279 }
 280
 281 /*
 282  * We're only looking at 7 bits of the address; everything is
 283  * aligned to 4, lots of things are aligned to greater powers
 284  * of 2.  Shift right by 8, i.e. drop the bottom 256 worth.
 285  */
 286 #define TABLESIZE       128
 287 #define LOOKUP(x)       (((intptr_t)(x) >> 8) & (TABLESIZE - 1))
 288
 289 static cpumask_t slpque_cpumasks[TABLESIZE];
 290
 291 /*
 292  * General scheduler initialization.  We force a reschedule 25 times
 293  * a second by default.  Note that cpu0 is initialized in early boot and
 294  * cannot make any high level calls.
 295  *
 296  * Each cpu has its own sleep queue.
 297  */
 298 void
 299 sleep_gdinit(globaldata_t gd)
 300 {
 301         static struct tslpque slpque_cpu0[TABLESIZE];
 302         int i;
 303
 304         if (gd->gd_cpuid == 0) {
 305                 sched_quantum = (hz + 24) / 25;
 306                 hogticks = 2 * sched_quantum;
 307
 308                 gd->gd_tsleep_hash = slpque_cpu0;
 309         } else {
 310                 gd->gd_tsleep_hash = kmalloc(sizeof(slpque_cpu0),
 311                                             M_TSLEEP, M_WAITOK | M_ZERO);
 312         }
 313         for (i = 0; i < TABLESIZE; ++i)
 314                 TAILQ_INIT(&gd->gd_tsleep_hash[i]);
 315 }
 316
 317 /*
 318  * General sleep call.  Suspends the current process until a wakeup is
 319  * performed on the specified identifier.  The process will then be made
 320  * runnable with the specified priority.  Sleeps at most timo/hz seconds
 321  * (0 means no timeout).  If flags includes PCATCH flag, signals are checked
 322  * before and after sleeping, else signals are not checked.  Returns 0 if
 323  * awakened, EWOULDBLOCK if the timeout expires.  If PCATCH is set and a
 324  * signal needs to be delivered, ERESTART is returned if the current system
 325  * call should be restarted if possible, and EINTR is returned if the system
 326  * call should be interrupted by the signal (return EINTR).
 327  *
 328  * Note that if we are a process, we release_curproc() before messing with
 329  * the LWKT scheduler.
 330  *
 331  * During autoconfiguration or after a panic, a sleep will simply
 332  * lower the priority briefly to allow interrupts, then return.
 333  */
 334 int
 335 tsleep(void *ident, int flags, const char *wmesg, int timo)
 336 {
 337         struct thread *td = curthread;
 338         struct lwp *lp = td->td_lwp;
 339         struct proc *p = td->td_proc;           /* may be NULL */
 340         globaldata_t gd;
 341         int sig;
 342         int catch;
 343         int id;
 344         int error;
 345         int oldpri;
 346         struct callout thandle;
 347
 348         /*
 349          * NOTE: removed KTRPOINT, it could cause races due to blocking
 350          * even in stable.  Just scrap it for now.
 351          */
 352         if (cold || panicstr) {
 353                 /*
 354                  * After a panic, or during autoconfiguration,
 355                  * just give interrupts a chance, then just return;
 356                  * don't run any other procs or panic below,
 357                  * in case this is the idle process and already asleep.
 358                  */
 359                 splz();
 360                 oldpri = td->td_pri & TDPRI_MASK;
 361                 lwkt_setpri_self(safepri);
 362                 lwkt_switch();
 363                 lwkt_setpri_self(oldpri);
 364                 return (0);
 365         }
 366         logtsleep(tsleep_beg);
 367         gd = td->td_gd;
 368         KKASSERT(td != &gd->gd_idlethread);     /* you must be kidding! */
 369
 370         /*
 371          * NOTE: all of this occurs on the current cpu, including any
 372          * callout-based wakeups, so a critical section is a sufficient
 373          * interlock.
 374          *
 375          * The entire sequence through to where we actually sleep must
 376          * run without breaking the critical section.
 377          */
 378         id = LOOKUP(ident);
 379         catch = flags & PCATCH;
 380         error = 0;
 381         sig = 0;
 382
 383         crit_enter_quick(td);
 384
 385         KASSERT(ident != NULL, ("tsleep: no ident"));
 386         KASSERT(lp == NULL ||
 387                 lp->lwp_stat == LSRUN ||        /* Obvious */
 388                 lp->lwp_stat == LSSTOP,         /* Set in tstop */
 389                 ("tsleep %p %s %d",
 390                         ident, wmesg, lp->lwp_stat));
 391
 392         /*
 393          * Setup for the current process (if this is a process).
 394          */
 395         if (lp) {
 396                 if (catch) {
 397                         /*
 398                          * Early termination if PCATCH was set and a
 399                          * signal is pending, interlocked with the
 400                          * critical section.
 401                          *
 402                          * Early termination only occurs when tsleep() is
 403                          * entered while in a normal LSRUN state.
 404                          */
 405                         if ((sig = CURSIG(lp)) != 0)
 406                                 goto resume;
 407
 408                         /*
 409                          * Early termination if PCATCH was set and a
 410                          * mailbox signal was possibly delivered prior to
 411                          * the system call even being made, in order to
 412                          * allow the user to interlock without having to
 413                          * make additional system calls.
 414                          */
 415                         if (p->p_flag & P_MAILBOX)
 416                                 goto resume;
 417
 418                         /*
 419                          * Causes ksignal to wake us up when.
 420                          */
 421                         lp->lwp_flag |= LWP_SINTR;
 422                 }
 423
 424                 /*
 425                  * Make sure the current process has been untangled from
 426                  * the userland scheduler and initialize slptime to start
 427                  * counting.
 428                  */
 429                 if (flags & PNORESCHED)
 430                         td->td_flags |= TDF_NORESCHED;
 431                 p->p_usched->release_curproc(lp);
 432                 lp->lwp_slptime = 0;
 433         }
 434
 435         /*
 436          * Move our thread to the correct queue and setup our wchan, etc.
 437          */
 438         lwkt_deschedule_self(td);
 439         td->td_flags |= TDF_TSLEEPQ;
 440         TAILQ_INSERT_TAIL(&gd->gd_tsleep_hash[id], td, td_threadq);
 441         atomic_set_int(&slpque_cpumasks[id], gd->gd_cpumask);
 442
 443         td->td_wchan = ident;
 444         td->td_wmesg = wmesg;
 445         td->td_wdomain = flags & PDOMAIN_MASK;
 446
 447         /*
 448          * Setup the timeout, if any
 449          */
 450         if (timo) {
 451                 callout_init(&thandle);
 452                 callout_reset(&thandle, timo, endtsleep, td);
 453         }
 454
 455         /*
 456          * Beddy bye bye.
 457          */
 458         if (lp) {
 459                 /*
 460                  * Ok, we are sleeping.  Place us in the SSLEEP state.
 461                  */
 462                 KKASSERT((lp->lwp_flag & LWP_ONRUNQ) == 0);
 463                 /*
 464                  * tstop() sets LSSTOP, so don't fiddle with that.
 465                  */
 466                 if (lp->lwp_stat != LSSTOP)
 467                         lp->lwp_stat = LSSLEEP;
 468                 lp->lwp_ru.ru_nvcsw++;
 469                 lwkt_switch();
 470
 471                 /*
 472                  * And when we are woken up, put us back in LSRUN.  If we
 473                  * slept for over a second, recalculate our estcpu.
 474                  */
 475                 lp->lwp_stat = LSRUN;
 476                 if (lp->lwp_slptime)
 477                         p->p_usched->recalculate(lp);
 478                 lp->lwp_slptime = 0;
 479         } else {
 480                 lwkt_switch();
 481         }
 482
 483         /*
 484          * Make sure we haven't switched cpus while we were asleep.  It's
 485          * not supposed to happen.  Cleanup our temporary flags.
 486          */
 487         KKASSERT(gd == td->td_gd);
 488         td->td_flags &= ~TDF_NORESCHED;
 489
 490         /*
 491          * Cleanup the timeout.
 492          */
 493         if (timo) {
 494                 if (td->td_flags & TDF_TIMEOUT) {
 495                         td->td_flags &= ~TDF_TIMEOUT;
 496                         error = EWOULDBLOCK;
 497                 } else {
 498                         callout_stop(&thandle);
 499                 }
 500         }
 501
 502         /*
 503          * Since td_threadq is used both for our run queue AND for the
 504          * tsleep hash queue, we can't still be on it at this point because
 505          * we've gotten cpu back.
 506          */
 507         KASSERT((td->td_flags & TDF_TSLEEPQ) == 0, ("tsleep: impossible thread flags %08x", td->td_flags));
 508         td->td_wchan = NULL;
 509         td->td_wmesg = NULL;
 510         td->td_wdomain = 0;
 511
 512         /*
 513          * Figure out the correct error return.  If interrupted by a
 514          * signal we want to return EINTR or ERESTART.
 515          *
 516          * If P_MAILBOX is set no automatic system call restart occurs
 517          * and we return EINTR.  P_MAILBOX is meant to be used as an
 518          * interlock, the user must poll it prior to any system call
 519          * that it wishes to interlock a mailbox signal against since
 520          * the flag is cleared on *any* system call that sleeps.
 521          */
 522 resume:
 523         if (p) {
 524                 if (catch && error == 0) {
 525                         if ((p->p_flag & P_MAILBOX) && sig == 0) {
 526                                 error = EINTR;
 527                         } else if (sig != 0 || (sig = CURSIG(lp))) {
 528                                 if (SIGISMEMBER(p->p_sigacts->ps_sigintr, sig))
 529                                         error = EINTR;
 530                                 else
 531                                         error = ERESTART;
 532                         }
 533                 }
 534                 lp->lwp_flag &= ~(LWP_BREAKTSLEEP | LWP_SINTR);
 535                 p->p_flag &= ~P_MAILBOX;
 536         }
 537         logtsleep(tsleep_end);
 538         crit_exit_quick(td);
 539         return (error);
 540 }
 541
 542 /*
 543  * This is a dandy function that allows us to interlock tsleep/wakeup
 544  * operations with unspecified upper level locks, such as lockmgr locks,
 545  * simply by holding a critical section.  The sequence is:
 546  *
 547  *      (enter critical section)
 548  *      (acquire upper level lock)
 549  *      tsleep_interlock(blah)
 550  *      (release upper level lock)
 551  *      tsleep(blah, ...)
 552  *      (exit critical section)
 553  *
 554  * Basically this function sets our cpumask for the ident which informs
 555  * other cpus that our cpu 'might' be waiting (or about to wait on) the
 556  * hash index related to the ident.  The critical section prevents another
 557  * cpu's wakeup() from being processed on our cpu until we are actually
 558  * able to enter the tsleep().  Thus, no race occurs between our attempt
 559  * to release a resource and sleep, and another cpu's attempt to acquire
 560  * a resource and call wakeup.
 561  *
 562  * There isn't much of a point to this function unless you call it while
 563  * holding a critical section.
 564  */
 565 static __inline void
 566 _tsleep_interlock(globaldata_t gd, void *ident)
 567 {
 568         int id = LOOKUP(ident);
 569
 570         atomic_set_int(&slpque_cpumasks[id], gd->gd_cpumask);
 571 }
 572
 573 void
 574 tsleep_interlock(void *ident)
 575 {
 576         _tsleep_interlock(mycpu, ident);
 577 }
 578
 579 /*
 580  * Interlocked spinlock sleep.  An exclusively held spinlock must
 581  * be passed to msleep().  The function will atomically release the
 582  * spinlock and tsleep on the ident, then reacquire the spinlock and
 583  * return.
 584  *
 585  * This routine is fairly important along the critical path, so optimize it
 586  * heavily.
 587  */
 588 int
 589 msleep(void *ident, struct spinlock *spin, int flags,
 590        const char *wmesg, int timo)
 591 {
 592         globaldata_t gd = mycpu;
 593         int error;
 594
 595         crit_enter_gd(gd);
 596         _tsleep_interlock(gd, ident);
 597         spin_unlock_wr_quick(gd, spin);
 598         error = tsleep(ident, flags, wmesg, timo);
 599         spin_lock_wr_quick(gd, spin);
 600         crit_exit_gd(gd);
 601
 602         return (error);
 603 }
 604
 605 /*
 606  * Implement the timeout for tsleep.
 607  *
 608  * We set LWP_BREAKTSLEEP to indicate that an event has occured, but
 609  * we only call setrunnable if the process is not stopped.
 610  *
 611  * This type of callout timeout is scheduled on the same cpu the process
 612  * is sleeping on.  Also, at the moment, the MP lock is held.
 613  */
 614 static void
 615 endtsleep(void *arg)
 616 {
 617         thread_t td = arg;
 618         struct lwp *lp;
 619
 620         ASSERT_MP_LOCK_HELD(curthread);
 621         crit_enter();
 622
 623         /*
 624          * cpu interlock.  Thread flags are only manipulated on
 625          * the cpu owning the thread.  proc flags are only manipulated
 626          * by the older of the MP lock.  We have both.
 627          */
 628         if (td->td_flags & TDF_TSLEEPQ) {
 629                 td->td_flags |= TDF_TIMEOUT;
 630
 631                 if ((lp = td->td_lwp) != NULL) {
 632                         lp->lwp_flag |= LWP_BREAKTSLEEP;
 633                         if (lp->lwp_proc->p_stat != SSTOP)
 634                                 setrunnable(lp);
 635                 } else {
 636                         unsleep_and_wakeup_thread(td);
 637                 }
 638         }
 639         crit_exit();
 640 }
 641
 642 /*
 643  * Unsleep and wakeup a thread.  This function runs without the MP lock
 644  * which means that it can only manipulate thread state on the owning cpu,
 645  * and cannot touch the process state at all.
 646  */
 647 static
 648 void
 649 unsleep_and_wakeup_thread(struct thread *td)
 650 {
 651         globaldata_t gd = mycpu;
 652         int id;
 653
 654 #ifdef SMP
 655         if (td->td_gd != gd) {
 656                 lwkt_send_ipiq(td->td_gd, (ipifunc1_t)unsleep_and_wakeup_thread, td);
 657                 return;
 658         }
 659 #endif
 660         crit_enter();
 661         if (td->td_flags & TDF_TSLEEPQ) {
 662                 td->td_flags &= ~TDF_TSLEEPQ;
 663                 id = LOOKUP(td->td_wchan);
 664                 TAILQ_REMOVE(&gd->gd_tsleep_hash[id], td, td_threadq);
 665                 if (TAILQ_FIRST(&gd->gd_tsleep_hash[id]) == NULL)
 666                         atomic_clear_int(&slpque_cpumasks[id], gd->gd_cpumask);
 667                 lwkt_schedule(td);
 668         }
 669         crit_exit();
 670 }
 671
 672 /*
 673  * Make all processes sleeping on the specified identifier runnable.
 674  * count may be zero or one only.
 675  *
 676  * The domain encodes the sleep/wakeup domain AND the first cpu to check
 677  * (which is always the current cpu).  As we iterate across cpus
 678  *
 679  * This call may run without the MP lock held.  We can only manipulate thread
 680  * state on the cpu owning the thread.  We CANNOT manipulate process state
 681  * at all.
 682  */
 683 static void
 684 _wakeup(void *ident, int domain)
 685 {
 686         struct tslpque *qp;
 687         struct thread *td;
 688         struct thread *ntd;
 689         globaldata_t gd;
 690 #ifdef SMP
 691         cpumask_t mask;
 692         cpumask_t tmask;
 693         int startcpu;
 694         int nextcpu;
 695 #endif
 696         int id;
 697
 698         crit_enter();
 699         logtsleep(wakeup_beg);
 700         gd = mycpu;
 701         id = LOOKUP(ident);
 702         qp = &gd->gd_tsleep_hash[id];
 703 restart:
 704         for (td = TAILQ_FIRST(qp); td != NULL; td = ntd) {
 705                 ntd = TAILQ_NEXT(td, td_threadq);
 706                 if (td->td_wchan == ident &&
 707                     td->td_wdomain == (domain & PDOMAIN_MASK)
 708                 ) {
 709                         KKASSERT(td->td_flags & TDF_TSLEEPQ);
 710                         td->td_flags &= ~TDF_TSLEEPQ;
 711                         TAILQ_REMOVE(qp, td, td_threadq);
 712                         if (TAILQ_FIRST(qp) == NULL) {
 713                                 atomic_clear_int(&slpque_cpumasks[id],
 714                                                  gd->gd_cpumask);
 715                         }
 716                         lwkt_schedule(td);
 717                         if (domain & PWAKEUP_ONE)
 718                                 goto done;
 719                         goto restart;
 720                 }
 721         }
 722
 723 #ifdef SMP
 724         /*
 725          * We finished checking the current cpu but there still may be
 726          * more work to do.  Either wakeup_one was requested and no matching
 727          * thread was found, or a normal wakeup was requested and we have
 728          * to continue checking cpus.
 729          *
 730          * The cpu that started the wakeup sequence is encoded in the domain.
 731          * We use this information to determine which cpus still need to be
 732          * checked, locate a candidate cpu, and chain the wakeup
 733          * asynchronously with an IPI message.
 734          *
 735          * It should be noted that this scheme is actually less expensive then
 736          * the old scheme when waking up multiple threads, since we send
 737          * only one IPI message per target candidate which may then schedule
 738          * multiple threads.  Before we could have wound up sending an IPI
 739          * message for each thread on the target cpu (!= current cpu) that
 740          * needed to be woken up.
 741          *
 742          * NOTE: Wakeups occuring on remote cpus are asynchronous.  This
 743          * should be ok since we are passing idents in the IPI rather then
 744          * thread pointers.
 745          */
 746         if ((domain & PWAKEUP_MYCPU) == 0 &&
 747             (mask = slpque_cpumasks[id]) != 0
 748         ) {
 749                 /*
 750                  * Look for a cpu that might have work to do.  Mask out cpus
 751                  * which have already been processed.
 752                  *
 753                  * 31xxxxxxxxxxxxxxxxxxxxxxxxxxxxx0
 754                  *        ^        ^           ^
 755                  *      start   currentcpu    start
 756                  *      case2                 case1
 757                  *        *        *           *
 758                  * 11111111111111110000000000000111     case1
 759                  * 00000000111111110000000000000000     case2
 760                  *
 761                  * case1:  We started at start_case1 and processed through
 762                  *         to the current cpu.  We have to check any bits
 763                  *         after the current cpu, then check bits before
 764                  *         the starting cpu.
 765                  *
 766                  * case2:  We have already checked all the bits from
 767                  *         start_case2 to the end, and from 0 to the current
 768                  *         cpu.  We just have the bits from the current cpu
 769                  *         to start_case2 left to check.
 770                  */
 771                 startcpu = PWAKEUP_DECODE(domain);
 772                 if (gd->gd_cpuid >= startcpu) {
 773                         /*
 774                          * CASE1
 775                          */
 776                         tmask = mask & ~((gd->gd_cpumask << 1) - 1);
 777                         if (mask & tmask) {
 778                                 nextcpu = bsfl(mask & tmask);
 779                                 lwkt_send_ipiq2(globaldata_find(nextcpu),
 780                                                 _wakeup, ident, domain);
 781                         } else {
 782                                 tmask = (1 << startcpu) - 1;
 783                                 if (mask & tmask) {
 784                                         nextcpu = bsfl(mask & tmask);
 785                                         lwkt_send_ipiq2(
 786                                                     globaldata_find(nextcpu),
 787                                                     _wakeup, ident, domain);
 788                                 }
 789                         }
 790                 } else {
 791                         /*
 792                          * CASE2
 793                          */
 794                         tmask = ~((gd->gd_cpumask << 1) - 1) &
 795                                  ((1 << startcpu) - 1);
 796                         if (mask & tmask) {
 797                                 nextcpu = bsfl(mask & tmask);
 798                                 lwkt_send_ipiq2(globaldata_find(nextcpu),
 799                                                 _wakeup, ident, domain);
 800                         }
 801                 }
 802         }
 803 #endif
 804 done:
 805         logtsleep(wakeup_end);
 806         crit_exit();
 807 }
 808
 809 /*
 810  * Wakeup all threads tsleep()ing on the specified ident, on all cpus
 811  */
 812 void
 813 wakeup(void *ident)
 814 {
 815     _wakeup(ident, PWAKEUP_ENCODE(0, mycpu->gd_cpuid));
 816 }
 817
 818 /*
 819  * Wakeup one thread tsleep()ing on the specified ident, on any cpu.
 820  */
 821 void
 822 wakeup_one(void *ident)
 823 {
 824     /* XXX potentially round-robin the first responding cpu */
 825     _wakeup(ident, PWAKEUP_ENCODE(0, mycpu->gd_cpuid) | PWAKEUP_ONE);
 826 }
 827
 828 /*
 829  * Wakeup threads tsleep()ing on the specified ident on the current cpu
 830  * only.
 831  */
 832 void
 833 wakeup_mycpu(void *ident)
 834 {
 835     _wakeup(ident, PWAKEUP_MYCPU);
 836 }
 837
 838 /*
 839  * Wakeup one thread tsleep()ing on the specified ident on the current cpu
 840  * only.
 841  */
 842 void
 843 wakeup_mycpu_one(void *ident)
 844 {
 845     /* XXX potentially round-robin the first responding cpu */
 846     _wakeup(ident, PWAKEUP_MYCPU|PWAKEUP_ONE);
 847 }
 848
 849 /*
 850  * Wakeup all thread tsleep()ing on the specified ident on the specified cpu
 851  * only.
 852  */
 853 void
 854 wakeup_oncpu(globaldata_t gd, void *ident)
 855 {
 856 #ifdef SMP
 857     if (gd == mycpu) {
 858         _wakeup(ident, PWAKEUP_MYCPU);
 859     } else {
 860         lwkt_send_ipiq2(gd, _wakeup, ident, PWAKEUP_MYCPU);
 861     }
 862 #else
 863     _wakeup(ident, PWAKEUP_MYCPU);
 864 #endif
 865 }
 866
 867 /*
 868  * Wakeup one thread tsleep()ing on the specified ident on the specified cpu
 869  * only.
 870  */
 871 void
 872 wakeup_oncpu_one(globaldata_t gd, void *ident)
 873 {
 874 #ifdef SMP
 875     if (gd == mycpu) {
 876         _wakeup(ident, PWAKEUP_MYCPU | PWAKEUP_ONE);
 877     } else {
 878         lwkt_send_ipiq2(gd, _wakeup, ident, PWAKEUP_MYCPU | PWAKEUP_ONE);
 879     }
 880 #else
 881     _wakeup(ident, PWAKEUP_MYCPU | PWAKEUP_ONE);
 882 #endif
 883 }
 884
 885 /*
 886  * Wakeup all threads waiting on the specified ident that slept using
 887  * the specified domain, on all cpus.
 888  */
 889 void
 890 wakeup_domain(void *ident, int domain)
 891 {
 892     _wakeup(ident, PWAKEUP_ENCODE(domain, mycpu->gd_cpuid));
 893 }
 894
 895 /*
 896  * Wakeup one thread waiting on the specified ident that slept using
 897  * the specified  domain, on any cpu.
 898  */
 899 void
 900 wakeup_domain_one(void *ident, int domain)
 901 {
 902     /* XXX potentially round-robin the first responding cpu */
 903     _wakeup(ident, PWAKEUP_ENCODE(domain, mycpu->gd_cpuid) | PWAKEUP_ONE);
 904 }
 905
 906 /*
 907  * setrunnable()
 908  *
 909  * Make a process runnable.  The MP lock must be held on call.  This only
 910  * has an effect if we are in SSLEEP.  We only break out of the
 911  * tsleep if LWP_BREAKTSLEEP is set, otherwise we just fix-up the state.
 912  *
 913  * NOTE: With the MP lock held we can only safely manipulate the process
 914  * structure.  We cannot safely manipulate the thread structure.
 915  */
 916 void
 917 setrunnable(struct lwp *lp)
 918 {
 919         crit_enter();
 920         ASSERT_MP_LOCK_HELD(curthread);
 921         if (lp->lwp_stat == LSSTOP)
 922                 lp->lwp_stat = LSSLEEP;
 923         if (lp->lwp_stat == LSSLEEP && (lp->lwp_flag & LWP_BREAKTSLEEP))
 924                 unsleep_and_wakeup_thread(lp->lwp_thread);
 925         crit_exit();
 926 }
 927
 928 /*
 929  * The process is stopped due to some condition, usually because p_stat is
 930  * set to SSTOP, but also possibly due to being traced.
 931  *
 932  * NOTE!  If the caller sets SSTOP, the caller must also clear P_WAITED
 933  * because the parent may check the child's status before the child actually
 934  * gets to this routine.
 935  *
 936  * This routine is called with the current lwp only, typically just
 937  * before returning to userland.
 938  *
 939  * Setting LWP_BREAKTSLEEP before entering the tsleep will cause a passive
 940  * SIGCONT to break out of the tsleep.
 941  */
 942 void
 943 tstop(void)
 944 {
 945         struct lwp *lp = curthread->td_lwp;
 946         struct proc *p = lp->lwp_proc;
 947
 948         lp->lwp_flag |= LWP_BREAKTSLEEP;
 949         lp->lwp_stat = LSSTOP;
 950         crit_enter();
 951         /*
 952          * If LWP_WSTOP is set, we were sleeping
 953          * while our process was stopped.  At this point
 954          * we were already counted as stopped.
 955          */
 956         if ((lp->lwp_flag & LWP_WSTOP) == 0) {
 957                 /*
 958                  * If we're the last thread to stop, signal
 959                  * our parent.
 960                  */
 961                 p->p_nstopped++;
 962                 lp->lwp_flag |= LWP_WSTOP;
 963                 if (p->p_nstopped == p->p_nthreads) {
 964                         p->p_flag &= ~P_WAITED;
 965                         wakeup(p->p_pptr);
 966                         if ((p->p_pptr->p_sigacts->ps_flag & PS_NOCLDSTOP) == 0)
 967                                 ksignal(p->p_pptr, SIGCHLD);
 968                 }
 969         }
 970         tsleep(lp->lwp_proc, 0, "stop", 0);
 971         p->p_nstopped--;
 972         crit_exit();
 973 }
 974
 975 /*
 976  * Yield / synchronous reschedule.  This is a bit tricky because the trap
 977  * code might have set a lazy release on the switch function.   Setting
 978  * P_PASSIVE_ACQ will ensure that the lazy release executes when we call
 979  * switch, and that we are given a greater chance of affinity with our
 980  * current cpu.
 981  *
 982  * We call lwkt_setpri_self() to rotate our thread to the end of the lwkt
 983  * run queue.  lwkt_switch() will also execute any assigned passive release
 984  * (which usually calls release_curproc()), allowing a same/higher priority
 985  * process to be designated as the current process.
 986  *
 987  * While it is possible for a lower priority process to be designated,
 988  * it's call to lwkt_maybe_switch() in acquire_curproc() will likely
 989  * round-robin back to us and we will be able to re-acquire the current
 990  * process designation.
 991  */
 992 void
 993 uio_yield(void)
 994 {
 995         struct thread *td = curthread;
 996         struct proc *p = td->td_proc;
 997
 998         lwkt_setpri_self(td->td_pri & TDPRI_MASK);
 999         if (p) {
1000                 p->p_flag |= P_PASSIVE_ACQ;
1001                 lwkt_switch();
1002                 p->p_flag &= ~P_PASSIVE_ACQ;
1003         } else {
1004                 lwkt_switch();
1005         }
1006 }
1007
1008 /*
1009  * Compute a tenex style load average of a quantity on
1010  * 1, 5 and 15 minute intervals.
1011  */
1012 static int loadav_count_runnable(struct lwp *p, void *data);
1013
1014 static void
1015 loadav(void *arg)
1016 {
1017         struct loadavg *avg;
1018         int i, nrun;
1019
1020         nrun = 0;
1021         alllwp_scan(loadav_count_runnable, &nrun);
1022         avg = &averunnable;
1023         for (i = 0; i < 3; i++) {
1024                 avg->ldavg[i] = (cexp[i] * avg->ldavg[i] +
1025                     nrun * FSCALE * (FSCALE - cexp[i])) >> FSHIFT;
1026         }
1027
1028         /*
1029          * Schedule the next update to occur after 5 seconds, but add a
1030          * random variation to avoid synchronisation with processes that
1031          * run at regular intervals.
1032          */
1033         callout_reset(&loadav_callout, hz * 4 + (int)(krandom() % (hz * 2 + 1)),
1034                       loadav, NULL);
1035 }
1036
1037 static int
1038 loadav_count_runnable(struct lwp *lp, void *data)
1039 {
1040         int *nrunp = data;
1041         thread_t td;
1042
1043         switch (lp->lwp_stat) {
1044         case LSRUN:
1045                 if ((td = lp->lwp_thread) == NULL)
1046                         break;
1047                 if (td->td_flags & TDF_BLOCKED)
1048                         break;
1049                 ++*nrunp;
1050                 break;
1051         default:
1052                 break;
1053         }
1054         return(0);
1055 }
1056
1057 /* ARGSUSED */
1058 static void
1059 sched_setup(void *dummy)
1060 {
1061         callout_init(&loadav_callout);
1062         callout_init(&schedcpu_callout);
1063
1064         /* Kick off timeout driven events by calling first time. */
1065         schedcpu(NULL);
1066         loadav(NULL);
1067 }
1068