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