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


dddaf47d77abf85a62f357695bc95ce278e75f35
[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
77 #include <machine/machine_routines.h>
78 #include <machine/sched_param.h>
79 #include <machine/machine_cpu.h>
80
81 #include <kern/kern_types.h>
82 #include <kern/clock.h>
83 #include <kern/counters.h>
84 #include <kern/cpu_number.h>
85 #include <kern/cpu_data.h>
86 #include <kern/debug.h>
87 #include <kern/lock.h>
88 #include <kern/macro_help.h>
89 #include <kern/machine.h>
90 #include <kern/misc_protos.h>
91 #include <kern/processor.h>
92 #include <kern/queue.h>
93 #include <kern/sched.h>
94 #include <kern/sched_prim.h>
95 #include <kern/syscall_subr.h>
96 #include <kern/task.h>
97 #include <kern/thread.h>
98 #include <kern/wait_queue.h>
99
100 #include <vm/pmap.h>
101 #include <vm/vm_kern.h>
102 #include <vm/vm_map.h>
103
104 #include <mach/sdt.h>
105
106 #include <sys/kdebug.h>
107
108 #include <kern/pms.h>
109
110 struct run_queue rt_runq;
111 #define RT_RUNQ ((processor_t)-1)
112 decl_simple_lock_data(static,rt_lock);
113
114 #define DEFAULT_PREEMPTION_RATE 100 /* (1/s) */
115 int default_preemption_rate = DEFAULT_PREEMPTION_RATE;
116
117 #define MAX_UNSAFE_QUANTA 800
118 int max_unsafe_quanta = MAX_UNSAFE_QUANTA;
119
120 #define MAX_POLL_QUANTA 2
121 int max_poll_quanta = MAX_POLL_QUANTA;
122
123 #define SCHED_POLL_YIELD_SHIFT 4 /* 1/16 */
124 int sched_poll_yield_shift = SCHED_POLL_YIELD_SHIFT;
125
126 uint64_t max_unsafe_computation;
127 uint32_t sched_safe_duration;
128 uint64_t max_poll_computation;
129
130 uint32_t std_quantum;
131 uint32_t min_std_quantum;
132
133 uint32_t std_quantum_us;
134
135 uint32_t max_rt_quantum;
136 uint32_t min_rt_quantum;
137
138 uint32_t sched_cswtime;
139
140 unsigned sched_tick;
141 uint32_t sched_tick_interval;
142
143 uint32_t sched_pri_shift = INT8_MAX;
144 uint32_t sched_fixed_shift;
145
146 uint32_t sched_run_count, sched_share_count;
147 uint32_t sched_load_average, sched_mach_factor;
148
149 /* Forwards */
150 static void load_shift_init(void) __attribute__((section("__TEXT, initcode")));
151 static void preempt_pri_init(void) __attribute__((section("__TEXT, initcode")));
152
153 static thread_t run_queue_dequeue(
154 run_queue_t runq,
155 integer_t options);
156
157 static thread_t choose_thread(
158 processor_t processor,
159 int priority);
160
161 static thread_t thread_select_idle(
162 thread_t thread,
163 processor_t processor);
164
165 static thread_t processor_idle(
166 thread_t thread,
167 processor_t processor);
168
169 static thread_t steal_thread(
170 processor_set_t pset);
171
172 static thread_t steal_processor_thread(
173 processor_t processor);
174
175 static void thread_update_scan(void);
176
177 #if DEBUG
178 extern int debug_task;
179 #define TLOG(a, fmt, args...) if(debug_task & a) kprintf(fmt, ## args)
180 #else
181 #define TLOG(a, fmt, args...) do {} while (0)
182 #endif
183
184 #if DEBUG
185 static
186 boolean_t thread_runnable(
187 thread_t thread);
188
189 #endif /*DEBUG*/
190
191 /*
192 * State machine
193 *
194 * states are combinations of:
195 * R running
196 * W waiting (or on wait queue)
197 * N non-interruptible
198 * O swapped out
199 * I being swapped in
200 *
201 * init action
202 * assert_wait thread_block clear_wait swapout swapin
203 *
204 * R RW, RWN R; setrun - -
205 * RN RWN RN; setrun - -
206 *
207 * RW W R -
208 * RWN WN RN -
209 *
210 * W R; setrun WO
211 * WN RN; setrun -
212 *
213 * RO - - R
214 *
215 */
216
217 int8_t sched_load_shifts[NRQS];
218 int sched_preempt_pri[NRQBM];
219
220 void
221 sched_init(void)
222 {
223 /*
224 * Calculate the timeslicing quantum
225 * in us.
226 */
227 if (default_preemption_rate < 1)
228 default_preemption_rate = DEFAULT_PREEMPTION_RATE;
229 std_quantum_us = (1000 * 1000) / default_preemption_rate;
230
231 printf("standard timeslicing quantum is %d us\n", std_quantum_us);
232
233 sched_safe_duration = (2 * max_unsafe_quanta / default_preemption_rate) *
234 (1 << SCHED_TICK_SHIFT);
235
236 load_shift_init();
237 preempt_pri_init();
238 simple_lock_init(&rt_lock, 0);
239 run_queue_init(&rt_runq);
240 sched_tick = 0;
241 ast_init();
242 }
243
244 void
245 sched_timebase_init(void)
246 {
247 uint64_t abstime;
248 uint32_t shift;
249
250 /* standard timeslicing quantum */
251 clock_interval_to_absolutetime_interval(
252 std_quantum_us, NSEC_PER_USEC, &abstime);
253 assert((abstime >> 32) == 0 && (uint32_t)abstime != 0);
254 std_quantum = (uint32_t)abstime;
255
256 /* smallest remaining quantum (250 us) */
257 clock_interval_to_absolutetime_interval(250, NSEC_PER_USEC, &abstime);
258 assert((abstime >> 32) == 0 && (uint32_t)abstime != 0);
259 min_std_quantum = (uint32_t)abstime;
260
261 /* smallest rt computaton (50 us) */
262 clock_interval_to_absolutetime_interval(50, NSEC_PER_USEC, &abstime);
263 assert((abstime >> 32) == 0 && (uint32_t)abstime != 0);
264 min_rt_quantum = (uint32_t)abstime;
265
266 /* maximum rt computation (50 ms) */
267 clock_interval_to_absolutetime_interval(
268 50, 1000*NSEC_PER_USEC, &abstime);
269 assert((abstime >> 32) == 0 && (uint32_t)abstime != 0);
270 max_rt_quantum = (uint32_t)abstime;
271
272 /* scheduler tick interval */
273 clock_interval_to_absolutetime_interval(USEC_PER_SEC >> SCHED_TICK_SHIFT,
274 NSEC_PER_USEC, &abstime);
275 assert((abstime >> 32) == 0 && (uint32_t)abstime != 0);
276 sched_tick_interval = (uint32_t)abstime;
277
278 /*
279 * Compute conversion factor from usage to
280 * timesharing priorities with 5/8 ** n aging.
281 */
282 abstime = (abstime * 5) / 3;
283 for (shift = 0; abstime > BASEPRI_DEFAULT; ++shift)
284 abstime >>= 1;
285 sched_fixed_shift = shift;
286
287 max_unsafe_computation = max_unsafe_quanta * std_quantum;
288 max_poll_computation = max_poll_quanta * std_quantum;
289 }
290
291 /*
292 * Set up values for timeshare
293 * loading factors.
294 */
295 static void
296 load_shift_init(void)
297 {
298 int8_t k, *p = sched_load_shifts;
299 uint32_t i, j;
300
301 *p++ = INT8_MIN; *p++ = 0;
302
303 for (i = j = 2, k = 1; i < NRQS; ++k) {
304 for (j <<= 1; i < j; ++i)
305 *p++ = k;
306 }
307 }
308
309 static void
310 preempt_pri_init(void)
311 {
312 int i, *p = sched_preempt_pri;
313
314 for (i = BASEPRI_FOREGROUND + 1; i < MINPRI_KERNEL; ++i)
315 setbit(i, p);
316
317 for (i = BASEPRI_PREEMPT; i <= MAXPRI; ++i)
318 setbit(i, p);
319 }
320
321 /*
322 * Thread wait timer expiration.
323 */
324 void
325 thread_timer_expire(
326 void *p0,
327 __unused void *p1)
328 {
329 thread_t thread = p0;
330 spl_t s;
331
332 s = splsched();
333 thread_lock(thread);
334 if (--thread->wait_timer_active == 0) {
335 if (thread->wait_timer_is_set) {
336 thread->wait_timer_is_set = FALSE;
337 clear_wait_internal(thread, THREAD_TIMED_OUT);
338 }
339 }
340 thread_unlock(thread);
341 splx(s);
342 }
343
344 #ifndef __LP64__
345
346 /*
347 * thread_set_timer:
348 *
349 * Set a timer for the current thread, if the thread
350 * is ready to wait. Must be called between assert_wait()
351 * and thread_block().
352 */
353 void
354 thread_set_timer(
355 uint32_t interval,
356 uint32_t scale_factor)
357 {
358 thread_t thread = current_thread();
359 uint64_t deadline;
360 spl_t s;
361
362 s = splsched();
363 thread_lock(thread);
364 if ((thread->state & TH_WAIT) != 0) {
365 clock_interval_to_deadline(interval, scale_factor, &deadline);
366 if (!timer_call_enter(&thread->wait_timer, deadline))
367 thread->wait_timer_active++;
368 thread->wait_timer_is_set = TRUE;
369 }
370 thread_unlock(thread);
371 splx(s);
372 }
373
374 void
375 thread_set_timer_deadline(
376 uint64_t deadline)
377 {
378 thread_t thread = current_thread();
379 spl_t s;
380
381 s = splsched();
382 thread_lock(thread);
383 if ((thread->state & TH_WAIT) != 0) {
384 if (!timer_call_enter(&thread->wait_timer, deadline))
385 thread->wait_timer_active++;
386 thread->wait_timer_is_set = TRUE;
387 }
388 thread_unlock(thread);
389 splx(s);
390 }
391
392 void
393 thread_cancel_timer(void)
394 {
395 thread_t thread = current_thread();
396 spl_t s;
397
398 s = splsched();
399 thread_lock(thread);
400 if (thread->wait_timer_is_set) {
401 if (timer_call_cancel(&thread->wait_timer))
402 thread->wait_timer_active--;
403 thread->wait_timer_is_set = FALSE;
404 }
405 thread_unlock(thread);
406 splx(s);
407 }
408
409 #endif /* __LP64__ */
410
411 /*
412 * thread_unblock:
413 *
414 * Unblock thread on wake up.
415 *
416 * Returns TRUE if the thread is still running.
417 *
418 * Thread must be locked.
419 */
420 boolean_t
421 thread_unblock(
422 thread_t thread,
423 wait_result_t wresult)
424 {
425 boolean_t result = FALSE;
426
427 /*
428 * Set wait_result.
429 */
430 thread->wait_result = wresult;
431
432 /*
433 * Cancel pending wait timer.
434 */
435 if (thread->wait_timer_is_set) {
436 if (timer_call_cancel(&thread->wait_timer))
437 thread->wait_timer_active--;
438 thread->wait_timer_is_set = FALSE;
439 }
440
441 /*
442 * Update scheduling state: not waiting,
443 * set running.
444 */
445 thread->state &= ~(TH_WAIT|TH_UNINT);
446
447 if (!(thread->state & TH_RUN)) {
448 thread->state |= TH_RUN;
449
450 (*thread->sched_call)(SCHED_CALL_UNBLOCK, thread);
451
452 /*
453 * Update run counts.
454 */
455 sched_run_incr();
456 if (thread->sched_mode & TH_MODE_TIMESHARE)
457 sched_share_incr();
458 }
459 else {
460 /*
461 * Signal if idling on another processor.
462 */
463 if (thread->state & TH_IDLE) {
464 processor_t processor = thread->last_processor;
465
466 if (processor != current_processor())
467 machine_signal_idle(processor);
468 }
469 result = TRUE;
470 }
471
472 /*
473 * Calculate deadline for real-time threads.
474 */
475 if (thread->sched_mode & TH_MODE_REALTIME) {
476 thread->realtime.deadline = mach_absolute_time();
477 thread->realtime.deadline += thread->realtime.constraint;
478 }
479
480 /*
481 * Clear old quantum, fail-safe computation, etc.
482 */
483 thread->current_quantum = 0;
484 thread->computation_metered = 0;
485 thread->reason = AST_NONE;
486
487 KERNEL_DEBUG_CONSTANT(
488 MACHDBG_CODE(DBG_MACH_SCHED,MACH_MAKE_RUNNABLE) | DBG_FUNC_NONE,
489 (uintptr_t)thread_tid(thread), thread->sched_pri, 0, 0, 0);
490
491 DTRACE_SCHED2(wakeup, struct thread *, thread, struct proc *, thread->task->bsd_info);
492
493 return (result);
494 }
495
496 /*
497 * Routine: thread_go
498 * Purpose:
499 * Unblock and dispatch thread.
500 * Conditions:
501 * thread lock held, IPC locks may be held.
502 * thread must have been pulled from wait queue under same lock hold.
503 * Returns:
504 * KERN_SUCCESS - Thread was set running
505 * KERN_NOT_WAITING - Thread was not waiting
506 */
507 kern_return_t
508 thread_go(
509 thread_t thread,
510 wait_result_t wresult)
511 {
512 assert(thread->at_safe_point == FALSE);
513 assert(thread->wait_event == NO_EVENT64);
514 assert(thread->wait_queue == WAIT_QUEUE_NULL);
515
516 if ((thread->state & (TH_WAIT|TH_TERMINATE)) == TH_WAIT) {
517 if (!thread_unblock(thread, wresult))
518 thread_setrun(thread, SCHED_PREEMPT | SCHED_TAILQ);
519
520 return (KERN_SUCCESS);
521 }
522
523 return (KERN_NOT_WAITING);
524 }
525
526 /*
527 * Routine: thread_mark_wait_locked
528 * Purpose:
529 * Mark a thread as waiting. If, given the circumstances,
530 * it doesn't want to wait (i.e. already aborted), then
531 * indicate that in the return value.
532 * Conditions:
533 * at splsched() and thread is locked.
534 */
535 __private_extern__
536 wait_result_t
537 thread_mark_wait_locked(
538 thread_t thread,
539 wait_interrupt_t interruptible)
540 {
541 boolean_t at_safe_point;
542
543 assert(thread == current_thread());
544
545 /*
546 * The thread may have certain types of interrupts/aborts masked
547 * off. Even if the wait location says these types of interrupts
548 * are OK, we have to honor mask settings (outer-scoped code may
549 * not be able to handle aborts at the moment).
550 */
551 if (interruptible > (thread->options & TH_OPT_INTMASK))
552 interruptible = thread->options & TH_OPT_INTMASK;
553
554 at_safe_point = (interruptible == THREAD_ABORTSAFE);
555
556 if ( interruptible == THREAD_UNINT ||
557 !(thread->sched_mode & TH_MODE_ABORT) ||
558 (!at_safe_point &&
559 (thread->sched_mode & TH_MODE_ABORTSAFELY))) {
560
561 DTRACE_SCHED(sleep);
562
563 thread->state |= (interruptible) ? TH_WAIT : (TH_WAIT | TH_UNINT);
564 thread->at_safe_point = at_safe_point;
565 return (thread->wait_result = THREAD_WAITING);
566 }
567 else
568 if (thread->sched_mode & TH_MODE_ABORTSAFELY)
569 thread->sched_mode &= ~TH_MODE_ISABORTED;
570
571 return (thread->wait_result = THREAD_INTERRUPTED);
572 }
573
574 /*
575 * Routine: thread_interrupt_level
576 * Purpose:
577 * Set the maximum interruptible state for the
578 * current thread. The effective value of any
579 * interruptible flag passed into assert_wait
580 * will never exceed this.
581 *
582 * Useful for code that must not be interrupted,
583 * but which calls code that doesn't know that.
584 * Returns:
585 * The old interrupt level for the thread.
586 */
587 __private_extern__
588 wait_interrupt_t
589 thread_interrupt_level(
590 wait_interrupt_t new_level)
591 {
592 thread_t thread = current_thread();
593 wait_interrupt_t result = thread->options & TH_OPT_INTMASK;
594
595 thread->options = (thread->options & ~TH_OPT_INTMASK) | (new_level & TH_OPT_INTMASK);
596
597 return result;
598 }
599
600 /*
601 * Check to see if an assert wait is possible, without actually doing one.
602 * This is used by debug code in locks and elsewhere to verify that it is
603 * always OK to block when trying to take a blocking lock (since waiting
604 * for the actual assert_wait to catch the case may make it hard to detect
605 * this case.
606 */
607 boolean_t
608 assert_wait_possible(void)
609 {
610
611 thread_t thread;
612
613 #if DEBUG
614 if(debug_mode) return TRUE; /* Always succeed in debug mode */
615 #endif
616
617 thread = current_thread();
618
619 return (thread == NULL || wait_queue_assert_possible(thread));
620 }
621
622 /*
623 * assert_wait:
624 *
625 * Assert that the current thread is about to go to
626 * sleep until the specified event occurs.
627 */
628 wait_result_t
629 assert_wait(
630 event_t event,
631 wait_interrupt_t interruptible)
632 {
633 register wait_queue_t wq;
634 register int index;
635
636 assert(event != NO_EVENT);
637
638 index = wait_hash(event);
639 wq = &wait_queues[index];
640 return wait_queue_assert_wait(wq, event, interruptible, 0);
641 }
642
643 wait_result_t
644 assert_wait_timeout(
645 event_t event,
646 wait_interrupt_t interruptible,
647 uint32_t interval,
648 uint32_t scale_factor)
649 {
650 thread_t thread = current_thread();
651 wait_result_t wresult;
652 wait_queue_t wqueue;
653 uint64_t deadline;
654 spl_t s;
655
656 assert(event != NO_EVENT);
657 wqueue = &wait_queues[wait_hash(event)];
658
659 s = splsched();
660 wait_queue_lock(wqueue);
661 thread_lock(thread);
662
663 clock_interval_to_deadline(interval, scale_factor, &deadline);
664 wresult = wait_queue_assert_wait64_locked(wqueue, CAST_DOWN(event64_t, event),
665 interruptible, deadline, thread);
666
667 thread_unlock(thread);
668 wait_queue_unlock(wqueue);
669 splx(s);
670
671 return (wresult);
672 }
673
674 wait_result_t
675 assert_wait_deadline(
676 event_t event,
677 wait_interrupt_t interruptible,
678 uint64_t deadline)
679 {
680 thread_t thread = current_thread();
681 wait_result_t wresult;
682 wait_queue_t wqueue;
683 spl_t s;
684
685 assert(event != NO_EVENT);
686 wqueue = &wait_queues[wait_hash(event)];
687
688 s = splsched();
689 wait_queue_lock(wqueue);
690 thread_lock(thread);
691
692 wresult = wait_queue_assert_wait64_locked(wqueue, CAST_DOWN(event64_t,event),
693 interruptible, deadline, thread);
694
695 thread_unlock(thread);
696 wait_queue_unlock(wqueue);
697 splx(s);
698
699 return (wresult);
700 }
701
702 /*
703 * thread_sleep_fast_usimple_lock:
704 *
705 * Cause the current thread to wait until the specified event
706 * occurs. The specified simple_lock is unlocked before releasing
707 * the cpu and re-acquired as part of waking up.
708 *
709 * This is the simple lock sleep interface for components that use a
710 * faster version of simple_lock() than is provided by usimple_lock().
711 */
712 __private_extern__ wait_result_t
713 thread_sleep_fast_usimple_lock(
714 event_t event,
715 simple_lock_t lock,
716 wait_interrupt_t interruptible)
717 {
718 wait_result_t res;
719
720 res = assert_wait(event, interruptible);
721 if (res == THREAD_WAITING) {
722 simple_unlock(lock);
723 res = thread_block(THREAD_CONTINUE_NULL);
724 simple_lock(lock);
725 }
726 return res;
727 }
728
729
730 /*
731 * thread_sleep_usimple_lock:
732 *
733 * Cause the current thread to wait until the specified event
734 * occurs. The specified usimple_lock is unlocked before releasing
735 * the cpu and re-acquired as part of waking up.
736 *
737 * This is the simple lock sleep interface for components where
738 * simple_lock() is defined in terms of usimple_lock().
739 */
740 wait_result_t
741 thread_sleep_usimple_lock(
742 event_t event,
743 usimple_lock_t lock,
744 wait_interrupt_t interruptible)
745 {
746 wait_result_t res;
747
748 res = assert_wait(event, interruptible);
749 if (res == THREAD_WAITING) {
750 usimple_unlock(lock);
751 res = thread_block(THREAD_CONTINUE_NULL);
752 usimple_lock(lock);
753 }
754 return res;
755 }
756
757 /*
758 * thread_sleep_lock_write:
759 *
760 * Cause the current thread to wait until the specified event
761 * occurs. The specified (write) lock is unlocked before releasing
762 * the cpu. The (write) lock will be re-acquired before returning.
763 */
764 wait_result_t
765 thread_sleep_lock_write(
766 event_t event,
767 lock_t *lock,
768 wait_interrupt_t interruptible)
769 {
770 wait_result_t res;
771
772 res = assert_wait(event, interruptible);
773 if (res == THREAD_WAITING) {
774 lock_write_done(lock);
775 res = thread_block(THREAD_CONTINUE_NULL);
776 lock_write(lock);
777 }
778 return res;
779 }
780
781 /*
782 * thread_stop:
783 *
784 * Force a preemption point for a thread and wait
785 * for it to stop running. Arbitrates access among
786 * multiple stop requests. (released by unstop)
787 *
788 * The thread must enter a wait state and stop via a
789 * separate means.
790 *
791 * Returns FALSE if interrupted.
792 */
793 boolean_t
794 thread_stop(
795 thread_t thread)
796 {
797 wait_result_t wresult;
798 spl_t s = splsched();
799
800 wake_lock(thread);
801 thread_lock(thread);
802
803 while (thread->state & TH_SUSP) {
804 thread->wake_active = TRUE;
805 thread_unlock(thread);
806
807 wresult = assert_wait(&thread->wake_active, THREAD_ABORTSAFE);
808 wake_unlock(thread);
809 splx(s);
810
811 if (wresult == THREAD_WAITING)
812 wresult = thread_block(THREAD_CONTINUE_NULL);
813
814 if (wresult != THREAD_AWAKENED)
815 return (FALSE);
816
817 s = splsched();
818 wake_lock(thread);
819 thread_lock(thread);
820 }
821
822 thread->state |= TH_SUSP;
823
824 while (thread->state & TH_RUN) {
825 processor_t processor = thread->last_processor;
826
827 if (processor != PROCESSOR_NULL && processor->active_thread == thread)
828 cause_ast_check(processor);
829
830 thread->wake_active = TRUE;
831 thread_unlock(thread);
832
833 wresult = assert_wait(&thread->wake_active, THREAD_ABORTSAFE);
834 wake_unlock(thread);
835 splx(s);
836
837 if (wresult == THREAD_WAITING)
838 wresult = thread_block(THREAD_CONTINUE_NULL);
839
840 if (wresult != THREAD_AWAKENED) {
841 thread_unstop(thread);
842 return (FALSE);
843 }
844
845 s = splsched();
846 wake_lock(thread);
847 thread_lock(thread);
848 }
849
850 thread_unlock(thread);
851 wake_unlock(thread);
852 splx(s);
853
854 return (TRUE);
855 }
856
857 /*
858 * thread_unstop:
859 *
860 * Release a previous stop request and set
861 * the thread running if appropriate.
862 *
863 * Use only after a successful stop operation.
864 */
865 void
866 thread_unstop(
867 thread_t thread)
868 {
869 spl_t s = splsched();
870
871 wake_lock(thread);
872 thread_lock(thread);
873
874 if ((thread->state & (TH_RUN|TH_WAIT|TH_SUSP)) == TH_SUSP) {
875 thread->state &= ~TH_SUSP;
876 thread_unblock(thread, THREAD_AWAKENED);
877
878 thread_setrun(thread, SCHED_PREEMPT | SCHED_TAILQ);
879 }
880 else
881 if (thread->state & TH_SUSP) {
882 thread->state &= ~TH_SUSP;
883
884 if (thread->wake_active) {
885 thread->wake_active = FALSE;
886 thread_unlock(thread);
887
888 thread_wakeup(&thread->wake_active);
889 wake_unlock(thread);
890 splx(s);
891
892 return;
893 }
894 }
895
896 thread_unlock(thread);
897 wake_unlock(thread);
898 splx(s);
899 }
900
901 /*
902 * thread_wait:
903 *
904 * Wait for a thread to stop running. (non-interruptible)
905 *
906 */
907 void
908 thread_wait(
909 thread_t thread)
910 {
911 wait_result_t wresult;
912 spl_t s = splsched();
913
914 wake_lock(thread);
915 thread_lock(thread);
916
917 while (thread->state & TH_RUN) {
918 processor_t processor = thread->last_processor;
919
920 if (processor != PROCESSOR_NULL && processor->active_thread == thread)
921 cause_ast_check(processor);
922
923 thread->wake_active = TRUE;
924 thread_unlock(thread);
925
926 wresult = assert_wait(&thread->wake_active, THREAD_UNINT);
927 wake_unlock(thread);
928 splx(s);
929
930 if (wresult == THREAD_WAITING)
931 thread_block(THREAD_CONTINUE_NULL);
932
933 s = splsched();
934 wake_lock(thread);
935 thread_lock(thread);
936 }
937
938 thread_unlock(thread);
939 wake_unlock(thread);
940 splx(s);
941 }
942
943 /*
944 * Routine: clear_wait_internal
945 *
946 * Clear the wait condition for the specified thread.
947 * Start the thread executing if that is appropriate.
948 * Arguments:
949 * thread thread to awaken
950 * result Wakeup result the thread should see
951 * Conditions:
952 * At splsched
953 * the thread is locked.
954 * Returns:
955 * KERN_SUCCESS thread was rousted out a wait
956 * KERN_FAILURE thread was waiting but could not be rousted
957 * KERN_NOT_WAITING thread was not waiting
958 */
959 __private_extern__ kern_return_t
960 clear_wait_internal(
961 thread_t thread,
962 wait_result_t wresult)
963 {
964 wait_queue_t wq = thread->wait_queue;
965 uint32_t i = LockTimeOut;
966
967 do {
968 if (wresult == THREAD_INTERRUPTED && (thread->state & TH_UNINT))
969 return (KERN_FAILURE);
970
971 if (wq != WAIT_QUEUE_NULL) {
972 if (wait_queue_lock_try(wq)) {
973 wait_queue_pull_thread_locked(wq, thread, TRUE);
974 /* wait queue unlocked, thread still locked */
975 }
976 else {
977 thread_unlock(thread);
978 delay(1);
979
980 thread_lock(thread);
981 if (wq != thread->wait_queue)
982 return (KERN_NOT_WAITING);
983
984 continue;
985 }
986 }
987
988 return (thread_go(thread, wresult));
989 } while ((--i > 0) || machine_timeout_suspended());
990
991 panic("clear_wait_internal: deadlock: thread=%p, wq=%p, cpu=%d\n",
992 thread, wq, cpu_number());
993
994 return (KERN_FAILURE);
995 }
996
997
998 /*
999 * clear_wait:
1000 *
1001 * Clear the wait condition for the specified thread. Start the thread
1002 * executing if that is appropriate.
1003 *
1004 * parameters:
1005 * thread thread to awaken
1006 * result Wakeup result the thread should see
1007 */
1008 kern_return_t
1009 clear_wait(
1010 thread_t thread,
1011 wait_result_t result)
1012 {
1013 kern_return_t ret;
1014 spl_t s;
1015
1016 s = splsched();
1017 thread_lock(thread);
1018 ret = clear_wait_internal(thread, result);
1019 thread_unlock(thread);
1020 splx(s);
1021 return ret;
1022 }
1023
1024
1025 /*
1026 * thread_wakeup_prim:
1027 *
1028 * Common routine for thread_wakeup, thread_wakeup_with_result,
1029 * and thread_wakeup_one.
1030 *
1031 */
1032 kern_return_t
1033 thread_wakeup_prim(
1034 event_t event,
1035 boolean_t one_thread,
1036 wait_result_t result)
1037 {
1038 register wait_queue_t wq;
1039 register int index;
1040
1041 index = wait_hash(event);
1042 wq = &wait_queues[index];
1043 if (one_thread)
1044 return (wait_queue_wakeup_one(wq, event, result));
1045 else
1046 return (wait_queue_wakeup_all(wq, event, result));
1047 }
1048
1049 /*
1050 * thread_bind:
1051 *
1052 * Force the current thread to execute on the specified processor.
1053 *
1054 * Returns the previous binding. PROCESSOR_NULL means
1055 * not bound.
1056 *
1057 * XXX - DO NOT export this to users - XXX
1058 */
1059 processor_t
1060 thread_bind(
1061 processor_t processor)
1062 {
1063 thread_t self = current_thread();
1064 processor_t prev;
1065 spl_t s;
1066
1067 s = splsched();
1068 thread_lock(self);
1069
1070 prev = self->bound_processor;
1071 self->bound_processor = processor;
1072
1073 thread_unlock(self);
1074 splx(s);
1075
1076 return (prev);
1077 }
1078
1079 /*
1080 * thread_select:
1081 *
1082 * Select a new thread for the current processor to execute.
1083 *
1084 * May select the current thread, which must be locked.
1085 */
1086 static thread_t
1087 thread_select(
1088 thread_t thread,
1089 processor_t processor)
1090 {
1091 processor_set_t pset = processor->processor_set;
1092 thread_t new_thread = THREAD_NULL;
1093 boolean_t inactive_state;
1094
1095 do {
1096 /*
1097 * Update the priority.
1098 */
1099 if (thread->sched_stamp != sched_tick)
1100 update_priority(thread);
1101
1102 processor->current_pri = thread->sched_pri;
1103
1104 pset_lock(pset);
1105
1106 inactive_state = processor->state != PROCESSOR_SHUTDOWN && machine_processor_is_inactive(processor);
1107
1108 simple_lock(&rt_lock);
1109
1110 /*
1111 * Test to see if the current thread should continue
1112 * to run on this processor. Must be runnable, and not
1113 * bound to a different processor, nor be in the wrong
1114 * processor set.
1115 */
1116 if (
1117 #if CONFIG_EMBEDDED
1118 ((thread->state & ~TH_SUSP) == TH_RUN) &&
1119 #else
1120 thread->state == TH_RUN &&
1121 #endif
1122 (thread->sched_pri >= BASEPRI_RTQUEUES ||
1123 processor->processor_meta == PROCESSOR_META_NULL ||
1124 processor->processor_meta->primary == processor) &&
1125 (thread->bound_processor == PROCESSOR_NULL ||
1126 thread->bound_processor == processor) &&
1127 (thread->affinity_set == AFFINITY_SET_NULL ||
1128 thread->affinity_set->aset_pset == pset) ) {
1129 if ( thread->sched_pri >= BASEPRI_RTQUEUES &&
1130 first_timeslice(processor) ) {
1131 if (rt_runq.highq >= BASEPRI_RTQUEUES) {
1132 register run_queue_t runq = &rt_runq;
1133 register queue_t q;
1134
1135 q = runq->queues + runq->highq;
1136 if (((thread_t)q->next)->realtime.deadline <
1137 processor->deadline) {
1138 thread = (thread_t)q->next;
1139 ((queue_entry_t)thread)->next->prev = q;
1140 q->next = ((queue_entry_t)thread)->next;
1141 thread->runq = PROCESSOR_NULL;
1142 runq->count--; runq->urgency--;
1143 assert(runq->urgency >= 0);
1144 if (queue_empty(q)) {
1145 if (runq->highq != IDLEPRI)
1146 clrbit(MAXPRI - runq->highq, runq->bitmap);
1147 runq->highq = MAXPRI - ffsbit(runq->bitmap);
1148 }
1149 }
1150 }
1151
1152 simple_unlock(&rt_lock);
1153
1154 processor->deadline = thread->realtime.deadline;
1155
1156 pset_unlock(pset);
1157
1158 return (thread);
1159 }
1160
1161 if (!inactive_state && rt_runq.highq < thread->sched_pri &&
1162 (new_thread = choose_thread(processor, thread->sched_pri)) == THREAD_NULL) {
1163
1164 simple_unlock(&rt_lock);
1165
1166 /* I am the highest priority runnable (non-idle) thread */
1167
1168 pset_pri_hint(pset, processor, processor->current_pri);
1169
1170 pset_count_hint(pset, processor, processor->runq.count);
1171
1172 processor->deadline = UINT64_MAX;
1173
1174 pset_unlock(pset);
1175
1176 return (thread);
1177 }
1178 }
1179
1180 if (new_thread != THREAD_NULL ||
1181 (processor->runq.highq >= rt_runq.highq &&
1182 (new_thread = choose_thread(processor, MINPRI)) != THREAD_NULL)) {
1183 simple_unlock(&rt_lock);
1184
1185 if (!inactive_state) {
1186 pset_pri_hint(pset, processor, new_thread->sched_pri);
1187
1188 pset_count_hint(pset, processor, processor->runq.count);
1189 }
1190
1191 processor->deadline = UINT64_MAX;
1192 pset_unlock(pset);
1193
1194 return (new_thread);
1195 }
1196
1197 if (rt_runq.count > 0) {
1198 thread = run_queue_dequeue(&rt_runq, SCHED_HEADQ);
1199 simple_unlock(&rt_lock);
1200
1201 processor->deadline = thread->realtime.deadline;
1202 pset_unlock(pset);
1203
1204 return (thread);
1205 }
1206
1207 simple_unlock(&rt_lock);
1208
1209 processor->deadline = UINT64_MAX;
1210
1211 /*
1212 * Set processor inactive based on
1213 * indication from the platform code.
1214 */
1215 if (inactive_state) {
1216 if (processor->state == PROCESSOR_RUNNING)
1217 remqueue(&pset->active_queue, (queue_entry_t)processor);
1218 else
1219 if (processor->state == PROCESSOR_IDLE)
1220 remqueue(&pset->idle_queue, (queue_entry_t)processor);
1221
1222 processor->state = PROCESSOR_INACTIVE;
1223
1224 pset_unlock(pset);
1225
1226 return (processor->idle_thread);
1227 }
1228
1229 /*
1230 * No runnable threads, attempt to steal
1231 * from other processors.
1232 */
1233 new_thread = steal_thread(pset);
1234 if (new_thread != THREAD_NULL)
1235 return (new_thread);
1236
1237 /*
1238 * If other threads have appeared, shortcut
1239 * around again.
1240 */
1241 if (processor->runq.count > 0 || rt_runq.count > 0)
1242 continue;
1243
1244 pset_lock(pset);
1245
1246 /*
1247 * Nothing is runnable, so set this processor idle if it
1248 * was running.
1249 */
1250 if (processor->state == PROCESSOR_RUNNING) {
1251 remqueue(&pset->active_queue, (queue_entry_t)processor);
1252 processor->state = PROCESSOR_IDLE;
1253
1254 if (processor->processor_meta == PROCESSOR_META_NULL || processor->processor_meta->primary == processor) {
1255 enqueue_head(&pset->idle_queue, (queue_entry_t)processor);
1256 pset->low_pri = pset->low_count = processor;
1257 }
1258 else {
1259 enqueue_head(&processor->processor_meta->idle_queue, (queue_entry_t)processor);
1260 pset_unlock(pset);
1261 return (processor->idle_thread);
1262 }
1263 }
1264
1265 pset_unlock(pset);
1266
1267 /*
1268 * Choose idle thread if fast idle is not possible.
1269 */
1270 if ((thread->state & (TH_IDLE|TH_TERMINATE|TH_SUSP)) || !(thread->state & TH_WAIT) || thread->wake_active)
1271 return (processor->idle_thread);
1272
1273 /*
1274 * Perform idling activities directly without a
1275 * context switch. Return dispatched thread,
1276 * else check again for a runnable thread.
1277 */
1278 new_thread = thread_select_idle(thread, processor);
1279
1280 } while (new_thread == THREAD_NULL);
1281
1282 return (new_thread);
1283 }
1284
1285 /*
1286 * thread_select_idle:
1287 *
1288 * Idle the processor using the current thread context.
1289 *
1290 * Called with thread locked, then dropped and relocked.
1291 */
1292 static thread_t
1293 thread_select_idle(
1294 thread_t thread,
1295 processor_t processor)
1296 {
1297 thread_t new_thread;
1298
1299 if (thread->sched_mode & TH_MODE_TIMESHARE)
1300 sched_share_decr();
1301 sched_run_decr();
1302
1303 thread->state |= TH_IDLE;
1304 processor->current_pri = IDLEPRI;
1305
1306 thread_unlock(thread);
1307
1308 /*
1309 * Switch execution timing to processor idle thread.
1310 */
1311 processor->last_dispatch = mach_absolute_time();
1312 thread_timer_event(processor->last_dispatch, &processor->idle_thread->system_timer);
1313 PROCESSOR_DATA(processor, kernel_timer) = &processor->idle_thread->system_timer;
1314
1315 /*
1316 * Cancel the quantum timer while idling.
1317 */
1318 timer_call_cancel(&processor->quantum_timer);
1319 processor->timeslice = 0;
1320
1321 (*thread->sched_call)(SCHED_CALL_BLOCK, thread);
1322
1323 /*
1324 * Enable interrupts and perform idling activities. No
1325 * preemption due to TH_IDLE being set.
1326 */
1327 spllo(); new_thread = processor_idle(thread, processor);
1328
1329 /*
1330 * Return at splsched.
1331 */
1332 (*thread->sched_call)(SCHED_CALL_UNBLOCK, thread);
1333
1334 thread_lock(thread);
1335
1336 /*
1337 * If awakened, switch to thread timer and start a new quantum.
1338 * Otherwise skip; we will context switch to another thread or return here.
1339 */
1340 if (!(thread->state & TH_WAIT)) {
1341 processor->last_dispatch = mach_absolute_time();
1342 thread_timer_event(processor->last_dispatch, &thread->system_timer);
1343 PROCESSOR_DATA(processor, kernel_timer) = &thread->system_timer;
1344
1345 thread_quantum_init(thread);
1346
1347 processor->quantum_end = processor->last_dispatch + thread->current_quantum;
1348 timer_call_enter1(&processor->quantum_timer, thread, processor->quantum_end);
1349 processor->timeslice = 1;
1350
1351 thread->computation_epoch = processor->last_dispatch;
1352 }
1353
1354 thread->state &= ~TH_IDLE;
1355
1356 sched_run_incr();
1357 if (thread->sched_mode & TH_MODE_TIMESHARE)
1358 sched_share_incr();
1359
1360 return (new_thread);
1361 }
1362
1363 /*
1364 * choose_thread:
1365 *
1366 * Locate a thread to execute from the processor run queue
1367 * and return it. Only choose a thread with greater or equal
1368 * priority.
1369 *
1370 * Associated pset must be locked. Returns THREAD_NULL
1371 * on failure.
1372 */
1373 static thread_t
1374 choose_thread(
1375 processor_t processor,
1376 int priority)
1377 {
1378 run_queue_t rq = &processor->runq;
1379 queue_t queue = rq->queues + rq->highq;
1380 int pri = rq->highq, count = rq->count;
1381 thread_t thread;
1382
1383 while (count > 0 && pri >= priority) {
1384 thread = (thread_t)queue_first(queue);
1385 while (!queue_end(queue, (queue_entry_t)thread)) {
1386 if (thread->bound_processor == PROCESSOR_NULL ||
1387 thread->bound_processor == processor) {
1388 remqueue(queue, (queue_entry_t)thread);
1389
1390 thread->runq = PROCESSOR_NULL;
1391 rq->count--;
1392 if (testbit(pri, sched_preempt_pri)) {
1393 rq->urgency--; assert(rq->urgency >= 0);
1394 }
1395 if (queue_empty(queue)) {
1396 if (pri != IDLEPRI)
1397 clrbit(MAXPRI - pri, rq->bitmap);
1398 rq->highq = MAXPRI - ffsbit(rq->bitmap);
1399 }
1400
1401 return (thread);
1402 }
1403 count--;
1404
1405 thread = (thread_t)queue_next((queue_entry_t)thread);
1406 }
1407
1408 queue--; pri--;
1409 }
1410
1411 return (THREAD_NULL);
1412 }
1413
1414 /*
1415 * Perform a context switch and start executing the new thread.
1416 *
1417 * Returns FALSE on failure, and the thread is re-dispatched.
1418 *
1419 * Called at splsched.
1420 */
1421
1422 #define funnel_release_check(thread, debug) \
1423 MACRO_BEGIN \
1424 if ((thread)->funnel_state & TH_FN_OWNED) { \
1425 (thread)->funnel_state = TH_FN_REFUNNEL; \
1426 KERNEL_DEBUG(0x603242c | DBG_FUNC_NONE, \
1427 (thread)->funnel_lock, (debug), 0, 0, 0); \
1428 funnel_unlock((thread)->funnel_lock); \
1429 } \
1430 MACRO_END
1431
1432 #define funnel_refunnel_check(thread, debug) \
1433 MACRO_BEGIN \
1434 if ((thread)->funnel_state & TH_FN_REFUNNEL) { \
1435 kern_return_t result = (thread)->wait_result; \
1436 \
1437 (thread)->funnel_state = 0; \
1438 KERNEL_DEBUG(0x6032428 | DBG_FUNC_NONE, \
1439 (thread)->funnel_lock, (debug), 0, 0, 0); \
1440 funnel_lock((thread)->funnel_lock); \
1441 KERNEL_DEBUG(0x6032430 | DBG_FUNC_NONE, \
1442 (thread)->funnel_lock, (debug), 0, 0, 0); \
1443 (thread)->funnel_state = TH_FN_OWNED; \
1444 (thread)->wait_result = result; \
1445 } \
1446 MACRO_END
1447
1448 static boolean_t
1449 thread_invoke(
1450 register thread_t self,
1451 register thread_t thread,
1452 ast_t reason)
1453 {
1454 thread_continue_t continuation = self->continuation;
1455 void *parameter = self->parameter;
1456 processor_t processor;
1457
1458 if (get_preemption_level() != 0) {
1459 int pl = get_preemption_level();
1460 panic("thread_invoke: preemption_level %d, possible cause: %s",
1461 pl, (pl < 0 ? "unlocking an unlocked mutex or spinlock" :
1462 "blocking while holding a spinlock, or within interrupt context"));
1463 }
1464
1465 assert(self == current_thread());
1466
1467 /*
1468 * Mark thread interruptible.
1469 */
1470 thread_lock(thread);
1471 thread->state &= ~TH_UNINT;
1472
1473 #if DEBUG
1474 assert(thread_runnable(thread));
1475 #endif
1476
1477 /*
1478 * Allow time constraint threads to hang onto
1479 * a stack.
1480 */
1481 if ((self->sched_mode & TH_MODE_REALTIME) && !self->reserved_stack)
1482 self->reserved_stack = self->kernel_stack;
1483
1484 if (continuation != NULL) {
1485 if (!thread->kernel_stack) {
1486 /*
1487 * If we are using a privileged stack,
1488 * check to see whether we can exchange it with
1489 * that of the other thread.
1490 */
1491 if (self->kernel_stack == self->reserved_stack && !thread->reserved_stack)
1492 goto need_stack;
1493
1494 /*
1495 * Context switch by performing a stack handoff.
1496 */
1497 continuation = thread->continuation;
1498 parameter = thread->parameter;
1499
1500 processor = current_processor();
1501 processor->active_thread = thread;
1502 processor->current_pri = thread->sched_pri;
1503 if (thread->last_processor != processor && thread->last_processor != NULL) {
1504 if (thread->last_processor->processor_set != processor->processor_set)
1505 thread->ps_switch++;
1506 thread->p_switch++;
1507 }
1508 thread->last_processor = processor;
1509 thread->c_switch++;
1510 ast_context(thread);
1511 thread_unlock(thread);
1512
1513 self->reason = reason;
1514
1515 processor->last_dispatch = mach_absolute_time();
1516 thread_timer_event(processor->last_dispatch, &thread->system_timer);
1517 PROCESSOR_DATA(processor, kernel_timer) = &thread->system_timer;
1518
1519 KERNEL_DEBUG_CONSTANT(MACHDBG_CODE(DBG_MACH_SCHED, MACH_STACK_HANDOFF)|DBG_FUNC_NONE,
1520 self->reason, (uintptr_t)thread_tid(thread), self->sched_pri, thread->sched_pri, 0);
1521
1522 DTRACE_SCHED2(off__cpu, struct thread *, thread, struct proc *, thread->task->bsd_info);
1523
1524 TLOG(1, "thread_invoke: calling machine_stack_handoff\n");
1525 machine_stack_handoff(self, thread);
1526
1527 DTRACE_SCHED(on__cpu);
1528
1529 thread_dispatch(self, thread);
1530
1531 thread->continuation = thread->parameter = NULL;
1532
1533 counter(c_thread_invoke_hits++);
1534
1535 funnel_refunnel_check(thread, 2);
1536 (void) spllo();
1537
1538 assert(continuation);
1539 call_continuation(continuation, parameter, thread->wait_result);
1540 /*NOTREACHED*/
1541 }
1542 else if (thread == self) {
1543 /* same thread but with continuation */
1544 ast_context(self);
1545 counter(++c_thread_invoke_same);
1546 thread_unlock(self);
1547
1548 self->continuation = self->parameter = NULL;
1549
1550 funnel_refunnel_check(self, 3);
1551 (void) spllo();
1552
1553 call_continuation(continuation, parameter, self->wait_result);
1554 /*NOTREACHED*/
1555 }
1556 }
1557 else {
1558 /*
1559 * Check that the other thread has a stack
1560 */
1561 if (!thread->kernel_stack) {
1562 need_stack:
1563 if (!stack_alloc_try(thread)) {
1564 counter(c_thread_invoke_misses++);
1565 thread_unlock(thread);
1566 thread_stack_enqueue(thread);
1567 return (FALSE);
1568 }
1569 }
1570 else if (thread == self) {
1571 ast_context(self);
1572 counter(++c_thread_invoke_same);
1573 thread_unlock(self);
1574 return (TRUE);
1575 }
1576 }
1577
1578 /*
1579 * Context switch by full context save.
1580 */
1581 processor = current_processor();
1582 processor->active_thread = thread;
1583 processor->current_pri = thread->sched_pri;
1584 if (thread->last_processor != processor && thread->last_processor != NULL) {
1585 if (thread->last_processor->processor_set != processor->processor_set)
1586 thread->ps_switch++;
1587 thread->p_switch++;
1588 }
1589 thread->last_processor = processor;
1590 thread->c_switch++;
1591 ast_context(thread);
1592 thread_unlock(thread);
1593
1594 counter(c_thread_invoke_csw++);
1595
1596 assert(self->runq == PROCESSOR_NULL);
1597 self->reason = reason;
1598
1599 processor->last_dispatch = mach_absolute_time();
1600 thread_timer_event(processor->last_dispatch, &thread->system_timer);
1601 PROCESSOR_DATA(processor, kernel_timer) = &thread->system_timer;
1602
1603 KERNEL_DEBUG_CONSTANT(MACHDBG_CODE(DBG_MACH_SCHED,MACH_SCHED) | DBG_FUNC_NONE,
1604 self->reason, (uintptr_t)thread_tid(thread), self->sched_pri, thread->sched_pri, 0);
1605
1606 DTRACE_SCHED2(off__cpu, struct thread *, thread, struct proc *, thread->task->bsd_info);
1607
1608 /*
1609 * This is where we actually switch register context,
1610 * and address space if required. We will next run
1611 * as a result of a subsequent context switch.
1612 */
1613 thread = machine_switch_context(self, continuation, thread);
1614 TLOG(1,"thread_invoke: returning machine_switch_context: self %p continuation %p thread %p\n", self, continuation, thread);
1615
1616 DTRACE_SCHED(on__cpu);
1617
1618 /*
1619 * We have been resumed and are set to run.
1620 */
1621 thread_dispatch(thread, self);
1622
1623 if (continuation) {
1624 self->continuation = self->parameter = NULL;
1625
1626 funnel_refunnel_check(self, 3);
1627 (void) spllo();
1628
1629 call_continuation(continuation, parameter, self->wait_result);
1630 /*NOTREACHED*/
1631 }
1632
1633 return (TRUE);
1634 }
1635
1636 /*
1637 * thread_dispatch:
1638 *
1639 * Handle threads at context switch. Re-dispatch other thread
1640 * if still running, otherwise update run state and perform
1641 * special actions. Update quantum for other thread and begin
1642 * the quantum for ourselves.
1643 *
1644 * Called at splsched.
1645 */
1646 void
1647 thread_dispatch(
1648 thread_t thread,
1649 thread_t self)
1650 {
1651 processor_t processor = self->last_processor;
1652
1653 if (thread != THREAD_NULL) {
1654 /*
1655 * If blocked at a continuation, discard
1656 * the stack.
1657 */
1658 if (thread->continuation != NULL && thread->kernel_stack != 0)
1659 stack_free(thread);
1660
1661 if (!(thread->state & TH_IDLE)) {
1662 wake_lock(thread);
1663 thread_lock(thread);
1664
1665 /*
1666 * Compute remainder of current quantum.
1667 */
1668 if ( first_timeslice(processor) &&
1669 processor->quantum_end > processor->last_dispatch )
1670 thread->current_quantum = (uint32_t)(processor->quantum_end - processor->last_dispatch);
1671 else
1672 thread->current_quantum = 0;
1673
1674 if (thread->sched_mode & TH_MODE_REALTIME) {
1675 /*
1676 * Cancel the deadline if the thread has
1677 * consumed the entire quantum.
1678 */
1679 if (thread->current_quantum == 0) {
1680 thread->realtime.deadline = UINT64_MAX;
1681 thread->reason |= AST_QUANTUM;
1682 }
1683 } else {
1684 /*
1685 * For non-realtime threads treat a tiny
1686 * remaining quantum as an expired quantum
1687 * but include what's left next time.
1688 */
1689 if (thread->current_quantum < min_std_quantum) {
1690 thread->reason |= AST_QUANTUM;
1691 thread->current_quantum += std_quantum;
1692 }
1693 }
1694
1695 /*
1696 * If we are doing a direct handoff then
1697 * take the remainder of the quantum.
1698 */
1699 if ((thread->reason & (AST_HANDOFF|AST_QUANTUM)) == AST_HANDOFF) {
1700 self->current_quantum = thread->current_quantum;
1701 thread->reason |= AST_QUANTUM;
1702 thread->current_quantum = 0;
1703 }
1704
1705 thread->computation_metered += (processor->last_dispatch - thread->computation_epoch);
1706
1707 if (!(thread->state & TH_WAIT)) {
1708 /*
1709 * Still running.
1710 */
1711 if (thread->reason & AST_QUANTUM)
1712 thread_setrun(thread, SCHED_TAILQ);
1713 else
1714 if (thread->reason & AST_PREEMPT)
1715 thread_setrun(thread, SCHED_HEADQ);
1716 else
1717 thread_setrun(thread, SCHED_PREEMPT | SCHED_TAILQ);
1718
1719 thread->reason = AST_NONE;
1720
1721 thread_unlock(thread);
1722 wake_unlock(thread);
1723 }
1724 else {
1725 /*
1726 * Waiting.
1727 */
1728 boolean_t should_terminate = FALSE;
1729
1730 /* Only the first call to thread_dispatch
1731 * after explicit termination should add
1732 * the thread to the termination queue
1733 */
1734 if ((thread->state & (TH_TERMINATE|TH_TERMINATE2)) == TH_TERMINATE) {
1735 should_terminate = TRUE;
1736 thread->state |= TH_TERMINATE2;
1737 }
1738
1739 thread->state &= ~TH_RUN;
1740
1741 if (thread->sched_mode & TH_MODE_TIMESHARE)
1742 sched_share_decr();
1743 sched_run_decr();
1744
1745 (*thread->sched_call)(SCHED_CALL_BLOCK, thread);
1746
1747 if (thread->wake_active) {
1748 thread->wake_active = FALSE;
1749 thread_unlock(thread);
1750
1751 thread_wakeup(&thread->wake_active);
1752 }
1753 else
1754 thread_unlock(thread);
1755
1756 wake_unlock(thread);
1757
1758 if (should_terminate)
1759 thread_terminate_enqueue(thread);
1760 }
1761 }
1762 }
1763
1764 if (!(self->state & TH_IDLE)) {
1765 /*
1766 * Get a new quantum if none remaining.
1767 */
1768 if (self->current_quantum == 0)
1769 thread_quantum_init(self);
1770
1771 /*
1772 * Set up quantum timer and timeslice.
1773 */
1774 processor->quantum_end = (processor->last_dispatch + self->current_quantum);
1775 timer_call_enter1(&processor->quantum_timer, self, processor->quantum_end);
1776
1777 processor->timeslice = 1;
1778
1779 self->computation_epoch = processor->last_dispatch;
1780 }
1781 else {
1782 timer_call_cancel(&processor->quantum_timer);
1783 processor->timeslice = 0;
1784 }
1785 }
1786
1787 #include <libkern/OSDebug.h>
1788
1789 uint32_t kdebug_thread_block = 0;
1790
1791
1792 /*
1793 * thread_block_reason:
1794 *
1795 * Forces a reschedule, blocking the caller if a wait
1796 * has been asserted.
1797 *
1798 * If a continuation is specified, then thread_invoke will
1799 * attempt to discard the thread's kernel stack. When the
1800 * thread resumes, it will execute the continuation function
1801 * on a new kernel stack.
1802 */
1803 counter(mach_counter_t c_thread_block_calls = 0;)
1804
1805 wait_result_t
1806 thread_block_reason(
1807 thread_continue_t continuation,
1808 void *parameter,
1809 ast_t reason)
1810 {
1811 register thread_t self = current_thread();
1812 register processor_t processor;
1813 register thread_t new_thread;
1814 spl_t s;
1815
1816 counter(++c_thread_block_calls);
1817
1818 s = splsched();
1819
1820 if (!(reason & AST_PREEMPT))
1821 funnel_release_check(self, 2);
1822
1823 processor = current_processor();
1824
1825 /* If we're explicitly yielding, force a subsequent quantum */
1826 if (reason & AST_YIELD)
1827 processor->timeslice = 0;
1828
1829 /* We're handling all scheduling AST's */
1830 ast_off(AST_SCHEDULING);
1831
1832 self->continuation = continuation;
1833 self->parameter = parameter;
1834
1835 if (kdebug_thread_block && kdebug_enable && self->state != TH_RUN) {
1836 uint32_t bt[8];
1837
1838 OSBacktrace((void **)&bt[0], 8);
1839
1840 KERNEL_DEBUG_CONSTANT(0x140004c | DBG_FUNC_START, bt[0], bt[1], bt[2], bt[3], 0);
1841 KERNEL_DEBUG_CONSTANT(0x140004c | DBG_FUNC_END, bt[4], bt[5], bt[6], bt[7], 0);
1842 }
1843
1844 do {
1845 thread_lock(self);
1846 new_thread = thread_select(self, processor);
1847 thread_unlock(self);
1848 } while (!thread_invoke(self, new_thread, reason));
1849
1850 funnel_refunnel_check(self, 5);
1851 splx(s);
1852
1853 return (self->wait_result);
1854 }
1855
1856 /*
1857 * thread_block:
1858 *
1859 * Block the current thread if a wait has been asserted.
1860 */
1861 wait_result_t
1862 thread_block(
1863 thread_continue_t continuation)
1864 {
1865 return thread_block_reason(continuation, NULL, AST_NONE);
1866 }
1867
1868 wait_result_t
1869 thread_block_parameter(
1870 thread_continue_t continuation,
1871 void *parameter)
1872 {
1873 return thread_block_reason(continuation, parameter, AST_NONE);
1874 }
1875
1876 /*
1877 * thread_run:
1878 *
1879 * Switch directly from the current thread to the
1880 * new thread, handing off our quantum if appropriate.
1881 *
1882 * New thread must be runnable, and not on a run queue.
1883 *
1884 * Called at splsched.
1885 */
1886 int
1887 thread_run(
1888 thread_t self,
1889 thread_continue_t continuation,
1890 void *parameter,
1891 thread_t new_thread)
1892 {
1893 ast_t handoff = AST_HANDOFF;
1894
1895 funnel_release_check(self, 3);
1896
1897 self->continuation = continuation;
1898 self->parameter = parameter;
1899
1900 while (!thread_invoke(self, new_thread, handoff)) {
1901 processor_t processor = current_processor();
1902
1903 thread_lock(self);
1904 new_thread = thread_select(self, processor);
1905 thread_unlock(self);
1906 handoff = AST_NONE;
1907 }
1908
1909 funnel_refunnel_check(self, 6);
1910
1911 return (self->wait_result);
1912 }
1913
1914 /*
1915 * thread_continue:
1916 *
1917 * Called at splsched when a thread first receives
1918 * a new stack after a continuation.
1919 */
1920 void
1921 thread_continue(
1922 register thread_t thread)
1923 {
1924 register thread_t self = current_thread();
1925 register thread_continue_t continuation;
1926 register void *parameter;
1927
1928 DTRACE_SCHED(on__cpu);
1929
1930 continuation = self->continuation;
1931 parameter = self->parameter;
1932
1933 thread_dispatch(thread, self);
1934
1935 self->continuation = self->parameter = NULL;
1936
1937 funnel_refunnel_check(self, 4);
1938
1939 if (thread != THREAD_NULL)
1940 (void)spllo();
1941
1942 TLOG(1, "thread_continue: calling call_continuation \n");
1943 call_continuation(continuation, parameter, self->wait_result);
1944 /*NOTREACHED*/
1945 }
1946
1947 /*
1948 * run_queue_init:
1949 *
1950 * Initialize a run queue before first use.
1951 */
1952 void
1953 run_queue_init(
1954 run_queue_t rq)
1955 {
1956 int i;
1957
1958 rq->highq = IDLEPRI;
1959 for (i = 0; i < NRQBM; i++)
1960 rq->bitmap[i] = 0;
1961 setbit(MAXPRI - IDLEPRI, rq->bitmap);
1962 rq->urgency = rq->count = 0;
1963 for (i = 0; i < NRQS; i++)
1964 queue_init(&rq->queues[i]);
1965 }
1966
1967 /*
1968 * run_queue_dequeue:
1969 *
1970 * Perform a dequeue operation on a run queue,
1971 * and return the resulting thread.
1972 *
1973 * The run queue must be locked (see run_queue_remove()
1974 * for more info), and not empty.
1975 */
1976 static thread_t
1977 run_queue_dequeue(
1978 run_queue_t rq,
1979 integer_t options)
1980 {
1981 thread_t thread;
1982 queue_t queue = rq->queues + rq->highq;
1983
1984 if (options & SCHED_HEADQ) {
1985 thread = (thread_t)queue->next;
1986 ((queue_entry_t)thread)->next->prev = queue;
1987 queue->next = ((queue_entry_t)thread)->next;
1988 }
1989 else {
1990 thread = (thread_t)queue->prev;
1991 ((queue_entry_t)thread)->prev->next = queue;
1992 queue->prev = ((queue_entry_t)thread)->prev;
1993 }
1994
1995 thread->runq = PROCESSOR_NULL;
1996 rq->count--;
1997 if (testbit(rq->highq, sched_preempt_pri)) {
1998 rq->urgency--; assert(rq->urgency >= 0);
1999 }
2000 if (queue_empty(queue)) {
2001 if (rq->highq != IDLEPRI)
2002 clrbit(MAXPRI - rq->highq, rq->bitmap);
2003 rq->highq = MAXPRI - ffsbit(rq->bitmap);
2004 }
2005
2006 return (thread);
2007 }
2008
2009 /*
2010 * realtime_queue_insert:
2011 *
2012 * Enqueue a thread for realtime execution.
2013 */
2014 static boolean_t
2015 realtime_queue_insert(
2016 thread_t thread)
2017 {
2018 run_queue_t rq = &rt_runq;
2019 queue_t queue = rq->queues + thread->sched_pri;
2020 uint64_t deadline = thread->realtime.deadline;
2021 boolean_t preempt = FALSE;
2022
2023 simple_lock(&rt_lock);
2024
2025 if (queue_empty(queue)) {
2026 enqueue_tail(queue, (queue_entry_t)thread);
2027
2028 setbit(MAXPRI - thread->sched_pri, rq->bitmap);
2029 if (thread->sched_pri > rq->highq)
2030 rq->highq = thread->sched_pri;
2031 preempt = TRUE;
2032 }
2033 else {
2034 register thread_t entry = (thread_t)queue_first(queue);
2035
2036 while (TRUE) {
2037 if ( queue_end(queue, (queue_entry_t)entry) ||
2038 deadline < entry->realtime.deadline ) {
2039 entry = (thread_t)queue_prev((queue_entry_t)entry);
2040 break;
2041 }
2042
2043 entry = (thread_t)queue_next((queue_entry_t)entry);
2044 }
2045
2046 if ((queue_entry_t)entry == queue)
2047 preempt = TRUE;
2048
2049 insque((queue_entry_t)thread, (queue_entry_t)entry);
2050 }
2051
2052 thread->runq = RT_RUNQ;
2053 rq->count++; rq->urgency++;
2054
2055 simple_unlock(&rt_lock);
2056
2057 return (preempt);
2058 }
2059
2060 /*
2061 * realtime_setrun:
2062 *
2063 * Dispatch a thread for realtime execution.
2064 *
2065 * Thread must be locked. Associated pset must
2066 * be locked, and is returned unlocked.
2067 */
2068 static void
2069 realtime_setrun(
2070 processor_t processor,
2071 thread_t thread)
2072 {
2073 processor_set_t pset = processor->processor_set;
2074
2075 /*
2076 * Dispatch directly onto idle processor.
2077 */
2078 if (processor->state == PROCESSOR_IDLE) {
2079 remqueue(&pset->idle_queue, (queue_entry_t)processor);
2080 enqueue_tail(&pset->active_queue, (queue_entry_t)processor);
2081
2082 processor->next_thread = thread;
2083 processor->deadline = thread->realtime.deadline;
2084 processor->state = PROCESSOR_DISPATCHING;
2085 pset_unlock(pset);
2086
2087 if (processor != current_processor())
2088 machine_signal_idle(processor);
2089 return;
2090 }
2091
2092 if (realtime_queue_insert(thread)) {
2093 if (processor == current_processor())
2094 ast_on(AST_PREEMPT | AST_URGENT);
2095 else
2096 cause_ast_check(processor);
2097 }
2098
2099 pset_unlock(pset);
2100 }
2101
2102 /*
2103 * processor_enqueue:
2104 *
2105 * Enqueue thread on a processor run queue. Thread must be locked,
2106 * and not already be on a run queue.
2107 *
2108 * Returns TRUE if a preemption is indicated based on the state
2109 * of the run queue.
2110 *
2111 * The run queue must be locked (see run_queue_remove()
2112 * for more info).
2113 */
2114 static boolean_t
2115 processor_enqueue(
2116 processor_t processor,
2117 thread_t thread,
2118 integer_t options)
2119 {
2120 run_queue_t rq = &processor->runq;
2121 queue_t queue = rq->queues + thread->sched_pri;
2122 boolean_t result = FALSE;
2123
2124 if (queue_empty(queue)) {
2125 enqueue_tail(queue, (queue_entry_t)thread);
2126
2127 setbit(MAXPRI - thread->sched_pri, rq->bitmap);
2128 if (thread->sched_pri > rq->highq) {
2129 rq->highq = thread->sched_pri;
2130 result = TRUE;
2131 }
2132 }
2133 else
2134 if (options & SCHED_TAILQ)
2135 enqueue_tail(queue, (queue_entry_t)thread);
2136 else
2137 enqueue_head(queue, (queue_entry_t)thread);
2138
2139 thread->runq = processor;
2140 if (testbit(thread->sched_pri, sched_preempt_pri))
2141 rq->urgency++;
2142 rq->count++;
2143
2144 return (result);
2145 }
2146
2147 /*
2148 * processor_setrun:
2149 *
2150 * Dispatch a thread for execution on a
2151 * processor.
2152 *
2153 * Thread must be locked. Associated pset must
2154 * be locked, and is returned unlocked.
2155 */
2156 static void
2157 processor_setrun(
2158 processor_t processor,
2159 thread_t thread,
2160 integer_t options)
2161 {
2162 processor_set_t pset = processor->processor_set;
2163 ast_t preempt;
2164
2165 /*
2166 * Dispatch directly onto idle processor.
2167 */
2168 if (processor->state == PROCESSOR_IDLE) {
2169 remqueue(&pset->idle_queue, (queue_entry_t)processor);
2170 enqueue_tail(&pset->active_queue, (queue_entry_t)processor);
2171
2172 processor->next_thread = thread;
2173 processor->deadline = UINT64_MAX;
2174 processor->state = PROCESSOR_DISPATCHING;
2175 pset_unlock(pset);
2176
2177 if (processor != current_processor())
2178 machine_signal_idle(processor);
2179 return;
2180 }
2181
2182 /*
2183 * Set preemption mode.
2184 */
2185 if (testbit(thread->sched_pri, sched_preempt_pri))
2186 preempt = (AST_PREEMPT | AST_URGENT);
2187 else
2188 if (thread->sched_mode & TH_MODE_TIMESHARE && thread->sched_pri < thread->priority)
2189 preempt = AST_NONE;
2190 else
2191 preempt = (options & SCHED_PREEMPT)? AST_PREEMPT: AST_NONE;
2192
2193 if (!processor_enqueue(processor, thread, options))
2194 preempt = AST_NONE;
2195
2196 if (preempt != AST_NONE) {
2197 if (processor == current_processor()) {
2198 if (csw_check(processor) != AST_NONE)
2199 ast_on(preempt);
2200 }
2201 else
2202 if ( (processor->state == PROCESSOR_RUNNING ||
2203 processor->state == PROCESSOR_SHUTDOWN) &&
2204 thread->sched_pri >= processor->current_pri ) {
2205 cause_ast_check(processor);
2206 }
2207 }
2208 else
2209 if ( processor->state == PROCESSOR_SHUTDOWN &&
2210 thread->sched_pri >= processor->current_pri ) {
2211 cause_ast_check(processor);
2212 }
2213
2214 pset_unlock(pset);
2215 }
2216
2217 #define next_pset(p) (((p)->pset_list != PROCESSOR_SET_NULL)? (p)->pset_list: (p)->node->psets)
2218
2219 /*
2220 * choose_next_pset:
2221 *
2222 * Return the next sibling pset containing
2223 * available processors.
2224 *
2225 * Returns the original pset if none other is
2226 * suitable.
2227 */
2228 static processor_set_t
2229 choose_next_pset(
2230 processor_set_t pset)
2231 {
2232 processor_set_t nset = pset;
2233
2234 do {
2235 nset = next_pset(nset);
2236 } while (nset->processor_count < 1 && nset != pset);
2237
2238 return (nset);
2239 }
2240
2241 /*
2242 * choose_processor:
2243 *
2244 * Choose a processor for the thread, beginning at
2245 * the pset. Accepts an optional processor hint in
2246 * the pset.
2247 *
2248 * Returns a processor, possibly from a different pset.
2249 *
2250 * The thread must be locked. The pset must be locked,
2251 * and the resulting pset is locked on return.
2252 */
2253 static processor_t
2254 choose_processor(
2255 processor_set_t pset,
2256 processor_t processor,
2257 thread_t thread)
2258 {
2259 processor_set_t nset, cset = pset;
2260 processor_meta_t pmeta = PROCESSOR_META_NULL;
2261 processor_t mprocessor;
2262
2263 /*
2264 * Prefer the hinted processor, when appropriate.
2265 */
2266
2267 if (processor != PROCESSOR_NULL) {
2268 if (processor->processor_meta != PROCESSOR_META_NULL)
2269 processor = processor->processor_meta->primary;
2270 }
2271
2272 mprocessor = machine_choose_processor(pset, processor);
2273 if (mprocessor != PROCESSOR_NULL)
2274 processor = mprocessor;
2275
2276 if (processor != PROCESSOR_NULL) {
2277 if (processor->processor_set != pset ||
2278 processor->state == PROCESSOR_INACTIVE ||
2279 processor->state == PROCESSOR_SHUTDOWN ||
2280 processor->state == PROCESSOR_OFF_LINE)
2281 processor = PROCESSOR_NULL;
2282 else
2283 if (processor->state == PROCESSOR_IDLE ||
2284 ((thread->sched_pri >= BASEPRI_RTQUEUES) &&
2285 (processor->current_pri < BASEPRI_RTQUEUES)))
2286 return (processor);
2287 }
2288
2289 /*
2290 * Iterate through the processor sets to locate
2291 * an appropriate processor.
2292 */
2293 do {
2294 /*
2295 * Choose an idle processor.
2296 */
2297 if (!queue_empty(&cset->idle_queue))
2298 return ((processor_t)queue_first(&cset->idle_queue));
2299
2300 if (thread->sched_pri >= BASEPRI_RTQUEUES) {
2301 integer_t lowest_priority = MAXPRI + 1;
2302 integer_t lowest_unpaired = MAXPRI + 1;
2303 uint64_t furthest_deadline = 1;
2304 processor_t lp_processor = PROCESSOR_NULL;
2305 processor_t lp_unpaired = PROCESSOR_NULL;
2306 processor_t fd_processor = PROCESSOR_NULL;
2307
2308 lp_processor = cset->low_pri;
2309 /* Consider hinted processor */
2310 if (lp_processor != PROCESSOR_NULL &&
2311 ((lp_processor->processor_meta == PROCESSOR_META_NULL) ||
2312 ((lp_processor == lp_processor->processor_meta->primary) &&
2313 !queue_empty(&lp_processor->processor_meta->idle_queue))) &&
2314 lp_processor->state != PROCESSOR_INACTIVE &&
2315 lp_processor->state != PROCESSOR_SHUTDOWN &&
2316 lp_processor->state != PROCESSOR_OFF_LINE &&
2317 (lp_processor->current_pri < thread->sched_pri))
2318 return lp_processor;
2319
2320 processor = (processor_t)queue_first(&cset->active_queue);
2321 while (!queue_end(&cset->active_queue, (queue_entry_t)processor)) {
2322 /* Discover the processor executing the
2323 * thread with the lowest priority within
2324 * this pset, or the one with the furthest
2325 * deadline
2326 */
2327 integer_t cpri = processor->current_pri;
2328 if (cpri < lowest_priority) {
2329 lowest_priority = cpri;
2330 lp_processor = processor;
2331 }
2332
2333 if ((cpri >= BASEPRI_RTQUEUES) && (processor->deadline > furthest_deadline)) {
2334 furthest_deadline = processor->deadline;
2335 fd_processor = processor;
2336 }
2337
2338
2339 if (processor->processor_meta != PROCESSOR_META_NULL &&
2340 !queue_empty(&processor->processor_meta->idle_queue)) {
2341 if (cpri < lowest_unpaired) {
2342 lowest_unpaired = cpri;
2343 lp_unpaired = processor;
2344 pmeta = processor->processor_meta;
2345 }
2346 else
2347 if (pmeta == PROCESSOR_META_NULL)
2348 pmeta = processor->processor_meta;
2349 }
2350 processor = (processor_t)queue_next((queue_entry_t)processor);
2351 }
2352
2353 if (thread->sched_pri > lowest_unpaired)
2354 return lp_unpaired;
2355
2356 if (pmeta != PROCESSOR_META_NULL)
2357 return ((processor_t)queue_first(&pmeta->idle_queue));
2358 if (thread->sched_pri > lowest_priority)
2359 return lp_processor;
2360 if (thread->realtime.deadline < furthest_deadline)
2361 return fd_processor;
2362 processor = PROCESSOR_NULL;
2363 }
2364 else {
2365 /*
2366 * Check any hinted processors in the processor set if available.
2367 */
2368 if (cset->low_pri != PROCESSOR_NULL && cset->low_pri->state != PROCESSOR_INACTIVE &&
2369 cset->low_pri->state != PROCESSOR_SHUTDOWN && cset->low_pri->state != PROCESSOR_OFF_LINE &&
2370 (processor == PROCESSOR_NULL ||
2371 (thread->sched_pri > BASEPRI_DEFAULT && cset->low_pri->current_pri < thread->sched_pri))) {
2372 processor = cset->low_pri;
2373 }
2374 else
2375 if (cset->low_count != PROCESSOR_NULL && cset->low_count->state != PROCESSOR_INACTIVE &&
2376 cset->low_count->state != PROCESSOR_SHUTDOWN && cset->low_count->state != PROCESSOR_OFF_LINE &&
2377 (processor == PROCESSOR_NULL || (thread->sched_pri <= BASEPRI_DEFAULT &&
2378 cset->low_count->runq.count < processor->runq.count))) {
2379 processor = cset->low_count;
2380 }
2381
2382 /*
2383 * Otherwise, choose an available processor in the set.
2384 */
2385 if (processor == PROCESSOR_NULL) {
2386 processor = (processor_t)dequeue_head(&cset->active_queue);
2387 if (processor != PROCESSOR_NULL)
2388 enqueue_tail(&cset->active_queue, (queue_entry_t)processor);
2389 }
2390 if (processor != PROCESSOR_NULL && pmeta == PROCESSOR_META_NULL) {
2391 if (processor->processor_meta != PROCESSOR_META_NULL &&
2392 !queue_empty(&processor->processor_meta->idle_queue))
2393 pmeta = processor->processor_meta;
2394 }
2395 }
2396
2397 /*
2398 * Move onto the next processor set.
2399 */
2400 nset = next_pset(cset);
2401
2402 if (nset != pset) {
2403 pset_unlock(cset);
2404
2405 cset = nset;
2406 pset_lock(cset);
2407 }
2408 } while (nset != pset);
2409
2410 /*
2411 * Make sure that we pick a running processor,
2412 * and that the correct processor set is locked.
2413 */
2414 do {
2415 if (pmeta != PROCESSOR_META_NULL) {
2416 if (cset != pmeta->primary->processor_set) {
2417 pset_unlock(cset);
2418
2419 cset = pmeta->primary->processor_set;
2420 pset_lock(cset);
2421 }
2422
2423 if (!queue_empty(&pmeta->idle_queue))
2424 return ((processor_t)queue_first(&pmeta->idle_queue));
2425
2426 pmeta = PROCESSOR_META_NULL;
2427 }
2428
2429 /*
2430 * If we haven't been able to choose a processor,
2431 * pick the boot processor and return it.
2432 */
2433 if (processor == PROCESSOR_NULL) {
2434 processor = master_processor;
2435
2436 /*
2437 * Check that the correct processor set is
2438 * returned locked.
2439 */
2440 if (cset != processor->processor_set) {
2441 pset_unlock(cset);
2442
2443 cset = processor->processor_set;
2444 pset_lock(cset);
2445 }
2446
2447 return (processor);
2448 }
2449
2450 /*
2451 * Check that the processor set for the chosen
2452 * processor is locked.
2453 */
2454 if (cset != processor->processor_set) {
2455 pset_unlock(cset);
2456
2457 cset = processor->processor_set;
2458 pset_lock(cset);
2459 }
2460
2461 /*
2462 * We must verify that the chosen processor is still available.
2463 */
2464 if (processor->state == PROCESSOR_INACTIVE ||
2465 processor->state == PROCESSOR_SHUTDOWN || processor->state == PROCESSOR_OFF_LINE)
2466 processor = PROCESSOR_NULL;
2467 } while (processor == PROCESSOR_NULL);
2468
2469 return (processor);
2470 }
2471
2472 /*
2473 * thread_setrun:
2474 *
2475 * Dispatch thread for execution, onto an idle
2476 * processor or run queue, and signal a preemption
2477 * as appropriate.
2478 *
2479 * Thread must be locked.
2480 */
2481 void
2482 thread_setrun(
2483 thread_t thread,
2484 integer_t options)
2485 {
2486 processor_t processor;
2487 processor_set_t pset;
2488
2489 #if DEBUG
2490 assert(thread_runnable(thread));
2491 #endif
2492
2493 /*
2494 * Update priority if needed.
2495 */
2496 if (thread->sched_stamp != sched_tick)
2497 update_priority(thread);
2498
2499 assert(thread->runq == PROCESSOR_NULL);
2500
2501 if (thread->bound_processor == PROCESSOR_NULL) {
2502 /*
2503 * Unbound case.
2504 */
2505 if (thread->affinity_set != AFFINITY_SET_NULL) {
2506 /*
2507 * Use affinity set policy hint.
2508 */
2509 pset = thread->affinity_set->aset_pset;
2510 pset_lock(pset);
2511
2512 processor = choose_processor(pset, PROCESSOR_NULL, thread);
2513 }
2514 else
2515 if (thread->last_processor != PROCESSOR_NULL) {
2516 /*
2517 * Simple (last processor) affinity case.
2518 */
2519 processor = thread->last_processor;
2520 pset = processor->processor_set;
2521 pset_lock(pset);
2522 processor = choose_processor(pset, processor, thread);
2523 }
2524 else {
2525 /*
2526 * No Affinity case:
2527 *
2528 * Utilitize a per task hint to spread threads
2529 * among the available processor sets.
2530 */
2531 task_t task = thread->task;
2532
2533 pset = task->pset_hint;
2534 if (pset == PROCESSOR_SET_NULL)
2535 pset = current_processor()->processor_set;
2536
2537 pset = choose_next_pset(pset);
2538 pset_lock(pset);
2539
2540 processor = choose_processor(pset, PROCESSOR_NULL, thread);
2541 task->pset_hint = processor->processor_set;
2542 }
2543 }
2544 else {
2545 /*
2546 * Bound case:
2547 *
2548 * Unconditionally dispatch on the processor.
2549 */
2550 processor = thread->bound_processor;
2551 pset = processor->processor_set;
2552 pset_lock(pset);
2553 }
2554
2555 /*
2556 * Dispatch the thread on the choosen processor.
2557 */
2558 if (thread->sched_pri >= BASEPRI_RTQUEUES)
2559 realtime_setrun(processor, thread);
2560 else
2561 processor_setrun(processor, thread, options);
2562 }
2563
2564 processor_set_t
2565 task_choose_pset(
2566 task_t task)
2567 {
2568 processor_set_t pset = task->pset_hint;
2569
2570 if (pset != PROCESSOR_SET_NULL)
2571 pset = choose_next_pset(pset);
2572
2573 return (pset);
2574 }
2575
2576 /*
2577 * processor_queue_shutdown:
2578 *
2579 * Shutdown a processor run queue by
2580 * re-dispatching non-bound threads.
2581 *
2582 * Associated pset must be locked, and is
2583 * returned unlocked.
2584 */
2585 void
2586 processor_queue_shutdown(
2587 processor_t processor)
2588 {
2589 processor_set_t pset = processor->processor_set;
2590 run_queue_t rq = &processor->runq;
2591 queue_t queue = rq->queues + rq->highq;
2592 int pri = rq->highq, count = rq->count;
2593 thread_t next, thread;
2594 queue_head_t tqueue;
2595
2596 queue_init(&tqueue);
2597
2598 while (count > 0) {
2599 thread = (thread_t)queue_first(queue);
2600 while (!queue_end(queue, (queue_entry_t)thread)) {
2601 next = (thread_t)queue_next((queue_entry_t)thread);
2602
2603 if (thread->bound_processor == PROCESSOR_NULL) {
2604 remqueue(queue, (queue_entry_t)thread);
2605
2606 thread->runq = PROCESSOR_NULL;
2607 rq->count--;
2608 if (testbit(pri, sched_preempt_pri)) {
2609 rq->urgency--; assert(rq->urgency >= 0);
2610 }
2611 if (queue_empty(queue)) {
2612 if (pri != IDLEPRI)
2613 clrbit(MAXPRI - pri, rq->bitmap);
2614 rq->highq = MAXPRI - ffsbit(rq->bitmap);
2615 }
2616
2617 enqueue_tail(&tqueue, (queue_entry_t)thread);
2618 }
2619 count--;
2620
2621 thread = next;
2622 }
2623
2624 queue--; pri--;
2625 }
2626
2627 pset_unlock(pset);
2628
2629 while ((thread = (thread_t)dequeue_head(&tqueue)) != THREAD_NULL) {
2630 thread_lock(thread);
2631
2632 thread_setrun(thread, SCHED_TAILQ);
2633
2634 thread_unlock(thread);
2635 }
2636 }
2637
2638 /*
2639 * Check for a preemption point in
2640 * the current context.
2641 *
2642 * Called at splsched.
2643 */
2644 ast_t
2645 csw_check(
2646 processor_t processor)
2647 {
2648 ast_t result = AST_NONE;
2649 run_queue_t runq;
2650
2651 if (first_timeslice(processor)) {
2652 runq = &rt_runq;
2653 if (runq->highq >= BASEPRI_RTQUEUES)
2654 return (AST_PREEMPT | AST_URGENT);
2655
2656 if (runq->highq > processor->current_pri) {
2657 if (runq->urgency > 0)
2658 return (AST_PREEMPT | AST_URGENT);
2659
2660 result |= AST_PREEMPT;
2661 }
2662
2663 runq = &processor->runq;
2664 if (runq->highq > processor->current_pri) {
2665 if (runq->urgency > 0)
2666 return (AST_PREEMPT | AST_URGENT);
2667
2668 result |= AST_PREEMPT;
2669 }
2670 }
2671 else {
2672 runq = &rt_runq;
2673 if (runq->highq >= processor->current_pri) {
2674 if (runq->urgency > 0)
2675 return (AST_PREEMPT | AST_URGENT);
2676
2677 result |= AST_PREEMPT;
2678 }
2679
2680 runq = &processor->runq;
2681 if (runq->highq >= processor->current_pri) {
2682 if (runq->urgency > 0)
2683 return (AST_PREEMPT | AST_URGENT);
2684
2685 result |= AST_PREEMPT;
2686 }
2687 }
2688
2689 if (result != AST_NONE)
2690 return (result);
2691
2692 if (processor->current_pri < BASEPRI_RTQUEUES && processor->processor_meta != PROCESSOR_META_NULL &&
2693 processor->processor_meta->primary != processor)
2694 return (AST_PREEMPT);
2695
2696 if (machine_processor_is_inactive(processor))
2697 return (AST_PREEMPT);
2698
2699 if (processor->active_thread->state & TH_SUSP)
2700 return (AST_PREEMPT);
2701
2702 return (AST_NONE);
2703 }
2704
2705 /*
2706 * set_sched_pri:
2707 *
2708 * Set the scheduled priority of the specified thread.
2709 *
2710 * This may cause the thread to change queues.
2711 *
2712 * Thread must be locked.
2713 */
2714 void
2715 set_sched_pri(
2716 thread_t thread,
2717 int priority)
2718 {
2719 boolean_t removed = run_queue_remove(thread);
2720
2721 thread->sched_pri = priority;
2722 if (removed)
2723 thread_setrun(thread, SCHED_PREEMPT | SCHED_TAILQ);
2724 else
2725 if (thread->state & TH_RUN) {
2726 processor_t processor = thread->last_processor;
2727
2728 if (thread == current_thread()) {
2729 ast_t preempt;
2730
2731 processor->current_pri = priority;
2732 if ((preempt = csw_check(processor)) != AST_NONE)
2733 ast_on(preempt);
2734 }
2735 else
2736 if ( processor != PROCESSOR_NULL &&
2737 processor->active_thread == thread )
2738 cause_ast_check(processor);
2739 }
2740 }
2741
2742 #if 0
2743
2744 static void
2745 run_queue_check(
2746 run_queue_t rq,
2747 thread_t thread)
2748 {
2749 queue_t q;
2750 queue_entry_t qe;
2751
2752 if (rq != thread->runq)
2753 panic("run_queue_check: thread runq");
2754
2755 if (thread->sched_pri > MAXPRI || thread->sched_pri < MINPRI)
2756 panic("run_queue_check: thread sched_pri");
2757
2758 q = &rq->queues[thread->sched_pri];
2759 qe = queue_first(q);
2760 while (!queue_end(q, qe)) {
2761 if (qe == (queue_entry_t)thread)
2762 return;
2763
2764 qe = queue_next(qe);
2765 }
2766
2767 panic("run_queue_check: end");
2768 }
2769
2770 #endif /* DEBUG */
2771
2772 /*
2773 * run_queue_remove:
2774 *
2775 * Remove a thread from a current run queue and
2776 * return TRUE if successful.
2777 *
2778 * Thread must be locked.
2779 */
2780 boolean_t
2781 run_queue_remove(
2782 thread_t thread)
2783 {
2784 processor_t processor = thread->runq;
2785
2786 /*
2787 * If processor is PROCESSOR_NULL, the thread will stay out of the
2788 * run queues because the caller locked the thread. Otherwise
2789 * the thread is on a run queue, but could be chosen for dispatch
2790 * and removed.
2791 */
2792 if (processor != PROCESSOR_NULL) {
2793 void * rqlock;
2794 run_queue_t rq;
2795
2796 /*
2797 * The processor run queues are locked by the
2798 * processor set. Real-time priorities use a
2799 * global queue with a dedicated lock.
2800 */
2801 if (thread->sched_pri < BASEPRI_RTQUEUES) {
2802 rqlock = &processor->processor_set->sched_lock;
2803 rq = &processor->runq;
2804 }
2805 else {
2806 rqlock = &rt_lock; rq = &rt_runq;
2807 }
2808
2809 simple_lock(rqlock);
2810
2811 if (processor == thread->runq) {
2812 /*
2813 * Thread is on a run queue and we have a lock on
2814 * that run queue.
2815 */
2816 remqueue(&rq->queues[0], (queue_entry_t)thread);
2817 rq->count--;
2818 if (testbit(thread->sched_pri, sched_preempt_pri)) {
2819 rq->urgency--; assert(rq->urgency >= 0);
2820 }
2821
2822 if (queue_empty(rq->queues + thread->sched_pri)) {
2823 /* update run queue status */
2824 if (thread->sched_pri != IDLEPRI)
2825 clrbit(MAXPRI - thread->sched_pri, rq->bitmap);
2826 rq->highq = MAXPRI - ffsbit(rq->bitmap);
2827 }
2828
2829 thread->runq = PROCESSOR_NULL;
2830 }
2831 else {
2832 /*
2833 * The thread left the run queue before we could
2834 * lock the run queue.
2835 */
2836 assert(thread->runq == PROCESSOR_NULL);
2837 processor = PROCESSOR_NULL;
2838 }
2839
2840 simple_unlock(rqlock);
2841 }
2842
2843 return (processor != PROCESSOR_NULL);
2844 }
2845
2846 /*
2847 * steal_processor_thread:
2848 *
2849 * Locate a thread to steal from the processor and
2850 * return it.
2851 *
2852 * Associated pset must be locked. Returns THREAD_NULL
2853 * on failure.
2854 */
2855 static thread_t
2856 steal_processor_thread(
2857 processor_t processor)
2858 {
2859 run_queue_t rq = &processor->runq;
2860 queue_t queue = rq->queues + rq->highq;
2861 int pri = rq->highq, count = rq->count;
2862 thread_t thread;
2863
2864 while (count > 0) {
2865 thread = (thread_t)queue_first(queue);
2866 while (!queue_end(queue, (queue_entry_t)thread)) {
2867 if (thread->bound_processor == PROCESSOR_NULL) {
2868 remqueue(queue, (queue_entry_t)thread);
2869
2870 thread->runq = PROCESSOR_NULL;
2871 rq->count--;
2872 if (testbit(pri, sched_preempt_pri)) {
2873 rq->urgency--; assert(rq->urgency >= 0);
2874 }
2875 if (queue_empty(queue)) {
2876 if (pri != IDLEPRI)
2877 clrbit(MAXPRI - pri, rq->bitmap);
2878 rq->highq = MAXPRI - ffsbit(rq->bitmap);
2879 }
2880
2881 return (thread);
2882 }
2883 count--;
2884
2885 thread = (thread_t)queue_next((queue_entry_t)thread);
2886 }
2887
2888 queue--; pri--;
2889 }
2890
2891 return (THREAD_NULL);
2892 }
2893
2894 /*
2895 * Locate and steal a thread, beginning
2896 * at the pset.
2897 *
2898 * The pset must be locked, and is returned
2899 * unlocked.
2900 *
2901 * Returns the stolen thread, or THREAD_NULL on
2902 * failure.
2903 */
2904 static thread_t
2905 steal_thread(
2906 processor_set_t pset)
2907 {
2908 processor_set_t nset, cset = pset;
2909 processor_t processor;
2910 thread_t thread;
2911
2912 do {
2913 processor = (processor_t)queue_first(&cset->active_queue);
2914 while (!queue_end(&cset->active_queue, (queue_entry_t)processor)) {
2915 if (processor->runq.count > 0) {
2916 thread = steal_processor_thread(processor);
2917 if (thread != THREAD_NULL) {
2918 remqueue(&cset->active_queue, (queue_entry_t)processor);
2919 enqueue_tail(&cset->active_queue, (queue_entry_t)processor);
2920
2921 pset_unlock(cset);
2922
2923 return (thread);
2924 }
2925 }
2926
2927 processor = (processor_t)queue_next((queue_entry_t)processor);
2928 }
2929
2930 nset = next_pset(cset);
2931
2932 if (nset != pset) {
2933 pset_unlock(cset);
2934
2935 cset = nset;
2936 pset_lock(cset);
2937 }
2938 } while (nset != pset);
2939
2940 pset_unlock(cset);
2941
2942 return (THREAD_NULL);
2943 }
2944
2945 /*
2946 * This is the processor idle loop, which just looks for other threads
2947 * to execute. Processor idle threads invoke this without supplying a
2948 * current thread to idle without an asserted wait state.
2949 *
2950 * Returns a the next thread to execute if dispatched directly.
2951 */
2952 static thread_t
2953 processor_idle(
2954 thread_t thread,
2955 processor_t processor)
2956 {
2957 processor_set_t pset = processor->processor_set;
2958 thread_t new_thread;
2959 int state;
2960
2961 (void)splsched();
2962
2963 KERNEL_DEBUG_CONSTANT(
2964 MACHDBG_CODE(DBG_MACH_SCHED,MACH_IDLE) | DBG_FUNC_START, (uintptr_t)thread_tid(thread), 0, 0, 0, 0);
2965
2966 timer_switch(&PROCESSOR_DATA(processor, system_state),
2967 mach_absolute_time(), &PROCESSOR_DATA(processor, idle_state));
2968 PROCESSOR_DATA(processor, current_state) = &PROCESSOR_DATA(processor, idle_state);
2969
2970 while (processor->next_thread == THREAD_NULL && processor->runq.count == 0 && rt_runq.count == 0 &&
2971 (thread == THREAD_NULL || ((thread->state & (TH_WAIT|TH_SUSP)) == TH_WAIT && !thread->wake_active))) {
2972 machine_idle();
2973
2974 (void)splsched();
2975
2976 if (processor->state == PROCESSOR_INACTIVE && !machine_processor_is_inactive(processor))
2977 break;
2978 }
2979
2980 timer_switch(&PROCESSOR_DATA(processor, idle_state),
2981 mach_absolute_time(), &PROCESSOR_DATA(processor, system_state));
2982 PROCESSOR_DATA(processor, current_state) = &PROCESSOR_DATA(processor, system_state);
2983
2984 pset_lock(pset);
2985
2986 state = processor->state;
2987 if (state == PROCESSOR_DISPATCHING) {
2988 /*
2989 * Commmon case -- cpu dispatched.
2990 */
2991 new_thread = processor->next_thread;
2992 processor->next_thread = THREAD_NULL;
2993 processor->state = PROCESSOR_RUNNING;
2994
2995 if ( processor->runq.highq > new_thread->sched_pri ||
2996 (rt_runq.highq > 0 && rt_runq.highq >= new_thread->sched_pri) ) {
2997 processor->deadline = UINT64_MAX;
2998
2999 pset_unlock(pset);
3000
3001 thread_lock(new_thread);
3002 thread_setrun(new_thread, SCHED_HEADQ);
3003 thread_unlock(new_thread);
3004
3005 KERNEL_DEBUG_CONSTANT(
3006 MACHDBG_CODE(DBG_MACH_SCHED,MACH_IDLE) | DBG_FUNC_END, (uintptr_t)thread_tid(thread), state, 0, 0, 0);
3007
3008 return (THREAD_NULL);
3009 }
3010
3011 pset_unlock(pset);
3012
3013 KERNEL_DEBUG_CONSTANT(
3014 MACHDBG_CODE(DBG_MACH_SCHED,MACH_IDLE) | DBG_FUNC_END, (uintptr_t)thread_tid(thread), state, (uintptr_t)thread_tid(new_thread), 0, 0);
3015
3016 return (new_thread);
3017 }
3018 else
3019 if (state == PROCESSOR_IDLE) {
3020 remqueue(&pset->idle_queue, (queue_entry_t)processor);
3021
3022 processor->state = PROCESSOR_RUNNING;
3023 enqueue_tail(&pset->active_queue, (queue_entry_t)processor);
3024 }
3025 else
3026 if (state == PROCESSOR_INACTIVE) {
3027 processor->state = PROCESSOR_RUNNING;
3028 enqueue_tail(&pset->active_queue, (queue_entry_t)processor);
3029 }
3030 else
3031 if (state == PROCESSOR_SHUTDOWN) {
3032 /*
3033 * Going off-line. Force a
3034 * reschedule.
3035 */
3036 if ((new_thread = processor->next_thread) != THREAD_NULL) {
3037 processor->next_thread = THREAD_NULL;
3038 processor->deadline = UINT64_MAX;
3039
3040 pset_unlock(pset);
3041
3042 thread_lock(new_thread);
3043 thread_setrun(new_thread, SCHED_HEADQ);
3044 thread_unlock(new_thread);
3045
3046 KERNEL_DEBUG_CONSTANT(
3047 MACHDBG_CODE(DBG_MACH_SCHED,MACH_IDLE) | DBG_FUNC_END, (uintptr_t)thread_tid(thread), state, 0, 0, 0);
3048
3049 return (THREAD_NULL);
3050 }
3051 }
3052
3053 pset_unlock(pset);
3054
3055 KERNEL_DEBUG_CONSTANT(
3056 MACHDBG_CODE(DBG_MACH_SCHED,MACH_IDLE) | DBG_FUNC_END, (uintptr_t)thread_tid(thread), state, 0, 0, 0);
3057
3058 return (THREAD_NULL);
3059 }
3060
3061 /*
3062 * Each processor has a dedicated thread which
3063 * executes the idle loop when there is no suitable
3064 * previous context.
3065 */
3066 void
3067 idle_thread(void)
3068 {
3069 processor_t processor = current_processor();
3070 thread_t new_thread;
3071
3072 new_thread = processor_idle(THREAD_NULL, processor);
3073 if (new_thread != THREAD_NULL) {
3074 thread_run(processor->idle_thread, (thread_continue_t)idle_thread, NULL, new_thread);
3075 /*NOTREACHED*/
3076 }
3077
3078 thread_block((thread_continue_t)idle_thread);
3079 /*NOTREACHED*/
3080 }
3081
3082 kern_return_t
3083 idle_thread_create(
3084 processor_t processor)
3085 {
3086 kern_return_t result;
3087 thread_t thread;
3088 spl_t s;
3089
3090 result = kernel_thread_create((thread_continue_t)idle_thread, NULL, MAXPRI_KERNEL, &thread);
3091 if (result != KERN_SUCCESS)
3092 return (result);
3093
3094 s = splsched();
3095 thread_lock(thread);
3096 thread->bound_processor = processor;
3097 processor->idle_thread = thread;
3098 thread->sched_pri = thread->priority = IDLEPRI;
3099 thread->state = (TH_RUN | TH_IDLE);
3100 thread_unlock(thread);
3101 splx(s);
3102
3103 thread_deallocate(thread);
3104
3105 return (KERN_SUCCESS);
3106 }
3107
3108 static uint64_t sched_tick_deadline;
3109
3110 /*
3111 * sched_startup:
3112 *
3113 * Kicks off scheduler services.
3114 *
3115 * Called at splsched.
3116 */
3117 void
3118 sched_startup(void)
3119 {
3120 kern_return_t result;
3121 thread_t thread;
3122
3123 result = kernel_thread_start_priority((thread_continue_t)sched_tick_thread, NULL, MAXPRI_KERNEL, &thread);
3124 if (result != KERN_SUCCESS)
3125 panic("sched_startup");
3126
3127 thread_deallocate(thread);
3128
3129 /*
3130 * Yield to the sched_tick_thread while it times
3131 * a series of context switches back. It stores
3132 * the baseline value in sched_cswtime.
3133 *
3134 * The current thread is the only other thread
3135 * active at this point.
3136 */
3137 while (sched_cswtime == 0)
3138 thread_block(THREAD_CONTINUE_NULL);
3139
3140 thread_daemon_init();
3141
3142 thread_call_initialize();
3143 }
3144
3145 /*
3146 * sched_tick_thread:
3147 *
3148 * Perform periodic bookkeeping functions about ten
3149 * times per second.
3150 */
3151 static void
3152 sched_tick_continue(void)
3153 {
3154 uint64_t abstime = mach_absolute_time();
3155
3156 sched_tick++;
3157
3158 /*
3159 * Compute various averages.
3160 */
3161 compute_averages();
3162
3163 /*
3164 * Scan the run queues for threads which
3165 * may need to be updated.
3166 */
3167 thread_update_scan();
3168
3169 clock_deadline_for_periodic_event(sched_tick_interval, abstime,
3170 &sched_tick_deadline);
3171
3172 assert_wait_deadline((event_t)sched_tick_thread, THREAD_UNINT, sched_tick_deadline);
3173 thread_block((thread_continue_t)sched_tick_continue);
3174 /*NOTREACHED*/
3175 }
3176
3177 /*
3178 * Time a series of context switches to determine
3179 * a baseline. Toss the high and low and return
3180 * the one-way value.
3181 */
3182 static uint32_t
3183 time_cswitch(void)
3184 {
3185 uint32_t new, hi, low, accum;
3186 uint64_t abstime;
3187 int i, tries = 7;
3188
3189 accum = hi = low = 0;
3190 for (i = 0; i < tries; ++i) {
3191 abstime = mach_absolute_time();
3192 thread_block(THREAD_CONTINUE_NULL);
3193
3194 new = (uint32_t)(mach_absolute_time() - abstime);
3195
3196 if (i == 0)
3197 accum = hi = low = new;
3198 else {
3199 if (new < low)
3200 low = new;
3201 else
3202 if (new > hi)
3203 hi = new;
3204 accum += new;
3205 }
3206 }
3207
3208 return ((accum - hi - low) / (2 * (tries - 2)));
3209 }
3210
3211 void
3212 sched_tick_thread(void)
3213 {
3214 sched_cswtime = time_cswitch();
3215
3216 sched_tick_deadline = mach_absolute_time();
3217
3218 sched_tick_continue();
3219 /*NOTREACHED*/
3220 }
3221
3222 /*
3223 * thread_update_scan / runq_scan:
3224 *
3225 * Scan the run queues to account for timesharing threads
3226 * which need to be updated.
3227 *
3228 * Scanner runs in two passes. Pass one squirrels likely
3229 * threads away in an array, pass two does the update.
3230 *
3231 * This is necessary because the run queue is locked for
3232 * the candidate scan, but the thread is locked for the update.
3233 *
3234 * Array should be sized to make forward progress, without
3235 * disabling preemption for long periods.
3236 */
3237
3238 #define THREAD_UPDATE_SIZE 128
3239
3240 static thread_t thread_update_array[THREAD_UPDATE_SIZE];
3241 static int thread_update_count = 0;
3242
3243 /*
3244 * Scan a runq for candidate threads.
3245 *
3246 * Returns TRUE if retry is needed.
3247 */
3248 static boolean_t
3249 runq_scan(
3250 run_queue_t runq)
3251 {
3252 register int count;
3253 register queue_t q;
3254 register thread_t thread;
3255
3256 if ((count = runq->count) > 0) {
3257 q = runq->queues + runq->highq;
3258 while (count > 0) {
3259 queue_iterate(q, thread, thread_t, links) {
3260 if ( thread->sched_stamp != sched_tick &&
3261 (thread->sched_mode & TH_MODE_TIMESHARE) ) {
3262 if (thread_update_count == THREAD_UPDATE_SIZE)
3263 return (TRUE);
3264
3265 thread_update_array[thread_update_count++] = thread;
3266 thread_reference_internal(thread);
3267 }
3268
3269 count--;
3270 }
3271
3272 q--;
3273 }
3274 }
3275
3276 return (FALSE);
3277 }
3278
3279 static void
3280 thread_update_scan(void)
3281 {
3282 boolean_t restart_needed = FALSE;
3283 processor_t processor = processor_list;
3284 processor_set_t pset;
3285 thread_t thread;
3286 spl_t s;
3287
3288 do {
3289 do {
3290 pset = processor->processor_set;
3291
3292 s = splsched();
3293 pset_lock(pset);
3294
3295 restart_needed = runq_scan(&processor->runq);
3296
3297 pset_unlock(pset);
3298 splx(s);
3299
3300 if (restart_needed)
3301 break;
3302
3303 thread = processor->idle_thread;
3304 if (thread != THREAD_NULL && thread->sched_stamp != sched_tick) {
3305 if (thread_update_count == THREAD_UPDATE_SIZE) {
3306 restart_needed = TRUE;
3307 break;
3308 }
3309
3310 thread_update_array[thread_update_count++] = thread;
3311 thread_reference_internal(thread);
3312 }
3313 } while ((processor = processor->processor_list) != NULL);
3314
3315 /*
3316 * Ok, we now have a collection of candidates -- fix them.
3317 */
3318 while (thread_update_count > 0) {
3319 thread = thread_update_array[--thread_update_count];
3320 thread_update_array[thread_update_count] = THREAD_NULL;
3321
3322 s = splsched();
3323 thread_lock(thread);
3324 if ( !(thread->state & (TH_WAIT|TH_SUSP)) &&
3325 thread->sched_stamp != sched_tick )
3326 update_priority(thread);
3327 thread_unlock(thread);
3328 splx(s);
3329
3330 thread_deallocate(thread);
3331 }
3332 } while (restart_needed);
3333 }
3334
3335 /*
3336 * Just in case someone doesn't use the macro
3337 */
3338 #undef thread_wakeup
3339 void
3340 thread_wakeup(
3341 event_t x);
3342
3343 void
3344 thread_wakeup(
3345 event_t x)
3346 {
3347 thread_wakeup_with_result(x, THREAD_AWAKENED);
3348 }
3349
3350 boolean_t
3351 preemption_enabled(void)
3352 {
3353 return (get_preemption_level() == 0 && ml_get_interrupts_enabled());
3354 }
3355
3356 #if DEBUG
3357 static boolean_t
3358 thread_runnable(
3359 thread_t thread)
3360 {
3361 return ((thread->state & (TH_RUN|TH_WAIT)) == TH_RUN);
3362 }
3363 #endif /* DEBUG */
3364
3365 #if MACH_KDB
3366 #include <ddb/db_output.h>
3367 #define printf kdbprintf
3368 void db_sched(void);
3369
3370 void
3371 db_sched(void)
3372 {
3373 iprintf("Scheduling Statistics:\n");
3374 db_indent += 2;
3375 iprintf("Thread invocations: csw %d same %d\n",
3376 c_thread_invoke_csw, c_thread_invoke_same);
3377 #if MACH_COUNTERS
3378 iprintf("Thread block: calls %d\n",
3379 c_thread_block_calls);
3380 iprintf("Idle thread:\n\thandoff %d block %d\n",
3381 c_idle_thread_handoff,
3382 c_idle_thread_block);
3383 iprintf("Sched thread blocks: %d\n", c_sched_thread_block);
3384 #endif /* MACH_COUNTERS */
3385 db_indent -= 2;
3386 }
3387
3388 #include <ddb/db_output.h>
3389 void db_show_thread_log(void);
3390
3391 void
3392 db_show_thread_log(void)
3393 {
3394 }
3395 #endif /* MACH_KDB */
mirror of XNU