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