]> git.saurik.com Git - apple/xnu.git/blob - osfmk/kern/sched_prim.c
projects / apple / xnu.git / blob
? search:


eebc19bf5b613150da8e046c0e9f90d0460240a7
[apple/xnu.git] / osfmk / kern / sched_prim.c
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_FREE_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.c
60 * Author: Avadis Tevanian, Jr.
61 * Date: 1986
62 *
63 * Scheduling primitives
64 *
65 */
66
67 #include <debug.h>
68
69 #include <mach/mach_types.h>
70 #include <mach/machine.h>
71 #include <mach/policy.h>
72 #include <mach/sync_policy.h>
73 #include <mach/thread_act.h>
74
75 #include <machine/machine_routines.h>
76 #include <machine/sched_param.h>
77 #include <machine/machine_cpu.h>
78 #include <machine/machlimits.h>
79
80 #include <kern/kern_types.h>
81 #include <kern/clock.h>
82 #include <kern/counters.h>
83 #include <kern/cpu_number.h>
84 #include <kern/cpu_data.h>
85 #include <kern/debug.h>
86 #include <kern/lock.h>
87 #include <kern/macro_help.h>
88 #include <kern/machine.h>
89 #include <kern/misc_protos.h>
90 #include <kern/processor.h>
91 #include <kern/queue.h>
92 #include <kern/sched.h>
93 #include <kern/sched_prim.h>
94 #include <kern/syscall_subr.h>
95 #include <kern/task.h>
96 #include <kern/thread.h>
97 #include <kern/wait_queue.h>
98 #include <kern/ledger.h>
99
100 #include <vm/pmap.h>
101 #include <vm/vm_kern.h>
102 #include <vm/vm_map.h>
103
104 #include <mach/sdt.h>
105
106 #include <sys/kdebug.h>
107
108 #include <kern/pms.h>
109
110 struct rt_queue rt_runq;
111 #define RT_RUNQ ((processor_t)-1)
112 decl_simple_lock_data(static,rt_lock);
113
114 #if defined(CONFIG_SCHED_TRADITIONAL) || defined(CONFIG_SCHED_PROTO) || defined(CONFIG_SCHED_GRRR) || defined(CONFIG_SCHED_FIXEDPRIORITY)
115 static struct fairshare_queue fs_runq;
116 #define FS_RUNQ ((processor_t)-2)
117 decl_simple_lock_data(static,fs_lock);
118 #endif
119
120 #define DEFAULT_PREEMPTION_RATE 100 /* (1/s) */
121 int default_preemption_rate = DEFAULT_PREEMPTION_RATE;
122
123 #define DEFAULT_BG_PREEMPTION_RATE 400 /* (1/s) */
124 int default_bg_preemption_rate = DEFAULT_BG_PREEMPTION_RATE;
125
126 #define MAX_UNSAFE_QUANTA 800
127 int max_unsafe_quanta = MAX_UNSAFE_QUANTA;
128
129 #define MAX_POLL_QUANTA 2
130 int max_poll_quanta = MAX_POLL_QUANTA;
131
132 #define SCHED_POLL_YIELD_SHIFT 4 /* 1/16 */
133 int sched_poll_yield_shift = SCHED_POLL_YIELD_SHIFT;
134
135 uint64_t max_poll_computation;
136
137 uint64_t max_unsafe_computation;
138 uint64_t sched_safe_duration;
139
140 #if defined(CONFIG_SCHED_TRADITIONAL)
141
142 uint32_t std_quantum;
143 uint32_t min_std_quantum;
144 uint32_t bg_quantum;
145
146 uint32_t std_quantum_us;
147 uint32_t bg_quantum_us;
148
149 #endif /* CONFIG_SCHED_TRADITIONAL */
150
151 uint32_t thread_depress_time;
152 uint32_t default_timeshare_computation;
153 uint32_t default_timeshare_constraint;
154
155 uint32_t max_rt_quantum;
156 uint32_t min_rt_quantum;
157
158 #if defined(CONFIG_SCHED_TRADITIONAL)
159
160 unsigned sched_tick;
161 uint32_t sched_tick_interval;
162
163 uint32_t sched_pri_shift = INT8_MAX;
164 uint32_t sched_fixed_shift;
165
166 static boolean_t sched_traditional_use_pset_runqueue = FALSE;
167
168 /* Defaults for timer deadline profiling */
169 #define TIMER_DEADLINE_TRACKING_BIN_1_DEFAULT 2000000 /* Timers with deadlines <=
170 * 2ms */
171 #define TIMER_DEADLINE_TRACKING_BIN_2_DEFAULT 5000000 /* Timers with deadlines
172 <= 5ms */
173 uint64_t timer_deadline_tracking_bin_1;
174 uint64_t timer_deadline_tracking_bin_2;
175
176 __attribute__((always_inline))
177 static inline run_queue_t runq_for_processor(processor_t processor)
178 {
179 if (sched_traditional_use_pset_runqueue)
180 return &processor->processor_set->pset_runq;
181 else
182 return &processor->runq;
183 }
184
185 __attribute__((always_inline))
186 static inline void runq_consider_incr_bound_count(processor_t processor, thread_t thread)
187 {
188 if (thread->bound_processor == PROCESSOR_NULL)
189 return;
190
191 assert(thread->bound_processor == processor);
192
193 if (sched_traditional_use_pset_runqueue)
194 processor->processor_set->pset_runq_bound_count++;
195
196 processor->runq_bound_count++;
197 }
198
199 __attribute__((always_inline))
200 static inline void runq_consider_decr_bound_count(processor_t processor, thread_t thread)
201 {
202 if (thread->bound_processor == PROCESSOR_NULL)
203 return;
204
205 assert(thread->bound_processor == processor);
206
207 if (sched_traditional_use_pset_runqueue)
208 processor->processor_set->pset_runq_bound_count--;
209
210 processor->runq_bound_count--;
211 }
212
213 #endif /* CONFIG_SCHED_TRADITIONAL */
214
215 uint64_t sched_one_second_interval;
216
217 uint32_t sched_run_count, sched_share_count;
218 uint32_t sched_load_average, sched_mach_factor;
219
220 /* Forwards */
221
222 #if defined(CONFIG_SCHED_TRADITIONAL)
223
224 static void load_shift_init(void) __attribute__((section("__TEXT, initcode")));
225 static void preempt_pri_init(void) __attribute__((section("__TEXT, initcode")));
226
227 #endif /* CONFIG_SCHED_TRADITIONAL */
228
229 static thread_t thread_select(
230 thread_t thread,
231 processor_t processor);
232
233 #if CONFIG_SCHED_IDLE_IN_PLACE
234 static thread_t thread_select_idle(
235 thread_t thread,
236 processor_t processor);
237 #endif
238
239 thread_t processor_idle(
240 thread_t thread,
241 processor_t processor);
242
243 #if defined(CONFIG_SCHED_TRADITIONAL)
244
245 static thread_t steal_thread(
246 processor_set_t pset);
247
248 static thread_t steal_thread_disabled(
249 processor_set_t pset) __attribute__((unused));
250
251
252 static thread_t steal_processor_thread(
253 processor_t processor);
254
255 static void thread_update_scan(void);
256
257 static void processor_setrun(
258 processor_t processor,
259 thread_t thread,
260 integer_t options);
261
262 static boolean_t
263 processor_enqueue(
264 processor_t processor,
265 thread_t thread,
266 integer_t options);
267
268 static boolean_t
269 processor_queue_remove(
270 processor_t processor,
271 thread_t thread);
272
273 static boolean_t processor_queue_empty(processor_t processor);
274
275 static boolean_t priority_is_urgent(int priority);
276
277 static ast_t processor_csw_check(processor_t processor);
278
279 static boolean_t processor_queue_has_priority(processor_t processor,
280 int priority,
281 boolean_t gte);
282
283 static boolean_t should_current_thread_rechoose_processor(processor_t processor);
284
285 static int sched_traditional_processor_runq_count(processor_t processor);
286
287 static boolean_t sched_traditional_with_pset_runqueue_processor_queue_empty(processor_t processor);
288
289 static uint64_t sched_traditional_processor_runq_stats_count_sum(processor_t processor);
290
291 static uint64_t sched_traditional_with_pset_runqueue_processor_runq_stats_count_sum(processor_t processor);
292 #endif
293
294
295 #if defined(CONFIG_SCHED_TRADITIONAL)
296
297 static void
298 sched_traditional_init(void);
299
300 static void
301 sched_traditional_timebase_init(void);
302
303 static void
304 sched_traditional_processor_init(processor_t processor);
305
306 static void
307 sched_traditional_pset_init(processor_set_t pset);
308
309 static void
310 sched_traditional_with_pset_runqueue_init(void);
311
312 #endif
313
314 static void
315 sched_realtime_init(void) __attribute__((section("__TEXT, initcode")));
316
317 static void
318 sched_realtime_timebase_init(void);
319
320 static void
321 sched_timer_deadline_tracking_init(void);
322
323 #if defined(CONFIG_SCHED_TRADITIONAL)
324 static void
325 sched_traditional_tick_continue(void);
326
327 static uint32_t
328 sched_traditional_initial_quantum_size(thread_t thread);
329
330 static sched_mode_t
331 sched_traditional_initial_thread_sched_mode(task_t parent_task);
332
333 static boolean_t
334 sched_traditional_supports_timeshare_mode(void);
335
336 static thread_t
337 sched_traditional_choose_thread(
338 processor_t processor,
339 int priority);
340
341 #endif
342
343 #if DEBUG
344 extern int debug_task;
345 #define TLOG(a, fmt, args...) if(debug_task & a) kprintf(fmt, ## args)
346 #else
347 #define TLOG(a, fmt, args...) do {} while (0)
348 #endif
349
350 #if DEBUG
351 static
352 boolean_t thread_runnable(
353 thread_t thread);
354
355 #endif /*DEBUG*/
356
357 /*
358 * State machine
359 *
360 * states are combinations of:
361 * R running
362 * W waiting (or on wait queue)
363 * N non-interruptible
364 * O swapped out
365 * I being swapped in
366 *
367 * init action
368 * assert_wait thread_block clear_wait swapout swapin
369 *
370 * R RW, RWN R; setrun - -
371 * RN RWN RN; setrun - -
372 *
373 * RW W R -
374 * RWN WN RN -
375 *
376 * W R; setrun WO
377 * WN RN; setrun -
378 *
379 * RO - - R
380 *
381 */
382
383 #if defined(CONFIG_SCHED_TRADITIONAL)
384 int8_t sched_load_shifts[NRQS];
385 int sched_preempt_pri[NRQBM];
386 #endif
387
388
389 #if defined(CONFIG_SCHED_TRADITIONAL)
390
391 const struct sched_dispatch_table sched_traditional_dispatch = {
392 sched_traditional_init,
393 sched_traditional_timebase_init,
394 sched_traditional_processor_init,
395 sched_traditional_pset_init,
396 sched_traditional_tick_continue,
397 sched_traditional_choose_thread,
398 steal_thread,
399 compute_priority,
400 choose_processor,
401 processor_enqueue,
402 processor_queue_shutdown,
403 processor_queue_remove,
404 processor_queue_empty,
405 priority_is_urgent,
406 processor_csw_check,
407 processor_queue_has_priority,
408 sched_traditional_initial_quantum_size,
409 sched_traditional_initial_thread_sched_mode,
410 sched_traditional_supports_timeshare_mode,
411 can_update_priority,
412 update_priority,
413 lightweight_update_priority,
414 sched_traditional_quantum_expire,
415 should_current_thread_rechoose_processor,
416 sched_traditional_processor_runq_count,
417 sched_traditional_processor_runq_stats_count_sum,
418 sched_traditional_fairshare_init,
419 sched_traditional_fairshare_runq_count,
420 sched_traditional_fairshare_runq_stats_count_sum,
421 sched_traditional_fairshare_enqueue,
422 sched_traditional_fairshare_dequeue,
423 sched_traditional_fairshare_queue_remove,
424 TRUE /* direct_dispatch_to_idle_processors */
425 };
426
427 const struct sched_dispatch_table sched_traditional_with_pset_runqueue_dispatch = {
428 sched_traditional_with_pset_runqueue_init,
429 sched_traditional_timebase_init,
430 sched_traditional_processor_init,
431 sched_traditional_pset_init,
432 sched_traditional_tick_continue,
433 sched_traditional_choose_thread,
434 steal_thread,
435 compute_priority,
436 choose_processor,
437 processor_enqueue,
438 processor_queue_shutdown,
439 processor_queue_remove,
440 sched_traditional_with_pset_runqueue_processor_queue_empty,
441 priority_is_urgent,
442 processor_csw_check,
443 processor_queue_has_priority,
444 sched_traditional_initial_quantum_size,
445 sched_traditional_initial_thread_sched_mode,
446 sched_traditional_supports_timeshare_mode,
447 can_update_priority,
448 update_priority,
449 lightweight_update_priority,
450 sched_traditional_quantum_expire,
451 should_current_thread_rechoose_processor,
452 sched_traditional_processor_runq_count,
453 sched_traditional_with_pset_runqueue_processor_runq_stats_count_sum,
454 sched_traditional_fairshare_init,
455 sched_traditional_fairshare_runq_count,
456 sched_traditional_fairshare_runq_stats_count_sum,
457 sched_traditional_fairshare_enqueue,
458 sched_traditional_fairshare_dequeue,
459 sched_traditional_fairshare_queue_remove,
460 FALSE /* direct_dispatch_to_idle_processors */
461 };
462
463 #endif
464
465 const struct sched_dispatch_table *sched_current_dispatch = NULL;
466
467 /*
468 * Statically allocate a buffer to hold the longest possible
469 * scheduler description string, as currently implemented.
470 * bsd/kern/kern_sysctl.c has a corresponding definition in bsd/
471 * to export to userspace via sysctl(3). If either version
472 * changes, update the other.
473 *
474 * Note that in addition to being an upper bound on the strings
475 * in the kernel, it's also an exact parameter to PE_get_default(),
476 * which interrogates the device tree on some platforms. That
477 * API requires the caller know the exact size of the device tree
478 * property, so we need both a legacy size (32) and the current size
479 * (48) to deal with old and new device trees. The device tree property
480 * is similarly padded to a fixed size so that the same kernel image
481 * can run on multiple devices with different schedulers configured
482 * in the device tree.
483 */
484 #define SCHED_STRING_MAX_LENGTH (48)
485
486 char sched_string[SCHED_STRING_MAX_LENGTH];
487 static enum sched_enum _sched_enum = sched_enum_unknown;
488
489 void
490 sched_init(void)
491 {
492 char sched_arg[SCHED_STRING_MAX_LENGTH] = { '\0' };
493
494 /* Check for runtime selection of the scheduler algorithm */
495 if (!PE_parse_boot_argn("sched", sched_arg, sizeof (sched_arg))) {
496 /* If no boot-args override, look in device tree */
497 if (!PE_get_default("kern.sched", sched_arg,
498 SCHED_STRING_MAX_LENGTH)) {
499 sched_arg[0] = '\0';
500 }
501 }
502
503 if (strlen(sched_arg) > 0) {
504 if (0) {
505 /* Allow pattern below */
506 #if defined(CONFIG_SCHED_TRADITIONAL)
507 } else if (0 == strcmp(sched_arg, kSchedTraditionalString)) {
508 sched_current_dispatch = &sched_traditional_dispatch;
509 _sched_enum = sched_enum_traditional;
510 strlcpy(sched_string, kSchedTraditionalString, sizeof(sched_string));
511 kprintf("Scheduler: Runtime selection of %s\n", kSchedTraditionalString);
512 } else if (0 == strcmp(sched_arg, kSchedTraditionalWithPsetRunqueueString)) {
513 sched_current_dispatch = &sched_traditional_with_pset_runqueue_dispatch;
514 _sched_enum = sched_enum_traditional_with_pset_runqueue;
515 strlcpy(sched_string, kSchedTraditionalWithPsetRunqueueString, sizeof(sched_string));
516 kprintf("Scheduler: Runtime selection of %s\n", kSchedTraditionalWithPsetRunqueueString);
517 #endif
518 #if defined(CONFIG_SCHED_PROTO)
519 } else if (0 == strcmp(sched_arg, kSchedProtoString)) {
520 sched_current_dispatch = &sched_proto_dispatch;
521 _sched_enum = sched_enum_proto;
522 strlcpy(sched_string, kSchedProtoString, sizeof(sched_string));
523 kprintf("Scheduler: Runtime selection of %s\n", kSchedProtoString);
524 #endif
525 #if defined(CONFIG_SCHED_GRRR)
526 } else if (0 == strcmp(sched_arg, kSchedGRRRString)) {
527 sched_current_dispatch = &sched_grrr_dispatch;
528 _sched_enum = sched_enum_grrr;
529 strlcpy(sched_string, kSchedGRRRString, sizeof(sched_string));
530 kprintf("Scheduler: Runtime selection of %s\n", kSchedGRRRString);
531 #endif
532 #if defined(CONFIG_SCHED_FIXEDPRIORITY)
533 } else if (0 == strcmp(sched_arg, kSchedFixedPriorityString)) {
534 sched_current_dispatch = &sched_fixedpriority_dispatch;
535 _sched_enum = sched_enum_fixedpriority;
536 strlcpy(sched_string, kSchedFixedPriorityString, sizeof(sched_string));
537 kprintf("Scheduler: Runtime selection of %s\n", kSchedFixedPriorityString);
538 } else if (0 == strcmp(sched_arg, kSchedFixedPriorityWithPsetRunqueueString)) {
539 sched_current_dispatch = &sched_fixedpriority_with_pset_runqueue_dispatch;
540 _sched_enum = sched_enum_fixedpriority_with_pset_runqueue;
541 strlcpy(sched_string, kSchedFixedPriorityWithPsetRunqueueString, sizeof(sched_string));
542 kprintf("Scheduler: Runtime selection of %s\n", kSchedFixedPriorityWithPsetRunqueueString);
543 #endif
544 } else {
545 panic("Unrecognized scheduler algorithm: %s", sched_arg);
546 }
547 } else {
548 #if defined(CONFIG_SCHED_TRADITIONAL)
549 sched_current_dispatch = &sched_traditional_dispatch;
550 _sched_enum = sched_enum_traditional;
551 strlcpy(sched_string, kSchedTraditionalString, sizeof(sched_string));
552 kprintf("Scheduler: Default of %s\n", kSchedTraditionalString);
553 #elif defined(CONFIG_SCHED_PROTO)
554 sched_current_dispatch = &sched_proto_dispatch;
555 _sched_enum = sched_enum_proto;
556 strlcpy(sched_string, kSchedProtoString, sizeof(sched_string));
557 kprintf("Scheduler: Default of %s\n", kSchedProtoString);
558 #elif defined(CONFIG_SCHED_GRRR)
559 sched_current_dispatch = &sched_grrr_dispatch;
560 _sched_enum = sched_enum_grrr;
561 strlcpy(sched_string, kSchedGRRRString, sizeof(sched_string));
562 kprintf("Scheduler: Default of %s\n", kSchedGRRRString);
563 #elif defined(CONFIG_SCHED_FIXEDPRIORITY)
564 sched_current_dispatch = &sched_fixedpriority_dispatch;
565 _sched_enum = sched_enum_fixedpriority;
566 strlcpy(sched_string, kSchedFixedPriorityString, sizeof(sched_string));
567 kprintf("Scheduler: Default of %s\n", kSchedFixedPriorityString);
568 #else
569 #error No default scheduler implementation
570 #endif
571 }
572
573 SCHED(init)();
574 SCHED(fairshare_init)();
575 sched_realtime_init();
576 ast_init();
577 sched_timer_deadline_tracking_init();
578
579 SCHED(pset_init)(&pset0);
580 SCHED(processor_init)(master_processor);
581 }
582
583 void
584 sched_timebase_init(void)
585 {
586 uint64_t abstime;
587
588 clock_interval_to_absolutetime_interval(1, NSEC_PER_SEC, &abstime);
589 sched_one_second_interval = abstime;
590
591 SCHED(timebase_init)();
592 sched_realtime_timebase_init();
593 }
594
595 #if defined(CONFIG_SCHED_TRADITIONAL)
596
597 static void
598 sched_traditional_init(void)
599 {
600 /*
601 * Calculate the timeslicing quantum
602 * in us.
603 */
604 if (default_preemption_rate < 1)
605 default_preemption_rate = DEFAULT_PREEMPTION_RATE;
606 std_quantum_us = (1000 * 1000) / default_preemption_rate;
607
608 printf("standard timeslicing quantum is %d us\n", std_quantum_us);
609
610 if (default_bg_preemption_rate < 1)
611 default_bg_preemption_rate = DEFAULT_BG_PREEMPTION_RATE;
612 bg_quantum_us = (1000 * 1000) / default_bg_preemption_rate;
613
614 printf("standard background quantum is %d us\n", bg_quantum_us);
615
616 load_shift_init();
617 preempt_pri_init();
618 sched_tick = 0;
619 }
620
621 static void
622 sched_traditional_timebase_init(void)
623 {
624 uint64_t abstime;
625 uint32_t shift;
626
627 /* standard timeslicing quantum */
628 clock_interval_to_absolutetime_interval(
629 std_quantum_us, NSEC_PER_USEC, &abstime);
630 assert((abstime >> 32) == 0 && (uint32_t)abstime != 0);
631 std_quantum = (uint32_t)abstime;
632
633 /* smallest remaining quantum (250 us) */
634 clock_interval_to_absolutetime_interval(250, NSEC_PER_USEC, &abstime);
635 assert((abstime >> 32) == 0 && (uint32_t)abstime != 0);
636 min_std_quantum = (uint32_t)abstime;
637
638 /* quantum for background tasks */
639 clock_interval_to_absolutetime_interval(
640 bg_quantum_us, NSEC_PER_USEC, &abstime);
641 assert((abstime >> 32) == 0 && (uint32_t)abstime != 0);
642 bg_quantum = (uint32_t)abstime;
643
644 /* scheduler tick interval */
645 clock_interval_to_absolutetime_interval(USEC_PER_SEC >> SCHED_TICK_SHIFT,
646 NSEC_PER_USEC, &abstime);
647 assert((abstime >> 32) == 0 && (uint32_t)abstime != 0);
648 sched_tick_interval = (uint32_t)abstime;
649
650 /*
651 * Compute conversion factor from usage to
652 * timesharing priorities with 5/8 ** n aging.
653 */
654 abstime = (abstime * 5) / 3;
655 for (shift = 0; abstime > BASEPRI_DEFAULT; ++shift)
656 abstime >>= 1;
657 sched_fixed_shift = shift;
658
659 max_unsafe_computation = max_unsafe_quanta * std_quantum;
660 sched_safe_duration = 2 * max_unsafe_quanta * std_quantum;
661
662 max_poll_computation = max_poll_quanta * std_quantum;
663 thread_depress_time = 1 * std_quantum;
664 default_timeshare_computation = std_quantum / 2;
665 default_timeshare_constraint = std_quantum;
666
667 }
668
669 static void
670 sched_traditional_processor_init(processor_t processor)
671 {
672 if (!sched_traditional_use_pset_runqueue) {
673 run_queue_init(&processor->runq);
674 }
675 processor->runq_bound_count = 0;
676 }
677
678 static void
679 sched_traditional_pset_init(processor_set_t pset)
680 {
681 if (sched_traditional_use_pset_runqueue) {
682 run_queue_init(&pset->pset_runq);
683 }
684 pset->pset_runq_bound_count = 0;
685 }
686
687 static void
688 sched_traditional_with_pset_runqueue_init(void)
689 {
690 sched_traditional_init();
691 sched_traditional_use_pset_runqueue = TRUE;
692 }
693
694 #endif /* CONFIG_SCHED_TRADITIONAL */
695
696 #if defined(CONFIG_SCHED_TRADITIONAL) || defined(CONFIG_SCHED_PROTO) || defined(CONFIG_SCHED_GRRR) || defined(CONFIG_SCHED_FIXEDPRIORITY)
697 void
698 sched_traditional_fairshare_init(void)
699 {
700 simple_lock_init(&fs_lock, 0);
701
702 fs_runq.count = 0;
703 queue_init(&fs_runq.queue);
704 }
705 #endif
706
707 static void
708 sched_realtime_init(void)
709 {
710 simple_lock_init(&rt_lock, 0);
711
712 rt_runq.count = 0;
713 queue_init(&rt_runq.queue);
714 }
715
716 static void
717 sched_realtime_timebase_init(void)
718 {
719 uint64_t abstime;
720
721 /* smallest rt computaton (50 us) */
722 clock_interval_to_absolutetime_interval(50, NSEC_PER_USEC, &abstime);
723 assert((abstime >> 32) == 0 && (uint32_t)abstime != 0);
724 min_rt_quantum = (uint32_t)abstime;
725
726 /* maximum rt computation (50 ms) */
727 clock_interval_to_absolutetime_interval(
728 50, 1000*NSEC_PER_USEC, &abstime);
729 assert((abstime >> 32) == 0 && (uint32_t)abstime != 0);
730 max_rt_quantum = (uint32_t)abstime;
731
732 }
733
734 #if defined(CONFIG_SCHED_TRADITIONAL)
735
736 /*
737 * Set up values for timeshare
738 * loading factors.
739 */
740 static void
741 load_shift_init(void)
742 {
743 int8_t k, *p = sched_load_shifts;
744 uint32_t i, j;
745
746 *p++ = INT8_MIN; *p++ = 0;
747
748 for (i = j = 2, k = 1; i < NRQS; ++k) {
749 for (j <<= 1; i < j; ++i)
750 *p++ = k;
751 }
752 }
753
754 static void
755 preempt_pri_init(void)
756 {
757 int i, *p = sched_preempt_pri;
758
759 for (i = BASEPRI_FOREGROUND + 1; i < MINPRI_KERNEL; ++i)
760 setbit(i, p);
761
762 for (i = BASEPRI_PREEMPT; i <= MAXPRI; ++i)
763 setbit(i, p);
764 }
765
766 #endif /* CONFIG_SCHED_TRADITIONAL */
767
768 /*
769 * Thread wait timer expiration.
770 */
771 void
772 thread_timer_expire(
773 void *p0,
774 __unused void *p1)
775 {
776 thread_t thread = p0;
777 spl_t s;
778
779 s = splsched();
780 thread_lock(thread);
781 if (--thread->wait_timer_active == 0) {
782 if (thread->wait_timer_is_set) {
783 thread->wait_timer_is_set = FALSE;
784 clear_wait_internal(thread, THREAD_TIMED_OUT);
785 }
786 }
787 thread_unlock(thread);
788 splx(s);
789 }
790
791 #ifndef __LP64__
792
793 /*
794 * thread_set_timer:
795 *
796 * Set a timer for the current thread, if the thread
797 * is ready to wait. Must be called between assert_wait()
798 * and thread_block().
799 */
800 void
801 thread_set_timer(
802 uint32_t interval,
803 uint32_t scale_factor)
804 {
805 thread_t thread = current_thread();
806 uint64_t deadline;
807 spl_t s;
808
809 s = splsched();
810 thread_lock(thread);
811 if ((thread->state & TH_WAIT) != 0) {
812 clock_interval_to_deadline(interval, scale_factor, &deadline);
813 if (!timer_call_enter(&thread->wait_timer, deadline, thread->sched_pri >= BASEPRI_RTQUEUES ? TIMER_CALL_CRITICAL : 0))
814 thread->wait_timer_active++;
815 thread->wait_timer_is_set = TRUE;
816 }
817 thread_unlock(thread);
818 splx(s);
819 }
820
821 void
822 thread_set_timer_deadline(
823 uint64_t deadline)
824 {
825 thread_t thread = current_thread();
826 spl_t s;
827
828 s = splsched();
829 thread_lock(thread);
830 if ((thread->state & TH_WAIT) != 0) {
831 if (!timer_call_enter(&thread->wait_timer, deadline, thread->sched_pri >= BASEPRI_RTQUEUES ? TIMER_CALL_CRITICAL : 0))
832 thread->wait_timer_active++;
833 thread->wait_timer_is_set = TRUE;
834 }
835 thread_unlock(thread);
836 splx(s);
837 }
838
839 void
840 thread_cancel_timer(void)
841 {
842 thread_t thread = current_thread();
843 spl_t s;
844
845 s = splsched();
846 thread_lock(thread);
847 if (thread->wait_timer_is_set) {
848 if (timer_call_cancel(&thread->wait_timer))
849 thread->wait_timer_active--;
850 thread->wait_timer_is_set = FALSE;
851 }
852 thread_unlock(thread);
853 splx(s);
854 }
855
856 #endif /* __LP64__ */
857
858 /*
859 * thread_unblock:
860 *
861 * Unblock thread on wake up.
862 *
863 * Returns TRUE if the thread is still running.
864 *
865 * Thread must be locked.
866 */
867 boolean_t
868 thread_unblock(
869 thread_t thread,
870 wait_result_t wresult)
871 {
872 boolean_t result = FALSE;
873 thread_t cthread = current_thread();
874
875 /*
876 * Set wait_result.
877 */
878 thread->wait_result = wresult;
879
880 /*
881 * Cancel pending wait timer.
882 */
883 if (thread->wait_timer_is_set) {
884 if (timer_call_cancel(&thread->wait_timer))
885 thread->wait_timer_active--;
886 thread->wait_timer_is_set = FALSE;
887 }
888
889 /*
890 * Update scheduling state: not waiting,
891 * set running.
892 */
893 thread->state &= ~(TH_WAIT|TH_UNINT);
894
895 if (!(thread->state & TH_RUN)) {
896 thread->state |= TH_RUN;
897
898 (*thread->sched_call)(SCHED_CALL_UNBLOCK, thread);
899
900 /*
901 * Update run counts.
902 */
903 sched_run_incr();
904 if (thread->sched_mode == TH_MODE_TIMESHARE)
905 sched_share_incr();
906 }
907 else {
908 /*
909 * Signal if idling on another processor.
910 */
911 #if CONFIG_SCHED_IDLE_IN_PLACE
912 if (thread->state & TH_IDLE) {
913 processor_t processor = thread->last_processor;
914
915 if (processor != current_processor())
916 machine_signal_idle(processor);
917 }
918 #else
919 assert((thread->state & TH_IDLE) == 0);
920 #endif
921
922 result = TRUE;
923 }
924
925 /*
926 * Calculate deadline for real-time threads.
927 */
928 if (thread->sched_mode == TH_MODE_REALTIME) {
929 thread->realtime.deadline = mach_absolute_time();
930 thread->realtime.deadline += thread->realtime.constraint;
931 }
932
933 /*
934 * Clear old quantum, fail-safe computation, etc.
935 */
936 thread->current_quantum = 0;
937 thread->computation_metered = 0;
938 thread->reason = AST_NONE;
939
940 /* Obtain power-relevant interrupt and "platform-idle exit" statistics.
941 * We also account for "double hop" thread signaling via
942 * the thread callout infrastructure.
943 * DRK: consider removing the callout wakeup counters in the future
944 * they're present for verification at the moment.
945 */
946 boolean_t aticontext, pidle;
947 ml_get_power_state(&aticontext, &pidle);
948 if (__improbable(aticontext)) {
949 ledger_credit(thread->t_ledger, task_ledgers.interrupt_wakeups, 1);
950 uint64_t ttd = PROCESSOR_DATA(current_processor(), timer_call_ttd);
951 if (ttd) {
952 if (ttd <= timer_deadline_tracking_bin_1)
953 thread->thread_timer_wakeups_bin_1++;
954 else
955 if (ttd <= timer_deadline_tracking_bin_2)
956 thread->thread_timer_wakeups_bin_2++;
957 }
958 if (pidle) {
959 ledger_credit(thread->t_ledger, task_ledgers.platform_idle_wakeups, 1);
960 }
961 } else if (thread_get_tag_internal(cthread) & THREAD_TAG_CALLOUT) {
962 if (cthread->callout_woken_from_icontext) {
963 ledger_credit(thread->t_ledger, task_ledgers.interrupt_wakeups, 1);
964 thread->thread_callout_interrupt_wakeups++;
965 if (cthread->callout_woken_from_platform_idle) {
966 ledger_credit(thread->t_ledger, task_ledgers.platform_idle_wakeups, 1);
967 thread->thread_callout_platform_idle_wakeups++;
968 }
969 }
970 }
971
972 if (thread_get_tag_internal(thread) & THREAD_TAG_CALLOUT) {
973 thread->callout_woken_from_icontext = aticontext;
974 thread->callout_woken_from_platform_idle = pidle;
975 }
976
977 /* Event should only be triggered if thread is not already running */
978 if (result == FALSE) {
979 KERNEL_DEBUG_CONSTANT_IST(KDEBUG_TRACE,
980 MACHDBG_CODE(DBG_MACH_SCHED,MACH_MAKE_RUNNABLE) | DBG_FUNC_NONE,
981 (uintptr_t)thread_tid(thread), thread->sched_pri, thread->wait_result, 0, 0);
982 }
983
984 DTRACE_SCHED2(wakeup, struct thread *, thread, struct proc *, thread->task->bsd_info);
985
986 return (result);
987 }
988
989 /*
990 * Routine: thread_go
991 * Purpose:
992 * Unblock and dispatch thread.
993 * Conditions:
994 * thread lock held, IPC locks may be held.
995 * thread must have been pulled from wait queue under same lock hold.
996 * Returns:
997 * KERN_SUCCESS - Thread was set running
998 * KERN_NOT_WAITING - Thread was not waiting
999 */
1000 kern_return_t
1001 thread_go(
1002 thread_t thread,
1003 wait_result_t wresult)
1004 {
1005 assert(thread->at_safe_point == FALSE);
1006 assert(thread->wait_event == NO_EVENT64);
1007 assert(thread->wait_queue == WAIT_QUEUE_NULL);
1008
1009 if ((thread->state & (TH_WAIT|TH_TERMINATE)) == TH_WAIT) {
1010 if (!thread_unblock(thread, wresult))
1011 thread_setrun(thread, SCHED_PREEMPT | SCHED_TAILQ);
1012
1013 return (KERN_SUCCESS);
1014 }
1015
1016 return (KERN_NOT_WAITING);
1017 }
1018
1019 /*
1020 * Routine: thread_mark_wait_locked
1021 * Purpose:
1022 * Mark a thread as waiting. If, given the circumstances,
1023 * it doesn't want to wait (i.e. already aborted), then
1024 * indicate that in the return value.
1025 * Conditions:
1026 * at splsched() and thread is locked.
1027 */
1028 __private_extern__
1029 wait_result_t
1030 thread_mark_wait_locked(
1031 thread_t thread,
1032 wait_interrupt_t interruptible)
1033 {
1034 boolean_t at_safe_point;
1035
1036 assert(thread == current_thread());
1037
1038 /*
1039 * The thread may have certain types of interrupts/aborts masked
1040 * off. Even if the wait location says these types of interrupts
1041 * are OK, we have to honor mask settings (outer-scoped code may
1042 * not be able to handle aborts at the moment).
1043 */
1044 if (interruptible > (thread->options & TH_OPT_INTMASK))
1045 interruptible = thread->options & TH_OPT_INTMASK;
1046
1047 at_safe_point = (interruptible == THREAD_ABORTSAFE);
1048
1049 if ( interruptible == THREAD_UNINT ||
1050 !(thread->sched_flags & TH_SFLAG_ABORT) ||
1051 (!at_safe_point &&
1052 (thread->sched_flags & TH_SFLAG_ABORTSAFELY))) {
1053
1054 if ( !(thread->state & TH_TERMINATE))
1055 DTRACE_SCHED(sleep);
1056
1057 thread->state |= (interruptible) ? TH_WAIT : (TH_WAIT | TH_UNINT);
1058 thread->at_safe_point = at_safe_point;
1059 return (thread->wait_result = THREAD_WAITING);
1060 }
1061 else
1062 if (thread->sched_flags & TH_SFLAG_ABORTSAFELY)
1063 thread->sched_flags &= ~TH_SFLAG_ABORTED_MASK;
1064
1065 return (thread->wait_result = THREAD_INTERRUPTED);
1066 }
1067
1068 /*
1069 * Routine: thread_interrupt_level
1070 * Purpose:
1071 * Set the maximum interruptible state for the
1072 * current thread. The effective value of any
1073 * interruptible flag passed into assert_wait
1074 * will never exceed this.
1075 *
1076 * Useful for code that must not be interrupted,
1077 * but which calls code that doesn't know that.
1078 * Returns:
1079 * The old interrupt level for the thread.
1080 */
1081 __private_extern__
1082 wait_interrupt_t
1083 thread_interrupt_level(
1084 wait_interrupt_t new_level)
1085 {
1086 thread_t thread = current_thread();
1087 wait_interrupt_t result = thread->options & TH_OPT_INTMASK;
1088
1089 thread->options = (thread->options & ~TH_OPT_INTMASK) | (new_level & TH_OPT_INTMASK);
1090
1091 return result;
1092 }
1093
1094 /*
1095 * Check to see if an assert wait is possible, without actually doing one.
1096 * This is used by debug code in locks and elsewhere to verify that it is
1097 * always OK to block when trying to take a blocking lock (since waiting
1098 * for the actual assert_wait to catch the case may make it hard to detect
1099 * this case.
1100 */
1101 boolean_t
1102 assert_wait_possible(void)
1103 {
1104
1105 thread_t thread;
1106
1107 #if DEBUG
1108 if(debug_mode) return TRUE; /* Always succeed in debug mode */
1109 #endif
1110
1111 thread = current_thread();
1112
1113 return (thread == NULL || wait_queue_assert_possible(thread));
1114 }
1115
1116 /*
1117 * assert_wait:
1118 *
1119 * Assert that the current thread is about to go to
1120 * sleep until the specified event occurs.
1121 */
1122 wait_result_t
1123 assert_wait(
1124 event_t event,
1125 wait_interrupt_t interruptible)
1126 {
1127 register wait_queue_t wq;
1128 register int index;
1129
1130 assert(event != NO_EVENT);
1131
1132 KERNEL_DEBUG_CONSTANT_IST(KDEBUG_TRACE,
1133 MACHDBG_CODE(DBG_MACH_SCHED, MACH_WAIT)|DBG_FUNC_NONE,
1134 VM_KERNEL_UNSLIDE(event), 0, 0, 0, 0);
1135
1136 index = wait_hash(event);
1137 wq = &wait_queues[index];
1138 return wait_queue_assert_wait(wq, event, interruptible, 0);
1139 }
1140
1141 wait_result_t
1142 assert_wait_timeout(
1143 event_t event,
1144 wait_interrupt_t interruptible,
1145 uint32_t interval,
1146 uint32_t scale_factor)
1147 {
1148 thread_t thread = current_thread();
1149 wait_result_t wresult;
1150 wait_queue_t wqueue;
1151 uint64_t deadline;
1152 spl_t s;
1153
1154 assert(event != NO_EVENT);
1155 wqueue = &wait_queues[wait_hash(event)];
1156
1157 s = splsched();
1158 wait_queue_lock(wqueue);
1159 thread_lock(thread);
1160
1161 clock_interval_to_deadline(interval, scale_factor, &deadline);
1162
1163 KERNEL_DEBUG_CONSTANT_IST(KDEBUG_TRACE,
1164 MACHDBG_CODE(DBG_MACH_SCHED, MACH_WAIT)|DBG_FUNC_NONE,
1165 VM_KERNEL_UNSLIDE(event), interruptible, deadline, 0, 0);
1166
1167 wresult = wait_queue_assert_wait64_locked(wqueue, CAST_DOWN(event64_t, event),
1168 interruptible, deadline, thread);
1169
1170 thread_unlock(thread);
1171 wait_queue_unlock(wqueue);
1172 splx(s);
1173
1174 return (wresult);
1175 }
1176
1177 wait_result_t
1178 assert_wait_deadline(
1179 event_t event,
1180 wait_interrupt_t interruptible,
1181 uint64_t deadline)
1182 {
1183 thread_t thread = current_thread();
1184 wait_result_t wresult;
1185 wait_queue_t wqueue;
1186 spl_t s;
1187
1188 assert(event != NO_EVENT);
1189 wqueue = &wait_queues[wait_hash(event)];
1190
1191 s = splsched();
1192 wait_queue_lock(wqueue);
1193 thread_lock(thread);
1194
1195 KERNEL_DEBUG_CONSTANT_IST(KDEBUG_TRACE,
1196 MACHDBG_CODE(DBG_MACH_SCHED, MACH_WAIT)|DBG_FUNC_NONE,
1197 VM_KERNEL_UNSLIDE(event), interruptible, deadline, 0, 0);
1198
1199 wresult = wait_queue_assert_wait64_locked(wqueue, CAST_DOWN(event64_t,event),
1200 interruptible, deadline, thread);
1201
1202 thread_unlock(thread);
1203 wait_queue_unlock(wqueue);
1204 splx(s);
1205
1206 return (wresult);
1207 }
1208
1209 /*
1210 * thread_sleep_fast_usimple_lock:
1211 *
1212 * Cause the current thread to wait until the specified event
1213 * occurs. The specified simple_lock is unlocked before releasing
1214 * the cpu and re-acquired as part of waking up.
1215 *
1216 * This is the simple lock sleep interface for components that use a
1217 * faster version of simple_lock() than is provided by usimple_lock().
1218 */
1219 __private_extern__ wait_result_t
1220 thread_sleep_fast_usimple_lock(
1221 event_t event,
1222 simple_lock_t lock,
1223 wait_interrupt_t interruptible)
1224 {
1225 wait_result_t res;
1226
1227 res = assert_wait(event, interruptible);
1228 if (res == THREAD_WAITING) {
1229 simple_unlock(lock);
1230 res = thread_block(THREAD_CONTINUE_NULL);
1231 simple_lock(lock);
1232 }
1233 return res;
1234 }
1235
1236
1237 /*
1238 * thread_sleep_usimple_lock:
1239 *
1240 * Cause the current thread to wait until the specified event
1241 * occurs. The specified usimple_lock is unlocked before releasing
1242 * the cpu and re-acquired as part of waking up.
1243 *
1244 * This is the simple lock sleep interface for components where
1245 * simple_lock() is defined in terms of usimple_lock().
1246 */
1247 wait_result_t
1248 thread_sleep_usimple_lock(
1249 event_t event,
1250 usimple_lock_t lock,
1251 wait_interrupt_t interruptible)
1252 {
1253 wait_result_t res;
1254
1255 res = assert_wait(event, interruptible);
1256 if (res == THREAD_WAITING) {
1257 usimple_unlock(lock);
1258 res = thread_block(THREAD_CONTINUE_NULL);
1259 usimple_lock(lock);
1260 }
1261 return res;
1262 }
1263
1264 /*
1265 * thread_sleep_lock_write:
1266 *
1267 * Cause the current thread to wait until the specified event
1268 * occurs. The specified (write) lock is unlocked before releasing
1269 * the cpu. The (write) lock will be re-acquired before returning.
1270 */
1271 wait_result_t
1272 thread_sleep_lock_write(
1273 event_t event,
1274 lock_t *lock,
1275 wait_interrupt_t interruptible)
1276 {
1277 wait_result_t res;
1278
1279 res = assert_wait(event, interruptible);
1280 if (res == THREAD_WAITING) {
1281 lock_write_done(lock);
1282 res = thread_block(THREAD_CONTINUE_NULL);
1283 lock_write(lock);
1284 }
1285 return res;
1286 }
1287
1288 /*
1289 * thread_stop:
1290 *
1291 * Force a preemption point for a thread and wait
1292 * for it to stop running. Arbitrates access among
1293 * multiple stop requests. (released by unstop)
1294 *
1295 * The thread must enter a wait state and stop via a
1296 * separate means.
1297 *
1298 * Returns FALSE if interrupted.
1299 */
1300 boolean_t
1301 thread_stop(
1302 thread_t thread)
1303 {
1304 wait_result_t wresult;
1305 spl_t s = splsched();
1306
1307 wake_lock(thread);
1308 thread_lock(thread);
1309
1310 while (thread->state & TH_SUSP) {
1311 thread->wake_active = TRUE;
1312 thread_unlock(thread);
1313
1314 wresult = assert_wait(&thread->wake_active, THREAD_ABORTSAFE);
1315 wake_unlock(thread);
1316 splx(s);
1317
1318 if (wresult == THREAD_WAITING)
1319 wresult = thread_block(THREAD_CONTINUE_NULL);
1320
1321 if (wresult != THREAD_AWAKENED)
1322 return (FALSE);
1323
1324 s = splsched();
1325 wake_lock(thread);
1326 thread_lock(thread);
1327 }
1328
1329 thread->state |= TH_SUSP;
1330
1331 while (thread->state & TH_RUN) {
1332 processor_t processor = thread->last_processor;
1333
1334 if (processor != PROCESSOR_NULL && processor->active_thread == thread)
1335 cause_ast_check(processor);
1336
1337 thread->wake_active = TRUE;
1338 thread_unlock(thread);
1339
1340 wresult = assert_wait(&thread->wake_active, THREAD_ABORTSAFE);
1341 wake_unlock(thread);
1342 splx(s);
1343
1344 if (wresult == THREAD_WAITING)
1345 wresult = thread_block(THREAD_CONTINUE_NULL);
1346
1347 if (wresult != THREAD_AWAKENED) {
1348 thread_unstop(thread);
1349 return (FALSE);
1350 }
1351
1352 s = splsched();
1353 wake_lock(thread);
1354 thread_lock(thread);
1355 }
1356
1357 thread_unlock(thread);
1358 wake_unlock(thread);
1359 splx(s);
1360
1361 return (TRUE);
1362 }
1363
1364 /*
1365 * thread_unstop:
1366 *
1367 * Release a previous stop request and set
1368 * the thread running if appropriate.
1369 *
1370 * Use only after a successful stop operation.
1371 */
1372 void
1373 thread_unstop(
1374 thread_t thread)
1375 {
1376 spl_t s = splsched();
1377
1378 wake_lock(thread);
1379 thread_lock(thread);
1380
1381 if ((thread->state & (TH_RUN|TH_WAIT|TH_SUSP)) == TH_SUSP) {
1382 thread->state &= ~TH_SUSP;
1383 thread_unblock(thread, THREAD_AWAKENED);
1384
1385 thread_setrun(thread, SCHED_PREEMPT | SCHED_TAILQ);
1386 }
1387 else
1388 if (thread->state & TH_SUSP) {
1389 thread->state &= ~TH_SUSP;
1390
1391 if (thread->wake_active) {
1392 thread->wake_active = FALSE;
1393 thread_unlock(thread);
1394
1395 thread_wakeup(&thread->wake_active);
1396 wake_unlock(thread);
1397 splx(s);
1398
1399 return;
1400 }
1401 }
1402
1403 thread_unlock(thread);
1404 wake_unlock(thread);
1405 splx(s);
1406 }
1407
1408 /*
1409 * Thread locked, returns the same way
1410 */
1411 static inline boolean_t
1412 thread_isoncpu(thread_t thread)
1413 {
1414 processor_t processor = thread->last_processor;
1415
1416 return ((processor != PROCESSOR_NULL) && (processor->active_thread == thread));
1417 }
1418 /*
1419 * thread_wait:
1420 *
1421 * Wait for a thread to stop running. (non-interruptible)
1422 *
1423 */
1424 void
1425 thread_wait(
1426 thread_t thread,
1427 boolean_t until_not_runnable)
1428 {
1429 wait_result_t wresult;
1430 boolean_t oncpu;
1431 processor_t processor;
1432 spl_t s = splsched();
1433
1434 wake_lock(thread);
1435 thread_lock(thread);
1436
1437 /*
1438 * Wait until not running on a CPU. If stronger requirement
1439 * desired, wait until not runnable. Assumption: if thread is
1440 * on CPU, then TH_RUN is set, so we're not waiting in any case
1441 * where the original, pure "TH_RUN" check would have let us
1442 * finish.
1443 */
1444 while ((oncpu = thread_isoncpu(thread)) ||
1445 (until_not_runnable && (thread->state & TH_RUN))) {
1446
1447 if (oncpu) {
1448 assert(thread->state & TH_RUN);
1449 processor = thread->last_processor;
1450 cause_ast_check(processor);
1451 }
1452
1453 thread->wake_active = TRUE;
1454 thread_unlock(thread);
1455
1456 wresult = assert_wait(&thread->wake_active, THREAD_UNINT);
1457 wake_unlock(thread);
1458 splx(s);
1459
1460 if (wresult == THREAD_WAITING)
1461 thread_block(THREAD_CONTINUE_NULL);
1462
1463 s = splsched();
1464 wake_lock(thread);
1465 thread_lock(thread);
1466 }
1467
1468 thread_unlock(thread);
1469 wake_unlock(thread);
1470 splx(s);
1471 }
1472
1473 /*
1474 * Routine: clear_wait_internal
1475 *
1476 * Clear the wait condition for the specified thread.
1477 * Start the thread executing if that is appropriate.
1478 * Arguments:
1479 * thread thread to awaken
1480 * result Wakeup result the thread should see
1481 * Conditions:
1482 * At splsched
1483 * the thread is locked.
1484 * Returns:
1485 * KERN_SUCCESS thread was rousted out a wait
1486 * KERN_FAILURE thread was waiting but could not be rousted
1487 * KERN_NOT_WAITING thread was not waiting
1488 */
1489 __private_extern__ kern_return_t
1490 clear_wait_internal(
1491 thread_t thread,
1492 wait_result_t wresult)
1493 {
1494 wait_queue_t wq = thread->wait_queue;
1495 uint32_t i = LockTimeOut;
1496
1497 do {
1498 if (wresult == THREAD_INTERRUPTED && (thread->state & TH_UNINT))
1499 return (KERN_FAILURE);
1500
1501 if (wq != WAIT_QUEUE_NULL) {
1502 if (wait_queue_lock_try(wq)) {
1503 wait_queue_pull_thread_locked(wq, thread, TRUE);
1504 /* wait queue unlocked, thread still locked */
1505 }
1506 else {
1507 thread_unlock(thread);
1508 delay(1);
1509
1510 thread_lock(thread);
1511 if (wq != thread->wait_queue)
1512 return (KERN_NOT_WAITING);
1513
1514 continue;
1515 }
1516 }
1517
1518 return (thread_go(thread, wresult));
1519 } while ((--i > 0) || machine_timeout_suspended());
1520
1521 panic("clear_wait_internal: deadlock: thread=%p, wq=%p, cpu=%d\n",
1522 thread, wq, cpu_number());
1523
1524 return (KERN_FAILURE);
1525 }
1526
1527
1528 /*
1529 * clear_wait:
1530 *
1531 * Clear the wait condition for the specified thread. Start the thread
1532 * executing if that is appropriate.
1533 *
1534 * parameters:
1535 * thread thread to awaken
1536 * result Wakeup result the thread should see
1537 */
1538 kern_return_t
1539 clear_wait(
1540 thread_t thread,
1541 wait_result_t result)
1542 {
1543 kern_return_t ret;
1544 spl_t s;
1545
1546 s = splsched();
1547 thread_lock(thread);
1548 ret = clear_wait_internal(thread, result);
1549 thread_unlock(thread);
1550 splx(s);
1551 return ret;
1552 }
1553
1554
1555 /*
1556 * thread_wakeup_prim:
1557 *
1558 * Common routine for thread_wakeup, thread_wakeup_with_result,
1559 * and thread_wakeup_one.
1560 *
1561 */
1562 kern_return_t
1563 thread_wakeup_prim(
1564 event_t event,
1565 boolean_t one_thread,
1566 wait_result_t result)
1567 {
1568 return (thread_wakeup_prim_internal(event, one_thread, result, -1));
1569 }
1570
1571
1572 kern_return_t
1573 thread_wakeup_prim_internal(
1574 event_t event,
1575 boolean_t one_thread,
1576 wait_result_t result,
1577 int priority)
1578 {
1579 register wait_queue_t wq;
1580 register int index;
1581
1582 index = wait_hash(event);
1583 wq = &wait_queues[index];
1584 if (one_thread)
1585 return (wait_queue_wakeup_one(wq, event, result, priority));
1586 else
1587 return (wait_queue_wakeup_all(wq, event, result));
1588 }
1589
1590 /*
1591 * thread_bind:
1592 *
1593 * Force the current thread to execute on the specified processor.
1594 *
1595 * Returns the previous binding. PROCESSOR_NULL means
1596 * not bound.
1597 *
1598 * XXX - DO NOT export this to users - XXX
1599 */
1600 processor_t
1601 thread_bind(
1602 processor_t processor)
1603 {
1604 thread_t self = current_thread();
1605 processor_t prev;
1606 spl_t s;
1607
1608 s = splsched();
1609 thread_lock(self);
1610
1611 prev = self->bound_processor;
1612 self->bound_processor = processor;
1613
1614 thread_unlock(self);
1615 splx(s);
1616
1617 return (prev);
1618 }
1619
1620 /*
1621 * thread_select:
1622 *
1623 * Select a new thread for the current processor to execute.
1624 *
1625 * May select the current thread, which must be locked.
1626 */
1627 static thread_t
1628 thread_select(
1629 thread_t thread,
1630 processor_t processor)
1631 {
1632 processor_set_t pset = processor->processor_set;
1633 thread_t new_thread = THREAD_NULL;
1634 boolean_t inactive_state;
1635
1636 assert(processor == current_processor());
1637
1638 do {
1639 /*
1640 * Update the priority.
1641 */
1642 if (SCHED(can_update_priority)(thread))
1643 SCHED(update_priority)(thread);
1644
1645 processor->current_pri = thread->sched_pri;
1646 processor->current_thmode = thread->sched_mode;
1647
1648 pset_lock(pset);
1649
1650 assert(pset->low_count);
1651 assert(pset->low_pri);
1652
1653 inactive_state = processor->state != PROCESSOR_SHUTDOWN && machine_processor_is_inactive(processor);
1654
1655 simple_lock(&rt_lock);
1656
1657 /*
1658 * Test to see if the current thread should continue
1659 * to run on this processor. Must be runnable, and not
1660 * bound to a different processor, nor be in the wrong
1661 * processor set.
1662 */
1663 if ( ((thread->state & ~TH_SUSP) == TH_RUN) &&
1664 (thread->sched_pri >= BASEPRI_RTQUEUES ||
1665 processor->processor_meta == PROCESSOR_META_NULL ||
1666 processor->processor_meta->primary == processor) &&
1667 (thread->bound_processor == PROCESSOR_NULL ||
1668 thread->bound_processor == processor) &&
1669 (thread->affinity_set == AFFINITY_SET_NULL ||
1670 thread->affinity_set->aset_pset == pset) ) {
1671 if ( thread->sched_pri >= BASEPRI_RTQUEUES &&
1672 first_timeslice(processor) ) {
1673 if (rt_runq.count > 0) {
1674 register queue_t q;
1675
1676 q = &rt_runq.queue;
1677 if (((thread_t)q->next)->realtime.deadline <
1678 processor->deadline) {
1679 thread = (thread_t)dequeue_head(q);
1680 thread->runq = PROCESSOR_NULL;
1681 SCHED_STATS_RUNQ_CHANGE(&rt_runq.runq_stats, rt_runq.count);
1682 rt_runq.count--;
1683 }
1684 }
1685
1686 simple_unlock(&rt_lock);
1687
1688 processor->deadline = thread->realtime.deadline;
1689
1690 pset_unlock(pset);
1691
1692 return (thread);
1693 }
1694
1695 if (!inactive_state && (thread->sched_mode != TH_MODE_FAIRSHARE || SCHED(fairshare_runq_count)() == 0) && (rt_runq.count == 0 || BASEPRI_RTQUEUES < thread->sched_pri) &&
1696 (new_thread = SCHED(choose_thread)(processor, thread->sched_mode == TH_MODE_FAIRSHARE ? MINPRI : thread->sched_pri)) == THREAD_NULL) {
1697
1698 simple_unlock(&rt_lock);
1699
1700 /* I am the highest priority runnable (non-idle) thread */
1701
1702 pset_pri_hint(pset, processor, processor->current_pri);
1703
1704 pset_count_hint(pset, processor, SCHED(processor_runq_count)(processor));
1705
1706 processor->deadline = UINT64_MAX;
1707
1708 pset_unlock(pset);
1709
1710 return (thread);
1711 }
1712 }
1713
1714 if (new_thread != THREAD_NULL ||
1715 (SCHED(processor_queue_has_priority)(processor, rt_runq.count == 0 ? IDLEPRI : BASEPRI_RTQUEUES, TRUE) &&
1716 (new_thread = SCHED(choose_thread)(processor, MINPRI)) != THREAD_NULL)) {
1717 simple_unlock(&rt_lock);
1718
1719 if (!inactive_state) {
1720 pset_pri_hint(pset, processor, new_thread->sched_pri);
1721
1722 pset_count_hint(pset, processor, SCHED(processor_runq_count)(processor));
1723 }
1724
1725 processor->deadline = UINT64_MAX;
1726 pset_unlock(pset);
1727
1728 return (new_thread);
1729 }
1730
1731 if (rt_runq.count > 0) {
1732 thread = (thread_t)dequeue_head(&rt_runq.queue);
1733
1734 thread->runq = PROCESSOR_NULL;
1735 SCHED_STATS_RUNQ_CHANGE(&rt_runq.runq_stats, rt_runq.count);
1736 rt_runq.count--;
1737
1738 simple_unlock(&rt_lock);
1739
1740 processor->deadline = thread->realtime.deadline;
1741 pset_unlock(pset);
1742
1743 return (thread);
1744 }
1745
1746 simple_unlock(&rt_lock);
1747
1748 /* No realtime threads and no normal threads on the per-processor
1749 * runqueue. Finally check for global fairshare threads.
1750 */
1751 if ((new_thread = SCHED(fairshare_dequeue)()) != THREAD_NULL) {
1752
1753 processor->deadline = UINT64_MAX;
1754 pset_unlock(pset);
1755
1756 return (new_thread);
1757 }
1758
1759 processor->deadline = UINT64_MAX;
1760
1761 /*
1762 * Set processor inactive based on
1763 * indication from the platform code.
1764 */
1765 if (inactive_state) {
1766 if (processor->state == PROCESSOR_RUNNING)
1767 remqueue((queue_entry_t)processor);
1768 else
1769 if (processor->state == PROCESSOR_IDLE)
1770 remqueue((queue_entry_t)processor);
1771
1772 processor->state = PROCESSOR_INACTIVE;
1773
1774 pset_unlock(pset);
1775
1776 return (processor->idle_thread);
1777 }
1778
1779 /*
1780 * No runnable threads, attempt to steal
1781 * from other processors.
1782 */
1783 new_thread = SCHED(steal_thread)(pset);
1784 if (new_thread != THREAD_NULL) {
1785 return (new_thread);
1786 }
1787
1788 /*
1789 * If other threads have appeared, shortcut
1790 * around again.
1791 */
1792 if (!SCHED(processor_queue_empty)(processor) || rt_runq.count > 0 || SCHED(fairshare_runq_count)() > 0)
1793 continue;
1794
1795 pset_lock(pset);
1796
1797 /*
1798 * Nothing is runnable, so set this processor idle if it
1799 * was running.
1800 */
1801 if (processor->state == PROCESSOR_RUNNING) {
1802 remqueue((queue_entry_t)processor);
1803 processor->state = PROCESSOR_IDLE;
1804
1805 if (processor->processor_meta == PROCESSOR_META_NULL || processor->processor_meta->primary == processor) {
1806 enqueue_head(&pset->idle_queue, (queue_entry_t)processor);
1807 pset_pri_init_hint(pset, processor);
1808 pset_count_init_hint(pset, processor);
1809 }
1810 else {
1811 enqueue_head(&processor->processor_meta->idle_queue, (queue_entry_t)processor);
1812 pset_unlock(pset);
1813 return (processor->idle_thread);
1814 }
1815 }
1816
1817 pset_unlock(pset);
1818
1819 #if CONFIG_SCHED_IDLE_IN_PLACE
1820 /*
1821 * Choose idle thread if fast idle is not possible.
1822 */
1823 if ((thread->state & (TH_IDLE|TH_TERMINATE|TH_SUSP)) || !(thread->state & TH_WAIT) || thread->wake_active || thread->sched_pri >= BASEPRI_RTQUEUES)
1824 return (processor->idle_thread);
1825
1826 /*
1827 * Perform idling activities directly without a
1828 * context switch. Return dispatched thread,
1829 * else check again for a runnable thread.
1830 */
1831 new_thread = thread_select_idle(thread, processor);
1832
1833 #else /* !CONFIG_SCHED_IDLE_IN_PLACE */
1834
1835 /*
1836 * Do a full context switch to idle so that the current
1837 * thread can start running on another processor without
1838 * waiting for the fast-idled processor to wake up.
1839 */
1840 return (processor->idle_thread);
1841
1842 #endif /* !CONFIG_SCHED_IDLE_IN_PLACE */
1843
1844 } while (new_thread == THREAD_NULL);
1845
1846 return (new_thread);
1847 }
1848
1849 #if CONFIG_SCHED_IDLE_IN_PLACE
1850 /*
1851 * thread_select_idle:
1852 *
1853 * Idle the processor using the current thread context.
1854 *
1855 * Called with thread locked, then dropped and relocked.
1856 */
1857 static thread_t
1858 thread_select_idle(
1859 thread_t thread,
1860 processor_t processor)
1861 {
1862 thread_t new_thread;
1863
1864 if (thread->sched_mode == TH_MODE_TIMESHARE)
1865 sched_share_decr();
1866 sched_run_decr();
1867
1868 thread->state |= TH_IDLE;
1869 processor->current_pri = IDLEPRI;
1870 processor->current_thmode = TH_MODE_NONE;
1871
1872 /* Reload precise timing global policy to thread-local policy */
1873 thread->precise_user_kernel_time = use_precise_user_kernel_time(thread);
1874
1875 thread_unlock(thread);
1876
1877 /*
1878 * Switch execution timing to processor idle thread.
1879 */
1880 processor->last_dispatch = mach_absolute_time();
1881 thread->last_run_time = processor->last_dispatch;
1882 thread_timer_event(processor->last_dispatch, &processor->idle_thread->system_timer);
1883 PROCESSOR_DATA(processor, kernel_timer) = &processor->idle_thread->system_timer;
1884
1885 /*
1886 * Cancel the quantum timer while idling.
1887 */
1888 timer_call_cancel(&processor->quantum_timer);
1889 processor->timeslice = 0;
1890
1891 (*thread->sched_call)(SCHED_CALL_BLOCK, thread);
1892
1893 thread_tell_urgency(THREAD_URGENCY_NONE, 0, 0);
1894
1895 /*
1896 * Enable interrupts and perform idling activities. No
1897 * preemption due to TH_IDLE being set.
1898 */
1899 spllo(); new_thread = processor_idle(thread, processor);
1900
1901 /*
1902 * Return at splsched.
1903 */
1904 (*thread->sched_call)(SCHED_CALL_UNBLOCK, thread);
1905
1906 thread_lock(thread);
1907
1908 /*
1909 * If we idled in place, simulate a context switch back
1910 * to the original priority of the thread so that the
1911 * platform layer cannot distinguish this from a true
1912 * switch to the idle thread.
1913 */
1914 if (thread->sched_mode == TH_MODE_REALTIME)
1915 thread_tell_urgency(THREAD_URGENCY_REAL_TIME, thread->realtime.period, thread->realtime.deadline);
1916 /* Identify non-promoted threads which have requested a
1917 * "background" priority.
1918 */
1919 else if ((thread->sched_pri <= MAXPRI_THROTTLE) &&
1920 (thread->priority <= MAXPRI_THROTTLE))
1921 thread_tell_urgency(THREAD_URGENCY_BACKGROUND, thread->sched_pri, thread->priority);
1922 else
1923 thread_tell_urgency(THREAD_URGENCY_NORMAL, thread->sched_pri, thread->priority);
1924
1925 /*
1926 * If awakened, switch to thread timer and start a new quantum.
1927 * Otherwise skip; we will context switch to another thread or return here.
1928 */
1929 if (!(thread->state & TH_WAIT)) {
1930 processor->last_dispatch = mach_absolute_time();
1931 thread_timer_event(processor->last_dispatch, &thread->system_timer);
1932 PROCESSOR_DATA(processor, kernel_timer) = &thread->system_timer;
1933
1934 thread_quantum_init(thread);
1935 thread->last_quantum_refill_time = processor->last_dispatch;
1936
1937 processor->quantum_end = processor->last_dispatch + thread->current_quantum;
1938 timer_call_enter1(&processor->quantum_timer, thread, processor->quantum_end, TIMER_CALL_CRITICAL);
1939 processor->timeslice = 1;
1940
1941 thread->computation_epoch = processor->last_dispatch;
1942 }
1943
1944 thread->state &= ~TH_IDLE;
1945
1946 sched_run_incr();
1947 if (thread->sched_mode == TH_MODE_TIMESHARE)
1948 sched_share_incr();
1949
1950 return (new_thread);
1951 }
1952 #endif /* CONFIG_SCHED_IDLE_IN_PLACE */
1953
1954 #if defined(CONFIG_SCHED_TRADITIONAL)
1955 static thread_t
1956 sched_traditional_choose_thread(
1957 processor_t processor,
1958 int priority)
1959 {
1960 thread_t thread;
1961
1962 thread = choose_thread(processor, runq_for_processor(processor), priority);
1963 if (thread != THREAD_NULL) {
1964 runq_consider_decr_bound_count(processor, thread);
1965 }
1966
1967 return thread;
1968 }
1969
1970 #endif /* defined(CONFIG_SCHED_TRADITIONAL) */
1971
1972 #if defined(CONFIG_SCHED_TRADITIONAL) || defined(CONFIG_SCHED_FIXEDPRIORITY)
1973
1974 /*
1975 * choose_thread:
1976 *
1977 * Locate a thread to execute from the processor run queue
1978 * and return it. Only choose a thread with greater or equal
1979 * priority.
1980 *
1981 * Associated pset must be locked. Returns THREAD_NULL
1982 * on failure.
1983 */
1984 thread_t
1985 choose_thread(
1986 processor_t processor,
1987 run_queue_t rq,
1988 int priority)
1989 {
1990 queue_t queue = rq->queues + rq->highq;
1991 int pri = rq->highq, count = rq->count;
1992 thread_t thread;
1993
1994 while (count > 0 && pri >= priority) {
1995 thread = (thread_t)queue_first(queue);
1996 while (!queue_end(queue, (queue_entry_t)thread)) {
1997 if (thread->bound_processor == PROCESSOR_NULL ||
1998 thread->bound_processor == processor) {
1999 remqueue((queue_entry_t)thread);
2000
2001 thread->runq = PROCESSOR_NULL;
2002 SCHED_STATS_RUNQ_CHANGE(&rq->runq_stats, rq->count);
2003 rq->count--;
2004 if (SCHED(priority_is_urgent)(pri)) {
2005 rq->urgency--; assert(rq->urgency >= 0);
2006 }
2007 if (queue_empty(queue)) {
2008 if (pri != IDLEPRI)
2009 clrbit(MAXPRI - pri, rq->bitmap);
2010 rq->highq = MAXPRI - ffsbit(rq->bitmap);
2011 }
2012
2013 return (thread);
2014 }
2015 count--;
2016
2017 thread = (thread_t)queue_next((queue_entry_t)thread);
2018 }
2019
2020 queue--; pri--;
2021 }
2022
2023 return (THREAD_NULL);
2024 }
2025
2026 #endif /* defined(CONFIG_SCHED_TRADITIONAL) || defined(CONFIG_SCHED_FIXEDPRIORITY) */
2027
2028 /*
2029 * Perform a context switch and start executing the new thread.
2030 *
2031 * Returns FALSE on failure, and the thread is re-dispatched.
2032 *
2033 * Called at splsched.
2034 */
2035
2036 #define funnel_release_check(thread, debug) \
2037 MACRO_BEGIN \
2038 if ((thread)->funnel_state & TH_FN_OWNED) { \
2039 (thread)->funnel_state = TH_FN_REFUNNEL; \
2040 KERNEL_DEBUG(0x603242c | DBG_FUNC_NONE, \
2041 (thread)->funnel_lock, (debug), 0, 0, 0); \
2042 funnel_unlock((thread)->funnel_lock); \
2043 } \
2044 MACRO_END
2045
2046 #define funnel_refunnel_check(thread, debug) \
2047 MACRO_BEGIN \
2048 if ((thread)->funnel_state & TH_FN_REFUNNEL) { \
2049 kern_return_t result = (thread)->wait_result; \
2050 \
2051 (thread)->funnel_state = 0; \
2052 KERNEL_DEBUG(0x6032428 | DBG_FUNC_NONE, \
2053 (thread)->funnel_lock, (debug), 0, 0, 0); \
2054 funnel_lock((thread)->funnel_lock); \
2055 KERNEL_DEBUG(0x6032430 | DBG_FUNC_NONE, \
2056 (thread)->funnel_lock, (debug), 0, 0, 0); \
2057 (thread)->funnel_state = TH_FN_OWNED; \
2058 (thread)->wait_result = result; \
2059 } \
2060 MACRO_END
2061
2062 static boolean_t
2063 thread_invoke(
2064 register thread_t self,
2065 register thread_t thread,
2066 ast_t reason)
2067 {
2068 thread_continue_t continuation = self->continuation;
2069 void *parameter = self->parameter;
2070 processor_t processor;
2071
2072 if (get_preemption_level() != 0) {
2073 int pl = get_preemption_level();
2074 panic("thread_invoke: preemption_level %d, possible cause: %s",
2075 pl, (pl < 0 ? "unlocking an unlocked mutex or spinlock" :
2076 "blocking while holding a spinlock, or within interrupt context"));
2077 }
2078
2079 assert(self == current_thread());
2080
2081 /*
2082 * Mark thread interruptible.
2083 */
2084 thread_lock(thread);
2085 thread->state &= ~TH_UNINT;
2086
2087 #if DEBUG
2088 assert(thread_runnable(thread));
2089 #endif
2090
2091 /* Reload precise timing global policy to thread-local policy */
2092 thread->precise_user_kernel_time = use_precise_user_kernel_time(thread);
2093
2094 /*
2095 * Allow time constraint threads to hang onto
2096 * a stack.
2097 */
2098 if ((self->sched_mode == TH_MODE_REALTIME) && !self->reserved_stack)
2099 self->reserved_stack = self->kernel_stack;
2100
2101 if (continuation != NULL) {
2102 if (!thread->kernel_stack) {
2103 /*
2104 * If we are using a privileged stack,
2105 * check to see whether we can exchange it with
2106 * that of the other thread.
2107 */
2108 if (self->kernel_stack == self->reserved_stack && !thread->reserved_stack)
2109 goto need_stack;
2110
2111 /*
2112 * Context switch by performing a stack handoff.
2113 */
2114 continuation = thread->continuation;
2115 parameter = thread->parameter;
2116
2117 processor = current_processor();
2118 processor->active_thread = thread;
2119 processor->current_pri = thread->sched_pri;
2120 processor->current_thmode = thread->sched_mode;
2121 if (thread->last_processor != processor && thread->last_processor != NULL) {
2122 if (thread->last_processor->processor_set != processor->processor_set)
2123 thread->ps_switch++;
2124 thread->p_switch++;
2125 }
2126 thread->last_processor = processor;
2127 thread->c_switch++;
2128 ast_context(thread);
2129 thread_unlock(thread);
2130
2131 self->reason = reason;
2132
2133 processor->last_dispatch = mach_absolute_time();
2134 self->last_run_time = processor->last_dispatch;
2135 thread_timer_event(processor->last_dispatch, &thread->system_timer);
2136 PROCESSOR_DATA(processor, kernel_timer) = &thread->system_timer;
2137
2138 /*
2139 * Since non-precise user/kernel time doesn't update the state timer
2140 * during privilege transitions, synthesize an event now.
2141 */
2142 if (!thread->precise_user_kernel_time) {
2143 timer_switch(PROCESSOR_DATA(processor, current_state),
2144 processor->last_dispatch,
2145 PROCESSOR_DATA(processor, current_state));
2146 }
2147
2148 KERNEL_DEBUG_CONSTANT_IST(KDEBUG_TRACE,
2149 MACHDBG_CODE(DBG_MACH_SCHED, MACH_STACK_HANDOFF)|DBG_FUNC_NONE,
2150 self->reason, (uintptr_t)thread_tid(thread), self->sched_pri, thread->sched_pri, 0);
2151
2152 if ((thread->chosen_processor != processor) && (thread->chosen_processor != NULL)) {
2153 KERNEL_DEBUG_CONSTANT(MACHDBG_CODE(DBG_MACH_SCHED, MACH_MOVED)|DBG_FUNC_NONE,
2154 (uintptr_t)thread_tid(thread), (uintptr_t)thread->chosen_processor->cpu_id, 0, 0, 0);
2155 }
2156
2157 DTRACE_SCHED2(off__cpu, struct thread *, thread, struct proc *, thread->task->bsd_info);
2158
2159 SCHED_STATS_CSW(processor, self->reason, self->sched_pri, thread->sched_pri);
2160
2161 TLOG(1, "thread_invoke: calling stack_handoff\n");
2162 stack_handoff(self, thread);
2163
2164 DTRACE_SCHED(on__cpu);
2165
2166 thread_dispatch(self, thread);
2167
2168 thread->continuation = thread->parameter = NULL;
2169
2170 counter(c_thread_invoke_hits++);
2171
2172 funnel_refunnel_check(thread, 2);
2173 (void) spllo();
2174
2175 assert(continuation);
2176 call_continuation(continuation, parameter, thread->wait_result);
2177 /*NOTREACHED*/
2178 }
2179 else if (thread == self) {
2180 /* same thread but with continuation */
2181 ast_context(self);
2182 counter(++c_thread_invoke_same);
2183 thread_unlock(self);
2184
2185 KERNEL_DEBUG_CONSTANT_IST(KDEBUG_TRACE,
2186 MACHDBG_CODE(DBG_MACH_SCHED,MACH_SCHED) | DBG_FUNC_NONE,
2187 self->reason, (uintptr_t)thread_tid(thread), self->sched_pri, thread->sched_pri, 0);
2188
2189 self->continuation = self->parameter = NULL;
2190
2191 funnel_refunnel_check(self, 3);
2192 (void) spllo();
2193
2194 call_continuation(continuation, parameter, self->wait_result);
2195 /*NOTREACHED*/
2196 }
2197 }
2198 else {
2199 /*
2200 * Check that the other thread has a stack
2201 */
2202 if (!thread->kernel_stack) {
2203 need_stack:
2204 if (!stack_alloc_try(thread)) {
2205 counter(c_thread_invoke_misses++);
2206 thread_unlock(thread);
2207 thread_stack_enqueue(thread);
2208 return (FALSE);
2209 }
2210 }
2211 else if (thread == self) {
2212 ast_context(self);
2213 counter(++c_thread_invoke_same);
2214 thread_unlock(self);
2215
2216 KERNEL_DEBUG_CONSTANT_IST(KDEBUG_TRACE,
2217 MACHDBG_CODE(DBG_MACH_SCHED,MACH_SCHED) | DBG_FUNC_NONE,
2218 self->reason, (uintptr_t)thread_tid(thread), self->sched_pri, thread->sched_pri, 0);
2219
2220 return (TRUE);
2221 }
2222 }
2223
2224 /*
2225 * Context switch by full context save.
2226 */
2227 processor = current_processor();
2228 processor->active_thread = thread;
2229 processor->current_pri = thread->sched_pri;
2230 processor->current_thmode = thread->sched_mode;
2231 if (thread->last_processor != processor && thread->last_processor != NULL) {
2232 if (thread->last_processor->processor_set != processor->processor_set)
2233 thread->ps_switch++;
2234 thread->p_switch++;
2235 }
2236 thread->last_processor = processor;
2237 thread->c_switch++;
2238 ast_context(thread);
2239 thread_unlock(thread);
2240
2241 counter(c_thread_invoke_csw++);
2242
2243 assert(self->runq == PROCESSOR_NULL);
2244 self->reason = reason;
2245
2246 processor->last_dispatch = mach_absolute_time();
2247 self->last_run_time = processor->last_dispatch;
2248 thread_timer_event(processor->last_dispatch, &thread->system_timer);
2249 PROCESSOR_DATA(processor, kernel_timer) = &thread->system_timer;
2250
2251 /*
2252 * Since non-precise user/kernel time doesn't update the state timer
2253 * during privilege transitions, synthesize an event now.
2254 */
2255 if (!thread->precise_user_kernel_time) {
2256 timer_switch(PROCESSOR_DATA(processor, current_state),
2257 processor->last_dispatch,
2258 PROCESSOR_DATA(processor, current_state));
2259 }
2260
2261
2262 KERNEL_DEBUG_CONSTANT_IST(KDEBUG_TRACE,
2263 MACHDBG_CODE(DBG_MACH_SCHED,MACH_SCHED) | DBG_FUNC_NONE,
2264 self->reason, (uintptr_t)thread_tid(thread), self->sched_pri, thread->sched_pri, 0);
2265
2266 if ((thread->chosen_processor != processor) && (thread->chosen_processor != NULL)) {
2267 KERNEL_DEBUG_CONSTANT(MACHDBG_CODE(DBG_MACH_SCHED, MACH_MOVED)|DBG_FUNC_NONE,
2268 (uintptr_t)thread_tid(thread), (uintptr_t)thread->chosen_processor->cpu_id, 0, 0, 0);
2269 }
2270
2271 DTRACE_SCHED2(off__cpu, struct thread *, thread, struct proc *, thread->task->bsd_info);
2272
2273 SCHED_STATS_CSW(processor, self->reason, self->sched_pri, thread->sched_pri);
2274
2275 /*
2276 * This is where we actually switch register context,
2277 * and address space if required. We will next run
2278 * as a result of a subsequent context switch.
2279 */
2280 assert(continuation == self->continuation);
2281 thread = machine_switch_context(self, continuation, thread);
2282 assert(self == current_thread());
2283 TLOG(1,"thread_invoke: returning machine_switch_context: self %p continuation %p thread %p\n", self, continuation, thread);
2284
2285 DTRACE_SCHED(on__cpu);
2286
2287 /*
2288 * We have been resumed and are set to run.
2289 */
2290 thread_dispatch(thread, self);
2291
2292 if (continuation) {
2293 self->continuation = self->parameter = NULL;
2294
2295 funnel_refunnel_check(self, 3);
2296 (void) spllo();
2297
2298 call_continuation(continuation, parameter, self->wait_result);
2299 /*NOTREACHED*/
2300 }
2301
2302 return (TRUE);
2303 }
2304
2305 /*
2306 * thread_dispatch:
2307 *
2308 * Handle threads at context switch. Re-dispatch other thread
2309 * if still running, otherwise update run state and perform
2310 * special actions. Update quantum for other thread and begin
2311 * the quantum for ourselves.
2312 *
2313 * Called at splsched.
2314 */
2315 void
2316 thread_dispatch(
2317 thread_t thread,
2318 thread_t self)
2319 {
2320 processor_t processor = self->last_processor;
2321
2322 if (thread != THREAD_NULL) {
2323 /*
2324 * If blocked at a continuation, discard
2325 * the stack.
2326 */
2327 if (thread->continuation != NULL && thread->kernel_stack != 0)
2328 stack_free(thread);
2329
2330 if (!(thread->state & TH_IDLE)) {
2331 int64_t consumed;
2332 int64_t remainder = 0;
2333
2334 if (processor->quantum_end > processor->last_dispatch)
2335 remainder = processor->quantum_end -
2336 processor->last_dispatch;
2337
2338 consumed = thread->current_quantum - remainder;
2339
2340 if ((thread->reason & AST_LEDGER) == 0)
2341 /*
2342 * Bill CPU time to both the individual thread
2343 * and the task.
2344 */
2345 ledger_credit(thread->t_ledger,
2346 task_ledgers.cpu_time, consumed);
2347 ledger_credit(thread->t_threadledger,
2348 thread_ledgers.cpu_time, consumed);
2349
2350 wake_lock(thread);
2351 thread_lock(thread);
2352
2353 /*
2354 * Compute remainder of current quantum.
2355 */
2356 if (first_timeslice(processor) &&
2357 processor->quantum_end > processor->last_dispatch)
2358 thread->current_quantum = (uint32_t)remainder;
2359 else
2360 thread->current_quantum = 0;
2361
2362 if (thread->sched_mode == TH_MODE_REALTIME) {
2363 /*
2364 * Cancel the deadline if the thread has
2365 * consumed the entire quantum.
2366 */
2367 if (thread->current_quantum == 0) {
2368 thread->realtime.deadline = UINT64_MAX;
2369 thread->reason |= AST_QUANTUM;
2370 }
2371 } else {
2372 #if defined(CONFIG_SCHED_TRADITIONAL)
2373 /*
2374 * For non-realtime threads treat a tiny
2375 * remaining quantum as an expired quantum
2376 * but include what's left next time.
2377 */
2378 if (thread->current_quantum < min_std_quantum) {
2379 thread->reason |= AST_QUANTUM;
2380 thread->current_quantum += SCHED(initial_quantum_size)(thread);
2381 }
2382 #endif
2383 }
2384
2385 /*
2386 * If we are doing a direct handoff then
2387 * take the remainder of the quantum.
2388 */
2389 if ((thread->reason & (AST_HANDOFF|AST_QUANTUM)) == AST_HANDOFF) {
2390 self->current_quantum = thread->current_quantum;
2391 thread->reason |= AST_QUANTUM;
2392 thread->current_quantum = 0;
2393 }
2394
2395 thread->computation_metered += (processor->last_dispatch - thread->computation_epoch);
2396
2397 if (!(thread->state & TH_WAIT)) {
2398 /*
2399 * Still running.
2400 */
2401 if (thread->reason & AST_QUANTUM)
2402 thread_setrun(thread, SCHED_TAILQ);
2403 else
2404 if (thread->reason & AST_PREEMPT)
2405 thread_setrun(thread, SCHED_HEADQ);
2406 else
2407 thread_setrun(thread, SCHED_PREEMPT | SCHED_TAILQ);
2408
2409 thread->reason = AST_NONE;
2410
2411 if (thread->wake_active) {
2412 thread->wake_active = FALSE;
2413 thread_unlock(thread);
2414
2415 thread_wakeup(&thread->wake_active);
2416 }
2417 else
2418 thread_unlock(thread);
2419
2420 wake_unlock(thread);
2421 }
2422 else {
2423 /*
2424 * Waiting.
2425 */
2426 boolean_t should_terminate = FALSE;
2427
2428 /* Only the first call to thread_dispatch
2429 * after explicit termination should add
2430 * the thread to the termination queue
2431 */
2432 if ((thread->state & (TH_TERMINATE|TH_TERMINATE2)) == TH_TERMINATE) {
2433 should_terminate = TRUE;
2434 thread->state |= TH_TERMINATE2;
2435 }
2436
2437 thread->state &= ~TH_RUN;
2438
2439 if (thread->sched_mode == TH_MODE_TIMESHARE)
2440 sched_share_decr();
2441 sched_run_decr();
2442
2443 (*thread->sched_call)(SCHED_CALL_BLOCK, thread);
2444
2445 if (thread->wake_active) {
2446 thread->wake_active = FALSE;
2447 thread_unlock(thread);
2448
2449 thread_wakeup(&thread->wake_active);
2450 }
2451 else
2452 thread_unlock(thread);
2453
2454 wake_unlock(thread);
2455
2456 if (should_terminate)
2457 thread_terminate_enqueue(thread);
2458 }
2459 }
2460 }
2461
2462 if (!(self->state & TH_IDLE)) {
2463
2464 if (self->sched_mode == TH_MODE_REALTIME)
2465 thread_tell_urgency(THREAD_URGENCY_REAL_TIME, self->realtime.period, self->realtime.deadline);
2466 /* Identify non-promoted threads which have requested a
2467 * "background" priority.
2468 */
2469 else if ((self->sched_pri <= MAXPRI_THROTTLE) &&
2470 (self->priority <= MAXPRI_THROTTLE))
2471 thread_tell_urgency(THREAD_URGENCY_BACKGROUND, self->sched_pri, self->priority);
2472 else
2473 thread_tell_urgency(THREAD_URGENCY_NORMAL, self->sched_pri, self->priority);
2474 /*
2475 * Get a new quantum if none remaining.
2476 */
2477 if (self->current_quantum == 0) {
2478 thread_quantum_init(self);
2479 self->last_quantum_refill_time = processor->last_dispatch;
2480 }
2481
2482 /*
2483 * Set up quantum timer and timeslice.
2484 */
2485 processor->quantum_end = (processor->last_dispatch + self->current_quantum);
2486 timer_call_enter1(&processor->quantum_timer, self, processor->quantum_end, TIMER_CALL_CRITICAL);
2487
2488 processor->timeslice = 1;
2489
2490 self->computation_epoch = processor->last_dispatch;
2491 }
2492 else {
2493 timer_call_cancel(&processor->quantum_timer);
2494 processor->timeslice = 0;
2495
2496 thread_tell_urgency(THREAD_URGENCY_NONE, 0, 0);
2497 }
2498 }
2499
2500 #include <libkern/OSDebug.h>
2501
2502 uint32_t kdebug_thread_block = 0;
2503
2504
2505 /*
2506 * thread_block_reason:
2507 *
2508 * Forces a reschedule, blocking the caller if a wait
2509 * has been asserted.
2510 *
2511 * If a continuation is specified, then thread_invoke will
2512 * attempt to discard the thread's kernel stack. When the
2513 * thread resumes, it will execute the continuation function
2514 * on a new kernel stack.
2515 */
2516 counter(mach_counter_t c_thread_block_calls = 0;)
2517
2518 wait_result_t
2519 thread_block_reason(
2520 thread_continue_t continuation,
2521 void *parameter,
2522 ast_t reason)
2523 {
2524 register thread_t self = current_thread();
2525 register processor_t processor;
2526 register thread_t new_thread;
2527 spl_t s;
2528
2529 counter(++c_thread_block_calls);
2530
2531 s = splsched();
2532
2533 if (!(reason & AST_PREEMPT))
2534 funnel_release_check(self, 2);
2535
2536 processor = current_processor();
2537
2538 /* If we're explicitly yielding, force a subsequent quantum */
2539 if (reason & AST_YIELD)
2540 processor->timeslice = 0;
2541
2542 /* We're handling all scheduling AST's */
2543 ast_off(AST_SCHEDULING);
2544
2545 self->continuation = continuation;
2546 self->parameter = parameter;
2547
2548 if (__improbable(kdebug_thread_block && kdebug_enable && self->state != TH_RUN)) {
2549 KERNEL_DEBUG_CONSTANT_IST(KDEBUG_TRACE,
2550 MACHDBG_CODE(DBG_MACH_SCHED,MACH_BLOCK),
2551 reason, VM_KERNEL_UNSLIDE(continuation), 0, 0, 0);
2552 }
2553
2554 do {
2555 thread_lock(self);
2556 new_thread = thread_select(self, processor);
2557 thread_unlock(self);
2558 } while (!thread_invoke(self, new_thread, reason));
2559
2560 funnel_refunnel_check(self, 5);
2561 splx(s);
2562
2563 return (self->wait_result);
2564 }
2565
2566 /*
2567 * thread_block:
2568 *
2569 * Block the current thread if a wait has been asserted.
2570 */
2571 wait_result_t
2572 thread_block(
2573 thread_continue_t continuation)
2574 {
2575 return thread_block_reason(continuation, NULL, AST_NONE);
2576 }
2577
2578 wait_result_t
2579 thread_block_parameter(
2580 thread_continue_t continuation,
2581 void *parameter)
2582 {
2583 return thread_block_reason(continuation, parameter, AST_NONE);
2584 }
2585
2586 /*
2587 * thread_run:
2588 *
2589 * Switch directly from the current thread to the
2590 * new thread, handing off our quantum if appropriate.
2591 *
2592 * New thread must be runnable, and not on a run queue.
2593 *
2594 * Called at splsched.
2595 */
2596 int
2597 thread_run(
2598 thread_t self,
2599 thread_continue_t continuation,
2600 void *parameter,
2601 thread_t new_thread)
2602 {
2603 ast_t handoff = AST_HANDOFF;
2604
2605 funnel_release_check(self, 3);
2606
2607 self->continuation = continuation;
2608 self->parameter = parameter;
2609
2610 while (!thread_invoke(self, new_thread, handoff)) {
2611 processor_t processor = current_processor();
2612
2613 thread_lock(self);
2614 new_thread = thread_select(self, processor);
2615 thread_unlock(self);
2616 handoff = AST_NONE;
2617 }
2618
2619 funnel_refunnel_check(self, 6);
2620
2621 return (self->wait_result);
2622 }
2623
2624 /*
2625 * thread_continue:
2626 *
2627 * Called at splsched when a thread first receives
2628 * a new stack after a continuation.
2629 */
2630 void
2631 thread_continue(
2632 register thread_t thread)
2633 {
2634 register thread_t self = current_thread();
2635 register thread_continue_t continuation;
2636 register void *parameter;
2637
2638 DTRACE_SCHED(on__cpu);
2639
2640 continuation = self->continuation;
2641 parameter = self->parameter;
2642
2643 thread_dispatch(thread, self);
2644
2645 self->continuation = self->parameter = NULL;
2646
2647 funnel_refunnel_check(self, 4);
2648
2649 if (thread != THREAD_NULL)
2650 (void)spllo();
2651
2652 TLOG(1, "thread_continue: calling call_continuation \n");
2653 call_continuation(continuation, parameter, self->wait_result);
2654 /*NOTREACHED*/
2655 }
2656
2657 void
2658 thread_quantum_init(thread_t thread)
2659 {
2660 if (thread->sched_mode == TH_MODE_REALTIME) {
2661 thread->current_quantum = thread->realtime.computation;
2662 } else {
2663 thread->current_quantum = SCHED(initial_quantum_size)(thread);
2664 }
2665 }
2666
2667 #if defined(CONFIG_SCHED_TRADITIONAL)
2668 static uint32_t
2669 sched_traditional_initial_quantum_size(thread_t thread)
2670 {
2671 if ((thread == THREAD_NULL) || thread->priority > MAXPRI_THROTTLE)
2672 return std_quantum;
2673 else
2674 return bg_quantum;
2675 }
2676
2677 static sched_mode_t
2678 sched_traditional_initial_thread_sched_mode(task_t parent_task)
2679 {
2680 if (parent_task == kernel_task)
2681 return TH_MODE_FIXED;
2682 else
2683 return TH_MODE_TIMESHARE;
2684 }
2685
2686 static boolean_t
2687 sched_traditional_supports_timeshare_mode(void)
2688 {
2689 return TRUE;
2690 }
2691
2692 #endif /* CONFIG_SCHED_TRADITIONAL */
2693
2694 /*
2695 * run_queue_init:
2696 *
2697 * Initialize a run queue before first use.
2698 */
2699 void
2700 run_queue_init(
2701 run_queue_t rq)
2702 {
2703 int i;
2704
2705 rq->highq = IDLEPRI;
2706 for (i = 0; i < NRQBM; i++)
2707 rq->bitmap[i] = 0;
2708 setbit(MAXPRI - IDLEPRI, rq->bitmap);
2709 rq->urgency = rq->count = 0;
2710 for (i = 0; i < NRQS; i++)
2711 queue_init(&rq->queues[i]);
2712 }
2713
2714 #if defined(CONFIG_SCHED_TRADITIONAL) || defined(CONFIG_SCHED_PROTO) || defined(CONFIG_SCHED_GRRR) || defined(CONFIG_SCHED_FIXEDPRIORITY)
2715 int
2716 sched_traditional_fairshare_runq_count(void)
2717 {
2718 return fs_runq.count;
2719 }
2720
2721 uint64_t
2722 sched_traditional_fairshare_runq_stats_count_sum(void)
2723 {
2724 return fs_runq.runq_stats.count_sum;
2725 }
2726
2727 void
2728 sched_traditional_fairshare_enqueue(thread_t thread)
2729 {
2730 queue_t queue = &fs_runq.queue;
2731
2732 simple_lock(&fs_lock);
2733
2734 enqueue_tail(queue, (queue_entry_t)thread);
2735
2736 thread->runq = FS_RUNQ;
2737 SCHED_STATS_RUNQ_CHANGE(&fs_runq.runq_stats, fs_runq.count);
2738 fs_runq.count++;
2739
2740 simple_unlock(&fs_lock);
2741 }
2742
2743 thread_t
2744 sched_traditional_fairshare_dequeue(void)
2745 {
2746 thread_t thread;
2747
2748 simple_lock(&fs_lock);
2749 if (fs_runq.count > 0) {
2750 thread = (thread_t)dequeue_head(&fs_runq.queue);
2751
2752 thread->runq = PROCESSOR_NULL;
2753 SCHED_STATS_RUNQ_CHANGE(&fs_runq.runq_stats, fs_runq.count);
2754 fs_runq.count--;
2755
2756 simple_unlock(&fs_lock);
2757
2758 return (thread);
2759 }
2760 simple_unlock(&fs_lock);
2761
2762 return THREAD_NULL;
2763 }
2764
2765 boolean_t
2766 sched_traditional_fairshare_queue_remove(thread_t thread)
2767 {
2768 queue_t q;
2769
2770 simple_lock(&fs_lock);
2771 q = &fs_runq.queue;
2772
2773 if (FS_RUNQ == thread->runq) {
2774 remqueue((queue_entry_t)thread);
2775 SCHED_STATS_RUNQ_CHANGE(&fs_runq.runq_stats, fs_runq.count);
2776 fs_runq.count--;
2777
2778 thread->runq = PROCESSOR_NULL;
2779 simple_unlock(&fs_lock);
2780 return (TRUE);
2781 }
2782 else {
2783 /*
2784 * The thread left the run queue before we could
2785 * lock the run queue.
2786 */
2787 assert(thread->runq == PROCESSOR_NULL);
2788 simple_unlock(&fs_lock);
2789 return (FALSE);
2790 }
2791 }
2792
2793 #endif /* defined(CONFIG_SCHED_TRADITIONAL) || defined(CONFIG_SCHED_PROTO) || defined(CONFIG_SCHED_GRRR) || defined(CONFIG_SCHED_FIXEDPRIORITY) */
2794
2795 /*
2796 * run_queue_dequeue:
2797 *
2798 * Perform a dequeue operation on a run queue,
2799 * and return the resulting thread.
2800 *
2801 * The run queue must be locked (see thread_run_queue_remove()
2802 * for more info), and not empty.
2803 */
2804 thread_t
2805 run_queue_dequeue(
2806 run_queue_t rq,
2807 integer_t options)
2808 {
2809 thread_t thread;
2810 queue_t queue = rq->queues + rq->highq;
2811
2812 if (options & SCHED_HEADQ) {
2813 thread = (thread_t)dequeue_head(queue);
2814 }
2815 else {
2816 thread = (thread_t)dequeue_tail(queue);
2817 }
2818
2819 thread->runq = PROCESSOR_NULL;
2820 SCHED_STATS_RUNQ_CHANGE(&rq->runq_stats, rq->count);
2821 rq->count--;
2822 if (SCHED(priority_is_urgent)(rq->highq)) {
2823 rq->urgency--; assert(rq->urgency >= 0);
2824 }
2825 if (queue_empty(queue)) {
2826 if (rq->highq != IDLEPRI)
2827 clrbit(MAXPRI - rq->highq, rq->bitmap);
2828 rq->highq = MAXPRI - ffsbit(rq->bitmap);
2829 }
2830
2831 return (thread);
2832 }
2833
2834 /*
2835 * run_queue_enqueue:
2836 *
2837 * Perform a enqueue operation on a run queue.
2838 *
2839 * The run queue must be locked (see thread_run_queue_remove()
2840 * for more info).
2841 */
2842 boolean_t
2843 run_queue_enqueue(
2844 run_queue_t rq,
2845 thread_t thread,
2846 integer_t options)
2847 {
2848 queue_t queue = rq->queues + thread->sched_pri;
2849 boolean_t result = FALSE;
2850
2851 if (queue_empty(queue)) {
2852 enqueue_tail(queue, (queue_entry_t)thread);
2853
2854 setbit(MAXPRI - thread->sched_pri, rq->bitmap);
2855 if (thread->sched_pri > rq->highq) {
2856 rq->highq = thread->sched_pri;
2857 result = TRUE;
2858 }
2859 }
2860 else
2861 if (options & SCHED_TAILQ)
2862 enqueue_tail(queue, (queue_entry_t)thread);
2863 else
2864 enqueue_head(queue, (queue_entry_t)thread);
2865
2866 if (SCHED(priority_is_urgent)(thread->sched_pri))
2867 rq->urgency++;
2868 SCHED_STATS_RUNQ_CHANGE(&rq->runq_stats, rq->count);
2869 rq->count++;
2870
2871 return (result);
2872
2873 }
2874
2875 /*
2876 * run_queue_remove:
2877 *
2878 * Remove a specific thread from a runqueue.
2879 *
2880 * The run queue must be locked.
2881 */
2882 void
2883 run_queue_remove(
2884 run_queue_t rq,
2885 thread_t thread)
2886 {
2887
2888 remqueue((queue_entry_t)thread);
2889 SCHED_STATS_RUNQ_CHANGE(&rq->runq_stats, rq->count);
2890 rq->count--;
2891 if (SCHED(priority_is_urgent)(thread->sched_pri)) {
2892 rq->urgency--; assert(rq->urgency >= 0);
2893 }
2894
2895 if (queue_empty(rq->queues + thread->sched_pri)) {
2896 /* update run queue status */
2897 if (thread->sched_pri != IDLEPRI)
2898 clrbit(MAXPRI - thread->sched_pri, rq->bitmap);
2899 rq->highq = MAXPRI - ffsbit(rq->bitmap);
2900 }
2901
2902 thread->runq = PROCESSOR_NULL;
2903 }
2904
2905 /*
2906 * fairshare_setrun:
2907 *
2908 * Dispatch a thread for round-robin execution.
2909 *
2910 * Thread must be locked. Associated pset must
2911 * be locked, and is returned unlocked.
2912 */
2913 static void
2914 fairshare_setrun(
2915 processor_t processor,
2916 thread_t thread)
2917 {
2918 processor_set_t pset = processor->processor_set;
2919
2920 thread->chosen_processor = processor;
2921
2922 SCHED(fairshare_enqueue)(thread);
2923
2924 if (processor != current_processor())
2925 machine_signal_idle(processor);
2926
2927 pset_unlock(pset);
2928
2929 }
2930
2931 /*
2932 * realtime_queue_insert:
2933 *
2934 * Enqueue a thread for realtime execution.
2935 */
2936 static boolean_t
2937 realtime_queue_insert(
2938 thread_t thread)
2939 {
2940 queue_t queue = &rt_runq.queue;
2941 uint64_t deadline = thread->realtime.deadline;
2942 boolean_t preempt = FALSE;
2943
2944 simple_lock(&rt_lock);
2945
2946 if (queue_empty(queue)) {
2947 enqueue_tail(queue, (queue_entry_t)thread);
2948 preempt = TRUE;
2949 }
2950 else {
2951 register thread_t entry = (thread_t)queue_first(queue);
2952
2953 while (TRUE) {
2954 if ( queue_end(queue, (queue_entry_t)entry) ||
2955 deadline < entry->realtime.deadline ) {
2956 entry = (thread_t)queue_prev((queue_entry_t)entry);
2957 break;
2958 }
2959
2960 entry = (thread_t)queue_next((queue_entry_t)entry);
2961 }
2962
2963 if ((queue_entry_t)entry == queue)
2964 preempt = TRUE;
2965
2966 insque((queue_entry_t)thread, (queue_entry_t)entry);
2967 }
2968
2969 thread->runq = RT_RUNQ;
2970 SCHED_STATS_RUNQ_CHANGE(&rt_runq.runq_stats, rt_runq.count);
2971 rt_runq.count++;
2972
2973 simple_unlock(&rt_lock);
2974
2975 return (preempt);
2976 }
2977
2978 /*
2979 * realtime_setrun:
2980 *
2981 * Dispatch a thread for realtime execution.
2982 *
2983 * Thread must be locked. Associated pset must
2984 * be locked, and is returned unlocked.
2985 */
2986 static void
2987 realtime_setrun(
2988 processor_t processor,
2989 thread_t thread)
2990 {
2991 processor_set_t pset = processor->processor_set;
2992
2993 thread->chosen_processor = processor;
2994
2995 /*
2996 * Dispatch directly onto idle processor.
2997 */
2998 if ( (thread->bound_processor == processor)
2999 && processor->state == PROCESSOR_IDLE) {
3000 remqueue((queue_entry_t)processor);
3001 enqueue_tail(&pset->active_queue, (queue_entry_t)processor);
3002
3003 processor->next_thread = thread;
3004 processor->deadline = thread->realtime.deadline;
3005 processor->state = PROCESSOR_DISPATCHING;
3006 pset_unlock(pset);
3007
3008 if (processor != current_processor())
3009 machine_signal_idle(processor);
3010 return;
3011 }
3012
3013 if (realtime_queue_insert(thread)) {
3014 int prstate = processor->state;
3015 if (processor == current_processor())
3016 ast_on(AST_PREEMPT | AST_URGENT);
3017 else if ((prstate == PROCESSOR_IDLE) || (prstate == PROCESSOR_DISPATCHING))
3018 machine_signal_idle(processor);
3019 else
3020 cause_ast_check(processor);
3021 }
3022
3023 pset_unlock(pset);
3024 }
3025
3026 #if defined(CONFIG_SCHED_TRADITIONAL)
3027
3028 static boolean_t
3029 priority_is_urgent(int priority)
3030 {
3031 return testbit(priority, sched_preempt_pri) ? TRUE : FALSE;
3032 }
3033
3034 /*
3035 * processor_enqueue:
3036 *
3037 * Enqueue thread on a processor run queue. Thread must be locked,
3038 * and not already be on a run queue.
3039 *
3040 * Returns TRUE if a preemption is indicated based on the state
3041 * of the run queue.
3042 *
3043 * The run queue must be locked (see thread_run_queue_remove()
3044 * for more info).
3045 */
3046 static boolean_t
3047 processor_enqueue(
3048 processor_t processor,
3049 thread_t thread,
3050 integer_t options)
3051 {
3052 run_queue_t rq = runq_for_processor(processor);
3053 boolean_t result;
3054
3055 result = run_queue_enqueue(rq, thread, options);
3056 thread->runq = processor;
3057 runq_consider_incr_bound_count(processor, thread);
3058
3059 return (result);
3060 }
3061
3062 #endif /* CONFIG_SCHED_TRADITIONAL */
3063
3064 /*
3065 * processor_setrun:
3066 *
3067 * Dispatch a thread for execution on a
3068 * processor.
3069 *
3070 * Thread must be locked. Associated pset must
3071 * be locked, and is returned unlocked.
3072 */
3073 static void
3074 processor_setrun(
3075 processor_t processor,
3076 thread_t thread,
3077 integer_t options)
3078 {
3079 processor_set_t pset = processor->processor_set;
3080 ast_t preempt;
3081
3082 thread->chosen_processor = processor;
3083
3084 /*
3085 * Dispatch directly onto idle processor.
3086 */
3087 if ( (SCHED(direct_dispatch_to_idle_processors) ||
3088 thread->bound_processor == processor)
3089 && processor->state == PROCESSOR_IDLE) {
3090 remqueue((queue_entry_t)processor);
3091 enqueue_tail(&pset->active_queue, (queue_entry_t)processor);
3092
3093 processor->next_thread = thread;
3094 processor->deadline = UINT64_MAX;
3095 processor->state = PROCESSOR_DISPATCHING;
3096 pset_unlock(pset);
3097
3098 if (processor != current_processor())
3099 machine_signal_idle(processor);
3100 return;
3101 }
3102
3103 /*
3104 * Set preemption mode.
3105 */
3106 if (SCHED(priority_is_urgent)(thread->sched_pri) && thread->sched_pri > processor->current_pri)
3107 preempt = (AST_PREEMPT | AST_URGENT);
3108 else if(processor->active_thread && thread_eager_preemption(processor->active_thread))
3109 preempt = (AST_PREEMPT | AST_URGENT);
3110 else
3111 if ((thread->sched_mode == TH_MODE_TIMESHARE) && thread->sched_pri < thread->priority)
3112 preempt = AST_NONE;
3113 else
3114 preempt = (options & SCHED_PREEMPT)? AST_PREEMPT: AST_NONE;
3115
3116 if (!SCHED(processor_enqueue)(processor, thread, options))
3117 preempt = AST_NONE;
3118
3119 if (preempt != AST_NONE) {
3120 if (processor == current_processor()) {
3121 if (csw_check(processor) != AST_NONE)
3122 ast_on(preempt);
3123 }
3124 else
3125 if ( processor->state == PROCESSOR_IDLE || processor->state == PROCESSOR_DISPATCHING) {
3126 machine_signal_idle(processor);
3127 }
3128 else
3129 if ( (processor->state == PROCESSOR_RUNNING ||
3130 processor->state == PROCESSOR_SHUTDOWN) &&
3131 (thread->sched_pri >= processor->current_pri ||
3132 processor->current_thmode == TH_MODE_FAIRSHARE)) {
3133 cause_ast_check(processor);
3134 }
3135 }
3136 else
3137 if ( processor->state == PROCESSOR_SHUTDOWN &&
3138 thread->sched_pri >= processor->current_pri ) {
3139 cause_ast_check(processor);
3140 }
3141 else
3142 if ( processor->state == PROCESSOR_IDLE &&
3143 processor != current_processor() ) {
3144 machine_signal_idle(processor);
3145 }
3146
3147 pset_unlock(pset);
3148 }
3149
3150 #if defined(CONFIG_SCHED_TRADITIONAL)
3151
3152 static boolean_t
3153 processor_queue_empty(processor_t processor)
3154 {
3155 return runq_for_processor(processor)->count == 0;
3156
3157 }
3158
3159 static boolean_t
3160 sched_traditional_with_pset_runqueue_processor_queue_empty(processor_t processor)
3161 {
3162 processor_set_t pset = processor->processor_set;
3163 int count = runq_for_processor(processor)->count;
3164
3165 /*
3166 * The pset runq contains the count of all runnable threads
3167 * for all processors in the pset. However, for threads that
3168 * are bound to another processor, the current "processor"
3169 * is not eligible to execute the thread. So we only
3170 * include bound threads that our bound to the current
3171 * "processor". This allows the processor to idle when the
3172 * count of eligible threads drops to 0, even if there's
3173 * a runnable thread bound to a different processor in the
3174 * shared runq.
3175 */
3176
3177 count -= pset->pset_runq_bound_count;
3178 count += processor->runq_bound_count;
3179
3180 return count == 0;
3181 }
3182
3183 static ast_t
3184 processor_csw_check(processor_t processor)
3185 {
3186 run_queue_t runq;
3187 boolean_t has_higher;
3188
3189 assert(processor->active_thread != NULL);
3190
3191 runq = runq_for_processor(processor);
3192 if (first_timeslice(processor)) {
3193 has_higher = (runq->highq > processor->current_pri);
3194 } else {
3195 has_higher = (runq->highq >= processor->current_pri);
3196 }
3197 if (has_higher) {
3198 if (runq->urgency > 0)
3199 return (AST_PREEMPT | AST_URGENT);
3200
3201 if (processor->active_thread && thread_eager_preemption(processor->active_thread))
3202 return (AST_PREEMPT | AST_URGENT);
3203
3204 return AST_PREEMPT;
3205 }
3206
3207 return AST_NONE;
3208 }
3209
3210 static boolean_t
3211 processor_queue_has_priority(processor_t processor,
3212 int priority,
3213 boolean_t gte)
3214 {
3215 if (gte)
3216 return runq_for_processor(processor)->highq >= priority;
3217 else
3218 return runq_for_processor(processor)->highq > priority;
3219 }
3220
3221 static boolean_t
3222 should_current_thread_rechoose_processor(processor_t processor)
3223 {
3224 return (processor->current_pri < BASEPRI_RTQUEUES
3225 && processor->processor_meta != PROCESSOR_META_NULL
3226 && processor->processor_meta->primary != processor);
3227 }
3228
3229 static int
3230 sched_traditional_processor_runq_count(processor_t processor)
3231 {
3232 return runq_for_processor(processor)->count;
3233 }
3234
3235
3236 static uint64_t
3237 sched_traditional_processor_runq_stats_count_sum(processor_t processor)
3238 {
3239 return runq_for_processor(processor)->runq_stats.count_sum;
3240 }
3241
3242 static uint64_t
3243 sched_traditional_with_pset_runqueue_processor_runq_stats_count_sum(processor_t processor)
3244 {
3245 if (processor->cpu_id == processor->processor_set->cpu_set_low)
3246 return runq_for_processor(processor)->runq_stats.count_sum;
3247 else
3248 return 0ULL;
3249 }
3250
3251 #endif /* CONFIG_SCHED_TRADITIONAL */
3252
3253 #define next_pset(p) (((p)->pset_list != PROCESSOR_SET_NULL)? (p)->pset_list: (p)->node->psets)
3254
3255 /*
3256 * choose_next_pset:
3257 *
3258 * Return the next sibling pset containing
3259 * available processors.
3260 *
3261 * Returns the original pset if none other is
3262 * suitable.
3263 */
3264 static processor_set_t
3265 choose_next_pset(
3266 processor_set_t pset)
3267 {
3268 processor_set_t nset = pset;
3269
3270 do {
3271 nset = next_pset(nset);
3272 } while (nset->online_processor_count < 1 && nset != pset);
3273
3274 return (nset);
3275 }
3276
3277 /*
3278 * choose_processor:
3279 *
3280 * Choose a processor for the thread, beginning at
3281 * the pset. Accepts an optional processor hint in
3282 * the pset.
3283 *
3284 * Returns a processor, possibly from a different pset.
3285 *
3286 * The thread must be locked. The pset must be locked,
3287 * and the resulting pset is locked on return.
3288 */
3289 processor_t
3290 choose_processor(
3291 processor_set_t pset,
3292 processor_t processor,
3293 thread_t thread)
3294 {
3295 processor_set_t nset, cset = pset;
3296 processor_meta_t pmeta = PROCESSOR_META_NULL;
3297 processor_t mprocessor;
3298
3299 /*
3300 * Prefer the hinted processor, when appropriate.
3301 */
3302
3303 if (processor != PROCESSOR_NULL) {
3304 if (processor->processor_meta != PROCESSOR_META_NULL)
3305 processor = processor->processor_meta->primary;
3306 }
3307
3308 mprocessor = machine_choose_processor(pset, processor);
3309 if (mprocessor != PROCESSOR_NULL)
3310 processor = mprocessor;
3311
3312 if (processor != PROCESSOR_NULL) {
3313 if (processor->processor_set != pset ||
3314 processor->state == PROCESSOR_INACTIVE ||
3315 processor->state == PROCESSOR_SHUTDOWN ||
3316 processor->state == PROCESSOR_OFF_LINE)
3317 processor = PROCESSOR_NULL;
3318 else
3319 if (processor->state == PROCESSOR_IDLE ||
3320 ((thread->sched_pri >= BASEPRI_RTQUEUES) &&
3321 (processor->current_pri < BASEPRI_RTQUEUES)))
3322 return (processor);
3323 }
3324
3325 /*
3326 * Iterate through the processor sets to locate
3327 * an appropriate processor.
3328 */
3329 do {
3330 /*
3331 * Choose an idle processor.
3332 */
3333 if (!queue_empty(&cset->idle_queue))
3334 return ((processor_t)queue_first(&cset->idle_queue));
3335
3336 if (thread->sched_pri >= BASEPRI_RTQUEUES) {
3337 integer_t lowest_priority = MAXPRI + 1;
3338 integer_t lowest_unpaired = MAXPRI + 1;
3339 uint64_t furthest_deadline = 1;
3340 processor_t lp_processor = PROCESSOR_NULL;
3341 processor_t lp_unpaired = PROCESSOR_NULL;
3342 processor_t fd_processor = PROCESSOR_NULL;
3343
3344 lp_processor = cset->low_pri;
3345 /* Consider hinted processor */
3346 if (lp_processor != PROCESSOR_NULL &&
3347 ((lp_processor->processor_meta == PROCESSOR_META_NULL) ||
3348 ((lp_processor == lp_processor->processor_meta->primary) &&
3349 !queue_empty(&lp_processor->processor_meta->idle_queue))) &&
3350 lp_processor->state != PROCESSOR_INACTIVE &&
3351 lp_processor->state != PROCESSOR_SHUTDOWN &&
3352 lp_processor->state != PROCESSOR_OFF_LINE &&
3353 (lp_processor->current_pri < thread->sched_pri))
3354 return lp_processor;
3355
3356 processor = (processor_t)queue_first(&cset->active_queue);
3357 while (!queue_end(&cset->active_queue, (queue_entry_t)processor)) {
3358 /* Discover the processor executing the
3359 * thread with the lowest priority within
3360 * this pset, or the one with the furthest
3361 * deadline
3362 */
3363 integer_t cpri = processor->current_pri;
3364 if (cpri < lowest_priority) {
3365 lowest_priority = cpri;
3366 lp_processor = processor;
3367 }
3368
3369 if ((cpri >= BASEPRI_RTQUEUES) && (processor->deadline > furthest_deadline)) {
3370 furthest_deadline = processor->deadline;
3371 fd_processor = processor;
3372 }
3373
3374
3375 if (processor->processor_meta != PROCESSOR_META_NULL &&
3376 !queue_empty(&processor->processor_meta->idle_queue)) {
3377 if (cpri < lowest_unpaired) {
3378 lowest_unpaired = cpri;
3379 lp_unpaired = processor;
3380 pmeta = processor->processor_meta;
3381 }
3382 else
3383 if (pmeta == PROCESSOR_META_NULL)
3384 pmeta = processor->processor_meta;
3385 }
3386 processor = (processor_t)queue_next((queue_entry_t)processor);
3387 }
3388
3389 if (thread->sched_pri > lowest_unpaired)
3390 return lp_unpaired;
3391
3392 if (pmeta != PROCESSOR_META_NULL)
3393 return ((processor_t)queue_first(&pmeta->idle_queue));
3394 if (thread->sched_pri > lowest_priority)
3395 return lp_processor;
3396 if (thread->realtime.deadline < furthest_deadline)
3397 return fd_processor;
3398
3399 processor = PROCESSOR_NULL;
3400 }
3401 else {
3402 /*
3403 * Check any hinted processors in the processor set if available.
3404 */
3405 if (cset->low_pri != PROCESSOR_NULL && cset->low_pri->state != PROCESSOR_INACTIVE &&
3406 cset->low_pri->state != PROCESSOR_SHUTDOWN && cset->low_pri->state != PROCESSOR_OFF_LINE &&
3407 (processor == PROCESSOR_NULL ||
3408 (thread->sched_pri > BASEPRI_DEFAULT && cset->low_pri->current_pri < thread->sched_pri))) {
3409 processor = cset->low_pri;
3410 }
3411 else
3412 if (cset->low_count != PROCESSOR_NULL && cset->low_count->state != PROCESSOR_INACTIVE &&
3413 cset->low_count->state != PROCESSOR_SHUTDOWN && cset->low_count->state != PROCESSOR_OFF_LINE &&
3414 (processor == PROCESSOR_NULL || (thread->sched_pri <= BASEPRI_DEFAULT &&
3415 SCHED(processor_runq_count)(cset->low_count) < SCHED(processor_runq_count)(processor)))) {
3416 processor = cset->low_count;
3417 }
3418
3419 /*
3420 * Otherwise, choose an available processor in the set.
3421 */
3422 if (processor == PROCESSOR_NULL) {
3423 processor = (processor_t)dequeue_head(&cset->active_queue);
3424 if (processor != PROCESSOR_NULL)
3425 enqueue_tail(&cset->active_queue, (queue_entry_t)processor);
3426 }
3427
3428 if (processor != PROCESSOR_NULL && pmeta == PROCESSOR_META_NULL) {
3429 if (processor->processor_meta != PROCESSOR_META_NULL &&
3430 !queue_empty(&processor->processor_meta->idle_queue))
3431 pmeta = processor->processor_meta;
3432 }
3433 }
3434
3435 /*
3436 * Move onto the next processor set.
3437 */
3438 nset = next_pset(cset);
3439
3440 if (nset != pset) {
3441 pset_unlock(cset);
3442
3443 cset = nset;
3444 pset_lock(cset);
3445 }
3446 } while (nset != pset);
3447
3448 /*
3449 * Make sure that we pick a running processor,
3450 * and that the correct processor set is locked.
3451 */
3452 do {
3453 if (pmeta != PROCESSOR_META_NULL) {
3454 if (cset != pmeta->primary->processor_set) {
3455 pset_unlock(cset);
3456
3457 cset = pmeta->primary->processor_set;
3458 pset_lock(cset);
3459 }
3460
3461 if (!queue_empty(&pmeta->idle_queue))
3462 return ((processor_t)queue_first(&pmeta->idle_queue));
3463
3464 pmeta = PROCESSOR_META_NULL;
3465 }
3466
3467 /*
3468 * If we haven't been able to choose a processor,
3469 * pick the boot processor and return it.
3470 */
3471 if (processor == PROCESSOR_NULL) {
3472 processor = master_processor;
3473
3474 /*
3475 * Check that the correct processor set is
3476 * returned locked.
3477 */
3478 if (cset != processor->processor_set) {
3479 pset_unlock(cset);
3480
3481 cset = processor->processor_set;
3482 pset_lock(cset);
3483 }
3484
3485 return (processor);
3486 }
3487
3488 /*
3489 * Check that the processor set for the chosen
3490 * processor is locked.
3491 */
3492 if (cset != processor->processor_set) {
3493 pset_unlock(cset);
3494
3495 cset = processor->processor_set;
3496 pset_lock(cset);
3497 }
3498
3499 /*
3500 * We must verify that the chosen processor is still available.
3501 */
3502 if (processor->state == PROCESSOR_INACTIVE ||
3503 processor->state == PROCESSOR_SHUTDOWN || processor->state == PROCESSOR_OFF_LINE)
3504 processor = PROCESSOR_NULL;
3505 } while (processor == PROCESSOR_NULL);
3506
3507 return (processor);
3508 }
3509
3510 /*
3511 * thread_setrun:
3512 *
3513 * Dispatch thread for execution, onto an idle
3514 * processor or run queue, and signal a preemption
3515 * as appropriate.
3516 *
3517 * Thread must be locked.
3518 */
3519 void
3520 thread_setrun(
3521 thread_t thread,
3522 integer_t options)
3523 {
3524 processor_t processor;
3525 processor_set_t pset;
3526
3527 #if DEBUG
3528 assert(thread_runnable(thread));
3529 #endif
3530
3531 /*
3532 * Update priority if needed.
3533 */
3534 if (SCHED(can_update_priority)(thread))
3535 SCHED(update_priority)(thread);
3536
3537 assert(thread->runq == PROCESSOR_NULL);
3538
3539 if (thread->bound_processor == PROCESSOR_NULL) {
3540 /*
3541 * Unbound case.
3542 */
3543 if (thread->affinity_set != AFFINITY_SET_NULL) {
3544 /*
3545 * Use affinity set policy hint.
3546 */
3547 pset = thread->affinity_set->aset_pset;
3548 pset_lock(pset);
3549
3550 processor = SCHED(choose_processor)(pset, PROCESSOR_NULL, thread);
3551 }
3552 else
3553 if (thread->last_processor != PROCESSOR_NULL) {
3554 /*
3555 * Simple (last processor) affinity case.
3556 */
3557 processor = thread->last_processor;
3558 pset = processor->processor_set;
3559 pset_lock(pset);
3560 processor = SCHED(choose_processor)(pset, processor, thread);
3561
3562 if ((thread->last_processor != processor) && (thread->last_processor != PROCESSOR_NULL)) {
3563 KERNEL_DEBUG_CONSTANT(MACHDBG_CODE(DBG_MACH_SCHED, MACH_SCHED_LPA_BROKEN)|DBG_FUNC_NONE,
3564 (uintptr_t)thread_tid(thread), (uintptr_t)thread->last_processor->cpu_id, (uintptr_t)processor->cpu_id, thread->last_processor->state, 0);
3565 }
3566
3567 }
3568 else {
3569 /*
3570 * No Affinity case:
3571 *
3572 * Utilitize a per task hint to spread threads
3573 * among the available processor sets.
3574 */
3575 task_t task = thread->task;
3576
3577 pset = task->pset_hint;
3578 if (pset == PROCESSOR_SET_NULL)
3579 pset = current_processor()->processor_set;
3580
3581 pset = choose_next_pset(pset);
3582 pset_lock(pset);
3583
3584 processor = SCHED(choose_processor)(pset, PROCESSOR_NULL, thread);
3585 task->pset_hint = processor->processor_set;
3586 }
3587 }
3588 else {
3589 /*
3590 * Bound case:
3591 *
3592 * Unconditionally dispatch on the processor.
3593 */
3594 processor = thread->bound_processor;
3595 pset = processor->processor_set;
3596 pset_lock(pset);
3597 }
3598
3599 /*
3600 * Dispatch the thread on the choosen processor.
3601 */
3602 if (thread->sched_pri >= BASEPRI_RTQUEUES)
3603 realtime_setrun(processor, thread);
3604 else if (thread->sched_mode == TH_MODE_FAIRSHARE)
3605 fairshare_setrun(processor, thread);
3606 else
3607 processor_setrun(processor, thread, options);
3608 }
3609
3610 processor_set_t
3611 task_choose_pset(
3612 task_t task)
3613 {
3614 processor_set_t pset = task->pset_hint;
3615
3616 if (pset != PROCESSOR_SET_NULL)
3617 pset = choose_next_pset(pset);
3618
3619 return (pset);
3620 }
3621
3622 #if defined(CONFIG_SCHED_TRADITIONAL)
3623
3624 /*
3625 * processor_queue_shutdown:
3626 *
3627 * Shutdown a processor run queue by
3628 * re-dispatching non-bound threads.
3629 *
3630 * Associated pset must be locked, and is
3631 * returned unlocked.
3632 */
3633 void
3634 processor_queue_shutdown(
3635 processor_t processor)
3636 {
3637 processor_set_t pset = processor->processor_set;
3638 run_queue_t rq = runq_for_processor(processor);
3639 queue_t queue = rq->queues + rq->highq;
3640 int pri = rq->highq, count = rq->count;
3641 thread_t next, thread;
3642 queue_head_t tqueue;
3643
3644 queue_init(&tqueue);
3645
3646 while (count > 0) {
3647 thread = (thread_t)queue_first(queue);
3648 while (!queue_end(queue, (queue_entry_t)thread)) {
3649 next = (thread_t)queue_next((queue_entry_t)thread);
3650
3651 if (thread->bound_processor == PROCESSOR_NULL) {
3652 remqueue((queue_entry_t)thread);
3653
3654 thread->runq = PROCESSOR_NULL;
3655 SCHED_STATS_RUNQ_CHANGE(&rq->runq_stats, rq->count);
3656 runq_consider_decr_bound_count(processor, thread);
3657 rq->count--;
3658 if (SCHED(priority_is_urgent)(pri)) {
3659 rq->urgency--; assert(rq->urgency >= 0);
3660 }
3661 if (queue_empty(queue)) {
3662 if (pri != IDLEPRI)
3663 clrbit(MAXPRI - pri, rq->bitmap);
3664 rq->highq = MAXPRI - ffsbit(rq->bitmap);
3665 }
3666
3667 enqueue_tail(&tqueue, (queue_entry_t)thread);
3668 }
3669 count--;
3670
3671 thread = next;
3672 }
3673
3674 queue--; pri--;
3675 }
3676
3677 pset_unlock(pset);
3678
3679 while ((thread = (thread_t)dequeue_head(&tqueue)) != THREAD_NULL) {
3680 thread_lock(thread);
3681
3682 thread_setrun(thread, SCHED_TAILQ);
3683
3684 thread_unlock(thread);
3685 }
3686 }
3687
3688 #endif /* CONFIG_SCHED_TRADITIONAL */
3689
3690 /*
3691 * Check for a preemption point in
3692 * the current context.
3693 *
3694 * Called at splsched.
3695 */
3696 ast_t
3697 csw_check(
3698 processor_t processor)
3699 {
3700 ast_t result = AST_NONE;
3701 thread_t thread = processor->active_thread;
3702
3703 if (first_timeslice(processor)) {
3704 if (rt_runq.count > 0)
3705 return (AST_PREEMPT | AST_URGENT);
3706 }
3707 else {
3708 if (rt_runq.count > 0 && BASEPRI_RTQUEUES >= processor->current_pri)
3709 return (AST_PREEMPT | AST_URGENT);
3710 }
3711
3712 result = SCHED(processor_csw_check)(processor);
3713 if (result != AST_NONE)
3714 return (result);
3715
3716 if (SCHED(should_current_thread_rechoose_processor)(processor))
3717 return (AST_PREEMPT);
3718
3719 if (machine_processor_is_inactive(processor))
3720 return (AST_PREEMPT);
3721
3722 if (thread->state & TH_SUSP)
3723 return (AST_PREEMPT);
3724
3725 return (AST_NONE);
3726 }
3727
3728 /*
3729 * set_sched_pri:
3730 *
3731 * Set the scheduled priority of the specified thread.
3732 *
3733 * This may cause the thread to change queues.
3734 *
3735 * Thread must be locked.
3736 */
3737 void
3738 set_sched_pri(
3739 thread_t thread,
3740 int priority)
3741 {
3742 boolean_t removed = thread_run_queue_remove(thread);
3743
3744 thread->sched_pri = priority;
3745 if (removed)
3746 thread_setrun(thread, SCHED_PREEMPT | SCHED_TAILQ);
3747 else
3748 if (thread->state & TH_RUN) {
3749 processor_t processor = thread->last_processor;
3750
3751 if (thread == current_thread()) {
3752 ast_t preempt;
3753
3754 processor->current_pri = priority;
3755 processor->current_thmode = thread->sched_mode;
3756 if ((preempt = csw_check(processor)) != AST_NONE)
3757 ast_on(preempt);
3758 }
3759 else
3760 if ( processor != PROCESSOR_NULL &&
3761 processor->active_thread == thread )
3762 cause_ast_check(processor);
3763 }
3764 }
3765
3766 #if 0
3767
3768 static void
3769 run_queue_check(
3770 run_queue_t rq,
3771 thread_t thread)
3772 {
3773 queue_t q;
3774 queue_entry_t qe;
3775
3776 if (rq != thread->runq)
3777 panic("run_queue_check: thread runq");
3778
3779 if (thread->sched_pri > MAXPRI || thread->sched_pri < MINPRI)
3780 panic("run_queue_check: thread sched_pri");
3781
3782 q = &rq->queues[thread->sched_pri];
3783 qe = queue_first(q);
3784 while (!queue_end(q, qe)) {
3785 if (qe == (queue_entry_t)thread)
3786 return;
3787
3788 qe = queue_next(qe);
3789 }
3790
3791 panic("run_queue_check: end");
3792 }
3793
3794 #endif /* DEBUG */
3795
3796 #if defined(CONFIG_SCHED_TRADITIONAL)
3797
3798 /* locks the runqueue itself */
3799
3800 static boolean_t
3801 processor_queue_remove(
3802 processor_t processor,
3803 thread_t thread)
3804 {
3805 void * rqlock;
3806 run_queue_t rq;
3807
3808 rqlock = &processor->processor_set->sched_lock;
3809 rq = runq_for_processor(processor);
3810
3811 simple_lock(rqlock);
3812 if (processor == thread->runq) {
3813 /*
3814 * Thread is on a run queue and we have a lock on
3815 * that run queue.
3816 */
3817 runq_consider_decr_bound_count(processor, thread);
3818 run_queue_remove(rq, thread);
3819 }
3820 else {
3821 /*
3822 * The thread left the run queue before we could
3823 * lock the run queue.
3824 */
3825 assert(thread->runq == PROCESSOR_NULL);
3826 processor = PROCESSOR_NULL;
3827 }
3828
3829 simple_unlock(rqlock);
3830
3831 return (processor != PROCESSOR_NULL);
3832 }
3833
3834 #endif /* CONFIG_SCHED_TRADITIONAL */
3835
3836 /*
3837 * thread_run_queue_remove:
3838 *
3839 * Remove a thread from a current run queue and
3840 * return TRUE if successful.
3841 *
3842 * Thread must be locked.
3843 */
3844 boolean_t
3845 thread_run_queue_remove(
3846 thread_t thread)
3847 {
3848 processor_t processor = thread->runq;
3849
3850 /*
3851 * If processor is PROCESSOR_NULL, the thread will stay out of the
3852 * run queues because the caller locked the thread. Otherwise
3853 * the thread is on a run queue, but could be chosen for dispatch
3854 * and removed.
3855 */
3856 if (processor != PROCESSOR_NULL) {
3857 queue_t q;
3858
3859 /*
3860 * The processor run queues are locked by the
3861 * processor set. Real-time priorities use a
3862 * global queue with a dedicated lock.
3863 */
3864 if (thread->sched_mode == TH_MODE_FAIRSHARE) {
3865 return SCHED(fairshare_queue_remove)(thread);
3866 }
3867
3868 if (thread->sched_pri < BASEPRI_RTQUEUES) {
3869 return SCHED(processor_queue_remove)(processor, thread);
3870 }
3871
3872 simple_lock(&rt_lock);
3873 q = &rt_runq.queue;
3874
3875 if (processor == thread->runq) {
3876 /*
3877 * Thread is on a run queue and we have a lock on
3878 * that run queue.
3879 */
3880 remqueue((queue_entry_t)thread);
3881 SCHED_STATS_RUNQ_CHANGE(&rt_runq.runq_stats, rt_runq.count);
3882 rt_runq.count--;
3883
3884 thread->runq = PROCESSOR_NULL;
3885 }
3886 else {
3887 /*
3888 * The thread left the run queue before we could
3889 * lock the run queue.
3890 */
3891 assert(thread->runq == PROCESSOR_NULL);
3892 processor = PROCESSOR_NULL;
3893 }
3894
3895 simple_unlock(&rt_lock);
3896 }
3897
3898 return (processor != PROCESSOR_NULL);
3899 }
3900
3901 #if defined(CONFIG_SCHED_TRADITIONAL)
3902
3903 /*
3904 * steal_processor_thread:
3905 *
3906 * Locate a thread to steal from the processor and
3907 * return it.
3908 *
3909 * Associated pset must be locked. Returns THREAD_NULL
3910 * on failure.
3911 */
3912 static thread_t
3913 steal_processor_thread(
3914 processor_t processor)
3915 {
3916 run_queue_t rq = runq_for_processor(processor);
3917 queue_t queue = rq->queues + rq->highq;
3918 int pri = rq->highq, count = rq->count;
3919 thread_t thread;
3920
3921 while (count > 0) {
3922 thread = (thread_t)queue_first(queue);
3923 while (!queue_end(queue, (queue_entry_t)thread)) {
3924 if (thread->bound_processor == PROCESSOR_NULL) {
3925 remqueue((queue_entry_t)thread);
3926
3927 thread->runq = PROCESSOR_NULL;
3928 SCHED_STATS_RUNQ_CHANGE(&rq->runq_stats, rq->count);
3929 runq_consider_decr_bound_count(processor, thread);
3930 rq->count--;
3931 if (SCHED(priority_is_urgent)(pri)) {
3932 rq->urgency--; assert(rq->urgency >= 0);
3933 }
3934 if (queue_empty(queue)) {
3935 if (pri != IDLEPRI)
3936 clrbit(MAXPRI - pri, rq->bitmap);
3937 rq->highq = MAXPRI - ffsbit(rq->bitmap);
3938 }
3939
3940 return (thread);
3941 }
3942 count--;
3943
3944 thread = (thread_t)queue_next((queue_entry_t)thread);
3945 }
3946
3947 queue--; pri--;
3948 }
3949
3950 return (THREAD_NULL);
3951 }
3952
3953 /*
3954 * Locate and steal a thread, beginning
3955 * at the pset.
3956 *
3957 * The pset must be locked, and is returned
3958 * unlocked.
3959 *
3960 * Returns the stolen thread, or THREAD_NULL on
3961 * failure.
3962 */
3963 static thread_t
3964 steal_thread(
3965 processor_set_t pset)
3966 {
3967 processor_set_t nset, cset = pset;
3968 processor_t processor;
3969 thread_t thread;
3970
3971 do {
3972 processor = (processor_t)queue_first(&cset->active_queue);
3973 while (!queue_end(&cset->active_queue, (queue_entry_t)processor)) {
3974 if (runq_for_processor(processor)->count > 0) {
3975 thread = steal_processor_thread(processor);
3976 if (thread != THREAD_NULL) {
3977 remqueue((queue_entry_t)processor);
3978 enqueue_tail(&cset->active_queue, (queue_entry_t)processor);
3979
3980 pset_unlock(cset);
3981
3982 return (thread);
3983 }
3984 }
3985
3986 processor = (processor_t)queue_next((queue_entry_t)processor);
3987 }
3988
3989 nset = next_pset(cset);
3990
3991 if (nset != pset) {
3992 pset_unlock(cset);
3993
3994 cset = nset;
3995 pset_lock(cset);
3996 }
3997 } while (nset != pset);
3998
3999 pset_unlock(cset);
4000
4001 return (THREAD_NULL);
4002 }
4003
4004 static thread_t steal_thread_disabled(
4005 processor_set_t pset)
4006 {
4007 pset_unlock(pset);
4008
4009 return (THREAD_NULL);
4010 }
4011
4012 #endif /* CONFIG_SCHED_TRADITIONAL */
4013
4014
4015 int
4016 thread_get_urgency(uint64_t *rt_period, uint64_t *rt_deadline)
4017 {
4018 processor_t processor;
4019 thread_t thread;
4020
4021 processor = current_processor();
4022
4023 thread = processor->next_thread;
4024
4025 if (thread != NULL) {
4026 if (thread->sched_mode == TH_MODE_REALTIME) {
4027
4028 if (rt_period != NULL)
4029 *rt_period = thread->realtime.period;
4030 if (rt_deadline != NULL)
4031 *rt_deadline = thread->realtime.deadline;
4032
4033 KERNEL_DEBUG(MACHDBG_CODE(DBG_MACH_SCHED, MACH_SCHED_GET_URGENCY), THREAD_URGENCY_REAL_TIME, thread->realtime.period,
4034 (thread->realtime.deadline >> 32), thread->realtime.deadline, 0);
4035
4036 return (THREAD_URGENCY_REAL_TIME);
4037 } else if ((thread->sched_pri <= MAXPRI_THROTTLE) &&
4038 (thread->priority <= MAXPRI_THROTTLE)) {
4039 KERNEL_DEBUG(MACHDBG_CODE(DBG_MACH_SCHED, MACH_SCHED_GET_URGENCY), THREAD_URGENCY_BACKGROUND, thread->sched_pri, thread->priority, 0, 0);
4040 return (THREAD_URGENCY_BACKGROUND);
4041 }
4042 else
4043 KERNEL_DEBUG(MACHDBG_CODE(DBG_MACH_SCHED, MACH_SCHED_GET_URGENCY), THREAD_URGENCY_NORMAL, 0, 0, 0, 0);
4044
4045 return (THREAD_URGENCY_NORMAL);
4046 }
4047 else
4048 KERNEL_DEBUG(MACHDBG_CODE(DBG_MACH_SCHED, MACH_SCHED_GET_URGENCY), THREAD_URGENCY_NONE, 0, 0, 0, 0);
4049 return (THREAD_URGENCY_NONE);
4050 }
4051
4052
4053 /*
4054 * This is the processor idle loop, which just looks for other threads
4055 * to execute. Processor idle threads invoke this without supplying a
4056 * current thread to idle without an asserted wait state.
4057 *
4058 * Returns a the next thread to execute if dispatched directly.
4059 */
4060
4061 #if 0
4062 #define IDLE_KERNEL_DEBUG_CONSTANT(...) KERNEL_DEBUG_CONSTANT(__VA_ARGS__)
4063 #else
4064 #define IDLE_KERNEL_DEBUG_CONSTANT(...) do { } while(0)
4065 #endif
4066
4067 thread_t
4068 processor_idle(
4069 thread_t thread,
4070 processor_t processor)
4071 {
4072 processor_set_t pset = processor->processor_set;
4073 thread_t new_thread;
4074 int state;
4075 (void)splsched();
4076
4077 KERNEL_DEBUG_CONSTANT_IST(KDEBUG_TRACE,
4078 MACHDBG_CODE(DBG_MACH_SCHED,MACH_IDLE) | DBG_FUNC_START,
4079 (uintptr_t)thread_tid(thread), 0, 0, 0, 0);
4080
4081 SCHED_STATS_CPU_IDLE_START(processor);
4082
4083 timer_switch(&PROCESSOR_DATA(processor, system_state),
4084 mach_absolute_time(), &PROCESSOR_DATA(processor, idle_state));
4085 PROCESSOR_DATA(processor, current_state) = &PROCESSOR_DATA(processor, idle_state);
4086
4087 while (processor->next_thread == THREAD_NULL && SCHED(processor_queue_empty)(processor) && rt_runq.count == 0 && SCHED(fairshare_runq_count)() == 0 &&
4088 (thread == THREAD_NULL || ((thread->state & (TH_WAIT|TH_SUSP)) == TH_WAIT && !thread->wake_active))) {
4089 IDLE_KERNEL_DEBUG_CONSTANT(
4090 MACHDBG_CODE(DBG_MACH_SCHED,MACH_IDLE) | DBG_FUNC_NONE, (uintptr_t)thread_tid(thread), rt_runq.count, SCHED(processor_runq_count)(processor), -1, 0);
4091
4092 machine_track_platform_idle(TRUE);
4093
4094 machine_idle();
4095
4096 machine_track_platform_idle(FALSE);
4097
4098 (void)splsched();
4099
4100 IDLE_KERNEL_DEBUG_CONSTANT(
4101 MACHDBG_CODE(DBG_MACH_SCHED,MACH_IDLE) | DBG_FUNC_NONE, (uintptr_t)thread_tid(thread), rt_runq.count, SCHED(processor_runq_count)(processor), -2, 0);
4102
4103 if (processor->state == PROCESSOR_INACTIVE && !machine_processor_is_inactive(processor))
4104 break;
4105 }
4106
4107 timer_switch(&PROCESSOR_DATA(processor, idle_state),
4108 mach_absolute_time(), &PROCESSOR_DATA(processor, system_state));
4109 PROCESSOR_DATA(processor, current_state) = &PROCESSOR_DATA(processor, system_state);
4110
4111 pset_lock(pset);
4112
4113 state = processor->state;
4114 if (state == PROCESSOR_DISPATCHING) {
4115 /*
4116 * Commmon case -- cpu dispatched.
4117 */
4118 new_thread = processor->next_thread;
4119 processor->next_thread = THREAD_NULL;
4120 processor->state = PROCESSOR_RUNNING;
4121
4122 if (SCHED(processor_queue_has_priority)(processor, new_thread->sched_pri, FALSE) ||
4123 (rt_runq.count > 0 && BASEPRI_RTQUEUES >= new_thread->sched_pri) ) {
4124 processor->deadline = UINT64_MAX;
4125
4126 pset_unlock(pset);
4127
4128 thread_lock(new_thread);
4129 KERNEL_DEBUG_CONSTANT(MACHDBG_CODE(DBG_MACH_SCHED, MACH_REDISPATCH), (uintptr_t)thread_tid(new_thread), new_thread->sched_pri, rt_runq.count, 0, 0);
4130 thread_setrun(new_thread, SCHED_HEADQ);
4131 thread_unlock(new_thread);
4132
4133 KERNEL_DEBUG_CONSTANT_IST(KDEBUG_TRACE,
4134 MACHDBG_CODE(DBG_MACH_SCHED,MACH_IDLE) | DBG_FUNC_END,
4135 (uintptr_t)thread_tid(thread), state, 0, 0, 0);
4136
4137 return (THREAD_NULL);
4138 }
4139
4140 pset_unlock(pset);
4141
4142 KERNEL_DEBUG_CONSTANT_IST(KDEBUG_TRACE,
4143 MACHDBG_CODE(DBG_MACH_SCHED,MACH_IDLE) | DBG_FUNC_END,
4144 (uintptr_t)thread_tid(thread), state, (uintptr_t)thread_tid(new_thread), 0, 0);
4145
4146 return (new_thread);
4147 }
4148 else
4149 if (state == PROCESSOR_IDLE) {
4150 remqueue((queue_entry_t)processor);
4151
4152 processor->state = PROCESSOR_RUNNING;
4153 enqueue_tail(&pset->active_queue, (queue_entry_t)processor);
4154 }
4155 else
4156 if (state == PROCESSOR_INACTIVE) {
4157 processor->state = PROCESSOR_RUNNING;
4158 enqueue_tail(&pset->active_queue, (queue_entry_t)processor);
4159 }
4160 else
4161 if (state == PROCESSOR_SHUTDOWN) {
4162 /*
4163 * Going off-line. Force a
4164 * reschedule.
4165 */
4166 if ((new_thread = processor->next_thread) != THREAD_NULL) {
4167 processor->next_thread = THREAD_NULL;
4168 processor->deadline = UINT64_MAX;
4169
4170 pset_unlock(pset);
4171
4172 thread_lock(new_thread);
4173 thread_setrun(new_thread, SCHED_HEADQ);
4174 thread_unlock(new_thread);
4175
4176 KERNEL_DEBUG_CONSTANT_IST(KDEBUG_TRACE,
4177 MACHDBG_CODE(DBG_MACH_SCHED,MACH_IDLE) | DBG_FUNC_END,
4178 (uintptr_t)thread_tid(thread), state, 0, 0, 0);
4179
4180 return (THREAD_NULL);
4181 }
4182 }
4183
4184 pset_unlock(pset);
4185
4186 KERNEL_DEBUG_CONSTANT_IST(KDEBUG_TRACE,
4187 MACHDBG_CODE(DBG_MACH_SCHED,MACH_IDLE) | DBG_FUNC_END,
4188 (uintptr_t)thread_tid(thread), state, 0, 0, 0);
4189
4190 return (THREAD_NULL);
4191 }
4192
4193 /*
4194 * Each processor has a dedicated thread which
4195 * executes the idle loop when there is no suitable
4196 * previous context.
4197 */
4198 void
4199 idle_thread(void)
4200 {
4201 processor_t processor = current_processor();
4202 thread_t new_thread;
4203
4204 new_thread = processor_idle(THREAD_NULL, processor);
4205 if (new_thread != THREAD_NULL) {
4206 thread_run(processor->idle_thread, (thread_continue_t)idle_thread, NULL, new_thread);
4207 /*NOTREACHED*/
4208 }
4209
4210 thread_block((thread_continue_t)idle_thread);
4211 /*NOTREACHED*/
4212 }
4213
4214 kern_return_t
4215 idle_thread_create(
4216 processor_t processor)
4217 {
4218 kern_return_t result;
4219 thread_t thread;
4220 spl_t s;
4221
4222 result = kernel_thread_create((thread_continue_t)idle_thread, NULL, MAXPRI_KERNEL, &thread);
4223 if (result != KERN_SUCCESS)
4224 return (result);
4225
4226 s = splsched();
4227 thread_lock(thread);
4228 thread->bound_processor = processor;
4229 processor->idle_thread = thread;
4230 thread->sched_pri = thread->priority = IDLEPRI;
4231 thread->state = (TH_RUN | TH_IDLE);
4232 thread_unlock(thread);
4233 splx(s);
4234
4235 thread_deallocate(thread);
4236
4237 return (KERN_SUCCESS);
4238 }
4239
4240 /*
4241 * sched_startup:
4242 *
4243 * Kicks off scheduler services.
4244 *
4245 * Called at splsched.
4246 */
4247 void
4248 sched_startup(void)
4249 {
4250 kern_return_t result;
4251 thread_t thread;
4252
4253 result = kernel_thread_start_priority((thread_continue_t)sched_init_thread,
4254 (void *)SCHED(maintenance_continuation),
4255 MAXPRI_KERNEL, &thread);
4256 if (result != KERN_SUCCESS)
4257 panic("sched_startup");
4258
4259 thread_deallocate(thread);
4260
4261 /*
4262 * Yield to the sched_init_thread once, to
4263 * initialize our own thread after being switched
4264 * back to.
4265 *
4266 * The current thread is the only other thread
4267 * active at this point.
4268 */
4269 thread_block(THREAD_CONTINUE_NULL);
4270 }
4271
4272 #if defined(CONFIG_SCHED_TRADITIONAL)
4273
4274 static uint64_t sched_tick_deadline = 0;
4275
4276 /*
4277 * sched_init_thread:
4278 *
4279 * Perform periodic bookkeeping functions about ten
4280 * times per second.
4281 */
4282 static void
4283 sched_traditional_tick_continue(void)
4284 {
4285 uint64_t abstime = mach_absolute_time();
4286
4287 sched_tick++;
4288
4289 /*
4290 * Compute various averages.
4291 */
4292 compute_averages();
4293
4294 /*
4295 * Scan the run queues for threads which
4296 * may need to be updated.
4297 */
4298 thread_update_scan();
4299
4300 if (sched_tick_deadline == 0)
4301 sched_tick_deadline = abstime;
4302
4303 clock_deadline_for_periodic_event(sched_tick_interval, abstime,
4304 &sched_tick_deadline);
4305
4306 assert_wait_deadline((event_t)sched_traditional_tick_continue, THREAD_UNINT, sched_tick_deadline);
4307 thread_block((thread_continue_t)sched_traditional_tick_continue);
4308 /*NOTREACHED*/
4309 }
4310
4311 #endif /* CONFIG_SCHED_TRADITIONAL */
4312
4313 void
4314 sched_init_thread(void (*continuation)(void))
4315 {
4316 thread_block(THREAD_CONTINUE_NULL);
4317
4318 continuation();
4319
4320 /*NOTREACHED*/
4321 }
4322
4323 #if defined(CONFIG_SCHED_TRADITIONAL)
4324
4325 /*
4326 * thread_update_scan / runq_scan:
4327 *
4328 * Scan the run queues to account for timesharing threads
4329 * which need to be updated.
4330 *
4331 * Scanner runs in two passes. Pass one squirrels likely
4332 * threads away in an array, pass two does the update.
4333 *
4334 * This is necessary because the run queue is locked for
4335 * the candidate scan, but the thread is locked for the update.
4336 *
4337 * Array should be sized to make forward progress, without
4338 * disabling preemption for long periods.
4339 */
4340
4341 #define THREAD_UPDATE_SIZE 128
4342
4343 static thread_t thread_update_array[THREAD_UPDATE_SIZE];
4344 static int thread_update_count = 0;
4345
4346 /*
4347 * Scan a runq for candidate threads.
4348 *
4349 * Returns TRUE if retry is needed.
4350 */
4351 static boolean_t
4352 runq_scan(
4353 run_queue_t runq)
4354 {
4355 register int count;
4356 register queue_t q;
4357 register thread_t thread;
4358
4359 if ((count = runq->count) > 0) {
4360 q = runq->queues + runq->highq;
4361 while (count > 0) {
4362 queue_iterate(q, thread, thread_t, links) {
4363 if ( thread->sched_stamp != sched_tick &&
4364 (thread->sched_mode == TH_MODE_TIMESHARE) ) {
4365 if (thread_update_count == THREAD_UPDATE_SIZE)
4366 return (TRUE);
4367
4368 thread_update_array[thread_update_count++] = thread;
4369 thread_reference_internal(thread);
4370 }
4371
4372 count--;
4373 }
4374
4375 q--;
4376 }
4377 }
4378
4379 return (FALSE);
4380 }
4381
4382 static void
4383 thread_update_scan(void)
4384 {
4385 boolean_t restart_needed = FALSE;
4386 processor_t processor = processor_list;
4387 processor_set_t pset;
4388 thread_t thread;
4389 spl_t s;
4390
4391 do {
4392 do {
4393 pset = processor->processor_set;
4394
4395 s = splsched();
4396 pset_lock(pset);
4397
4398 restart_needed = runq_scan(runq_for_processor(processor));
4399
4400 pset_unlock(pset);
4401 splx(s);
4402
4403 if (restart_needed)
4404 break;
4405
4406 thread = processor->idle_thread;
4407 if (thread != THREAD_NULL && thread->sched_stamp != sched_tick) {
4408 if (thread_update_count == THREAD_UPDATE_SIZE) {
4409 restart_needed = TRUE;
4410 break;
4411 }
4412
4413 thread_update_array[thread_update_count++] = thread;
4414 thread_reference_internal(thread);
4415 }
4416 } while ((processor = processor->processor_list) != NULL);
4417
4418 /*
4419 * Ok, we now have a collection of candidates -- fix them.
4420 */
4421 while (thread_update_count > 0) {
4422 thread = thread_update_array[--thread_update_count];
4423 thread_update_array[thread_update_count] = THREAD_NULL;
4424
4425 s = splsched();
4426 thread_lock(thread);
4427 if ( !(thread->state & (TH_WAIT)) ) {
4428 if (SCHED(can_update_priority)(thread))
4429 SCHED(update_priority)(thread);
4430 }
4431 thread_unlock(thread);
4432 splx(s);
4433
4434 thread_deallocate(thread);
4435 }
4436 } while (restart_needed);
4437 }
4438
4439 #endif /* CONFIG_SCHED_TRADITIONAL */
4440
4441 boolean_t
4442 thread_eager_preemption(thread_t thread)
4443 {
4444 return ((thread->sched_flags & TH_SFLAG_EAGERPREEMPT) != 0);
4445 }
4446
4447 void
4448 thread_set_eager_preempt(thread_t thread)
4449 {
4450 spl_t x;
4451 processor_t p;
4452 ast_t ast = AST_NONE;
4453
4454 x = splsched();
4455 p = current_processor();
4456
4457 thread_lock(thread);
4458 thread->sched_flags |= TH_SFLAG_EAGERPREEMPT;
4459
4460 if (thread == current_thread()) {
4461 thread_unlock(thread);
4462
4463 ast = csw_check(p);
4464 if (ast != AST_NONE) {
4465 (void) thread_block_reason(THREAD_CONTINUE_NULL, NULL, ast);
4466 }
4467 } else {
4468 p = thread->last_processor;
4469
4470 if (p != PROCESSOR_NULL && p->state == PROCESSOR_RUNNING &&
4471 p->active_thread == thread) {
4472 cause_ast_check(p);
4473 }
4474
4475 thread_unlock(thread);
4476 }
4477
4478 splx(x);
4479 }
4480
4481 void
4482 thread_clear_eager_preempt(thread_t thread)
4483 {
4484 spl_t x;
4485
4486 x = splsched();
4487 thread_lock(thread);
4488
4489 thread->sched_flags &= ~TH_SFLAG_EAGERPREEMPT;
4490
4491 thread_unlock(thread);
4492 splx(x);
4493 }
4494 /*
4495 * Scheduling statistics
4496 */
4497 void
4498 sched_stats_handle_csw(processor_t processor, int reasons, int selfpri, int otherpri)
4499 {
4500 struct processor_sched_statistics *stats;
4501 boolean_t to_realtime = FALSE;
4502
4503 stats = &processor->processor_data.sched_stats;
4504 stats->csw_count++;
4505
4506 if (otherpri >= BASEPRI_REALTIME) {
4507 stats->rt_sched_count++;
4508 to_realtime = TRUE;
4509 }
4510
4511 if ((reasons & AST_PREEMPT) != 0) {
4512 stats->preempt_count++;
4513
4514 if (selfpri >= BASEPRI_REALTIME) {
4515 stats->preempted_rt_count++;
4516 }
4517
4518 if (to_realtime) {
4519 stats->preempted_by_rt_count++;
4520 }
4521
4522 }
4523 }
4524
4525 void
4526 sched_stats_handle_runq_change(struct runq_stats *stats, int old_count)
4527 {
4528 uint64_t timestamp = mach_absolute_time();
4529
4530 stats->count_sum += (timestamp - stats->last_change_timestamp) * old_count;
4531 stats->last_change_timestamp = timestamp;
4532 }
4533
4534 /*
4535 * For calls from assembly code
4536 */
4537 #undef thread_wakeup
4538 void
4539 thread_wakeup(
4540 event_t x);
4541
4542 void
4543 thread_wakeup(
4544 event_t x)
4545 {
4546 thread_wakeup_with_result(x, THREAD_AWAKENED);
4547 }
4548
4549 boolean_t
4550 preemption_enabled(void)
4551 {
4552 return (get_preemption_level() == 0 && ml_get_interrupts_enabled());
4553 }
4554
4555 #if DEBUG
4556 static boolean_t
4557 thread_runnable(
4558 thread_t thread)
4559 {
4560 return ((thread->state & (TH_RUN|TH_WAIT)) == TH_RUN);
4561 }
4562 #endif /* DEBUG */
4563
4564 static void
4565 sched_timer_deadline_tracking_init(void) {
4566 nanoseconds_to_absolutetime(TIMER_DEADLINE_TRACKING_BIN_1_DEFAULT, &timer_deadline_tracking_bin_1);
4567 nanoseconds_to_absolutetime(TIMER_DEADLINE_TRACKING_BIN_2_DEFAULT, &timer_deadline_tracking_bin_2);
4568 }
mirror of XNU