]> git.saurik.com Git - apple/xnu.git/blame - osfmk/kern/sched_prim.c
xnu-792.24.17.tar.gz
[apple/xnu.git] / osfmk / kern / sched_prim.c
CommitLineData
1c79356b 1/*
3a60a9f5 2 * Copyright (c) 2000-2005 Apple Computer, Inc. All rights reserved.
1c79356b 3 *
6601e61a 4 * @APPLE_LICENSE_HEADER_START@
1c79356b 5 *
6601e61a
A
6 * The contents of this file constitute Original Code as defined in and
7 * are subject to the Apple Public Source License Version 1.1 (the
8 * "License"). You may not use this file except in compliance with the
9 * License. Please obtain a copy of the License at
10 * http://www.apple.com/publicsource and read it before using this file.
8f6c56a5 11 *
6601e61a
A
12 * This Original Code and all software distributed under the License are
13 * distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER
8f6c56a5
A
14 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
15 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
6601e61a
A
16 * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT. Please see the
17 * License for the specific language governing rights and limitations
18 * under the License.
8f6c56a5 19 *
6601e61a 20 * @APPLE_LICENSE_HEADER_END@
1c79356b
A
21 */
22/*
23 * @OSF_FREE_COPYRIGHT@
24 */
25/*
26 * Mach Operating System
27 * Copyright (c) 1991,1990,1989,1988,1987 Carnegie Mellon University
28 * All Rights Reserved.
29 *
30 * Permission to use, copy, modify and distribute this software and its
31 * documentation is hereby granted, provided that both the copyright
32 * notice and this permission notice appear in all copies of the
33 * software, derivative works or modified versions, and any portions
34 * thereof, and that both notices appear in supporting documentation.
35 *
36 * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS"
37 * CONDITION. CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND FOR
38 * ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
39 *
40 * Carnegie Mellon requests users of this software to return to
41 *
42 * Software Distribution Coordinator or Software.Distribution@CS.CMU.EDU
43 * School of Computer Science
44 * Carnegie Mellon University
45 * Pittsburgh PA 15213-3890
46 *
47 * any improvements or extensions that they make and grant Carnegie Mellon
48 * the rights to redistribute these changes.
49 */
50/*
51 */
52/*
53 * File: sched_prim.c
54 * Author: Avadis Tevanian, Jr.
55 * Date: 1986
56 *
57 * Scheduling primitives
58 *
59 */
60
61#include <debug.h>
1c79356b 62#include <mach_kdb.h>
1c79356b
A
63
64#include <ddb/db_output.h>
91447636
A
65
66#include <mach/mach_types.h>
1c79356b 67#include <mach/machine.h>
91447636
A
68#include <mach/policy.h>
69#include <mach/sync_policy.h>
70
1c79356b
A
71#include <machine/machine_routines.h>
72#include <machine/sched_param.h>
91447636
A
73
74#include <kern/kern_types.h>
1c79356b
A
75#include <kern/clock.h>
76#include <kern/counters.h>
77#include <kern/cpu_number.h>
78#include <kern/cpu_data.h>
91447636 79#include <kern/debug.h>
1c79356b
A
80#include <kern/lock.h>
81#include <kern/macro_help.h>
82#include <kern/machine.h>
83#include <kern/misc_protos.h>
84#include <kern/processor.h>
85#include <kern/queue.h>
86#include <kern/sched.h>
87#include <kern/sched_prim.h>
88#include <kern/syscall_subr.h>
89#include <kern/task.h>
90#include <kern/thread.h>
91447636
A
91#include <kern/wait_queue.h>
92
1c79356b
A
93#include <vm/pmap.h>
94#include <vm/vm_kern.h>
95#include <vm/vm_map.h>
91447636 96
1c79356b
A
97#include <sys/kdebug.h>
98
6601e61a
A
99#ifdef __ppc__
100#include <ppc/pms.h>
101#endif
3a60a9f5 102
0b4e3aa0 103#define DEFAULT_PREEMPTION_RATE 100 /* (1/s) */
1c79356b
A
104int default_preemption_rate = DEFAULT_PREEMPTION_RATE;
105
0b4e3aa0
A
106#define MAX_UNSAFE_QUANTA 800
107int max_unsafe_quanta = MAX_UNSAFE_QUANTA;
108
109#define MAX_POLL_QUANTA 2
110int max_poll_quanta = MAX_POLL_QUANTA;
111
112#define SCHED_POLL_YIELD_SHIFT 4 /* 1/16 */
113int sched_poll_yield_shift = SCHED_POLL_YIELD_SHIFT;
114
55e303ae
A
115uint64_t max_unsafe_computation;
116uint32_t sched_safe_duration;
117uint64_t max_poll_computation;
118
119uint32_t std_quantum;
120uint32_t min_std_quantum;
121
91447636
A
122uint32_t std_quantum_us;
123
55e303ae
A
124uint32_t max_rt_quantum;
125uint32_t min_rt_quantum;
126
91447636
A
127uint32_t sched_cswtime;
128
129static uint32_t delay_idle_limit, delay_idle_spin;
130static processor_t delay_idle(
131 processor_t processor,
132 thread_t self);
55e303ae 133
1c79356b 134unsigned sched_tick;
91447636 135uint32_t sched_tick_interval;
1c79356b 136
91447636 137uint32_t sched_pri_shift;
1c79356b
A
138
139/* Forwards */
1c79356b
A
140void wait_queues_init(void);
141
91447636
A
142static void load_shift_init(void);
143
55e303ae
A
144static thread_t choose_thread(
145 processor_set_t pset,
146 processor_t processor);
1c79356b 147
91447636 148static void thread_update_scan(void);
1c79356b 149
1c79356b 150#if DEBUG
0b4e3aa0 151static
1c79356b
A
152boolean_t thread_runnable(
153 thread_t thread);
154
0b4e3aa0
A
155#endif /*DEBUG*/
156
157
1c79356b
A
158/*
159 * State machine
160 *
161 * states are combinations of:
162 * R running
163 * W waiting (or on wait queue)
164 * N non-interruptible
165 * O swapped out
166 * I being swapped in
167 *
168 * init action
169 * assert_wait thread_block clear_wait swapout swapin
170 *
171 * R RW, RWN R; setrun - -
172 * RN RWN RN; setrun - -
173 *
174 * RW W R -
175 * RWN WN RN -
176 *
177 * W R; setrun WO
178 * WN RN; setrun -
179 *
180 * RO - - R
181 *
182 */
183
184/*
185 * Waiting protocols and implementation:
186 *
187 * Each thread may be waiting for exactly one event; this event
188 * is set using assert_wait(). That thread may be awakened either
189 * by performing a thread_wakeup_prim() on its event,
190 * or by directly waking that thread up with clear_wait().
191 *
192 * The implementation of wait events uses a hash table. Each
193 * bucket is queue of threads having the same hash function
194 * value; the chain for the queue (linked list) is the run queue
195 * field. [It is not possible to be waiting and runnable at the
196 * same time.]
197 *
198 * Locks on both the thread and on the hash buckets govern the
199 * wait event field and the queue chain field. Because wakeup
200 * operations only have the event as an argument, the event hash
201 * bucket must be locked before any thread.
202 *
203 * Scheduling operations may also occur at interrupt level; therefore,
204 * interrupts below splsched() must be prevented when holding
205 * thread or hash bucket locks.
206 *
207 * The wait event hash table declarations are as follows:
208 */
209
210#define NUMQUEUES 59
211
212struct wait_queue wait_queues[NUMQUEUES];
213
214#define wait_hash(event) \
215 ((((int)(event) < 0)? ~(int)(event): (int)(event)) % NUMQUEUES)
216
91447636
A
217int8_t sched_load_shifts[NRQS];
218
1c79356b
A
219void
220sched_init(void)
221{
222 /*
0b4e3aa0
A
223 * Calculate the timeslicing quantum
224 * in us.
1c79356b
A
225 */
226 if (default_preemption_rate < 1)
227 default_preemption_rate = DEFAULT_PREEMPTION_RATE;
0b4e3aa0 228 std_quantum_us = (1000 * 1000) / default_preemption_rate;
1c79356b 229
0b4e3aa0 230 printf("standard timeslicing quantum is %d us\n", std_quantum_us);
1c79356b 231
55e303ae
A
232 sched_safe_duration = (2 * max_unsafe_quanta / default_preemption_rate) *
233 (1 << SCHED_TICK_SHIFT);
234
1c79356b 235 wait_queues_init();
91447636
A
236 load_shift_init();
237 pset_init(&default_pset);
1c79356b 238 sched_tick = 0;
1c79356b 239 ast_init();
1c79356b
A
240}
241
55e303ae
A
242void
243sched_timebase_init(void)
244{
91447636
A
245 uint64_t abstime;
246 uint32_t shift;
55e303ae 247
91447636 248 /* standard timeslicing quantum */
55e303ae
A
249 clock_interval_to_absolutetime_interval(
250 std_quantum_us, NSEC_PER_USEC, &abstime);
251 assert((abstime >> 32) == 0 && (uint32_t)abstime != 0);
252 std_quantum = abstime;
253
91447636 254 /* smallest remaining quantum (250 us) */
55e303ae
A
255 clock_interval_to_absolutetime_interval(250, NSEC_PER_USEC, &abstime);
256 assert((abstime >> 32) == 0 && (uint32_t)abstime != 0);
257 min_std_quantum = abstime;
258
91447636 259 /* smallest rt computaton (50 us) */
55e303ae
A
260 clock_interval_to_absolutetime_interval(50, NSEC_PER_USEC, &abstime);
261 assert((abstime >> 32) == 0 && (uint32_t)abstime != 0);
262 min_rt_quantum = abstime;
263
91447636 264 /* maximum rt computation (50 ms) */
55e303ae
A
265 clock_interval_to_absolutetime_interval(
266 50, 1000*NSEC_PER_USEC, &abstime);
267 assert((abstime >> 32) == 0 && (uint32_t)abstime != 0);
268 max_rt_quantum = abstime;
269
91447636
A
270 /* scheduler tick interval */
271 clock_interval_to_absolutetime_interval(USEC_PER_SEC >> SCHED_TICK_SHIFT,
272 NSEC_PER_USEC, &abstime);
55e303ae
A
273 assert((abstime >> 32) == 0 && (uint32_t)abstime != 0);
274 sched_tick_interval = abstime;
275
91447636
A
276 /*
277 * Compute conversion factor from usage to
278 * timesharing priorities with 5/8 ** n aging.
279 */
280 abstime = (abstime * 5) / 3;
281 for (shift = 0; abstime > BASEPRI_DEFAULT; ++shift)
282 abstime >>= 1;
283 sched_pri_shift = shift;
284
55e303ae
A
285 max_unsafe_computation = max_unsafe_quanta * std_quantum;
286 max_poll_computation = max_poll_quanta * std_quantum;
91447636
A
287
288 /* delay idle constant(s) (60, 1 us) */
289 clock_interval_to_absolutetime_interval(60, NSEC_PER_USEC, &abstime);
290 assert((abstime >> 32) == 0 && (uint32_t)abstime != 0);
291 delay_idle_limit = abstime;
292
293 clock_interval_to_absolutetime_interval(1, NSEC_PER_USEC, &abstime);
294 assert((abstime >> 32) == 0 && (uint32_t)abstime != 0);
295 delay_idle_spin = abstime;
55e303ae
A
296}
297
1c79356b
A
298void
299wait_queues_init(void)
300{
301 register int i;
302
303 for (i = 0; i < NUMQUEUES; i++) {
304 wait_queue_init(&wait_queues[i], SYNC_POLICY_FIFO);
305 }
306}
307
91447636
A
308/*
309 * Set up values for timeshare
310 * loading factors.
311 */
312static void
313load_shift_init(void)
314{
315 int8_t k, *p = sched_load_shifts;
316 uint32_t i, j;
317
318 *p++ = INT8_MIN; *p++ = 0;
319
320 for (i = j = 2, k = 1; i < NRQS; ++k) {
321 for (j <<= 1; i < j; ++i)
322 *p++ = k;
323 }
324}
325
1c79356b 326/*
0b4e3aa0 327 * Thread wait timer expiration.
1c79356b
A
328 */
329void
330thread_timer_expire(
91447636
A
331 void *p0,
332 __unused void *p1)
1c79356b
A
333{
334 thread_t thread = p0;
335 spl_t s;
336
337 s = splsched();
55e303ae 338 thread_lock(thread);
91447636 339 if (--thread->wait_timer_active == 0) {
0b4e3aa0
A
340 if (thread->wait_timer_is_set) {
341 thread->wait_timer_is_set = FALSE;
55e303ae 342 clear_wait_internal(thread, THREAD_TIMED_OUT);
0b4e3aa0 343 }
1c79356b 344 }
55e303ae 345 thread_unlock(thread);
1c79356b
A
346 splx(s);
347}
348
349/*
350 * thread_set_timer:
351 *
352 * Set a timer for the current thread, if the thread
353 * is ready to wait. Must be called between assert_wait()
354 * and thread_block().
355 */
356void
357thread_set_timer(
0b4e3aa0
A
358 uint32_t interval,
359 uint32_t scale_factor)
1c79356b
A
360{
361 thread_t thread = current_thread();
0b4e3aa0 362 uint64_t deadline;
1c79356b
A
363 spl_t s;
364
365 s = splsched();
1c79356b
A
366 thread_lock(thread);
367 if ((thread->state & TH_WAIT) != 0) {
368 clock_interval_to_deadline(interval, scale_factor, &deadline);
91447636
A
369 if (!timer_call_enter(&thread->wait_timer, deadline))
370 thread->wait_timer_active++;
1c79356b
A
371 thread->wait_timer_is_set = TRUE;
372 }
373 thread_unlock(thread);
1c79356b
A
374 splx(s);
375}
376
377void
378thread_set_timer_deadline(
0b4e3aa0 379 uint64_t deadline)
1c79356b
A
380{
381 thread_t thread = current_thread();
382 spl_t s;
383
384 s = splsched();
1c79356b
A
385 thread_lock(thread);
386 if ((thread->state & TH_WAIT) != 0) {
91447636
A
387 if (!timer_call_enter(&thread->wait_timer, deadline))
388 thread->wait_timer_active++;
1c79356b
A
389 thread->wait_timer_is_set = TRUE;
390 }
391 thread_unlock(thread);
1c79356b
A
392 splx(s);
393}
394
395void
396thread_cancel_timer(void)
397{
398 thread_t thread = current_thread();
399 spl_t s;
400
401 s = splsched();
55e303ae 402 thread_lock(thread);
1c79356b
A
403 if (thread->wait_timer_is_set) {
404 if (timer_call_cancel(&thread->wait_timer))
405 thread->wait_timer_active--;
406 thread->wait_timer_is_set = FALSE;
407 }
55e303ae 408 thread_unlock(thread);
1c79356b
A
409 splx(s);
410}
411
1c79356b 412/*
91447636
A
413 * thread_unblock:
414 *
415 * Unblock thread on wake up.
416 *
417 * Returns TRUE if the thread is still running.
418 *
419 * Thread must be locked.
1c79356b 420 */
91447636
A
421boolean_t
422thread_unblock(
423 thread_t thread,
424 wait_result_t wresult)
1c79356b 425{
91447636 426 boolean_t result = FALSE;
0b4e3aa0 427
91447636
A
428 /*
429 * Set wait_result.
430 */
431 thread->wait_result = wresult;
1c79356b 432
91447636
A
433 /*
434 * Cancel pending wait timer.
435 */
1c79356b
A
436 if (thread->wait_timer_is_set) {
437 if (timer_call_cancel(&thread->wait_timer))
438 thread->wait_timer_active--;
439 thread->wait_timer_is_set = FALSE;
440 }
441
91447636
A
442 /*
443 * Update scheduling state.
444 */
445 thread->state &= ~(TH_WAIT|TH_UNINT);
1c79356b 446
91447636
A
447 if (!(thread->state & TH_RUN)) {
448 thread->state |= TH_RUN;
1c79356b 449
91447636
A
450 /*
451 * Mark unblocked if call out.
452 */
453 if (thread->options & TH_OPT_CALLOUT)
454 call_thread_unblock();
1c79356b 455
91447636
A
456 /*
457 * Update pset run counts.
458 */
459 pset_run_incr(thread->processor_set);
460 if (thread->sched_mode & TH_MODE_TIMESHARE)
461 pset_share_incr(thread->processor_set);
1c79356b 462 }
91447636
A
463 else
464 result = TRUE;
1c79356b 465
91447636
A
466 /*
467 * Calculate deadline for real-time threads.
468 */
469 if (thread->sched_mode & TH_MODE_REALTIME) {
470 thread->realtime.deadline = mach_absolute_time();
471 thread->realtime.deadline += thread->realtime.constraint;
0b4e3aa0
A
472 }
473
91447636
A
474 /*
475 * Clear old quantum, fail-safe computation, etc.
476 */
477 thread->current_quantum = 0;
478 thread->computation_metered = 0;
479 thread->reason = AST_NONE;
1c79356b 480
91447636
A
481 KERNEL_DEBUG_CONSTANT(
482 MACHDBG_CODE(DBG_MACH_SCHED,MACH_MAKE_RUNNABLE) | DBG_FUNC_NONE,
483 (int)thread, (int)thread->sched_pri, 0, 0, 0);
484
485 return (result);
1c79356b
A
486}
487
488/*
91447636 489 * Routine: thread_go
1c79356b 490 * Purpose:
91447636 491 * Unblock and dispatch thread.
1c79356b
A
492 * Conditions:
493 * thread lock held, IPC locks may be held.
494 * thread must have been pulled from wait queue under same lock hold.
9bccf70c
A
495 * Returns:
496 * KERN_SUCCESS - Thread was set running
497 * KERN_NOT_WAITING - Thread was not waiting
1c79356b 498 */
9bccf70c 499kern_return_t
91447636 500thread_go(
1c79356b 501 thread_t thread,
55e303ae 502 wait_result_t wresult)
1c79356b 503{
1c79356b 504 assert(thread->at_safe_point == FALSE);
9bccf70c 505 assert(thread->wait_event == NO_EVENT64);
1c79356b
A
506 assert(thread->wait_queue == WAIT_QUEUE_NULL);
507
9bccf70c 508 if ((thread->state & (TH_WAIT|TH_TERMINATE)) == TH_WAIT) {
91447636 509 if (!thread_unblock(thread, wresult))
55e303ae 510 thread_setrun(thread, SCHED_PREEMPT | SCHED_TAILQ);
55e303ae
A
511
512 return (KERN_SUCCESS);
1c79356b 513 }
55e303ae
A
514
515 return (KERN_NOT_WAITING);
1c79356b
A
516}
517
9bccf70c
A
518/*
519 * Routine: thread_mark_wait_locked
520 * Purpose:
521 * Mark a thread as waiting. If, given the circumstances,
522 * it doesn't want to wait (i.e. already aborted), then
523 * indicate that in the return value.
524 * Conditions:
525 * at splsched() and thread is locked.
526 */
527__private_extern__
528wait_result_t
1c79356b 529thread_mark_wait_locked(
9bccf70c
A
530 thread_t thread,
531 wait_interrupt_t interruptible)
1c79356b 532{
55e303ae 533 boolean_t at_safe_point;
1c79356b 534
9bccf70c
A
535 /*
536 * The thread may have certain types of interrupts/aborts masked
537 * off. Even if the wait location says these types of interrupts
538 * are OK, we have to honor mask settings (outer-scoped code may
539 * not be able to handle aborts at the moment).
540 */
91447636
A
541 if (interruptible > (thread->options & TH_OPT_INTMASK))
542 interruptible = thread->options & TH_OPT_INTMASK;
9bccf70c
A
543
544 at_safe_point = (interruptible == THREAD_ABORTSAFE);
545
55e303ae
A
546 if ( interruptible == THREAD_UNINT ||
547 !(thread->state & TH_ABORT) ||
548 (!at_safe_point &&
549 (thread->state & TH_ABORT_SAFELY)) ) {
9bccf70c
A
550 thread->state |= (interruptible) ? TH_WAIT : (TH_WAIT | TH_UNINT);
551 thread->at_safe_point = at_safe_point;
9bccf70c 552 return (thread->wait_result = THREAD_WAITING);
9bccf70c 553 }
55e303ae
A
554 else
555 if (thread->state & TH_ABORT_SAFELY)
556 thread->state &= ~(TH_ABORT|TH_ABORT_SAFELY);
557
9bccf70c 558 return (thread->wait_result = THREAD_INTERRUPTED);
1c79356b
A
559}
560
9bccf70c
A
561/*
562 * Routine: thread_interrupt_level
563 * Purpose:
564 * Set the maximum interruptible state for the
565 * current thread. The effective value of any
566 * interruptible flag passed into assert_wait
567 * will never exceed this.
568 *
569 * Useful for code that must not be interrupted,
570 * but which calls code that doesn't know that.
571 * Returns:
572 * The old interrupt level for the thread.
573 */
574__private_extern__
575wait_interrupt_t
576thread_interrupt_level(
577 wait_interrupt_t new_level)
578{
579 thread_t thread = current_thread();
91447636 580 wait_interrupt_t result = thread->options & TH_OPT_INTMASK;
1c79356b 581
91447636 582 thread->options = (thread->options & ~TH_OPT_INTMASK) | (new_level & TH_OPT_INTMASK);
1c79356b 583
91447636 584 return result;
1c79356b
A
585}
586
587/*
588 * Check to see if an assert wait is possible, without actually doing one.
589 * This is used by debug code in locks and elsewhere to verify that it is
590 * always OK to block when trying to take a blocking lock (since waiting
591 * for the actual assert_wait to catch the case may make it hard to detect
592 * this case.
593 */
594boolean_t
595assert_wait_possible(void)
596{
597
598 thread_t thread;
1c79356b
A
599
600#if DEBUG
601 if(debug_mode) return TRUE; /* Always succeed in debug mode */
602#endif
603
604 thread = current_thread();
605
606 return (thread == NULL || wait_queue_assert_possible(thread));
607}
608
609/*
610 * assert_wait:
611 *
612 * Assert that the current thread is about to go to
613 * sleep until the specified event occurs.
614 */
9bccf70c 615wait_result_t
1c79356b
A
616assert_wait(
617 event_t event,
9bccf70c 618 wait_interrupt_t interruptible)
1c79356b
A
619{
620 register wait_queue_t wq;
621 register int index;
622
623 assert(event != NO_EVENT);
1c79356b
A
624
625 index = wait_hash(event);
626 wq = &wait_queues[index];
91447636 627 return wait_queue_assert_wait(wq, event, interruptible, 0);
9bccf70c
A
628}
629
91447636
A
630wait_result_t
631assert_wait_timeout(
632 event_t event,
633 wait_interrupt_t interruptible,
634 uint32_t interval,
635 uint32_t scale_factor)
55e303ae 636{
91447636
A
637 thread_t thread = current_thread();
638 wait_result_t wresult;
639 wait_queue_t wqueue;
640 uint64_t deadline;
641 spl_t s;
642
55e303ae 643 assert(event != NO_EVENT);
91447636
A
644 wqueue = &wait_queues[wait_hash(event)];
645
646 s = splsched();
647 wait_queue_lock(wqueue);
648 thread_lock(thread);
649
650 clock_interval_to_deadline(interval, scale_factor, &deadline);
651 wresult = wait_queue_assert_wait64_locked(wqueue, (uint32_t)event,
652 interruptible, deadline, thread);
653
654 thread_unlock(thread);
655 wait_queue_unlock(wqueue);
656 splx(s);
55e303ae 657
91447636 658 return (wresult);
55e303ae
A
659}
660
661wait_result_t
91447636 662assert_wait_deadline(
55e303ae 663 event_t event,
91447636
A
664 wait_interrupt_t interruptible,
665 uint64_t deadline)
55e303ae
A
666{
667 thread_t thread = current_thread();
91447636
A
668 wait_result_t wresult;
669 wait_queue_t wqueue;
55e303ae
A
670 spl_t s;
671
672 assert(event != NO_EVENT);
91447636 673 wqueue = &wait_queues[wait_hash(event)];
55e303ae
A
674
675 s = splsched();
91447636 676 wait_queue_lock(wqueue);
55e303ae
A
677 thread_lock(thread);
678
91447636
A
679 wresult = wait_queue_assert_wait64_locked(wqueue, (uint32_t)event,
680 interruptible, deadline, thread);
55e303ae
A
681
682 thread_unlock(thread);
91447636 683 wait_queue_unlock(wqueue);
55e303ae
A
684 splx(s);
685
686 return (wresult);
687}
9bccf70c
A
688
689/*
690 * thread_sleep_fast_usimple_lock:
691 *
692 * Cause the current thread to wait until the specified event
693 * occurs. The specified simple_lock is unlocked before releasing
694 * the cpu and re-acquired as part of waking up.
695 *
696 * This is the simple lock sleep interface for components that use a
697 * faster version of simple_lock() than is provided by usimple_lock().
698 */
699__private_extern__ wait_result_t
700thread_sleep_fast_usimple_lock(
701 event_t event,
702 simple_lock_t lock,
703 wait_interrupt_t interruptible)
704{
705 wait_result_t res;
706
707 res = assert_wait(event, interruptible);
708 if (res == THREAD_WAITING) {
709 simple_unlock(lock);
710 res = thread_block(THREAD_CONTINUE_NULL);
711 simple_lock(lock);
712 }
713 return res;
1c79356b
A
714}
715
9bccf70c
A
716
717/*
718 * thread_sleep_usimple_lock:
719 *
720 * Cause the current thread to wait until the specified event
721 * occurs. The specified usimple_lock is unlocked before releasing
722 * the cpu and re-acquired as part of waking up.
723 *
724 * This is the simple lock sleep interface for components where
725 * simple_lock() is defined in terms of usimple_lock().
726 */
727wait_result_t
728thread_sleep_usimple_lock(
729 event_t event,
730 usimple_lock_t lock,
731 wait_interrupt_t interruptible)
732{
733 wait_result_t res;
734
735 res = assert_wait(event, interruptible);
736 if (res == THREAD_WAITING) {
737 usimple_unlock(lock);
738 res = thread_block(THREAD_CONTINUE_NULL);
739 usimple_lock(lock);
740 }
741 return res;
742}
743
744/*
745 * thread_sleep_mutex:
746 *
747 * Cause the current thread to wait until the specified event
748 * occurs. The specified mutex is unlocked before releasing
749 * the cpu. The mutex will be re-acquired before returning.
750 *
751 * JMM - Add hint to make sure mutex is available before rousting
752 */
753wait_result_t
754thread_sleep_mutex(
755 event_t event,
756 mutex_t *mutex,
757 wait_interrupt_t interruptible)
758{
759 wait_result_t res;
760
761 res = assert_wait(event, interruptible);
762 if (res == THREAD_WAITING) {
763 mutex_unlock(mutex);
764 res = thread_block(THREAD_CONTINUE_NULL);
765 mutex_lock(mutex);
766 }
767 return res;
768}
1c79356b 769
9bccf70c
A
770/*
771 * thread_sleep_mutex_deadline:
772 *
773 * Cause the current thread to wait until the specified event
774 * (or deadline) occurs. The specified mutex is unlocked before
775 * releasing the cpu. The mutex will be re-acquired before returning.
9bccf70c
A
776 */
777wait_result_t
778thread_sleep_mutex_deadline(
779 event_t event,
780 mutex_t *mutex,
781 uint64_t deadline,
782 wait_interrupt_t interruptible)
783{
784 wait_result_t res;
785
91447636 786 res = assert_wait_deadline(event, interruptible, deadline);
9bccf70c
A
787 if (res == THREAD_WAITING) {
788 mutex_unlock(mutex);
9bccf70c 789 res = thread_block(THREAD_CONTINUE_NULL);
9bccf70c
A
790 mutex_lock(mutex);
791 }
792 return res;
793}
794
795/*
796 * thread_sleep_lock_write:
797 *
798 * Cause the current thread to wait until the specified event
799 * occurs. The specified (write) lock is unlocked before releasing
800 * the cpu. The (write) lock will be re-acquired before returning.
9bccf70c
A
801 */
802wait_result_t
803thread_sleep_lock_write(
804 event_t event,
805 lock_t *lock,
806 wait_interrupt_t interruptible)
807{
808 wait_result_t res;
809
810 res = assert_wait(event, interruptible);
811 if (res == THREAD_WAITING) {
812 lock_write_done(lock);
813 res = thread_block(THREAD_CONTINUE_NULL);
814 lock_write(lock);
815 }
816 return res;
817}
818
1c79356b 819/*
91447636 820 * thread_stop:
1c79356b 821 *
91447636
A
822 * Force a preemption point for a thread and wait
823 * for it to stop running. Arbitrates access among
824 * multiple stop requests. (released by unstop)
1c79356b 825 *
91447636
A
826 * The thread must enter a wait state and stop via a
827 * separate means.
1c79356b 828 *
91447636 829 * Returns FALSE if interrupted.
1c79356b
A
830 */
831boolean_t
832thread_stop(
91447636 833 thread_t thread)
1c79356b 834{
91447636
A
835 wait_result_t wresult;
836 spl_t s;
1c79356b 837
91447636 838 s = splsched();
1c79356b
A
839 wake_lock(thread);
840
841 while (thread->state & TH_SUSP) {
842 thread->wake_active = TRUE;
91447636 843 wresult = assert_wait(&thread->wake_active, THREAD_ABORTSAFE);
1c79356b
A
844 wake_unlock(thread);
845 splx(s);
846
91447636
A
847 if (wresult == THREAD_WAITING)
848 wresult = thread_block(THREAD_CONTINUE_NULL);
9bccf70c 849
91447636 850 if (wresult != THREAD_AWAKENED)
1c79356b
A
851 return (FALSE);
852
853 s = splsched();
854 wake_lock(thread);
855 }
9bccf70c 856
1c79356b
A
857 thread_lock(thread);
858 thread->state |= TH_SUSP;
1c79356b 859
9bccf70c 860 while (thread->state & TH_RUN) {
9bccf70c
A
861 processor_t processor = thread->last_processor;
862
55e303ae
A
863 if ( processor != PROCESSOR_NULL &&
864 processor->state == PROCESSOR_RUNNING &&
865 processor->active_thread == thread )
9bccf70c
A
866 cause_ast_check(processor);
867 thread_unlock(thread);
868
869 thread->wake_active = TRUE;
91447636 870 wresult = assert_wait(&thread->wake_active, THREAD_ABORTSAFE);
9bccf70c
A
871 wake_unlock(thread);
872 splx(s);
873
91447636
A
874 if (wresult == THREAD_WAITING)
875 wresult = thread_block(THREAD_CONTINUE_NULL);
9bccf70c 876
91447636 877 if (wresult != THREAD_AWAKENED) {
9bccf70c
A
878 thread_unstop(thread);
879 return (FALSE);
880 }
881
882 s = splsched();
883 wake_lock(thread);
884 thread_lock(thread);
885 }
886
887 thread_unlock(thread);
1c79356b
A
888 wake_unlock(thread);
889 splx(s);
890
891 return (TRUE);
892}
893
894/*
91447636
A
895 * thread_unstop:
896 *
897 * Release a previous stop request and set
898 * the thread running if appropriate.
899 *
900 * Use only after a successful stop operation.
1c79356b
A
901 */
902void
903thread_unstop(
9bccf70c 904 thread_t thread)
1c79356b 905{
9bccf70c 906 spl_t s = splsched();
1c79356b 907
1c79356b
A
908 wake_lock(thread);
909 thread_lock(thread);
910
9bccf70c 911 if ((thread->state & (TH_RUN|TH_WAIT|TH_SUSP)) == TH_SUSP) {
0b4e3aa0 912 thread->state &= ~TH_SUSP;
91447636 913 thread_unblock(thread, THREAD_AWAKENED);
55e303ae
A
914
915 thread_setrun(thread, SCHED_PREEMPT | SCHED_TAILQ);
1c79356b
A
916 }
917 else
918 if (thread->state & TH_SUSP) {
919 thread->state &= ~TH_SUSP;
920
921 if (thread->wake_active) {
922 thread->wake_active = FALSE;
923 thread_unlock(thread);
924 wake_unlock(thread);
925 splx(s);
1c79356b 926
9bccf70c 927 thread_wakeup(&thread->wake_active);
1c79356b
A
928 return;
929 }
930 }
931
932 thread_unlock(thread);
933 wake_unlock(thread);
934 splx(s);
935}
936
937/*
91447636
A
938 * thread_wait:
939 *
940 * Wait for a thread to stop running. (non-interruptible)
941 *
1c79356b 942 */
91447636 943void
1c79356b 944thread_wait(
91447636 945 thread_t thread)
1c79356b 946{
91447636
A
947 wait_result_t wresult;
948 spl_t s = splsched();
1c79356b 949
1c79356b 950 wake_lock(thread);
9bccf70c 951 thread_lock(thread);
1c79356b 952
9bccf70c 953 while (thread->state & TH_RUN) {
9bccf70c 954 processor_t processor = thread->last_processor;
e7c99d92 955
55e303ae
A
956 if ( processor != PROCESSOR_NULL &&
957 processor->state == PROCESSOR_RUNNING &&
958 processor->active_thread == thread )
9bccf70c
A
959 cause_ast_check(processor);
960 thread_unlock(thread);
1c79356b
A
961
962 thread->wake_active = TRUE;
91447636 963 wresult = assert_wait(&thread->wake_active, THREAD_UNINT);
1c79356b
A
964 wake_unlock(thread);
965 splx(s);
966
91447636
A
967 if (wresult == THREAD_WAITING)
968 thread_block(THREAD_CONTINUE_NULL);
1c79356b
A
969
970 s = splsched();
971 wake_lock(thread);
9bccf70c 972 thread_lock(thread);
1c79356b 973 }
0b4e3aa0 974
9bccf70c 975 thread_unlock(thread);
1c79356b
A
976 wake_unlock(thread);
977 splx(s);
1c79356b
A
978}
979
1c79356b
A
980/*
981 * Routine: clear_wait_internal
982 *
983 * Clear the wait condition for the specified thread.
984 * Start the thread executing if that is appropriate.
985 * Arguments:
986 * thread thread to awaken
987 * result Wakeup result the thread should see
988 * Conditions:
989 * At splsched
990 * the thread is locked.
9bccf70c
A
991 * Returns:
992 * KERN_SUCCESS thread was rousted out a wait
993 * KERN_FAILURE thread was waiting but could not be rousted
994 * KERN_NOT_WAITING thread was not waiting
1c79356b 995 */
9bccf70c 996__private_extern__ kern_return_t
1c79356b 997clear_wait_internal(
9bccf70c 998 thread_t thread,
55e303ae 999 wait_result_t wresult)
1c79356b 1000{
9bccf70c 1001 wait_queue_t wq = thread->wait_queue;
55e303ae 1002 int i = LockTimeOut;
9bccf70c 1003
9bccf70c 1004 do {
55e303ae
A
1005 if (wresult == THREAD_INTERRUPTED && (thread->state & TH_UNINT))
1006 return (KERN_FAILURE);
9bccf70c
A
1007
1008 if (wq != WAIT_QUEUE_NULL) {
1009 if (wait_queue_lock_try(wq)) {
1010 wait_queue_pull_thread_locked(wq, thread, TRUE);
1011 /* wait queue unlocked, thread still locked */
55e303ae
A
1012 }
1013 else {
9bccf70c
A
1014 thread_unlock(thread);
1015 delay(1);
55e303ae 1016
9bccf70c 1017 thread_lock(thread);
55e303ae
A
1018 if (wq != thread->wait_queue)
1019 return (KERN_NOT_WAITING);
9bccf70c 1020
9bccf70c
A
1021 continue;
1022 }
1c79356b 1023 }
55e303ae 1024
91447636 1025 return (thread_go(thread, wresult));
55e303ae
A
1026 } while (--i > 0);
1027
9bccf70c
A
1028 panic("clear_wait_internal: deadlock: thread=0x%x, wq=0x%x, cpu=%d\n",
1029 thread, wq, cpu_number());
55e303ae
A
1030
1031 return (KERN_FAILURE);
1c79356b
A
1032}
1033
1034
1035/*
1036 * clear_wait:
1037 *
1038 * Clear the wait condition for the specified thread. Start the thread
1039 * executing if that is appropriate.
1040 *
1041 * parameters:
1042 * thread thread to awaken
1043 * result Wakeup result the thread should see
1044 */
9bccf70c 1045kern_return_t
1c79356b 1046clear_wait(
9bccf70c
A
1047 thread_t thread,
1048 wait_result_t result)
1c79356b 1049{
9bccf70c 1050 kern_return_t ret;
1c79356b
A
1051 spl_t s;
1052
1053 s = splsched();
1054 thread_lock(thread);
9bccf70c 1055 ret = clear_wait_internal(thread, result);
1c79356b
A
1056 thread_unlock(thread);
1057 splx(s);
9bccf70c 1058 return ret;
1c79356b
A
1059}
1060
1061
1062/*
1063 * thread_wakeup_prim:
1064 *
1065 * Common routine for thread_wakeup, thread_wakeup_with_result,
1066 * and thread_wakeup_one.
1067 *
1068 */
9bccf70c 1069kern_return_t
1c79356b
A
1070thread_wakeup_prim(
1071 event_t event,
1072 boolean_t one_thread,
9bccf70c 1073 wait_result_t result)
1c79356b
A
1074{
1075 register wait_queue_t wq;
1076 register int index;
1077
1078 index = wait_hash(event);
1079 wq = &wait_queues[index];
1080 if (one_thread)
9bccf70c 1081 return (wait_queue_wakeup_one(wq, event, result));
1c79356b 1082 else
9bccf70c 1083 return (wait_queue_wakeup_all(wq, event, result));
1c79356b
A
1084}
1085
1086/*
1087 * thread_bind:
1088 *
1089 * Force a thread to execute on the specified processor.
1c79356b 1090 *
55e303ae
A
1091 * Returns the previous binding. PROCESSOR_NULL means
1092 * not bound.
1093 *
1094 * XXX - DO NOT export this to users - XXX
1c79356b 1095 */
55e303ae 1096processor_t
1c79356b
A
1097thread_bind(
1098 register thread_t thread,
1099 processor_t processor)
1100{
55e303ae
A
1101 processor_t prev;
1102 run_queue_t runq = RUN_QUEUE_NULL;
1103 spl_t s;
1c79356b
A
1104
1105 s = splsched();
1106 thread_lock(thread);
55e303ae
A
1107 prev = thread->bound_processor;
1108 if (prev != PROCESSOR_NULL)
1109 runq = run_queue_remove(thread);
1110
1111 thread->bound_processor = processor;
1112
1113 if (runq != RUN_QUEUE_NULL)
1114 thread_setrun(thread, SCHED_PREEMPT | SCHED_TAILQ);
1c79356b
A
1115 thread_unlock(thread);
1116 splx(s);
55e303ae
A
1117
1118 return (prev);
1c79356b
A
1119}
1120
55e303ae
A
1121struct {
1122 uint32_t idle_pset_last,
1123 idle_pset_any,
1124 idle_bound;
1125
1126 uint32_t pset_self,
1127 pset_last,
1128 pset_other,
1129 bound_self,
1130 bound_other;
1131
1132 uint32_t realtime_self,
1133 realtime_last,
1134 realtime_other;
1135
1136 uint32_t missed_realtime,
1137 missed_other;
1138} dispatch_counts;
1139
1c79356b 1140/*
55e303ae
A
1141 * Select a thread for the current processor to run.
1142 *
1143 * May select the current thread, which must be locked.
1c79356b
A
1144 */
1145thread_t
1146thread_select(
55e303ae 1147 register processor_t processor)
1c79356b
A
1148{
1149 register thread_t thread;
1150 processor_set_t pset;
1c79356b 1151 boolean_t other_runnable;
1c79356b
A
1152
1153 /*
1154 * Check for other non-idle runnable threads.
1155 */
55e303ae
A
1156 pset = processor->processor_set;
1157 thread = processor->active_thread;
0b4e3aa0
A
1158
1159 /* Update the thread's priority */
1160 if (thread->sched_stamp != sched_tick)
1161 update_priority(thread);
1c79356b 1162
55e303ae 1163 processor->current_pri = thread->sched_pri;
9bccf70c 1164
55e303ae 1165 simple_lock(&pset->sched_lock);
1c79356b 1166
55e303ae 1167 other_runnable = processor->runq.count > 0 || pset->runq.count > 0;
1c79356b
A
1168
1169 if ( thread->state == TH_RUN &&
1c79356b
A
1170 thread->processor_set == pset &&
1171 (thread->bound_processor == PROCESSOR_NULL ||
55e303ae
A
1172 thread->bound_processor == processor) ) {
1173 if ( thread->sched_pri >= BASEPRI_RTQUEUES &&
1174 first_timeslice(processor) ) {
1175 if (pset->runq.highq >= BASEPRI_RTQUEUES) {
1176 register run_queue_t runq = &pset->runq;
1177 register queue_t q;
1178
1179 q = runq->queues + runq->highq;
1180 if (((thread_t)q->next)->realtime.deadline <
1181 processor->deadline) {
1182 thread = (thread_t)q->next;
1183 ((queue_entry_t)thread)->next->prev = q;
1184 q->next = ((queue_entry_t)thread)->next;
1185 thread->runq = RUN_QUEUE_NULL;
1186 assert(thread->sched_mode & TH_MODE_PREEMPT);
1187 runq->count--; runq->urgency--;
1188 if (queue_empty(q)) {
1189 if (runq->highq != IDLEPRI)
1190 clrbit(MAXPRI - runq->highq, runq->bitmap);
1191 runq->highq = MAXPRI - ffsbit(runq->bitmap);
1192 }
1193 }
1194 }
1195
1196 processor->deadline = thread->realtime.deadline;
1197
1198 simple_unlock(&pset->sched_lock);
1199
1200 return (thread);
1201 }
1c79356b 1202
55e303ae
A
1203 if ( (!other_runnable ||
1204 (processor->runq.highq < thread->sched_pri &&
1205 pset->runq.highq < thread->sched_pri)) ) {
1c79356b 1206
55e303ae
A
1207 /* I am the highest priority runnable (non-idle) thread */
1208
1209 processor->deadline = UINT64_MAX;
1210
1211 simple_unlock(&pset->sched_lock);
1212
1213 return (thread);
1214 }
1c79356b 1215 }
55e303ae 1216
9bccf70c 1217 if (other_runnable)
55e303ae 1218 thread = choose_thread(pset, processor);
1c79356b 1219 else {
1c79356b
A
1220 /*
1221 * Nothing is runnable, so set this processor idle if it
55e303ae 1222 * was running. Return its idle thread.
1c79356b 1223 */
55e303ae
A
1224 if (processor->state == PROCESSOR_RUNNING) {
1225 remqueue(&pset->active_queue, (queue_entry_t)processor);
1226 processor->state = PROCESSOR_IDLE;
1c79356b 1227
55e303ae 1228 enqueue_tail(&pset->idle_queue, (queue_entry_t)processor);
1c79356b
A
1229 pset->idle_count++;
1230 }
1c79356b 1231
55e303ae
A
1232 processor->deadline = UINT64_MAX;
1233
1234 thread = processor->idle_thread;
1c79356b
A
1235 }
1236
55e303ae
A
1237 simple_unlock(&pset->sched_lock);
1238
1c79356b
A
1239 return (thread);
1240}
1241
1c79356b 1242/*
55e303ae
A
1243 * Perform a context switch and start executing the new thread.
1244 *
91447636 1245 * Returns FALSE on failure, and the thread is re-dispatched.
9bccf70c 1246 *
55e303ae 1247 * Called at splsched.
1c79356b
A
1248 */
1249
55e303ae
A
1250#define funnel_release_check(thread, debug) \
1251MACRO_BEGIN \
1252 if ((thread)->funnel_state & TH_FN_OWNED) { \
1253 (thread)->funnel_state = TH_FN_REFUNNEL; \
1254 KERNEL_DEBUG(0x603242c | DBG_FUNC_NONE, \
1255 (thread)->funnel_lock, (debug), 0, 0, 0); \
1256 funnel_unlock((thread)->funnel_lock); \
1257 } \
1258MACRO_END
1259
1260#define funnel_refunnel_check(thread, debug) \
1261MACRO_BEGIN \
1262 if ((thread)->funnel_state & TH_FN_REFUNNEL) { \
1263 kern_return_t result = (thread)->wait_result; \
1264 \
1265 (thread)->funnel_state = 0; \
1266 KERNEL_DEBUG(0x6032428 | DBG_FUNC_NONE, \
1267 (thread)->funnel_lock, (debug), 0, 0, 0); \
1268 funnel_lock((thread)->funnel_lock); \
1269 KERNEL_DEBUG(0x6032430 | DBG_FUNC_NONE, \
1270 (thread)->funnel_lock, (debug), 0, 0, 0); \
1271 (thread)->funnel_state = TH_FN_OWNED; \
1272 (thread)->wait_result = result; \
1273 } \
1274MACRO_END
1275
1c79356b
A
1276boolean_t
1277thread_invoke(
1278 register thread_t old_thread,
1279 register thread_t new_thread,
91447636 1280 ast_t reason)
1c79356b 1281{
91447636
A
1282 thread_continue_t new_cont, continuation = old_thread->continuation;
1283 void *new_param, *parameter = old_thread->parameter;
9bccf70c 1284 processor_t processor;
91447636 1285 thread_t prev_thread;
1c79356b 1286
9bccf70c 1287 if (get_preemption_level() != 0)
0b4e3aa0 1288 panic("thread_invoke: preemption_level %d\n",
9bccf70c 1289 get_preemption_level());
0b4e3aa0 1290
91447636
A
1291 assert(old_thread == current_thread());
1292
1c79356b 1293 /*
9bccf70c 1294 * Mark thread interruptible.
1c79356b
A
1295 */
1296 thread_lock(new_thread);
1297 new_thread->state &= ~TH_UNINT;
1298
1c79356b
A
1299 assert(thread_runnable(new_thread));
1300
9bccf70c
A
1301 /*
1302 * Allow time constraint threads to hang onto
1303 * a stack.
1304 */
0b4e3aa0 1305 if ( (old_thread->sched_mode & TH_MODE_REALTIME) &&
55e303ae
A
1306 !old_thread->reserved_stack ) {
1307 old_thread->reserved_stack = old_thread->kernel_stack;
1c79356b
A
1308 }
1309
91447636
A
1310 if (continuation != NULL) {
1311 if (!new_thread->kernel_stack) {
9bccf70c
A
1312 /*
1313 * If the old thread is using a privileged stack,
1314 * check to see whether we can exchange it with
1315 * that of the new thread.
1316 */
55e303ae
A
1317 if ( old_thread->kernel_stack == old_thread->reserved_stack &&
1318 !new_thread->reserved_stack)
9bccf70c 1319 goto need_stack;
1c79356b 1320
91447636
A
1321 /*
1322 * Context switch by performing a stack handoff.
1323 */
9bccf70c
A
1324 new_cont = new_thread->continuation;
1325 new_thread->continuation = NULL;
91447636
A
1326 new_param = new_thread->parameter;
1327 new_thread->parameter = NULL;
1c79356b 1328
9bccf70c 1329 processor = current_processor();
55e303ae 1330 processor->active_thread = new_thread;
9bccf70c 1331 processor->current_pri = new_thread->sched_pri;
55e303ae 1332 new_thread->last_processor = processor;
91447636 1333 ast_context(new_thread);
9bccf70c 1334 thread_unlock(new_thread);
0b4e3aa0 1335
9bccf70c 1336 current_task()->csw++;
1c79356b 1337
9bccf70c 1338 old_thread->reason = reason;
91447636
A
1339
1340 processor->last_dispatch = mach_absolute_time();
1341 timer_event((uint32_t)processor->last_dispatch,
1342 &new_thread->system_timer);
0b4e3aa0 1343
91447636 1344 thread_done(old_thread, new_thread, processor);
1c79356b 1345
55e303ae 1346 machine_stack_handoff(old_thread, new_thread);
9bccf70c 1347
91447636 1348 thread_begin(new_thread, processor);
1c79356b 1349
91447636
A
1350 /*
1351 * Now dispatch the old thread.
9bccf70c 1352 */
91447636 1353 thread_dispatch(old_thread);
1c79356b 1354
9bccf70c 1355 counter_always(c_thread_invoke_hits++);
1c79356b 1356
55e303ae 1357 funnel_refunnel_check(new_thread, 2);
9bccf70c 1358 (void) spllo();
1c79356b 1359
9bccf70c 1360 assert(new_cont);
91447636 1361 call_continuation(new_cont, new_param, new_thread->wait_result);
9bccf70c 1362 /*NOTREACHED*/
9bccf70c
A
1363 }
1364 else
1365 if (new_thread == old_thread) {
1366 /* same thread but with continuation */
1367 counter(++c_thread_invoke_same);
1368 thread_unlock(new_thread);
1369
55e303ae 1370 funnel_refunnel_check(new_thread, 3);
9bccf70c 1371 (void) spllo();
55e303ae 1372
91447636 1373 call_continuation(continuation, parameter, new_thread->wait_result);
9bccf70c
A
1374 /*NOTREACHED*/
1375 }
1c79356b 1376 }
9bccf70c
A
1377 else {
1378 /*
1379 * Check that the new thread has a stack
1380 */
91447636 1381 if (!new_thread->kernel_stack) {
9bccf70c 1382need_stack:
91447636 1383 if (!stack_alloc_try(new_thread)) {
9bccf70c 1384 counter_always(c_thread_invoke_misses++);
91447636
A
1385 thread_unlock(new_thread);
1386 thread_stack_enqueue(new_thread);
9bccf70c
A
1387 return (FALSE);
1388 }
9bccf70c
A
1389 }
1390 else
91447636 1391 if (new_thread == old_thread) {
9bccf70c
A
1392 counter(++c_thread_invoke_same);
1393 thread_unlock(new_thread);
1394 return (TRUE);
1395 }
1396 }
1c79356b
A
1397
1398 /*
91447636 1399 * Context switch by full context save.
1c79356b 1400 */
9bccf70c 1401 processor = current_processor();
55e303ae 1402 processor->active_thread = new_thread;
9bccf70c 1403 processor->current_pri = new_thread->sched_pri;
55e303ae 1404 new_thread->last_processor = processor;
91447636 1405 ast_context(new_thread);
1c79356b 1406 assert(thread_runnable(new_thread));
1c79356b
A
1407 thread_unlock(new_thread);
1408
1409 counter_always(c_thread_invoke_csw++);
1410 current_task()->csw++;
1411
1c79356b 1412 assert(old_thread->runq == RUN_QUEUE_NULL);
9bccf70c 1413 old_thread->reason = reason;
1c79356b 1414
91447636
A
1415 processor->last_dispatch = mach_absolute_time();
1416 timer_event((uint32_t)processor->last_dispatch, &new_thread->system_timer);
1417
1418 thread_done(old_thread, new_thread, processor);
1c79356b
A
1419
1420 /*
91447636
A
1421 * This is where we actually switch register context,
1422 * and address space if required. Control will not
1423 * return here immediately.
1c79356b 1424 */
91447636 1425 prev_thread = machine_switch_context(old_thread, continuation, new_thread);
1c79356b 1426
91447636
A
1427 /*
1428 * We are still old_thread, possibly on a different processor,
1429 * and new_thread is now stale.
1430 */
1431 thread_begin(old_thread, old_thread->last_processor);
1c79356b
A
1432
1433 /*
91447636 1434 * Now dispatch the thread which resumed us.
1c79356b 1435 */
91447636 1436 thread_dispatch(prev_thread);
9bccf70c 1437
91447636
A
1438 if (continuation) {
1439 funnel_refunnel_check(old_thread, 3);
9bccf70c 1440 (void) spllo();
55e303ae 1441
91447636 1442 call_continuation(continuation, parameter, old_thread->wait_result);
9bccf70c 1443 /*NOTREACHED*/
1c79356b
A
1444 }
1445
9bccf70c 1446 return (TRUE);
1c79356b
A
1447}
1448
1449/*
91447636 1450 * thread_done:
1c79356b 1451 *
91447636
A
1452 * Perform calculations for thread
1453 * finishing execution on the current processor.
1454 *
1455 * Called at splsched.
1c79356b
A
1456 */
1457void
91447636
A
1458thread_done(
1459 thread_t old_thread,
1460 thread_t new_thread,
1461 processor_t processor)
1c79356b 1462{
91447636
A
1463 if (!(old_thread->state & TH_IDLE)) {
1464 /*
1465 * Compute remainder of current quantum.
1466 */
1467 if ( first_timeslice(processor) &&
1468 processor->quantum_end > processor->last_dispatch )
1469 old_thread->current_quantum =
1470 (processor->quantum_end - processor->last_dispatch);
1471 else
1472 old_thread->current_quantum = 0;
9bccf70c 1473
91447636
A
1474 if (old_thread->sched_mode & TH_MODE_REALTIME) {
1475 /*
1476 * Cancel the deadline if the thread has
1477 * consumed the entire quantum.
1478 */
1479 if (old_thread->current_quantum == 0) {
1480 old_thread->realtime.deadline = UINT64_MAX;
1481 old_thread->reason |= AST_QUANTUM;
1482 }
1483 }
1484 else {
1485 /*
1486 * For non-realtime threads treat a tiny
1487 * remaining quantum as an expired quantum
1488 * but include what's left next time.
1489 */
1490 if (old_thread->current_quantum < min_std_quantum) {
1491 old_thread->reason |= AST_QUANTUM;
1492 old_thread->current_quantum += std_quantum;
1493 }
1494 }
1495
1496 /*
1497 * If we are doing a direct handoff then
1498 * give the remainder of our quantum to
1499 * the next thread.
1500 */
1501 if ((old_thread->reason & (AST_HANDOFF|AST_QUANTUM)) == AST_HANDOFF) {
1502 new_thread->current_quantum = old_thread->current_quantum;
1503 old_thread->reason |= AST_QUANTUM;
1504 old_thread->current_quantum = 0;
1505 }
1506
1507 old_thread->last_switch = processor->last_dispatch;
1508
1509 old_thread->computation_metered +=
1510 (old_thread->last_switch - old_thread->computation_epoch);
1511 }
1512}
1513
1514/*
1515 * thread_begin:
1516 *
1517 * Set up for thread beginning execution on
1518 * the current processor.
1519 *
1520 * Called at splsched.
1521 */
1522void
1523thread_begin(
1524 thread_t thread,
1525 processor_t processor)
1526{
1527 if (!(thread->state & TH_IDLE)) {
1528 /*
1529 * Give the thread a new quantum
1530 * if none remaining.
1531 */
1532 if (thread->current_quantum == 0)
1533 thread_quantum_init(thread);
1534
1535 /*
1536 * Set up quantum timer and timeslice.
1537 */
1538 processor->quantum_end =
1539 (processor->last_dispatch + thread->current_quantum);
1540 timer_call_enter1(&processor->quantum_timer,
1541 thread, processor->quantum_end);
1542
1543 processor_timeslice_setup(processor, thread);
1544
1545 thread->last_switch = processor->last_dispatch;
1546
1547 thread->computation_epoch = thread->last_switch;
1548 }
1549 else {
1550 timer_call_cancel(&processor->quantum_timer);
1551 processor->timeslice = 1;
1552 }
1553}
1554
1555/*
1556 * thread_dispatch:
1557 *
1558 * Handle previous thread at context switch. Re-dispatch
1559 * if still running, otherwise update run state and perform
1560 * special actions.
1561 *
1562 * Called at splsched.
1563 */
1564void
1565thread_dispatch(
1566 register thread_t thread)
1567{
1c79356b 1568 /*
91447636
A
1569 * If blocked at a continuation, discard
1570 * the stack.
1c79356b 1571 */
6601e61a 1572#ifndef i386
91447636
A
1573 if (thread->continuation != NULL && thread->kernel_stack)
1574 stack_free(thread);
6601e61a 1575#endif
1c79356b 1576
91447636
A
1577 if (!(thread->state & TH_IDLE)) {
1578 wake_lock(thread);
1579 thread_lock(thread);
55e303ae 1580
91447636
A
1581 if (!(thread->state & TH_WAIT)) {
1582 /*
1583 * Still running.
1584 */
1585 if (thread->reason & AST_QUANTUM)
1586 thread_setrun(thread, SCHED_TAILQ);
1587 else
1588 if (thread->reason & AST_PREEMPT)
1589 thread_setrun(thread, SCHED_HEADQ);
1590 else
1591 thread_setrun(thread, SCHED_PREEMPT | SCHED_TAILQ);
1592
1593 thread->reason = AST_NONE;
1594
1595 thread_unlock(thread);
1596 wake_unlock(thread);
1597 }
1598 else {
1599 boolean_t wake;
1600
1601 /*
1602 * Waiting.
1603 */
1604 thread->state &= ~TH_RUN;
1605
1606 wake = thread->wake_active;
1607 thread->wake_active = FALSE;
1608
1609 if (thread->sched_mode & TH_MODE_TIMESHARE)
1610 pset_share_decr(thread->processor_set);
1611 pset_run_decr(thread->processor_set);
1612
1613 thread_unlock(thread);
1614 wake_unlock(thread);
1615
1616 if (thread->options & TH_OPT_CALLOUT)
1617 call_thread_block();
1618
1619 if (wake)
1620 thread_wakeup((event_t)&thread->wake_active);
1621
1622 if (thread->state & TH_TERMINATE)
1623 thread_terminate_enqueue(thread);
1624 }
1625 }
1c79356b
A
1626}
1627
1c79356b
A
1628/*
1629 * thread_block_reason:
1630 *
55e303ae
A
1631 * Forces a reschedule, blocking the caller if a wait
1632 * has been asserted.
1633 *
1634 * If a continuation is specified, then thread_invoke will
1c79356b
A
1635 * attempt to discard the thread's kernel stack. When the
1636 * thread resumes, it will execute the continuation function
1637 * on a new kernel stack.
1638 */
1639counter(mach_counter_t c_thread_block_calls = 0;)
1640
91447636 1641wait_result_t
1c79356b 1642thread_block_reason(
9bccf70c 1643 thread_continue_t continuation,
91447636 1644 void *parameter,
9bccf70c 1645 ast_t reason)
1c79356b 1646{
91447636 1647 register thread_t self = current_thread();
55e303ae 1648 register processor_t processor;
1c79356b
A
1649 register thread_t new_thread;
1650 spl_t s;
1651
1652 counter(++c_thread_block_calls);
1653
1c79356b
A
1654 s = splsched();
1655
55e303ae 1656 if (!(reason & AST_PREEMPT))
91447636 1657 funnel_release_check(self, 2);
1c79356b 1658
55e303ae 1659 processor = current_processor();
1c79356b 1660
91447636
A
1661 /*
1662 * Delay switching to the idle thread under certain conditions.
1663 */
1664 if (s != FALSE && (self->state & (TH_IDLE|TH_TERMINATE|TH_WAIT)) == TH_WAIT) {
1665 if ( processor->processor_set->processor_count > 1 &&
1666 processor->processor_set->runq.count == 0 &&
1667 processor->runq.count == 0 )
1668 processor = delay_idle(processor, self);
1669 }
1670
9bccf70c
A
1671 /* If we're explicitly yielding, force a subsequent quantum */
1672 if (reason & AST_YIELD)
55e303ae 1673 processor->timeslice = 0;
0b4e3aa0 1674
9bccf70c
A
1675 /* We're handling all scheduling AST's */
1676 ast_off(AST_SCHEDULING);
1c79356b 1677
91447636
A
1678 self->continuation = continuation;
1679 self->parameter = parameter;
1680
1681 thread_lock(self);
55e303ae 1682 new_thread = thread_select(processor);
9bccf70c 1683 assert(new_thread && thread_runnable(new_thread));
91447636
A
1684 thread_unlock(self);
1685 while (!thread_invoke(self, new_thread, reason)) {
1686 thread_lock(self);
55e303ae 1687 new_thread = thread_select(processor);
9bccf70c 1688 assert(new_thread && thread_runnable(new_thread));
91447636 1689 thread_unlock(self);
1c79356b
A
1690 }
1691
91447636 1692 funnel_refunnel_check(self, 5);
1c79356b
A
1693 splx(s);
1694
91447636 1695 return (self->wait_result);
1c79356b
A
1696}
1697
1698/*
1699 * thread_block:
1700 *
9bccf70c 1701 * Block the current thread if a wait has been asserted.
1c79356b 1702 */
91447636 1703wait_result_t
1c79356b 1704thread_block(
9bccf70c 1705 thread_continue_t continuation)
1c79356b 1706{
91447636
A
1707 return thread_block_reason(continuation, NULL, AST_NONE);
1708}
1709
1710wait_result_t
1711thread_block_parameter(
1712 thread_continue_t continuation,
1713 void *parameter)
1714{
1715 return thread_block_reason(continuation, parameter, AST_NONE);
1c79356b
A
1716}
1717
1718/*
1719 * thread_run:
1720 *
91447636 1721 * Switch directly from the current thread to the
55e303ae 1722 * new thread, handing off our quantum if appropriate.
9bccf70c
A
1723 *
1724 * New thread must be runnable, and not on a run queue.
1c79356b 1725 *
55e303ae 1726 * Called at splsched.
1c79356b
A
1727 */
1728int
1729thread_run(
91447636 1730 thread_t self,
9bccf70c 1731 thread_continue_t continuation,
91447636 1732 void *parameter,
9bccf70c 1733 thread_t new_thread)
1c79356b 1734{
9bccf70c
A
1735 ast_t handoff = AST_HANDOFF;
1736
91447636 1737 funnel_release_check(self, 3);
9bccf70c 1738
91447636
A
1739 self->continuation = continuation;
1740 self->parameter = parameter;
9bccf70c 1741
91447636 1742 while (!thread_invoke(self, new_thread, handoff)) {
55e303ae 1743 register processor_t processor = current_processor();
9bccf70c 1744
91447636 1745 thread_lock(self);
55e303ae 1746 new_thread = thread_select(processor);
91447636 1747 thread_unlock(self);
9bccf70c
A
1748 handoff = AST_NONE;
1749 }
1750
91447636 1751 funnel_refunnel_check(self, 6);
9bccf70c 1752
91447636 1753 return (self->wait_result);
1c79356b
A
1754}
1755
1756/*
91447636 1757 * thread_continue:
55e303ae 1758 *
91447636
A
1759 * Called at splsched when a thread first receives
1760 * a new stack after a continuation.
1c79356b
A
1761 */
1762void
91447636
A
1763thread_continue(
1764 register thread_t old_thread)
1c79356b 1765{
91447636
A
1766 register thread_t self = current_thread();
1767 register thread_continue_t continuation;
1768 register void *parameter;
1c79356b 1769
91447636
A
1770 continuation = self->continuation;
1771 self->continuation = NULL;
1772 parameter = self->parameter;
1773 self->parameter = NULL;
9bccf70c 1774
91447636 1775 thread_begin(self, self->last_processor);
9bccf70c 1776
91447636
A
1777 if (old_thread != THREAD_NULL)
1778 thread_dispatch(old_thread);
1c79356b 1779
91447636 1780 funnel_refunnel_check(self, 4);
1c79356b 1781
91447636
A
1782 if (old_thread != THREAD_NULL)
1783 (void)spllo();
9bccf70c 1784
91447636
A
1785 call_continuation(continuation, parameter, self->wait_result);
1786 /*NOTREACHED*/
1c79356b
A
1787}
1788
1789/*
55e303ae
A
1790 * Enqueue thread on run queue. Thread must be locked,
1791 * and not already be on a run queue. Returns TRUE
1792 * if a preemption is indicated based on the state
1793 * of the run queue.
1794 *
1795 * Run queue must be locked, see run_queue_remove()
1796 * for more info.
1c79356b 1797 */
55e303ae 1798static boolean_t
1c79356b
A
1799run_queue_enqueue(
1800 register run_queue_t rq,
1801 register thread_t thread,
55e303ae 1802 integer_t options)
1c79356b 1803{
9bccf70c
A
1804 register int whichq = thread->sched_pri;
1805 register queue_t queue = &rq->queues[whichq];
1806 boolean_t result = FALSE;
1c79356b 1807
1c79356b
A
1808 assert(whichq >= MINPRI && whichq <= MAXPRI);
1809
1c79356b 1810 assert(thread->runq == RUN_QUEUE_NULL);
9bccf70c
A
1811 if (queue_empty(queue)) {
1812 enqueue_tail(queue, (queue_entry_t)thread);
1813
1814 setbit(MAXPRI - whichq, rq->bitmap);
55e303ae 1815 if (whichq > rq->highq) {
9bccf70c 1816 rq->highq = whichq;
55e303ae
A
1817 result = TRUE;
1818 }
9bccf70c
A
1819 }
1820 else
55e303ae 1821 if (options & SCHED_HEADQ)
9bccf70c 1822 enqueue_head(queue, (queue_entry_t)thread);
55e303ae
A
1823 else
1824 enqueue_tail(queue, (queue_entry_t)thread);
1c79356b 1825
1c79356b 1826 thread->runq = rq;
9bccf70c
A
1827 if (thread->sched_mode & TH_MODE_PREEMPT)
1828 rq->urgency++;
1829 rq->count++;
1c79356b 1830
9bccf70c 1831 return (result);
1c79356b
A
1832}
1833
1834/*
55e303ae
A
1835 * Enqueue a thread for realtime execution, similar
1836 * to above. Handles preemption directly.
1c79356b 1837 */
55e303ae
A
1838static void
1839realtime_schedule_insert(
1840 register processor_set_t pset,
1841 register thread_t thread)
1c79356b 1842{
55e303ae
A
1843 register run_queue_t rq = &pset->runq;
1844 register int whichq = thread->sched_pri;
1845 register queue_t queue = &rq->queues[whichq];
1846 uint64_t deadline = thread->realtime.deadline;
1847 boolean_t try_preempt = FALSE;
1c79356b 1848
55e303ae 1849 assert(whichq >= BASEPRI_REALTIME && whichq <= MAXPRI);
1c79356b 1850
55e303ae
A
1851 assert(thread->runq == RUN_QUEUE_NULL);
1852 if (queue_empty(queue)) {
1853 enqueue_tail(queue, (queue_entry_t)thread);
1854
1855 setbit(MAXPRI - whichq, rq->bitmap);
1856 if (whichq > rq->highq)
1857 rq->highq = whichq;
1858 try_preempt = TRUE;
1859 }
1860 else {
1861 register thread_t entry = (thread_t)queue_first(queue);
1862
1863 while (TRUE) {
1864 if ( queue_end(queue, (queue_entry_t)entry) ||
1865 deadline < entry->realtime.deadline ) {
1866 entry = (thread_t)queue_prev((queue_entry_t)entry);
1867 break;
1868 }
1869
1870 entry = (thread_t)queue_next((queue_entry_t)entry);
1871 }
1872
1873 if ((queue_entry_t)entry == queue)
1874 try_preempt = TRUE;
1875
1876 insque((queue_entry_t)thread, (queue_entry_t)entry);
1877 }
1878
1879 thread->runq = rq;
1880 assert(thread->sched_mode & TH_MODE_PREEMPT);
1881 rq->count++; rq->urgency++;
1882
1883 if (try_preempt) {
1884 register processor_t processor;
1885
1886 processor = current_processor();
1887 if ( pset == processor->processor_set &&
1888 (thread->sched_pri > processor->current_pri ||
1889 deadline < processor->deadline ) ) {
1890 dispatch_counts.realtime_self++;
1891 simple_unlock(&pset->sched_lock);
1892
1893 ast_on(AST_PREEMPT | AST_URGENT);
1894 return;
1895 }
1896
1897 if ( pset->processor_count > 1 ||
1898 pset != processor->processor_set ) {
1899 processor_t myprocessor, lastprocessor;
1900 queue_entry_t next;
1901
1902 myprocessor = processor;
1903 processor = thread->last_processor;
1904 if ( processor != myprocessor &&
1905 processor != PROCESSOR_NULL &&
1906 processor->processor_set == pset &&
1907 processor->state == PROCESSOR_RUNNING &&
1908 (thread->sched_pri > processor->current_pri ||
1909 deadline < processor->deadline ) ) {
1910 dispatch_counts.realtime_last++;
1911 cause_ast_check(processor);
1912 simple_unlock(&pset->sched_lock);
1913 return;
1914 }
1915
1916 lastprocessor = processor;
1917 queue = &pset->active_queue;
1918 processor = (processor_t)queue_first(queue);
1919 while (!queue_end(queue, (queue_entry_t)processor)) {
1920 next = queue_next((queue_entry_t)processor);
1921
1922 if ( processor != myprocessor &&
1923 processor != lastprocessor &&
1924 (thread->sched_pri > processor->current_pri ||
1925 deadline < processor->deadline ) ) {
1926 if (!queue_end(queue, next)) {
1927 remqueue(queue, (queue_entry_t)processor);
1928 enqueue_tail(queue, (queue_entry_t)processor);
1929 }
1930 dispatch_counts.realtime_other++;
1931 cause_ast_check(processor);
1932 simple_unlock(&pset->sched_lock);
1933 return;
1934 }
1935
1936 processor = (processor_t)next;
1937 }
1938 }
1939 }
1940
1941 simple_unlock(&pset->sched_lock);
1942}
1943
1944/*
1945 * thread_setrun:
1946 *
1947 * Dispatch thread for execution, directly onto an idle
1948 * processor if possible. Else put on appropriate run
1949 * queue. (local if bound, else processor set)
1950 *
1951 * Thread must be locked.
1952 */
1953void
1954thread_setrun(
1955 register thread_t new_thread,
1956 integer_t options)
1957{
1958 register processor_t processor;
1959 register processor_set_t pset;
1960 register thread_t thread;
1961 ast_t preempt = (options & SCHED_PREEMPT)?
1962 AST_PREEMPT: AST_NONE;
1963
1964 assert(thread_runnable(new_thread));
1965
1966 /*
1967 * Update priority if needed.
1968 */
1969 if (new_thread->sched_stamp != sched_tick)
1970 update_priority(new_thread);
1971
1972 /*
9bccf70c 1973 * Check for urgent preemption.
1c79356b 1974 */
9bccf70c 1975 if (new_thread->sched_mode & TH_MODE_PREEMPT)
55e303ae 1976 preempt = (AST_PREEMPT | AST_URGENT);
9bccf70c
A
1977
1978 assert(new_thread->runq == RUN_QUEUE_NULL);
1979
1c79356b
A
1980 if ((processor = new_thread->bound_processor) == PROCESSOR_NULL) {
1981 /*
9bccf70c
A
1982 * First try to dispatch on
1983 * the last processor.
1c79356b
A
1984 */
1985 pset = new_thread->processor_set;
9bccf70c
A
1986 processor = new_thread->last_processor;
1987 if ( pset->processor_count > 1 &&
1988 processor != PROCESSOR_NULL &&
1989 processor->state == PROCESSOR_IDLE ) {
55e303ae 1990 processor_lock(processor);
9bccf70c
A
1991 simple_lock(&pset->sched_lock);
1992 if ( processor->processor_set == pset &&
1993 processor->state == PROCESSOR_IDLE ) {
1994 remqueue(&pset->idle_queue, (queue_entry_t)processor);
1c79356b
A
1995 pset->idle_count--;
1996 processor->next_thread = new_thread;
55e303ae
A
1997 if (new_thread->sched_pri >= BASEPRI_RTQUEUES)
1998 processor->deadline = new_thread->realtime.deadline;
1999 else
2000 processor->deadline = UINT64_MAX;
1c79356b 2001 processor->state = PROCESSOR_DISPATCHING;
55e303ae 2002 dispatch_counts.idle_pset_last++;
9bccf70c 2003 simple_unlock(&pset->sched_lock);
55e303ae 2004 processor_unlock(processor);
9bccf70c 2005 if (processor != current_processor())
1c79356b 2006 machine_signal_idle(processor);
1c79356b
A
2007 return;
2008 }
55e303ae 2009 processor_unlock(processor);
9bccf70c
A
2010 }
2011 else
2012 simple_lock(&pset->sched_lock);
2013
2014 /*
2015 * Next pick any idle processor
2016 * in the processor set.
2017 */
2018 if (pset->idle_count > 0) {
2019 processor = (processor_t)dequeue_head(&pset->idle_queue);
2020 pset->idle_count--;
2021 processor->next_thread = new_thread;
55e303ae
A
2022 if (new_thread->sched_pri >= BASEPRI_RTQUEUES)
2023 processor->deadline = new_thread->realtime.deadline;
2024 else
2025 processor->deadline = UINT64_MAX;
9bccf70c 2026 processor->state = PROCESSOR_DISPATCHING;
55e303ae 2027 dispatch_counts.idle_pset_any++;
9bccf70c
A
2028 simple_unlock(&pset->sched_lock);
2029 if (processor != current_processor())
2030 machine_signal_idle(processor);
9bccf70c
A
2031 return;
2032 }
1c79356b 2033
55e303ae
A
2034 if (new_thread->sched_pri >= BASEPRI_RTQUEUES)
2035 realtime_schedule_insert(pset, new_thread);
2036 else {
2037 if (!run_queue_enqueue(&pset->runq, new_thread, options))
2038 preempt = AST_NONE;
9bccf70c 2039
9bccf70c 2040 /*
55e303ae 2041 * Update the timesharing quanta.
1c79356b 2042 */
55e303ae
A
2043 timeshare_quanta_update(pset);
2044
9bccf70c 2045 /*
55e303ae 2046 * Preempt check.
9bccf70c 2047 */
55e303ae 2048 if (preempt != AST_NONE) {
9bccf70c 2049 /*
55e303ae
A
2050 * First try the current processor
2051 * if it is a member of the correct
2052 * processor set.
9bccf70c 2053 */
55e303ae
A
2054 processor = current_processor();
2055 thread = processor->active_thread;
2056 if ( pset == processor->processor_set &&
2057 csw_needed(thread, processor) ) {
2058 dispatch_counts.pset_self++;
9bccf70c 2059 simple_unlock(&pset->sched_lock);
55e303ae
A
2060
2061 ast_on(preempt);
9bccf70c
A
2062 return;
2063 }
2064
2065 /*
55e303ae
A
2066 * If that failed and we have other
2067 * processors available keep trying.
9bccf70c 2068 */
55e303ae
A
2069 if ( pset->processor_count > 1 ||
2070 pset != processor->processor_set ) {
2071 queue_t queue = &pset->active_queue;
2072 processor_t myprocessor, lastprocessor;
2073 queue_entry_t next;
2074
2075 /*
2076 * Next try the last processor
2077 * dispatched on.
2078 */
2079 myprocessor = processor;
2080 processor = new_thread->last_processor;
9bccf70c 2081 if ( processor != myprocessor &&
55e303ae
A
2082 processor != PROCESSOR_NULL &&
2083 processor->processor_set == pset &&
2084 processor->state == PROCESSOR_RUNNING &&
9bccf70c 2085 new_thread->sched_pri > processor->current_pri ) {
55e303ae 2086 dispatch_counts.pset_last++;
9bccf70c
A
2087 cause_ast_check(processor);
2088 simple_unlock(&pset->sched_lock);
9bccf70c
A
2089 return;
2090 }
2091
55e303ae
A
2092 /*
2093 * Lastly, pick any other
2094 * available processor.
2095 */
2096 lastprocessor = processor;
2097 processor = (processor_t)queue_first(queue);
2098 while (!queue_end(queue, (queue_entry_t)processor)) {
2099 next = queue_next((queue_entry_t)processor);
2100
2101 if ( processor != myprocessor &&
2102 processor != lastprocessor &&
2103 new_thread->sched_pri >
2104 processor->current_pri ) {
2105 if (!queue_end(queue, next)) {
2106 remqueue(queue, (queue_entry_t)processor);
2107 enqueue_tail(queue, (queue_entry_t)processor);
2108 }
2109 dispatch_counts.pset_other++;
2110 cause_ast_check(processor);
2111 simple_unlock(&pset->sched_lock);
2112 return;
2113 }
2114
2115 processor = (processor_t)next;
2116 }
9bccf70c
A
2117 }
2118 }
9bccf70c 2119
55e303ae
A
2120 simple_unlock(&pset->sched_lock);
2121 }
1c79356b
A
2122 }
2123 else {
2124 /*
2125 * Bound, can only run on bound processor. Have to lock
2126 * processor here because it may not be the current one.
2127 */
55e303ae
A
2128 processor_lock(processor);
2129 pset = processor->processor_set;
2130 if (pset != PROCESSOR_SET_NULL) {
9bccf70c 2131 simple_lock(&pset->sched_lock);
1c79356b 2132 if (processor->state == PROCESSOR_IDLE) {
9bccf70c 2133 remqueue(&pset->idle_queue, (queue_entry_t)processor);
1c79356b
A
2134 pset->idle_count--;
2135 processor->next_thread = new_thread;
55e303ae 2136 processor->deadline = UINT64_MAX;
1c79356b 2137 processor->state = PROCESSOR_DISPATCHING;
55e303ae 2138 dispatch_counts.idle_bound++;
9bccf70c 2139 simple_unlock(&pset->sched_lock);
55e303ae 2140 processor_unlock(processor);
9bccf70c 2141 if (processor != current_processor())
1c79356b 2142 machine_signal_idle(processor);
1c79356b
A
2143 return;
2144 }
1c79356b
A
2145 }
2146
55e303ae
A
2147 if (!run_queue_enqueue(&processor->runq, new_thread, options))
2148 preempt = AST_NONE;
9bccf70c 2149
55e303ae
A
2150 if (preempt != AST_NONE) {
2151 if (processor == current_processor()) {
2152 thread = processor->active_thread;
9bccf70c 2153 if (csw_needed(thread, processor)) {
9bccf70c 2154 dispatch_counts.bound_self++;
55e303ae 2155 ast_on(preempt);
9bccf70c
A
2156 }
2157 }
55e303ae
A
2158 else
2159 if ( processor->state == PROCESSOR_RUNNING &&
2160 new_thread->sched_pri > processor->current_pri ) {
2161 dispatch_counts.bound_other++;
2162 cause_ast_check(processor);
9bccf70c
A
2163 }
2164 }
55e303ae
A
2165
2166 if (pset != PROCESSOR_SET_NULL)
2167 simple_unlock(&pset->sched_lock);
2168
2169 processor_unlock(processor);
9bccf70c
A
2170 }
2171}
2172
2173/*
55e303ae
A
2174 * Check for a possible preemption point in
2175 * the (current) thread.
2176 *
2177 * Called at splsched.
9bccf70c
A
2178 */
2179ast_t
2180csw_check(
2181 thread_t thread,
2182 processor_t processor)
2183{
2184 int current_pri = thread->sched_pri;
2185 ast_t result = AST_NONE;
2186 run_queue_t runq;
2187
55e303ae 2188 if (first_timeslice(processor)) {
9bccf70c 2189 runq = &processor->processor_set->runq;
55e303ae
A
2190 if (runq->highq >= BASEPRI_RTQUEUES)
2191 return (AST_PREEMPT | AST_URGENT);
2192
9bccf70c
A
2193 if (runq->highq > current_pri) {
2194 if (runq->urgency > 0)
55e303ae 2195 return (AST_PREEMPT | AST_URGENT);
9bccf70c 2196
55e303ae 2197 result |= AST_PREEMPT;
9bccf70c
A
2198 }
2199
2200 runq = &processor->runq;
2201 if (runq->highq > current_pri) {
2202 if (runq->urgency > 0)
55e303ae 2203 return (AST_PREEMPT | AST_URGENT);
9bccf70c 2204
55e303ae 2205 result |= AST_PREEMPT;
9bccf70c
A
2206 }
2207 }
2208 else {
2209 runq = &processor->processor_set->runq;
2210 if (runq->highq >= current_pri) {
2211 if (runq->urgency > 0)
55e303ae 2212 return (AST_PREEMPT | AST_URGENT);
9bccf70c 2213
55e303ae 2214 result |= AST_PREEMPT;
9bccf70c
A
2215 }
2216
2217 runq = &processor->runq;
2218 if (runq->highq >= current_pri) {
2219 if (runq->urgency > 0)
55e303ae 2220 return (AST_PREEMPT | AST_URGENT);
9bccf70c 2221
55e303ae 2222 result |= AST_PREEMPT;
9bccf70c 2223 }
1c79356b 2224 }
9bccf70c
A
2225
2226 if (result != AST_NONE)
2227 return (result);
2228
2229 if (thread->state & TH_SUSP)
55e303ae 2230 result |= AST_PREEMPT;
9bccf70c
A
2231
2232 return (result);
1c79356b
A
2233}
2234
2235/*
9bccf70c 2236 * set_sched_pri:
1c79356b 2237 *
55e303ae
A
2238 * Set the scheduled priority of the specified thread.
2239 *
9bccf70c 2240 * This may cause the thread to change queues.
1c79356b 2241 *
55e303ae 2242 * Thread must be locked.
1c79356b
A
2243 */
2244void
9bccf70c 2245set_sched_pri(
1c79356b 2246 thread_t thread,
9bccf70c 2247 int priority)
1c79356b 2248{
55e303ae 2249 register struct run_queue *rq = run_queue_remove(thread);
9bccf70c
A
2250
2251 if ( !(thread->sched_mode & TH_MODE_TIMESHARE) &&
2252 (priority >= BASEPRI_PREEMPT ||
2253 (thread->task_priority < MINPRI_KERNEL &&
2254 thread->task_priority >= BASEPRI_BACKGROUND &&
91447636 2255 priority > thread->task_priority) ) )
9bccf70c
A
2256 thread->sched_mode |= TH_MODE_PREEMPT;
2257 else
2258 thread->sched_mode &= ~TH_MODE_PREEMPT;
1c79356b 2259
9bccf70c
A
2260 thread->sched_pri = priority;
2261 if (rq != RUN_QUEUE_NULL)
55e303ae 2262 thread_setrun(thread, SCHED_PREEMPT | SCHED_TAILQ);
9bccf70c 2263 else
55e303ae 2264 if (thread->state & TH_RUN) {
9bccf70c
A
2265 processor_t processor = thread->last_processor;
2266
2267 if (thread == current_thread()) {
2268 ast_t preempt = csw_check(thread, processor);
2269
2270 if (preempt != AST_NONE)
2271 ast_on(preempt);
2272 processor->current_pri = priority;
2273 }
2274 else
2275 if ( processor != PROCESSOR_NULL &&
55e303ae 2276 processor->active_thread == thread )
9bccf70c 2277 cause_ast_check(processor);
1c79356b
A
2278 }
2279}
2280
91447636
A
2281#if 0
2282
2283static void
2284run_queue_check(
2285 run_queue_t rq,
2286 thread_t thread)
2287{
2288 queue_t q;
2289 queue_entry_t qe;
2290
2291 if (rq != thread->runq)
2292 panic("run_queue_check: thread runq");
2293
2294 if (thread->sched_pri > MAXPRI || thread->sched_pri < MINPRI)
2295 panic("run_queue_check: thread sched_pri");
2296
2297 q = &rq->queues[thread->sched_pri];
2298 qe = queue_first(q);
2299 while (!queue_end(q, qe)) {
2300 if (qe == (queue_entry_t)thread)
2301 return;
2302
2303 qe = queue_next(qe);
2304 }
2305
2306 panic("run_queue_check: end");
2307}
2308
2309#endif /* DEBUG */
2310
1c79356b 2311/*
55e303ae 2312 * run_queue_remove:
1c79356b 2313 *
55e303ae
A
2314 * Remove a thread from its current run queue and
2315 * return the run queue if successful.
2316 *
2317 * Thread must be locked.
1c79356b
A
2318 */
2319run_queue_t
55e303ae 2320run_queue_remove(
1c79356b
A
2321 thread_t thread)
2322{
55e303ae 2323 register run_queue_t rq = thread->runq;
1c79356b 2324
1c79356b
A
2325 /*
2326 * If rq is RUN_QUEUE_NULL, the thread will stay out of the
55e303ae
A
2327 * run queues because the caller locked the thread. Otherwise
2328 * the thread is on a run queue, but could be chosen for dispatch
2329 * and removed.
1c79356b
A
2330 */
2331 if (rq != RUN_QUEUE_NULL) {
55e303ae
A
2332 processor_set_t pset = thread->processor_set;
2333 processor_t processor = thread->bound_processor;
2334
2335 /*
2336 * The run queues are locked by the pset scheduling
2337 * lock, except when a processor is off-line the
2338 * local run queue is locked by the processor lock.
2339 */
2340 if (processor != PROCESSOR_NULL) {
2341 processor_lock(processor);
2342 pset = processor->processor_set;
2343 }
2344
2345 if (pset != PROCESSOR_SET_NULL)
2346 simple_lock(&pset->sched_lock);
2347
1c79356b
A
2348 if (rq == thread->runq) {
2349 /*
55e303ae
A
2350 * Thread is on a run queue and we have a lock on
2351 * that run queue.
1c79356b 2352 */
1c79356b
A
2353 remqueue(&rq->queues[0], (queue_entry_t)thread);
2354 rq->count--;
9bccf70c
A
2355 if (thread->sched_mode & TH_MODE_PREEMPT)
2356 rq->urgency--;
2357 assert(rq->urgency >= 0);
1c79356b
A
2358
2359 if (queue_empty(rq->queues + thread->sched_pri)) {
2360 /* update run queue status */
2361 if (thread->sched_pri != IDLEPRI)
2362 clrbit(MAXPRI - thread->sched_pri, rq->bitmap);
2363 rq->highq = MAXPRI - ffsbit(rq->bitmap);
2364 }
55e303ae 2365
1c79356b 2366 thread->runq = RUN_QUEUE_NULL;
1c79356b
A
2367 }
2368 else {
2369 /*
55e303ae
A
2370 * The thread left the run queue before we could
2371 * lock the run queue.
1c79356b
A
2372 */
2373 assert(thread->runq == RUN_QUEUE_NULL);
1c79356b
A
2374 rq = RUN_QUEUE_NULL;
2375 }
55e303ae
A
2376
2377 if (pset != PROCESSOR_SET_NULL)
2378 simple_unlock(&pset->sched_lock);
2379
2380 if (processor != PROCESSOR_NULL)
2381 processor_unlock(processor);
1c79356b
A
2382 }
2383
2384 return (rq);
2385}
2386
1c79356b
A
2387/*
2388 * choose_thread:
2389 *
55e303ae
A
2390 * Remove a thread to execute from the run queues
2391 * and return it.
1c79356b 2392 *
55e303ae 2393 * Called with pset scheduling lock held.
1c79356b 2394 */
55e303ae 2395static thread_t
1c79356b 2396choose_thread(
55e303ae
A
2397 processor_set_t pset,
2398 processor_t processor)
1c79356b 2399{
1c79356b 2400 register run_queue_t runq;
55e303ae
A
2401 register thread_t thread;
2402 register queue_t q;
1c79356b 2403
55e303ae 2404 runq = &processor->runq;
1c79356b 2405
1c79356b
A
2406 if (runq->count > 0 && runq->highq >= pset->runq.highq) {
2407 q = runq->queues + runq->highq;
55e303ae
A
2408
2409 thread = (thread_t)q->next;
2410 ((queue_entry_t)thread)->next->prev = q;
2411 q->next = ((queue_entry_t)thread)->next;
2412 thread->runq = RUN_QUEUE_NULL;
2413 runq->count--;
2414 if (thread->sched_mode & TH_MODE_PREEMPT)
2415 runq->urgency--;
2416 assert(runq->urgency >= 0);
2417 if (queue_empty(q)) {
2418 if (runq->highq != IDLEPRI)
2419 clrbit(MAXPRI - runq->highq, runq->bitmap);
2420 runq->highq = MAXPRI - ffsbit(runq->bitmap);
1c79356b 2421 }
1c79356b 2422
55e303ae 2423 processor->deadline = UINT64_MAX;
1c79356b 2424
55e303ae 2425 return (thread);
1c79356b 2426 }
1c79356b 2427
55e303ae 2428 runq = &pset->runq;
9bccf70c 2429
55e303ae
A
2430 assert(runq->count > 0);
2431 q = runq->queues + runq->highq;
1c79356b 2432
55e303ae
A
2433 thread = (thread_t)q->next;
2434 ((queue_entry_t)thread)->next->prev = q;
2435 q->next = ((queue_entry_t)thread)->next;
2436 thread->runq = RUN_QUEUE_NULL;
2437 runq->count--;
2438 if (runq->highq >= BASEPRI_RTQUEUES)
2439 processor->deadline = thread->realtime.deadline;
2440 else
2441 processor->deadline = UINT64_MAX;
2442 if (thread->sched_mode & TH_MODE_PREEMPT)
2443 runq->urgency--;
2444 assert(runq->urgency >= 0);
2445 if (queue_empty(q)) {
2446 if (runq->highq != IDLEPRI)
2447 clrbit(MAXPRI - runq->highq, runq->bitmap);
2448 runq->highq = MAXPRI - ffsbit(runq->bitmap);
1c79356b 2449 }
1c79356b 2450
55e303ae
A
2451 timeshare_quanta_update(pset);
2452
2453 return (thread);
1c79356b
A
2454}
2455
91447636
A
2456static processor_t
2457delay_idle(
2458 processor_t processor,
2459 thread_t self)
2460{
2461 int *gcount, *lcount;
2462 uint64_t abstime, spin, limit;
2463
2464 lcount = &processor->runq.count;
2465 gcount = &processor->processor_set->runq.count;
2466
2467 abstime = mach_absolute_time();
2468 limit = abstime + delay_idle_limit;
2469 spin = abstime + delay_idle_spin;
2470
2471 timer_event((uint32_t)abstime, &processor->idle_thread->system_timer);
2472
2473 self->options |= TH_OPT_DELAYIDLE;
2474
2475 while ( *gcount == 0 && *lcount == 0 &&
2476 (self->state & TH_WAIT) != 0 &&
2477 abstime < limit ) {
2478 if (abstime >= spin) {
2479 (void)spllo();
2480
2481 (void)splsched();
2482 processor = current_processor();
2483 lcount = &processor->runq.count;
2484 gcount = &processor->processor_set->runq.count;
2485
2486 abstime = mach_absolute_time();
2487 spin = abstime + delay_idle_spin;
2488
2489 timer_event((uint32_t)abstime, &processor->idle_thread->system_timer);
2490 }
6601e61a 2491 else
91447636
A
2492 abstime = mach_absolute_time();
2493 }
2494
2495 timer_event((uint32_t)abstime, &self->system_timer);
2496
2497 self->options &= ~TH_OPT_DELAYIDLE;
2498
2499 return (processor);
2500}
2501
1c79356b
A
2502/*
2503 * no_dispatch_count counts number of times processors go non-idle
2504 * without being dispatched. This should be very rare.
2505 */
2506int no_dispatch_count = 0;
2507
2508/*
91447636 2509 * This is the idle processor thread, which just looks for other threads
1c79356b
A
2510 * to execute.
2511 */
2512void
91447636 2513idle_thread(void)
1c79356b 2514{
55e303ae 2515 register processor_t processor;
91447636
A
2516 register thread_t *threadp;
2517 register int *gcount;
2518 register int *lcount;
1c79356b
A
2519 register thread_t new_thread;
2520 register int state;
2521 register processor_set_t pset;
91447636 2522 ast_t *myast = ast_pending();
1c79356b 2523
91447636 2524 processor = current_processor();
1c79356b 2525
91447636
A
2526 threadp = &processor->next_thread;
2527 lcount = &processor->runq.count;
2528 gcount = &processor->processor_set->runq.count;
1c79356b 2529
3a60a9f5
A
2530
2531 (void)splsched(); /* Turn interruptions off */
2532
6601e61a 2533#ifdef __ppc__
3a60a9f5 2534 pmsDown(); /* Step power down. Note: interruptions must be disabled for this call */
6601e61a 2535#endif
3a60a9f5 2536
91447636
A
2537 while ( (*threadp == THREAD_NULL) &&
2538 (*gcount == 0) && (*lcount == 0) ) {
de355530 2539
55e303ae 2540 /* check for ASTs while we wait */
91447636 2541 if (*myast &~ (AST_SCHEDULING | AST_BSD)) {
55e303ae 2542 /* no ASTs for us */
91447636 2543 *myast &= AST_NONE;
55e303ae 2544 (void)spllo();
1c79356b 2545 }
55e303ae
A
2546 else
2547 machine_idle();
2548
2549 (void)splsched();
2550 }
2551
2552 /*
2553 * This is not a switch statement to avoid the
2554 * bounds checking code in the common case.
2555 */
2556 pset = processor->processor_set;
2557 simple_lock(&pset->sched_lock);
1c79356b 2558
6601e61a 2559#ifdef __ppc__
3a60a9f5 2560 pmsStep(0); /* Step up out of idle power, may start timer for next step */
6601e61a 2561#endif
3a60a9f5 2562
55e303ae
A
2563 state = processor->state;
2564 if (state == PROCESSOR_DISPATCHING) {
1c79356b 2565 /*
55e303ae 2566 * Commmon case -- cpu dispatched.
1c79356b 2567 */
55e303ae
A
2568 new_thread = *threadp;
2569 *threadp = (volatile thread_t) THREAD_NULL;
2570 processor->state = PROCESSOR_RUNNING;
2571 enqueue_tail(&pset->active_queue, (queue_entry_t)processor);
2572
2573 if ( pset->runq.highq >= BASEPRI_RTQUEUES &&
2574 new_thread->sched_pri >= BASEPRI_RTQUEUES ) {
2575 register run_queue_t runq = &pset->runq;
2576 register queue_t q;
2577
2578 q = runq->queues + runq->highq;
2579 if (((thread_t)q->next)->realtime.deadline <
2580 processor->deadline) {
2581 thread_t thread = new_thread;
2582
2583 new_thread = (thread_t)q->next;
2584 ((queue_entry_t)new_thread)->next->prev = q;
2585 q->next = ((queue_entry_t)new_thread)->next;
2586 new_thread->runq = RUN_QUEUE_NULL;
2587 processor->deadline = new_thread->realtime.deadline;
2588 assert(new_thread->sched_mode & TH_MODE_PREEMPT);
2589 runq->count--; runq->urgency--;
2590 if (queue_empty(q)) {
2591 if (runq->highq != IDLEPRI)
2592 clrbit(MAXPRI - runq->highq, runq->bitmap);
2593 runq->highq = MAXPRI - ffsbit(runq->bitmap);
2594 }
2595 dispatch_counts.missed_realtime++;
2596 simple_unlock(&pset->sched_lock);
1c79356b 2597
55e303ae
A
2598 thread_lock(thread);
2599 thread_setrun(thread, SCHED_HEADQ);
2600 thread_unlock(thread);
1c79356b 2601
1c79356b 2602 counter(c_idle_thread_handoff++);
91447636 2603 thread_run(processor->idle_thread, (thread_continue_t)idle_thread, NULL, new_thread);
55e303ae 2604 /*NOTREACHED*/
1c79356b 2605 }
9bccf70c 2606 simple_unlock(&pset->sched_lock);
1c79356b 2607
55e303ae 2608 counter(c_idle_thread_handoff++);
91447636 2609 thread_run(processor->idle_thread, (thread_continue_t)idle_thread, NULL, new_thread);
55e303ae 2610 /*NOTREACHED*/
1c79356b 2611 }
9bccf70c 2612
55e303ae
A
2613 if ( processor->runq.highq > new_thread->sched_pri ||
2614 pset->runq.highq > new_thread->sched_pri ) {
2615 thread_t thread = new_thread;
2616
2617 new_thread = choose_thread(pset, processor);
2618 dispatch_counts.missed_other++;
2619 simple_unlock(&pset->sched_lock);
1c79356b 2620
55e303ae
A
2621 thread_lock(thread);
2622 thread_setrun(thread, SCHED_HEADQ);
2623 thread_unlock(thread);
2624
2625 counter(c_idle_thread_handoff++);
91447636 2626 thread_run(processor->idle_thread, (thread_continue_t)idle_thread, NULL, new_thread);
9bccf70c 2627 /* NOTREACHED */
1c79356b
A
2628 }
2629 else {
9bccf70c 2630 simple_unlock(&pset->sched_lock);
1c79356b 2631
55e303ae 2632 counter(c_idle_thread_handoff++);
91447636 2633 thread_run(processor->idle_thread, (thread_continue_t)idle_thread, NULL, new_thread);
55e303ae 2634 /* NOTREACHED */
1c79356b 2635 }
55e303ae
A
2636 }
2637 else
2638 if (state == PROCESSOR_IDLE) {
2639 /*
2640 * Processor was not dispatched (Rare).
2641 * Set it running again and force a
2642 * reschedule.
2643 */
2644 no_dispatch_count++;
2645 pset->idle_count--;
2646 remqueue(&pset->idle_queue, (queue_entry_t)processor);
2647 processor->state = PROCESSOR_RUNNING;
2648 enqueue_tail(&pset->active_queue, (queue_entry_t)processor);
2649 simple_unlock(&pset->sched_lock);
1c79356b 2650
55e303ae 2651 counter(c_idle_thread_block++);
91447636 2652 thread_block((thread_continue_t)idle_thread);
55e303ae 2653 /* NOTREACHED */
1c79356b 2654 }
55e303ae
A
2655 else
2656 if (state == PROCESSOR_SHUTDOWN) {
2657 /*
2658 * Going off-line. Force a
2659 * reschedule.
2660 */
2661 if ((new_thread = (thread_t)*threadp) != THREAD_NULL) {
2662 *threadp = (volatile thread_t) THREAD_NULL;
2663 processor->deadline = UINT64_MAX;
2664 simple_unlock(&pset->sched_lock);
2665
2666 thread_lock(new_thread);
2667 thread_setrun(new_thread, SCHED_HEADQ);
2668 thread_unlock(new_thread);
2669 }
2670 else
2671 simple_unlock(&pset->sched_lock);
2672
2673 counter(c_idle_thread_block++);
91447636 2674 thread_block((thread_continue_t)idle_thread);
55e303ae
A
2675 /* NOTREACHED */
2676 }
2677
2678 simple_unlock(&pset->sched_lock);
2679
91447636 2680 panic("idle_thread: state %d\n", processor->state);
55e303ae 2681 /*NOTREACHED*/
1c79356b
A
2682}
2683
91447636
A
2684kern_return_t
2685idle_thread_create(
2686 processor_t processor)
1c79356b 2687{
91447636
A
2688 kern_return_t result;
2689 thread_t thread;
2690 spl_t s;
2691
2692 result = kernel_thread_create((thread_continue_t)idle_thread, NULL, MAXPRI_KERNEL, &thread);
2693 if (result != KERN_SUCCESS)
2694 return (result);
2695
2696 s = splsched();
2697 thread_lock(thread);
2698 thread->bound_processor = processor;
2699 processor->idle_thread = thread;
2700 thread->sched_pri = thread->priority = IDLEPRI;
2701 thread->state = (TH_RUN | TH_IDLE);
2702 thread_unlock(thread);
2703 splx(s);
2704
2705 thread_deallocate(thread);
2706
2707 return (KERN_SUCCESS);
1c79356b
A
2708}
2709
55e303ae 2710static uint64_t sched_tick_deadline;
0b4e3aa0 2711
91447636
A
2712/*
2713 * sched_startup:
2714 *
2715 * Kicks off scheduler services.
2716 *
2717 * Called at splsched.
2718 */
0b4e3aa0 2719void
91447636 2720sched_startup(void)
0b4e3aa0 2721{
91447636
A
2722 kern_return_t result;
2723 thread_t thread;
2724
2725 result = kernel_thread_start_priority((thread_continue_t)sched_tick_thread, NULL, MAXPRI_KERNEL, &thread);
2726 if (result != KERN_SUCCESS)
2727 panic("sched_startup");
2728
2729 thread_deallocate(thread);
2730
2731 /*
2732 * Yield to the sched_tick_thread while it times
2733 * a series of context switches back. It stores
2734 * the baseline value in sched_cswtime.
2735 *
2736 * The current thread is the only other thread
2737 * active at this point.
2738 */
2739 while (sched_cswtime == 0)
2740 thread_block(THREAD_CONTINUE_NULL);
2741
2742 thread_daemon_init();
2743
2744 thread_call_initialize();
0b4e3aa0 2745}
1c79356b
A
2746
2747/*
91447636 2748 * sched_tick_thread:
1c79356b 2749 *
55e303ae
A
2750 * Perform periodic bookkeeping functions about ten
2751 * times per second.
1c79356b 2752 */
91447636
A
2753static void
2754sched_tick_continue(void)
1c79356b 2755{
91447636 2756 uint64_t abstime = mach_absolute_time();
1c79356b 2757
91447636 2758 sched_tick++;
1c79356b
A
2759
2760 /*
91447636 2761 * Compute various averages.
1c79356b 2762 */
91447636 2763 compute_averages();
1c79356b
A
2764
2765 /*
91447636
A
2766 * Scan the run queues for threads which
2767 * may need to be updated.
1c79356b 2768 */
91447636 2769 thread_update_scan();
1c79356b
A
2770
2771 clock_deadline_for_periodic_event(sched_tick_interval, abstime,
2772 &sched_tick_deadline);
2773
91447636
A
2774 assert_wait_deadline((event_t)sched_tick_thread, THREAD_UNINT, sched_tick_deadline);
2775 thread_block((thread_continue_t)sched_tick_continue);
1c79356b
A
2776 /*NOTREACHED*/
2777}
2778
91447636
A
2779/*
2780 * Time a series of context switches to determine
2781 * a baseline. Toss the high and low and return
2782 * the one-way value.
2783 */
2784static uint32_t
2785time_cswitch(void)
2786{
2787 uint32_t new, hi, low, accum;
2788 uint64_t abstime;
2789 int i, tries = 7;
2790
2791 accum = hi = low = 0;
2792 for (i = 0; i < tries; ++i) {
2793 abstime = mach_absolute_time();
2794 thread_block(THREAD_CONTINUE_NULL);
2795
2796 new = mach_absolute_time() - abstime;
2797
2798 if (i == 0)
2799 accum = hi = low = new;
2800 else {
2801 if (new < low)
2802 low = new;
2803 else
2804 if (new > hi)
2805 hi = new;
2806 accum += new;
2807 }
2808 }
2809
2810 return ((accum - hi - low) / (2 * (tries - 2)));
2811}
2812
1c79356b
A
2813void
2814sched_tick_thread(void)
2815{
91447636
A
2816 sched_cswtime = time_cswitch();
2817
55e303ae 2818 sched_tick_deadline = mach_absolute_time();
1c79356b 2819
91447636 2820 sched_tick_continue();
1c79356b
A
2821 /*NOTREACHED*/
2822}
2823
1c79356b 2824/*
91447636 2825 * thread_update_scan / runq_scan:
55e303ae 2826 *
91447636
A
2827 * Scan the run queues to account for timesharing threads
2828 * which need to be updated.
1c79356b
A
2829 *
2830 * Scanner runs in two passes. Pass one squirrels likely
91447636 2831 * threads away in an array, pass two does the update.
1c79356b 2832 *
91447636
A
2833 * This is necessary because the run queue is locked for
2834 * the candidate scan, but the thread is locked for the update.
1c79356b 2835 *
91447636
A
2836 * Array should be sized to make forward progress, without
2837 * disabling preemption for long periods.
1c79356b 2838 */
55e303ae 2839
91447636 2840#define THREAD_UPDATE_SIZE 128
55e303ae 2841
91447636
A
2842static thread_t thread_update_array[THREAD_UPDATE_SIZE];
2843static int thread_update_count = 0;
1c79356b
A
2844
2845/*
91447636
A
2846 * Scan a runq for candidate threads.
2847 *
2848 * Returns TRUE if retry is needed.
1c79356b 2849 */
55e303ae 2850static boolean_t
91447636 2851runq_scan(
1c79356b
A
2852 run_queue_t runq)
2853{
91447636 2854 register int count;
1c79356b
A
2855 register queue_t q;
2856 register thread_t thread;
1c79356b 2857
1c79356b
A
2858 if ((count = runq->count) > 0) {
2859 q = runq->queues + runq->highq;
2860 while (count > 0) {
2861 queue_iterate(q, thread, thread_t, links) {
55e303ae 2862 if ( thread->sched_stamp != sched_tick &&
0b4e3aa0 2863 (thread->sched_mode & TH_MODE_TIMESHARE) ) {
91447636 2864 if (thread_update_count == THREAD_UPDATE_SIZE)
55e303ae 2865 return (TRUE);
1c79356b 2866
91447636
A
2867 thread_update_array[thread_update_count++] = thread;
2868 thread_reference_internal(thread);
1c79356b
A
2869 }
2870
2871 count--;
2872 }
2873
2874 q--;
2875 }
2876 }
1c79356b 2877
91447636 2878 return (FALSE);
1c79356b
A
2879}
2880
55e303ae 2881static void
91447636 2882thread_update_scan(void)
1c79356b 2883{
91447636 2884 register boolean_t restart_needed;
1c79356b
A
2885 register processor_set_t pset = &default_pset;
2886 register processor_t processor;
91447636 2887 register thread_t thread;
1c79356b
A
2888 spl_t s;
2889
1c79356b 2890 do {
55e303ae
A
2891 s = splsched();
2892 simple_lock(&pset->sched_lock);
91447636 2893 restart_needed = runq_scan(&pset->runq);
55e303ae
A
2894 simple_unlock(&pset->sched_lock);
2895
1c79356b 2896 if (!restart_needed) {
55e303ae 2897 simple_lock(&pset->sched_lock);
1c79356b
A
2898 processor = (processor_t)queue_first(&pset->processors);
2899 while (!queue_end(&pset->processors, (queue_entry_t)processor)) {
91447636 2900 if ((restart_needed = runq_scan(&processor->runq)) != 0)
1c79356b
A
2901 break;
2902
0b4e3aa0
A
2903 thread = processor->idle_thread;
2904 if (thread->sched_stamp != sched_tick) {
91447636 2905 if (thread_update_count == THREAD_UPDATE_SIZE) {
0b4e3aa0
A
2906 restart_needed = TRUE;
2907 break;
2908 }
2909
91447636
A
2910 thread_update_array[thread_update_count++] = thread;
2911 thread_reference_internal(thread);
0b4e3aa0
A
2912 }
2913
1c79356b
A
2914 processor = (processor_t)queue_next(&processor->processors);
2915 }
55e303ae 2916 simple_unlock(&pset->sched_lock);
1c79356b 2917 }
55e303ae 2918 splx(s);
1c79356b
A
2919
2920 /*
2921 * Ok, we now have a collection of candidates -- fix them.
2922 */
91447636
A
2923 while (thread_update_count > 0) {
2924 thread = thread_update_array[--thread_update_count];
2925 thread_update_array[thread_update_count] = THREAD_NULL;
55e303ae 2926
1c79356b
A
2927 s = splsched();
2928 thread_lock(thread);
55e303ae
A
2929 if ( !(thread->state & (TH_WAIT|TH_SUSP)) &&
2930 thread->sched_stamp != sched_tick )
2931 update_priority(thread);
1c79356b
A
2932 thread_unlock(thread);
2933 splx(s);
55e303ae 2934
91447636 2935 thread_deallocate(thread);
1c79356b 2936 }
1c79356b
A
2937 } while (restart_needed);
2938}
2939
2940/*
2941 * Just in case someone doesn't use the macro
2942 */
2943#undef thread_wakeup
2944void
2945thread_wakeup(
2946 event_t x);
2947
2948void
2949thread_wakeup(
2950 event_t x)
2951{
2952 thread_wakeup_with_result(x, THREAD_AWAKENED);
2953}
2954
91447636
A
2955boolean_t
2956preemption_enabled(void)
2957{
2958 return (get_preemption_level() == 0 && ml_get_interrupts_enabled());
2959}
9bccf70c 2960
0b4e3aa0 2961#if DEBUG
0b4e3aa0 2962static boolean_t
1c79356b 2963thread_runnable(
0b4e3aa0 2964 thread_t thread)
1c79356b 2965{
0b4e3aa0 2966 return ((thread->state & (TH_RUN|TH_WAIT)) == TH_RUN);
1c79356b 2967}
1c79356b
A
2968#endif /* DEBUG */
2969
2970#if MACH_KDB
2971#include <ddb/db_output.h>
2972#define printf kdbprintf
1c79356b
A
2973void db_sched(void);
2974
2975void
2976db_sched(void)
2977{
2978 iprintf("Scheduling Statistics:\n");
2979 db_indent += 2;
2980 iprintf("Thread invocations: csw %d same %d\n",
2981 c_thread_invoke_csw, c_thread_invoke_same);
2982#if MACH_COUNTERS
2983 iprintf("Thread block: calls %d\n",
2984 c_thread_block_calls);
2985 iprintf("Idle thread:\n\thandoff %d block %d no_dispatch %d\n",
2986 c_idle_thread_handoff,
2987 c_idle_thread_block, no_dispatch_count);
2988 iprintf("Sched thread blocks: %d\n", c_sched_thread_block);
2989#endif /* MACH_COUNTERS */
2990 db_indent -= 2;
2991}
55e303ae
A
2992
2993#include <ddb/db_output.h>
2994void db_show_thread_log(void);
2995
2996void
2997db_show_thread_log(void)
2998{
2999}
1c79356b 3000#endif /* MACH_KDB */