#include <debug.h>
#include <mach_kdb.h>
#include <ddb/db_output.h>
#include <mach/mach_types.h>
#include <mach/machine.h>
#include <mach/policy.h>
#include <mach/sync_policy.h>
#include <machine/machine_routines.h>
#include <machine/sched_param.h>
#include <kern/kern_types.h>
#include <kern/clock.h>
#include <kern/counters.h>
#include <kern/cpu_number.h>
#include <kern/cpu_data.h>
#include <kern/debug.h>
#include <kern/lock.h>
#include <kern/macro_help.h>
#include <kern/machine.h>
#include <kern/misc_protos.h>
#include <kern/processor.h>
#include <kern/queue.h>
#include <kern/sched.h>
#include <kern/sched_prim.h>
#include <kern/syscall_subr.h>
#include <kern/task.h>
#include <kern/thread.h>
#include <kern/wait_queue.h>
#include <vm/pmap.h>
#include <vm/vm_kern.h>
#include <vm/vm_map.h>
#include <sys/kdebug.h>
#ifdef __ppc__
#include <ppc/pms.h>
#endif
#define DEFAULT_PREEMPTION_RATE 100
int default_preemption_rate = DEFAULT_PREEMPTION_RATE;
#define MAX_UNSAFE_QUANTA 800
int max_unsafe_quanta = MAX_UNSAFE_QUANTA;
#define MAX_POLL_QUANTA 2
int max_poll_quanta = MAX_POLL_QUANTA;
#define SCHED_POLL_YIELD_SHIFT 4
int sched_poll_yield_shift = SCHED_POLL_YIELD_SHIFT;
uint64_t max_unsafe_computation;
uint32_t sched_safe_duration;
uint64_t max_poll_computation;
uint32_t std_quantum;
uint32_t min_std_quantum;
uint32_t std_quantum_us;
uint32_t max_rt_quantum;
uint32_t min_rt_quantum;
uint32_t sched_cswtime;
static uint32_t delay_idle_limit, delay_idle_spin;
static processor_t delay_idle(
processor_t processor,
thread_t self);
unsigned sched_tick;
uint32_t sched_tick_interval;
uint32_t sched_pri_shift;
void wait_queues_init(void);
static void load_shift_init(void);
static thread_t choose_thread(
processor_set_t pset,
processor_t processor);
static void thread_update_scan(void);
#if DEBUG
static
boolean_t thread_runnable(
thread_t thread);
#endif
#define NUMQUEUES 59
struct wait_queue wait_queues[NUMQUEUES];
#define wait_hash(event) \
((((int)(event) < 0)? ~(int)(event): (int)(event)) % NUMQUEUES)
int8_t sched_load_shifts[NRQS];
void
sched_init(void)
{
if (default_preemption_rate < 1)
default_preemption_rate = DEFAULT_PREEMPTION_RATE;
std_quantum_us = (1000 * 1000) / default_preemption_rate;
printf("standard timeslicing quantum is %d us\n", std_quantum_us);
sched_safe_duration = (2 * max_unsafe_quanta / default_preemption_rate) *
(1 << SCHED_TICK_SHIFT);
wait_queues_init();
load_shift_init();
pset_init(&default_pset);
sched_tick = 0;
ast_init();
}
void
sched_timebase_init(void)
{
uint64_t abstime;
uint32_t shift;
clock_interval_to_absolutetime_interval(
std_quantum_us, NSEC_PER_USEC, &abstime);
assert((abstime >> 32) == 0 && (uint32_t)abstime != 0);
std_quantum = abstime;
clock_interval_to_absolutetime_interval(250, NSEC_PER_USEC, &abstime);
assert((abstime >> 32) == 0 && (uint32_t)abstime != 0);
min_std_quantum = abstime;
clock_interval_to_absolutetime_interval(50, NSEC_PER_USEC, &abstime);
assert((abstime >> 32) == 0 && (uint32_t)abstime != 0);
min_rt_quantum = abstime;
clock_interval_to_absolutetime_interval(
50, 1000*NSEC_PER_USEC, &abstime);
assert((abstime >> 32) == 0 && (uint32_t)abstime != 0);
max_rt_quantum = abstime;
clock_interval_to_absolutetime_interval(USEC_PER_SEC >> SCHED_TICK_SHIFT,
NSEC_PER_USEC, &abstime);
assert((abstime >> 32) == 0 && (uint32_t)abstime != 0);
sched_tick_interval = abstime;
abstime = (abstime * 5) / 3;
for (shift = 0; abstime > BASEPRI_DEFAULT; ++shift)
abstime >>= 1;
sched_pri_shift = shift;
max_unsafe_computation = max_unsafe_quanta * std_quantum;
max_poll_computation = max_poll_quanta * std_quantum;
clock_interval_to_absolutetime_interval(60, NSEC_PER_USEC, &abstime);
assert((abstime >> 32) == 0 && (uint32_t)abstime != 0);
delay_idle_limit = abstime;
clock_interval_to_absolutetime_interval(1, NSEC_PER_USEC, &abstime);
assert((abstime >> 32) == 0 && (uint32_t)abstime != 0);
delay_idle_spin = abstime;
}
void
wait_queues_init(void)
{
register int i;
for (i = 0; i < NUMQUEUES; i++) {
wait_queue_init(&wait_queues[i], SYNC_POLICY_FIFO);
}
}
static void
load_shift_init(void)
{
int8_t k, *p = sched_load_shifts;
uint32_t i, j;
*p++ = INT8_MIN; *p++ = 0;
for (i = j = 2, k = 1; i < NRQS; ++k) {
for (j <<= 1; i < j; ++i)
*p++ = k;
}
}
void
thread_timer_expire(
void *p0,
__unused void *p1)
{
thread_t thread = p0;
spl_t s;
s = splsched();
thread_lock(thread);
if (--thread->wait_timer_active == 0) {
if (thread->wait_timer_is_set) {
thread->wait_timer_is_set = FALSE;
clear_wait_internal(thread, THREAD_TIMED_OUT);
}
}
thread_unlock(thread);
splx(s);
}
void
thread_set_timer(
uint32_t interval,
uint32_t scale_factor)
{
thread_t thread = current_thread();
uint64_t deadline;
spl_t s;
s = splsched();
thread_lock(thread);
if ((thread->state & TH_WAIT) != 0) {
clock_interval_to_deadline(interval, scale_factor, &deadline);
if (!timer_call_enter(&thread->wait_timer, deadline))
thread->wait_timer_active++;
thread->wait_timer_is_set = TRUE;
}
thread_unlock(thread);
splx(s);
}
void
thread_set_timer_deadline(
uint64_t deadline)
{
thread_t thread = current_thread();
spl_t s;
s = splsched();
thread_lock(thread);
if ((thread->state & TH_WAIT) != 0) {
if (!timer_call_enter(&thread->wait_timer, deadline))
thread->wait_timer_active++;
thread->wait_timer_is_set = TRUE;
}
thread_unlock(thread);
splx(s);
}
void
thread_cancel_timer(void)
{
thread_t thread = current_thread();
spl_t s;
s = splsched();
thread_lock(thread);
if (thread->wait_timer_is_set) {
if (timer_call_cancel(&thread->wait_timer))
thread->wait_timer_active--;
thread->wait_timer_is_set = FALSE;
}
thread_unlock(thread);
splx(s);
}
boolean_t
thread_unblock(
thread_t thread,
wait_result_t wresult)
{
boolean_t result = FALSE;
thread->wait_result = wresult;
if (thread->wait_timer_is_set) {
if (timer_call_cancel(&thread->wait_timer))
thread->wait_timer_active--;
thread->wait_timer_is_set = FALSE;
}
thread->state &= ~(TH_WAIT|TH_UNINT);
if (!(thread->state & TH_RUN)) {
thread->state |= TH_RUN;
if (thread->options & TH_OPT_CALLOUT)
call_thread_unblock();
pset_run_incr(thread->processor_set);
if (thread->sched_mode & TH_MODE_TIMESHARE)
pset_share_incr(thread->processor_set);
}
else
result = TRUE;
if (thread->sched_mode & TH_MODE_REALTIME) {
thread->realtime.deadline = mach_absolute_time();
thread->realtime.deadline += thread->realtime.constraint;
}
thread->current_quantum = 0;
thread->computation_metered = 0;
thread->reason = AST_NONE;
KERNEL_DEBUG_CONSTANT(
MACHDBG_CODE(DBG_MACH_SCHED,MACH_MAKE_RUNNABLE) | DBG_FUNC_NONE,
(int)thread, (int)thread->sched_pri, 0, 0, 0);
return (result);
}
kern_return_t
thread_go(
thread_t thread,
wait_result_t wresult)
{
assert(thread->at_safe_point == FALSE);
assert(thread->wait_event == NO_EVENT64);
assert(thread->wait_queue == WAIT_QUEUE_NULL);
if ((thread->state & (TH_WAIT|TH_TERMINATE)) == TH_WAIT) {
if (!thread_unblock(thread, wresult))
thread_setrun(thread, SCHED_PREEMPT | SCHED_TAILQ);
return (KERN_SUCCESS);
}
return (KERN_NOT_WAITING);
}
__private_extern__
wait_result_t
thread_mark_wait_locked(
thread_t thread,
wait_interrupt_t interruptible)
{
boolean_t at_safe_point;
if (interruptible > (thread->options & TH_OPT_INTMASK))
interruptible = thread->options & TH_OPT_INTMASK;
at_safe_point = (interruptible == THREAD_ABORTSAFE);
if ( interruptible == THREAD_UNINT ||
!(thread->state & TH_ABORT) ||
(!at_safe_point &&
(thread->state & TH_ABORT_SAFELY)) ) {
thread->state |= (interruptible) ? TH_WAIT : (TH_WAIT | TH_UNINT);
thread->at_safe_point = at_safe_point;
return (thread->wait_result = THREAD_WAITING);
}
else
if (thread->state & TH_ABORT_SAFELY)
thread->state &= ~(TH_ABORT|TH_ABORT_SAFELY);
return (thread->wait_result = THREAD_INTERRUPTED);
}
__private_extern__
wait_interrupt_t
thread_interrupt_level(
wait_interrupt_t new_level)
{
thread_t thread = current_thread();
wait_interrupt_t result = thread->options & TH_OPT_INTMASK;
thread->options = (thread->options & ~TH_OPT_INTMASK) | (new_level & TH_OPT_INTMASK);
return result;
}
boolean_t
assert_wait_possible(void)
{
thread_t thread;
#if DEBUG
if(debug_mode) return TRUE;
#endif
thread = current_thread();
return (thread == NULL || wait_queue_assert_possible(thread));
}
wait_result_t
assert_wait(
event_t event,
wait_interrupt_t interruptible)
{
register wait_queue_t wq;
register int index;
assert(event != NO_EVENT);
index = wait_hash(event);
wq = &wait_queues[index];
return wait_queue_assert_wait(wq, event, interruptible, 0);
}
wait_result_t
assert_wait_timeout(
event_t event,
wait_interrupt_t interruptible,
uint32_t interval,
uint32_t scale_factor)
{
thread_t thread = current_thread();
wait_result_t wresult;
wait_queue_t wqueue;
uint64_t deadline;
spl_t s;
assert(event != NO_EVENT);
wqueue = &wait_queues[wait_hash(event)];
s = splsched();
wait_queue_lock(wqueue);
thread_lock(thread);
clock_interval_to_deadline(interval, scale_factor, &deadline);
wresult = wait_queue_assert_wait64_locked(wqueue, (uint32_t)event,
interruptible, deadline, thread);
thread_unlock(thread);
wait_queue_unlock(wqueue);
splx(s);
return (wresult);
}
wait_result_t
assert_wait_deadline(
event_t event,
wait_interrupt_t interruptible,
uint64_t deadline)
{
thread_t thread = current_thread();
wait_result_t wresult;
wait_queue_t wqueue;
spl_t s;
assert(event != NO_EVENT);
wqueue = &wait_queues[wait_hash(event)];
s = splsched();
wait_queue_lock(wqueue);
thread_lock(thread);
wresult = wait_queue_assert_wait64_locked(wqueue, (uint32_t)event,
interruptible, deadline, thread);
thread_unlock(thread);
wait_queue_unlock(wqueue);
splx(s);
return (wresult);
}
__private_extern__ wait_result_t
thread_sleep_fast_usimple_lock(
event_t event,
simple_lock_t lock,
wait_interrupt_t interruptible)
{
wait_result_t res;
res = assert_wait(event, interruptible);
if (res == THREAD_WAITING) {
simple_unlock(lock);
res = thread_block(THREAD_CONTINUE_NULL);
simple_lock(lock);
}
return res;
}
wait_result_t
thread_sleep_usimple_lock(
event_t event,
usimple_lock_t lock,
wait_interrupt_t interruptible)
{
wait_result_t res;
res = assert_wait(event, interruptible);
if (res == THREAD_WAITING) {
usimple_unlock(lock);
res = thread_block(THREAD_CONTINUE_NULL);
usimple_lock(lock);
}
return res;
}
wait_result_t
thread_sleep_mutex(
event_t event,
mutex_t *mutex,
wait_interrupt_t interruptible)
{
wait_result_t res;
res = assert_wait(event, interruptible);
if (res == THREAD_WAITING) {
mutex_unlock(mutex);
res = thread_block(THREAD_CONTINUE_NULL);
mutex_lock(mutex);
}
return res;
}
wait_result_t
thread_sleep_mutex_deadline(
event_t event,
mutex_t *mutex,
uint64_t deadline,
wait_interrupt_t interruptible)
{
wait_result_t res;
res = assert_wait_deadline(event, interruptible, deadline);
if (res == THREAD_WAITING) {
mutex_unlock(mutex);
res = thread_block(THREAD_CONTINUE_NULL);
mutex_lock(mutex);
}
return res;
}
wait_result_t
thread_sleep_lock_write(
event_t event,
lock_t *lock,
wait_interrupt_t interruptible)
{
wait_result_t res;
res = assert_wait(event, interruptible);
if (res == THREAD_WAITING) {
lock_write_done(lock);
res = thread_block(THREAD_CONTINUE_NULL);
lock_write(lock);
}
return res;
}
boolean_t
thread_stop(
thread_t thread)
{
wait_result_t wresult;
spl_t s;
s = splsched();
wake_lock(thread);
while (thread->state & TH_SUSP) {
thread->wake_active = TRUE;
wresult = assert_wait(&thread->wake_active, THREAD_ABORTSAFE);
wake_unlock(thread);
splx(s);
if (wresult == THREAD_WAITING)
wresult = thread_block(THREAD_CONTINUE_NULL);
if (wresult != THREAD_AWAKENED)
return (FALSE);
s = splsched();
wake_lock(thread);
}
thread_lock(thread);
thread->state |= TH_SUSP;
while (thread->state & TH_RUN) {
processor_t processor = thread->last_processor;
if ( processor != PROCESSOR_NULL &&
processor->state == PROCESSOR_RUNNING &&
processor->active_thread == thread )
cause_ast_check(processor);
thread_unlock(thread);
thread->wake_active = TRUE;
wresult = assert_wait(&thread->wake_active, THREAD_ABORTSAFE);
wake_unlock(thread);
splx(s);
if (wresult == THREAD_WAITING)
wresult = thread_block(THREAD_CONTINUE_NULL);
if (wresult != THREAD_AWAKENED) {
thread_unstop(thread);
return (FALSE);
}
s = splsched();
wake_lock(thread);
thread_lock(thread);
}
thread_unlock(thread);
wake_unlock(thread);
splx(s);
return (TRUE);
}
void
thread_unstop(
thread_t thread)
{
spl_t s = splsched();
wake_lock(thread);
thread_lock(thread);
if ((thread->state & (TH_RUN|TH_WAIT|TH_SUSP)) == TH_SUSP) {
thread->state &= ~TH_SUSP;
thread_unblock(thread, THREAD_AWAKENED);
thread_setrun(thread, SCHED_PREEMPT | SCHED_TAILQ);
}
else
if (thread->state & TH_SUSP) {
thread->state &= ~TH_SUSP;
if (thread->wake_active) {
thread->wake_active = FALSE;
thread_unlock(thread);
wake_unlock(thread);
splx(s);
thread_wakeup(&thread->wake_active);
return;
}
}
thread_unlock(thread);
wake_unlock(thread);
splx(s);
}
void
thread_wait(
thread_t thread)
{
wait_result_t wresult;
spl_t s = splsched();
wake_lock(thread);
thread_lock(thread);
while (thread->state & TH_RUN) {
processor_t processor = thread->last_processor;
if ( processor != PROCESSOR_NULL &&
processor->state == PROCESSOR_RUNNING &&
processor->active_thread == thread )
cause_ast_check(processor);
thread_unlock(thread);
thread->wake_active = TRUE;
wresult = assert_wait(&thread->wake_active, THREAD_UNINT);
wake_unlock(thread);
splx(s);
if (wresult == THREAD_WAITING)
thread_block(THREAD_CONTINUE_NULL);
s = splsched();
wake_lock(thread);
thread_lock(thread);
}
thread_unlock(thread);
wake_unlock(thread);
splx(s);
}
__private_extern__ kern_return_t
clear_wait_internal(
thread_t thread,
wait_result_t wresult)
{
wait_queue_t wq = thread->wait_queue;
int i = LockTimeOut;
do {
if (wresult == THREAD_INTERRUPTED && (thread->state & TH_UNINT))
return (KERN_FAILURE);
if (wq != WAIT_QUEUE_NULL) {
if (wait_queue_lock_try(wq)) {
wait_queue_pull_thread_locked(wq, thread, TRUE);
}
else {
thread_unlock(thread);
delay(1);
thread_lock(thread);
if (wq != thread->wait_queue)
return (KERN_NOT_WAITING);
continue;
}
}
return (thread_go(thread, wresult));
} while (--i > 0);
panic("clear_wait_internal: deadlock: thread=0x%x, wq=0x%x, cpu=%d\n",
thread, wq, cpu_number());
return (KERN_FAILURE);
}
kern_return_t
clear_wait(
thread_t thread,
wait_result_t result)
{
kern_return_t ret;
spl_t s;
s = splsched();
thread_lock(thread);
ret = clear_wait_internal(thread, result);
thread_unlock(thread);
splx(s);
return ret;
}
kern_return_t
thread_wakeup_prim(
event_t event,
boolean_t one_thread,
wait_result_t result)
{
register wait_queue_t wq;
register int index;
index = wait_hash(event);
wq = &wait_queues[index];
if (one_thread)
return (wait_queue_wakeup_one(wq, event, result));
else
return (wait_queue_wakeup_all(wq, event, result));
}
processor_t
thread_bind(
register thread_t thread,
processor_t processor)
{
processor_t prev;
run_queue_t runq = RUN_QUEUE_NULL;
spl_t s;
s = splsched();
thread_lock(thread);
prev = thread->bound_processor;
if (prev != PROCESSOR_NULL)
runq = run_queue_remove(thread);
thread->bound_processor = processor;
if (runq != RUN_QUEUE_NULL)
thread_setrun(thread, SCHED_PREEMPT | SCHED_TAILQ);
thread_unlock(thread);
splx(s);
return (prev);
}
struct {
uint32_t idle_pset_last,
idle_pset_any,
idle_bound;
uint32_t pset_self,
pset_last,
pset_other,
bound_self,
bound_other;
uint32_t realtime_self,
realtime_last,
realtime_other;
uint32_t missed_realtime,
missed_other;
} dispatch_counts;
thread_t
thread_select(
register processor_t processor)
{
register thread_t thread;
processor_set_t pset;
boolean_t other_runnable;
pset = processor->processor_set;
thread = processor->active_thread;
if (thread->sched_stamp != sched_tick)
update_priority(thread);
processor->current_pri = thread->sched_pri;
simple_lock(&pset->sched_lock);
other_runnable = processor->runq.count > 0 || pset->runq.count > 0;
if ( thread->state == TH_RUN &&
thread->processor_set == pset &&
(thread->bound_processor == PROCESSOR_NULL ||
thread->bound_processor == processor) ) {
if ( thread->sched_pri >= BASEPRI_RTQUEUES &&
first_timeslice(processor) ) {
if (pset->runq.highq >= BASEPRI_RTQUEUES) {
register run_queue_t runq = &pset->runq;
register queue_t q;
q = runq->queues + runq->highq;
if (((thread_t)q->next)->realtime.deadline <
processor->deadline) {
thread = (thread_t)q->next;
((queue_entry_t)thread)->next->prev = q;
q->next = ((queue_entry_t)thread)->next;
thread->runq = RUN_QUEUE_NULL;
assert(thread->sched_mode & TH_MODE_PREEMPT);
runq->count--; runq->urgency--;
if (queue_empty(q)) {
if (runq->highq != IDLEPRI)
clrbit(MAXPRI - runq->highq, runq->bitmap);
runq->highq = MAXPRI - ffsbit(runq->bitmap);
}
}
}
processor->deadline = thread->realtime.deadline;
simple_unlock(&pset->sched_lock);
return (thread);
}
if ( (!other_runnable ||
(processor->runq.highq < thread->sched_pri &&
pset->runq.highq < thread->sched_pri)) ) {
processor->deadline = UINT64_MAX;
simple_unlock(&pset->sched_lock);
return (thread);
}
}
if (other_runnable)
thread = choose_thread(pset, processor);
else {
if (processor->state == PROCESSOR_RUNNING) {
remqueue(&pset->active_queue, (queue_entry_t)processor);
processor->state = PROCESSOR_IDLE;
enqueue_tail(&pset->idle_queue, (queue_entry_t)processor);
pset->idle_count++;
}
processor->deadline = UINT64_MAX;
thread = processor->idle_thread;
}
simple_unlock(&pset->sched_lock);
return (thread);
}
#define funnel_release_check(thread, debug) \
MACRO_BEGIN \
if ((thread)->funnel_state & TH_FN_OWNED) { \
(thread)->funnel_state = TH_FN_REFUNNEL; \
KERNEL_DEBUG(0x603242c | DBG_FUNC_NONE, \
(thread)->funnel_lock, (debug), 0, 0, 0); \
funnel_unlock((thread)->funnel_lock); \
} \
MACRO_END
#define funnel_refunnel_check(thread, debug) \
MACRO_BEGIN \
if ((thread)->funnel_state & TH_FN_REFUNNEL) { \
kern_return_t result = (thread)->wait_result; \
\
(thread)->funnel_state = 0; \
KERNEL_DEBUG(0x6032428 | DBG_FUNC_NONE, \
(thread)->funnel_lock, (debug), 0, 0, 0); \
funnel_lock((thread)->funnel_lock); \
KERNEL_DEBUG(0x6032430 | DBG_FUNC_NONE, \
(thread)->funnel_lock, (debug), 0, 0, 0); \
(thread)->funnel_state = TH_FN_OWNED; \
(thread)->wait_result = result; \
} \
MACRO_END
boolean_t
thread_invoke(
register thread_t old_thread,
register thread_t new_thread,
ast_t reason)
{
thread_continue_t new_cont, continuation = old_thread->continuation;
void *new_param, *parameter = old_thread->parameter;
processor_t processor;
thread_t prev_thread;
if (get_preemption_level() != 0)
panic("thread_invoke: preemption_level %d\n",
get_preemption_level());
assert(old_thread == current_thread());
thread_lock(new_thread);
new_thread->state &= ~TH_UNINT;
assert(thread_runnable(new_thread));
if ( (old_thread->sched_mode & TH_MODE_REALTIME) &&
!old_thread->reserved_stack ) {
old_thread->reserved_stack = old_thread->kernel_stack;
}
if (continuation != NULL) {
if (!new_thread->kernel_stack) {
if ( old_thread->kernel_stack == old_thread->reserved_stack &&
!new_thread->reserved_stack)
goto need_stack;
new_cont = new_thread->continuation;
new_thread->continuation = NULL;
new_param = new_thread->parameter;
new_thread->parameter = NULL;
processor = current_processor();
processor->active_thread = new_thread;
processor->current_pri = new_thread->sched_pri;
new_thread->last_processor = processor;
ast_context(new_thread);
thread_unlock(new_thread);
current_task()->csw++;
old_thread->reason = reason;
processor->last_dispatch = mach_absolute_time();
timer_event((uint32_t)processor->last_dispatch,
&new_thread->system_timer);
thread_done(old_thread, new_thread, processor);
machine_stack_handoff(old_thread, new_thread);
thread_begin(new_thread, processor);
thread_dispatch(old_thread);
counter_always(c_thread_invoke_hits++);
funnel_refunnel_check(new_thread, 2);
(void) spllo();
assert(new_cont);
call_continuation(new_cont, new_param, new_thread->wait_result);
}
else
if (new_thread == old_thread) {
counter(++c_thread_invoke_same);
thread_unlock(new_thread);
funnel_refunnel_check(new_thread, 3);
(void) spllo();
call_continuation(continuation, parameter, new_thread->wait_result);
}
}
else {
if (!new_thread->kernel_stack) {
need_stack:
if (!stack_alloc_try(new_thread)) {
counter_always(c_thread_invoke_misses++);
thread_unlock(new_thread);
thread_stack_enqueue(new_thread);
return (FALSE);
}
}
else
if (new_thread == old_thread) {
counter(++c_thread_invoke_same);
thread_unlock(new_thread);
return (TRUE);
}
}
processor = current_processor();
processor->active_thread = new_thread;
processor->current_pri = new_thread->sched_pri;
new_thread->last_processor = processor;
ast_context(new_thread);
assert(thread_runnable(new_thread));
thread_unlock(new_thread);
counter_always(c_thread_invoke_csw++);
current_task()->csw++;
assert(old_thread->runq == RUN_QUEUE_NULL);
old_thread->reason = reason;
processor->last_dispatch = mach_absolute_time();
timer_event((uint32_t)processor->last_dispatch, &new_thread->system_timer);
thread_done(old_thread, new_thread, processor);
prev_thread = machine_switch_context(old_thread, continuation, new_thread);
thread_begin(old_thread, old_thread->last_processor);
thread_dispatch(prev_thread);
if (continuation) {
funnel_refunnel_check(old_thread, 3);
(void) spllo();
call_continuation(continuation, parameter, old_thread->wait_result);
}
return (TRUE);
}
void
thread_done(
thread_t old_thread,
thread_t new_thread,
processor_t processor)
{
if (!(old_thread->state & TH_IDLE)) {
if ( first_timeslice(processor) &&
processor->quantum_end > processor->last_dispatch )
old_thread->current_quantum =
(processor->quantum_end - processor->last_dispatch);
else
old_thread->current_quantum = 0;
if (old_thread->sched_mode & TH_MODE_REALTIME) {
if (old_thread->current_quantum == 0) {
old_thread->realtime.deadline = UINT64_MAX;
old_thread->reason |= AST_QUANTUM;
}
}
else {
if (old_thread->current_quantum < min_std_quantum) {
old_thread->reason |= AST_QUANTUM;
old_thread->current_quantum += std_quantum;
}
}
if ((old_thread->reason & (AST_HANDOFF|AST_QUANTUM)) == AST_HANDOFF) {
new_thread->current_quantum = old_thread->current_quantum;
old_thread->reason |= AST_QUANTUM;
old_thread->current_quantum = 0;
}
old_thread->last_switch = processor->last_dispatch;
old_thread->computation_metered +=
(old_thread->last_switch - old_thread->computation_epoch);
}
}
void
thread_begin(
thread_t thread,
processor_t processor)
{
if (!(thread->state & TH_IDLE)) {
if (thread->current_quantum == 0)
thread_quantum_init(thread);
processor->quantum_end =
(processor->last_dispatch + thread->current_quantum);
timer_call_enter1(&processor->quantum_timer,
thread, processor->quantum_end);
processor_timeslice_setup(processor, thread);
thread->last_switch = processor->last_dispatch;
thread->computation_epoch = thread->last_switch;
}
else {
timer_call_cancel(&processor->quantum_timer);
processor->timeslice = 1;
}
}
void
thread_dispatch(
register thread_t thread)
{
#ifndef i386
if (thread->continuation != NULL && thread->kernel_stack)
stack_free(thread);
#endif
if (!(thread->state & TH_IDLE)) {
wake_lock(thread);
thread_lock(thread);
if (!(thread->state & TH_WAIT)) {
if (thread->reason & AST_QUANTUM)
thread_setrun(thread, SCHED_TAILQ);
else
if (thread->reason & AST_PREEMPT)
thread_setrun(thread, SCHED_HEADQ);
else
thread_setrun(thread, SCHED_PREEMPT | SCHED_TAILQ);
thread->reason = AST_NONE;
thread_unlock(thread);
wake_unlock(thread);
}
else {
boolean_t wake;
thread->state &= ~TH_RUN;
wake = thread->wake_active;
thread->wake_active = FALSE;
if (thread->sched_mode & TH_MODE_TIMESHARE)
pset_share_decr(thread->processor_set);
pset_run_decr(thread->processor_set);
thread_unlock(thread);
wake_unlock(thread);
if (thread->options & TH_OPT_CALLOUT)
call_thread_block();
if (wake)
thread_wakeup((event_t)&thread->wake_active);
if (thread->state & TH_TERMINATE)
thread_terminate_enqueue(thread);
}
}
}
counter(mach_counter_t c_thread_block_calls = 0;)
wait_result_t
thread_block_reason(
thread_continue_t continuation,
void *parameter,
ast_t reason)
{
register thread_t self = current_thread();
register processor_t processor;
register thread_t new_thread;
spl_t s;
counter(++c_thread_block_calls);
s = splsched();
if (!(reason & AST_PREEMPT))
funnel_release_check(self, 2);
processor = current_processor();
if (s != FALSE && (self->state & (TH_IDLE|TH_TERMINATE|TH_WAIT)) == TH_WAIT) {
if ( processor->processor_set->processor_count > 1 &&
processor->processor_set->runq.count == 0 &&
processor->runq.count == 0 )
processor = delay_idle(processor, self);
}
if (reason & AST_YIELD)
processor->timeslice = 0;
ast_off(AST_SCHEDULING);
self->continuation = continuation;
self->parameter = parameter;
thread_lock(self);
new_thread = thread_select(processor);
assert(new_thread && thread_runnable(new_thread));
thread_unlock(self);
while (!thread_invoke(self, new_thread, reason)) {
thread_lock(self);
new_thread = thread_select(processor);
assert(new_thread && thread_runnable(new_thread));
thread_unlock(self);
}
funnel_refunnel_check(self, 5);
splx(s);
return (self->wait_result);
}
wait_result_t
thread_block(
thread_continue_t continuation)
{
return thread_block_reason(continuation, NULL, AST_NONE);
}
wait_result_t
thread_block_parameter(
thread_continue_t continuation,
void *parameter)
{
return thread_block_reason(continuation, parameter, AST_NONE);
}
int
thread_run(
thread_t self,
thread_continue_t continuation,
void *parameter,
thread_t new_thread)
{
ast_t handoff = AST_HANDOFF;
funnel_release_check(self, 3);
self->continuation = continuation;
self->parameter = parameter;
while (!thread_invoke(self, new_thread, handoff)) {
register processor_t processor = current_processor();
thread_lock(self);
new_thread = thread_select(processor);
thread_unlock(self);
handoff = AST_NONE;
}
funnel_refunnel_check(self, 6);
return (self->wait_result);
}
void
thread_continue(
register thread_t old_thread)
{
register thread_t self = current_thread();
register thread_continue_t continuation;
register void *parameter;
continuation = self->continuation;
self->continuation = NULL;
parameter = self->parameter;
self->parameter = NULL;
thread_begin(self, self->last_processor);
if (old_thread != THREAD_NULL)
thread_dispatch(old_thread);
funnel_refunnel_check(self, 4);
if (old_thread != THREAD_NULL)
(void)spllo();
call_continuation(continuation, parameter, self->wait_result);
}
static boolean_t
run_queue_enqueue(
register run_queue_t rq,
register thread_t thread,
integer_t options)
{
register int whichq = thread->sched_pri;
register queue_t queue = &rq->queues[whichq];
boolean_t result = FALSE;
assert(whichq >= MINPRI && whichq <= MAXPRI);
assert(thread->runq == RUN_QUEUE_NULL);
if (queue_empty(queue)) {
enqueue_tail(queue, (queue_entry_t)thread);
setbit(MAXPRI - whichq, rq->bitmap);
if (whichq > rq->highq) {
rq->highq = whichq;
result = TRUE;
}
}
else
if (options & SCHED_HEADQ)
enqueue_head(queue, (queue_entry_t)thread);
else
enqueue_tail(queue, (queue_entry_t)thread);
thread->runq = rq;
if (thread->sched_mode & TH_MODE_PREEMPT)
rq->urgency++;
rq->count++;
return (result);
}
static void
realtime_schedule_insert(
register processor_set_t pset,
register thread_t thread)
{
register run_queue_t rq = &pset->runq;
register int whichq = thread->sched_pri;
register queue_t queue = &rq->queues[whichq];
uint64_t deadline = thread->realtime.deadline;
boolean_t try_preempt = FALSE;
assert(whichq >= BASEPRI_REALTIME && whichq <= MAXPRI);
assert(thread->runq == RUN_QUEUE_NULL);
if (queue_empty(queue)) {
enqueue_tail(queue, (queue_entry_t)thread);
setbit(MAXPRI - whichq, rq->bitmap);
if (whichq > rq->highq)
rq->highq = whichq;
try_preempt = TRUE;
}
else {
register thread_t entry = (thread_t)queue_first(queue);
while (TRUE) {
if ( queue_end(queue, (queue_entry_t)entry) ||
deadline < entry->realtime.deadline ) {
entry = (thread_t)queue_prev((queue_entry_t)entry);
break;
}
entry = (thread_t)queue_next((queue_entry_t)entry);
}
if ((queue_entry_t)entry == queue)
try_preempt = TRUE;
insque((queue_entry_t)thread, (queue_entry_t)entry);
}
thread->runq = rq;
assert(thread->sched_mode & TH_MODE_PREEMPT);
rq->count++; rq->urgency++;
if (try_preempt) {
register processor_t processor;
processor = current_processor();
if ( pset == processor->processor_set &&
(thread->sched_pri > processor->current_pri ||
deadline < processor->deadline ) ) {
dispatch_counts.realtime_self++;
simple_unlock(&pset->sched_lock);
ast_on(AST_PREEMPT | AST_URGENT);
return;
}
if ( pset->processor_count > 1 ||
pset != processor->processor_set ) {
processor_t myprocessor, lastprocessor;
queue_entry_t next;
myprocessor = processor;
processor = thread->last_processor;
if ( processor != myprocessor &&
processor != PROCESSOR_NULL &&
processor->processor_set == pset &&
processor->state == PROCESSOR_RUNNING &&
(thread->sched_pri > processor->current_pri ||
deadline < processor->deadline ) ) {
dispatch_counts.realtime_last++;
cause_ast_check(processor);
simple_unlock(&pset->sched_lock);
return;
}
lastprocessor = processor;
queue = &pset->active_queue;
processor = (processor_t)queue_first(queue);
while (!queue_end(queue, (queue_entry_t)processor)) {
next = queue_next((queue_entry_t)processor);
if ( processor != myprocessor &&
processor != lastprocessor &&
(thread->sched_pri > processor->current_pri ||
deadline < processor->deadline ) ) {
if (!queue_end(queue, next)) {
remqueue(queue, (queue_entry_t)processor);
enqueue_tail(queue, (queue_entry_t)processor);
}
dispatch_counts.realtime_other++;
cause_ast_check(processor);
simple_unlock(&pset->sched_lock);
return;
}
processor = (processor_t)next;
}
}
}
simple_unlock(&pset->sched_lock);
}
void
thread_setrun(
register thread_t new_thread,
integer_t options)
{
register processor_t processor;
register processor_set_t pset;
register thread_t thread;
ast_t preempt = (options & SCHED_PREEMPT)?
AST_PREEMPT: AST_NONE;
assert(thread_runnable(new_thread));
if (new_thread->sched_stamp != sched_tick)
update_priority(new_thread);
if (new_thread->sched_mode & TH_MODE_PREEMPT)
preempt = (AST_PREEMPT | AST_URGENT);
assert(new_thread->runq == RUN_QUEUE_NULL);
if ((processor = new_thread->bound_processor) == PROCESSOR_NULL) {
pset = new_thread->processor_set;
processor = new_thread->last_processor;
if ( pset->processor_count > 1 &&
processor != PROCESSOR_NULL &&
processor->state == PROCESSOR_IDLE ) {
processor_lock(processor);
simple_lock(&pset->sched_lock);
if ( processor->processor_set == pset &&
processor->state == PROCESSOR_IDLE ) {
remqueue(&pset->idle_queue, (queue_entry_t)processor);
pset->idle_count--;
processor->next_thread = new_thread;
if (new_thread->sched_pri >= BASEPRI_RTQUEUES)
processor->deadline = new_thread->realtime.deadline;
else
processor->deadline = UINT64_MAX;
processor->state = PROCESSOR_DISPATCHING;
dispatch_counts.idle_pset_last++;
simple_unlock(&pset->sched_lock);
processor_unlock(processor);
if (processor != current_processor())
machine_signal_idle(processor);
return;
}
processor_unlock(processor);
}
else
simple_lock(&pset->sched_lock);
if (pset->idle_count > 0) {
processor = (processor_t)dequeue_head(&pset->idle_queue);
pset->idle_count--;
processor->next_thread = new_thread;
if (new_thread->sched_pri >= BASEPRI_RTQUEUES)
processor->deadline = new_thread->realtime.deadline;
else
processor->deadline = UINT64_MAX;
processor->state = PROCESSOR_DISPATCHING;
dispatch_counts.idle_pset_any++;
simple_unlock(&pset->sched_lock);
if (processor != current_processor())
machine_signal_idle(processor);
return;
}
if (new_thread->sched_pri >= BASEPRI_RTQUEUES)
realtime_schedule_insert(pset, new_thread);
else {
if (!run_queue_enqueue(&pset->runq, new_thread, options))
preempt = AST_NONE;
timeshare_quanta_update(pset);
if (preempt != AST_NONE) {
processor = current_processor();
thread = processor->active_thread;
if ( pset == processor->processor_set &&
csw_needed(thread, processor) ) {
dispatch_counts.pset_self++;
simple_unlock(&pset->sched_lock);
ast_on(preempt);
return;
}
if ( pset->processor_count > 1 ||
pset != processor->processor_set ) {
queue_t queue = &pset->active_queue;
processor_t myprocessor, lastprocessor;
queue_entry_t next;
myprocessor = processor;
processor = new_thread->last_processor;
if ( processor != myprocessor &&
processor != PROCESSOR_NULL &&
processor->processor_set == pset &&
processor->state == PROCESSOR_RUNNING &&
new_thread->sched_pri > processor->current_pri ) {
dispatch_counts.pset_last++;
cause_ast_check(processor);
simple_unlock(&pset->sched_lock);
return;
}
lastprocessor = processor;
processor = (processor_t)queue_first(queue);
while (!queue_end(queue, (queue_entry_t)processor)) {
next = queue_next((queue_entry_t)processor);
if ( processor != myprocessor &&
processor != lastprocessor &&
new_thread->sched_pri >
processor->current_pri ) {
if (!queue_end(queue, next)) {
remqueue(queue, (queue_entry_t)processor);
enqueue_tail(queue, (queue_entry_t)processor);
}
dispatch_counts.pset_other++;
cause_ast_check(processor);
simple_unlock(&pset->sched_lock);
return;
}
processor = (processor_t)next;
}
}
}
simple_unlock(&pset->sched_lock);
}
}
else {
processor_lock(processor);
pset = processor->processor_set;
if (pset != PROCESSOR_SET_NULL) {
simple_lock(&pset->sched_lock);
if (processor->state == PROCESSOR_IDLE) {
remqueue(&pset->idle_queue, (queue_entry_t)processor);
pset->idle_count--;
processor->next_thread = new_thread;
processor->deadline = UINT64_MAX;
processor->state = PROCESSOR_DISPATCHING;
dispatch_counts.idle_bound++;
simple_unlock(&pset->sched_lock);
processor_unlock(processor);
if (processor != current_processor())
machine_signal_idle(processor);
return;
}
}
if (!run_queue_enqueue(&processor->runq, new_thread, options))
preempt = AST_NONE;
if (preempt != AST_NONE) {
if (processor == current_processor()) {
thread = processor->active_thread;
if (csw_needed(thread, processor)) {
dispatch_counts.bound_self++;
ast_on(preempt);
}
}
else
if ( processor->state == PROCESSOR_RUNNING &&
new_thread->sched_pri > processor->current_pri ) {
dispatch_counts.bound_other++;
cause_ast_check(processor);
}
}
if (pset != PROCESSOR_SET_NULL)
simple_unlock(&pset->sched_lock);
processor_unlock(processor);
}
}
ast_t
csw_check(
thread_t thread,
processor_t processor)
{
int current_pri = thread->sched_pri;
ast_t result = AST_NONE;
run_queue_t runq;
if (first_timeslice(processor)) {
runq = &processor->processor_set->runq;
if (runq->highq >= BASEPRI_RTQUEUES)
return (AST_PREEMPT | AST_URGENT);
if (runq->highq > current_pri) {
if (runq->urgency > 0)
return (AST_PREEMPT | AST_URGENT);
result |= AST_PREEMPT;
}
runq = &processor->runq;
if (runq->highq > current_pri) {
if (runq->urgency > 0)
return (AST_PREEMPT | AST_URGENT);
result |= AST_PREEMPT;
}
}
else {
runq = &processor->processor_set->runq;
if (runq->highq >= current_pri) {
if (runq->urgency > 0)
return (AST_PREEMPT | AST_URGENT);
result |= AST_PREEMPT;
}
runq = &processor->runq;
if (runq->highq >= current_pri) {
if (runq->urgency > 0)
return (AST_PREEMPT | AST_URGENT);
result |= AST_PREEMPT;
}
}
if (result != AST_NONE)
return (result);
if (thread->state & TH_SUSP)
result |= AST_PREEMPT;
return (result);
}
void
set_sched_pri(
thread_t thread,
int priority)
{
register struct run_queue *rq = run_queue_remove(thread);
if ( !(thread->sched_mode & TH_MODE_TIMESHARE) &&
(priority >= BASEPRI_PREEMPT ||
(thread->task_priority < MINPRI_KERNEL &&
thread->task_priority >= BASEPRI_BACKGROUND &&
priority > thread->task_priority) ) )
thread->sched_mode |= TH_MODE_PREEMPT;
else
thread->sched_mode &= ~TH_MODE_PREEMPT;
thread->sched_pri = priority;
if (rq != RUN_QUEUE_NULL)
thread_setrun(thread, SCHED_PREEMPT | SCHED_TAILQ);
else
if (thread->state & TH_RUN) {
processor_t processor = thread->last_processor;
if (thread == current_thread()) {
ast_t preempt = csw_check(thread, processor);
if (preempt != AST_NONE)
ast_on(preempt);
processor->current_pri = priority;
}
else
if ( processor != PROCESSOR_NULL &&
processor->active_thread == thread )
cause_ast_check(processor);
}
}
#if 0
static void
run_queue_check(
run_queue_t rq,
thread_t thread)
{
queue_t q;
queue_entry_t qe;
if (rq != thread->runq)
panic("run_queue_check: thread runq");
if (thread->sched_pri > MAXPRI || thread->sched_pri < MINPRI)
panic("run_queue_check: thread sched_pri");
q = &rq->queues[thread->sched_pri];
qe = queue_first(q);
while (!queue_end(q, qe)) {
if (qe == (queue_entry_t)thread)
return;
qe = queue_next(qe);
}
panic("run_queue_check: end");
}
#endif
run_queue_t
run_queue_remove(
thread_t thread)
{
register run_queue_t rq = thread->runq;
if (rq != RUN_QUEUE_NULL) {
processor_set_t pset = thread->processor_set;
processor_t processor = thread->bound_processor;
if (processor != PROCESSOR_NULL) {
processor_lock(processor);
pset = processor->processor_set;
}
if (pset != PROCESSOR_SET_NULL)
simple_lock(&pset->sched_lock);
if (rq == thread->runq) {
remqueue(&rq->queues[0], (queue_entry_t)thread);
rq->count--;
if (thread->sched_mode & TH_MODE_PREEMPT)
rq->urgency--;
assert(rq->urgency >= 0);
if (queue_empty(rq->queues + thread->sched_pri)) {
if (thread->sched_pri != IDLEPRI)
clrbit(MAXPRI - thread->sched_pri, rq->bitmap);
rq->highq = MAXPRI - ffsbit(rq->bitmap);
}
thread->runq = RUN_QUEUE_NULL;
}
else {
assert(thread->runq == RUN_QUEUE_NULL);
rq = RUN_QUEUE_NULL;
}
if (pset != PROCESSOR_SET_NULL)
simple_unlock(&pset->sched_lock);
if (processor != PROCESSOR_NULL)
processor_unlock(processor);
}
return (rq);
}
static thread_t
choose_thread(
processor_set_t pset,
processor_t processor)
{
register run_queue_t runq;
register thread_t thread;
register queue_t q;
runq = &processor->runq;
if (runq->count > 0 && runq->highq >= pset->runq.highq) {
q = runq->queues + runq->highq;
thread = (thread_t)q->next;
((queue_entry_t)thread)->next->prev = q;
q->next = ((queue_entry_t)thread)->next;
thread->runq = RUN_QUEUE_NULL;
runq->count--;
if (thread->sched_mode & TH_MODE_PREEMPT)
runq->urgency--;
assert(runq->urgency >= 0);
if (queue_empty(q)) {
if (runq->highq != IDLEPRI)
clrbit(MAXPRI - runq->highq, runq->bitmap);
runq->highq = MAXPRI - ffsbit(runq->bitmap);
}
processor->deadline = UINT64_MAX;
return (thread);
}
runq = &pset->runq;
assert(runq->count > 0);
q = runq->queues + runq->highq;
thread = (thread_t)q->next;
((queue_entry_t)thread)->next->prev = q;
q->next = ((queue_entry_t)thread)->next;
thread->runq = RUN_QUEUE_NULL;
runq->count--;
if (runq->highq >= BASEPRI_RTQUEUES)
processor->deadline = thread->realtime.deadline;
else
processor->deadline = UINT64_MAX;
if (thread->sched_mode & TH_MODE_PREEMPT)
runq->urgency--;
assert(runq->urgency >= 0);
if (queue_empty(q)) {
if (runq->highq != IDLEPRI)
clrbit(MAXPRI - runq->highq, runq->bitmap);
runq->highq = MAXPRI - ffsbit(runq->bitmap);
}
timeshare_quanta_update(pset);
return (thread);
}
static processor_t
delay_idle(
processor_t processor,
thread_t self)
{
int *gcount, *lcount;
uint64_t abstime, spin, limit;
lcount = &processor->runq.count;
gcount = &processor->processor_set->runq.count;
abstime = mach_absolute_time();
limit = abstime + delay_idle_limit;
spin = abstime + delay_idle_spin;
timer_event((uint32_t)abstime, &processor->idle_thread->system_timer);
self->options |= TH_OPT_DELAYIDLE;
while ( *gcount == 0 && *lcount == 0 &&
(self->state & TH_WAIT) != 0 &&
abstime < limit ) {
if (abstime >= spin) {
(void)spllo();
(void)splsched();
processor = current_processor();
lcount = &processor->runq.count;
gcount = &processor->processor_set->runq.count;
abstime = mach_absolute_time();
spin = abstime + delay_idle_spin;
timer_event((uint32_t)abstime, &processor->idle_thread->system_timer);
}
else
abstime = mach_absolute_time();
}
timer_event((uint32_t)abstime, &self->system_timer);
self->options &= ~TH_OPT_DELAYIDLE;
return (processor);
}
int no_dispatch_count = 0;
void
idle_thread(void)
{
register processor_t processor;
register thread_t *threadp;
register int *gcount;
register int *lcount;
register thread_t new_thread;
register int state;
register processor_set_t pset;
ast_t *myast = ast_pending();
processor = current_processor();
threadp = &processor->next_thread;
lcount = &processor->runq.count;
gcount = &processor->processor_set->runq.count;
(void)splsched();
#ifdef __ppc__
pmsDown();
#endif
while ( (*threadp == THREAD_NULL) &&
(*gcount == 0) && (*lcount == 0) ) {
if (*myast &~ (AST_SCHEDULING | AST_BSD)) {
*myast &= AST_NONE;
(void)spllo();
}
else
machine_idle();
(void)splsched();
}
pset = processor->processor_set;
simple_lock(&pset->sched_lock);
#ifdef __ppc__
pmsStep(0);
#endif
state = processor->state;
if (state == PROCESSOR_DISPATCHING) {
new_thread = *threadp;
*threadp = (volatile thread_t) THREAD_NULL;
processor->state = PROCESSOR_RUNNING;
enqueue_tail(&pset->active_queue, (queue_entry_t)processor);
if ( pset->runq.highq >= BASEPRI_RTQUEUES &&
new_thread->sched_pri >= BASEPRI_RTQUEUES ) {
register run_queue_t runq = &pset->runq;
register queue_t q;
q = runq->queues + runq->highq;
if (((thread_t)q->next)->realtime.deadline <
processor->deadline) {
thread_t thread = new_thread;
new_thread = (thread_t)q->next;
((queue_entry_t)new_thread)->next->prev = q;
q->next = ((queue_entry_t)new_thread)->next;
new_thread->runq = RUN_QUEUE_NULL;
processor->deadline = new_thread->realtime.deadline;
assert(new_thread->sched_mode & TH_MODE_PREEMPT);
runq->count--; runq->urgency--;
if (queue_empty(q)) {
if (runq->highq != IDLEPRI)
clrbit(MAXPRI - runq->highq, runq->bitmap);
runq->highq = MAXPRI - ffsbit(runq->bitmap);
}
dispatch_counts.missed_realtime++;
simple_unlock(&pset->sched_lock);
thread_lock(thread);
thread_setrun(thread, SCHED_HEADQ);
thread_unlock(thread);
counter(c_idle_thread_handoff++);
thread_run(processor->idle_thread, (thread_continue_t)idle_thread, NULL, new_thread);
}
simple_unlock(&pset->sched_lock);
counter(c_idle_thread_handoff++);
thread_run(processor->idle_thread, (thread_continue_t)idle_thread, NULL, new_thread);
}
if ( processor->runq.highq > new_thread->sched_pri ||
pset->runq.highq > new_thread->sched_pri ) {
thread_t thread = new_thread;
new_thread = choose_thread(pset, processor);
dispatch_counts.missed_other++;
simple_unlock(&pset->sched_lock);
thread_lock(thread);
thread_setrun(thread, SCHED_HEADQ);
thread_unlock(thread);
counter(c_idle_thread_handoff++);
thread_run(processor->idle_thread, (thread_continue_t)idle_thread, NULL, new_thread);
}
else {
simple_unlock(&pset->sched_lock);
counter(c_idle_thread_handoff++);
thread_run(processor->idle_thread, (thread_continue_t)idle_thread, NULL, new_thread);
}
}
else
if (state == PROCESSOR_IDLE) {
no_dispatch_count++;
pset->idle_count--;
remqueue(&pset->idle_queue, (queue_entry_t)processor);
processor->state = PROCESSOR_RUNNING;
enqueue_tail(&pset->active_queue, (queue_entry_t)processor);
simple_unlock(&pset->sched_lock);
counter(c_idle_thread_block++);
thread_block((thread_continue_t)idle_thread);
}
else
if (state == PROCESSOR_SHUTDOWN) {
if ((new_thread = (thread_t)*threadp) != THREAD_NULL) {
*threadp = (volatile thread_t) THREAD_NULL;
processor->deadline = UINT64_MAX;
simple_unlock(&pset->sched_lock);
thread_lock(new_thread);
thread_setrun(new_thread, SCHED_HEADQ);
thread_unlock(new_thread);
}
else
simple_unlock(&pset->sched_lock);
counter(c_idle_thread_block++);
thread_block((thread_continue_t)idle_thread);
}
simple_unlock(&pset->sched_lock);
panic("idle_thread: state %d\n", processor->state);
}
kern_return_t
idle_thread_create(
processor_t processor)
{
kern_return_t result;
thread_t thread;
spl_t s;
result = kernel_thread_create((thread_continue_t)idle_thread, NULL, MAXPRI_KERNEL, &thread);
if (result != KERN_SUCCESS)
return (result);
s = splsched();
thread_lock(thread);
thread->bound_processor = processor;
processor->idle_thread = thread;
thread->sched_pri = thread->priority = IDLEPRI;
thread->state = (TH_RUN | TH_IDLE);
thread_unlock(thread);
splx(s);
thread_deallocate(thread);
return (KERN_SUCCESS);
}
static uint64_t sched_tick_deadline;
void
sched_startup(void)
{
kern_return_t result;
thread_t thread;
result = kernel_thread_start_priority((thread_continue_t)sched_tick_thread, NULL, MAXPRI_KERNEL, &thread);
if (result != KERN_SUCCESS)
panic("sched_startup");
thread_deallocate(thread);
while (sched_cswtime == 0)
thread_block(THREAD_CONTINUE_NULL);
thread_daemon_init();
thread_call_initialize();
}
static void
sched_tick_continue(void)
{
uint64_t abstime = mach_absolute_time();
sched_tick++;
compute_averages();
thread_update_scan();
clock_deadline_for_periodic_event(sched_tick_interval, abstime,
&sched_tick_deadline);
assert_wait_deadline((event_t)sched_tick_thread, THREAD_UNINT, sched_tick_deadline);
thread_block((thread_continue_t)sched_tick_continue);
}
static uint32_t
time_cswitch(void)
{
uint32_t new, hi, low, accum;
uint64_t abstime;
int i, tries = 7;
accum = hi = low = 0;
for (i = 0; i < tries; ++i) {
abstime = mach_absolute_time();
thread_block(THREAD_CONTINUE_NULL);
new = mach_absolute_time() - abstime;
if (i == 0)
accum = hi = low = new;
else {
if (new < low)
low = new;
else
if (new > hi)
hi = new;
accum += new;
}
}
return ((accum - hi - low) / (2 * (tries - 2)));
}
void
sched_tick_thread(void)
{
sched_cswtime = time_cswitch();
sched_tick_deadline = mach_absolute_time();
sched_tick_continue();
}
#define THREAD_UPDATE_SIZE 128
static thread_t thread_update_array[THREAD_UPDATE_SIZE];
static int thread_update_count = 0;
static boolean_t
runq_scan(
run_queue_t runq)
{
register int count;
register queue_t q;
register thread_t thread;
if ((count = runq->count) > 0) {
q = runq->queues + runq->highq;
while (count > 0) {
queue_iterate(q, thread, thread_t, links) {
if ( thread->sched_stamp != sched_tick &&
(thread->sched_mode & TH_MODE_TIMESHARE) ) {
if (thread_update_count == THREAD_UPDATE_SIZE)
return (TRUE);
thread_update_array[thread_update_count++] = thread;
thread_reference_internal(thread);
}
count--;
}
q--;
}
}
return (FALSE);
}
static void
thread_update_scan(void)
{
register boolean_t restart_needed;
register processor_set_t pset = &default_pset;
register processor_t processor;
register thread_t thread;
spl_t s;
do {
s = splsched();
simple_lock(&pset->sched_lock);
restart_needed = runq_scan(&pset->runq);
simple_unlock(&pset->sched_lock);
if (!restart_needed) {
simple_lock(&pset->sched_lock);
processor = (processor_t)queue_first(&pset->processors);
while (!queue_end(&pset->processors, (queue_entry_t)processor)) {
if ((restart_needed = runq_scan(&processor->runq)) != 0)
break;
thread = processor->idle_thread;
if (thread->sched_stamp != sched_tick) {
if (thread_update_count == THREAD_UPDATE_SIZE) {
restart_needed = TRUE;
break;
}
thread_update_array[thread_update_count++] = thread;
thread_reference_internal(thread);
}
processor = (processor_t)queue_next(&processor->processors);
}
simple_unlock(&pset->sched_lock);
}
splx(s);
while (thread_update_count > 0) {
thread = thread_update_array[--thread_update_count];
thread_update_array[thread_update_count] = THREAD_NULL;
s = splsched();
thread_lock(thread);
if ( !(thread->state & (TH_WAIT|TH_SUSP)) &&
thread->sched_stamp != sched_tick )
update_priority(thread);
thread_unlock(thread);
splx(s);
thread_deallocate(thread);
}
} while (restart_needed);
}
#undef thread_wakeup
void
thread_wakeup(
event_t x);
void
thread_wakeup(
event_t x)
{
thread_wakeup_with_result(x, THREAD_AWAKENED);
}
boolean_t
preemption_enabled(void)
{
return (get_preemption_level() == 0 && ml_get_interrupts_enabled());
}
#if DEBUG
static boolean_t
thread_runnable(
thread_t thread)
{
return ((thread->state & (TH_RUN|TH_WAIT)) == TH_RUN);
}
#endif
#if MACH_KDB
#include <ddb/db_output.h>
#define printf kdbprintf
void db_sched(void);
void
db_sched(void)
{
iprintf("Scheduling Statistics:\n");
db_indent += 2;
iprintf("Thread invocations: csw %d same %d\n",
c_thread_invoke_csw, c_thread_invoke_same);
#if MACH_COUNTERS
iprintf("Thread block: calls %d\n",
c_thread_block_calls);
iprintf("Idle thread:\n\thandoff %d block %d no_dispatch %d\n",
c_idle_thread_handoff,
c_idle_thread_block, no_dispatch_count);
iprintf("Sched thread blocks: %d\n", c_sched_thread_block);
#endif
db_indent -= 2;
}
#include <ddb/db_output.h>
void db_show_thread_log(void);
void
db_show_thread_log(void)
{
}
#endif