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