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


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