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