The Design and Implementation of the FreeBSD Operating System, Second Edition
Now available: The Design and Implementation of the FreeBSD Operating System (Second Edition)


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]

FreeBSD/Linux Kernel Cross Reference
sys/kern/sched_4bsd.c

Version: -  FREEBSD  -  FREEBSD-13-STABLE  -  FREEBSD-13-0  -  FREEBSD-12-STABLE  -  FREEBSD-12-0  -  FREEBSD-11-STABLE  -  FREEBSD-11-0  -  FREEBSD-10-STABLE  -  FREEBSD-10-0  -  FREEBSD-9-STABLE  -  FREEBSD-9-0  -  FREEBSD-8-STABLE  -  FREEBSD-8-0  -  FREEBSD-7-STABLE  -  FREEBSD-7-0  -  FREEBSD-6-STABLE  -  FREEBSD-6-0  -  FREEBSD-5-STABLE  -  FREEBSD-5-0  -  FREEBSD-4-STABLE  -  FREEBSD-3-STABLE  -  FREEBSD22  -  l41  -  OPENBSD  -  linux-2.6  -  MK84  -  PLAN9  -  xnu-8792 
SearchContext: -  none  -  3  -  10 

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

Cache object: 70e979f70d6a05a34b7c6ba2bdca70d1


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]


This page is part of the FreeBSD/Linux Linux Kernel Cross-Reference, and was automatically generated using a modified version of the LXR engine.