sys/kern/sched_4bsd.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  * 4. Neither the name of the University nor the names of its contributors
  19  *    may be used to endorse or promote products derived from this software
  20  *    without specific prior written permission.
  21  *
  22  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  23  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  24  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  25  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  26  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  27  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  28  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  29  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  30  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  31  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  32  * SUCH DAMAGE.
  33  */
  34
  35 #include <sys/cdefs.h>
  36 __FBSDID("$FreeBSD$");
  37
  38 #include "opt_hwpmc_hooks.h"
  39 #include "opt_sched.h"
  40 #include "opt_kdtrace.h"
  41
  42 #include <sys/param.h>
  43 #include <sys/systm.h>
  44 #include <sys/cpuset.h>
  45 #include <sys/kernel.h>
  46 #include <sys/ktr.h>
  47 #include <sys/lock.h>
  48 #include <sys/kthread.h>
  49 #include <sys/mutex.h>
  50 #include <sys/proc.h>
  51 #include <sys/resourcevar.h>
  52 #include <sys/sched.h>
  53 #include <sys/smp.h>
  54 #include <sys/sysctl.h>
  55 #include <sys/sx.h>
  56 #include <sys/turnstile.h>
  57 #include <sys/umtx.h>
  58 #include <machine/pcb.h>
  59 #include <machine/smp.h>
  60
  61 #ifdef HWPMC_HOOKS
  62 #include <sys/pmckern.h>
  63 #endif
  64
  65 #ifdef KDTRACE_HOOKS
  66 #include <sys/dtrace_bsd.h>
  67 int                             dtrace_vtime_active;
  68 dtrace_vtime_switch_func_t      dtrace_vtime_switch_func;
  69 #endif
  70
  71 /*
  72  * INVERSE_ESTCPU_WEIGHT is only suitable for statclock() frequencies in
  73  * the range 100-256 Hz (approximately).
  74  */
  75 #define ESTCPULIM(e) \
  76     min((e), INVERSE_ESTCPU_WEIGHT * (NICE_WEIGHT * (PRIO_MAX - PRIO_MIN) - \
  77     RQ_PPQ) + INVERSE_ESTCPU_WEIGHT - 1)
  78 #ifdef SMP
  79 #define INVERSE_ESTCPU_WEIGHT   (8 * smp_cpus)
  80 #else
  81 #define INVERSE_ESTCPU_WEIGHT   8       /* 1 / (priorities per estcpu level). */
  82 #endif
  83 #define NICE_WEIGHT             1       /* Priorities per nice level. */
  84
  85 #define TS_NAME_LEN (MAXCOMLEN + sizeof(" td ") + sizeof(__XSTRING(UINT_MAX)))
  86
  87 /*
  88  * The schedulable entity that runs a context.
  89  * This is  an extension to the thread structure and is tailored to
  90  * the requirements of this scheduler
  91  */
  92 struct td_sched {
  93         fixpt_t         ts_pctcpu;      /* (j) %cpu during p_swtime. */
  94         int             ts_cpticks;     /* (j) Ticks of cpu time. */
  95         int             ts_slptime;     /* (j) Seconds !RUNNING. */
  96         int             ts_flags;
  97         struct runq     *ts_runq;       /* runq the thread is currently on */
  98 #ifdef KTR
  99         char            ts_name[TS_NAME_LEN];
 100 #endif
 101 };
 102
 103 /* flags kept in td_flags */
 104 #define TDF_DIDRUN      TDF_SCHED0      /* thread actually ran. */
 105 #define TDF_BOUND       TDF_SCHED1      /* Bound to one CPU. */
 106
 107 /* flags kept in ts_flags */
 108 #define TSF_AFFINITY    0x0001          /* Has a non-"full" CPU set. */
 109
 110 #define SKE_RUNQ_PCPU(ts)                                               \
 111     ((ts)->ts_runq != 0 && (ts)->ts_runq != &runq)
 112
 113 #define THREAD_CAN_SCHED(td, cpu)       \
 114     CPU_ISSET((cpu), &(td)->td_cpuset->cs_mask)
 115
 116 static struct td_sched td_sched0;
 117 struct mtx sched_lock;
 118
 119 static int      sched_tdcnt;    /* Total runnable threads in the system. */
 120 static int      sched_quantum;  /* Roundrobin scheduling quantum in ticks. */
 121 #define SCHED_QUANTUM   (hz / 10)       /* Default sched quantum */
 122
 123 static void     setup_runqs(void);
 124 static void     schedcpu(void);
 125 static void     schedcpu_thread(void);
 126 static void     sched_priority(struct thread *td, u_char prio);
 127 static void     sched_setup(void *dummy);
 128 static void     maybe_resched(struct thread *td);
 129 static void     updatepri(struct thread *td);
 130 static void     resetpriority(struct thread *td);
 131 static void     resetpriority_thread(struct thread *td);
 132 #ifdef SMP
 133 static int      sched_pickcpu(struct thread *td);
 134 static int      forward_wakeup(int cpunum);
 135 static void     kick_other_cpu(int pri, int cpuid);
 136 #endif
 137
 138 static struct kproc_desc sched_kp = {
 139         "schedcpu",
 140         schedcpu_thread,
 141         NULL
 142 };
 143 SYSINIT(schedcpu, SI_SUB_RUN_SCHEDULER, SI_ORDER_FIRST, kproc_start,
 144     &sched_kp);
 145 SYSINIT(sched_setup, SI_SUB_RUN_QUEUE, SI_ORDER_FIRST, sched_setup, NULL);
 146
 147 /*
 148  * Global run queue.
 149  */
 150 static struct runq runq;
 151
 152 #ifdef SMP
 153 /*
 154  * Per-CPU run queues
 155  */
 156 static struct runq runq_pcpu[MAXCPU];
 157 long runq_length[MAXCPU];
 158
 159 static cpumask_t idle_cpus_mask;
 160 #endif
 161
 162 struct pcpuidlestat {
 163         u_int idlecalls;
 164         u_int oldidlecalls;
 165 };
 166 static DPCPU_DEFINE(struct pcpuidlestat, idlestat);
 167
 168 static void
 169 setup_runqs(void)
 170 {
 171 #ifdef SMP
 172         int i;
 173
 174         for (i = 0; i < MAXCPU; ++i)
 175                 runq_init(&runq_pcpu[i]);
 176 #endif
 177
 178         runq_init(&runq);
 179 }
 180
 181 static int
 182 sysctl_kern_quantum(SYSCTL_HANDLER_ARGS)
 183 {
 184         int error, new_val;
 185
 186         new_val = sched_quantum * tick;
 187         error = sysctl_handle_int(oidp, &new_val, 0, req);
 188         if (error != 0 || req->newptr == NULL)
 189                 return (error);
 190         if (new_val < tick)
 191                 return (EINVAL);
 192         sched_quantum = new_val / tick;
 193         hogticks = 2 * sched_quantum;
 194         return (0);
 195 }
 196
 197 SYSCTL_NODE(_kern, OID_AUTO, sched, CTLFLAG_RD, 0, "Scheduler");
 198
 199 SYSCTL_STRING(_kern_sched, OID_AUTO, name, CTLFLAG_RD, "4BSD", 0,
 200     "Scheduler name");
 201
 202 SYSCTL_PROC(_kern_sched, OID_AUTO, quantum, CTLTYPE_INT | CTLFLAG_RW,
 203     0, sizeof sched_quantum, sysctl_kern_quantum, "I",
 204     "Roundrobin scheduling quantum in microseconds");
 205
 206 #ifdef SMP
 207 /* Enable forwarding of wakeups to all other cpus */
 208 SYSCTL_NODE(_kern_sched, OID_AUTO, ipiwakeup, CTLFLAG_RD, NULL, "Kernel SMP");
 209
 210 static int runq_fuzz = 1;
 211 SYSCTL_INT(_kern_sched, OID_AUTO, runq_fuzz, CTLFLAG_RW, &runq_fuzz, 0, "");
 212
 213 static int forward_wakeup_enabled = 1;
 214 SYSCTL_INT(_kern_sched_ipiwakeup, OID_AUTO, enabled, CTLFLAG_RW,
 215            &forward_wakeup_enabled, 0,
 216            "Forwarding of wakeup to idle CPUs");
 217
 218 static int forward_wakeups_requested = 0;
 219 SYSCTL_INT(_kern_sched_ipiwakeup, OID_AUTO, requested, CTLFLAG_RD,
 220            &forward_wakeups_requested, 0,
 221            "Requests for Forwarding of wakeup to idle CPUs");
 222
 223 static int forward_wakeups_delivered = 0;
 224 SYSCTL_INT(_kern_sched_ipiwakeup, OID_AUTO, delivered, CTLFLAG_RD,
 225            &forward_wakeups_delivered, 0,
 226            "Completed Forwarding of wakeup to idle CPUs");
 227
 228 static int forward_wakeup_use_mask = 1;
 229 SYSCTL_INT(_kern_sched_ipiwakeup, OID_AUTO, usemask, CTLFLAG_RW,
 230            &forward_wakeup_use_mask, 0,
 231            "Use the mask of idle cpus");
 232
 233 static int forward_wakeup_use_loop = 0;
 234 SYSCTL_INT(_kern_sched_ipiwakeup, OID_AUTO, useloop, CTLFLAG_RW,
 235            &forward_wakeup_use_loop, 0,
 236            "Use a loop to find idle cpus");
 237
 238 #endif
 239 #if 0
 240 static int sched_followon = 0;
 241 SYSCTL_INT(_kern_sched, OID_AUTO, followon, CTLFLAG_RW,
 242            &sched_followon, 0,
 243            "allow threads to share a quantum");
 244 #endif
 245
 246 static __inline void
 247 sched_load_add(void)
 248 {
 249
 250         sched_tdcnt++;
 251         KTR_COUNTER0(KTR_SCHED, "load", "global load", sched_tdcnt);
 252 }
 253
 254 static __inline void
 255 sched_load_rem(void)
 256 {
 257
 258         sched_tdcnt--;
 259         KTR_COUNTER0(KTR_SCHED, "load", "global load", sched_tdcnt);
 260 }
 261 /*
 262  * Arrange to reschedule if necessary, taking the priorities and
 263  * schedulers into account.
 264  */
 265 static void
 266 maybe_resched(struct thread *td)
 267 {
 268
 269         THREAD_LOCK_ASSERT(td, MA_OWNED);
 270         if (td->td_priority < curthread->td_priority)
 271                 curthread->td_flags |= TDF_NEEDRESCHED;
 272 }
 273
 274 /*
 275  * This function is called when a thread is about to be put on run queue
 276  * because it has been made runnable or its priority has been adjusted.  It
 277  * determines if the new thread should be immediately preempted to.  If so,
 278  * it switches to it and eventually returns true.  If not, it returns false
 279  * so that the caller may place the thread on an appropriate run queue.
 280  */
 281 int
 282 maybe_preempt(struct thread *td)
 283 {
 284 #ifdef PREEMPTION
 285         struct thread *ctd;
 286         int cpri, pri;
 287
 288         /*
 289          * The new thread should not preempt the current thread if any of the
 290          * following conditions are true:
 291          *
 292          *  - The kernel is in the throes of crashing (panicstr).
 293          *  - The current thread has a higher (numerically lower) or
 294          *    equivalent priority.  Note that this prevents curthread from
 295          *    trying to preempt to itself.
 296          *  - It is too early in the boot for context switches (cold is set).
 297          *  - The current thread has an inhibitor set or is in the process of
 298          *    exiting.  In this case, the current thread is about to switch
 299          *    out anyways, so there's no point in preempting.  If we did,
 300          *    the current thread would not be properly resumed as well, so
 301          *    just avoid that whole landmine.
 302          *  - If the new thread's priority is not a realtime priority and
 303          *    the current thread's priority is not an idle priority and
 304          *    FULL_PREEMPTION is disabled.
 305          *
 306          * If all of these conditions are false, but the current thread is in
 307          * a nested critical section, then we have to defer the preemption
 308          * until we exit the critical section.  Otherwise, switch immediately
 309          * to the new thread.
 310          */
 311         ctd = curthread;
 312         THREAD_LOCK_ASSERT(td, MA_OWNED);
 313         KASSERT((td->td_inhibitors == 0),
 314                         ("maybe_preempt: trying to run inhibited thread"));
 315         pri = td->td_priority;
 316         cpri = ctd->td_priority;
 317         if (panicstr != NULL || pri >= cpri || cold /* || dumping */ ||
 318             TD_IS_INHIBITED(ctd))
 319                 return (0);
 320 #ifndef FULL_PREEMPTION
 321         if (pri > PRI_MAX_ITHD && cpri < PRI_MIN_IDLE)
 322                 return (0);
 323 #endif
 324
 325         if (ctd->td_critnest > 1) {
 326                 CTR1(KTR_PROC, "maybe_preempt: in critical section %d",
 327                     ctd->td_critnest);
 328                 ctd->td_owepreempt = 1;
 329                 return (0);
 330         }
 331         /*
 332          * Thread is runnable but not yet put on system run queue.
 333          */
 334         MPASS(ctd->td_lock == td->td_lock);
 335         MPASS(TD_ON_RUNQ(td));
 336         TD_SET_RUNNING(td);
 337         CTR3(KTR_PROC, "preempting to thread %p (pid %d, %s)\n", td,
 338             td->td_proc->p_pid, td->td_name);
 339         mi_switch(SW_INVOL | SW_PREEMPT | SWT_PREEMPT, td);
 340         /*
 341          * td's lock pointer may have changed.  We have to return with it
 342          * locked.
 343          */
 344         spinlock_enter();
 345         thread_unlock(ctd);
 346         thread_lock(td);
 347         spinlock_exit();
 348         return (1);
 349 #else
 350         return (0);
 351 #endif
 352 }
 353
 354 /*
 355  * Constants for digital decay and forget:
 356  *      90% of (td_estcpu) usage in 5 * loadav time
 357  *      95% of (ts_pctcpu) usage in 60 seconds (load insensitive)
 358  *          Note that, as ps(1) mentions, this can let percentages
 359  *          total over 100% (I've seen 137.9% for 3 processes).
 360  *
 361  * Note that schedclock() updates td_estcpu and p_cpticks asynchronously.
 362  *
 363  * We wish to decay away 90% of td_estcpu in (5 * loadavg) seconds.
 364  * That is, the system wants to compute a value of decay such
 365  * that the following for loop:
 366  *      for (i = 0; i < (5 * loadavg); i++)
 367  *              td_estcpu *= decay;
 368  * will compute
 369  *      td_estcpu *= 0.1;
 370  * for all values of loadavg:
 371  *
 372  * Mathematically this loop can be expressed by saying:
 373  *      decay ** (5 * loadavg) ~= .1
 374  *
 375  * The system computes decay as:
 376  *      decay = (2 * loadavg) / (2 * loadavg + 1)
 377  *
 378  * We wish to prove that the system's computation of decay
 379  * will always fulfill the equation:
 380  *      decay ** (5 * loadavg) ~= .1
 381  *
 382  * If we compute b as:
 383  *      b = 2 * loadavg
 384  * then
 385  *      decay = b / (b + 1)
 386  *
 387  * We now need to prove two things:
 388  *      1) Given factor ** (5 * loadavg) ~= .1, prove factor == b/(b+1)
 389  *      2) Given b/(b+1) ** power ~= .1, prove power == (5 * loadavg)
 390  *
 391  * Facts:
 392  *         For x close to zero, exp(x) =~ 1 + x, since
 393  *              exp(x) = 0! + x**1/1! + x**2/2! + ... .
 394  *              therefore exp(-1/b) =~ 1 - (1/b) = (b-1)/b.
 395  *         For x close to zero, ln(1+x) =~ x, since
 396  *              ln(1+x) = x - x**2/2 + x**3/3 - ...     -1 < x < 1
 397  *              therefore ln(b/(b+1)) = ln(1 - 1/(b+1)) =~ -1/(b+1).
 398  *         ln(.1) =~ -2.30
 399  *
 400  * Proof of (1):
 401  *    Solve (factor)**(power) =~ .1 given power (5*loadav):
 402  *      solving for factor,
 403  *      ln(factor) =~ (-2.30/5*loadav), or
 404  *      factor =~ exp(-1/((5/2.30)*loadav)) =~ exp(-1/(2*loadav)) =
 405  *          exp(-1/b) =~ (b-1)/b =~ b/(b+1).                    QED
 406  *
 407  * Proof of (2):
 408  *    Solve (factor)**(power) =~ .1 given factor == (b/(b+1)):
 409  *      solving for power,
 410  *      power*ln(b/(b+1)) =~ -2.30, or
 411  *      power =~ 2.3 * (b + 1) = 4.6*loadav + 2.3 =~ 5*loadav.  QED
 412  *
 413  * Actual power values for the implemented algorithm are as follows:
 414  *      loadav: 1       2       3       4
 415  *      power:  5.68    10.32   14.94   19.55
 416  */
 417
 418 /* calculations for digital decay to forget 90% of usage in 5*loadav sec */
 419 #define loadfactor(loadav)      (2 * (loadav))
 420 #define decay_cpu(loadfac, cpu) (((loadfac) * (cpu)) / ((loadfac) + FSCALE))
 421
 422 /* decay 95% of `ts_pctcpu' in 60 seconds; see CCPU_SHIFT before changing */
 423 static fixpt_t  ccpu = 0.95122942450071400909 * FSCALE; /* exp(-1/20) */
 424 SYSCTL_UINT(_kern, OID_AUTO, ccpu, CTLFLAG_RD, &ccpu, 0, "");
 425
 426 /*
 427  * If `ccpu' is not equal to `exp(-1/20)' and you still want to use the
 428  * faster/more-accurate formula, you'll have to estimate CCPU_SHIFT below
 429  * and possibly adjust FSHIFT in "param.h" so that (FSHIFT >= CCPU_SHIFT).
 430  *
 431  * To estimate CCPU_SHIFT for exp(-1/20), the following formula was used:
 432  *      1 - exp(-1/20) ~= 0.0487 ~= 0.0488 == 1 (fixed pt, *11* bits).
 433  *
 434  * If you don't want to bother with the faster/more-accurate formula, you
 435  * can set CCPU_SHIFT to (FSHIFT + 1) which will use a slower/less-accurate
 436  * (more general) method of calculating the %age of CPU used by a process.
 437  */
 438 #define CCPU_SHIFT      11
 439
 440 /*
 441  * Recompute process priorities, every hz ticks.
 442  * MP-safe, called without the Giant mutex.
 443  */
 444 /* ARGSUSED */
 445 static void
 446 schedcpu(void)
 447 {
 448         register fixpt_t loadfac = loadfactor(averunnable.ldavg[0]);
 449         struct thread *td;
 450         struct proc *p;
 451         struct td_sched *ts;
 452         int awake, realstathz;
 453
 454         realstathz = stathz ? stathz : hz;
 455         sx_slock(&allproc_lock);
 456         FOREACH_PROC_IN_SYSTEM(p) {
 457                 PROC_LOCK(p);
 458                 if (p->p_state == PRS_NEW) {
 459                         PROC_UNLOCK(p);
 460                         continue;
 461                 }
 462                 FOREACH_THREAD_IN_PROC(p, td) {
 463                         awake = 0;
 464                         thread_lock(td);
 465                         ts = td->td_sched;
 466                         /*
 467                          * Increment sleep time (if sleeping).  We
 468                          * ignore overflow, as above.
 469                          */
 470                         /*
 471                          * The td_sched slptimes are not touched in wakeup
 472                          * because the thread may not HAVE everything in
 473                          * memory? XXX I think this is out of date.
 474                          */
 475                         if (TD_ON_RUNQ(td)) {
 476                                 awake = 1;
 477                                 td->td_flags &= ~TDF_DIDRUN;
 478                         } else if (TD_IS_RUNNING(td)) {
 479                                 awake = 1;
 480                                 /* Do not clear TDF_DIDRUN */
 481                         } else if (td->td_flags & TDF_DIDRUN) {
 482                                 awake = 1;
 483                                 td->td_flags &= ~TDF_DIDRUN;
 484                         }
 485
 486                         /*
 487                          * ts_pctcpu is only for ps and ttyinfo().
 488                          */
 489                         ts->ts_pctcpu = (ts->ts_pctcpu * ccpu) >> FSHIFT;
 490                         /*
 491                          * If the td_sched has been idle the entire second,
 492                          * stop recalculating its priority until
 493                          * it wakes up.
 494                          */
 495                         if (ts->ts_cpticks != 0) {
 496 #if     (FSHIFT >= CCPU_SHIFT)
 497                                 ts->ts_pctcpu += (realstathz == 100)
 498                                     ? ((fixpt_t) ts->ts_cpticks) <<
 499                                     (FSHIFT - CCPU_SHIFT) :
 500                                     100 * (((fixpt_t) ts->ts_cpticks)
 501                                     << (FSHIFT - CCPU_SHIFT)) / realstathz;
 502 #else
 503                                 ts->ts_pctcpu += ((FSCALE - ccpu) *
 504                                     (ts->ts_cpticks *
 505                                     FSCALE / realstathz)) >> FSHIFT;
 506 #endif
 507                                 ts->ts_cpticks = 0;
 508                         }
 509                         /*
 510                          * If there are ANY running threads in this process,
 511                          * then don't count it as sleeping.
 512                          * XXX: this is broken.
 513                          */
 514                         if (awake) {
 515                                 if (ts->ts_slptime > 1) {
 516                                         /*
 517                                          * In an ideal world, this should not
 518                                          * happen, because whoever woke us
 519                                          * up from the long sleep should have
 520                                          * unwound the slptime and reset our
 521                                          * priority before we run at the stale
 522                                          * priority.  Should KASSERT at some
 523                                          * point when all the cases are fixed.
 524                                          */
 525                                         updatepri(td);
 526                                 }
 527                                 ts->ts_slptime = 0;
 528                         } else
 529                                 ts->ts_slptime++;
 530                         if (ts->ts_slptime > 1) {
 531                                 thread_unlock(td);
 532                                 continue;
 533                         }
 534                         td->td_estcpu = decay_cpu(loadfac, td->td_estcpu);
 535                         resetpriority(td);
 536                         resetpriority_thread(td);
 537                         thread_unlock(td);
 538                 }
 539                 PROC_UNLOCK(p);
 540         }
 541         sx_sunlock(&allproc_lock);
 542 }
 543
 544 /*
 545  * Main loop for a kthread that executes schedcpu once a second.
 546  */
 547 static void
 548 schedcpu_thread(void)
 549 {
 550
 551         for (;;) {
 552                 schedcpu();
 553                 pause("-", hz);
 554         }
 555 }
 556
 557 /*
 558  * Recalculate the priority of a process after it has slept for a while.
 559  * For all load averages >= 1 and max td_estcpu of 255, sleeping for at
 560  * least six times the loadfactor will decay td_estcpu to zero.
 561  */
 562 static void
 563 updatepri(struct thread *td)
 564 {
 565         struct td_sched *ts;
 566         fixpt_t loadfac;
 567         unsigned int newcpu;
 568
 569         ts = td->td_sched;
 570         loadfac = loadfactor(averunnable.ldavg[0]);
 571         if (ts->ts_slptime > 5 * loadfac)
 572                 td->td_estcpu = 0;
 573         else {
 574                 newcpu = td->td_estcpu;
 575                 ts->ts_slptime--;       /* was incremented in schedcpu() */
 576                 while (newcpu && --ts->ts_slptime)
 577                         newcpu = decay_cpu(loadfac, newcpu);
 578                 td->td_estcpu = newcpu;
 579         }
 580 }
 581
 582 /*
 583  * Compute the priority of a process when running in user mode.
 584  * Arrange to reschedule if the resulting priority is better
 585  * than that of the current process.
 586  */
 587 static void
 588 resetpriority(struct thread *td)
 589 {
 590         register unsigned int newpriority;
 591
 592         if (td->td_pri_class == PRI_TIMESHARE) {
 593                 newpriority = PUSER + td->td_estcpu / INVERSE_ESTCPU_WEIGHT +
 594                     NICE_WEIGHT * (td->td_proc->p_nice - PRIO_MIN);
 595                 newpriority = min(max(newpriority, PRI_MIN_TIMESHARE),
 596                     PRI_MAX_TIMESHARE);
 597                 sched_user_prio(td, newpriority);
 598         }
 599 }
 600
 601 /*
 602  * Update the thread's priority when the associated process's user
 603  * priority changes.
 604  */
 605 static void
 606 resetpriority_thread(struct thread *td)
 607 {
 608
 609         /* Only change threads with a time sharing user priority. */
 610         if (td->td_priority < PRI_MIN_TIMESHARE ||
 611             td->td_priority > PRI_MAX_TIMESHARE)
 612                 return;
 613
 614         /* XXX the whole needresched thing is broken, but not silly. */
 615         maybe_resched(td);
 616
 617         sched_prio(td, td->td_user_pri);
 618 }
 619
 620 /* ARGSUSED */
 621 static void
 622 sched_setup(void *dummy)
 623 {
 624         setup_runqs();
 625
 626         if (sched_quantum == 0)
 627                 sched_quantum = SCHED_QUANTUM;
 628         hogticks = 2 * sched_quantum;
 629
 630         /* Account for thread0. */
 631         sched_load_add();
 632 }
 633
 634 /* External interfaces start here */
 635
 636 /*
 637  * Very early in the boot some setup of scheduler-specific
 638  * parts of proc0 and of some scheduler resources needs to be done.
 639  * Called from:
 640  *  proc0_init()
 641  */
 642 void
 643 schedinit(void)
 644 {
 645         /*
 646          * Set up the scheduler specific parts of proc0.
 647          */
 648         proc0.p_sched = NULL; /* XXX */
 649         thread0.td_sched = &td_sched0;
 650         thread0.td_lock = &sched_lock;
 651         mtx_init(&sched_lock, "sched lock", NULL, MTX_SPIN | MTX_RECURSE);
 652 }
 653
 654 int
 655 sched_runnable(void)
 656 {
 657 #ifdef SMP
 658         return runq_check(&runq) + runq_check(&runq_pcpu[PCPU_GET(cpuid)]);
 659 #else
 660         return runq_check(&runq);
 661 #endif
 662 }
 663
 664 int
 665 sched_rr_interval(void)
 666 {
 667         if (sched_quantum == 0)
 668                 sched_quantum = SCHED_QUANTUM;
 669         return (sched_quantum);
 670 }
 671
 672 /*
 673  * We adjust the priority of the current process.  The priority of
 674  * a process gets worse as it accumulates CPU time.  The cpu usage
 675  * estimator (td_estcpu) is increased here.  resetpriority() will
 676  * compute a different priority each time td_estcpu increases by
 677  * INVERSE_ESTCPU_WEIGHT
 678  * (until MAXPRI is reached).  The cpu usage estimator ramps up
 679  * quite quickly when the process is running (linearly), and decays
 680  * away exponentially, at a rate which is proportionally slower when
 681  * the system is busy.  The basic principle is that the system will
 682  * 90% forget that the process used a lot of CPU time in 5 * loadav
 683  * seconds.  This causes the system to favor processes which haven't
 684  * run much recently, and to round-robin among other processes.
 685  */
 686 void
 687 sched_clock(struct thread *td)
 688 {
 689         struct pcpuidlestat *stat;
 690         struct td_sched *ts;
 691
 692         THREAD_LOCK_ASSERT(td, MA_OWNED);
 693         ts = td->td_sched;
 694
 695         ts->ts_cpticks++;
 696         td->td_estcpu = ESTCPULIM(td->td_estcpu + 1);
 697         if ((td->td_estcpu % INVERSE_ESTCPU_WEIGHT) == 0) {
 698                 resetpriority(td);
 699                 resetpriority_thread(td);
 700         }
 701
 702         /*
 703          * Force a context switch if the current thread has used up a full
 704          * quantum (default quantum is 100ms).
 705          */
 706         if (!TD_IS_IDLETHREAD(td) &&
 707             ticks - PCPU_GET(switchticks) >= sched_quantum)
 708                 td->td_flags |= TDF_NEEDRESCHED;
 709
 710         stat = DPCPU_PTR(idlestat);
 711         stat->oldidlecalls = stat->idlecalls;
 712         stat->idlecalls = 0;
 713 }
 714
 715 /*
 716  * Charge child's scheduling CPU usage to parent.
 717  */
 718 void
 719 sched_exit(struct proc *p, struct thread *td)
 720 {
 721
 722         KTR_STATE1(KTR_SCHED, "thread", sched_tdname(td), "proc exit",
 723             "prio:td", td->td_priority);
 724
 725         PROC_LOCK_ASSERT(p, MA_OWNED);
 726         sched_exit_thread(FIRST_THREAD_IN_PROC(p), td);
 727 }
 728
 729 void
 730 sched_exit_thread(struct thread *td, struct thread *child)
 731 {
 732
 733         KTR_STATE1(KTR_SCHED, "thread", sched_tdname(child), "exit",
 734             "prio:td", child->td_priority);
 735         thread_lock(td);
 736         td->td_estcpu = ESTCPULIM(td->td_estcpu + child->td_estcpu);
 737         thread_unlock(td);
 738         thread_lock(child);
 739         if ((child->td_flags & TDF_NOLOAD) == 0)
 740                 sched_load_rem();
 741         thread_unlock(child);
 742 }
 743
 744 void
 745 sched_fork(struct thread *td, struct thread *childtd)
 746 {
 747         sched_fork_thread(td, childtd);
 748 }
 749
 750 void
 751 sched_fork_thread(struct thread *td, struct thread *childtd)
 752 {
 753         struct td_sched *ts;
 754
 755         childtd->td_estcpu = td->td_estcpu;
 756         childtd->td_lock = &sched_lock;
 757         childtd->td_cpuset = cpuset_ref(td->td_cpuset);
 758         childtd->td_priority = childtd->td_base_pri;
 759         ts = childtd->td_sched;
 760         bzero(ts, sizeof(*ts));
 761         ts->ts_flags |= (td->td_sched->ts_flags & TSF_AFFINITY);
 762 }
 763
 764 void
 765 sched_nice(struct proc *p, int nice)
 766 {
 767         struct thread *td;
 768
 769         PROC_LOCK_ASSERT(p, MA_OWNED);
 770         p->p_nice = nice;
 771         FOREACH_THREAD_IN_PROC(p, td) {
 772                 thread_lock(td);
 773                 resetpriority(td);
 774                 resetpriority_thread(td);
 775                 thread_unlock(td);
 776         }
 777 }
 778
 779 void
 780 sched_class(struct thread *td, int class)
 781 {
 782         THREAD_LOCK_ASSERT(td, MA_OWNED);
 783         td->td_pri_class = class;
 784 }
 785
 786 /*
 787  * Adjust the priority of a thread.
 788  */
 789 static void
 790 sched_priority(struct thread *td, u_char prio)
 791 {
 792
 793
 794         KTR_POINT3(KTR_SCHED, "thread", sched_tdname(td), "priority change",
 795             "prio:%d", td->td_priority, "new prio:%d", prio, KTR_ATTR_LINKED,
 796             sched_tdname(curthread));
 797         if (td != curthread && prio > td->td_priority) {
 798                 KTR_POINT3(KTR_SCHED, "thread", sched_tdname(curthread),
 799                     "lend prio", "prio:%d", td->td_priority, "new prio:%d",
 800                     prio, KTR_ATTR_LINKED, sched_tdname(td));
 801         }
 802         THREAD_LOCK_ASSERT(td, MA_OWNED);
 803         if (td->td_priority == prio)
 804                 return;
 805         td->td_priority = prio;
 806         if (TD_ON_RUNQ(td) && td->td_rqindex != (prio / RQ_PPQ)) {
 807                 sched_rem(td);
 808                 sched_add(td, SRQ_BORING);
 809         }
 810 }
 811
 812 /*
 813  * Update a thread's priority when it is lent another thread's
 814  * priority.
 815  */
 816 void
 817 sched_lend_prio(struct thread *td, u_char prio)
 818 {
 819
 820         td->td_flags |= TDF_BORROWING;
 821         sched_priority(td, prio);
 822 }
 823
 824 /*
 825  * Restore a thread's priority when priority propagation is
 826  * over.  The prio argument is the minimum priority the thread
 827  * needs to have to satisfy other possible priority lending
 828  * requests.  If the thread's regulary priority is less
 829  * important than prio the thread will keep a priority boost
 830  * of prio.
 831  */
 832 void
 833 sched_unlend_prio(struct thread *td, u_char prio)
 834 {
 835         u_char base_pri;
 836
 837         if (td->td_base_pri >= PRI_MIN_TIMESHARE &&
 838             td->td_base_pri <= PRI_MAX_TIMESHARE)
 839                 base_pri = td->td_user_pri;
 840         else
 841                 base_pri = td->td_base_pri;
 842         if (prio >= base_pri) {
 843                 td->td_flags &= ~TDF_BORROWING;
 844                 sched_prio(td, base_pri);
 845         } else
 846                 sched_lend_prio(td, prio);
 847 }
 848
 849 void
 850 sched_prio(struct thread *td, u_char prio)
 851 {
 852         u_char oldprio;
 853
 854         /* First, update the base priority. */
 855         td->td_base_pri = prio;
 856
 857         /*
 858          * If the thread is borrowing another thread's priority, don't ever
 859          * lower the priority.
 860          */
 861         if (td->td_flags & TDF_BORROWING && td->td_priority < prio)
 862                 return;
 863
 864         /* Change the real priority. */
 865         oldprio = td->td_priority;
 866         sched_priority(td, prio);
 867
 868         /*
 869          * If the thread is on a turnstile, then let the turnstile update
 870          * its state.
 871          */
 872         if (TD_ON_LOCK(td) && oldprio != prio)
 873                 turnstile_adjust(td, oldprio);
 874 }
 875
 876 void
 877 sched_user_prio(struct thread *td, u_char prio)
 878 {
 879
 880         THREAD_LOCK_ASSERT(td, MA_OWNED);
 881         td->td_base_user_pri = prio;
 882         if (td->td_lend_user_pri <= prio)
 883                 return;
 884         td->td_user_pri = prio;
 885 }
 886
 887 void
 888 sched_lend_user_prio(struct thread *td, u_char prio)
 889 {
 890
 891         THREAD_LOCK_ASSERT(td, MA_OWNED);
 892         td->td_lend_user_pri = prio;
 893         td->td_user_pri = min(prio, td->td_base_user_pri);
 894         if (td->td_priority > td->td_user_pri)
 895                 sched_prio(td, td->td_user_pri);
 896         else if (td->td_priority != td->td_user_pri)
 897                 td->td_flags |= TDF_NEEDRESCHED;
 898 }
 899
 900 void
 901 sched_sleep(struct thread *td, int pri)
 902 {
 903
 904         THREAD_LOCK_ASSERT(td, MA_OWNED);
 905         td->td_slptick = ticks;
 906         td->td_sched->ts_slptime = 0;
 907         if (pri != 0 && PRI_BASE(td->td_pri_class) == PRI_TIMESHARE)
 908                 sched_prio(td, pri);
 909         if (TD_IS_SUSPENDED(td) || pri >= PSOCK)
 910                 td->td_flags |= TDF_CANSWAP;
 911 }
 912
 913 void
 914 sched_switch(struct thread *td, struct thread *newtd, int flags)
 915 {
 916         struct mtx *tmtx;
 917         struct td_sched *ts;
 918         struct proc *p;
 919
 920         tmtx = NULL;
 921         ts = td->td_sched;
 922         p = td->td_proc;
 923
 924         THREAD_LOCK_ASSERT(td, MA_OWNED);
 925
 926         /*
 927          * Switch to the sched lock to fix things up and pick
 928          * a new thread.
 929          * Block the td_lock in order to avoid breaking the critical path.
 930          */
 931         if (td->td_lock != &sched_lock) {
 932                 mtx_lock_spin(&sched_lock);
 933                 tmtx = thread_lock_block(td);
 934         }
 935
 936         if ((td->td_flags & TDF_NOLOAD) == 0)
 937                 sched_load_rem();
 938
 939         td->td_lastcpu = td->td_oncpu;
 940         if (!(flags & SW_PREEMPT))
 941                 td->td_flags &= ~TDF_NEEDRESCHED;
 942         td->td_owepreempt = 0;
 943         td->td_oncpu = NOCPU;
 944
 945         /*
 946          * At the last moment, if this thread is still marked RUNNING,
 947          * then put it back on the run queue as it has not been suspended
 948          * or stopped or any thing else similar.  We never put the idle
 949          * threads on the run queue, however.
 950          */
 951         if (td->td_flags & TDF_IDLETD) {
 952                 TD_SET_CAN_RUN(td);
 953 #ifdef SMP
 954                 idle_cpus_mask &= ~PCPU_GET(cpumask);
 955 #endif
 956         } else {
 957                 if (TD_IS_RUNNING(td)) {
 958                         /* Put us back on the run queue. */
 959                         sched_add(td, (flags & SW_PREEMPT) ?
 960                             SRQ_OURSELF|SRQ_YIELDING|SRQ_PREEMPTED :
 961                             SRQ_OURSELF|SRQ_YIELDING);
 962                 }
 963         }
 964         if (newtd) {
 965                 /*
 966                  * The thread we are about to run needs to be counted
 967                  * as if it had been added to the run queue and selected.
 968                  * It came from:
 969                  * * A preemption
 970                  * * An upcall
 971                  * * A followon
 972                  */
 973                 KASSERT((newtd->td_inhibitors == 0),
 974                         ("trying to run inhibited thread"));
 975                 newtd->td_flags |= TDF_DIDRUN;
 976                 TD_SET_RUNNING(newtd);
 977                 if ((newtd->td_flags & TDF_NOLOAD) == 0)
 978                         sched_load_add();
 979         } else {
 980                 newtd = choosethread();
 981                 MPASS(newtd->td_lock == &sched_lock);
 982         }
 983
 984         if (td != newtd) {
 985 #ifdef  HWPMC_HOOKS
 986                 if (PMC_PROC_IS_USING_PMCS(td->td_proc))
 987                         PMC_SWITCH_CONTEXT(td, PMC_FN_CSW_OUT);
 988 #endif
 989                 /* I feel sleepy */
 990                 lock_profile_release_lock(&sched_lock.lock_object);
 991 #ifdef KDTRACE_HOOKS
 992                 /*
 993                  * If DTrace has set the active vtime enum to anything
 994                  * other than INACTIVE (0), then it should have set the
 995                  * function to call.
 996                  */
 997                 if (dtrace_vtime_active)
 998                         (*dtrace_vtime_switch_func)(newtd);
 999 #endif
1000
1001                 cpu_switch(td, newtd, tmtx != NULL ? tmtx : td->td_lock);
1002                 lock_profile_obtain_lock_success(&sched_lock.lock_object,
1003                     0, 0, __FILE__, __LINE__);
1004                 /*
1005                  * Where am I?  What year is it?
1006                  * We are in the same thread that went to sleep above,
1007                  * but any amount of time may have passed. All our context
1008                  * will still be available as will local variables.
1009                  * PCPU values however may have changed as we may have
1010                  * changed CPU so don't trust cached values of them.
1011                  * New threads will go to fork_exit() instead of here
1012                  * so if you change things here you may need to change
1013                  * things there too.
1014                  *
1015                  * If the thread above was exiting it will never wake
1016                  * up again here, so either it has saved everything it
1017                  * needed to, or the thread_wait() or wait() will
1018                  * need to reap it.
1019                  */
1020 #ifdef  HWPMC_HOOKS
1021                 if (PMC_PROC_IS_USING_PMCS(td->td_proc))
1022                         PMC_SWITCH_CONTEXT(td, PMC_FN_CSW_IN);
1023 #endif
1024         }
1025
1026 #ifdef SMP
1027         if (td->td_flags & TDF_IDLETD)
1028                 idle_cpus_mask |= PCPU_GET(cpumask);
1029 #endif
1030         sched_lock.mtx_lock = (uintptr_t)td;
1031         td->td_oncpu = PCPU_GET(cpuid);
1032         MPASS(td->td_lock == &sched_lock);
1033 }
1034
1035 void
1036 sched_wakeup(struct thread *td)
1037 {
1038         struct td_sched *ts;
1039
1040         THREAD_LOCK_ASSERT(td, MA_OWNED);
1041         ts = td->td_sched;
1042         td->td_flags &= ~TDF_CANSWAP;
1043         if (ts->ts_slptime > 1) {
1044                 updatepri(td);
1045                 resetpriority(td);
1046         }
1047         td->td_slptick = 0;
1048         ts->ts_slptime = 0;
1049         sched_add(td, SRQ_BORING);
1050 }
1051
1052 #ifdef SMP
1053 static int
1054 forward_wakeup(int cpunum)
1055 {
1056         struct pcpu *pc;
1057         cpumask_t dontuse, id, map, map2, me;
1058
1059         mtx_assert(&sched_lock, MA_OWNED);
1060
1061         CTR0(KTR_RUNQ, "forward_wakeup()");
1062
1063         if ((!forward_wakeup_enabled) ||
1064              (forward_wakeup_use_mask == 0 && forward_wakeup_use_loop == 0))
1065                 return (0);
1066         if (!smp_started || cold || panicstr)
1067                 return (0);
1068
1069         forward_wakeups_requested++;
1070
1071         /*
1072          * Check the idle mask we received against what we calculated
1073          * before in the old version.
1074          */
1075         me = PCPU_GET(cpumask);
1076
1077         /* Don't bother if we should be doing it ourself. */
1078         if ((me & idle_cpus_mask) && (cpunum == NOCPU || me == (1 << cpunum)))
1079                 return (0);
1080
1081         dontuse = me | stopped_cpus | hlt_cpus_mask;
1082         map2 = 0;
1083         if (forward_wakeup_use_loop) {
1084                 STAILQ_FOREACH(pc, &cpuhead, pc_allcpu) {
1085                         id = pc->pc_cpumask;
1086                         if ((id & dontuse) == 0 &&
1087                             pc->pc_curthread == pc->pc_idlethread) {
1088                                 map2 |= id;
1089                         }
1090                 }
1091         }
1092
1093         if (forward_wakeup_use_mask) {
1094                 map = 0;
1095                 map = idle_cpus_mask & ~dontuse;
1096
1097                 /* If they are both on, compare and use loop if different. */
1098                 if (forward_wakeup_use_loop) {
1099                         if (map != map2) {
1100                                 printf("map != map2, loop method preferred\n");
1101                                 map = map2;
1102                         }
1103                 }
1104         } else {
1105                 map = map2;
1106         }
1107
1108         /* If we only allow a specific CPU, then mask off all the others. */
1109         if (cpunum != NOCPU) {
1110                 KASSERT((cpunum <= mp_maxcpus),("forward_wakeup: bad cpunum."));
1111                 map &= (1 << cpunum);
1112         }
1113         if (map) {
1114                 forward_wakeups_delivered++;
1115                 STAILQ_FOREACH(pc, &cpuhead, pc_allcpu) {
1116                         id = pc->pc_cpumask;
1117                         if ((map & id) == 0)
1118                                 continue;
1119                         if (cpu_idle_wakeup(pc->pc_cpuid))
1120                                 map &= ~id;
1121                 }
1122                 if (map)
1123                         ipi_selected(map, IPI_AST);
1124                 return (1);
1125         }
1126         if (cpunum == NOCPU)
1127                 printf("forward_wakeup: Idle processor not found\n");
1128         return (0);
1129 }
1130
1131 static void
1132 kick_other_cpu(int pri, int cpuid)
1133 {
1134         struct pcpu *pcpu;
1135         int cpri;
1136
1137         pcpu = pcpu_find(cpuid);
1138         if (idle_cpus_mask & pcpu->pc_cpumask) {
1139                 forward_wakeups_delivered++;
1140                 if (!cpu_idle_wakeup(cpuid))
1141                         ipi_cpu(cpuid, IPI_AST);
1142                 return;
1143         }
1144
1145         cpri = pcpu->pc_curthread->td_priority;
1146         if (pri >= cpri)
1147                 return;
1148
1149 #if defined(IPI_PREEMPTION) && defined(PREEMPTION)
1150 #if !defined(FULL_PREEMPTION)
1151         if (pri <= PRI_MAX_ITHD)
1152 #endif /* ! FULL_PREEMPTION */
1153         {
1154                 ipi_cpu(cpuid, IPI_PREEMPT);
1155                 return;
1156         }
1157 #endif /* defined(IPI_PREEMPTION) && defined(PREEMPTION) */
1158
1159         pcpu->pc_curthread->td_flags |= TDF_NEEDRESCHED;
1160         ipi_cpu(cpuid, IPI_AST);
1161         return;
1162 }
1163 #endif /* SMP */
1164
1165 #ifdef SMP
1166 static int
1167 sched_pickcpu(struct thread *td)
1168 {
1169         int best, cpu;
1170
1171         mtx_assert(&sched_lock, MA_OWNED);
1172
1173         if (THREAD_CAN_SCHED(td, td->td_lastcpu))
1174                 best = td->td_lastcpu;
1175         else
1176                 best = NOCPU;
1177         CPU_FOREACH(cpu) {
1178                 if (!THREAD_CAN_SCHED(td, cpu))
1179                         continue;
1180
1181                 if (best == NOCPU)
1182                         best = cpu;
1183                 else if (runq_length[cpu] < runq_length[best])
1184                         best = cpu;
1185         }
1186         KASSERT(best != NOCPU, ("no valid CPUs"));
1187
1188         return (best);
1189 }
1190 #endif
1191
1192 void
1193 sched_add(struct thread *td, int flags)
1194 #ifdef SMP
1195 {
1196         struct td_sched *ts;
1197         int forwarded = 0;
1198         int cpu;
1199         int single_cpu = 0;
1200
1201         ts = td->td_sched;
1202         THREAD_LOCK_ASSERT(td, MA_OWNED);
1203         KASSERT((td->td_inhibitors == 0),
1204             ("sched_add: trying to run inhibited thread"));
1205         KASSERT((TD_CAN_RUN(td) || TD_IS_RUNNING(td)),
1206             ("sched_add: bad thread state"));
1207         KASSERT(td->td_flags & TDF_INMEM,
1208             ("sched_add: thread swapped out"));
1209
1210         KTR_STATE2(KTR_SCHED, "thread", sched_tdname(td), "runq add",
1211             "prio:%d", td->td_priority, KTR_ATTR_LINKED,
1212             sched_tdname(curthread));
1213         KTR_POINT1(KTR_SCHED, "thread", sched_tdname(curthread), "wokeup",
1214             KTR_ATTR_LINKED, sched_tdname(td));
1215
1216
1217         /*
1218          * Now that the thread is moving to the run-queue, set the lock
1219          * to the scheduler's lock.
1220          */
1221         if (td->td_lock != &sched_lock) {
1222                 mtx_lock_spin(&sched_lock);
1223                 thread_lock_set(td, &sched_lock);
1224         }
1225         TD_SET_RUNQ(td);
1226
1227         /*
1228          * If SMP is started and the thread is pinned or otherwise limited to
1229          * a specific set of CPUs, queue the thread to a per-CPU run queue.
1230          * Otherwise, queue the thread to the global run queue.
1231          *
1232          * If SMP has not yet been started we must use the global run queue
1233          * as per-CPU state may not be initialized yet and we may crash if we
1234          * try to access the per-CPU run queues.
1235          */
1236         if (smp_started && (td->td_pinned != 0 || td->td_flags & TDF_BOUND ||
1237             ts->ts_flags & TSF_AFFINITY)) {
1238                 if (td->td_pinned != 0)
1239                         cpu = td->td_lastcpu;
1240                 else if (td->td_flags & TDF_BOUND) {
1241                         /* Find CPU from bound runq. */
1242                         KASSERT(SKE_RUNQ_PCPU(ts),
1243                             ("sched_add: bound td_sched not on cpu runq"));
1244                         cpu = ts->ts_runq - &runq_pcpu[0];
1245                 } else
1246                         /* Find a valid CPU for our cpuset */
1247                         cpu = sched_pickcpu(td);
1248                 ts->ts_runq = &runq_pcpu[cpu];
1249                 single_cpu = 1;
1250                 CTR3(KTR_RUNQ,
1251                     "sched_add: Put td_sched:%p(td:%p) on cpu%d runq", ts, td,
1252                     cpu);
1253         } else {
1254                 CTR2(KTR_RUNQ,
1255                     "sched_add: adding td_sched:%p (td:%p) to gbl runq", ts,
1256                     td);
1257                 cpu = NOCPU;
1258                 ts->ts_runq = &runq;
1259         }
1260
1261         if (single_cpu && (cpu != PCPU_GET(cpuid))) {
1262                 kick_other_cpu(td->td_priority, cpu);
1263         } else {
1264                 if (!single_cpu) {
1265                         cpumask_t me = PCPU_GET(cpumask);
1266                         cpumask_t idle = idle_cpus_mask & me;
1267
1268                         if (!idle && ((flags & SRQ_INTR) == 0) &&
1269                             (idle_cpus_mask & ~(hlt_cpus_mask | me)))
1270                                 forwarded = forward_wakeup(cpu);
1271                 }
1272
1273                 if (!forwarded) {
1274                         if ((flags & SRQ_YIELDING) == 0 && maybe_preempt(td))
1275                                 return;
1276                         else
1277                                 maybe_resched(td);
1278                 }
1279         }
1280
1281         if ((td->td_flags & TDF_NOLOAD) == 0)
1282                 sched_load_add();
1283         runq_add(ts->ts_runq, td, flags);
1284         if (cpu != NOCPU)
1285                 runq_length[cpu]++;
1286 }
1287 #else /* SMP */
1288 {
1289         struct td_sched *ts;
1290
1291         ts = td->td_sched;
1292         THREAD_LOCK_ASSERT(td, MA_OWNED);
1293         KASSERT((td->td_inhibitors == 0),
1294             ("sched_add: trying to run inhibited thread"));
1295         KASSERT((TD_CAN_RUN(td) || TD_IS_RUNNING(td)),
1296             ("sched_add: bad thread state"));
1297         KASSERT(td->td_flags & TDF_INMEM,
1298             ("sched_add: thread swapped out"));
1299         KTR_STATE2(KTR_SCHED, "thread", sched_tdname(td), "runq add",
1300             "prio:%d", td->td_priority, KTR_ATTR_LINKED,
1301             sched_tdname(curthread));
1302         KTR_POINT1(KTR_SCHED, "thread", sched_tdname(curthread), "wokeup",
1303             KTR_ATTR_LINKED, sched_tdname(td));
1304
1305         /*
1306          * Now that the thread is moving to the run-queue, set the lock
1307          * to the scheduler's lock.
1308          */
1309         if (td->td_lock != &sched_lock) {
1310                 mtx_lock_spin(&sched_lock);
1311                 thread_lock_set(td, &sched_lock);
1312         }
1313         TD_SET_RUNQ(td);
1314         CTR2(KTR_RUNQ, "sched_add: adding td_sched:%p (td:%p) to runq", ts, td);
1315         ts->ts_runq = &runq;
1316
1317         /*
1318          * If we are yielding (on the way out anyhow) or the thread
1319          * being saved is US, then don't try be smart about preemption
1320          * or kicking off another CPU as it won't help and may hinder.
1321          * In the YIEDLING case, we are about to run whoever is being
1322          * put in the queue anyhow, and in the OURSELF case, we are
1323          * puting ourself on the run queue which also only happens
1324          * when we are about to yield.
1325          */
1326         if ((flags & SRQ_YIELDING) == 0) {
1327                 if (maybe_preempt(td))
1328                         return;
1329         }
1330         if ((td->td_flags & TDF_NOLOAD) == 0)
1331                 sched_load_add();
1332         runq_add(ts->ts_runq, td, flags);
1333         maybe_resched(td);
1334 }
1335 #endif /* SMP */
1336
1337 void
1338 sched_rem(struct thread *td)
1339 {
1340         struct td_sched *ts;
1341
1342         ts = td->td_sched;
1343         KASSERT(td->td_flags & TDF_INMEM,
1344             ("sched_rem: thread swapped out"));
1345         KASSERT(TD_ON_RUNQ(td),
1346             ("sched_rem: thread not on run queue"));
1347         mtx_assert(&sched_lock, MA_OWNED);
1348         KTR_STATE2(KTR_SCHED, "thread", sched_tdname(td), "runq rem",
1349             "prio:%d", td->td_priority, KTR_ATTR_LINKED,
1350             sched_tdname(curthread));
1351
1352         if ((td->td_flags & TDF_NOLOAD) == 0)
1353                 sched_load_rem();
1354 #ifdef SMP
1355         if (ts->ts_runq != &runq)
1356                 runq_length[ts->ts_runq - runq_pcpu]--;
1357 #endif
1358         runq_remove(ts->ts_runq, td);
1359         TD_SET_CAN_RUN(td);
1360 }
1361
1362 /*
1363  * Select threads to run.  Note that running threads still consume a
1364  * slot.
1365  */
1366 struct thread *
1367 sched_choose(void)
1368 {
1369         struct thread *td;
1370         struct runq *rq;
1371
1372         mtx_assert(&sched_lock,  MA_OWNED);
1373 #ifdef SMP
1374         struct thread *tdcpu;
1375
1376         rq = &runq;
1377         td = runq_choose_fuzz(&runq, runq_fuzz);
1378         tdcpu = runq_choose(&runq_pcpu[PCPU_GET(cpuid)]);
1379
1380         if (td == NULL ||
1381             (tdcpu != NULL &&
1382              tdcpu->td_priority < td->td_priority)) {
1383                 CTR2(KTR_RUNQ, "choosing td %p from pcpu runq %d", tdcpu,
1384                      PCPU_GET(cpuid));
1385                 td = tdcpu;
1386                 rq = &runq_pcpu[PCPU_GET(cpuid)];
1387         } else {
1388                 CTR1(KTR_RUNQ, "choosing td_sched %p from main runq", td);
1389         }
1390
1391 #else
1392         rq = &runq;
1393         td = runq_choose(&runq);
1394 #endif
1395
1396         if (td) {
1397 #ifdef SMP
1398                 if (td == tdcpu)
1399                         runq_length[PCPU_GET(cpuid)]--;
1400 #endif
1401                 runq_remove(rq, td);
1402                 td->td_flags |= TDF_DIDRUN;
1403
1404                 KASSERT(td->td_flags & TDF_INMEM,
1405                     ("sched_choose: thread swapped out"));
1406                 return (td);
1407         }
1408         return (PCPU_GET(idlethread));
1409 }
1410
1411 void
1412 sched_preempt(struct thread *td)
1413 {
1414         thread_lock(td);
1415         if (td->td_critnest > 1)
1416                 td->td_owepreempt = 1;
1417         else
1418                 mi_switch(SW_INVOL | SW_PREEMPT | SWT_PREEMPT, NULL);
1419         thread_unlock(td);
1420 }
1421
1422 void
1423 sched_userret(struct thread *td)
1424 {
1425         /*
1426          * XXX we cheat slightly on the locking here to avoid locking in
1427          * the usual case.  Setting td_priority here is essentially an
1428          * incomplete workaround for not setting it properly elsewhere.
1429          * Now that some interrupt handlers are threads, not setting it
1430          * properly elsewhere can clobber it in the window between setting
1431          * it here and returning to user mode, so don't waste time setting
1432          * it perfectly here.
1433          */
1434         KASSERT((td->td_flags & TDF_BORROWING) == 0,
1435             ("thread with borrowed priority returning to userland"));
1436         if (td->td_priority != td->td_user_pri) {
1437                 thread_lock(td);
1438                 td->td_priority = td->td_user_pri;
1439                 td->td_base_pri = td->td_user_pri;
1440                 thread_unlock(td);
1441         }
1442 }
1443
1444 void
1445 sched_bind(struct thread *td, int cpu)
1446 {
1447         struct td_sched *ts;
1448
1449         THREAD_LOCK_ASSERT(td, MA_OWNED|MA_NOTRECURSED);
1450         KASSERT(td == curthread, ("sched_bind: can only bind curthread"));
1451
1452         ts = td->td_sched;
1453
1454         td->td_flags |= TDF_BOUND;
1455 #ifdef SMP
1456         ts->ts_runq = &runq_pcpu[cpu];
1457         if (PCPU_GET(cpuid) == cpu)
1458                 return;
1459
1460         mi_switch(SW_VOL, NULL);
1461 #endif
1462 }
1463
1464 void
1465 sched_unbind(struct thread* td)
1466 {
1467         THREAD_LOCK_ASSERT(td, MA_OWNED);
1468         KASSERT(td == curthread, ("sched_unbind: can only bind curthread"));
1469         td->td_flags &= ~TDF_BOUND;
1470 }
1471
1472 int
1473 sched_is_bound(struct thread *td)
1474 {
1475         THREAD_LOCK_ASSERT(td, MA_OWNED);
1476         return (td->td_flags & TDF_BOUND);
1477 }
1478
1479 void
1480 sched_relinquish(struct thread *td)
1481 {
1482         thread_lock(td);
1483         mi_switch(SW_VOL | SWT_RELINQUISH, NULL);
1484         thread_unlock(td);
1485 }
1486
1487 int
1488 sched_load(void)
1489 {
1490         return (sched_tdcnt);
1491 }
1492
1493 int
1494 sched_sizeof_proc(void)
1495 {
1496         return (sizeof(struct proc));
1497 }
1498
1499 int
1500 sched_sizeof_thread(void)
1501 {
1502         return (sizeof(struct thread) + sizeof(struct td_sched));
1503 }
1504
1505 fixpt_t
1506 sched_pctcpu(struct thread *td)
1507 {
1508         struct td_sched *ts;
1509
1510         THREAD_LOCK_ASSERT(td, MA_OWNED);
1511         ts = td->td_sched;
1512         return (ts->ts_pctcpu);
1513 }
1514
1515 void
1516 sched_tick(int cnt)
1517 {
1518 }
1519
1520 /*
1521  * The actual idle process.
1522  */
1523 void
1524 sched_idletd(void *dummy)
1525 {
1526         struct pcpuidlestat *stat;
1527
1528         stat = DPCPU_PTR(idlestat);
1529         for (;;) {
1530                 mtx_assert(&Giant, MA_NOTOWNED);
1531
1532                 while (sched_runnable() == 0) {
1533                         cpu_idle(stat->idlecalls + stat->oldidlecalls > 64);
1534                         stat->idlecalls++;
1535                 }
1536
1537                 mtx_lock_spin(&sched_lock);
1538                 mi_switch(SW_VOL | SWT_IDLE, NULL);
1539                 mtx_unlock_spin(&sched_lock);
1540         }
1541 }
1542
1543 /*
1544  * A CPU is entering for the first time or a thread is exiting.
1545  */
1546 void
1547 sched_throw(struct thread *td)
1548 {
1549         /*
1550          * Correct spinlock nesting.  The idle thread context that we are
1551          * borrowing was created so that it would start out with a single
1552          * spin lock (sched_lock) held in fork_trampoline().  Since we've
1553          * explicitly acquired locks in this function, the nesting count
1554          * is now 2 rather than 1.  Since we are nested, calling
1555          * spinlock_exit() will simply adjust the counts without allowing
1556          * spin lock using code to interrupt us.
1557          */
1558         if (td == NULL) {
1559                 mtx_lock_spin(&sched_lock);
1560                 spinlock_exit();
1561         } else {
1562                 lock_profile_release_lock(&sched_lock.lock_object);
1563                 MPASS(td->td_lock == &sched_lock);
1564         }
1565         mtx_assert(&sched_lock, MA_OWNED);
1566         KASSERT(curthread->td_md.md_spinlock_count == 1, ("invalid count"));
1567         PCPU_SET(switchtime, cpu_ticks());
1568         PCPU_SET(switchticks, ticks);
1569         cpu_throw(td, choosethread());  /* doesn't return */
1570 }
1571
1572 void
1573 sched_fork_exit(struct thread *td)
1574 {
1575
1576         /*
1577          * Finish setting up thread glue so that it begins execution in a
1578          * non-nested critical section with sched_lock held but not recursed.
1579          */
1580         td->td_oncpu = PCPU_GET(cpuid);
1581         sched_lock.mtx_lock = (uintptr_t)td;
1582         lock_profile_obtain_lock_success(&sched_lock.lock_object,
1583             0, 0, __FILE__, __LINE__);
1584         THREAD_LOCK_ASSERT(td, MA_OWNED | MA_NOTRECURSED);
1585 }
1586
1587 char *
1588 sched_tdname(struct thread *td)
1589 {
1590 #ifdef KTR
1591         struct td_sched *ts;
1592
1593         ts = td->td_sched;
1594         if (ts->ts_name[0] == '\0')
1595                 snprintf(ts->ts_name, sizeof(ts->ts_name),
1596                     "%s tid %d", td->td_name, td->td_tid);
1597         return (ts->ts_name);
1598 #else
1599         return (td->td_name);
1600 #endif
1601 }
1602
1603 void
1604 sched_affinity(struct thread *td)
1605 {
1606 #ifdef SMP
1607         struct td_sched *ts;
1608         int cpu;
1609
1610         THREAD_LOCK_ASSERT(td, MA_OWNED);
1611
1612         /*
1613          * Set the TSF_AFFINITY flag if there is at least one CPU this
1614          * thread can't run on.
1615          */
1616         ts = td->td_sched;
1617         ts->ts_flags &= ~TSF_AFFINITY;
1618         CPU_FOREACH(cpu) {
1619                 if (!THREAD_CAN_SCHED(td, cpu)) {
1620                         ts->ts_flags |= TSF_AFFINITY;
1621                         break;
1622                 }
1623         }
1624
1625         /*
1626          * If this thread can run on all CPUs, nothing else to do.
1627          */
1628         if (!(ts->ts_flags & TSF_AFFINITY))
1629                 return;
1630
1631         /* Pinned threads and bound threads should be left alone. */
1632         if (td->td_pinned != 0 || td->td_flags & TDF_BOUND)
1633                 return;
1634
1635         switch (td->td_state) {
1636         case TDS_RUNQ:
1637                 /*
1638                  * If we are on a per-CPU runqueue that is in the set,
1639                  * then nothing needs to be done.
1640                  */
1641                 if (ts->ts_runq != &runq &&
1642                     THREAD_CAN_SCHED(td, ts->ts_runq - runq_pcpu))
1643                         return;
1644
1645                 /* Put this thread on a valid per-CPU runqueue. */
1646                 sched_rem(td);
1647                 sched_add(td, SRQ_BORING);
1648                 break;
1649         case TDS_RUNNING:
1650                 /*
1651                  * See if our current CPU is in the set.  If not, force a
1652                  * context switch.
1653                  */
1654                 if (THREAD_CAN_SCHED(td, td->td_oncpu))
1655                         return;
1656
1657                 td->td_flags |= TDF_NEEDRESCHED;
1658                 if (td != curthread)
1659                         ipi_cpu(cpu, IPI_AST);
1660                 break;
1661         default:
1662                 break;
1663         }
1664 #endif
1665 }