HelenOS sources
This source file includes following definitions.
- scheduler_fpu_lazy_request
- scheduler_init
- try_find_thread
- find_best_thread
- switch_task
- relink_rq
- fpu_cleanup
- fpu_restore
- prepare_to_run_thread
- add_to_rq
- thread_requeue_preempted
- thread_requeue_sleeping
- cleanup_after_thread
- scheduler_enter
- scheduler_run
- thread_main_func
- steal_thread_from
- kcpulb
- sched_print_list
#include <assert.h>
#include <atomic.h>
#include <proc/scheduler.h>
#include <proc/thread.h>
#include <proc/task.h>
#include <mm/frame.h>
#include <mm/page.h>
#include <mm/as.h>
#include <time/timeout.h>
#include <time/delay.h>
#include <arch/asm.h>
#include <arch/cycle.h>
#include <atomic.h>
#include <synch/spinlock.h>
#include <config.h>
#include <context.h>
#include <fpu_context.h>
#include <halt.h>
#include <arch.h>
#include <adt/list.h>
#include <panic.h>
#include <cpu.h>
#include <stdio.h>
#include <log.h>
#include <stacktrace.h>
atomic_size_t nrdy;
#ifdef CONFIG_FPU_LAZY
void scheduler_fpu_lazy_request(void)
{
fpu_enable();
irq_spinlock_lock(&CPU->fpu_lock, false);
thread_t *owner = atomic_load_explicit(&CPU->fpu_owner, memory_order_relaxed);
if (owner != NULL) {
fpu_context_save(&owner->fpu_context);
atomic_store_explicit(&CPU->fpu_owner, NULL, memory_order_relaxed);
}
irq_spinlock_unlock(&CPU->fpu_lock, false);
if (THREAD->fpu_context_exists) {
fpu_context_restore(&THREAD->fpu_context);
} else {
fpu_init();
THREAD->fpu_context_exists = true;
}
atomic_store_explicit(&CPU->fpu_owner, THREAD, memory_order_relaxed);
}
#endif
void scheduler_init(void)
{
}
static thread_t *try_find_thread(int *rq_index)
{
assert(interrupts_disabled());
assert(CPU != NULL);
if (atomic_load(&CPU->nrdy) == 0)
return NULL;
for (int i = 0; i < RQ_COUNT; i++) {
irq_spinlock_lock(&(CPU->rq[i].lock), false);
if (CPU->rq[i].n == 0) {
irq_spinlock_unlock(&(CPU->rq[i].lock), false);
continue;
}
atomic_dec(&CPU->nrdy);
atomic_dec(&nrdy);
CPU->rq[i].n--;
thread_t *thread = list_get_instance(
list_first(&CPU->rq[i].rq), thread_t, rq_link);
list_remove(&thread->rq_link);
irq_spinlock_unlock(&(CPU->rq[i].lock), false);
*rq_index = i;
return thread;
}
return NULL;
}
static thread_t *find_best_thread(int *rq_index)
{
assert(interrupts_disabled());
assert(CPU != NULL);
while (true) {
thread_t *thread = try_find_thread(rq_index);
if (thread != NULL)
return thread;
CPU_LOCAL->idle = true;
cpu_interruptible_sleep();
}
}
static void switch_task(task_t *task)
{
if (TASK == task)
return;
as_t *old_as = AS;
as_t *new_as = task->as;
if (old_as != new_as)
as_switch(old_as, new_as);
if (TASK)
task_release(TASK);
TASK = task;
task_hold(TASK);
before_task_runs_arch();
}
static void relink_rq(int start)
{
assert(interrupts_disabled());
if (CPU_LOCAL->current_clock_tick < CPU_LOCAL->relink_deadline)
return;
CPU_LOCAL->relink_deadline = CPU_LOCAL->current_clock_tick + NEEDS_RELINK_MAX;
list_t list;
list_initialize(&list);
size_t n = 0;
for (int i = RQ_COUNT - 1; i > start; i--) {
irq_spinlock_lock(&CPU->rq[i].lock, false);
list_swap(&CPU->rq[i].rq, &list);
size_t tmpn = CPU->rq[i].n;
CPU->rq[i].n = n;
n = tmpn;
irq_spinlock_unlock(&CPU->rq[i].lock, false);
}
if (n != 0) {
irq_spinlock_lock(&CPU->rq[start].lock, false);
list_concat(&CPU->rq[start].rq, &list);
CPU->rq[start].n += n;
irq_spinlock_unlock(&CPU->rq[start].lock, false);
}
}
static void fpu_cleanup(void)
{
#if (defined CONFIG_FPU) && (!defined CONFIG_FPU_LAZY)
fpu_context_save(&THREAD->fpu_context);
#endif
}
static void fpu_restore(void)
{
#ifdef CONFIG_FPU_LAZY
thread_t *owner = atomic_load_explicit(&CPU->fpu_owner,
memory_order_relaxed);
if (THREAD == owner)
fpu_enable();
else
fpu_disable();
#elif defined CONFIG_FPU
fpu_enable();
if (THREAD->fpu_context_exists)
fpu_context_restore(&THREAD->fpu_context);
else {
fpu_init();
THREAD->fpu_context_exists = true;
}
#endif
}
static void prepare_to_run_thread(int rq_index)
{
relink_rq(rq_index);
switch_task(THREAD->task);
assert(atomic_get_unordered(&THREAD->cpu) == CPU);
atomic_set_unordered(&THREAD->state, Running);
atomic_set_unordered(&THREAD->priority, rq_index);
THREAD->stolen = false;
#ifdef SCHEDULER_VERBOSE
log(LF_OTHER, LVL_DEBUG,
"cpu%u: tid %" PRIu64 " (priority=%d, ticks=%" PRIu64
", nrdy=%zu)", CPU->id, THREAD->tid, rq_index,
THREAD->ticks, atomic_load(&CPU->nrdy));
#endif
before_thread_runs_arch();
#ifdef CONFIG_UDEBUG
if (atomic_get_unordered(&THREAD->btrace)) {
istate_t *istate = THREAD->udebug.uspace_state;
if (istate != NULL) {
printf("Thread %" PRIu64 " stack trace:\n", THREAD->tid);
stack_trace_istate(istate);
} else {
printf("Thread %" PRIu64 " interrupt state not available\n", THREAD->tid);
}
atomic_set_unordered(&THREAD->btrace, false);
}
#endif
fpu_restore();
uint64_t time_to_run = (rq_index + 1) * 10000;
CPU_LOCAL->preempt_deadline =
CPU_LOCAL->current_clock_tick + us2ticks(time_to_run);
THREAD->last_cycle = get_cycle();
}
static void add_to_rq(thread_t *thread, cpu_t *cpu, int i)
{
runq_t *rq = &cpu->rq[i];
irq_spinlock_lock(&rq->lock, false);
list_append(&thread->rq_link, &rq->rq);
rq->n++;
irq_spinlock_unlock(&rq->lock, false);
atomic_inc(&nrdy);
atomic_inc(&cpu->nrdy);
}
static void thread_requeue_preempted(thread_t *thread)
{
assert(interrupts_disabled());
assert(atomic_get_unordered(&thread->state) == Running);
assert(atomic_get_unordered(&thread->cpu) == CPU);
int prio = atomic_get_unordered(&thread->priority);
if (prio < RQ_COUNT - 1) {
prio++;
atomic_set_unordered(&thread->priority, prio);
}
atomic_set_unordered(&thread->state, Ready);
add_to_rq(thread, CPU, prio);
}
void thread_requeue_sleeping(thread_t *thread)
{
ipl_t ipl = interrupts_disable();
assert(atomic_get_unordered(&thread->state) == Sleeping || atomic_get_unordered(&thread->state) == Entering);
atomic_set_unordered(&thread->priority, 0);
atomic_set_unordered(&thread->state, Ready);
cpu_t *cpu = atomic_get_unordered(&thread->cpu);
if (!cpu) {
cpu = CPU;
atomic_set_unordered(&thread->cpu, CPU);
}
add_to_rq(thread, cpu, 0);
interrupts_restore(ipl);
}
static void cleanup_after_thread(thread_t *thread)
{
assert(CURRENT->mutex_locks == 0);
assert(interrupts_disabled());
int expected;
switch (atomic_get_unordered(&thread->state)) {
case Running:
thread_requeue_preempted(thread);
break;
case Exiting:
waitq_close(&thread->join_wq);
thread_put(thread);
break;
case Sleeping:
expected = SLEEP_INITIAL;
if (!atomic_compare_exchange_strong_explicit(&thread->sleep_state,
&expected, SLEEP_ASLEEP,
memory_order_acq_rel, memory_order_acquire)) {
assert(expected == SLEEP_WOKE);
thread_requeue_sleeping(thread);
}
break;
default:
panic("tid%" PRIu64 ": unexpected state %s.",
thread->tid, thread_states[atomic_get_unordered(&thread->state)]);
break;
}
}
void scheduler_enter(state_t new_state)
{
ipl_t ipl = interrupts_disable();
assert(CPU != NULL);
assert(THREAD != NULL);
if (atomic_load(&haltstate))
halt();
int rq_index;
thread_t *new_thread = try_find_thread(&rq_index);
if (new_thread == NULL && new_state == Running) {
interrupts_restore(ipl);
return;
}
atomic_set_unordered(&THREAD->state, new_state);
atomic_time_increment(&THREAD->kcycles, get_cycle() - THREAD->last_cycle);
fpu_cleanup();
after_thread_ran_arch();
if (new_thread) {
thread_t *old_thread = THREAD;
CPU_LOCAL->prev_thread = old_thread;
THREAD = new_thread;
prepare_to_run_thread(rq_index);
current_copy(CURRENT, (current_t *) new_thread->kstack);
context_swap(&old_thread->saved_context, &new_thread->saved_context);
} else {
current_copy(CURRENT, (current_t *) CPU_LOCAL->stack);
context_swap(&THREAD->saved_context, &CPU_LOCAL->scheduler_context);
}
assert(CURRENT->mutex_locks == 0);
assert(interrupts_disabled());
if (CPU_LOCAL->prev_thread) {
cleanup_after_thread(CPU_LOCAL->prev_thread);
CPU_LOCAL->prev_thread = NULL;
}
interrupts_restore(ipl);
}
void scheduler_run(void)
{
assert(interrupts_disabled());
assert(CPU != NULL);
assert(TASK == NULL);
assert(THREAD == NULL);
assert(interrupts_disabled());
while (!atomic_load(&haltstate)) {
assert(CURRENT->mutex_locks == 0);
int rq_index;
THREAD = find_best_thread(&rq_index);
prepare_to_run_thread(rq_index);
current_copy(CURRENT, (current_t *) THREAD->kstack);
context_swap(&CPU_LOCAL->scheduler_context, &THREAD->saved_context);
assert(CPU != NULL);
assert(THREAD != NULL);
assert(CURRENT->mutex_locks == 0);
assert(interrupts_disabled());
cleanup_after_thread(THREAD);
THREAD = NULL;
}
halt();
}
void thread_main_func(void)
{
assert(interrupts_disabled());
void (*f)(void *) = THREAD->thread_code;
void *arg = THREAD->thread_arg;
if (CPU_LOCAL->prev_thread) {
cleanup_after_thread(CPU_LOCAL->prev_thread);
CPU_LOCAL->prev_thread = NULL;
}
interrupts_enable();
f(arg);
thread_exit();
}
#ifdef CONFIG_SMP
static thread_t *steal_thread_from(cpu_t *old_cpu, int i)
{
runq_t *old_rq = &old_cpu->rq[i];
runq_t *new_rq = &CPU->rq[i];
ipl_t ipl = interrupts_disable();
irq_spinlock_lock(&old_rq->lock, false);
thread_t *fpu_owner = atomic_load_explicit(&old_cpu->fpu_owner,
memory_order_relaxed);
list_foreach_rev(old_rq->rq, rq_link, thread_t, thread) {
if (thread->stolen || thread->nomigrate || thread == fpu_owner) {
continue;
}
thread->stolen = true;
atomic_set_unordered(&thread->cpu, CPU);
#ifdef KCPULB_VERBOSE
log(LF_OTHER, LVL_DEBUG,
"kcpulb%u: TID %" PRIu64 " -> cpu%u, "
"nrdy=%ld, avg=%ld", CPU->id, thread->tid,
CPU->id, atomic_load(&CPU->nrdy),
atomic_load(&nrdy) / config.cpu_active);
#endif
old_rq->n--;
list_remove(&thread->rq_link);
irq_spinlock_unlock(&old_rq->lock, false);
irq_spinlock_lock(&new_rq->lock, false);
list_append(&thread->rq_link, &new_rq->rq);
new_rq->n++;
irq_spinlock_unlock(&new_rq->lock, false);
atomic_dec(&old_cpu->nrdy);
atomic_inc(&CPU->nrdy);
interrupts_restore(ipl);
return thread;
}
irq_spinlock_unlock(&old_rq->lock, false);
interrupts_restore(ipl);
return NULL;
}
void kcpulb(void *arg)
{
size_t average;
size_t rdy;
loop:
thread_sleep(1);
not_satisfied:
average = atomic_load(&nrdy) / config.cpu_active + 1;
rdy = atomic_load(&CPU->nrdy);
if (average <= rdy)
goto satisfied;
size_t count = average - rdy;
size_t acpu;
int rq;
for (rq = RQ_COUNT - 1; rq >= 0; rq--) {
for (acpu = 0; acpu < config.cpu_active; acpu++) {
cpu_t *cpu = &cpus[acpu];
if (CPU == cpu)
continue;
if (atomic_load(&cpu->nrdy) <= average)
continue;
if (steal_thread_from(cpu, rq) && --count == 0)
goto satisfied;
}
}
if (atomic_load(&CPU->nrdy)) {
thread_yield();
} else {
goto loop;
}
goto not_satisfied;
satisfied:
goto loop;
}
#endif
void sched_print_list(void)
{
size_t cpu;
for (cpu = 0; cpu < config.cpu_count; cpu++) {
if (!cpus[cpu].active)
continue;
printf("cpu%u: address=%p, nrdy=%zu\n",
cpus[cpu].id, &cpus[cpu], atomic_load(&cpus[cpu].nrdy));
unsigned int i;
for (i = 0; i < RQ_COUNT; i++) {
irq_spinlock_lock(&(cpus[cpu].rq[i].lock), false);
if (cpus[cpu].rq[i].n == 0) {
irq_spinlock_unlock(&(cpus[cpu].rq[i].lock), false);
continue;
}
printf("\trq[%u]: ", i);
list_foreach(cpus[cpu].rq[i].rq, rq_link, thread_t,
thread) {
printf("%" PRIu64 "(%s) ", thread->tid,
thread_states[atomic_get_unordered(&thread->state)]);
}
printf("\n");
irq_spinlock_unlock(&(cpus[cpu].rq[i].lock), false);
}
}
}
HelenOS homepage, sources at GitHub