sys/kern/sched_ule.c

   1 /*-
   2  * Copyright (c) 2002-2007, Jeffrey Roberson <jeff@freebsd.org>
   3  * All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions
   7  * are met:
   8  * 1. Redistributions of source code must retain the above copyright
   9  *    notice unmodified, this list of conditions, and the following
  10  *    disclaimer.
  11  * 2. Redistributions in binary form must reproduce the above copyright
  12  *    notice, this list of conditions and the following disclaimer in the
  13  *    documentation and/or other materials provided with the distribution.
  14  *
  15  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  16  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  17  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  18  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  19  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  20  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  21  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  22  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  23  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  24  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  25  */
  26
  27 /*
  28  * This file implements the ULE scheduler.  ULE supports independent CPU
  29  * run queues and fine grain locking.  It has superior interactive
  30  * performance under load even on uni-processor systems.
  31  *
  32  * etymology:
  33  *   ULE is the last three letters in schedule.  It owes its name to a
  34  * generic user created for a scheduling system by Paul Mikesell at
  35  * Isilon Systems and a general lack of creativity on the part of the author.
  36  */
  37
  38 #include <sys/cdefs.h>
  39 __FBSDID("$FreeBSD$");
  40
  41 #include "opt_hwpmc_hooks.h"
  42 #include "opt_kdtrace.h"
  43 #include "opt_sched.h"
  44
  45 #include <sys/param.h>
  46 #include <sys/systm.h>
  47 #include <sys/kdb.h>
  48 #include <sys/kernel.h>
  49 #include <sys/ktr.h>
  50 #include <sys/lock.h>
  51 #include <sys/mutex.h>
  52 #include <sys/proc.h>
  53 #include <sys/resource.h>
  54 #include <sys/resourcevar.h>
  55 #include <sys/sched.h>
  56 #include <sys/smp.h>
  57 #include <sys/sx.h>
  58 #include <sys/sysctl.h>
  59 #include <sys/sysproto.h>
  60 #include <sys/turnstile.h>
  61 #include <sys/umtx.h>
  62 #include <sys/vmmeter.h>
  63 #include <sys/cpuset.h>
  64 #ifdef KTRACE
  65 #include <sys/uio.h>
  66 #include <sys/ktrace.h>
  67 #endif
  68
  69 #ifdef HWPMC_HOOKS
  70 #include <sys/pmckern.h>
  71 #endif
  72
  73 #ifdef KDTRACE_HOOKS
  74 #include <sys/dtrace_bsd.h>
  75 int                             dtrace_vtime_active;
  76 dtrace_vtime_switch_func_t      dtrace_vtime_switch_func;
  77 #endif
  78
  79 #include <machine/cpu.h>
  80 #include <machine/smp.h>
  81
  82 #if !defined(__i386__) && !defined(__amd64__) && !defined(__arm__)
  83 #error "This architecture is not currently compatible with ULE"
  84 #endif
  85
  86 #define KTR_ULE 0
  87
  88 /*
  89  * Thread scheduler specific section.  All fields are protected
  90  * by the thread lock.
  91  */
  92 struct td_sched {
  93         TAILQ_ENTRY(td_sched) ts_procq; /* Run queue. */
  94         struct thread   *ts_thread;     /* Active associated thread. */
  95         struct runq     *ts_runq;       /* Run-queue we're queued on. */
  96         short           ts_flags;       /* TSF_* flags. */
  97         u_char          ts_rqindex;     /* Run queue index. */
  98         u_char          ts_cpu;         /* CPU that we have affinity for. */
  99         int             ts_slice;       /* Ticks of slice remaining. */
 100         u_int           ts_slptime;     /* Number of ticks we vol. slept */
 101         u_int           ts_runtime;     /* Number of ticks we were running */
 102         /* The following variables are only used for pctcpu calculation */
 103         int             ts_ltick;       /* Last tick that we were running on */
 104         int             ts_ftick;       /* First tick that we were running on */
 105         int             ts_ticks;       /* Tick count */
 106 #ifdef SMP
 107         int             ts_rltick;      /* Real last tick, for affinity. */
 108 #endif
 109 };
 110 /* flags kept in ts_flags */
 111 #define TSF_BOUND       0x0001          /* Thread can not migrate. */
 112 #define TSF_XFERABLE    0x0002          /* Thread was added as transferable. */
 113
 114 static struct td_sched td_sched0;
 115
 116 #define THREAD_CAN_MIGRATE(td)  ((td)->td_pinned == 0)
 117 #define THREAD_CAN_SCHED(td, cpu)       \
 118     CPU_ISSET((cpu), &(td)->td_cpuset->cs_mask)
 119
 120 /*
 121  * Cpu percentage computation macros and defines.
 122  *
 123  * SCHED_TICK_SECS:     Number of seconds to average the cpu usage across.
 124  * SCHED_TICK_TARG:     Number of hz ticks to average the cpu usage across.
 125  * SCHED_TICK_MAX:      Maximum number of ticks before scaling back.
 126  * SCHED_TICK_SHIFT:    Shift factor to avoid rounding away results.
 127  * SCHED_TICK_HZ:       Compute the number of hz ticks for a given ticks count.
 128  * SCHED_TICK_TOTAL:    Gives the amount of time we've been recording ticks.
 129  */
 130 #define SCHED_TICK_SECS         10
 131 #define SCHED_TICK_TARG         (hz * SCHED_TICK_SECS)
 132 #define SCHED_TICK_MAX          (SCHED_TICK_TARG + hz)
 133 #define SCHED_TICK_SHIFT        10
 134 #define SCHED_TICK_HZ(ts)       ((ts)->ts_ticks >> SCHED_TICK_SHIFT)
 135 #define SCHED_TICK_TOTAL(ts)    (max((ts)->ts_ltick - (ts)->ts_ftick, hz))
 136
 137 /*
 138  * These macros determine priorities for non-interactive threads.  They are
 139  * assigned a priority based on their recent cpu utilization as expressed
 140  * by the ratio of ticks to the tick total.  NHALF priorities at the start
 141  * and end of the MIN to MAX timeshare range are only reachable with negative
 142  * or positive nice respectively.
 143  *
 144  * PRI_RANGE:   Priority range for utilization dependent priorities.
 145  * PRI_NRESV:   Number of nice values.
 146  * PRI_TICKS:   Compute a priority in PRI_RANGE from the ticks count and total.
 147  * PRI_NICE:    Determines the part of the priority inherited from nice.
 148  */
 149 #define SCHED_PRI_NRESV         (PRIO_MAX - PRIO_MIN)
 150 #define SCHED_PRI_NHALF         (SCHED_PRI_NRESV / 2)
 151 #define SCHED_PRI_MIN           (PRI_MIN_TIMESHARE + SCHED_PRI_NHALF)
 152 #define SCHED_PRI_MAX           (PRI_MAX_TIMESHARE - SCHED_PRI_NHALF)
 153 #define SCHED_PRI_RANGE         (SCHED_PRI_MAX - SCHED_PRI_MIN)
 154 #define SCHED_PRI_TICKS(ts)                                             \
 155     (SCHED_TICK_HZ((ts)) /                                              \
 156     (roundup(SCHED_TICK_TOTAL((ts)), SCHED_PRI_RANGE) / SCHED_PRI_RANGE))
 157 #define SCHED_PRI_NICE(nice)    (nice)
 158
 159 /*
 160  * These determine the interactivity of a process.  Interactivity differs from
 161  * cpu utilization in that it expresses the voluntary time slept vs time ran
 162  * while cpu utilization includes all time not running.  This more accurately
 163  * models the intent of the thread.
 164  *
 165  * SLP_RUN_MAX: Maximum amount of sleep time + run time we'll accumulate
 166  *              before throttling back.
 167  * SLP_RUN_FORK:        Maximum slp+run time to inherit at fork time.
 168  * INTERACT_MAX:        Maximum interactivity value.  Smaller is better.
 169  * INTERACT_THRESH:     Threshhold for placement on the current runq.
 170  */
 171 #define SCHED_SLP_RUN_MAX       ((hz * 5) << SCHED_TICK_SHIFT)
 172 #define SCHED_SLP_RUN_FORK      ((hz / 2) << SCHED_TICK_SHIFT)
 173 #define SCHED_INTERACT_MAX      (100)
 174 #define SCHED_INTERACT_HALF     (SCHED_INTERACT_MAX / 2)
 175 #define SCHED_INTERACT_THRESH   (30)
 176
 177 /*
 178  * tickincr:            Converts a stathz tick into a hz domain scaled by
 179  *                      the shift factor.  Without the shift the error rate
 180  *                      due to rounding would be unacceptably high.
 181  * realstathz:          stathz is sometimes 0 and run off of hz.
 182  * sched_slice:         Runtime of each thread before rescheduling.
 183  * preempt_thresh:      Priority threshold for preemption and remote IPIs.
 184  */
 185 static int sched_interact = SCHED_INTERACT_THRESH;
 186 static int realstathz;
 187 static int tickincr;
 188 static int sched_slice;
 189 #ifdef PREEMPTION
 190 #ifdef FULL_PREEMPTION
 191 static int preempt_thresh = PRI_MAX_IDLE;
 192 #else
 193 static int preempt_thresh = PRI_MIN_KERN;
 194 #endif
 195 #else
 196 static int preempt_thresh = 0;
 197 #endif
 198
 199 /*
 200  * tdq - per processor runqs and statistics.  All fields are protected by the
 201  * tdq_lock.  The load and lowpri may be accessed without to avoid excess
 202  * locking in sched_pickcpu();
 203  */
 204 struct tdq {
 205         struct mtx      *tdq_lock;              /* Pointer to group lock. */
 206         struct runq     tdq_realtime;           /* real-time run queue. */
 207         struct runq     tdq_timeshare;          /* timeshare run queue. */
 208         struct runq     tdq_idle;               /* Queue of IDLE threads. */
 209         int             tdq_load;               /* Aggregate load. */
 210         u_char          tdq_idx;                /* Current insert index. */
 211         u_char          tdq_ridx;               /* Current removal index. */
 212 #ifdef SMP
 213         u_char          tdq_lowpri;             /* Lowest priority thread. */
 214         int             tdq_transferable;       /* Transferable thread count. */
 215         LIST_ENTRY(tdq) tdq_siblings;           /* Next in tdq group. */
 216         struct tdq_group *tdq_group;            /* Our processor group. */
 217 #else
 218         int             tdq_sysload;            /* For loadavg, !ITHD load. */
 219 #endif
 220 } __aligned(64);
 221
 222
 223 #ifdef SMP
 224 /*
 225  * tdq groups are groups of processors which can cheaply share threads.  When
 226  * one processor in the group goes idle it will check the runqs of the other
 227  * processors in its group prior to halting and waiting for an interrupt.
 228  * These groups are suitable for SMT (Symetric Multi-Threading) and not NUMA.
 229  * In a numa environment we'd want an idle bitmap per group and a two tiered
 230  * load balancer.
 231  */
 232 struct tdq_group {
 233         struct mtx      tdg_lock;       /* Protects all fields below. */
 234         int             tdg_cpus;       /* Count of CPUs in this tdq group. */
 235         cpumask_t       tdg_cpumask;    /* Mask of cpus in this group. */
 236         cpumask_t       tdg_idlemask;   /* Idle cpus in this group. */
 237         cpumask_t       tdg_mask;       /* Bit mask for first cpu. */
 238         int             tdg_load;       /* Total load of this group. */
 239         int     tdg_transferable;       /* Transferable load of this group. */
 240         LIST_HEAD(, tdq) tdg_members;   /* Linked list of all members. */
 241         char            tdg_name[16];   /* lock name. */
 242 } __aligned(64);
 243
 244 #define SCHED_AFFINITY_DEFAULT  (max(1, hz / 300))
 245 #define SCHED_AFFINITY(ts)      ((ts)->ts_rltick > ticks - affinity)
 246
 247 /*
 248  * Run-time tunables.
 249  */
 250 static int rebalance = 1;
 251 static int balance_interval = 128;      /* Default set in sched_initticks(). */
 252 static int pick_pri = 1;
 253 static int affinity;
 254 static int tryself = 1;
 255 static int steal_htt = 1;
 256 static int steal_idle = 1;
 257 static int steal_thresh = 2;
 258 static int topology = 0;
 259
 260 /*
 261  * One thread queue per processor.
 262  */
 263 static volatile cpumask_t tdq_idle;
 264 static int tdg_maxid;
 265 static struct tdq       tdq_cpu[MAXCPU];
 266 static struct tdq_group tdq_groups[MAXCPU];
 267 static struct tdq       *balance_tdq;
 268 static int balance_group_ticks;
 269 static int balance_ticks;
 270
 271 #define TDQ_SELF()      (&tdq_cpu[PCPU_GET(cpuid)])
 272 #define TDQ_CPU(x)      (&tdq_cpu[(x)])
 273 #define TDQ_ID(x)       ((int)((x) - tdq_cpu))
 274 #define TDQ_GROUP(x)    (&tdq_groups[(x)])
 275 #define TDG_ID(x)       ((int)((x) - tdq_groups))
 276 #else   /* !SMP */
 277 static struct tdq       tdq_cpu;
 278 static struct mtx       tdq_lock;
 279
 280 #define TDQ_ID(x)       (0)
 281 #define TDQ_SELF()      (&tdq_cpu)
 282 #define TDQ_CPU(x)      (&tdq_cpu)
 283 #endif
 284
 285 #define TDQ_LOCK_ASSERT(t, type)        mtx_assert(TDQ_LOCKPTR((t)), (type))
 286 #define TDQ_LOCK(t)             mtx_lock_spin(TDQ_LOCKPTR((t)))
 287 #define TDQ_LOCK_FLAGS(t, f)    mtx_lock_spin_flags(TDQ_LOCKPTR((t)), (f))
 288 #define TDQ_UNLOCK(t)           mtx_unlock_spin(TDQ_LOCKPTR((t)))
 289 #define TDQ_LOCKPTR(t)          ((t)->tdq_lock)
 290
 291 static void sched_priority(struct thread *);
 292 static void sched_thread_priority(struct thread *, u_char);
 293 static int sched_interact_score(struct thread *);
 294 static void sched_interact_update(struct thread *);
 295 static void sched_interact_fork(struct thread *);
 296 static void sched_pctcpu_update(struct td_sched *);
 297
 298 /* Operations on per processor queues */
 299 static struct td_sched * tdq_choose(struct tdq *);
 300 static void tdq_setup(struct tdq *);
 301 static void tdq_load_add(struct tdq *, struct td_sched *);
 302 static void tdq_load_rem(struct tdq *, struct td_sched *);
 303 static __inline void tdq_runq_add(struct tdq *, struct td_sched *, int);
 304 static __inline void tdq_runq_rem(struct tdq *, struct td_sched *);
 305 void tdq_print(int cpu);
 306 static void runq_print(struct runq *rq);
 307 static void tdq_add(struct tdq *, struct thread *, int);
 308 #ifdef SMP
 309 static void tdq_move(struct tdq *, struct tdq *);
 310 static int tdq_idled(struct tdq *);
 311 static void tdq_notify(struct td_sched *);
 312 static struct td_sched *tdq_steal(struct tdq *, int);
 313 static struct td_sched *runq_steal(struct runq *, int);
 314 static int sched_pickcpu(struct thread *, int);
 315 static void sched_balance(void);
 316 static void sched_balance_groups(void);
 317 static void sched_balance_group(struct tdq_group *);
 318 static void sched_balance_pair(struct tdq *, struct tdq *);
 319 static inline struct tdq *sched_setcpu(struct td_sched *, int, int);
 320 static inline struct mtx *thread_block_switch(struct thread *);
 321 static inline void thread_unblock_switch(struct thread *, struct mtx *);
 322 static struct mtx *sched_switch_migrate(struct tdq *, struct thread *, int);
 323 #endif
 324
 325 static void sched_setup(void *dummy);
 326 SYSINIT(sched_setup, SI_SUB_RUN_QUEUE, SI_ORDER_FIRST, sched_setup, NULL);
 327
 328 static void sched_initticks(void *dummy);
 329 SYSINIT(sched_initticks, SI_SUB_CLOCKS, SI_ORDER_THIRD, sched_initticks,
 330     NULL);
 331
 332 /*
 333  * Print the threads waiting on a run-queue.
 334  */
 335 static void
 336 runq_print(struct runq *rq)
 337 {
 338         struct rqhead *rqh;
 339         struct td_sched *ts;
 340         int pri;
 341         int j;
 342         int i;
 343
 344         for (i = 0; i < RQB_LEN; i++) {
 345                 printf("\t\trunq bits %d 0x%zx\n",
 346                     i, rq->rq_status.rqb_bits[i]);
 347                 for (j = 0; j < RQB_BPW; j++)
 348                         if (rq->rq_status.rqb_bits[i] & (1ul << j)) {
 349                                 pri = j + (i << RQB_L2BPW);
 350                                 rqh = &rq->rq_queues[pri];
 351                                 TAILQ_FOREACH(ts, rqh, ts_procq) {
 352                                         printf("\t\t\ttd %p(%s) priority %d rqindex %d pri %d\n",
 353                                             ts->ts_thread, ts->ts_thread->td_proc->p_comm, ts->ts_thread->td_priority, ts->ts_rqindex, pri);
 354                                 }
 355                         }
 356         }
 357 }
 358
 359 /*
 360  * Print the status of a per-cpu thread queue.  Should be a ddb show cmd.
 361  */
 362 void
 363 tdq_print(int cpu)
 364 {
 365         struct tdq *tdq;
 366
 367         tdq = TDQ_CPU(cpu);
 368
 369         printf("tdq %d:\n", TDQ_ID(tdq));
 370         printf("\tlockptr         %p\n", TDQ_LOCKPTR(tdq));
 371         printf("\tload:           %d\n", tdq->tdq_load);
 372         printf("\ttimeshare idx:  %d\n", tdq->tdq_idx);
 373         printf("\ttimeshare ridx: %d\n", tdq->tdq_ridx);
 374         printf("\trealtime runq:\n");
 375         runq_print(&tdq->tdq_realtime);
 376         printf("\ttimeshare runq:\n");
 377         runq_print(&tdq->tdq_timeshare);
 378         printf("\tidle runq:\n");
 379         runq_print(&tdq->tdq_idle);
 380 #ifdef SMP
 381         printf("\tload transferable: %d\n", tdq->tdq_transferable);
 382         printf("\tlowest priority:   %d\n", tdq->tdq_lowpri);
 383         printf("\tgroup:             %d\n", TDG_ID(tdq->tdq_group));
 384         printf("\tLock name:         %s\n", tdq->tdq_group->tdg_name);
 385 #endif
 386 }
 387
 388 #define TS_RQ_PPQ       (((PRI_MAX_TIMESHARE - PRI_MIN_TIMESHARE) + 1) / RQ_NQS)
 389 /*
 390  * Add a thread to the actual run-queue.  Keeps transferable counts up to
 391  * date with what is actually on the run-queue.  Selects the correct
 392  * queue position for timeshare threads.
 393  */
 394 static __inline void
 395 tdq_runq_add(struct tdq *tdq, struct td_sched *ts, int flags)
 396 {
 397         TDQ_LOCK_ASSERT(tdq, MA_OWNED);
 398         THREAD_LOCK_ASSERT(ts->ts_thread, MA_OWNED);
 399 #ifdef SMP
 400         if (THREAD_CAN_MIGRATE(ts->ts_thread)) {
 401                 tdq->tdq_transferable++;
 402                 tdq->tdq_group->tdg_transferable++;
 403                 ts->ts_flags |= TSF_XFERABLE;
 404         }
 405 #endif
 406         if (ts->ts_runq == &tdq->tdq_timeshare) {
 407                 u_char pri;
 408
 409                 pri = ts->ts_thread->td_priority;
 410                 KASSERT(pri <= PRI_MAX_TIMESHARE && pri >= PRI_MIN_TIMESHARE,
 411                         ("Invalid priority %d on timeshare runq", pri));
 412                 /*
 413                  * This queue contains only priorities between MIN and MAX
 414                  * realtime.  Use the whole queue to represent these values.
 415                  */
 416                 if ((flags & (SRQ_BORROWING|SRQ_PREEMPTED)) == 0) {
 417                         pri = (pri - PRI_MIN_TIMESHARE) / TS_RQ_PPQ;
 418                         pri = (pri + tdq->tdq_idx) % RQ_NQS;
 419                         /*
 420                          * This effectively shortens the queue by one so we
 421                          * can have a one slot difference between idx and
 422                          * ridx while we wait for threads to drain.
 423                          */
 424                         if (tdq->tdq_ridx != tdq->tdq_idx &&
 425                             pri == tdq->tdq_ridx)
 426                                 pri = (unsigned char)(pri - 1) % RQ_NQS;
 427                 } else
 428                         pri = tdq->tdq_ridx;
 429                 runq_add_pri(ts->ts_runq, ts, pri, flags);
 430         } else
 431                 runq_add(ts->ts_runq, ts, flags);
 432 }
 433
 434 /*
 435  * Remove a thread from a run-queue.  This typically happens when a thread
 436  * is selected to run.  Running threads are not on the queue and the
 437  * transferable count does not reflect them.
 438  */
 439 static __inline void
 440 tdq_runq_rem(struct tdq *tdq, struct td_sched *ts)
 441 {
 442         TDQ_LOCK_ASSERT(tdq, MA_OWNED);
 443         KASSERT(ts->ts_runq != NULL,
 444             ("tdq_runq_remove: thread %p null ts_runq", ts->ts_thread));
 445 #ifdef SMP
 446         if (ts->ts_flags & TSF_XFERABLE) {
 447                 tdq->tdq_transferable--;
 448                 tdq->tdq_group->tdg_transferable--;
 449                 ts->ts_flags &= ~TSF_XFERABLE;
 450         }
 451 #endif
 452         if (ts->ts_runq == &tdq->tdq_timeshare) {
 453                 if (tdq->tdq_idx != tdq->tdq_ridx)
 454                         runq_remove_idx(ts->ts_runq, ts, &tdq->tdq_ridx);
 455                 else
 456                         runq_remove_idx(ts->ts_runq, ts, NULL);
 457                 /*
 458                  * For timeshare threads we update the priority here so
 459                  * the priority reflects the time we've been sleeping.
 460                  */
 461                 ts->ts_ltick = ticks;
 462                 sched_pctcpu_update(ts);
 463                 sched_priority(ts->ts_thread);
 464         } else
 465                 runq_remove(ts->ts_runq, ts);
 466 }
 467
 468 /*
 469  * Load is maintained for all threads RUNNING and ON_RUNQ.  Add the load
 470  * for this thread to the referenced thread queue.
 471  */
 472 static void
 473 tdq_load_add(struct tdq *tdq, struct td_sched *ts)
 474 {
 475         int class;
 476
 477         TDQ_LOCK_ASSERT(tdq, MA_OWNED);
 478         THREAD_LOCK_ASSERT(ts->ts_thread, MA_OWNED);
 479         class = PRI_BASE(ts->ts_thread->td_pri_class);
 480         tdq->tdq_load++;
 481         CTR2(KTR_SCHED, "cpu %d load: %d", TDQ_ID(tdq), tdq->tdq_load);
 482         if (class != PRI_ITHD &&
 483             (ts->ts_thread->td_proc->p_flag & P_NOLOAD) == 0)
 484 #ifdef SMP
 485                 tdq->tdq_group->tdg_load++;
 486 #else
 487                 tdq->tdq_sysload++;
 488 #endif
 489 }
 490
 491 /*
 492  * Remove the load from a thread that is transitioning to a sleep state or
 493  * exiting.
 494  */
 495 static void
 496 tdq_load_rem(struct tdq *tdq, struct td_sched *ts)
 497 {
 498         int class;
 499
 500         THREAD_LOCK_ASSERT(ts->ts_thread, MA_OWNED);
 501         TDQ_LOCK_ASSERT(tdq, MA_OWNED);
 502         class = PRI_BASE(ts->ts_thread->td_pri_class);
 503         if (class != PRI_ITHD &&
 504             (ts->ts_thread->td_proc->p_flag & P_NOLOAD) == 0)
 505 #ifdef SMP
 506                 tdq->tdq_group->tdg_load--;
 507 #else
 508                 tdq->tdq_sysload--;
 509 #endif
 510         KASSERT(tdq->tdq_load != 0,
 511             ("tdq_load_rem: Removing with 0 load on queue %d", TDQ_ID(tdq)));
 512         tdq->tdq_load--;
 513         CTR1(KTR_SCHED, "load: %d", tdq->tdq_load);
 514         ts->ts_runq = NULL;
 515 }
 516
 517 #ifdef SMP
 518 /*
 519  * sched_balance is a simple CPU load balancing algorithm.  It operates by
 520  * finding the least loaded and most loaded cpu and equalizing their load
 521  * by migrating some processes.
 522  *
 523  * Dealing only with two CPUs at a time has two advantages.  Firstly, most
 524  * installations will only have 2 cpus.  Secondly, load balancing too much at
 525  * once can have an unpleasant effect on the system.  The scheduler rarely has
 526  * enough information to make perfect decisions.  So this algorithm chooses
 527  * simplicity and more gradual effects on load in larger systems.
 528  *
 529  */
 530 static void
 531 sched_balance()
 532 {
 533         struct tdq_group *high;
 534         struct tdq_group *low;
 535         struct tdq_group *tdg;
 536         struct tdq *tdq;
 537         int cnt;
 538         int i;
 539
 540         /*
 541          * Select a random time between .5 * balance_interval and
 542          * 1.5 * balance_interval.
 543          */
 544         balance_ticks = max(balance_interval / 2, 1);
 545         balance_ticks += random() % balance_interval;
 546         if (smp_started == 0 || rebalance == 0)
 547                 return;
 548         tdq = TDQ_SELF();
 549         TDQ_UNLOCK(tdq);
 550         low = high = NULL;
 551         i = random() % (tdg_maxid + 1);
 552         for (cnt = 0; cnt <= tdg_maxid; cnt++) {
 553                 tdg = TDQ_GROUP(i);
 554                 /*
 555                  * Find the CPU with the highest load that has some
 556                  * threads to transfer.
 557                  */
 558                 if ((high == NULL || tdg->tdg_load > high->tdg_load)
 559                     && tdg->tdg_transferable)
 560                         high = tdg;
 561                 if (low == NULL || tdg->tdg_load < low->tdg_load)
 562                         low = tdg;
 563                 if (++i > tdg_maxid)
 564                         i = 0;
 565         }
 566         if (low != NULL && high != NULL && high != low)
 567                 sched_balance_pair(LIST_FIRST(&high->tdg_members),
 568                     LIST_FIRST(&low->tdg_members));
 569         TDQ_LOCK(tdq);
 570 }
 571
 572 /*
 573  * Balance load between CPUs in a group.  Will only migrate within the group.
 574  */
 575 static void
 576 sched_balance_groups()
 577 {
 578         struct tdq *tdq;
 579         int i;
 580
 581         /*
 582          * Select a random time between .5 * balance_interval and
 583          * 1.5 * balance_interval.
 584          */
 585         balance_group_ticks = max(balance_interval / 2, 1);
 586         balance_group_ticks += random() % balance_interval;
 587         if (smp_started == 0 || rebalance == 0)
 588                 return;
 589         tdq = TDQ_SELF();
 590         TDQ_UNLOCK(tdq);
 591         for (i = 0; i <= tdg_maxid; i++)
 592                 sched_balance_group(TDQ_GROUP(i));
 593         TDQ_LOCK(tdq);
 594 }
 595
 596 /*
 597  * Finds the greatest imbalance between two tdqs in a group.
 598  */
 599 static void
 600 sched_balance_group(struct tdq_group *tdg)
 601 {
 602         struct tdq *tdq;
 603         struct tdq *high;
 604         struct tdq *low;
 605         int load;
 606
 607         if (tdg->tdg_transferable == 0)
 608                 return;
 609         low = NULL;
 610         high = NULL;
 611         LIST_FOREACH(tdq, &tdg->tdg_members, tdq_siblings) {
 612                 load = tdq->tdq_load;
 613                 if (high == NULL || load > high->tdq_load)
 614                         high = tdq;
 615                 if (low == NULL || load < low->tdq_load)
 616                         low = tdq;
 617         }
 618         if (high != NULL && low != NULL && high != low)
 619                 sched_balance_pair(high, low);
 620 }
 621
 622 /*
 623  * Lock two thread queues using their address to maintain lock order.
 624  */
 625 static void
 626 tdq_lock_pair(struct tdq *one, struct tdq *two)
 627 {
 628         if (one < two) {
 629                 TDQ_LOCK(one);
 630                 TDQ_LOCK_FLAGS(two, MTX_DUPOK);
 631         } else {
 632                 TDQ_LOCK(two);
 633                 TDQ_LOCK_FLAGS(one, MTX_DUPOK);
 634         }
 635 }
 636
 637 /*
 638  * Unlock two thread queues.  Order is not important here.
 639  */
 640 static void
 641 tdq_unlock_pair(struct tdq *one, struct tdq *two)
 642 {
 643         TDQ_UNLOCK(one);
 644         TDQ_UNLOCK(two);
 645 }
 646
 647 /*
 648  * Transfer load between two imbalanced thread queues.
 649  */
 650 static void
 651 sched_balance_pair(struct tdq *high, struct tdq *low)
 652 {
 653         int transferable;
 654         int high_load;
 655         int low_load;
 656         int move;
 657         int diff;
 658         int i;
 659
 660         tdq_lock_pair(high, low);
 661         /*
 662          * If we're transfering within a group we have to use this specific
 663          * tdq's transferable count, otherwise we can steal from other members
 664          * of the group.
 665          */
 666         if (high->tdq_group == low->tdq_group) {
 667                 transferable = high->tdq_transferable;
 668                 high_load = high->tdq_load;
 669                 low_load = low->tdq_load;
 670         } else {
 671                 transferable = high->tdq_group->tdg_transferable;
 672                 high_load = high->tdq_group->tdg_load;
 673                 low_load = low->tdq_group->tdg_load;
 674         }
 675         /*
 676          * Determine what the imbalance is and then adjust that to how many
 677          * threads we actually have to give up (transferable).
 678          */
 679         if (transferable != 0) {
 680                 diff = high_load - low_load;
 681                 move = diff / 2;
 682                 if (diff & 0x1)
 683                         move++;
 684                 move = min(move, transferable);
 685                 for (i = 0; i < move; i++)
 686                         tdq_move(high, low);
 687                 /*
 688                  * IPI the target cpu to force it to reschedule with the new
 689                  * workload.
 690                  */
 691                 ipi_selected(1 << TDQ_ID(low), IPI_PREEMPT);
 692         }
 693         tdq_unlock_pair(high, low);
 694         return;
 695 }
 696
 697 /*
 698  * Move a thread from one thread queue to another.
 699  */
 700 static void
 701 tdq_move(struct tdq *from, struct tdq *to)
 702 {
 703         struct td_sched *ts;
 704         struct thread *td;
 705         struct tdq *tdq;
 706         int cpu;
 707
 708         TDQ_LOCK_ASSERT(from, MA_OWNED);
 709         TDQ_LOCK_ASSERT(to, MA_OWNED);
 710
 711         tdq = from;
 712         cpu = TDQ_ID(to);
 713         ts = tdq_steal(tdq, cpu);
 714         if (ts == NULL) {
 715                 struct tdq_group *tdg;
 716
 717                 tdg = tdq->tdq_group;
 718                 LIST_FOREACH(tdq, &tdg->tdg_members, tdq_siblings) {
 719                         if (tdq == from || tdq->tdq_transferable == 0)
 720                                 continue;
 721                         ts = tdq_steal(tdq, cpu);
 722                         break;
 723                 }
 724                 if (ts == NULL)
 725                         return;
 726         }
 727         if (tdq == to)
 728                 return;
 729         td = ts->ts_thread;
 730         /*
 731          * Although the run queue is locked the thread may be blocked.  Lock
 732          * it to clear this and acquire the run-queue lock.
 733          */
 734         thread_lock(td);
 735         /* Drop recursive lock on from acquired via thread_lock(). */
 736         TDQ_UNLOCK(from);
 737         sched_rem(td);
 738         ts->ts_cpu = cpu;
 739         td->td_lock = TDQ_LOCKPTR(to);
 740         tdq_add(to, td, SRQ_YIELDING);
 741 }
 742
 743 /*
 744  * This tdq has idled.  Try to steal a thread from another cpu and switch
 745  * to it.
 746  */
 747 static int
 748 tdq_idled(struct tdq *tdq)
 749 {
 750         struct tdq_group *tdg;
 751         struct tdq *steal;
 752         int highload;
 753         int highcpu;
 754         int cpu;
 755
 756         if (smp_started == 0 || steal_idle == 0)
 757                 return (1);
 758         /* We don't want to be preempted while we're iterating over tdqs */
 759         spinlock_enter();
 760         tdg = tdq->tdq_group;
 761         /*
 762          * If we're in a cpu group, try and steal threads from another cpu in
 763          * the group before idling.  In a HTT group all cpus share the same
 764          * run-queue lock, however, we still need a recursive lock to
 765          * call tdq_move().
 766          */
 767         if (steal_htt && tdg->tdg_cpus > 1 && tdg->tdg_transferable) {
 768                 TDQ_LOCK(tdq);
 769                 LIST_FOREACH(steal, &tdg->tdg_members, tdq_siblings) {
 770                         if (steal == tdq || steal->tdq_transferable == 0)
 771                                 continue;
 772                         TDQ_LOCK(steal);
 773                         goto steal;
 774                 }
 775                 TDQ_UNLOCK(tdq);
 776         }
 777         /*
 778          * Find the least loaded CPU with a transferable thread and attempt
 779          * to steal it.  We make a lockless pass and then verify that the
 780          * thread is still available after locking.
 781          */
 782         for (;;) {
 783                 highcpu = 0;
 784                 highload = 0;
 785                 for (cpu = 0; cpu <= mp_maxid; cpu++) {
 786                         if (CPU_ABSENT(cpu))
 787                                 continue;
 788                         steal = TDQ_CPU(cpu);
 789                         if (steal->tdq_transferable == 0)
 790                                 continue;
 791                         if (steal->tdq_load < highload)
 792                                 continue;
 793                         highload = steal->tdq_load;
 794                         highcpu = cpu;
 795                 }
 796                 if (highload < steal_thresh)
 797                         break;
 798                 steal = TDQ_CPU(highcpu);
 799                 if (steal == tdq)
 800                         break;
 801                 tdq_lock_pair(tdq, steal);
 802                 if (steal->tdq_load >= steal_thresh && steal->tdq_transferable)
 803                         goto steal;
 804                 tdq_unlock_pair(tdq, steal);
 805         }
 806         spinlock_exit();
 807         return (1);
 808 steal:
 809         spinlock_exit();
 810         tdq_move(steal, tdq);
 811         TDQ_UNLOCK(steal);
 812         mi_switch(SW_VOL, NULL);
 813         thread_unlock(curthread);
 814
 815         return (0);
 816 }
 817
 818 /*
 819  * Notify a remote cpu of new work.  Sends an IPI if criteria are met.
 820  */
 821 static void
 822 tdq_notify(struct td_sched *ts)
 823 {
 824         struct thread *ctd;
 825         struct pcpu *pcpu;
 826         int cpri;
 827         int pri;
 828         int cpu;
 829
 830         cpu = ts->ts_cpu;
 831         pri = ts->ts_thread->td_priority;
 832         pcpu = pcpu_find(cpu);
 833         ctd = pcpu->pc_curthread;
 834         cpri = ctd->td_priority;
 835
 836         /*
 837          * If our priority is not better than the current priority there is
 838          * nothing to do.
 839          */
 840         if (pri > cpri)
 841                 return;
 842         /*
 843          * Always IPI idle.
 844          */
 845         if (cpri > PRI_MIN_IDLE)
 846                 goto sendipi;
 847         /*
 848          * If we're realtime or better and there is timeshare or worse running
 849          * send an IPI.
 850          */
 851         if (pri < PRI_MAX_REALTIME && cpri > PRI_MAX_REALTIME)
 852                 goto sendipi;
 853         /*
 854          * Otherwise only IPI if we exceed the threshold.
 855          */
 856         if (pri > preempt_thresh)
 857                 return;
 858 sendipi:
 859         ipi_selected(1 << cpu, IPI_PREEMPT);
 860 }
 861
 862 /*
 863  * Steals load from a timeshare queue.  Honors the rotating queue head
 864  * index.
 865  */
 866 static struct td_sched *
 867 runq_steal_from(struct runq *rq, int cpu, u_char start)
 868 {
 869         struct td_sched *ts;
 870         struct rqbits *rqb;
 871         struct rqhead *rqh;
 872         int first;
 873         int bit;
 874         int pri;
 875         int i;
 876
 877         rqb = &rq->rq_status;
 878         bit = start & (RQB_BPW -1);
 879         pri = 0;
 880         first = 0;
 881 again:
 882         for (i = RQB_WORD(start); i < RQB_LEN; bit = 0, i++) {
 883                 if (rqb->rqb_bits[i] == 0)
 884                         continue;
 885                 if (bit != 0) {
 886                         for (pri = bit; pri < RQB_BPW; pri++)
 887                                 if (rqb->rqb_bits[i] & (1ul << pri))
 888                                         break;
 889                         if (pri >= RQB_BPW)
 890                                 continue;
 891                 } else
 892                         pri = RQB_FFS(rqb->rqb_bits[i]);
 893                 pri += (i << RQB_L2BPW);
 894                 rqh = &rq->rq_queues[pri];
 895                 TAILQ_FOREACH(ts, rqh, ts_procq) {
 896                         if (first && THREAD_CAN_MIGRATE(ts->ts_thread) &&
 897                             THREAD_CAN_SCHED(ts->ts_thread, cpu))
 898                                 return (ts);
 899                         first = 1;
 900                 }
 901         }
 902         if (start != 0) {
 903                 start = 0;
 904                 goto again;
 905         }
 906
 907         return (NULL);
 908 }
 909
 910 /*
 911  * Steals load from a standard linear queue.
 912  */
 913 static struct td_sched *
 914 runq_steal(struct runq *rq, int cpu)
 915 {
 916         struct rqhead *rqh;
 917         struct rqbits *rqb;
 918         struct td_sched *ts;
 919         int word;
 920         int bit;
 921
 922         rqb = &rq->rq_status;
 923         for (word = 0; word < RQB_LEN; word++) {
 924                 if (rqb->rqb_bits[word] == 0)
 925                         continue;
 926                 for (bit = 0; bit < RQB_BPW; bit++) {
 927                         if ((rqb->rqb_bits[word] & (1ul << bit)) == 0)
 928                                 continue;
 929                         rqh = &rq->rq_queues[bit + (word << RQB_L2BPW)];
 930                         TAILQ_FOREACH(ts, rqh, ts_procq)
 931                                 if (THREAD_CAN_MIGRATE(ts->ts_thread) &&
 932                                     THREAD_CAN_SCHED(ts->ts_thread, cpu))
 933                                         return (ts);
 934                 }
 935         }
 936         return (NULL);
 937 }
 938
 939 /*
 940  * Attempt to steal a thread in priority order from a thread queue.
 941  */
 942 static struct td_sched *
 943 tdq_steal(struct tdq *tdq, int cpu)
 944 {
 945         struct td_sched *ts;
 946
 947         TDQ_LOCK_ASSERT(tdq, MA_OWNED);
 948         if ((ts = runq_steal(&tdq->tdq_realtime, cpu)) != NULL)
 949                 return (ts);
 950         if ((ts = runq_steal_from(&tdq->tdq_timeshare,
 951             cpu, tdq->tdq_ridx)) != NULL)
 952                 return (ts);
 953         return (runq_steal(&tdq->tdq_idle, cpu));
 954 }
 955
 956 /*
 957  * Sets the thread lock and ts_cpu to match the requested cpu.  Unlocks the
 958  * current lock and returns with the assigned queue locked.
 959  */
 960 static inline struct tdq *
 961 sched_setcpu(struct td_sched *ts, int cpu, int flags)
 962 {
 963         struct thread *td;
 964         struct tdq *tdq;
 965
 966         THREAD_LOCK_ASSERT(ts->ts_thread, MA_OWNED);
 967
 968         tdq = TDQ_CPU(cpu);
 969         td = ts->ts_thread;
 970         ts->ts_cpu = cpu;
 971
 972         /* If the lock matches just return the queue. */
 973         if (td->td_lock == TDQ_LOCKPTR(tdq))
 974                 return (tdq);
 975 #ifdef notyet
 976         /*
 977          * If the thread isn't running its lockptr is a
 978          * turnstile or a sleepqueue.  We can just lock_set without
 979          * blocking.
 980          */
 981         if (TD_CAN_RUN(td)) {
 982                 TDQ_LOCK(tdq);
 983                 thread_lock_set(td, TDQ_LOCKPTR(tdq));
 984                 return (tdq);
 985         }
 986 #endif
 987         /*
 988          * The hard case, migration, we need to block the thread first to
 989          * prevent order reversals with other cpus locks.
 990          */
 991         thread_lock_block(td);
 992         TDQ_LOCK(tdq);
 993         thread_lock_unblock(td, TDQ_LOCKPTR(tdq));
 994         return (tdq);
 995 }
 996
 997 /*
 998  * Find the thread queue running the lowest priority thread.
 999  */
1000 static int
1001 tdq_lowestpri(struct thread *td)
1002 {
1003         struct tdq *tdq;
1004         int lowpri;
1005         int lowcpu;
1006         int lowload;
1007         int load;
1008         int cpu;
1009         int pri;
1010
1011         lowload = 0;
1012         lowpri = lowcpu = 0;
1013         for (cpu = 0; cpu <= mp_maxid; cpu++) {
1014                 if (CPU_ABSENT(cpu))
1015                         continue;
1016                 if (!THREAD_CAN_SCHED(td, cpu))
1017                         continue;
1018                 tdq = TDQ_CPU(cpu);
1019                 pri = tdq->tdq_lowpri;
1020                 load = TDQ_CPU(cpu)->tdq_load;
1021                 CTR4(KTR_ULE,
1022                     "cpu %d pri %d lowcpu %d lowpri %d",
1023                     cpu, pri, lowcpu, lowpri);
1024                 if (pri < lowpri)
1025                         continue;
1026                 if (lowpri && lowpri == pri && load > lowload)
1027                         continue;
1028                 lowpri = pri;
1029                 lowcpu = cpu;
1030                 lowload = load;
1031         }
1032
1033         return (lowcpu);
1034 }
1035
1036 /*
1037  * Find the thread queue with the least load.
1038  */
1039 static int
1040 tdq_lowestload(struct thread *td)
1041 {
1042         struct tdq *tdq;
1043         int lowload;
1044         int lowpri;
1045         int lowcpu;
1046         int load;
1047         int cpu;
1048         int pri;
1049
1050         lowcpu = 0;
1051         lowload = TDQ_CPU(0)->tdq_load;
1052         lowpri = TDQ_CPU(0)->tdq_lowpri;
1053         for (cpu = 1; cpu <= mp_maxid; cpu++) {
1054                 if (CPU_ABSENT(cpu))
1055                         continue;
1056                 if (!THREAD_CAN_SCHED(td, cpu))
1057                         continue;
1058                 tdq = TDQ_CPU(cpu);
1059                 load = tdq->tdq_load;
1060                 pri = tdq->tdq_lowpri;
1061                 CTR4(KTR_ULE, "cpu %d load %d lowcpu %d lowload %d",
1062                     cpu, load, lowcpu, lowload);
1063                 if (load > lowload)
1064                         continue;
1065                 if (load == lowload && pri < lowpri)
1066                         continue;
1067                 lowcpu = cpu;
1068                 lowload = load;
1069                 lowpri = pri;
1070         }
1071
1072         return (lowcpu);
1073 }
1074
1075 /*
1076  * Pick the destination cpu for sched_add().  Respects affinity and makes
1077  * a determination based on load or priority of available processors.
1078  */
1079 static int
1080 sched_pickcpu(struct thread *td, int flags)
1081 {
1082         struct tdq *tdq;
1083         struct td_sched *ts;
1084         cpumask_t mask;
1085         int self;
1086         int pri;
1087         int cpu;
1088
1089         self = PCPU_GET(cpuid);
1090         ts = td->td_sched;
1091         if (smp_started == 0)
1092                 return (self);
1093         /*
1094          * Don't migrate a running thread from sched_switch().
1095          */
1096         if (flags & SRQ_OURSELF) {
1097                 CTR1(KTR_ULE, "YIELDING %d",
1098                     curthread->td_priority);
1099                 return (self);
1100         }
1101         pri = ts->ts_thread->td_priority;
1102         cpu = ts->ts_cpu;
1103         if (THREAD_CAN_SCHED(td, cpu)) {
1104                 /*
1105                  * Regardless of affinity, if the last cpu is idle
1106                  * send it there.
1107                  */
1108                 tdq = TDQ_CPU(cpu);
1109                 if (tdq->tdq_lowpri > PRI_MIN_IDLE) {
1110                         CTR5(KTR_ULE,
1111                     "ts_cpu %d idle, ltick %d ticks %d pri %d curthread %d",
1112                             ts->ts_cpu, ts->ts_rltick, ticks, pri,
1113                             tdq->tdq_lowpri);
1114                         return (ts->ts_cpu);
1115                 }
1116                 /*
1117                  * If we have affinity, try to place it on the cpu we
1118                  * last ran on.
1119                  */
1120                 if (SCHED_AFFINITY(ts) && tdq->tdq_lowpri > pri) {
1121                         CTR5(KTR_ULE,
1122                     "affinity for %d, ltick %d ticks %d pri %d curthread %d",
1123                             ts->ts_cpu, ts->ts_rltick, ticks, pri,
1124                             tdq->tdq_lowpri);
1125                         return (ts->ts_cpu);
1126                 }
1127         }
1128
1129         /*
1130          * Look for an idle group.
1131          */
1132         CTR1(KTR_ULE, "tdq_idle %X", tdq_idle);
1133         mask = tdq_idle;
1134         while ((cpu = ffs(mask)) != 0) {
1135                 --cpu;
1136                 if (THREAD_CAN_SCHED(td, cpu))
1137                         return (cpu);
1138                 mask &= ~(1 << cpu);
1139         }
1140         /*
1141          * If there are no idle cores see if we can run the thread locally.
1142          * This may improve locality among sleepers and wakers when there
1143          * is shared data.
1144          */
1145         if (tryself && THREAD_CAN_SCHED(td, self) &&
1146             pri < curthread->td_priority) {
1147                 CTR1(KTR_ULE, "tryself %d",
1148                     curthread->td_priority);
1149                 return (self);
1150         }
1151         /*
1152          * Now search for the cpu running the lowest priority thread with
1153          * the least load.
1154          */
1155         if (pick_pri)
1156                 cpu = tdq_lowestpri(td);
1157         else
1158                 cpu = tdq_lowestload(td);
1159         return (cpu);
1160 }
1161
1162 #endif  /* SMP */
1163
1164 /*
1165  * Pick the highest priority task we have and return it.
1166  */
1167 static struct td_sched *
1168 tdq_choose(struct tdq *tdq)
1169 {
1170         struct td_sched *ts;
1171
1172         TDQ_LOCK_ASSERT(tdq, MA_OWNED);
1173         ts = runq_choose(&tdq->tdq_realtime);
1174         if (ts != NULL)
1175                 return (ts);
1176         ts = runq_choose_from(&tdq->tdq_timeshare, tdq->tdq_ridx);
1177         if (ts != NULL) {
1178                 KASSERT(ts->ts_thread->td_priority >= PRI_MIN_TIMESHARE,
1179                     ("tdq_choose: Invalid priority on timeshare queue %d",
1180                     ts->ts_thread->td_priority));
1181                 return (ts);
1182         }
1183
1184         ts = runq_choose(&tdq->tdq_idle);
1185         if (ts != NULL) {
1186                 KASSERT(ts->ts_thread->td_priority >= PRI_MIN_IDLE,
1187                     ("tdq_choose: Invalid priority on idle queue %d",
1188                     ts->ts_thread->td_priority));
1189                 return (ts);
1190         }
1191
1192         return (NULL);
1193 }
1194
1195 /*
1196  * Initialize a thread queue.
1197  */
1198 static void
1199 tdq_setup(struct tdq *tdq)
1200 {
1201
1202         if (bootverbose)
1203                 printf("ULE: setup cpu %d\n", TDQ_ID(tdq));
1204         runq_init(&tdq->tdq_realtime);
1205         runq_init(&tdq->tdq_timeshare);
1206         runq_init(&tdq->tdq_idle);
1207         tdq->tdq_load = 0;
1208 }
1209
1210 #ifdef SMP
1211 static void
1212 tdg_setup(struct tdq_group *tdg)
1213 {
1214         if (bootverbose)
1215                 printf("ULE: setup cpu group %d\n", TDG_ID(tdg));
1216         snprintf(tdg->tdg_name, sizeof(tdg->tdg_name),
1217             "sched lock %d", (int)TDG_ID(tdg));
1218         mtx_init(&tdg->tdg_lock, tdg->tdg_name, "sched lock",
1219             MTX_SPIN | MTX_RECURSE);
1220         LIST_INIT(&tdg->tdg_members);
1221         tdg->tdg_load = 0;
1222         tdg->tdg_transferable = 0;
1223         tdg->tdg_cpus = 0;
1224         tdg->tdg_mask = 0;
1225         tdg->tdg_cpumask = 0;
1226         tdg->tdg_idlemask = 0;
1227 }
1228
1229 static void
1230 tdg_add(struct tdq_group *tdg, struct tdq *tdq)
1231 {
1232         if (tdg->tdg_mask == 0)
1233                 tdg->tdg_mask |= 1 << TDQ_ID(tdq);
1234         tdg->tdg_cpumask |= 1 << TDQ_ID(tdq);
1235         tdg->tdg_cpus++;
1236         tdq->tdq_group = tdg;
1237         tdq->tdq_lock = &tdg->tdg_lock;
1238         LIST_INSERT_HEAD(&tdg->tdg_members, tdq, tdq_siblings);
1239         if (bootverbose)
1240                 printf("ULE: adding cpu %d to group %d: cpus %d mask 0x%X\n",
1241                     TDQ_ID(tdq), TDG_ID(tdg), tdg->tdg_cpus, tdg->tdg_cpumask);
1242 }
1243
1244 static void
1245 sched_setup_topology(void)
1246 {
1247         struct tdq_group *tdg;
1248         struct cpu_group *cg;
1249         int balance_groups;
1250         struct tdq *tdq;
1251         int i;
1252         int j;
1253
1254         topology = 1;
1255         balance_groups = 0;
1256         for (i = 0; i < smp_topology->ct_count; i++) {
1257                 cg = &smp_topology->ct_group[i];
1258                 tdg = &tdq_groups[i];
1259                 /*
1260                  * Initialize the group.
1261                  */
1262                 tdg_setup(tdg);
1263                 /*
1264                  * Find all of the group members and add them.
1265                  */
1266                 for (j = 0; j < MAXCPU; j++) {
1267                         if ((cg->cg_mask & (1 << j)) != 0) {
1268                                 tdq = TDQ_CPU(j);
1269                                 tdq_setup(tdq);
1270                                 tdg_add(tdg, tdq);
1271                         }
1272                 }
1273                 if (tdg->tdg_cpus > 1)
1274                         balance_groups = 1;
1275         }
1276         tdg_maxid = smp_topology->ct_count - 1;
1277         if (balance_groups)
1278                 sched_balance_groups();
1279 }
1280
1281 static void
1282 sched_setup_smp(void)
1283 {
1284         struct tdq_group *tdg;
1285         struct tdq *tdq;
1286         int cpus;
1287         int i;
1288
1289         for (cpus = 0, i = 0; i < MAXCPU; i++) {
1290                 if (CPU_ABSENT(i))
1291                         continue;
1292                 tdq = &tdq_cpu[i];
1293                 tdg = &tdq_groups[i];
1294                 /*
1295                  * Setup a tdq group with one member.
1296                  */
1297                 tdg_setup(tdg);
1298                 tdq_setup(tdq);
1299                 tdg_add(tdg, tdq);
1300                 cpus++;
1301         }
1302         tdg_maxid = cpus - 1;
1303 }
1304
1305 /*
1306  * Fake a topology with one group containing all CPUs.
1307  */
1308 static void
1309 sched_fake_topo(void)
1310 {
1311 #ifdef SCHED_FAKE_TOPOLOGY
1312         static struct cpu_top top;
1313         static struct cpu_group group;
1314
1315         top.ct_count = 1;
1316         top.ct_group = &group;
1317         group.cg_mask = all_cpus;
1318         group.cg_count = mp_ncpus;
1319         group.cg_children = 0;
1320         smp_topology = &top;
1321 #endif
1322 }
1323 #endif
1324
1325 /*
1326  * Setup the thread queues and initialize the topology based on MD
1327  * information.
1328  */
1329 static void
1330 sched_setup(void *dummy)
1331 {
1332         struct tdq *tdq;
1333
1334         tdq = TDQ_SELF();
1335 #ifdef SMP
1336         sched_fake_topo();
1337         /*
1338          * Setup tdqs based on a topology configuration or vanilla SMP based
1339          * on mp_maxid.
1340          */
1341         if (smp_topology == NULL)
1342                 sched_setup_smp();
1343         else
1344                 sched_setup_topology();
1345         balance_tdq = tdq;
1346         sched_balance();
1347 #else
1348         tdq_setup(tdq);
1349         mtx_init(&tdq_lock, "sched lock", "sched lock", MTX_SPIN | MTX_RECURSE);
1350         tdq->tdq_lock = &tdq_lock;
1351 #endif
1352         /*
1353          * To avoid divide-by-zero, we set realstathz a dummy value
1354          * in case which sched_clock() called before sched_initticks().
1355          */
1356         realstathz = hz;
1357         sched_slice = (realstathz/10);  /* ~100ms */
1358         tickincr = 1 << SCHED_TICK_SHIFT;
1359
1360         /* Add thread0's load since it's running. */
1361         TDQ_LOCK(tdq);
1362         thread0.td_lock = TDQ_LOCKPTR(TDQ_SELF());
1363         tdq_load_add(tdq, &td_sched0);
1364         TDQ_UNLOCK(tdq);
1365 }
1366
1367 /*
1368  * This routine determines the tickincr after stathz and hz are setup.
1369  */
1370 /* ARGSUSED */
1371 static void
1372 sched_initticks(void *dummy)
1373 {
1374         int incr;
1375
1376         realstathz = stathz ? stathz : hz;
1377         sched_slice = (realstathz/10);  /* ~100ms */
1378
1379         /*
1380          * tickincr is shifted out by 10 to avoid rounding errors due to
1381          * hz not being evenly divisible by stathz on all platforms.
1382          */
1383         incr = (hz << SCHED_TICK_SHIFT) / realstathz;
1384         /*
1385          * This does not work for values of stathz that are more than
1386          * 1 << SCHED_TICK_SHIFT * hz.  In practice this does not happen.
1387          */
1388         if (incr == 0)
1389                 incr = 1;
1390         tickincr = incr;
1391 #ifdef SMP
1392         /*
1393          * Set the default balance interval now that we know
1394          * what realstathz is.
1395          */
1396         balance_interval = realstathz;
1397         /*
1398          * Set steal thresh to roughly log2(mp_ncpu) but no greater than 4.
1399          * This prevents excess thrashing on large machines and excess idle
1400          * on smaller machines.
1401          */
1402         steal_thresh = min(fls(mp_ncpus) - 1, 3);
1403         affinity = SCHED_AFFINITY_DEFAULT;
1404 #endif
1405 }
1406
1407
1408 /*
1409  * This is the core of the interactivity algorithm.  Determines a score based
1410  * on past behavior.  It is the ratio of sleep time to run time scaled to
1411  * a [0, 100] integer.  This is the voluntary sleep time of a process, which
1412  * differs from the cpu usage because it does not account for time spent
1413  * waiting on a run-queue.  Would be prettier if we had floating point.
1414  */
1415 static int
1416 sched_interact_score(struct thread *td)
1417 {
1418         struct td_sched *ts;
1419         int div;
1420
1421         ts = td->td_sched;
1422         /*
1423          * The score is only needed if this is likely to be an interactive
1424          * task.  Don't go through the expense of computing it if there's
1425          * no chance.
1426          */
1427         if (sched_interact <= SCHED_INTERACT_HALF &&
1428                 ts->ts_runtime >= ts->ts_slptime)
1429                         return (SCHED_INTERACT_HALF);
1430
1431         if (ts->ts_runtime > ts->ts_slptime) {
1432                 div = max(1, ts->ts_runtime / SCHED_INTERACT_HALF);
1433                 return (SCHED_INTERACT_HALF +
1434                     (SCHED_INTERACT_HALF - (ts->ts_slptime / div)));
1435         }
1436         if (ts->ts_slptime > ts->ts_runtime) {
1437                 div = max(1, ts->ts_slptime / SCHED_INTERACT_HALF);
1438                 return (ts->ts_runtime / div);
1439         }
1440         /* runtime == slptime */
1441         if (ts->ts_runtime)
1442                 return (SCHED_INTERACT_HALF);
1443
1444         /*
1445          * This can happen if slptime and runtime are 0.
1446          */
1447         return (0);
1448
1449 }
1450
1451 /*
1452  * Scale the scheduling priority according to the "interactivity" of this
1453  * process.
1454  */
1455 static void
1456 sched_priority(struct thread *td)
1457 {
1458         int score;
1459         int pri;
1460
1461         if (td->td_pri_class != PRI_TIMESHARE)
1462                 return;
1463         /*
1464          * If the score is interactive we place the thread in the realtime
1465          * queue with a priority that is less than kernel and interrupt
1466          * priorities.  These threads are not subject to nice restrictions.
1467          *
1468          * Scores greater than this are placed on the normal timeshare queue
1469          * where the priority is partially decided by the most recent cpu
1470          * utilization and the rest is decided by nice value.
1471          *
1472          * The nice value of the process has a linear effect on the calculated
1473          * score.  Negative nice values make it easier for a thread to be
1474          * considered interactive.
1475          */
1476         score = imax(0, sched_interact_score(td) - td->td_proc->p_nice);
1477         if (score < sched_interact) {
1478                 pri = PRI_MIN_REALTIME;
1479                 pri += ((PRI_MAX_REALTIME - PRI_MIN_REALTIME) / sched_interact)
1480                     * score;
1481                 KASSERT(pri >= PRI_MIN_REALTIME && pri <= PRI_MAX_REALTIME,
1482                     ("sched_priority: invalid interactive priority %d score %d",
1483                     pri, score));
1484         } else {
1485                 pri = SCHED_PRI_MIN;
1486                 if (td->td_sched->ts_ticks)
1487                         pri += SCHED_PRI_TICKS(td->td_sched);
1488                 pri += SCHED_PRI_NICE(td->td_proc->p_nice);
1489                 KASSERT(pri >= PRI_MIN_TIMESHARE && pri <= PRI_MAX_TIMESHARE,
1490                     ("sched_priority: invalid priority %d: nice %d, "
1491                     "ticks %d ftick %d ltick %d tick pri %d",
1492                     pri, td->td_proc->p_nice, td->td_sched->ts_ticks,
1493                     td->td_sched->ts_ftick, td->td_sched->ts_ltick,
1494                     SCHED_PRI_TICKS(td->td_sched)));
1495         }
1496         sched_user_prio(td, pri);
1497
1498         return;
1499 }
1500
1501 /*
1502  * This routine enforces a maximum limit on the amount of scheduling history
1503  * kept.  It is called after either the slptime or runtime is adjusted.  This
1504  * function is ugly due to integer math.
1505  */
1506 static void
1507 sched_interact_update(struct thread *td)
1508 {
1509         struct td_sched *ts;
1510         u_int sum;
1511
1512         ts = td->td_sched;
1513         sum = ts->ts_runtime + ts->ts_slptime;
1514         if (sum < SCHED_SLP_RUN_MAX)
1515                 return;
1516         /*
1517          * This only happens from two places:
1518          * 1) We have added an unusual amount of run time from fork_exit.
1519          * 2) We have added an unusual amount of sleep time from sched_sleep().
1520          */
1521         if (sum > SCHED_SLP_RUN_MAX * 2) {
1522                 if (ts->ts_runtime > ts->ts_slptime) {
1523                         ts->ts_runtime = SCHED_SLP_RUN_MAX;
1524                         ts->ts_slptime = 1;
1525                 } else {
1526                         ts->ts_slptime = SCHED_SLP_RUN_MAX;
1527                         ts->ts_runtime = 1;
1528                 }
1529                 return;
1530         }
1531         /*
1532          * If we have exceeded by more than 1/5th then the algorithm below
1533          * will not bring us back into range.  Dividing by two here forces
1534          * us into the range of [4/5 * SCHED_INTERACT_MAX, SCHED_INTERACT_MAX]
1535          */
1536         if (sum > (SCHED_SLP_RUN_MAX / 5) * 6) {
1537                 ts->ts_runtime /= 2;
1538                 ts->ts_slptime /= 2;
1539                 return;
1540         }
1541         ts->ts_runtime = (ts->ts_runtime / 5) * 4;
1542         ts->ts_slptime = (ts->ts_slptime / 5) * 4;
1543 }
1544
1545 /*
1546  * Scale back the interactivity history when a child thread is created.  The
1547  * history is inherited from the parent but the thread may behave totally
1548  * differently.  For example, a shell spawning a compiler process.  We want
1549  * to learn that the compiler is behaving badly very quickly.
1550  */
1551 static void
1552 sched_interact_fork(struct thread *td)
1553 {
1554         int ratio;
1555         int sum;
1556
1557         sum = td->td_sched->ts_runtime + td->td_sched->ts_slptime;
1558         if (sum > SCHED_SLP_RUN_FORK) {
1559                 ratio = sum / SCHED_SLP_RUN_FORK;
1560                 td->td_sched->ts_runtime /= ratio;
1561                 td->td_sched->ts_slptime /= ratio;
1562         }
1563 }
1564
1565 /*
1566  * Called from proc0_init() to setup the scheduler fields.
1567  */
1568 void
1569 schedinit(void)
1570 {
1571
1572         /*
1573          * Set up the scheduler specific parts of proc0.
1574          */
1575         proc0.p_sched = NULL; /* XXX */
1576         thread0.td_sched = &td_sched0;
1577         td_sched0.ts_ltick = ticks;
1578         td_sched0.ts_ftick = ticks;
1579         td_sched0.ts_thread = &thread0;
1580 }
1581
1582 /*
1583  * This is only somewhat accurate since given many processes of the same
1584  * priority they will switch when their slices run out, which will be
1585  * at most sched_slice stathz ticks.
1586  */
1587 int
1588 sched_rr_interval(void)
1589 {
1590
1591         /* Convert sched_slice to hz */
1592         return (hz/(realstathz/sched_slice));
1593 }
1594
1595 /*
1596  * Update the percent cpu tracking information when it is requested or
1597  * the total history exceeds the maximum.  We keep a sliding history of
1598  * tick counts that slowly decays.  This is less precise than the 4BSD
1599  * mechanism since it happens with less regular and frequent events.
1600  */
1601 static void
1602 sched_pctcpu_update(struct td_sched *ts)
1603 {
1604
1605         if (ts->ts_ticks == 0)
1606                 return;
1607         if (ticks - (hz / 10) < ts->ts_ltick &&
1608             SCHED_TICK_TOTAL(ts) < SCHED_TICK_MAX)
1609                 return;
1610         /*
1611          * Adjust counters and watermark for pctcpu calc.
1612          */
1613         if (ts->ts_ltick > ticks - SCHED_TICK_TARG)
1614                 ts->ts_ticks = (ts->ts_ticks / (ticks - ts->ts_ftick)) *
1615                             SCHED_TICK_TARG;
1616         else
1617                 ts->ts_ticks = 0;
1618         ts->ts_ltick = ticks;
1619         ts->ts_ftick = ts->ts_ltick - SCHED_TICK_TARG;
1620 }
1621
1622 /*
1623  * Adjust the priority of a thread.  Move it to the appropriate run-queue
1624  * if necessary.  This is the back-end for several priority related
1625  * functions.
1626  */
1627 static void
1628 sched_thread_priority(struct thread *td, u_char prio)
1629 {
1630         struct td_sched *ts;
1631
1632         CTR6(KTR_SCHED, "sched_prio: %p(%s) prio %d newprio %d by %p(%s)",
1633             td, td->td_proc->p_comm, td->td_priority, prio, curthread,
1634             curthread->td_proc->p_comm);
1635         ts = td->td_sched;
1636         THREAD_LOCK_ASSERT(td, MA_OWNED);
1637         if (td->td_priority == prio)
1638                 return;
1639
1640         if (TD_ON_RUNQ(td) && prio < td->td_priority) {
1641                 /*
1642                  * If the priority has been elevated due to priority
1643                  * propagation, we may have to move ourselves to a new
1644                  * queue.  This could be optimized to not re-add in some
1645                  * cases.
1646                  */
1647                 sched_rem(td);
1648                 td->td_priority = prio;
1649                 sched_add(td, SRQ_BORROWING);
1650         } else {
1651 #ifdef SMP
1652                 struct tdq *tdq;
1653
1654                 tdq = TDQ_CPU(ts->ts_cpu);
1655                 if (prio < tdq->tdq_lowpri)
1656                         tdq->tdq_lowpri = prio;
1657 #endif
1658                 td->td_priority = prio;
1659         }
1660 }
1661
1662 /*
1663  * Update a thread's priority when it is lent another thread's
1664  * priority.
1665  */
1666 void
1667 sched_lend_prio(struct thread *td, u_char prio)
1668 {
1669
1670         td->td_flags |= TDF_BORROWING;
1671         sched_thread_priority(td, prio);
1672 }
1673
1674 /*
1675  * Restore a thread's priority when priority propagation is
1676  * over.  The prio argument is the minimum priority the thread
1677  * needs to have to satisfy other possible priority lending
1678  * requests.  If the thread's regular priority is less
1679  * important than prio, the thread will keep a priority boost
1680  * of prio.
1681  */
1682 void
1683 sched_unlend_prio(struct thread *td, u_char prio)
1684 {
1685         u_char base_pri;
1686
1687         if (td->td_base_pri >= PRI_MIN_TIMESHARE &&
1688             td->td_base_pri <= PRI_MAX_TIMESHARE)
1689                 base_pri = td->td_user_pri;
1690         else
1691                 base_pri = td->td_base_pri;
1692         if (prio >= base_pri) {
1693                 td->td_flags &= ~TDF_BORROWING;
1694                 sched_thread_priority(td, base_pri);
1695         } else
1696                 sched_lend_prio(td, prio);
1697 }
1698
1699 /*
1700  * Standard entry for setting the priority to an absolute value.
1701  */
1702 void
1703 sched_prio(struct thread *td, u_char prio)
1704 {
1705         u_char oldprio;
1706
1707         /* First, update the base priority. */
1708         td->td_base_pri = prio;
1709
1710         /*
1711          * If the thread is borrowing another thread's priority, don't
1712          * ever lower the priority.
1713          */
1714         if (td->td_flags & TDF_BORROWING && td->td_priority < prio)
1715                 return;
1716
1717         /* Change the real priority. */
1718         oldprio = td->td_priority;
1719         sched_thread_priority(td, prio);
1720
1721         /*
1722          * If the thread is on a turnstile, then let the turnstile update
1723          * its state.
1724          */
1725         if (TD_ON_LOCK(td) && oldprio != prio)
1726                 turnstile_adjust(td, oldprio);
1727 }
1728
1729 /*
1730  * Set the base user priority, does not effect current running priority.
1731  */
1732 void
1733 sched_user_prio(struct thread *td, u_char prio)
1734 {
1735         u_char oldprio;
1736
1737         td->td_base_user_pri = prio;
1738         if (td->td_flags & TDF_UBORROWING && td->td_user_pri <= prio)
1739                 return;
1740         oldprio = td->td_user_pri;
1741         td->td_user_pri = prio;
1742 }
1743
1744 void
1745 sched_lend_user_prio(struct thread *td, u_char prio)
1746 {
1747         u_char oldprio;
1748
1749         THREAD_LOCK_ASSERT(td, MA_OWNED);
1750         td->td_flags |= TDF_UBORROWING;
1751         oldprio = td->td_user_pri;
1752         td->td_user_pri = prio;
1753 }
1754
1755 void
1756 sched_unlend_user_prio(struct thread *td, u_char prio)
1757 {
1758         u_char base_pri;
1759
1760         THREAD_LOCK_ASSERT(td, MA_OWNED);
1761         base_pri = td->td_base_user_pri;
1762         if (prio >= base_pri) {
1763                 td->td_flags &= ~TDF_UBORROWING;
1764                 sched_user_prio(td, base_pri);
1765         } else {
1766                 sched_lend_user_prio(td, prio);
1767         }
1768 }
1769
1770 /*
1771  * Add the thread passed as 'newtd' to the run queue before selecting
1772  * the next thread to run.  This is only used for KSE.
1773  */
1774 static void
1775 sched_switchin(struct tdq *tdq, struct thread *td)
1776 {
1777 #ifdef SMP
1778         spinlock_enter();
1779         TDQ_UNLOCK(tdq);
1780         thread_lock(td);
1781         spinlock_exit();
1782         sched_setcpu(td->td_sched, TDQ_ID(tdq), SRQ_YIELDING);
1783 #else
1784         td->td_lock = TDQ_LOCKPTR(tdq);
1785 #endif
1786         tdq_add(tdq, td, SRQ_YIELDING);
1787         MPASS(td->td_lock == TDQ_LOCKPTR(tdq));
1788 }
1789
1790 /*
1791  * Block a thread for switching.  Similar to thread_block() but does not
1792  * bump the spin count.
1793  */
1794 static inline struct mtx *
1795 thread_block_switch(struct thread *td)
1796 {
1797         struct mtx *lock;
1798
1799         THREAD_LOCK_ASSERT(td, MA_OWNED);
1800         lock = td->td_lock;
1801         td->td_lock = &blocked_lock;
1802         mtx_unlock_spin(lock);
1803
1804         return (lock);
1805 }
1806
1807 /*
1808  * Handle migration from sched_switch().  This happens only for
1809  * cpu binding.
1810  */
1811 static struct mtx *
1812 sched_switch_migrate(struct tdq *tdq, struct thread *td, int flags)
1813 {
1814         struct tdq *tdn;
1815
1816         tdn = TDQ_CPU(td->td_sched->ts_cpu);
1817 #ifdef SMP
1818         /*
1819          * Do the lock dance required to avoid LOR.  We grab an extra
1820          * spinlock nesting to prevent preemption while we're
1821          * not holding either run-queue lock.
1822          */
1823         spinlock_enter();
1824         thread_block_switch(td);        /* This releases the lock on tdq. */
1825         TDQ_LOCK(tdn);
1826         tdq_add(tdn, td, flags);
1827         tdq_notify(td->td_sched);
1828         /*
1829          * After we unlock tdn the new cpu still can't switch into this
1830          * thread until we've unblocked it in cpu_switch().  The lock
1831          * pointers may match in the case of HTT cores.  Don't unlock here
1832          * or we can deadlock when the other CPU runs the IPI handler.
1833          */
1834         if (TDQ_LOCKPTR(tdn) != TDQ_LOCKPTR(tdq)) {
1835                 TDQ_UNLOCK(tdn);
1836                 TDQ_LOCK(tdq);
1837         }
1838         spinlock_exit();
1839 #endif
1840         return (TDQ_LOCKPTR(tdn));
1841 }
1842
1843 /*
1844  * Release a thread that was blocked with thread_block_switch().
1845  */
1846 static inline void
1847 thread_unblock_switch(struct thread *td, struct mtx *mtx)
1848 {
1849         atomic_store_rel_ptr((volatile uintptr_t *)&td->td_lock,
1850             (uintptr_t)mtx);
1851 }
1852
1853 /*
1854  * Switch threads.  This function has to handle threads coming in while
1855  * blocked for some reason, running, or idle.  It also must deal with
1856  * migrating a thread from one queue to another as running threads may
1857  * be assigned elsewhere via binding.
1858  */
1859 void
1860 sched_switch(struct thread *td, struct thread *newtd, int flags)
1861 {
1862         struct tdq *tdq;
1863         struct td_sched *ts;
1864         struct mtx *mtx;
1865         int srqflag;
1866         int cpuid;
1867
1868         THREAD_LOCK_ASSERT(td, MA_OWNED);
1869
1870         cpuid = PCPU_GET(cpuid);
1871         tdq = TDQ_CPU(cpuid);
1872         ts = td->td_sched;
1873         mtx = td->td_lock;
1874 #ifdef SMP
1875         ts->ts_rltick = ticks;
1876         if (newtd && newtd->td_priority < tdq->tdq_lowpri)
1877                 tdq->tdq_lowpri = newtd->td_priority;
1878 #endif
1879         td->td_lastcpu = td->td_oncpu;
1880         td->td_oncpu = NOCPU;
1881         td->td_flags &= ~TDF_NEEDRESCHED;
1882         td->td_owepreempt = 0;
1883         /*
1884          * The lock pointer in an idle thread should never change.  Reset it
1885          * to CAN_RUN as well.
1886          */
1887         if (TD_IS_IDLETHREAD(td)) {
1888                 MPASS(td->td_lock == TDQ_LOCKPTR(tdq));
1889                 TD_SET_CAN_RUN(td);
1890         } else if (TD_IS_RUNNING(td)) {
1891                 MPASS(td->td_lock == TDQ_LOCKPTR(tdq));
1892                 tdq_load_rem(tdq, ts);
1893                 srqflag = (flags & SW_PREEMPT) ?
1894                     SRQ_OURSELF|SRQ_YIELDING|SRQ_PREEMPTED :
1895                     SRQ_OURSELF|SRQ_YIELDING;
1896                 if (ts->ts_cpu == cpuid)
1897                         tdq_add(tdq, td, srqflag);
1898                 else
1899                         mtx = sched_switch_migrate(tdq, td, srqflag);
1900         } else {
1901                 /* This thread must be going to sleep. */
1902                 TDQ_LOCK(tdq);
1903                 mtx = thread_block_switch(td);
1904                 tdq_load_rem(tdq, ts);
1905         }
1906         /*
1907          * We enter here with the thread blocked and assigned to the
1908          * appropriate cpu run-queue or sleep-queue and with the current
1909          * thread-queue locked.
1910          */
1911         TDQ_LOCK_ASSERT(tdq, MA_OWNED | MA_NOTRECURSED);
1912         /*
1913          * If KSE assigned a new thread just add it here and let choosethread
1914          * select the best one.
1915          */
1916         if (newtd != NULL)
1917                 sched_switchin(tdq, newtd);
1918         newtd = choosethread();
1919         /*
1920          * Call the MD code to switch contexts if necessary.
1921          */
1922         if (td != newtd) {
1923 #ifdef  HWPMC_HOOKS
1924                 if (PMC_PROC_IS_USING_PMCS(td->td_proc))
1925                         PMC_SWITCH_CONTEXT(td, PMC_FN_CSW_OUT);
1926 #endif
1927                 TDQ_LOCKPTR(tdq)->mtx_lock = (uintptr_t)newtd;
1928
1929 #ifdef KDTRACE_HOOKS
1930                 /*
1931                  * If DTrace has set the active vtime enum to anything
1932                  * other than INACTIVE (0), then it should have set the
1933                  * function to call.
1934                  */
1935                 if (dtrace_vtime_active)
1936                         (*dtrace_vtime_switch_func)(newtd);
1937 #endif
1938                 cpu_switch(td, newtd, mtx);
1939                 /*
1940                  * We may return from cpu_switch on a different cpu.  However,
1941                  * we always return with td_lock pointing to the current cpu's
1942                  * run queue lock.
1943                  */
1944                 cpuid = PCPU_GET(cpuid);
1945                 tdq = TDQ_CPU(cpuid);
1946 #ifdef  HWPMC_HOOKS
1947                 if (PMC_PROC_IS_USING_PMCS(td->td_proc))
1948                         PMC_SWITCH_CONTEXT(td, PMC_FN_CSW_IN);
1949 #endif
1950         } else
1951                 thread_unblock_switch(td, mtx);
1952         /*
1953          * Assert that all went well and return.
1954          */
1955 #ifdef SMP
1956         /* We should always get here with the lowest priority td possible */
1957         tdq->tdq_lowpri = td->td_priority;
1958 #endif
1959         TDQ_LOCK_ASSERT(tdq, MA_OWNED|MA_NOTRECURSED);
1960         MPASS(td->td_lock == TDQ_LOCKPTR(tdq));
1961         td->td_oncpu = cpuid;
1962 }
1963
1964 /*
1965  * Adjust thread priorities as a result of a nice request.
1966  */
1967 void
1968 sched_nice(struct proc *p, int nice)
1969 {
1970         struct thread *td;
1971
1972         PROC_LOCK_ASSERT(p, MA_OWNED);
1973         PROC_SLOCK_ASSERT(p, MA_OWNED);
1974
1975         p->p_nice = nice;
1976         FOREACH_THREAD_IN_PROC(p, td) {
1977                 thread_lock(td);
1978                 sched_priority(td);
1979                 sched_prio(td, td->td_base_user_pri);
1980                 thread_unlock(td);
1981         }
1982 }
1983
1984 /*
1985  * Record the sleep time for the interactivity scorer.
1986  */
1987 void
1988 sched_sleep(struct thread *td)
1989 {
1990
1991         THREAD_LOCK_ASSERT(td, MA_OWNED);
1992
1993         td->td_slptick = ticks;
1994 }
1995
1996 /*
1997  * Schedule a thread to resume execution and record how long it voluntarily
1998  * slept.  We also update the pctcpu, interactivity, and priority.
1999  */
2000 void
2001 sched_wakeup(struct thread *td)
2002 {
2003         struct td_sched *ts;
2004         int slptick;
2005
2006         THREAD_LOCK_ASSERT(td, MA_OWNED);
2007         ts = td->td_sched;
2008         /*
2009          * If we slept for more than a tick update our interactivity and
2010          * priority.
2011          */
2012         slptick = td->td_slptick;
2013         td->td_slptick = 0;
2014         if (slptick && slptick != ticks) {
2015                 u_int hzticks;
2016
2017                 hzticks = (ticks - slptick) << SCHED_TICK_SHIFT;
2018                 ts->ts_slptime += hzticks;
2019                 sched_interact_update(td);
2020                 sched_pctcpu_update(ts);
2021                 sched_priority(td);
2022         }
2023         /* Reset the slice value after we sleep. */
2024         ts->ts_slice = sched_slice;
2025         sched_add(td, SRQ_BORING);
2026 }
2027
2028 /*
2029  * Penalize the parent for creating a new child and initialize the child's
2030  * priority.
2031  */
2032 void
2033 sched_fork(struct thread *td, struct thread *child)
2034 {
2035         THREAD_LOCK_ASSERT(td, MA_OWNED);
2036         sched_fork_thread(td, child);
2037         /*
2038          * Penalize the parent and child for forking.
2039          */
2040         sched_interact_fork(child);
2041         sched_priority(child);
2042         td->td_sched->ts_runtime += tickincr;
2043         sched_interact_update(td);
2044         sched_priority(td);
2045 }
2046
2047 /*
2048  * Fork a new thread, may be within the same process.
2049  */
2050 void
2051 sched_fork_thread(struct thread *td, struct thread *child)
2052 {
2053         struct td_sched *ts;
2054         struct td_sched *ts2;
2055
2056         /*
2057          * Initialize child.
2058          */
2059         THREAD_LOCK_ASSERT(td, MA_OWNED);
2060         sched_newthread(child);
2061         child->td_lock = TDQ_LOCKPTR(TDQ_SELF());
2062         child->td_cpuset = cpuset_ref(td->td_cpuset);
2063         ts = td->td_sched;
2064         ts2 = child->td_sched;
2065         ts2->ts_cpu = ts->ts_cpu;
2066         ts2->ts_runq = NULL;
2067         /*
2068          * Grab our parents cpu estimation information and priority.
2069          */
2070         ts2->ts_ticks = ts->ts_ticks;
2071         ts2->ts_ltick = ts->ts_ltick;
2072         ts2->ts_ftick = ts->ts_ftick;
2073         child->td_user_pri = td->td_user_pri;
2074         child->td_base_user_pri = td->td_base_user_pri;
2075         /*
2076          * And update interactivity score.
2077          */
2078         ts2->ts_slptime = ts->ts_slptime;
2079         ts2->ts_runtime = ts->ts_runtime;
2080         ts2->ts_slice = 1;      /* Attempt to quickly learn interactivity. */
2081 }
2082
2083 /*
2084  * Adjust the priority class of a thread.
2085  */
2086 void
2087 sched_class(struct thread *td, int class)
2088 {
2089
2090         THREAD_LOCK_ASSERT(td, MA_OWNED);
2091         if (td->td_pri_class == class)
2092                 return;
2093
2094 #ifdef SMP
2095         /*
2096          * On SMP if we're on the RUNQ we must adjust the transferable
2097          * count because could be changing to or from an interrupt
2098          * class.
2099          */
2100         if (TD_ON_RUNQ(td)) {
2101                 struct tdq *tdq;
2102
2103                 tdq = TDQ_CPU(td->td_sched->ts_cpu);
2104                 if (THREAD_CAN_MIGRATE(td)) {
2105                         tdq->tdq_transferable--;
2106                         tdq->tdq_group->tdg_transferable--;
2107                 }
2108                 td->td_pri_class = class;
2109                 if (THREAD_CAN_MIGRATE(td)) {
2110                         tdq->tdq_transferable++;
2111                         tdq->tdq_group->tdg_transferable++;
2112                 }
2113         }
2114 #endif
2115         td->td_pri_class = class;
2116 }
2117
2118 /*
2119  * Return some of the child's priority and interactivity to the parent.
2120  */
2121 void
2122 sched_exit(struct proc *p, struct thread *child)
2123 {
2124         struct thread *td;
2125
2126         CTR3(KTR_SCHED, "sched_exit: %p(%s) prio %d",
2127             child, child->td_proc->p_comm, child->td_priority);
2128
2129         PROC_SLOCK_ASSERT(p, MA_OWNED);
2130         td = FIRST_THREAD_IN_PROC(p);
2131         sched_exit_thread(td, child);
2132 }
2133
2134 /*
2135  * Penalize another thread for the time spent on this one.  This helps to
2136  * worsen the priority and interactivity of processes which schedule batch
2137  * jobs such as make.  This has little effect on the make process itself but
2138  * causes new processes spawned by it to receive worse scores immediately.
2139  */
2140 void
2141 sched_exit_thread(struct thread *td, struct thread *child)
2142 {
2143
2144         CTR3(KTR_SCHED, "sched_exit_thread: %p(%s) prio %d",
2145             child, child->td_proc->p_comm, child->td_priority);
2146
2147 #ifdef KSE
2148         /*
2149          * KSE forks and exits so often that this penalty causes short-lived
2150          * threads to always be non-interactive.  This causes mozilla to
2151          * crawl under load.
2152          */
2153         if ((td->td_pflags & TDP_SA) && td->td_proc == child->td_proc)
2154                 return;
2155 #endif
2156         /*
2157          * Give the child's runtime to the parent without returning the
2158          * sleep time as a penalty to the parent.  This causes shells that
2159          * launch expensive things to mark their children as expensive.
2160          */
2161         thread_lock(td);
2162         td->td_sched->ts_runtime += child->td_sched->ts_runtime;
2163         sched_interact_update(td);
2164         sched_priority(td);
2165         thread_unlock(td);
2166 }
2167
2168 /*
2169  * Fix priorities on return to user-space.  Priorities may be elevated due
2170  * to static priorities in msleep() or similar.
2171  */
2172 void
2173 sched_userret(struct thread *td)
2174 {
2175         /*
2176          * XXX we cheat slightly on the locking here to avoid locking in
2177          * the usual case.  Setting td_priority here is essentially an
2178          * incomplete workaround for not setting it properly elsewhere.
2179          * Now that some interrupt handlers are threads, not setting it
2180          * properly elsewhere can clobber it in the window between setting
2181          * it here and returning to user mode, so don't waste time setting
2182          * it perfectly here.
2183          */
2184         KASSERT((td->td_flags & TDF_BORROWING) == 0,
2185             ("thread with borrowed priority returning to userland"));
2186         if (td->td_priority != td->td_user_pri) {
2187                 thread_lock(td);
2188                 td->td_priority = td->td_user_pri;
2189                 td->td_base_pri = td->td_user_pri;
2190                 thread_unlock(td);
2191         }
2192 }
2193
2194 /*
2195  * Handle a stathz tick.  This is really only relevant for timeshare
2196  * threads.
2197  */
2198 void
2199 sched_clock(struct thread *td)
2200 {
2201         struct tdq *tdq;
2202         struct td_sched *ts;
2203
2204         THREAD_LOCK_ASSERT(td, MA_OWNED);
2205         tdq = TDQ_SELF();
2206 #ifdef SMP
2207         /*
2208          * We run the long term load balancer infrequently on the first cpu.
2209          */
2210         if (balance_tdq == tdq) {
2211                 if (balance_ticks && --balance_ticks == 0)
2212                         sched_balance();
2213                 if (balance_group_ticks && --balance_group_ticks == 0)
2214                         sched_balance_groups();
2215         }
2216 #endif
2217         /*
2218          * Advance the insert index once for each tick to ensure that all
2219          * threads get a chance to run.
2220          */
2221         if (tdq->tdq_idx == tdq->tdq_ridx) {
2222                 tdq->tdq_idx = (tdq->tdq_idx + 1) % RQ_NQS;
2223                 if (TAILQ_EMPTY(&tdq->tdq_timeshare.rq_queues[tdq->tdq_ridx]))
2224                         tdq->tdq_ridx = tdq->tdq_idx;
2225         }
2226         ts = td->td_sched;
2227         if (td->td_pri_class & PRI_FIFO_BIT)
2228                 return;
2229         if (td->td_pri_class == PRI_TIMESHARE) {
2230                 /*
2231                  * We used a tick; charge it to the thread so
2232                  * that we can compute our interactivity.
2233                  */
2234                 td->td_sched->ts_runtime += tickincr;
2235                 sched_interact_update(td);
2236         }
2237         /*
2238          * We used up one time slice.
2239          */
2240         if (--ts->ts_slice > 0)
2241                 return;
2242         /*
2243          * We're out of time, recompute priorities and requeue.
2244          */
2245         sched_priority(td);
2246         td->td_flags |= TDF_NEEDRESCHED;
2247 }
2248
2249 /*
2250  * Called once per hz tick.  Used for cpu utilization information.  This
2251  * is easier than trying to scale based on stathz.
2252  */
2253 void
2254 sched_tick(void)
2255 {
2256         struct td_sched *ts;
2257
2258         ts = curthread->td_sched;
2259         /*
2260          * Ticks is updated asynchronously on a single cpu.  Check here to
2261          * avoid incrementing ts_ticks multiple times in a single tick.
2262          */
2263         if (ts->ts_ltick == ticks)
2264                 return;
2265         /* Adjust ticks for pctcpu */
2266         ts->ts_ticks += 1 << SCHED_TICK_SHIFT;
2267         ts->ts_ltick = ticks;
2268         /*
2269          * Update if we've exceeded our desired tick threshhold by over one
2270          * second.
2271          */
2272         if (ts->ts_ftick + SCHED_TICK_MAX < ts->ts_ltick)
2273                 sched_pctcpu_update(ts);
2274 }
2275
2276 /*
2277  * Return whether the current CPU has runnable tasks.  Used for in-kernel
2278  * cooperative idle threads.
2279  */
2280 int
2281 sched_runnable(void)
2282 {
2283         struct tdq *tdq;
2284         int load;
2285
2286         load = 1;
2287
2288         tdq = TDQ_SELF();
2289         if ((curthread->td_flags & TDF_IDLETD) != 0) {
2290                 if (tdq->tdq_load > 0)
2291                         goto out;
2292         } else
2293                 if (tdq->tdq_load - 1 > 0)
2294                         goto out;
2295         load = 0;
2296 out:
2297         return (load);
2298 }
2299
2300 /*
2301  * Choose the highest priority thread to run.  The thread is removed from
2302  * the run-queue while running however the load remains.  For SMP we set
2303  * the tdq in the global idle bitmask if it idles here.
2304  */
2305 struct thread *
2306 sched_choose(void)
2307 {
2308 #ifdef SMP
2309         struct tdq_group *tdg;
2310 #endif
2311         struct td_sched *ts;
2312         struct tdq *tdq;
2313
2314         tdq = TDQ_SELF();
2315         TDQ_LOCK_ASSERT(tdq, MA_OWNED);
2316         ts = tdq_choose(tdq);
2317         if (ts) {
2318                 tdq_runq_rem(tdq, ts);
2319                 return (ts->ts_thread);
2320         }
2321 #ifdef SMP
2322         /*
2323          * We only set the idled bit when all of the cpus in the group are
2324          * idle.  Otherwise we could get into a situation where a thread bounces
2325          * back and forth between two idle cores on seperate physical CPUs.
2326          */
2327         tdg = tdq->tdq_group;
2328         tdg->tdg_idlemask |= PCPU_GET(cpumask);
2329         if (tdg->tdg_idlemask == tdg->tdg_cpumask)
2330                 atomic_set_int(&tdq_idle, tdg->tdg_mask);
2331         tdq->tdq_lowpri = PRI_MAX_IDLE;
2332 #endif
2333         return (PCPU_GET(idlethread));
2334 }
2335
2336 /*
2337  * Set owepreempt if necessary.  Preemption never happens directly in ULE,
2338  * we always request it once we exit a critical section.
2339  */
2340 static inline void
2341 sched_setpreempt(struct thread *td)
2342 {
2343         struct thread *ctd;
2344         int cpri;
2345         int pri;
2346
2347         ctd = curthread;
2348         pri = td->td_priority;
2349         cpri = ctd->td_priority;
2350         if (td->td_priority < ctd->td_priority)
2351                 curthread->td_flags |= TDF_NEEDRESCHED;
2352         if (panicstr != NULL || pri >= cpri || cold || TD_IS_INHIBITED(ctd))
2353                 return;
2354         /*
2355          * Always preempt IDLE threads.  Otherwise only if the preempting
2356          * thread is an ithread.
2357          */
2358         if (pri > preempt_thresh && cpri < PRI_MIN_IDLE)
2359                 return;
2360         ctd->td_owepreempt = 1;
2361         return;
2362 }
2363
2364 /*
2365  * Add a thread to a thread queue.  Initializes priority, slice, runq, and
2366  * add it to the appropriate queue.  This is the internal function called
2367  * when the tdq is predetermined.
2368  */
2369 void
2370 tdq_add(struct tdq *tdq, struct thread *td, int flags)
2371 {
2372         struct td_sched *ts;
2373         int class;
2374 #ifdef SMP
2375         int cpumask;
2376 #endif
2377
2378         TDQ_LOCK_ASSERT(tdq, MA_OWNED);
2379         KASSERT((td->td_inhibitors == 0),
2380             ("sched_add: trying to run inhibited thread"));
2381         KASSERT((TD_CAN_RUN(td) || TD_IS_RUNNING(td)),
2382             ("sched_add: bad thread state"));
2383         KASSERT(td->td_flags & TDF_INMEM,
2384             ("sched_add: thread swapped out"));
2385
2386         ts = td->td_sched;
2387         class = PRI_BASE(td->td_pri_class);
2388         TD_SET_RUNQ(td);
2389         if (ts->ts_slice == 0)
2390                 ts->ts_slice = sched_slice;
2391         /*
2392          * Pick the run queue based on priority.
2393          */
2394         if (td->td_priority <= PRI_MAX_REALTIME)
2395                 ts->ts_runq = &tdq->tdq_realtime;
2396         else if (td->td_priority <= PRI_MAX_TIMESHARE)
2397                 ts->ts_runq = &tdq->tdq_timeshare;
2398         else
2399                 ts->ts_runq = &tdq->tdq_idle;
2400 #ifdef SMP
2401         cpumask = 1 << ts->ts_cpu;
2402         /*
2403          * If we had been idle, clear our bit in the group and potentially
2404          * the global bitmap.
2405          */
2406         if ((class != PRI_IDLE && class != PRI_ITHD) &&
2407             (tdq->tdq_group->tdg_idlemask & cpumask) != 0) {
2408                 /*
2409                  * Check to see if our group is unidling, and if so, remove it
2410                  * from the global idle mask.
2411                  */
2412                 if (tdq->tdq_group->tdg_idlemask ==
2413                     tdq->tdq_group->tdg_cpumask)
2414                         atomic_clear_int(&tdq_idle, tdq->tdq_group->tdg_mask);
2415                 /*
2416                  * Now remove ourselves from the group specific idle mask.
2417                  */
2418                 tdq->tdq_group->tdg_idlemask &= ~cpumask;
2419         }
2420         if (td->td_priority < tdq->tdq_lowpri)
2421                 tdq->tdq_lowpri = td->td_priority;
2422 #endif
2423         tdq_runq_add(tdq, ts, flags);
2424         tdq_load_add(tdq, ts);
2425 }
2426
2427 /*
2428  * Select the target thread queue and add a thread to it.  Request
2429  * preemption or IPI a remote processor if required.
2430  */
2431 void
2432 sched_add(struct thread *td, int flags)
2433 {
2434         struct td_sched *ts;
2435         struct tdq *tdq;
2436 #ifdef SMP
2437         int cpuid;
2438         int cpu;
2439 #endif
2440         CTR5(KTR_SCHED, "sched_add: %p(%s) prio %d by %p(%s)",
2441             td, td->td_proc->p_comm, td->td_priority, curthread,
2442             curthread->td_proc->p_comm);
2443         THREAD_LOCK_ASSERT(td, MA_OWNED);
2444         ts = td->td_sched;
2445         /*
2446          * Recalculate the priority before we select the target cpu or
2447          * run-queue.
2448          */
2449         if (PRI_BASE(td->td_pri_class) == PRI_TIMESHARE)
2450                 sched_priority(td);
2451 #ifdef SMP
2452         cpuid = PCPU_GET(cpuid);
2453         /*
2454          * Pick the destination cpu and if it isn't ours transfer to the
2455          * target cpu.
2456          */
2457         if (td->td_priority <= PRI_MAX_ITHD && THREAD_CAN_MIGRATE(td) &&
2458             curthread->td_intr_nesting_level)
2459                 ts->ts_cpu = cpuid;
2460         if (!THREAD_CAN_MIGRATE(td))
2461                 cpu = ts->ts_cpu;
2462         else
2463                 cpu = sched_pickcpu(td, flags);
2464         tdq = sched_setcpu(ts, cpu, flags);
2465         tdq_add(tdq, td, flags);
2466         if (cpu != cpuid) {
2467                 tdq_notify(ts);
2468                 return;
2469         }
2470 #else
2471         tdq = TDQ_SELF();
2472         TDQ_LOCK(tdq);
2473         /*
2474          * Now that the thread is moving to the run-queue, set the lock
2475          * to the scheduler's lock.
2476          */
2477         thread_lock_set(td, TDQ_LOCKPTR(tdq));
2478         tdq_add(tdq, td, flags);
2479 #endif
2480         if (!(flags & SRQ_YIELDING))
2481                 sched_setpreempt(td);
2482 }
2483
2484 /*
2485  * Remove a thread from a run-queue without running it.  This is used
2486  * when we're stealing a thread from a remote queue.  Otherwise all threads
2487  * exit by calling sched_exit_thread() and sched_throw() themselves.
2488  */
2489 void
2490 sched_rem(struct thread *td)
2491 {
2492         struct tdq *tdq;
2493         struct td_sched *ts;
2494
2495         CTR5(KTR_SCHED, "sched_rem: %p(%s) prio %d by %p(%s)",
2496             td, td->td_proc->p_comm, td->td_priority, curthread,
2497             curthread->td_proc->p_comm);
2498         ts = td->td_sched;
2499         tdq = TDQ_CPU(ts->ts_cpu);
2500         TDQ_LOCK_ASSERT(tdq, MA_OWNED);
2501         MPASS(td->td_lock == TDQ_LOCKPTR(tdq));
2502         KASSERT(TD_ON_RUNQ(td),
2503             ("sched_rem: thread not on run queue"));
2504         tdq_runq_rem(tdq, ts);
2505         tdq_load_rem(tdq, ts);
2506         TD_SET_CAN_RUN(td);
2507 }
2508
2509 /*
2510  * Fetch cpu utilization information.  Updates on demand.
2511  */
2512 fixpt_t
2513 sched_pctcpu(struct thread *td)
2514 {
2515         fixpt_t pctcpu;
2516         struct td_sched *ts;
2517
2518         pctcpu = 0;
2519         ts = td->td_sched;
2520         if (ts == NULL)
2521                 return (0);
2522
2523         thread_lock(td);
2524         if (ts->ts_ticks) {
2525                 int rtick;
2526
2527                 sched_pctcpu_update(ts);
2528                 /* How many rtick per second ? */
2529                 rtick = min(SCHED_TICK_HZ(ts) / SCHED_TICK_SECS, hz);
2530                 pctcpu = (FSCALE * ((FSCALE * rtick)/hz)) >> FSHIFT;
2531         }
2532         thread_unlock(td);
2533
2534         return (pctcpu);
2535 }
2536
2537 /*
2538  * Enforce affinity settings for a thread.  Called after adjustments to
2539  * cpumask.
2540  */
2541 void
2542 sched_affinity(struct thread *td)
2543 {
2544 #ifdef SMP
2545         struct td_sched *ts;
2546         int cpu;
2547
2548         THREAD_LOCK_ASSERT(td, MA_OWNED);
2549         ts = td->td_sched;
2550         if (THREAD_CAN_SCHED(td, ts->ts_cpu))
2551                 return;
2552         if (TD_ON_RUNQ(td)) {
2553                 sched_rem(td);
2554                 sched_add(td, SRQ_BORING);
2555                 return;
2556         }
2557         if (!TD_IS_RUNNING(td))
2558                 return;
2559         td->td_flags |= TDF_NEEDRESCHED;
2560         if (!THREAD_CAN_MIGRATE(td))
2561                 return;
2562         /*
2563          * Assign the new cpu and force a switch before returning to
2564          * userspace.  If the target thread is not running locally send
2565          * an ipi to force the issue.
2566          */
2567         cpu = ts->ts_cpu;
2568         ts->ts_cpu = sched_pickcpu(td, 0);
2569         if (cpu != PCPU_GET(cpuid))
2570                 ipi_selected(1 << cpu, IPI_PREEMPT);
2571 #endif
2572 }
2573
2574 /*
2575  * Bind a thread to a target cpu.
2576  */
2577 void
2578 sched_bind(struct thread *td, int cpu)
2579 {
2580         struct td_sched *ts;
2581
2582         THREAD_LOCK_ASSERT(td, MA_OWNED|MA_NOTRECURSED);
2583         ts = td->td_sched;
2584         if (ts->ts_flags & TSF_BOUND)
2585                 sched_unbind(td);
2586         ts->ts_flags |= TSF_BOUND;
2587 #ifdef SMP
2588         sched_pin();
2589         if (PCPU_GET(cpuid) == cpu)
2590                 return;
2591         ts->ts_cpu = cpu;
2592         /* When we return from mi_switch we'll be on the correct cpu. */
2593         mi_switch(SW_VOL, NULL);
2594 #endif
2595 }
2596
2597 /*
2598  * Release a bound thread.
2599  */
2600 void
2601 sched_unbind(struct thread *td)
2602 {
2603         struct td_sched *ts;
2604
2605         THREAD_LOCK_ASSERT(td, MA_OWNED);
2606         ts = td->td_sched;
2607         if ((ts->ts_flags & TSF_BOUND) == 0)
2608                 return;
2609         ts->ts_flags &= ~TSF_BOUND;
2610 #ifdef SMP
2611         sched_unpin();
2612 #endif
2613 }
2614
2615 int
2616 sched_is_bound(struct thread *td)
2617 {
2618         THREAD_LOCK_ASSERT(td, MA_OWNED);
2619         return (td->td_sched->ts_flags & TSF_BOUND);
2620 }
2621
2622 /*
2623  * Basic yield call.
2624  */
2625 void
2626 sched_relinquish(struct thread *td)
2627 {
2628         thread_lock(td);
2629         SCHED_STAT_INC(switch_relinquish);
2630         mi_switch(SW_VOL, NULL);
2631         thread_unlock(td);
2632 }
2633
2634 /*
2635  * Return the total system load.
2636  */
2637 int
2638 sched_load(void)
2639 {
2640 #ifdef SMP
2641         int total;
2642         int i;
2643
2644         total = 0;
2645         for (i = 0; i <= tdg_maxid; i++)
2646                 total += TDQ_GROUP(i)->tdg_load;
2647         return (total);
2648 #else
2649         return (TDQ_SELF()->tdq_sysload);
2650 #endif
2651 }
2652
2653 int
2654 sched_sizeof_proc(void)
2655 {
2656         return (sizeof(struct proc));
2657 }
2658
2659 int
2660 sched_sizeof_thread(void)
2661 {
2662         return (sizeof(struct thread) + sizeof(struct td_sched));
2663 }
2664
2665 /*
2666  * The actual idle process.
2667  */
2668 void
2669 sched_idletd(void *dummy)
2670 {
2671         struct thread *td;
2672         struct tdq *tdq;
2673
2674         td = curthread;
2675         tdq = TDQ_SELF();
2676         mtx_assert(&Giant, MA_NOTOWNED);
2677         /* ULE relies on preemption for idle interruption. */
2678         for (;;) {
2679 #ifdef SMP
2680                 if (tdq_idled(tdq))
2681                         cpu_idle();
2682 #else
2683                 cpu_idle();
2684 #endif
2685         }
2686 }
2687
2688 /*
2689  * A CPU is entering for the first time or a thread is exiting.
2690  */
2691 void
2692 sched_throw(struct thread *td)
2693 {
2694         struct thread *newtd;
2695         struct tdq *tdq;
2696
2697         tdq = TDQ_SELF();
2698         if (td == NULL) {
2699                 /* Correct spinlock nesting and acquire the correct lock. */
2700                 TDQ_LOCK(tdq);
2701                 spinlock_exit();
2702         } else {
2703                 MPASS(td->td_lock == TDQ_LOCKPTR(tdq));
2704                 tdq_load_rem(tdq, td->td_sched);
2705         }
2706         KASSERT(curthread->td_md.md_spinlock_count == 1, ("invalid count"));
2707         newtd = choosethread();
2708         TDQ_LOCKPTR(tdq)->mtx_lock = (uintptr_t)newtd;
2709         PCPU_SET(switchtime, cpu_ticks());
2710         PCPU_SET(switchticks, ticks);
2711         cpu_throw(td, newtd);           /* doesn't return */
2712 }
2713
2714 /*
2715  * This is called from fork_exit().  Just acquire the correct locks and
2716  * let fork do the rest of the work.
2717  */
2718 void
2719 sched_fork_exit(struct thread *td)
2720 {
2721         struct td_sched *ts;
2722         struct tdq *tdq;
2723         int cpuid;
2724
2725         /*
2726          * Finish setting up thread glue so that it begins execution in a
2727          * non-nested critical section with the scheduler lock held.
2728          */
2729         cpuid = PCPU_GET(cpuid);
2730         tdq = TDQ_CPU(cpuid);
2731         ts = td->td_sched;
2732         if (TD_IS_IDLETHREAD(td))
2733                 td->td_lock = TDQ_LOCKPTR(tdq);
2734         MPASS(td->td_lock == TDQ_LOCKPTR(tdq));
2735         td->td_oncpu = cpuid;
2736         TDQ_LOCK_ASSERT(tdq, MA_OWNED | MA_NOTRECURSED);
2737 }
2738
2739 static SYSCTL_NODE(_kern, OID_AUTO, sched, CTLFLAG_RW, 0,
2740     "Scheduler");
2741 SYSCTL_STRING(_kern_sched, OID_AUTO, name, CTLFLAG_RD, "ULE", 0,
2742     "Scheduler name");
2743 SYSCTL_INT(_kern_sched, OID_AUTO, slice, CTLFLAG_RW, &sched_slice, 0,
2744     "Slice size for timeshare threads");
2745 SYSCTL_INT(_kern_sched, OID_AUTO, interact, CTLFLAG_RW, &sched_interact, 0,
2746      "Interactivity score threshold");
2747 SYSCTL_INT(_kern_sched, OID_AUTO, preempt_thresh, CTLFLAG_RW, &preempt_thresh,
2748      0,"Min priority for preemption, lower priorities have greater precedence");
2749 #ifdef SMP
2750 SYSCTL_INT(_kern_sched, OID_AUTO, pick_pri, CTLFLAG_RW, &pick_pri, 0,
2751     "Pick the target cpu based on priority rather than load.");
2752 SYSCTL_INT(_kern_sched, OID_AUTO, affinity, CTLFLAG_RW, &affinity, 0,
2753     "Number of hz ticks to keep thread affinity for");
2754 SYSCTL_INT(_kern_sched, OID_AUTO, tryself, CTLFLAG_RW, &tryself, 0, "");
2755 SYSCTL_INT(_kern_sched, OID_AUTO, balance, CTLFLAG_RW, &rebalance, 0,
2756     "Enables the long-term load balancer");
2757 SYSCTL_INT(_kern_sched, OID_AUTO, balance_interval, CTLFLAG_RW,
2758     &balance_interval, 0,
2759     "Average frequency in stathz ticks to run the long-term balancer");
2760 SYSCTL_INT(_kern_sched, OID_AUTO, steal_htt, CTLFLAG_RW, &steal_htt, 0,
2761     "Steals work from another hyper-threaded core on idle");
2762 SYSCTL_INT(_kern_sched, OID_AUTO, steal_idle, CTLFLAG_RW, &steal_idle, 0,
2763     "Attempts to steal work from other cores before idling");
2764 SYSCTL_INT(_kern_sched, OID_AUTO, steal_thresh, CTLFLAG_RW, &steal_thresh, 0,
2765     "Minimum load on remote cpu before we'll steal");
2766 SYSCTL_INT(_kern_sched, OID_AUTO, topology, CTLFLAG_RD, &topology, 0,
2767     "True when a topology has been specified by the MD code.");
2768 #endif
2769
2770 /* ps compat.  All cpu percentages from ULE are weighted. */
2771 static int ccpu = 0;
2772 SYSCTL_INT(_kern, OID_AUTO, ccpu, CTLFLAG_RD, &ccpu, 0, "");
2773
2774
2775 #define KERN_SWITCH_INCLUDE 1
2776 #include "kern/kern_switch.c"