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