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