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