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