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: clock_prim.c 60 * Author: Avadis Tevanian, Jr. 61 * Date: 1986 62 * 63 * Clock primitives. 64 */ 65 66#include <mach/boolean.h> 67#include <mach/kern_return.h> 68#include <mach/machine.h> 69#include <kern/host.h> 70#include <kern/mach_param.h> 71#include <kern/sched.h> 72#include <sys/kdebug.h> 73#include <kern/spl.h> 74#include <kern/thread.h> 75#include <kern/processor.h> 76#include <kern/ledger.h> 77#include <machine/machparam.h> 78 79/* 80 * thread_quantum_expire: 81 * 82 * Recalculate the quantum and priority for a thread. 83 * 84 * Called at splsched. 85 */ 86 87void 88thread_quantum_expire( 89 timer_call_param_t p0, 90 timer_call_param_t p1) 91{ 92 processor_t processor = p0; 93 thread_t thread = p1; 94 ast_t preempt; 95 96 SCHED_STATS_QUANTUM_TIMER_EXPIRATION(processor); 97 98 /* 99 * We bill CPU time to both the individual thread and its task. 100 * 101 * Because this balance adjustment could potentially attempt to wake this very 102 * thread, we must credit the ledger before taking the thread lock. The ledger 103 * pointers are only manipulated by the thread itself at the ast boundary. 104 */ 105 ledger_credit(thread->t_ledger, task_ledgers.cpu_time, thread->current_quantum); 106 ledger_credit(thread->t_threadledger, thread_ledgers.cpu_time, thread->current_quantum); 107 108 thread_lock(thread); 109 110 /* 111 * We've run up until our quantum expiration, and will (potentially) 112 * continue without re-entering the scheduler, so update this now. 113 */ 114 thread->last_run_time = processor->quantum_end; 115 116 /* 117 * Check for fail-safe trip. 118 */ 119 if ((thread->sched_mode == TH_MODE_REALTIME || thread->sched_mode == TH_MODE_FIXED) && 120 !(thread->sched_flags & TH_SFLAG_PROMOTED) && 121 !(thread->options & TH_OPT_SYSTEM_CRITICAL)) { 122 uint64_t new_computation; 123 124 new_computation = processor->quantum_end - thread->computation_epoch; 125 new_computation += thread->computation_metered; 126 if (new_computation > max_unsafe_computation) { 127 KERNEL_DEBUG_CONSTANT(MACHDBG_CODE(DBG_MACH_SCHED, MACH_FAILSAFE)|DBG_FUNC_NONE, 128 (uintptr_t)thread->sched_pri, (uintptr_t)thread->sched_mode, 0, 0, 0); 129 130 if (thread->sched_mode == TH_MODE_REALTIME) { 131 thread->priority = DEPRESSPRI; 132 } 133 134 thread->saved_mode = thread->sched_mode; 135 136 if (SCHED(supports_timeshare_mode)) { 137 sched_share_incr(); 138 thread->sched_mode = TH_MODE_TIMESHARE; 139 } else { 140 /* XXX handle fixed->fixed case */ 141 thread->sched_mode = TH_MODE_FIXED; 142 } 143 144 thread->safe_release = processor->quantum_end + sched_safe_duration; 145 thread->sched_flags |= TH_SFLAG_FAILSAFE; 146 } 147 } 148 149 /* 150 * Recompute scheduled priority if appropriate. 151 */ 152 if (SCHED(can_update_priority)(thread)) 153 SCHED(update_priority)(thread); 154 else 155 SCHED(lightweight_update_priority)(thread); 156 157 SCHED(quantum_expire)(thread); 158 159 processor->current_pri = thread->sched_pri; 160 processor->current_thmode = thread->sched_mode; 161 162 /* 163 * This quantum is up, give this thread another. 164 */ 165 if (first_timeslice(processor)) 166 processor->timeslice--; 167 168 thread_quantum_init(thread); 169 thread->last_quantum_refill_time = processor->quantum_end; 170 171 /* Reload precise timing global policy to thread-local policy */ 172 thread->precise_user_kernel_time = use_precise_user_kernel_time(thread); 173 174 /* 175 * Since non-precise user/kernel time doesn't update the state/thread timer 176 * during privilege transitions, synthesize an event now. 177 */ 178 if (!thread->precise_user_kernel_time) { 179 timer_switch(PROCESSOR_DATA(processor, current_state), 180 processor->quantum_end, 181 PROCESSOR_DATA(processor, current_state)); 182 timer_switch(PROCESSOR_DATA(processor, thread_timer), 183 processor->quantum_end, 184 PROCESSOR_DATA(processor, thread_timer)); 185 } 186 187 processor->quantum_end = mach_absolute_time() + thread->current_quantum; 188 timer_call_enter1(&processor->quantum_timer, thread, 189 processor->quantum_end, TIMER_CALL_CRITICAL); 190 191 /* 192 * Context switch check. 193 */ 194 if ((preempt = csw_check(processor)) != AST_NONE) 195 ast_on(preempt); 196 else { 197 processor_set_t pset = processor->processor_set; 198 199 pset_lock(pset); 200 201 pset_pri_hint(pset, processor, processor->current_pri); 202 pset_count_hint(pset, processor, SCHED(processor_runq_count)(processor)); 203 204 pset_unlock(pset); 205 } 206 207 thread_unlock(thread); 208} 209 210#if defined(CONFIG_SCHED_TRADITIONAL) 211 212void 213sched_traditional_quantum_expire(thread_t thread __unused) 214{ 215 /* 216 * No special behavior when a timeshare, fixed, or realtime thread 217 * uses up its entire quantum 218 */ 219} 220 221void 222lightweight_update_priority(thread_t thread) 223{ 224 if (thread->sched_mode == TH_MODE_TIMESHARE) { 225 register uint32_t delta; 226 227 thread_timer_delta(thread, delta); 228 229 /* 230 * Accumulate timesharing usage only 231 * during contention for processor 232 * resources. 233 */ 234 if (thread->pri_shift < INT8_MAX) 235 thread->sched_usage += delta; 236 237 thread->cpu_delta += delta; 238 239 /* 240 * Adjust the scheduled priority if 241 * the thread has not been promoted 242 * and is not depressed. 243 */ 244 if ( !(thread->sched_flags & TH_SFLAG_PROMOTED) && 245 !(thread->sched_flags & TH_SFLAG_DEPRESSED_MASK) ) 246 compute_my_priority(thread); 247 } 248} 249 250/* 251 * Define shifts for simulating (5/8) ** n 252 * 253 * Shift structures for holding update shifts. Actual computation 254 * is usage = (usage >> shift1) +/- (usage >> abs(shift2)) where the 255 * +/- is determined by the sign of shift 2. 256 */ 257struct shift_data { 258 int shift1; 259 int shift2; 260}; 261 262#define SCHED_DECAY_TICKS 32 263static struct shift_data sched_decay_shifts[SCHED_DECAY_TICKS] = { 264 {1,1},{1,3},{1,-3},{2,-7},{3,5},{3,-5},{4,-8},{5,7}, 265 {5,-7},{6,-10},{7,10},{7,-9},{8,-11},{9,12},{9,-11},{10,-13}, 266 {11,14},{11,-13},{12,-15},{13,17},{13,-15},{14,-17},{15,19},{16,18}, 267 {16,-19},{17,22},{18,20},{18,-20},{19,26},{20,22},{20,-22},{21,-27} 268}; 269 270/* 271 * do_priority_computation: 272 * 273 * Calculate the timesharing priority based upon usage and load. 274 */ 275#ifdef CONFIG_EMBEDDED 276 277#define do_priority_computation(thread, pri) \ 278 MACRO_BEGIN \ 279 (pri) = (thread)->priority /* start with base priority */ \ 280 - ((thread)->sched_usage >> (thread)->pri_shift); \ 281 if ((pri) < MAXPRI_THROTTLE) { \ 282 if ((thread)->task->max_priority > MAXPRI_THROTTLE) \ 283 (pri) = MAXPRI_THROTTLE; \ 284 else \ 285 if ((pri) < MINPRI_USER) \ 286 (pri) = MINPRI_USER; \ 287 } else \ 288 if ((pri) > MAXPRI_KERNEL) \ 289 (pri) = MAXPRI_KERNEL; \ 290 MACRO_END 291 292#else 293 294#define do_priority_computation(thread, pri) \ 295 MACRO_BEGIN \ 296 (pri) = (thread)->priority /* start with base priority */ \ 297 - ((thread)->sched_usage >> (thread)->pri_shift); \ 298 if ((pri) < MINPRI_USER) \ 299 (pri) = MINPRI_USER; \ 300 else \ 301 if ((pri) > MAXPRI_KERNEL) \ 302 (pri) = MAXPRI_KERNEL; \ 303 MACRO_END 304 305#endif /* defined(CONFIG_SCHED_TRADITIONAL) */ 306 307#endif 308 309/* 310 * set_priority: 311 * 312 * Set the base priority of the thread 313 * and reset its scheduled priority. 314 * 315 * Called with the thread locked. 316 */ 317void 318set_priority( 319 register thread_t thread, 320 register int priority) 321{ 322 thread->priority = priority; 323 SCHED(compute_priority)(thread, FALSE); 324} 325 326#if defined(CONFIG_SCHED_TRADITIONAL) 327 328/* 329 * compute_priority: 330 * 331 * Reset the scheduled priority of the thread 332 * according to its base priority if the 333 * thread has not been promoted or depressed. 334 * 335 * Called with the thread locked. 336 */ 337void 338compute_priority( 339 register thread_t thread, 340 boolean_t override_depress) 341{ 342 register int priority; 343 344 if ( !(thread->sched_flags & TH_SFLAG_PROMOTED) && 345 (!(thread->sched_flags & TH_SFLAG_DEPRESSED_MASK) || 346 override_depress ) ) { 347 if (thread->sched_mode == TH_MODE_TIMESHARE) 348 do_priority_computation(thread, priority); 349 else 350 priority = thread->priority; 351 352 set_sched_pri(thread, priority); 353 } 354} 355 356/* 357 * compute_my_priority: 358 * 359 * Reset the scheduled priority for 360 * a timesharing thread. 361 * 362 * Only for use on the current thread 363 * if timesharing and not depressed. 364 * 365 * Called with the thread locked. 366 */ 367void 368compute_my_priority( 369 register thread_t thread) 370{ 371 register int priority; 372 373 do_priority_computation(thread, priority); 374 assert(thread->runq == PROCESSOR_NULL); 375 thread->sched_pri = priority; 376} 377 378/* 379 * can_update_priority 380 * 381 * Make sure we don't do re-dispatches more frequently than a scheduler tick. 382 * 383 * Called with the thread locked. 384 */ 385boolean_t 386can_update_priority( 387 thread_t thread) 388{ 389 if (sched_tick == thread->sched_stamp) 390 return (FALSE); 391 else 392 return (TRUE); 393} 394 395/* 396 * update_priority 397 * 398 * Perform housekeeping operations driven by scheduler tick. 399 * 400 * Called with the thread locked. 401 */ 402void 403update_priority( 404 register thread_t thread) 405{ 406 register unsigned ticks; 407 register uint32_t delta; 408 409 ticks = sched_tick - thread->sched_stamp; 410 assert(ticks != 0); 411 thread->sched_stamp += ticks; 412 thread->pri_shift = sched_pri_shift; 413 414 /* 415 * Gather cpu usage data. 416 */ 417 thread_timer_delta(thread, delta); 418 if (ticks < SCHED_DECAY_TICKS) { 419 register struct shift_data *shiftp; 420 421 /* 422 * Accumulate timesharing usage only 423 * during contention for processor 424 * resources. 425 */ 426 if (thread->pri_shift < INT8_MAX) 427 thread->sched_usage += delta; 428 429 thread->cpu_usage += delta + thread->cpu_delta; 430 thread->cpu_delta = 0; 431 432 shiftp = &sched_decay_shifts[ticks]; 433 if (shiftp->shift2 > 0) { 434 thread->cpu_usage = 435 (thread->cpu_usage >> shiftp->shift1) + 436 (thread->cpu_usage >> shiftp->shift2); 437 thread->sched_usage = 438 (thread->sched_usage >> shiftp->shift1) + 439 (thread->sched_usage >> shiftp->shift2); 440 } 441 else { 442 thread->cpu_usage = 443 (thread->cpu_usage >> shiftp->shift1) - 444 (thread->cpu_usage >> -(shiftp->shift2)); 445 thread->sched_usage = 446 (thread->sched_usage >> shiftp->shift1) - 447 (thread->sched_usage >> -(shiftp->shift2)); 448 } 449 } 450 else { 451 thread->cpu_usage = thread->cpu_delta = 0; 452 thread->sched_usage = 0; 453 } 454 455 /* 456 * Check for fail-safe release. 457 */ 458 if ( (thread->sched_flags & TH_SFLAG_FAILSAFE) && 459 mach_absolute_time() >= thread->safe_release ) { 460 if (thread->saved_mode != TH_MODE_TIMESHARE) { 461 if (thread->saved_mode == TH_MODE_REALTIME) { 462 thread->priority = BASEPRI_RTQUEUES; 463 } 464 465 thread->sched_mode = thread->saved_mode; 466 thread->saved_mode = TH_MODE_NONE; 467 468 if ((thread->state & (TH_RUN|TH_IDLE)) == TH_RUN) 469 sched_share_decr(); 470 471 if (!(thread->sched_flags & TH_SFLAG_DEPRESSED_MASK)) 472 set_sched_pri(thread, thread->priority); 473 } 474 475 thread->sched_flags &= ~TH_SFLAG_FAILSAFE; 476 } 477 478#if CONFIG_EMBEDDED 479 /* Check for pending throttle transitions, and safely switch queues */ 480 if (thread->sched_flags & TH_SFLAG_PENDING_THROTTLE_MASK) { 481 boolean_t removed = thread_run_queue_remove(thread); 482 483 if (thread->sched_flags & TH_SFLAG_PENDING_THROTTLE_DEMOTION) { 484 if (thread->sched_mode == TH_MODE_REALTIME) { 485 thread->saved_mode = thread->sched_mode; 486 thread->sched_mode = TH_MODE_TIMESHARE; 487 488 if ((thread->state & (TH_RUN|TH_IDLE)) == TH_RUN) 489 sched_share_incr(); 490 } else { 491 /* 492 * It's possible that this is a realtime thread that has 493 * already tripped the failsafe, in which case saved_mode 494 * is already set correctly. 495 */ 496 if (!(thread->sched_flags & TH_SFLAG_FAILSAFE)) { 497 thread->saved_mode = thread->sched_mode; 498 } 499 thread->sched_flags &= ~TH_SFLAG_FAILSAFE; 500 } 501 thread->sched_flags |= TH_SFLAG_THROTTLED; 502 503 } else { 504 if ((thread->sched_mode == TH_MODE_TIMESHARE) 505 && (thread->saved_mode == TH_MODE_REALTIME)) { 506 if ((thread->state & (TH_RUN|TH_IDLE)) == TH_RUN) 507 sched_share_decr(); 508 } 509 510 thread->sched_mode = thread->saved_mode; 511 thread->saved_mode = TH_MODE_NONE; 512 thread->sched_flags &= ~TH_SFLAG_THROTTLED; 513 } 514 515 thread->sched_flags &= ~(TH_SFLAG_PENDING_THROTTLE_MASK); 516 517 if (removed) 518 thread_setrun(thread, SCHED_TAILQ); 519 } 520#endif 521 522 /* 523 * Recompute scheduled priority if appropriate. 524 */ 525 if ( (thread->sched_mode == TH_MODE_TIMESHARE) && 526 !(thread->sched_flags & TH_SFLAG_PROMOTED) && 527 !(thread->sched_flags & TH_SFLAG_DEPRESSED_MASK) ) { 528 register int new_pri; 529 530 do_priority_computation(thread, new_pri); 531 if (new_pri != thread->sched_pri) { 532 boolean_t removed = thread_run_queue_remove(thread); 533 534 thread->sched_pri = new_pri; 535 if (removed) 536 thread_setrun(thread, SCHED_TAILQ); 537 } 538 } 539 540 return; 541} 542 543#endif /* CONFIG_SCHED_TRADITIONAL */ 544