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