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