sys/kern/sched_ule.c

   1 /*-
   2  * Copyright (c) 2002-2005, 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 #include <sys/cdefs.h>
  28 __FBSDID("$FreeBSD$");
  29
  30 #include "opt_hwpmc_hooks.h"
  31 #include "opt_sched.h"
  32
  33 #define kse td_sched
  34
  35 #include <sys/param.h>
  36 #include <sys/systm.h>
  37 #include <sys/kdb.h>
  38 #include <sys/kernel.h>
  39 #include <sys/ktr.h>
  40 #include <sys/lock.h>
  41 #include <sys/mutex.h>
  42 #include <sys/proc.h>
  43 #include <sys/resource.h>
  44 #include <sys/resourcevar.h>
  45 #include <sys/sched.h>
  46 #include <sys/smp.h>
  47 #include <sys/sx.h>
  48 #include <sys/sysctl.h>
  49 #include <sys/sysproto.h>
  50 #include <sys/turnstile.h>
  51 #include <sys/vmmeter.h>
  52 #ifdef KTRACE
  53 #include <sys/uio.h>
  54 #include <sys/ktrace.h>
  55 #endif
  56
  57 #ifdef HWPMC_HOOKS
  58 #include <sys/pmckern.h>
  59 #endif
  60
  61 #include <machine/cpu.h>
  62 #include <machine/smp.h>
  63
  64 /* decay 95% of `p_pctcpu' in 60 seconds; see CCPU_SHIFT before changing */
  65 /* XXX This is bogus compatability crap for ps */
  66 static fixpt_t  ccpu = 0.95122942450071400909 * FSCALE; /* exp(-1/20) */
  67 SYSCTL_INT(_kern, OID_AUTO, ccpu, CTLFLAG_RD, &ccpu, 0, "");
  68
  69 static void sched_setup(void *dummy);
  70 SYSINIT(sched_setup, SI_SUB_RUN_QUEUE, SI_ORDER_FIRST, sched_setup, NULL)
  71
  72 static void sched_initticks(void *dummy);
  73 SYSINIT(sched_initticks, SI_SUB_CLOCKS, SI_ORDER_THIRD, sched_initticks, NULL)
  74
  75 static SYSCTL_NODE(_kern, OID_AUTO, sched, CTLFLAG_RW, 0, "Scheduler");
  76
  77 SYSCTL_STRING(_kern_sched, OID_AUTO, name, CTLFLAG_RD, "ule", 0,
  78     "Scheduler name");
  79
  80 static int slice_min = 1;
  81 SYSCTL_INT(_kern_sched, OID_AUTO, slice_min, CTLFLAG_RW, &slice_min, 0, "");
  82
  83 static int slice_max = 10;
  84 SYSCTL_INT(_kern_sched, OID_AUTO, slice_max, CTLFLAG_RW, &slice_max, 0, "");
  85
  86 int realstathz;
  87 int tickincr = 1 << 10;
  88
  89 /*
  90  * The following datastructures are allocated within their parent structure
  91  * but are scheduler specific.
  92  */
  93 /*
  94  * The schedulable entity that can be given a context to run.  A process may
  95  * have several of these.
  96  */
  97 struct kse {
  98         TAILQ_ENTRY(kse) ke_procq;      /* (j/z) Run queue. */
  99         int             ke_flags;       /* (j) KEF_* flags. */
 100         struct thread   *ke_thread;     /* (*) Active associated thread. */
 101         fixpt_t         ke_pctcpu;      /* (j) %cpu during p_swtime. */
 102         char            ke_rqindex;     /* (j) Run queue index. */
 103         enum {
 104                 KES_THREAD = 0x0,       /* slaved to thread state */
 105                 KES_ONRUNQ
 106         } ke_state;                     /* (j) thread sched specific status. */
 107         int             ke_slptime;
 108         int             ke_slice;
 109         struct runq     *ke_runq;
 110         u_char          ke_cpu;         /* CPU that we have affinity for. */
 111         /* The following variables are only used for pctcpu calculation */
 112         int             ke_ltick;       /* Last tick that we were running on */
 113         int             ke_ftick;       /* First tick that we were running on */
 114         int             ke_ticks;       /* Tick count */
 115
 116 };
 117 #define td_kse                  td_sched
 118 #define td_slptime              td_kse->ke_slptime
 119 #define ke_proc                 ke_thread->td_proc
 120 #define ke_ksegrp               ke_thread->td_ksegrp
 121 #define ke_assign               ke_procq.tqe_next
 122 /* flags kept in ke_flags */
 123 #define KEF_ASSIGNED    0x0001          /* Thread is being migrated. */
 124 #define KEF_BOUND       0x0002          /* Thread can not migrate. */
 125 #define KEF_XFERABLE    0x0004          /* Thread was added as transferable. */
 126 #define KEF_HOLD        0x0008          /* Thread is temporarily bound. */
 127 #define KEF_REMOVED     0x0010          /* Thread was removed while ASSIGNED */
 128 #define KEF_INTERNAL    0x0020          /* Thread added due to migration. */
 129 #define KEF_PREEMPTED   0x0040          /* Thread was preempted */
 130 #define KEF_DIDRUN      0x02000         /* Thread actually ran. */
 131 #define KEF_EXIT        0x04000         /* Thread is being killed. */
 132
 133 struct kg_sched {
 134         struct thread   *skg_last_assigned; /* (j) Last thread assigned to */
 135                                            /* the system scheduler */
 136         int     skg_slptime;            /* Number of ticks we vol. slept */
 137         int     skg_runtime;            /* Number of ticks we were running */
 138         int     skg_avail_opennings;    /* (j) Num unfilled slots in group.*/
 139         int     skg_concurrency;        /* (j) Num threads requested in group.*/
 140 };
 141 #define kg_last_assigned        kg_sched->skg_last_assigned
 142 #define kg_avail_opennings      kg_sched->skg_avail_opennings
 143 #define kg_concurrency          kg_sched->skg_concurrency
 144 #define kg_runtime              kg_sched->skg_runtime
 145 #define kg_slptime              kg_sched->skg_slptime
 146
 147 #define SLOT_RELEASE(kg)        (kg)->kg_avail_opennings++
 148 #define SLOT_USE(kg)            (kg)->kg_avail_opennings--
 149
 150 static struct kse kse0;
 151 static struct kg_sched kg_sched0;
 152
 153 /*
 154  * The priority is primarily determined by the interactivity score.  Thus, we
 155  * give lower(better) priorities to kse groups that use less CPU.  The nice
 156  * value is then directly added to this to allow nice to have some effect
 157  * on latency.
 158  *
 159  * PRI_RANGE:   Total priority range for timeshare threads.
 160  * PRI_NRESV:   Number of nice values.
 161  * PRI_BASE:    The start of the dynamic range.
 162  */
 163 #define SCHED_PRI_RANGE         (PRI_MAX_TIMESHARE - PRI_MIN_TIMESHARE + 1)
 164 #define SCHED_PRI_NRESV         ((PRIO_MAX - PRIO_MIN) + 1)
 165 #define SCHED_PRI_NHALF         (SCHED_PRI_NRESV / 2)
 166 #define SCHED_PRI_BASE          (PRI_MIN_TIMESHARE)
 167 #define SCHED_PRI_INTERACT(score)                                       \
 168     ((score) * SCHED_PRI_RANGE / SCHED_INTERACT_MAX)
 169
 170 /*
 171  * These determine the interactivity of a process.
 172  *
 173  * SLP_RUN_MAX: Maximum amount of sleep time + run time we'll accumulate
 174  *              before throttling back.
 175  * SLP_RUN_FORK:        Maximum slp+run time to inherit at fork time.
 176  * INTERACT_MAX:        Maximum interactivity value.  Smaller is better.
 177  * INTERACT_THRESH:     Threshhold for placement on the current runq.
 178  */
 179 #define SCHED_SLP_RUN_MAX       ((hz * 5) << 10)
 180 #define SCHED_SLP_RUN_FORK      ((hz / 2) << 10)
 181 #define SCHED_INTERACT_MAX      (100)
 182 #define SCHED_INTERACT_HALF     (SCHED_INTERACT_MAX / 2)
 183 #define SCHED_INTERACT_THRESH   (30)
 184
 185 /*
 186  * These parameters and macros determine the size of the time slice that is
 187  * granted to each thread.
 188  *
 189  * SLICE_MIN:   Minimum time slice granted, in units of ticks.
 190  * SLICE_MAX:   Maximum time slice granted.
 191  * SLICE_RANGE: Range of available time slices scaled by hz.
 192  * SLICE_SCALE: The number slices granted per val in the range of [0, max].
 193  * SLICE_NICE:  Determine the amount of slice granted to a scaled nice.
 194  * SLICE_NTHRESH:       The nice cutoff point for slice assignment.
 195  */
 196 #define SCHED_SLICE_MIN                 (slice_min)
 197 #define SCHED_SLICE_MAX                 (slice_max)
 198 #define SCHED_SLICE_INTERACTIVE         (slice_max)
 199 #define SCHED_SLICE_NTHRESH     (SCHED_PRI_NHALF - 1)
 200 #define SCHED_SLICE_RANGE               (SCHED_SLICE_MAX - SCHED_SLICE_MIN + 1)
 201 #define SCHED_SLICE_SCALE(val, max)     (((val) * SCHED_SLICE_RANGE) / (max))
 202 #define SCHED_SLICE_NICE(nice)                                          \
 203     (SCHED_SLICE_MAX - SCHED_SLICE_SCALE((nice), SCHED_SLICE_NTHRESH))
 204
 205 /*
 206  * This macro determines whether or not the thread belongs on the current or
 207  * next run queue.
 208  */
 209 #define SCHED_INTERACTIVE(kg)                                           \
 210     (sched_interact_score(kg) < SCHED_INTERACT_THRESH)
 211 #define SCHED_CURR(kg, ke)                                              \
 212     ((ke->ke_thread->td_flags & TDF_BORROWING) ||                       \
 213      (ke->ke_flags & KEF_PREEMPTED) || SCHED_INTERACTIVE(kg))
 214
 215 /*
 216  * Cpu percentage computation macros and defines.
 217  *
 218  * SCHED_CPU_TIME:      Number of seconds to average the cpu usage across.
 219  * SCHED_CPU_TICKS:     Number of hz ticks to average the cpu usage across.
 220  */
 221
 222 #define SCHED_CPU_TIME  10
 223 #define SCHED_CPU_TICKS (hz * SCHED_CPU_TIME)
 224
 225 /*
 226  * kseq - per processor runqs and statistics.
 227  */
 228 struct kseq {
 229         struct runq     ksq_idle;               /* Queue of IDLE threads. */
 230         struct runq     ksq_timeshare[2];       /* Run queues for !IDLE. */
 231         struct runq     *ksq_next;              /* Next timeshare queue. */
 232         struct runq     *ksq_curr;              /* Current queue. */
 233         int             ksq_load_timeshare;     /* Load for timeshare. */
 234         int             ksq_load;               /* Aggregate load. */
 235         short           ksq_nice[SCHED_PRI_NRESV]; /* KSEs in each nice bin. */
 236         short           ksq_nicemin;            /* Least nice. */
 237 #ifdef SMP
 238         int                     ksq_transferable;
 239         LIST_ENTRY(kseq)        ksq_siblings;   /* Next in kseq group. */
 240         struct kseq_group       *ksq_group;     /* Our processor group. */
 241         volatile struct kse     *ksq_assigned;  /* assigned by another CPU. */
 242 #else
 243         int             ksq_sysload;            /* For loadavg, !ITHD load. */
 244 #endif
 245 };
 246
 247 #ifdef SMP
 248 /*
 249  * kseq groups are groups of processors which can cheaply share threads.  When
 250  * one processor in the group goes idle it will check the runqs of the other
 251  * processors in its group prior to halting and waiting for an interrupt.
 252  * These groups are suitable for SMT (Symetric Multi-Threading) and not NUMA.
 253  * In a numa environment we'd want an idle bitmap per group and a two tiered
 254  * load balancer.
 255  */
 256 struct kseq_group {
 257         int     ksg_cpus;               /* Count of CPUs in this kseq group. */
 258         cpumask_t ksg_cpumask;          /* Mask of cpus in this group. */
 259         cpumask_t ksg_idlemask;         /* Idle cpus in this group. */
 260         cpumask_t ksg_mask;             /* Bit mask for first cpu. */
 261         int     ksg_load;               /* Total load of this group. */
 262         int     ksg_transferable;       /* Transferable load of this group. */
 263         LIST_HEAD(, kseq)       ksg_members; /* Linked list of all members. */
 264 };
 265 #endif
 266
 267 /*
 268  * One kse queue per processor.
 269  */
 270 #ifdef SMP
 271 static cpumask_t kseq_idle;
 272 static int ksg_maxid;
 273 static struct kseq      kseq_cpu[MAXCPU];
 274 static struct kseq_group kseq_groups[MAXCPU];
 275 static int bal_tick;
 276 static int gbal_tick;
 277 static int balance_groups;
 278
 279 #define KSEQ_SELF()     (&kseq_cpu[PCPU_GET(cpuid)])
 280 #define KSEQ_CPU(x)     (&kseq_cpu[(x)])
 281 #define KSEQ_ID(x)      ((x) - kseq_cpu)
 282 #define KSEQ_GROUP(x)   (&kseq_groups[(x)])
 283 #else   /* !SMP */
 284 static struct kseq      kseq_cpu;
 285
 286 #define KSEQ_SELF()     (&kseq_cpu)
 287 #define KSEQ_CPU(x)     (&kseq_cpu)
 288 #endif
 289
 290 static void slot_fill(struct ksegrp *);
 291 static struct kse *sched_choose(void);          /* XXX Should be thread * */
 292 static void sched_slice(struct kse *);
 293 static void sched_priority(struct ksegrp *);
 294 static void sched_thread_priority(struct thread *, u_char);
 295 static int sched_interact_score(struct ksegrp *);
 296 static void sched_interact_update(struct ksegrp *);
 297 static void sched_interact_fork(struct ksegrp *);
 298 static void sched_pctcpu_update(struct kse *);
 299
 300 /* Operations on per processor queues */
 301 static struct kse * kseq_choose(struct kseq *);
 302 static void kseq_setup(struct kseq *);
 303 static void kseq_load_add(struct kseq *, struct kse *);
 304 static void kseq_load_rem(struct kseq *, struct kse *);
 305 static __inline void kseq_runq_add(struct kseq *, struct kse *, int);
 306 static __inline void kseq_runq_rem(struct kseq *, struct kse *);
 307 static void kseq_nice_add(struct kseq *, int);
 308 static void kseq_nice_rem(struct kseq *, int);
 309 void kseq_print(int cpu);
 310 #ifdef SMP
 311 static int kseq_transfer(struct kseq *, struct kse *, int);
 312 static struct kse *runq_steal(struct runq *);
 313 static void sched_balance(void);
 314 static void sched_balance_groups(void);
 315 static void sched_balance_group(struct kseq_group *);
 316 static void sched_balance_pair(struct kseq *, struct kseq *);
 317 static void kseq_move(struct kseq *, int);
 318 static int kseq_idled(struct kseq *);
 319 static void kseq_notify(struct kse *, int);
 320 static void kseq_assign(struct kseq *);
 321 static struct kse *kseq_steal(struct kseq *, int);
 322 #define KSE_CAN_MIGRATE(ke)                                             \
 323     ((ke)->ke_thread->td_pinned == 0 && ((ke)->ke_flags & KEF_BOUND) == 0)
 324 #endif
 325
 326 void
 327 kseq_print(int cpu)
 328 {
 329         struct kseq *kseq;
 330         int i;
 331
 332         kseq = KSEQ_CPU(cpu);
 333
 334         printf("kseq:\n");
 335         printf("\tload:           %d\n", kseq->ksq_load);
 336         printf("\tload TIMESHARE: %d\n", kseq->ksq_load_timeshare);
 337 #ifdef SMP
 338         printf("\tload transferable: %d\n", kseq->ksq_transferable);
 339 #endif
 340         printf("\tnicemin:\t%d\n", kseq->ksq_nicemin);
 341         printf("\tnice counts:\n");
 342         for (i = 0; i < SCHED_PRI_NRESV; i++)
 343                 if (kseq->ksq_nice[i])
 344                         printf("\t\t%d = %d\n",
 345                             i - SCHED_PRI_NHALF, kseq->ksq_nice[i]);
 346 }
 347
 348 static __inline void
 349 kseq_runq_add(struct kseq *kseq, struct kse *ke, int flags)
 350 {
 351 #ifdef SMP
 352         if (KSE_CAN_MIGRATE(ke)) {
 353                 kseq->ksq_transferable++;
 354                 kseq->ksq_group->ksg_transferable++;
 355                 ke->ke_flags |= KEF_XFERABLE;
 356         }
 357 #endif
 358         if (ke->ke_flags & KEF_PREEMPTED)
 359                 flags |= SRQ_PREEMPTED;
 360         runq_add(ke->ke_runq, ke, flags);
 361 }
 362
 363 static __inline void
 364 kseq_runq_rem(struct kseq *kseq, struct kse *ke)
 365 {
 366 #ifdef SMP
 367         if (ke->ke_flags & KEF_XFERABLE) {
 368                 kseq->ksq_transferable--;
 369                 kseq->ksq_group->ksg_transferable--;
 370                 ke->ke_flags &= ~KEF_XFERABLE;
 371         }
 372 #endif
 373         runq_remove(ke->ke_runq, ke);
 374 }
 375
 376 static void
 377 kseq_load_add(struct kseq *kseq, struct kse *ke)
 378 {
 379         int class;
 380         mtx_assert(&sched_lock, MA_OWNED);
 381         class = PRI_BASE(ke->ke_ksegrp->kg_pri_class);
 382         if (class == PRI_TIMESHARE)
 383                 kseq->ksq_load_timeshare++;
 384         kseq->ksq_load++;
 385         CTR1(KTR_SCHED, "load: %d", kseq->ksq_load);
 386         if (class != PRI_ITHD && (ke->ke_proc->p_flag & P_NOLOAD) == 0)
 387 #ifdef SMP
 388                 kseq->ksq_group->ksg_load++;
 389 #else
 390                 kseq->ksq_sysload++;
 391 #endif
 392         if (ke->ke_ksegrp->kg_pri_class == PRI_TIMESHARE)
 393                 kseq_nice_add(kseq, ke->ke_proc->p_nice);
 394 }
 395
 396 static void
 397 kseq_load_rem(struct kseq *kseq, struct kse *ke)
 398 {
 399         int class;
 400         mtx_assert(&sched_lock, MA_OWNED);
 401         class = PRI_BASE(ke->ke_ksegrp->kg_pri_class);
 402         if (class == PRI_TIMESHARE)
 403                 kseq->ksq_load_timeshare--;
 404         if (class != PRI_ITHD  && (ke->ke_proc->p_flag & P_NOLOAD) == 0)
 405 #ifdef SMP
 406                 kseq->ksq_group->ksg_load--;
 407 #else
 408                 kseq->ksq_sysload--;
 409 #endif
 410         kseq->ksq_load--;
 411         CTR1(KTR_SCHED, "load: %d", kseq->ksq_load);
 412         ke->ke_runq = NULL;
 413         if (ke->ke_ksegrp->kg_pri_class == PRI_TIMESHARE)
 414                 kseq_nice_rem(kseq, ke->ke_proc->p_nice);
 415 }
 416
 417 static void
 418 kseq_nice_add(struct kseq *kseq, int nice)
 419 {
 420         mtx_assert(&sched_lock, MA_OWNED);
 421         /* Normalize to zero. */
 422         kseq->ksq_nice[nice + SCHED_PRI_NHALF]++;
 423         if (nice < kseq->ksq_nicemin || kseq->ksq_load_timeshare == 1)
 424                 kseq->ksq_nicemin = nice;
 425 }
 426
 427 static void
 428 kseq_nice_rem(struct kseq *kseq, int nice)
 429 {
 430         int n;
 431
 432         mtx_assert(&sched_lock, MA_OWNED);
 433         /* Normalize to zero. */
 434         n = nice + SCHED_PRI_NHALF;
 435         kseq->ksq_nice[n]--;
 436         KASSERT(kseq->ksq_nice[n] >= 0, ("Negative nice count."));
 437
 438         /*
 439          * If this wasn't the smallest nice value or there are more in
 440          * this bucket we can just return.  Otherwise we have to recalculate
 441          * the smallest nice.
 442          */
 443         if (nice != kseq->ksq_nicemin ||
 444             kseq->ksq_nice[n] != 0 ||
 445             kseq->ksq_load_timeshare == 0)
 446                 return;
 447
 448         for (; n < SCHED_PRI_NRESV; n++)
 449                 if (kseq->ksq_nice[n]) {
 450                         kseq->ksq_nicemin = n - SCHED_PRI_NHALF;
 451                         return;
 452                 }
 453 }
 454
 455 #ifdef SMP
 456 /*
 457  * sched_balance is a simple CPU load balancing algorithm.  It operates by
 458  * finding the least loaded and most loaded cpu and equalizing their load
 459  * by migrating some processes.
 460  *
 461  * Dealing only with two CPUs at a time has two advantages.  Firstly, most
 462  * installations will only have 2 cpus.  Secondly, load balancing too much at
 463  * once can have an unpleasant effect on the system.  The scheduler rarely has
 464  * enough information to make perfect decisions.  So this algorithm chooses
 465  * algorithm simplicity and more gradual effects on load in larger systems.
 466  *
 467  * It could be improved by considering the priorities and slices assigned to
 468  * each task prior to balancing them.  There are many pathological cases with
 469  * any approach and so the semi random algorithm below may work as well as any.
 470  *
 471  */
 472 static void
 473 sched_balance(void)
 474 {
 475         struct kseq_group *high;
 476         struct kseq_group *low;
 477         struct kseq_group *ksg;
 478         int cnt;
 479         int i;
 480
 481         bal_tick = ticks + (random() % (hz * 2));
 482         if (smp_started == 0)
 483                 return;
 484         low = high = NULL;
 485         i = random() % (ksg_maxid + 1);
 486         for (cnt = 0; cnt <= ksg_maxid; cnt++) {
 487                 ksg = KSEQ_GROUP(i);
 488                 /*
 489                  * Find the CPU with the highest load that has some
 490                  * threads to transfer.
 491                  */
 492                 if ((high == NULL || ksg->ksg_load > high->ksg_load)
 493                     && ksg->ksg_transferable)
 494                         high = ksg;
 495                 if (low == NULL || ksg->ksg_load < low->ksg_load)
 496                         low = ksg;
 497                 if (++i > ksg_maxid)
 498                         i = 0;
 499         }
 500         if (low != NULL && high != NULL && high != low)
 501                 sched_balance_pair(LIST_FIRST(&high->ksg_members),
 502                     LIST_FIRST(&low->ksg_members));
 503 }
 504
 505 static void
 506 sched_balance_groups(void)
 507 {
 508         int i;
 509
 510         gbal_tick = ticks + (random() % (hz * 2));
 511         mtx_assert(&sched_lock, MA_OWNED);
 512         if (smp_started)
 513                 for (i = 0; i <= ksg_maxid; i++)
 514                         sched_balance_group(KSEQ_GROUP(i));
 515 }
 516
 517 static void
 518 sched_balance_group(struct kseq_group *ksg)
 519 {
 520         struct kseq *kseq;
 521         struct kseq *high;
 522         struct kseq *low;
 523         int load;
 524
 525         if (ksg->ksg_transferable == 0)
 526                 return;
 527         low = NULL;
 528         high = NULL;
 529         LIST_FOREACH(kseq, &ksg->ksg_members, ksq_siblings) {
 530                 load = kseq->ksq_load;
 531                 if (high == NULL || load > high->ksq_load)
 532                         high = kseq;
 533                 if (low == NULL || load < low->ksq_load)
 534                         low = kseq;
 535         }
 536         if (high != NULL && low != NULL && high != low)
 537                 sched_balance_pair(high, low);
 538 }
 539
 540 static void
 541 sched_balance_pair(struct kseq *high, struct kseq *low)
 542 {
 543         int transferable;
 544         int high_load;
 545         int low_load;
 546         int move;
 547         int diff;
 548         int i;
 549
 550         /*
 551          * If we're transfering within a group we have to use this specific
 552          * kseq's transferable count, otherwise we can steal from other members
 553          * of the group.
 554          */
 555         if (high->ksq_group == low->ksq_group) {
 556                 transferable = high->ksq_transferable;
 557                 high_load = high->ksq_load;
 558                 low_load = low->ksq_load;
 559         } else {
 560                 transferable = high->ksq_group->ksg_transferable;
 561                 high_load = high->ksq_group->ksg_load;
 562                 low_load = low->ksq_group->ksg_load;
 563         }
 564         if (transferable == 0)
 565                 return;
 566         /*
 567          * Determine what the imbalance is and then adjust that to how many
 568          * kses we actually have to give up (transferable).
 569          */
 570         diff = high_load - low_load;
 571         move = diff / 2;
 572         if (diff & 0x1)
 573                 move++;
 574         move = min(move, transferable);
 575         for (i = 0; i < move; i++)
 576                 kseq_move(high, KSEQ_ID(low));
 577         return;
 578 }
 579
 580 static void
 581 kseq_move(struct kseq *from, int cpu)
 582 {
 583         struct kseq *kseq;
 584         struct kseq *to;
 585         struct kse *ke;
 586
 587         kseq = from;
 588         to = KSEQ_CPU(cpu);
 589         ke = kseq_steal(kseq, 1);
 590         if (ke == NULL) {
 591                 struct kseq_group *ksg;
 592
 593                 ksg = kseq->ksq_group;
 594                 LIST_FOREACH(kseq, &ksg->ksg_members, ksq_siblings) {
 595                         if (kseq == from || kseq->ksq_transferable == 0)
 596                                 continue;
 597                         ke = kseq_steal(kseq, 1);
 598                         break;
 599                 }
 600                 if (ke == NULL)
 601                         panic("kseq_move: No KSEs available with a "
 602                             "transferable count of %d\n",
 603                             ksg->ksg_transferable);
 604         }
 605         if (kseq == to)
 606                 return;
 607         ke->ke_state = KES_THREAD;
 608         kseq_runq_rem(kseq, ke);
 609         kseq_load_rem(kseq, ke);
 610         kseq_notify(ke, cpu);
 611 }
 612
 613 static int
 614 kseq_idled(struct kseq *kseq)
 615 {
 616         struct kseq_group *ksg;
 617         struct kseq *steal;
 618         struct kse *ke;
 619
 620         ksg = kseq->ksq_group;
 621         /*
 622          * If we're in a cpu group, try and steal kses from another cpu in
 623          * the group before idling.
 624          */
 625         if (ksg->ksg_cpus > 1 && ksg->ksg_transferable) {
 626                 LIST_FOREACH(steal, &ksg->ksg_members, ksq_siblings) {
 627                         if (steal == kseq || steal->ksq_transferable == 0)
 628                                 continue;
 629                         ke = kseq_steal(steal, 0);
 630                         if (ke == NULL)
 631                                 continue;
 632                         ke->ke_state = KES_THREAD;
 633                         kseq_runq_rem(steal, ke);
 634                         kseq_load_rem(steal, ke);
 635                         ke->ke_cpu = PCPU_GET(cpuid);
 636                         ke->ke_flags |= KEF_INTERNAL | KEF_HOLD;
 637                         sched_add(ke->ke_thread, SRQ_YIELDING);
 638                         return (0);
 639                 }
 640         }
 641         /*
 642          * We only set the idled bit when all of the cpus in the group are
 643          * idle.  Otherwise we could get into a situation where a KSE bounces
 644          * back and forth between two idle cores on seperate physical CPUs.
 645          */
 646         ksg->ksg_idlemask |= PCPU_GET(cpumask);
 647         if (ksg->ksg_idlemask != ksg->ksg_cpumask)
 648                 return (1);
 649         atomic_set_int(&kseq_idle, ksg->ksg_mask);
 650         return (1);
 651 }
 652
 653 static void
 654 kseq_assign(struct kseq *kseq)
 655 {
 656         struct kse *nke;
 657         struct kse *ke;
 658
 659         do {
 660                 *(volatile struct kse **)&ke = kseq->ksq_assigned;
 661         } while(!atomic_cmpset_ptr((volatile uintptr_t *)&kseq->ksq_assigned,
 662                 (uintptr_t)ke, (uintptr_t)NULL));
 663         for (; ke != NULL; ke = nke) {
 664                 nke = ke->ke_assign;
 665                 kseq->ksq_group->ksg_load--;
 666                 kseq->ksq_load--;
 667                 ke->ke_flags &= ~KEF_ASSIGNED;
 668                 if (ke->ke_flags & KEF_REMOVED) {
 669                         ke->ke_flags &= ~KEF_REMOVED;
 670                         continue;
 671                 }
 672                 ke->ke_flags |= KEF_INTERNAL | KEF_HOLD;
 673                 sched_add(ke->ke_thread, SRQ_YIELDING);
 674         }
 675 }
 676
 677 static void
 678 kseq_notify(struct kse *ke, int cpu)
 679 {
 680         struct kseq *kseq;
 681         struct thread *td;
 682         struct pcpu *pcpu;
 683         int class;
 684         int prio;
 685
 686         kseq = KSEQ_CPU(cpu);
 687         /* XXX */
 688         class = PRI_BASE(ke->ke_ksegrp->kg_pri_class);
 689         if ((class == PRI_TIMESHARE || class == PRI_REALTIME) &&
 690             (kseq_idle & kseq->ksq_group->ksg_mask))
 691                 atomic_clear_int(&kseq_idle, kseq->ksq_group->ksg_mask);
 692         kseq->ksq_group->ksg_load++;
 693         kseq->ksq_load++;
 694         ke->ke_cpu = cpu;
 695         ke->ke_flags |= KEF_ASSIGNED;
 696         prio = ke->ke_thread->td_priority;
 697
 698         /*
 699          * Place a KSE on another cpu's queue and force a resched.
 700          */
 701         do {
 702                 *(volatile struct kse **)&ke->ke_assign = kseq->ksq_assigned;
 703         } while(!atomic_cmpset_ptr((volatile uintptr_t *)&kseq->ksq_assigned,
 704                 (uintptr_t)ke->ke_assign, (uintptr_t)ke));
 705         /*
 706          * Without sched_lock we could lose a race where we set NEEDRESCHED
 707          * on a thread that is switched out before the IPI is delivered.  This
 708          * would lead us to miss the resched.  This will be a problem once
 709          * sched_lock is pushed down.
 710          */
 711         pcpu = pcpu_find(cpu);
 712         td = pcpu->pc_curthread;
 713         if (ke->ke_thread->td_priority < td->td_priority ||
 714             td == pcpu->pc_idlethread) {
 715                 td->td_flags |= TDF_NEEDRESCHED;
 716                 ipi_selected(1 << cpu, IPI_AST);
 717         }
 718 }
 719
 720 static struct kse *
 721 runq_steal(struct runq *rq)
 722 {
 723         struct rqhead *rqh;
 724         struct rqbits *rqb;
 725         struct kse *ke;
 726         int word;
 727         int bit;
 728
 729         mtx_assert(&sched_lock, MA_OWNED);
 730         rqb = &rq->rq_status;
 731         for (word = 0; word < RQB_LEN; word++) {
 732                 if (rqb->rqb_bits[word] == 0)
 733                         continue;
 734                 for (bit = 0; bit < RQB_BPW; bit++) {
 735                         if ((rqb->rqb_bits[word] & (1ul << bit)) == 0)
 736                                 continue;
 737                         rqh = &rq->rq_queues[bit + (word << RQB_L2BPW)];
 738                         TAILQ_FOREACH(ke, rqh, ke_procq) {
 739                                 if (KSE_CAN_MIGRATE(ke))
 740                                         return (ke);
 741                         }
 742                 }
 743         }
 744         return (NULL);
 745 }
 746
 747 static struct kse *
 748 kseq_steal(struct kseq *kseq, int stealidle)
 749 {
 750         struct kse *ke;
 751
 752         /*
 753          * Steal from next first to try to get a non-interactive task that
 754          * may not have run for a while.
 755          */
 756         if ((ke = runq_steal(kseq->ksq_next)) != NULL)
 757                 return (ke);
 758         if ((ke = runq_steal(kseq->ksq_curr)) != NULL)
 759                 return (ke);
 760         if (stealidle)
 761                 return (runq_steal(&kseq->ksq_idle));
 762         return (NULL);
 763 }
 764
 765 int
 766 kseq_transfer(struct kseq *kseq, struct kse *ke, int class)
 767 {
 768         struct kseq_group *nksg;
 769         struct kseq_group *ksg;
 770         struct kseq *old;
 771         int cpu;
 772         int idx;
 773
 774         if (smp_started == 0)
 775                 return (0);
 776         cpu = 0;
 777         /*
 778          * If our load exceeds a certain threshold we should attempt to
 779          * reassign this thread.  The first candidate is the cpu that
 780          * originally ran the thread.  If it is idle, assign it there,
 781          * otherwise, pick an idle cpu.
 782          *
 783          * The threshold at which we start to reassign kses has a large impact
 784          * on the overall performance of the system.  Tuned too high and
 785          * some CPUs may idle.  Too low and there will be excess migration
 786          * and context switches.
 787          */
 788         old = KSEQ_CPU(ke->ke_cpu);
 789         nksg = old->ksq_group;
 790         ksg = kseq->ksq_group;
 791         if (kseq_idle) {
 792                 if (kseq_idle & nksg->ksg_mask) {
 793                         cpu = ffs(nksg->ksg_idlemask);
 794                         if (cpu) {
 795                                 CTR2(KTR_SCHED,
 796                                     "kseq_transfer: %p found old cpu %X "
 797                                     "in idlemask.", ke, cpu);
 798                                 goto migrate;
 799                         }
 800                 }
 801                 /*
 802                  * Multiple cpus could find this bit simultaneously
 803                  * but the race shouldn't be terrible.
 804                  */
 805                 cpu = ffs(kseq_idle);
 806                 if (cpu) {
 807                         CTR2(KTR_SCHED, "kseq_transfer: %p found %X "
 808                             "in idlemask.", ke, cpu);
 809                         goto migrate;
 810                 }
 811         }
 812         idx = 0;
 813 #if 0
 814         if (old->ksq_load < kseq->ksq_load) {
 815                 cpu = ke->ke_cpu + 1;
 816                 CTR2(KTR_SCHED, "kseq_transfer: %p old cpu %X "
 817                     "load less than ours.", ke, cpu);
 818                 goto migrate;
 819         }
 820         /*
 821          * No new CPU was found, look for one with less load.
 822          */
 823         for (idx = 0; idx <= ksg_maxid; idx++) {
 824                 nksg = KSEQ_GROUP(idx);
 825                 if (nksg->ksg_load /*+ (nksg->ksg_cpus  * 2)*/ < ksg->ksg_load) {
 826                         cpu = ffs(nksg->ksg_cpumask);
 827                         CTR2(KTR_SCHED, "kseq_transfer: %p cpu %X load less "
 828                             "than ours.", ke, cpu);
 829                         goto migrate;
 830                 }
 831         }
 832 #endif
 833         /*
 834          * If another cpu in this group has idled, assign a thread over
 835          * to them after checking to see if there are idled groups.
 836          */
 837         if (ksg->ksg_idlemask) {
 838                 cpu = ffs(ksg->ksg_idlemask);
 839                 if (cpu) {
 840                         CTR2(KTR_SCHED, "kseq_transfer: %p cpu %X idle in "
 841                             "group.", ke, cpu);
 842                         goto migrate;
 843                 }
 844         }
 845         return (0);
 846 migrate:
 847         /*
 848          * Now that we've found an idle CPU, migrate the thread.
 849          */
 850         cpu--;
 851         ke->ke_runq = NULL;
 852         kseq_notify(ke, cpu);
 853
 854         return (1);
 855 }
 856
 857 #endif  /* SMP */
 858
 859 /*
 860  * Pick the highest priority task we have and return it.
 861  */
 862
 863 static struct kse *
 864 kseq_choose(struct kseq *kseq)
 865 {
 866         struct runq *swap;
 867         struct kse *ke;
 868         int nice;
 869
 870         mtx_assert(&sched_lock, MA_OWNED);
 871         swap = NULL;
 872
 873         for (;;) {
 874                 ke = runq_choose(kseq->ksq_curr);
 875                 if (ke == NULL) {
 876                         /*
 877                          * We already swapped once and didn't get anywhere.
 878                          */
 879                         if (swap)
 880                                 break;
 881                         swap = kseq->ksq_curr;
 882                         kseq->ksq_curr = kseq->ksq_next;
 883                         kseq->ksq_next = swap;
 884                         continue;
 885                 }
 886                 /*
 887                  * If we encounter a slice of 0 the kse is in a
 888                  * TIMESHARE kse group and its nice was too far out
 889                  * of the range that receives slices.
 890                  */
 891                 nice = ke->ke_proc->p_nice + (0 - kseq->ksq_nicemin);
 892 #if 0
 893                 if (ke->ke_slice == 0 || (nice > SCHED_SLICE_NTHRESH &&
 894                     ke->ke_proc->p_nice != 0)) {
 895                         runq_remove(ke->ke_runq, ke);
 896                         sched_slice(ke);
 897                         ke->ke_runq = kseq->ksq_next;
 898                         runq_add(ke->ke_runq, ke, 0);
 899                         continue;
 900                 }
 901 #endif
 902                 return (ke);
 903         }
 904
 905         return (runq_choose(&kseq->ksq_idle));
 906 }
 907
 908 static void
 909 kseq_setup(struct kseq *kseq)
 910 {
 911         runq_init(&kseq->ksq_timeshare[0]);
 912         runq_init(&kseq->ksq_timeshare[1]);
 913         runq_init(&kseq->ksq_idle);
 914         kseq->ksq_curr = &kseq->ksq_timeshare[0];
 915         kseq->ksq_next = &kseq->ksq_timeshare[1];
 916         kseq->ksq_load = 0;
 917         kseq->ksq_load_timeshare = 0;
 918 }
 919
 920 static void
 921 sched_setup(void *dummy)
 922 {
 923 #ifdef SMP
 924         int i;
 925 #endif
 926
 927         /*
 928          * To avoid divide-by-zero, we set realstathz a dummy value
 929          * in case which sched_clock() called before sched_initticks().
 930          */
 931         realstathz = hz;
 932         slice_min = (hz/100);   /* 10ms */
 933         slice_max = (hz/7);     /* ~140ms */
 934
 935 #ifdef SMP
 936         balance_groups = 0;
 937         /*
 938          * Initialize the kseqs.
 939          */
 940         for (i = 0; i < MAXCPU; i++) {
 941                 struct kseq *ksq;
 942
 943                 ksq = &kseq_cpu[i];
 944                 ksq->ksq_assigned = NULL;
 945                 kseq_setup(&kseq_cpu[i]);
 946         }
 947         if (smp_topology == NULL) {
 948                 struct kseq_group *ksg;
 949                 struct kseq *ksq;
 950                 int cpus;
 951
 952                 for (cpus = 0, i = 0; i < MAXCPU; i++) {
 953                         if (CPU_ABSENT(i))
 954                                 continue;
 955                         ksq = &kseq_cpu[i];
 956                         ksg = &kseq_groups[cpus];
 957                         /*
 958                          * Setup a kseq group with one member.
 959                          */
 960                         ksq->ksq_transferable = 0;
 961                         ksq->ksq_group = ksg;
 962                         ksg->ksg_cpus = 1;
 963                         ksg->ksg_idlemask = 0;
 964                         ksg->ksg_cpumask = ksg->ksg_mask = 1 << i;
 965                         ksg->ksg_load = 0;
 966                         ksg->ksg_transferable = 0;
 967                         LIST_INIT(&ksg->ksg_members);
 968                         LIST_INSERT_HEAD(&ksg->ksg_members, ksq, ksq_siblings);
 969                         cpus++;
 970                 }
 971                 ksg_maxid = cpus - 1;
 972         } else {
 973                 struct kseq_group *ksg;
 974                 struct cpu_group *cg;
 975                 int j;
 976
 977                 for (i = 0; i < smp_topology->ct_count; i++) {
 978                         cg = &smp_topology->ct_group[i];
 979                         ksg = &kseq_groups[i];
 980                         /*
 981                          * Initialize the group.
 982                          */
 983                         ksg->ksg_idlemask = 0;
 984                         ksg->ksg_load = 0;
 985                         ksg->ksg_transferable = 0;
 986                         ksg->ksg_cpus = cg->cg_count;
 987                         ksg->ksg_cpumask = cg->cg_mask;
 988                         LIST_INIT(&ksg->ksg_members);
 989                         /*
 990                          * Find all of the group members and add them.
 991                          */
 992                         for (j = 0; j < MAXCPU; j++) {
 993                                 if ((cg->cg_mask & (1 << j)) != 0) {
 994                                         if (ksg->ksg_mask == 0)
 995                                                 ksg->ksg_mask = 1 << j;
 996                                         kseq_cpu[j].ksq_transferable = 0;
 997                                         kseq_cpu[j].ksq_group = ksg;
 998                                         LIST_INSERT_HEAD(&ksg->ksg_members,
 999                                             &kseq_cpu[j], ksq_siblings);
1000                                 }
1001                         }
1002                         if (ksg->ksg_cpus > 1)
1003                                 balance_groups = 1;
1004                 }
1005                 ksg_maxid = smp_topology->ct_count - 1;
1006         }
1007         /*
1008          * Stagger the group and global load balancer so they do not
1009          * interfere with each other.
1010          */
1011         bal_tick = ticks + hz;
1012         if (balance_groups)
1013                 gbal_tick = ticks + (hz / 2);
1014 #else
1015         kseq_setup(KSEQ_SELF());
1016 #endif
1017         mtx_lock_spin(&sched_lock);
1018         kseq_load_add(KSEQ_SELF(), &kse0);
1019         mtx_unlock_spin(&sched_lock);
1020 }
1021
1022 /* ARGSUSED */
1023 static void
1024 sched_initticks(void *dummy)
1025 {
1026         mtx_lock_spin(&sched_lock);
1027         realstathz = stathz ? stathz : hz;
1028         slice_min = (realstathz/100);   /* 10ms */
1029         slice_max = (realstathz/7);     /* ~140ms */
1030
1031         tickincr = (hz << 10) / realstathz;
1032         /*
1033          * XXX This does not work for values of stathz that are much
1034          * larger than hz.
1035          */
1036         if (tickincr == 0)
1037                 tickincr = 1;
1038         mtx_unlock_spin(&sched_lock);
1039 }
1040
1041
1042 /*
1043  * Scale the scheduling priority according to the "interactivity" of this
1044  * process.
1045  */
1046 static void
1047 sched_priority(struct ksegrp *kg)
1048 {
1049         int pri;
1050
1051         if (kg->kg_pri_class != PRI_TIMESHARE)
1052                 return;
1053
1054         pri = SCHED_PRI_INTERACT(sched_interact_score(kg));
1055         pri += SCHED_PRI_BASE;
1056         pri += kg->kg_proc->p_nice;
1057
1058         if (pri > PRI_MAX_TIMESHARE)
1059                 pri = PRI_MAX_TIMESHARE;
1060         else if (pri < PRI_MIN_TIMESHARE)
1061                 pri = PRI_MIN_TIMESHARE;
1062
1063         kg->kg_user_pri = pri;
1064
1065         return;
1066 }
1067
1068 /*
1069  * Calculate a time slice based on the properties of the kseg and the runq
1070  * that we're on.  This is only for PRI_TIMESHARE ksegrps.
1071  */
1072 static void
1073 sched_slice(struct kse *ke)
1074 {
1075         struct kseq *kseq;
1076         struct ksegrp *kg;
1077
1078         kg = ke->ke_ksegrp;
1079         kseq = KSEQ_CPU(ke->ke_cpu);
1080
1081         if (ke->ke_thread->td_flags & TDF_BORROWING) {
1082                 ke->ke_slice = SCHED_SLICE_MIN;
1083                 return;
1084         }
1085
1086         /*
1087          * Rationale:
1088          * KSEs in interactive ksegs get a minimal slice so that we
1089          * quickly notice if it abuses its advantage.
1090          *
1091          * KSEs in non-interactive ksegs are assigned a slice that is
1092          * based on the ksegs nice value relative to the least nice kseg
1093          * on the run queue for this cpu.
1094          *
1095          * If the KSE is less nice than all others it gets the maximum
1096          * slice and other KSEs will adjust their slice relative to
1097          * this when they first expire.
1098          *
1099          * There is 20 point window that starts relative to the least
1100          * nice kse on the run queue.  Slice size is determined by
1101          * the kse distance from the last nice ksegrp.
1102          *
1103          * If the kse is outside of the window it will get no slice
1104          * and will be reevaluated each time it is selected on the
1105          * run queue.  The exception to this is nice 0 ksegs when
1106          * a nice -20 is running.  They are always granted a minimum
1107          * slice.
1108          */
1109         if (!SCHED_INTERACTIVE(kg)) {
1110                 int nice;
1111
1112                 nice = kg->kg_proc->p_nice + (0 - kseq->ksq_nicemin);
1113                 if (kseq->ksq_load_timeshare == 0 ||
1114                     kg->kg_proc->p_nice < kseq->ksq_nicemin)
1115                         ke->ke_slice = SCHED_SLICE_MAX;
1116                 else if (nice <= SCHED_SLICE_NTHRESH)
1117                         ke->ke_slice = SCHED_SLICE_NICE(nice);
1118                 else if (kg->kg_proc->p_nice == 0)
1119                         ke->ke_slice = SCHED_SLICE_MIN;
1120                 else
1121                         ke->ke_slice = SCHED_SLICE_MIN; /* 0 */
1122         } else
1123                 ke->ke_slice = SCHED_SLICE_INTERACTIVE;
1124
1125         return;
1126 }
1127
1128 /*
1129  * This routine enforces a maximum limit on the amount of scheduling history
1130  * kept.  It is called after either the slptime or runtime is adjusted.
1131  * This routine will not operate correctly when slp or run times have been
1132  * adjusted to more than double their maximum.
1133  */
1134 static void
1135 sched_interact_update(struct ksegrp *kg)
1136 {
1137         int sum;
1138
1139         sum = kg->kg_runtime + kg->kg_slptime;
1140         if (sum < SCHED_SLP_RUN_MAX)
1141                 return;
1142         /*
1143          * If we have exceeded by more than 1/5th then the algorithm below
1144          * will not bring us back into range.  Dividing by two here forces
1145          * us into the range of [4/5 * SCHED_INTERACT_MAX, SCHED_INTERACT_MAX]
1146          */
1147         if (sum > (SCHED_SLP_RUN_MAX / 5) * 6) {
1148                 kg->kg_runtime /= 2;
1149                 kg->kg_slptime /= 2;
1150                 return;
1151         }
1152         kg->kg_runtime = (kg->kg_runtime / 5) * 4;
1153         kg->kg_slptime = (kg->kg_slptime / 5) * 4;
1154 }
1155
1156 static void
1157 sched_interact_fork(struct ksegrp *kg)
1158 {
1159         int ratio;
1160         int sum;
1161
1162         sum = kg->kg_runtime + kg->kg_slptime;
1163         if (sum > SCHED_SLP_RUN_FORK) {
1164                 ratio = sum / SCHED_SLP_RUN_FORK;
1165                 kg->kg_runtime /= ratio;
1166                 kg->kg_slptime /= ratio;
1167         }
1168 }
1169
1170 static int
1171 sched_interact_score(struct ksegrp *kg)
1172 {
1173         int div;
1174
1175         if (kg->kg_runtime > kg->kg_slptime) {
1176                 div = max(1, kg->kg_runtime / SCHED_INTERACT_HALF);
1177                 return (SCHED_INTERACT_HALF +
1178                     (SCHED_INTERACT_HALF - (kg->kg_slptime / div)));
1179         } if (kg->kg_slptime > kg->kg_runtime) {
1180                 div = max(1, kg->kg_slptime / SCHED_INTERACT_HALF);
1181                 return (kg->kg_runtime / div);
1182         }
1183
1184         /*
1185          * This can happen if slptime and runtime are 0.
1186          */
1187         return (0);
1188
1189 }
1190
1191 /*
1192  * Very early in the boot some setup of scheduler-specific
1193  * parts of proc0 and of soem scheduler resources needs to be done.
1194  * Called from:
1195  *  proc0_init()
1196  */
1197 void
1198 schedinit(void)
1199 {
1200         /*
1201          * Set up the scheduler specific parts of proc0.
1202          */
1203         proc0.p_sched = NULL; /* XXX */
1204         ksegrp0.kg_sched = &kg_sched0;
1205         thread0.td_sched = &kse0;
1206         kse0.ke_thread = &thread0;
1207         kse0.ke_state = KES_THREAD;
1208         kg_sched0.skg_concurrency = 1;
1209         kg_sched0.skg_avail_opennings = 0; /* we are already running */
1210 }
1211
1212 /*
1213  * This is only somewhat accurate since given many processes of the same
1214  * priority they will switch when their slices run out, which will be
1215  * at most SCHED_SLICE_MAX.
1216  */
1217 int
1218 sched_rr_interval(void)
1219 {
1220         return (SCHED_SLICE_MAX);
1221 }
1222
1223 static void
1224 sched_pctcpu_update(struct kse *ke)
1225 {
1226         /*
1227          * Adjust counters and watermark for pctcpu calc.
1228          */
1229         if (ke->ke_ltick > ticks - SCHED_CPU_TICKS) {
1230                 /*
1231                  * Shift the tick count out so that the divide doesn't
1232                  * round away our results.
1233                  */
1234                 ke->ke_ticks <<= 10;
1235                 ke->ke_ticks = (ke->ke_ticks / (ticks - ke->ke_ftick)) *
1236                             SCHED_CPU_TICKS;
1237                 ke->ke_ticks >>= 10;
1238         } else
1239                 ke->ke_ticks = 0;
1240         ke->ke_ltick = ticks;
1241         ke->ke_ftick = ke->ke_ltick - SCHED_CPU_TICKS;
1242 }
1243
1244 void
1245 sched_thread_priority(struct thread *td, u_char prio)
1246 {
1247         struct kse *ke;
1248
1249         CTR6(KTR_SCHED, "sched_prio: %p(%s) prio %d newprio %d by %p(%s)",
1250             td, td->td_proc->p_comm, td->td_priority, prio, curthread,
1251             curthread->td_proc->p_comm);
1252         ke = td->td_kse;
1253         mtx_assert(&sched_lock, MA_OWNED);
1254         if (td->td_priority == prio)
1255                 return;
1256         if (TD_ON_RUNQ(td)) {
1257                 /*
1258                  * If the priority has been elevated due to priority
1259                  * propagation, we may have to move ourselves to a new
1260                  * queue.  We still call adjustrunqueue below in case kse
1261                  * needs to fix things up.
1262                  */
1263                 if (prio < td->td_priority && ke->ke_runq != NULL &&
1264                     (ke->ke_flags & KEF_ASSIGNED) == 0 &&
1265                     ke->ke_runq != KSEQ_CPU(ke->ke_cpu)->ksq_curr) {
1266                         runq_remove(ke->ke_runq, ke);
1267                         ke->ke_runq = KSEQ_CPU(ke->ke_cpu)->ksq_curr;
1268                         runq_add(ke->ke_runq, ke, 0);
1269                 }
1270                 /*
1271                  * Hold this kse on this cpu so that sched_prio() doesn't
1272                  * cause excessive migration.  We only want migration to
1273                  * happen as the result of a wakeup.
1274                  */
1275                 ke->ke_flags |= KEF_HOLD;
1276                 adjustrunqueue(td, prio);
1277                 ke->ke_flags &= ~KEF_HOLD;
1278         } else
1279                 td->td_priority = prio;
1280 }
1281
1282 /*
1283  * Update a thread's priority when it is lent another thread's
1284  * priority.
1285  */
1286 void
1287 sched_lend_prio(struct thread *td, u_char prio)
1288 {
1289
1290         td->td_flags |= TDF_BORROWING;
1291         sched_thread_priority(td, prio);
1292 }
1293
1294 /*
1295  * Restore a thread's priority when priority propagation is
1296  * over.  The prio argument is the minimum priority the thread
1297  * needs to have to satisfy other possible priority lending
1298  * requests.  If the thread's regular priority is less
1299  * important than prio, the thread will keep a priority boost
1300  * of prio.
1301  */
1302 void
1303 sched_unlend_prio(struct thread *td, u_char prio)
1304 {
1305         u_char base_pri;
1306
1307         if (td->td_base_pri >= PRI_MIN_TIMESHARE &&
1308             td->td_base_pri <= PRI_MAX_TIMESHARE)
1309                 base_pri = td->td_ksegrp->kg_user_pri;
1310         else
1311                 base_pri = td->td_base_pri;
1312         if (prio >= base_pri) {
1313                 td->td_flags &= ~TDF_BORROWING;
1314                 sched_thread_priority(td, base_pri);
1315         } else
1316                 sched_lend_prio(td, prio);
1317 }
1318
1319 void
1320 sched_prio(struct thread *td, u_char prio)
1321 {
1322         u_char oldprio;
1323
1324         /* First, update the base priority. */
1325         td->td_base_pri = prio;
1326
1327         /*
1328          * If the thread is borrowing another thread's priority, don't
1329          * ever lower the priority.
1330          */
1331         if (td->td_flags & TDF_BORROWING && td->td_priority < prio)
1332                 return;
1333
1334         /* Change the real priority. */
1335         oldprio = td->td_priority;
1336         sched_thread_priority(td, prio);
1337
1338         /*
1339          * If the thread is on a turnstile, then let the turnstile update
1340          * its state.
1341          */
1342         if (TD_ON_LOCK(td) && oldprio != prio)
1343                 turnstile_adjust(td, oldprio);
1344 }
1345
1346 void
1347 sched_switch(struct thread *td, struct thread *newtd, int flags)
1348 {
1349         struct kseq *ksq;
1350         struct kse *ke;
1351
1352         mtx_assert(&sched_lock, MA_OWNED);
1353
1354         ke = td->td_kse;
1355         ksq = KSEQ_SELF();
1356
1357         td->td_lastcpu = td->td_oncpu;
1358         td->td_oncpu = NOCPU;
1359         td->td_flags &= ~TDF_NEEDRESCHED;
1360         td->td_owepreempt = 0;
1361
1362         /*
1363          * If the KSE has been assigned it may be in the process of switching
1364          * to the new cpu.  This is the case in sched_bind().
1365          */
1366         if (td == PCPU_GET(idlethread)) {
1367                 TD_SET_CAN_RUN(td);
1368         } else if ((ke->ke_flags & KEF_ASSIGNED) == 0) {
1369                 /* We are ending our run so make our slot available again */
1370                 SLOT_RELEASE(td->td_ksegrp);
1371                 kseq_load_rem(ksq, ke);
1372                 if (TD_IS_RUNNING(td)) {
1373                         /*
1374                          * Don't allow the thread to migrate
1375                          * from a preemption.
1376                          */
1377                         ke->ke_flags |= KEF_HOLD;
1378                         setrunqueue(td, (flags & SW_PREEMPT) ?
1379                             SRQ_OURSELF|SRQ_YIELDING|SRQ_PREEMPTED :
1380                             SRQ_OURSELF|SRQ_YIELDING);
1381                         ke->ke_flags &= ~KEF_HOLD;
1382                 } else if ((td->td_proc->p_flag & P_HADTHREADS) &&
1383                     (newtd == NULL || newtd->td_ksegrp != td->td_ksegrp))
1384                         /*
1385                          * We will not be on the run queue.
1386                          * So we must be sleeping or similar.
1387                          * Don't use the slot if we will need it
1388                          * for newtd.
1389                          */
1390                         slot_fill(td->td_ksegrp);
1391         }
1392         if (newtd != NULL) {
1393                 /*
1394                  * If we bring in a thread account for it as if it had been
1395                  * added to the run queue and then chosen.
1396                  */
1397                 newtd->td_kse->ke_flags |= KEF_DIDRUN;
1398                 newtd->td_kse->ke_runq = ksq->ksq_curr;
1399                 TD_SET_RUNNING(newtd);
1400                 kseq_load_add(KSEQ_SELF(), newtd->td_kse);
1401                 /*
1402                  * XXX When we preempt, we've already consumed a slot because
1403                  * we got here through sched_add().  However, newtd can come
1404                  * from thread_switchout() which can't SLOT_USE() because
1405                  * the SLOT code is scheduler dependent.  We must use the
1406                  * slot here otherwise.
1407                  */
1408                 if ((flags & SW_PREEMPT) == 0)
1409                         SLOT_USE(newtd->td_ksegrp);
1410         } else
1411                 newtd = choosethread();
1412         if (td != newtd) {
1413 #ifdef  HWPMC_HOOKS
1414                 if (PMC_PROC_IS_USING_PMCS(td->td_proc))
1415                         PMC_SWITCH_CONTEXT(td, PMC_FN_CSW_OUT);
1416 #endif
1417                 cpu_switch(td, newtd);
1418 #ifdef  HWPMC_HOOKS
1419                 if (PMC_PROC_IS_USING_PMCS(td->td_proc))
1420                         PMC_SWITCH_CONTEXT(td, PMC_FN_CSW_IN);
1421 #endif
1422         }
1423
1424         sched_lock.mtx_lock = (uintptr_t)td;
1425
1426         td->td_oncpu = PCPU_GET(cpuid);
1427 }
1428
1429 void
1430 sched_nice(struct proc *p, int nice)
1431 {
1432         struct ksegrp *kg;
1433         struct kse *ke;
1434         struct thread *td;
1435         struct kseq *kseq;
1436
1437         PROC_LOCK_ASSERT(p, MA_OWNED);
1438         mtx_assert(&sched_lock, MA_OWNED);
1439         /*
1440          * We need to adjust the nice counts for running KSEs.
1441          */
1442         FOREACH_KSEGRP_IN_PROC(p, kg) {
1443                 if (kg->kg_pri_class == PRI_TIMESHARE) {
1444                         FOREACH_THREAD_IN_GROUP(kg, td) {
1445                                 ke = td->td_kse;
1446                                 if (ke->ke_runq == NULL)
1447                                         continue;
1448                                 kseq = KSEQ_CPU(ke->ke_cpu);
1449                                 kseq_nice_rem(kseq, p->p_nice);
1450                                 kseq_nice_add(kseq, nice);
1451                         }
1452                 }
1453         }
1454         p->p_nice = nice;
1455         FOREACH_KSEGRP_IN_PROC(p, kg) {
1456                 sched_priority(kg);
1457                 FOREACH_THREAD_IN_GROUP(kg, td)
1458                         td->td_flags |= TDF_NEEDRESCHED;
1459         }
1460 }
1461
1462 void
1463 sched_sleep(struct thread *td)
1464 {
1465         mtx_assert(&sched_lock, MA_OWNED);
1466
1467         td->td_slptime = ticks;
1468 }
1469
1470 void
1471 sched_wakeup(struct thread *td)
1472 {
1473         mtx_assert(&sched_lock, MA_OWNED);
1474
1475         /*
1476          * Let the kseg know how long we slept for.  This is because process
1477          * interactivity behavior is modeled in the kseg.
1478          */
1479         if (td->td_slptime) {
1480                 struct ksegrp *kg;
1481                 int hzticks;
1482
1483                 kg = td->td_ksegrp;
1484                 hzticks = (ticks - td->td_slptime) << 10;
1485                 if (hzticks >= SCHED_SLP_RUN_MAX) {
1486                         kg->kg_slptime = SCHED_SLP_RUN_MAX;
1487                         kg->kg_runtime = 1;
1488                 } else {
1489                         kg->kg_slptime += hzticks;
1490                         sched_interact_update(kg);
1491                 }
1492                 sched_priority(kg);
1493                 sched_slice(td->td_kse);
1494                 td->td_slptime = 0;
1495         }
1496         setrunqueue(td, SRQ_BORING);
1497 }
1498
1499 /*
1500  * Penalize the parent for creating a new child and initialize the child's
1501  * priority.
1502  */
1503 void
1504 sched_fork(struct thread *td, struct thread *childtd)
1505 {
1506
1507         mtx_assert(&sched_lock, MA_OWNED);
1508
1509         sched_fork_ksegrp(td, childtd->td_ksegrp);
1510         sched_fork_thread(td, childtd);
1511 }
1512
1513 void
1514 sched_fork_ksegrp(struct thread *td, struct ksegrp *child)
1515 {
1516         struct ksegrp *kg = td->td_ksegrp;
1517         mtx_assert(&sched_lock, MA_OWNED);
1518
1519         child->kg_slptime = kg->kg_slptime;
1520         child->kg_runtime = kg->kg_runtime;
1521         child->kg_user_pri = kg->kg_user_pri;
1522         sched_interact_fork(child);
1523         kg->kg_runtime += tickincr;
1524         sched_interact_update(kg);
1525 }
1526
1527 void
1528 sched_fork_thread(struct thread *td, struct thread *child)
1529 {
1530         struct kse *ke;
1531         struct kse *ke2;
1532
1533         sched_newthread(child);
1534         ke = td->td_kse;
1535         ke2 = child->td_kse;
1536         ke2->ke_slice = 1;      /* Attempt to quickly learn interactivity. */
1537         ke2->ke_cpu = ke->ke_cpu;
1538         ke2->ke_runq = NULL;
1539
1540         /* Grab our parents cpu estimation information. */
1541         ke2->ke_ticks = ke->ke_ticks;
1542         ke2->ke_ltick = ke->ke_ltick;
1543         ke2->ke_ftick = ke->ke_ftick;
1544 }
1545
1546 void
1547 sched_class(struct ksegrp *kg, int class)
1548 {
1549         struct kseq *kseq;
1550         struct kse *ke;
1551         struct thread *td;
1552         int nclass;
1553         int oclass;
1554
1555         mtx_assert(&sched_lock, MA_OWNED);
1556         if (kg->kg_pri_class == class)
1557                 return;
1558
1559         nclass = PRI_BASE(class);
1560         oclass = PRI_BASE(kg->kg_pri_class);
1561         FOREACH_THREAD_IN_GROUP(kg, td) {
1562                 ke = td->td_kse;
1563                 if ((ke->ke_state != KES_ONRUNQ &&
1564                     ke->ke_state != KES_THREAD) || ke->ke_runq == NULL)
1565                         continue;
1566                 kseq = KSEQ_CPU(ke->ke_cpu);
1567
1568 #ifdef SMP
1569                 /*
1570                  * On SMP if we're on the RUNQ we must adjust the transferable
1571                  * count because could be changing to or from an interrupt
1572                  * class.
1573                  */
1574                 if (ke->ke_state == KES_ONRUNQ) {
1575                         if (KSE_CAN_MIGRATE(ke)) {
1576                                 kseq->ksq_transferable--;
1577                                 kseq->ksq_group->ksg_transferable--;
1578                         }
1579                         if (KSE_CAN_MIGRATE(ke)) {
1580                                 kseq->ksq_transferable++;
1581                                 kseq->ksq_group->ksg_transferable++;
1582                         }
1583                 }
1584 #endif
1585                 if (oclass == PRI_TIMESHARE) {
1586                         kseq->ksq_load_timeshare--;
1587                         kseq_nice_rem(kseq, kg->kg_proc->p_nice);
1588                 }
1589                 if (nclass == PRI_TIMESHARE) {
1590                         kseq->ksq_load_timeshare++;
1591                         kseq_nice_add(kseq, kg->kg_proc->p_nice);
1592                 }
1593         }
1594
1595         kg->kg_pri_class = class;
1596 }
1597
1598 /*
1599  * Return some of the child's priority and interactivity to the parent.
1600  */
1601 void
1602 sched_exit(struct proc *p, struct thread *childtd)
1603 {
1604         mtx_assert(&sched_lock, MA_OWNED);
1605         sched_exit_ksegrp(FIRST_KSEGRP_IN_PROC(p), childtd);
1606         sched_exit_thread(NULL, childtd);
1607 }
1608
1609 void
1610 sched_exit_ksegrp(struct ksegrp *kg, struct thread *td)
1611 {
1612         /* kg->kg_slptime += td->td_ksegrp->kg_slptime; */
1613         kg->kg_runtime += td->td_ksegrp->kg_runtime;
1614         sched_interact_update(kg);
1615 }
1616
1617 void
1618 sched_exit_thread(struct thread *td, struct thread *childtd)
1619 {
1620         CTR3(KTR_SCHED, "sched_exit_thread: %p(%s) prio %d",
1621             childtd, childtd->td_proc->p_comm, childtd->td_priority);
1622         kseq_load_rem(KSEQ_CPU(childtd->td_kse->ke_cpu), childtd->td_kse);
1623 }
1624
1625 void
1626 sched_clock(struct thread *td)
1627 {
1628         struct kseq *kseq;
1629         struct ksegrp *kg;
1630         struct kse *ke;
1631
1632         mtx_assert(&sched_lock, MA_OWNED);
1633         kseq = KSEQ_SELF();
1634 #ifdef SMP
1635         if (ticks >= bal_tick)
1636                 sched_balance();
1637         if (ticks >= gbal_tick && balance_groups)
1638                 sched_balance_groups();
1639         /*
1640          * We could have been assigned a non real-time thread without an
1641          * IPI.
1642          */
1643         if (kseq->ksq_assigned)
1644                 kseq_assign(kseq);      /* Potentially sets NEEDRESCHED */
1645 #endif
1646         ke = td->td_kse;
1647         kg = ke->ke_ksegrp;
1648
1649         /* Adjust ticks for pctcpu */
1650         ke->ke_ticks++;
1651         ke->ke_ltick = ticks;
1652
1653         /* Go up to one second beyond our max and then trim back down */
1654         if (ke->ke_ftick + SCHED_CPU_TICKS + hz < ke->ke_ltick)
1655                 sched_pctcpu_update(ke);
1656
1657         if (td->td_flags & TDF_IDLETD)
1658                 return;
1659         /*
1660          * We only do slicing code for TIMESHARE ksegrps.
1661          */
1662         if (kg->kg_pri_class != PRI_TIMESHARE)
1663                 return;
1664         /*
1665          * We used a tick charge it to the ksegrp so that we can compute our
1666          * interactivity.
1667          */
1668         kg->kg_runtime += tickincr;
1669         sched_interact_update(kg);
1670
1671         /*
1672          * We used up one time slice.
1673          */
1674         if (--ke->ke_slice > 0)
1675                 return;
1676         /*
1677          * We're out of time, recompute priorities and requeue.
1678          */
1679         kseq_load_rem(kseq, ke);
1680         sched_priority(kg);
1681         sched_slice(ke);
1682         if (SCHED_CURR(kg, ke))
1683                 ke->ke_runq = kseq->ksq_curr;
1684         else
1685                 ke->ke_runq = kseq->ksq_next;
1686         kseq_load_add(kseq, ke);
1687         td->td_flags |= TDF_NEEDRESCHED;
1688 }
1689
1690 int
1691 sched_runnable(void)
1692 {
1693         struct kseq *kseq;
1694         int load;
1695
1696         load = 1;
1697
1698         kseq = KSEQ_SELF();
1699 #ifdef SMP
1700         if (kseq->ksq_assigned) {
1701                 mtx_lock_spin(&sched_lock);
1702                 kseq_assign(kseq);
1703                 mtx_unlock_spin(&sched_lock);
1704         }
1705 #endif
1706         if ((curthread->td_flags & TDF_IDLETD) != 0) {
1707                 if (kseq->ksq_load > 0)
1708                         goto out;
1709         } else
1710                 if (kseq->ksq_load - 1 > 0)
1711                         goto out;
1712         load = 0;
1713 out:
1714         return (load);
1715 }
1716
1717 void
1718 sched_userret(struct thread *td)
1719 {
1720         struct ksegrp *kg;
1721
1722         KASSERT((td->td_flags & TDF_BORROWING) == 0,
1723             ("thread with borrowed priority returning to userland"));
1724         kg = td->td_ksegrp;
1725         if (td->td_priority != kg->kg_user_pri) {
1726                 mtx_lock_spin(&sched_lock);
1727                 td->td_priority = kg->kg_user_pri;
1728                 td->td_base_pri = kg->kg_user_pri;
1729                 mtx_unlock_spin(&sched_lock);
1730         }
1731 }
1732
1733 struct kse *
1734 sched_choose(void)
1735 {
1736         struct kseq *kseq;
1737         struct kse *ke;
1738
1739         mtx_assert(&sched_lock, MA_OWNED);
1740         kseq = KSEQ_SELF();
1741 #ifdef SMP
1742 restart:
1743         if (kseq->ksq_assigned)
1744                 kseq_assign(kseq);
1745 #endif
1746         ke = kseq_choose(kseq);
1747         if (ke) {
1748 #ifdef SMP
1749                 if (ke->ke_ksegrp->kg_pri_class == PRI_IDLE)
1750                         if (kseq_idled(kseq) == 0)
1751                                 goto restart;
1752 #endif
1753                 kseq_runq_rem(kseq, ke);
1754                 ke->ke_state = KES_THREAD;
1755                 ke->ke_flags &= ~KEF_PREEMPTED;
1756                 return (ke);
1757         }
1758 #ifdef SMP
1759         if (kseq_idled(kseq) == 0)
1760                 goto restart;
1761 #endif
1762         return (NULL);
1763 }
1764
1765 void
1766 sched_add(struct thread *td, int flags)
1767 {
1768         struct kseq *kseq;
1769         struct ksegrp *kg;
1770         struct kse *ke;
1771         int preemptive;
1772         int canmigrate;
1773         int class;
1774
1775         CTR5(KTR_SCHED, "sched_add: %p(%s) prio %d by %p(%s)",
1776             td, td->td_proc->p_comm, td->td_priority, curthread,
1777             curthread->td_proc->p_comm);
1778         mtx_assert(&sched_lock, MA_OWNED);
1779         ke = td->td_kse;
1780         kg = td->td_ksegrp;
1781         canmigrate = 1;
1782         preemptive = !(flags & SRQ_YIELDING);
1783         class = PRI_BASE(kg->kg_pri_class);
1784         kseq = KSEQ_SELF();
1785         if ((ke->ke_flags & KEF_INTERNAL) == 0)
1786                 SLOT_USE(td->td_ksegrp);
1787         ke->ke_flags &= ~KEF_INTERNAL;
1788 #ifdef SMP
1789         if (ke->ke_flags & KEF_ASSIGNED) {
1790                 if (ke->ke_flags & KEF_REMOVED)
1791                         ke->ke_flags &= ~KEF_REMOVED;
1792                 return;
1793         }
1794         canmigrate = KSE_CAN_MIGRATE(ke);
1795         /*
1796          * Don't migrate running threads here.  Force the long term balancer
1797          * to do it.
1798          */
1799         if (ke->ke_flags & KEF_HOLD) {
1800                 ke->ke_flags &= ~KEF_HOLD;
1801                 canmigrate = 0;
1802         }
1803 #endif
1804         KASSERT(ke->ke_state != KES_ONRUNQ,
1805             ("sched_add: kse %p (%s) already in run queue", ke,
1806             ke->ke_proc->p_comm));
1807         KASSERT(ke->ke_proc->p_sflag & PS_INMEM,
1808             ("sched_add: process swapped out"));
1809         KASSERT(ke->ke_runq == NULL,
1810             ("sched_add: KSE %p is still assigned to a run queue", ke));
1811         if (flags & SRQ_PREEMPTED)
1812                 ke->ke_flags |= KEF_PREEMPTED;
1813         switch (class) {
1814         case PRI_ITHD:
1815         case PRI_REALTIME:
1816                 ke->ke_runq = kseq->ksq_curr;
1817                 ke->ke_slice = SCHED_SLICE_MAX;
1818                 if (canmigrate)
1819                         ke->ke_cpu = PCPU_GET(cpuid);
1820                 break;
1821         case PRI_TIMESHARE:
1822                 if (SCHED_CURR(kg, ke))
1823                         ke->ke_runq = kseq->ksq_curr;
1824                 else
1825                         ke->ke_runq = kseq->ksq_next;
1826                 break;
1827         case PRI_IDLE:
1828                 /*
1829                  * This is for priority prop.
1830                  */
1831                 if (ke->ke_thread->td_priority < PRI_MIN_IDLE)
1832                         ke->ke_runq = kseq->ksq_curr;
1833                 else
1834                         ke->ke_runq = &kseq->ksq_idle;
1835                 ke->ke_slice = SCHED_SLICE_MIN;
1836                 break;
1837         default:
1838                 panic("Unknown pri class.");
1839                 break;
1840         }
1841 #ifdef SMP
1842         /*
1843          * If this thread is pinned or bound, notify the target cpu.
1844          */
1845         if (!canmigrate && ke->ke_cpu != PCPU_GET(cpuid) ) {
1846                 ke->ke_runq = NULL;
1847                 kseq_notify(ke, ke->ke_cpu);
1848                 return;
1849         }
1850         /*
1851          * If we had been idle, clear our bit in the group and potentially
1852          * the global bitmap.  If not, see if we should transfer this thread.
1853          */
1854         if ((class == PRI_TIMESHARE || class == PRI_REALTIME) &&
1855             (kseq->ksq_group->ksg_idlemask & PCPU_GET(cpumask)) != 0) {
1856                 /*
1857                  * Check to see if our group is unidling, and if so, remove it
1858                  * from the global idle mask.
1859                  */
1860                 if (kseq->ksq_group->ksg_idlemask ==
1861                     kseq->ksq_group->ksg_cpumask)
1862                         atomic_clear_int(&kseq_idle, kseq->ksq_group->ksg_mask);
1863                 /*
1864                  * Now remove ourselves from the group specific idle mask.
1865                  */
1866                 kseq->ksq_group->ksg_idlemask &= ~PCPU_GET(cpumask);
1867         } else if (canmigrate && kseq->ksq_load > 1 && class != PRI_ITHD)
1868                 if (kseq_transfer(kseq, ke, class))
1869                         return;
1870         ke->ke_cpu = PCPU_GET(cpuid);
1871 #endif
1872         if (td->td_priority < curthread->td_priority &&
1873             ke->ke_runq == kseq->ksq_curr)
1874                 curthread->td_flags |= TDF_NEEDRESCHED;
1875         if (preemptive && maybe_preempt(td))
1876                 return;
1877         ke->ke_state = KES_ONRUNQ;
1878
1879         kseq_runq_add(kseq, ke, flags);
1880         kseq_load_add(kseq, ke);
1881 }
1882
1883 void
1884 sched_rem(struct thread *td)
1885 {
1886         struct kseq *kseq;
1887         struct kse *ke;
1888
1889         CTR5(KTR_SCHED, "sched_rem: %p(%s) prio %d by %p(%s)",
1890             td, td->td_proc->p_comm, td->td_priority, curthread,
1891             curthread->td_proc->p_comm);
1892         mtx_assert(&sched_lock, MA_OWNED);
1893         ke = td->td_kse;
1894         SLOT_RELEASE(td->td_ksegrp);
1895         ke->ke_flags &= ~KEF_PREEMPTED;
1896         if (ke->ke_flags & KEF_ASSIGNED) {
1897                 ke->ke_flags |= KEF_REMOVED;
1898                 return;
1899         }
1900         KASSERT((ke->ke_state == KES_ONRUNQ),
1901             ("sched_rem: KSE not on run queue"));
1902
1903         ke->ke_state = KES_THREAD;
1904         kseq = KSEQ_CPU(ke->ke_cpu);
1905         kseq_runq_rem(kseq, ke);
1906         kseq_load_rem(kseq, ke);
1907 }
1908
1909 fixpt_t
1910 sched_pctcpu(struct thread *td)
1911 {
1912         fixpt_t pctcpu;
1913         struct kse *ke;
1914
1915         pctcpu = 0;
1916         ke = td->td_kse;
1917         if (ke == NULL)
1918                 return (0);
1919
1920         mtx_lock_spin(&sched_lock);
1921         if (ke->ke_ticks) {
1922                 int rtick;
1923
1924                 /*
1925                  * Don't update more frequently than twice a second.  Allowing
1926                  * this causes the cpu usage to decay away too quickly due to
1927                  * rounding errors.
1928                  */
1929                 if (ke->ke_ftick + SCHED_CPU_TICKS < ke->ke_ltick ||
1930                     ke->ke_ltick < (ticks - (hz / 2)))
1931                         sched_pctcpu_update(ke);
1932                 /* How many rtick per second ? */
1933                 rtick = min(ke->ke_ticks / SCHED_CPU_TIME, SCHED_CPU_TICKS);
1934                 pctcpu = (FSCALE * ((FSCALE * rtick)/realstathz)) >> FSHIFT;
1935         }
1936
1937         ke->ke_proc->p_swtime = ke->ke_ltick - ke->ke_ftick;
1938         mtx_unlock_spin(&sched_lock);
1939
1940         return (pctcpu);
1941 }
1942
1943 void
1944 sched_bind(struct thread *td, int cpu)
1945 {
1946         struct kse *ke;
1947
1948         mtx_assert(&sched_lock, MA_OWNED);
1949         ke = td->td_kse;
1950         ke->ke_flags |= KEF_BOUND;
1951 #ifdef SMP
1952         if (PCPU_GET(cpuid) == cpu)
1953                 return;
1954         /* sched_rem without the runq_remove */
1955         ke->ke_state = KES_THREAD;
1956         kseq_load_rem(KSEQ_CPU(ke->ke_cpu), ke);
1957         kseq_notify(ke, cpu);
1958         /* When we return from mi_switch we'll be on the correct cpu. */
1959         mi_switch(SW_VOL, NULL);
1960 #endif
1961 }
1962
1963 void
1964 sched_unbind(struct thread *td)
1965 {
1966         mtx_assert(&sched_lock, MA_OWNED);
1967         td->td_kse->ke_flags &= ~KEF_BOUND;
1968 }
1969
1970 int
1971 sched_is_bound(struct thread *td)
1972 {
1973         mtx_assert(&sched_lock, MA_OWNED);
1974         return (td->td_kse->ke_flags & KEF_BOUND);
1975 }
1976
1977 int
1978 sched_load(void)
1979 {
1980 #ifdef SMP
1981         int total;
1982         int i;
1983
1984         total = 0;
1985         for (i = 0; i <= ksg_maxid; i++)
1986                 total += KSEQ_GROUP(i)->ksg_load;
1987         return (total);
1988 #else
1989         return (KSEQ_SELF()->ksq_sysload);
1990 #endif
1991 }
1992
1993 int
1994 sched_sizeof_ksegrp(void)
1995 {
1996         return (sizeof(struct ksegrp) + sizeof(struct kg_sched));
1997 }
1998
1999 int
2000 sched_sizeof_proc(void)
2001 {
2002         return (sizeof(struct proc));
2003 }
2004
2005 int
2006 sched_sizeof_thread(void)
2007 {
2008         return (sizeof(struct thread) + sizeof(struct td_sched));
2009 }
2010 #define KERN_SWITCH_INCLUDE 1
2011 #include "kern/kern_switch.c"