1/* 2 * Copyright (c) 2000-2012 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 * @OSF_COPYRIGHT@ 30 */ 31/* 32 * Mach Operating System 33 * Copyright (c) 1991,1990,1989,1988,1987 Carnegie Mellon University 34 * All Rights Reserved. 35 * 36 * Permission to use, copy, modify and distribute this software and its 37 * documentation is hereby granted, provided that both the copyright 38 * notice and this permission notice appear in all copies of the 39 * software, derivative works or modified versions, and any portions 40 * thereof, and that both notices appear in supporting documentation. 41 * 42 * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS" 43 * CONDITION. CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND FOR 44 * ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE. 45 * 46 * Carnegie Mellon requests users of this software to return to 47 * 48 * Software Distribution Coordinator or Software.Distribution@CS.CMU.EDU 49 * School of Computer Science 50 * Carnegie Mellon University 51 * Pittsburgh PA 15213-3890 52 * 53 * any improvements or extensions that they make and grant Carnegie Mellon 54 * the rights to redistribute these changes. 55 */ 56/* 57 */ 58/* 59 * File: sched_prim.h 60 * Author: David Golub 61 * 62 * Scheduling primitive definitions file 63 * 64 */ 65 66#ifndef _KERN_SCHED_PRIM_H_ 67#define _KERN_SCHED_PRIM_H_ 68 69#include <mach/boolean.h> 70#include <mach/machine/vm_types.h> 71#include <mach/kern_return.h> 72#include <kern/clock.h> 73#include <kern/kern_types.h> 74#include <kern/thread.h> 75#include <sys/cdefs.h> 76 77#ifdef MACH_KERNEL_PRIVATE 78 79/* Initialization */ 80extern void sched_init(void); 81 82extern void sched_startup(void); 83 84extern void sched_timebase_init(void); 85 86/* Force a preemption point for a thread and wait for it to stop running */ 87extern boolean_t thread_stop( 88 thread_t thread, 89 boolean_t until_not_runnable); 90 91/* Release a previous stop request */ 92extern void thread_unstop( 93 thread_t thread); 94 95/* Wait for a thread to stop running */ 96extern void thread_wait( 97 thread_t thread, 98 boolean_t until_not_runnable); 99 100/* Unblock thread on wake up */ 101extern boolean_t thread_unblock( 102 thread_t thread, 103 wait_result_t wresult); 104 105/* Unblock and dispatch thread */ 106extern kern_return_t thread_go( 107 thread_t thread, 108 wait_result_t wresult); 109 110/* Handle threads at context switch */ 111extern void thread_dispatch( 112 thread_t old_thread, 113 thread_t new_thread); 114 115/* Switch directly to a particular thread */ 116extern int thread_run( 117 thread_t self, 118 thread_continue_t continuation, 119 void *parameter, 120 thread_t new_thread); 121 122/* Resume thread with new stack */ 123extern void thread_continue( 124 thread_t old_thread); 125 126/* Invoke continuation */ 127extern void call_continuation( 128 thread_continue_t continuation, 129 void *parameter, 130 wait_result_t wresult); 131 132/* Set the current scheduled priority */ 133extern void set_sched_pri( 134 thread_t thread, 135 int priority); 136 137/* Set base priority of the specified thread */ 138extern void set_priority( 139 thread_t thread, 140 int priority); 141 142/* Reset scheduled priority of thread */ 143extern void compute_priority( 144 thread_t thread, 145 boolean_t override_depress); 146 147/* Adjust scheduled priority of thread during execution */ 148extern void compute_my_priority( 149 thread_t thread); 150 151/* Periodic scheduler activity */ 152extern void sched_init_thread(void (*)(void)); 153 154/* Perform sched_tick housekeeping activities */ 155extern boolean_t can_update_priority( 156 thread_t thread); 157 158extern void update_priority( 159 thread_t thread); 160 161extern void lightweight_update_priority( 162 thread_t thread); 163 164extern void sched_traditional_quantum_expire(thread_t thread); 165 166/* Idle processor thread */ 167extern void idle_thread(void); 168 169extern kern_return_t idle_thread_create( 170 processor_t processor); 171 172/* Continuation return from syscall */ 173extern void thread_syscall_return( 174 kern_return_t ret); 175 176/* Context switch */ 177extern wait_result_t thread_block_reason( 178 thread_continue_t continuation, 179 void *parameter, 180 ast_t reason); 181 182/* Reschedule thread for execution */ 183extern void thread_setrun( 184 thread_t thread, 185 integer_t options); 186 187#define SCHED_TAILQ 1 188#define SCHED_HEADQ 2 189#define SCHED_PREEMPT 4 190 191extern processor_set_t task_choose_pset( 192 task_t task); 193 194/* Bind the current thread to a particular processor */ 195extern processor_t thread_bind( 196 processor_t processor); 197 198/* Choose the best processor to run a thread */ 199extern processor_t choose_processor( 200 processor_set_t pset, 201 processor_t processor, 202 thread_t thread); 203 204/* Choose a thread from a processor's priority-based runq */ 205extern thread_t choose_thread( 206 processor_t processor, 207 run_queue_t runq, 208 int priority); 209 210 211extern void thread_quantum_init( 212 thread_t thread); 213 214extern void run_queue_init( 215 run_queue_t runq); 216 217extern thread_t run_queue_dequeue( 218 run_queue_t runq, 219 integer_t options); 220 221extern boolean_t run_queue_enqueue( 222 run_queue_t runq, 223 thread_t thread, 224 integer_t options); 225 226extern void run_queue_remove( 227 run_queue_t runq, 228 thread_t thread); 229 230/* Remove thread from its run queue */ 231extern boolean_t thread_run_queue_remove( 232 thread_t thread); 233 234extern void thread_timer_expire( 235 void *thread, 236 void *p1); 237 238extern boolean_t thread_eager_preemption( 239 thread_t thread); 240 241/* Fair Share routines */ 242#if defined(CONFIG_SCHED_TRADITIONAL) || defined(CONFIG_SCHED_PROTO) || defined(CONFIG_SCHED_FIXEDPRIORITY) 243void sched_traditional_fairshare_init(void); 244 245int sched_traditional_fairshare_runq_count(void); 246 247uint64_t sched_traditional_fairshare_runq_stats_count_sum(void); 248 249void sched_traditional_fairshare_enqueue(thread_t thread); 250 251thread_t sched_traditional_fairshare_dequeue(void); 252 253boolean_t sched_traditional_fairshare_queue_remove(thread_t thread); 254#endif 255 256#if defined(CONFIG_SCHED_GRRR) || defined(CONFIG_SCHED_FIXEDPRIORITY) 257void sched_grrr_fairshare_init(void); 258 259int sched_grrr_fairshare_runq_count(void); 260 261uint64_t sched_grrr_fairshare_runq_stats_count_sum(void); 262 263void sched_grrr_fairshare_enqueue(thread_t thread); 264 265thread_t sched_grrr_fairshare_dequeue(void); 266 267boolean_t sched_grrr_fairshare_queue_remove(thread_t thread); 268#endif 269 270extern boolean_t sched_generic_direct_dispatch_to_idle_processors; 271 272/* Set the maximum interrupt level for the thread */ 273__private_extern__ wait_interrupt_t thread_interrupt_level( 274 wait_interrupt_t interruptible); 275 276__private_extern__ wait_result_t thread_mark_wait_locked( 277 thread_t thread, 278 wait_interrupt_t interruptible); 279 280/* Wake up locked thread directly, passing result */ 281__private_extern__ kern_return_t clear_wait_internal( 282 thread_t thread, 283 wait_result_t result); 284 285extern void sched_stats_handle_csw( 286 processor_t processor, 287 int reasons, 288 int selfpri, 289 int otherpri); 290 291extern void sched_stats_handle_runq_change( 292 struct runq_stats *stats, 293 int old_count); 294 295 296 297#define SCHED_STATS_CSW(processor, reasons, selfpri, otherpri) \ 298do { \ 299 if (__builtin_expect(sched_stats_active, 0)) { \ 300 sched_stats_handle_csw((processor), \ 301 (reasons), (selfpri), (otherpri)); \ 302 } \ 303} while (0) 304 305 306#define SCHED_STATS_RUNQ_CHANGE(stats, old_count) \ 307do { \ 308 if (__builtin_expect(sched_stats_active, 0)) { \ 309 sched_stats_handle_runq_change((stats), \ 310 (old_count)); \ 311 } \ 312} while (0) 313 314#define THREAD_URGENCY_NONE 0 /* indicates that there is no currently runnable */ 315#define THREAD_URGENCY_BACKGROUND 1 /* indicates that the thread is marked as a "background" thread */ 316#define THREAD_URGENCY_NORMAL 2 /* indicates that the thread is marked as a "normal" thread */ 317#define THREAD_URGENCY_REAL_TIME 3 /* indicates that the thread is marked as a "real-time" or urgent thread */ 318#define THREAD_URGENCY_MAX 4 /* Marker */ 319/* Returns the "urgency" of a thread (provided by scheduler) */ 320extern int thread_get_urgency( 321 thread_t thread, 322 uint64_t *rt_period, 323 uint64_t *rt_deadline); 324 325/* Tells the "urgency" of the just scheduled thread (provided by CPU PM) */ 326extern void thread_tell_urgency( 327 int urgency, 328 uint64_t rt_period, 329 uint64_t rt_deadline, 330 thread_t nthread); 331 332/* Tells if there are "active" RT threads in the system (provided by CPU PM) */ 333extern void active_rt_threads( 334 boolean_t active); 335 336#endif /* MACH_KERNEL_PRIVATE */ 337 338__BEGIN_DECLS 339 340#ifdef XNU_KERNEL_PRIVATE 341 342extern boolean_t assert_wait_possible(void); 343 344/* Toggles a global override to turn off CPU Throttling */ 345#define CPU_THROTTLE_DISABLE 0 346#define CPU_THROTTLE_ENABLE 1 347extern void sys_override_cpu_throttle(int flag); 348 349/* 350 ****************** Only exported until BSD stops using ******************** 351 */ 352 353/* Wake up thread directly, passing result */ 354extern kern_return_t clear_wait( 355 thread_t thread, 356 wait_result_t result); 357 358/* Start thread running */ 359extern void thread_bootstrap_return(void); 360 361/* Return from exception (BSD-visible interface) */ 362extern void thread_exception_return(void) __dead2; 363 364#endif /* XNU_KERNEL_PRIVATE */ 365 366/* Context switch */ 367extern wait_result_t thread_block( 368 thread_continue_t continuation); 369 370extern wait_result_t thread_block_parameter( 371 thread_continue_t continuation, 372 void *parameter); 373 374/* Declare thread will wait on a particular event */ 375extern wait_result_t assert_wait( 376 event_t event, 377 wait_interrupt_t interruptible); 378 379/* Assert that the thread intends to wait with a timeout */ 380extern wait_result_t assert_wait_timeout( 381 event_t event, 382 wait_interrupt_t interruptible, 383 uint32_t interval, 384 uint32_t scale_factor); 385 386/* Assert that the thread intends to wait with an urgency, timeout and leeway */ 387extern wait_result_t assert_wait_timeout_with_leeway( 388 event_t event, 389 wait_interrupt_t interruptible, 390 wait_timeout_urgency_t urgency, 391 uint32_t interval, 392 uint32_t leeway, 393 uint32_t scale_factor); 394 395extern wait_result_t assert_wait_deadline( 396 event_t event, 397 wait_interrupt_t interruptible, 398 uint64_t deadline); 399 400/* Assert that the thread intends to wait with an urgency, deadline, and leeway */ 401extern wait_result_t assert_wait_deadline_with_leeway( 402 event_t event, 403 wait_interrupt_t interruptible, 404 wait_timeout_urgency_t urgency, 405 uint64_t deadline, 406 uint64_t leeway); 407 408/* Wake up thread (or threads) waiting on a particular event */ 409extern kern_return_t thread_wakeup_prim( 410 event_t event, 411 boolean_t one_thread, 412 wait_result_t result); 413 414extern kern_return_t thread_wakeup_prim_internal( 415 event_t event, 416 boolean_t one_thread, 417 wait_result_t result, 418 int priority); 419 420 421#define thread_wakeup(x) \ 422 thread_wakeup_prim((x), FALSE, THREAD_AWAKENED) 423#define thread_wakeup_with_result(x, z) \ 424 thread_wakeup_prim((x), FALSE, (z)) 425#define thread_wakeup_one(x) \ 426 thread_wakeup_prim((x), TRUE, THREAD_AWAKENED) 427 428#ifdef MACH_KERNEL_PRIVATE 429#define thread_wakeup_one_with_pri(x, pri) \ 430 thread_wakeup_prim_internal((x), TRUE, THREAD_AWAKENED, pri) 431#endif 432 433extern boolean_t preemption_enabled(void); 434 435#ifdef MACH_KERNEL_PRIVATE 436 437/* 438 * Scheduler algorithm indirection. If only one algorithm is 439 * enabled at compile-time, a direction function call is used. 440 * If more than one is enabled, calls are dispatched through 441 * a function pointer table. 442 */ 443 444#if !defined(CONFIG_SCHED_TRADITIONAL) && !defined(CONFIG_SCHED_PROTO) && !defined(CONFIG_SCHED_GRRR) && !defined(CONFIG_SCHED_FIXEDPRIORITY) 445#error Enable at least one scheduler algorithm in osfmk/conf/MASTER.XXX 446#endif 447 448#define SCHED(f) (sched_current_dispatch->f) 449 450struct sched_dispatch_table { 451 void (*init)(void); /* Init global state */ 452 void (*timebase_init)(void); /* Timebase-dependent initialization */ 453 void (*processor_init)(processor_t processor); /* Per-processor scheduler init */ 454 void (*pset_init)(processor_set_t pset); /* Per-processor set scheduler init */ 455 456 void (*maintenance_continuation)(void); /* Function called regularly */ 457 458 /* 459 * Choose a thread of greater or equal priority from the per-processor 460 * runqueue for timeshare/fixed threads 461 */ 462 thread_t (*choose_thread)( 463 processor_t processor, 464 int priority); 465 466 /* 467 * Steal a thread from another processor in the pset so that it can run 468 * immediately 469 */ 470 thread_t (*steal_thread)( 471 processor_set_t pset); 472 473 /* 474 * Recalculate sched_pri based on base priority, past running time, 475 * and scheduling class. 476 */ 477 void (*compute_priority)( 478 thread_t thread, 479 boolean_t override_depress); 480 481 /* 482 * Pick the best processor for a thread (any kind of thread) to run on. 483 */ 484 processor_t (*choose_processor)( 485 processor_set_t pset, 486 processor_t processor, 487 thread_t thread); 488 /* 489 * Enqueue a timeshare or fixed priority thread onto the per-processor 490 * runqueue 491 */ 492 boolean_t (*processor_enqueue)( 493 processor_t processor, 494 thread_t thread, 495 integer_t options); 496 497 /* Migrate threads away in preparation for processor shutdown */ 498 void (*processor_queue_shutdown)( 499 processor_t processor); 500 501 /* Remove the specific thread from the per-processor runqueue */ 502 boolean_t (*processor_queue_remove)( 503 processor_t processor, 504 thread_t thread); 505 506 /* 507 * Does the per-processor runqueue have any timeshare or fixed priority 508 * threads on it? Called without pset lock held, so should 509 * not assume immutability while executing. 510 */ 511 boolean_t (*processor_queue_empty)(processor_t processor); 512 513 /* 514 * Would this priority trigger an urgent preemption if it's sitting 515 * on the per-processor runqueue? 516 */ 517 boolean_t (*priority_is_urgent)(int priority); 518 519 /* 520 * Does the per-processor runqueue contain runnable threads that 521 * should cause the currently-running thread to be preempted? 522 */ 523 ast_t (*processor_csw_check)(processor_t processor); 524 525 /* 526 * Does the per-processor runqueue contain a runnable thread 527 * of > or >= priority, as a preflight for choose_thread() or other 528 * thread selection 529 */ 530 boolean_t (*processor_queue_has_priority)(processor_t processor, 531 int priority, 532 boolean_t gte); 533 534 /* Quantum size for the specified non-realtime thread. */ 535 uint32_t (*initial_quantum_size)(thread_t thread); 536 537 /* Scheduler mode for a new thread */ 538 sched_mode_t (*initial_thread_sched_mode)(task_t parent_task); 539 540 /* Scheduler algorithm supports timeshare (decay) mode */ 541 boolean_t (*supports_timeshare_mode)(void); 542 543 /* 544 * Is it safe to call update_priority, which may change a thread's 545 * runqueue or other state. This can be used to throttle changes 546 * to dynamic priority. 547 */ 548 boolean_t (*can_update_priority)(thread_t thread); 549 550 /* 551 * Update both scheduled priority and other persistent state. 552 * Side effects may including migration to another processor's runqueue. 553 */ 554 void (*update_priority)(thread_t thread); 555 556 /* Lower overhead update to scheduled priority and state. */ 557 void (*lightweight_update_priority)(thread_t thread); 558 559 /* Callback for non-realtime threads when the quantum timer fires */ 560 void (*quantum_expire)(thread_t thread); 561 562 /* 563 * Even though we could continue executing on this processor, does the 564 * topology (SMT, for instance) indicate that a better processor could be 565 * chosen 566 */ 567 boolean_t (*should_current_thread_rechoose_processor)(processor_t processor); 568 569 /* 570 * Runnable threads on per-processor runqueue. Should only 571 * be used for relative comparisons of load between processors. 572 */ 573 int (*processor_runq_count)(processor_t processor); 574 575 /* Aggregate runcount statistics for per-processor runqueue */ 576 uint64_t (*processor_runq_stats_count_sum)(processor_t processor); 577 578 /* Initialize structures to track demoted fairshare threads */ 579 void (*fairshare_init)(void); 580 581 /* Number of runnable fairshare threads */ 582 int (*fairshare_runq_count)(void); 583 584 /* Aggregate runcount statistics for fairshare runqueue */ 585 uint64_t (*fairshare_runq_stats_count_sum)(void); 586 587 void (*fairshare_enqueue)(thread_t thread); 588 589 thread_t (*fairshare_dequeue)(void); 590 591 boolean_t (*fairshare_queue_remove)(thread_t thread); 592 593 /* 594 * Use processor->next_thread to pin a thread to an idle 595 * processor. If FALSE, threads are enqueued and can 596 * be stolen by other processors. 597 */ 598 boolean_t direct_dispatch_to_idle_processors; 599}; 600 601#if defined(CONFIG_SCHED_TRADITIONAL) 602#define kSchedTraditionalString "traditional" 603#define kSchedTraditionalWithPsetRunqueueString "traditional_with_pset_runqueue" 604extern const struct sched_dispatch_table sched_traditional_dispatch; 605extern const struct sched_dispatch_table sched_traditional_with_pset_runqueue_dispatch; 606#endif 607 608#if defined(CONFIG_SCHED_PROTO) 609#define kSchedProtoString "proto" 610extern const struct sched_dispatch_table sched_proto_dispatch; 611#endif 612 613#if defined(CONFIG_SCHED_GRRR) 614#define kSchedGRRRString "grrr" 615extern const struct sched_dispatch_table sched_grrr_dispatch; 616#endif 617 618#if defined(CONFIG_SCHED_FIXEDPRIORITY) 619#define kSchedFixedPriorityString "fixedpriority" 620#define kSchedFixedPriorityWithPsetRunqueueString "fixedpriority_with_pset_runqueue" 621extern const struct sched_dispatch_table sched_fixedpriority_dispatch; 622extern const struct sched_dispatch_table sched_fixedpriority_with_pset_runqueue_dispatch; 623#endif 624 625/* 626 * It is an error to invoke any scheduler-related code 627 * before this is set up 628 */ 629enum sched_enum { 630 sched_enum_unknown = 0, 631#if defined(CONFIG_SCHED_TRADITIONAL) 632 sched_enum_traditional = 1, 633 sched_enum_traditional_with_pset_runqueue = 2, 634#endif 635#if defined(CONFIG_SCHED_PROTO) 636 sched_enum_proto = 3, 637#endif 638#if defined(CONFIG_SCHED_GRRR) 639 sched_enum_grrr = 4, 640#endif 641#if defined(CONFIG_SCHED_FIXEDPRIORITY) 642 sched_enum_fixedpriority = 5, 643 sched_enum_fixedpriority_with_pset_runqueue = 6, 644#endif 645 sched_enum_max = 7 646}; 647 648extern const struct sched_dispatch_table *sched_current_dispatch; 649 650#endif /* MACH_KERNEL_PRIVATE */ 651 652__END_DECLS 653 654#endif /* _KERN_SCHED_PRIM_H_ */ 655