1/* 2 * Copyright (c) 2009 Apple Inc. All rights reserved. 3 * 4 * @APPLE_OSREFERENCE_LICENSE_HEADER_START@ 5 * 6 * This file contains Original Code and/or Modifications of Original Code 7 * as defined in and that are subject to the Apple Public Source License 8 * Version 2.0 (the 'License'). You may not use this file except in 9 * compliance with the License. The rights granted to you under the License 10 * may not be used to create, or enable the creation or redistribution of, 11 * unlawful or unlicensed copies of an Apple operating system, or to 12 * circumvent, violate, or enable the circumvention or violation of, any 13 * terms of an Apple operating system software license agreement. 14 * 15 * Please obtain a copy of the License at 16 * http://www.opensource.apple.com/apsl/ and read it before using this file. 17 * 18 * The Original Code and all software distributed under the License are 19 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER 20 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, 21 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, 22 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT. 23 * Please see the License for the specific language governing rights and 24 * limitations under the License. 25 * 26 * @APPLE_OSREFERENCE_LICENSE_HEADER_END@ 27 */ 28 29#include <mach/mach_types.h> 30#include <mach/machine.h> 31#include <mach/policy.h> 32#include <mach/sync_policy.h> 33#include <mach/thread_act.h> 34 35#include <machine/machine_routines.h> 36#include <machine/sched_param.h> 37#include <machine/machine_cpu.h> 38 39#include <kern/kern_types.h> 40#include <kern/clock.h> 41#include <kern/counters.h> 42#include <kern/cpu_number.h> 43#include <kern/cpu_data.h> 44#include <kern/debug.h> 45#include <kern/lock.h> 46#include <kern/macro_help.h> 47#include <kern/machine.h> 48#include <kern/misc_protos.h> 49#include <kern/processor.h> 50#include <kern/queue.h> 51#include <kern/sched.h> 52#include <kern/sched_prim.h> 53#include <kern/syscall_subr.h> 54#include <kern/task.h> 55#include <kern/thread.h> 56#include <kern/wait_queue.h> 57 58#include <vm/pmap.h> 59#include <vm/vm_kern.h> 60#include <vm/vm_map.h> 61 62#include <mach/sdt.h> 63 64#include <sys/kdebug.h> 65 66static void 67sched_proto_init(void); 68 69static void 70sched_proto_timebase_init(void); 71 72static void 73sched_proto_processor_init(processor_t processor); 74 75static void 76sched_proto_pset_init(processor_set_t pset); 77 78static void 79sched_proto_maintenance_continuation(void); 80 81static thread_t 82sched_proto_choose_thread(processor_t processor, 83 int priority); 84 85static thread_t 86sched_proto_steal_thread(processor_set_t pset); 87 88static void 89sched_proto_compute_priority(thread_t thread, 90 boolean_t override_depress); 91 92static processor_t 93sched_proto_choose_processor( processor_set_t pset, 94 processor_t processor, 95 thread_t thread); 96 97 98static boolean_t 99sched_proto_processor_enqueue( 100 processor_t processor, 101 thread_t thread, 102 integer_t options); 103 104static void 105sched_proto_processor_queue_shutdown( 106 processor_t processor); 107 108static boolean_t 109sched_proto_processor_queue_remove( 110 processor_t processor, 111 thread_t thread); 112 113static boolean_t 114sched_proto_processor_queue_empty(processor_t processor); 115 116static boolean_t 117sched_proto_processor_queue_has_priority(processor_t processor, 118 int priority, 119 boolean_t gte); 120 121static boolean_t 122sched_proto_priority_is_urgent(int priority); 123 124static ast_t 125sched_proto_processor_csw_check(processor_t processor); 126 127static uint32_t 128sched_proto_initial_quantum_size(thread_t thread); 129 130static sched_mode_t 131sched_proto_initial_thread_sched_mode(task_t parent_task); 132 133static boolean_t 134sched_proto_supports_timeshare_mode(void); 135 136static boolean_t 137sched_proto_can_update_priority(thread_t thread); 138 139static void 140sched_proto_update_priority(thread_t thread); 141 142static void 143sched_proto_lightweight_update_priority(thread_t thread); 144 145static void 146sched_proto_quantum_expire(thread_t thread); 147 148static boolean_t 149sched_proto_should_current_thread_rechoose_processor(processor_t processor); 150 151static int 152sched_proto_processor_runq_count(processor_t processor); 153 154static uint64_t 155sched_proto_processor_runq_stats_count_sum(processor_t processor); 156 157const struct sched_dispatch_table sched_proto_dispatch = { 158 sched_proto_init, 159 sched_proto_timebase_init, 160 sched_proto_processor_init, 161 sched_proto_pset_init, 162 sched_proto_maintenance_continuation, 163 sched_proto_choose_thread, 164 sched_proto_steal_thread, 165 sched_proto_compute_priority, 166 sched_proto_choose_processor, 167 sched_proto_processor_enqueue, 168 sched_proto_processor_queue_shutdown, 169 sched_proto_processor_queue_remove, 170 sched_proto_processor_queue_empty, 171 sched_proto_priority_is_urgent, 172 sched_proto_processor_csw_check, 173 sched_proto_processor_queue_has_priority, 174 sched_proto_initial_quantum_size, 175 sched_proto_initial_thread_sched_mode, 176 sched_proto_supports_timeshare_mode, 177 sched_proto_can_update_priority, 178 sched_proto_update_priority, 179 sched_proto_lightweight_update_priority, 180 sched_proto_quantum_expire, 181 sched_proto_should_current_thread_rechoose_processor, 182 sched_proto_processor_runq_count, 183 sched_proto_processor_runq_stats_count_sum, 184 sched_traditional_fairshare_init, 185 sched_traditional_fairshare_runq_count, 186 sched_traditional_fairshare_runq_stats_count_sum, 187 sched_traditional_fairshare_enqueue, 188 sched_traditional_fairshare_dequeue, 189 sched_traditional_fairshare_queue_remove, 190 TRUE /* direct_dispatch_to_idle_processors */ 191}; 192 193static struct run_queue *global_runq; 194static struct run_queue global_runq_storage; 195 196#define GLOBAL_RUNQ ((processor_t)-2) 197decl_simple_lock_data(static,global_runq_lock); 198 199extern int max_unsafe_quanta; 200 201static uint32_t proto_quantum_us; 202static uint32_t proto_quantum; 203 204static uint32_t runqueue_generation; 205 206static processor_t proto_processor; 207 208static uint64_t sched_proto_tick_deadline; 209static uint32_t sched_proto_tick; 210 211static void 212sched_proto_init(void) 213{ 214 proto_quantum_us = 10*1000; 215 216 printf("standard proto timeslicing quantum is %d us\n", proto_quantum_us); 217 218 simple_lock_init(&global_runq_lock, 0); 219 global_runq = &global_runq_storage; 220 run_queue_init(global_runq); 221 runqueue_generation = 0; 222 223 proto_processor = master_processor; 224} 225 226static void 227sched_proto_timebase_init(void) 228{ 229 uint64_t abstime; 230 231 /* standard timeslicing quantum */ 232 clock_interval_to_absolutetime_interval( 233 proto_quantum_us, NSEC_PER_USEC, &abstime); 234 assert((abstime >> 32) == 0 && (uint32_t)abstime != 0); 235 proto_quantum = (uint32_t)abstime; 236 237 thread_depress_time = 1 * proto_quantum; 238 default_timeshare_computation = proto_quantum / 2; 239 default_timeshare_constraint = proto_quantum; 240 241 max_unsafe_computation = max_unsafe_quanta * proto_quantum; 242 sched_safe_duration = 2 * max_unsafe_quanta * proto_quantum; 243 244} 245 246static void 247sched_proto_processor_init(processor_t processor __unused) 248{ 249 /* No per-processor state */ 250} 251 252static void 253sched_proto_pset_init(processor_set_t pset __unused) 254{ 255} 256 257static void 258sched_proto_maintenance_continuation(void) 259{ 260 uint64_t abstime = mach_absolute_time(); 261 262 sched_proto_tick++; 263 264 /* Every 8 seconds, switch to another processor */ 265 if ((sched_proto_tick & 0x7) == 0) { 266 processor_t new_processor; 267 268 new_processor = proto_processor->processor_list; 269 if (new_processor == PROCESSOR_NULL) 270 proto_processor = master_processor; 271 else 272 proto_processor = new_processor; 273 } 274 275 276 /* 277 * Compute various averages. 278 */ 279 compute_averages(); 280 281 if (sched_proto_tick_deadline == 0) 282 sched_proto_tick_deadline = abstime; 283 284 clock_deadline_for_periodic_event(sched_one_second_interval, abstime, 285 &sched_proto_tick_deadline); 286 287 assert_wait_deadline((event_t)sched_proto_maintenance_continuation, THREAD_UNINT, sched_proto_tick_deadline); 288 thread_block((thread_continue_t)sched_proto_maintenance_continuation); 289 /*NOTREACHED*/ 290} 291 292static thread_t 293sched_proto_choose_thread(processor_t processor, 294 int priority) 295{ 296 run_queue_t rq = global_runq; 297 queue_t queue; 298 int pri, count; 299 thread_t thread; 300 301 302 simple_lock(&global_runq_lock); 303 304 queue = rq->queues + rq->highq; 305 pri = rq->highq; 306 count = rq->count; 307 308 /* 309 * Since we don't depress priorities, a high priority thread 310 * may get selected over and over again. Put a runqueue 311 * generation number in the thread structure so that we 312 * can ensure that we've cycled through all runnable tasks 313 * before coming back to a high priority thread. This isn't 314 * perfect, especially if the number of runnable threads always 315 * stays high, but is a workable approximation 316 */ 317 318 while (count > 0 && pri >= priority) { 319 thread = (thread_t)queue_first(queue); 320 while (!queue_end(queue, (queue_entry_t)thread)) { 321 if ((thread->bound_processor == PROCESSOR_NULL || 322 thread->bound_processor == processor) && 323 runqueue_generation != thread->runqueue_generation) { 324 remqueue((queue_entry_t)thread); 325 326 thread->runq = PROCESSOR_NULL; 327 thread->runqueue_generation = runqueue_generation; 328 SCHED_STATS_RUNQ_CHANGE(&rq->runq_stats, rq->count); 329 rq->count--; 330 if (queue_empty(queue)) { 331 if (pri != IDLEPRI) 332 clrbit(MAXPRI - pri, rq->bitmap); 333 rq->highq = MAXPRI - ffsbit(rq->bitmap); 334 } 335 336 simple_unlock(&global_runq_lock); 337 return (thread); 338 } 339 count--; 340 341 thread = (thread_t)queue_next((queue_entry_t)thread); 342 } 343 344 queue--; pri--; 345 } 346 347 runqueue_generation++; 348 349 simple_unlock(&global_runq_lock); 350 return (THREAD_NULL); 351} 352 353static thread_t 354sched_proto_steal_thread(processor_set_t pset) 355{ 356 pset_unlock(pset); 357 358 return (THREAD_NULL); 359 360} 361 362static void 363sched_proto_compute_priority(thread_t thread, 364 boolean_t override_depress __unused) 365{ 366 set_sched_pri(thread, thread->priority); 367} 368 369static processor_t 370sched_proto_choose_processor( processor_set_t pset, 371 processor_t processor, 372 thread_t thread __unused) 373{ 374 processor = proto_processor; 375 376 /* 377 * Check that the correct processor set is 378 * returned locked. 379 */ 380 if (pset != processor->processor_set) { 381 pset_unlock(pset); 382 383 pset = processor->processor_set; 384 pset_lock(pset); 385 } 386 387 return (processor); 388} 389 390static boolean_t 391sched_proto_processor_enqueue( 392 processor_t processor __unused, 393 thread_t thread, 394 integer_t options) 395{ 396 run_queue_t rq = global_runq; 397 boolean_t result; 398 399 simple_lock(&global_runq_lock); 400 result = run_queue_enqueue(rq, thread, options); 401 thread->runq = GLOBAL_RUNQ; 402 simple_unlock(&global_runq_lock); 403 404 return (result); 405} 406 407static void 408sched_proto_processor_queue_shutdown( 409 processor_t processor) 410{ 411 /* With a global runqueue, just stop choosing this processor */ 412 (void)processor; 413} 414 415static boolean_t 416sched_proto_processor_queue_remove( 417 processor_t processor, 418 thread_t thread) 419{ 420 void * rqlock; 421 run_queue_t rq; 422 423 rqlock = &global_runq_lock; 424 rq = global_runq; 425 426 simple_lock(rqlock); 427 if (processor == thread->runq) { 428 /* 429 * Thread is on a run queue and we have a lock on 430 * that run queue. 431 */ 432 remqueue((queue_entry_t)thread); 433 SCHED_STATS_RUNQ_CHANGE(&rq->runq_stats, rq->count); 434 rq->count--; 435 if (SCHED(priority_is_urgent)(thread->sched_pri)) { 436 rq->urgency--; assert(rq->urgency >= 0); 437 } 438 439 if (queue_empty(rq->queues + thread->sched_pri)) { 440 /* update run queue status */ 441 if (thread->sched_pri != IDLEPRI) 442 clrbit(MAXPRI - thread->sched_pri, rq->bitmap); 443 rq->highq = MAXPRI - ffsbit(rq->bitmap); 444 } 445 446 thread->runq = PROCESSOR_NULL; 447 } 448 else { 449 /* 450 * The thread left the run queue before we could 451 * lock the run queue. 452 */ 453 assert(thread->runq == PROCESSOR_NULL); 454 processor = PROCESSOR_NULL; 455 } 456 457 simple_unlock(rqlock); 458 459 return (processor != PROCESSOR_NULL); 460} 461 462static boolean_t 463sched_proto_processor_queue_empty(processor_t processor __unused) 464{ 465 boolean_t result; 466 467 result = (global_runq->count == 0); 468 469 return result; 470} 471 472static boolean_t 473sched_proto_processor_queue_has_priority(processor_t processor __unused, 474 int priority, 475 boolean_t gte) 476{ 477 boolean_t result; 478 479 simple_lock(&global_runq_lock); 480 481 if (gte) 482 result = global_runq->highq >= priority; 483 else 484 result = global_runq->highq >= priority; 485 486 simple_unlock(&global_runq_lock); 487 488 return result; 489} 490 491/* Implement sched_preempt_pri in code */ 492static boolean_t 493sched_proto_priority_is_urgent(int priority) 494{ 495 if (priority <= BASEPRI_FOREGROUND) 496 return FALSE; 497 498 if (priority < MINPRI_KERNEL) 499 return TRUE; 500 501 if (priority >= BASEPRI_PREEMPT) 502 return TRUE; 503 504 return FALSE; 505} 506 507static ast_t 508sched_proto_processor_csw_check(processor_t processor __unused) 509{ 510 run_queue_t runq; 511 int count, urgency; 512 513 runq = global_runq; 514 count = runq->count; 515 urgency = runq->urgency; 516 517 if (count > 0) { 518 if (urgency > 0) 519 return (AST_PREEMPT | AST_URGENT); 520 521 return AST_PREEMPT; 522 } 523 524 return AST_NONE; 525} 526 527static uint32_t 528sched_proto_initial_quantum_size(thread_t thread __unused) 529{ 530 return proto_quantum; 531} 532 533static sched_mode_t 534sched_proto_initial_thread_sched_mode(task_t parent_task) 535{ 536 if (parent_task == kernel_task) 537 return TH_MODE_FIXED; 538 else 539 return TH_MODE_TIMESHARE; 540} 541 542static boolean_t 543sched_proto_supports_timeshare_mode(void) 544{ 545 return TRUE; 546} 547 548static boolean_t 549sched_proto_can_update_priority(thread_t thread __unused) 550{ 551 return FALSE; 552} 553 554static void 555sched_proto_update_priority(thread_t thread __unused) 556{ 557 558} 559 560static void 561sched_proto_lightweight_update_priority(thread_t thread __unused) 562{ 563 564} 565 566static void 567sched_proto_quantum_expire(thread_t thread __unused) 568{ 569 570} 571 572static boolean_t 573sched_proto_should_current_thread_rechoose_processor(processor_t processor) 574{ 575 return (proto_processor != processor); 576} 577 578static int 579sched_proto_processor_runq_count(processor_t processor) 580{ 581 if (master_processor == processor) { 582 return global_runq->count; 583 } else { 584 return 0; 585 } 586} 587 588static uint64_t 589sched_proto_processor_runq_stats_count_sum(processor_t processor) 590{ 591 if (master_processor == processor) { 592 return global_runq->runq_stats.count_sum; 593 } else { 594 return 0ULL; 595 } 596} 597 598