Subversion Repositories c0or1k

/*
 * A basic priority-based scheduler.
 *
 * Copyright (C) 2007, 2008 Bahadir Balban
 */
#include <l4/lib/list.h>
#include <l4/lib/printk.h>
#include <l4/lib/string.h>
#include <l4/lib/mutex.h>
#include <l4/lib/math.h>
#include <l4/lib/bit.h>
#include <l4/lib/spinlock.h>
#include <l4/generic/scheduler.h>
#include <l4/generic/resource.h>
#include <l4/generic/container.h>
#include <l4/generic/preempt.h>
#include <l4/generic/thread.h>
#include <l4/generic/debug.h>
#include <l4/generic/irq.h>
#include <l4/generic/tcb.h>
#include <l4/api/errno.h>
#include <l4/api/kip.h>
#include INC_SUBARCH(mm.h)
#include INC_GLUE(mapping.h)
#include INC_GLUE(init.h)
#include INC_PLAT(platform.h)
#include INC_ARCH(exception.h)
#include INC_SUBARCH(irq.h)
 
DECLARE_PERCPU(struct scheduler, scheduler);
 
/* This is incremented on each irq or voluntarily by preempt_disable() */
DECLARE_PERCPU(extern unsigned int, current_irq_nest_count);
 
/* This ensures no scheduling occurs after voluntary preempt_disable() */
DECLARE_PERCPU(static int, voluntary_preempt);
 
void sched_lock_runqueues(struct scheduler *sched, unsigned long *irqflags)
{
	spin_lock_irq(&sched->sched_rq[0].lock, irqflags);
	spin_lock(&sched->sched_rq[1].lock);
	BUG_ON(irqs_enabled());
}
 
void sched_unlock_runqueues(struct scheduler *sched, unsigned long irqflags)
{
	spin_unlock(&sched->sched_rq[1].lock);
	spin_unlock_irq(&sched->sched_rq[0].lock, irqflags);
}
 
int preemptive()
{
	return per_cpu(current_irq_nest_count) == 0;
}
 
int preempt_count()
{
	return per_cpu(current_irq_nest_count);
}
 
#if !defined(CONFIG_PREEMPT_DISABLE)
 
void preempt_enable(void)
{
	per_cpu(voluntary_preempt)--;
	per_cpu(current_irq_nest_count)--;
}
 
/* A positive irq nest count implies current context cannot be preempted. */
void preempt_disable(void)
{
	per_cpu(current_irq_nest_count)++;
	per_cpu(voluntary_preempt)++;
}
 
#else /* End of !CONFIG_PREEMPT_DISABLE */
 
void preempt_enable(void) { }
void preempt_disable(void) { }
 
#endif /* CONFIG_PREEMPT_DISABLE */
 
int in_irq_context(void)
{
	/*
	 * If there was a real irq, irq nest count must be
	 * one more than all preempt_disable()'s which are
	 * counted by voluntary_preempt.
	 */
	return (per_cpu(current_irq_nest_count) ==
	        (per_cpu(voluntary_preempt) + 1));
}
 
int in_nested_irq_context(void)
{
	/* Deducing voluntary preemptions we get real irq nesting */
	return (per_cpu(current_irq_nest_count) -
		per_cpu(voluntary_preempt)) > 1;
}
 
int in_process_context(void)
{
	return !in_irq_context();
}
 
void sched_init_runqueue(struct scheduler *sched, struct runqueue *rq)
{
	link_init(&rq->task_list);
	spin_lock_init(&rq->lock);
	rq->sched = sched;
}
 
void sched_init()
{
	struct scheduler *sched = &per_cpu(scheduler);
 
	for (int i = 0; i < SCHED_RQ_TOTAL; i++)
		sched_init_runqueue(sched, &sched->sched_rq[i]);
 
	sched->rq_runnable = &sched->sched_rq[0];
	sched->rq_expired = &sched->sched_rq[1];
	sched->rq_rt_runnable = &sched->sched_rq[2];
	sched->rq_rt_expired = &sched->sched_rq[3];
	sched->prio_total = TASK_PRIO_TOTAL;
	sched->idle_task = current;
}
 
/* Swap runnable and expired runqueues. */
static void sched_rq_swap_queues(void)
{
	struct runqueue *temp;
 
	BUG_ON(list_empty(&per_cpu(scheduler).rq_expired->task_list));
 
	/* Queues are swapped and expired list becomes runnable */
	temp = per_cpu(scheduler).rq_runnable;
	per_cpu(scheduler).rq_runnable = per_cpu(scheduler).rq_expired;
	per_cpu(scheduler).rq_expired = temp;
}
 
static void sched_rq_swap_rtqueues(void)
{
	struct runqueue *temp;
 
	BUG_ON(list_empty(&per_cpu(scheduler).rq_rt_expired->task_list));
 
	/* Queues are swapped and expired list becomes runnable */
	temp = per_cpu(scheduler).rq_rt_runnable;
	per_cpu(scheduler).rq_rt_runnable = per_cpu(scheduler).rq_rt_expired;
	per_cpu(scheduler).rq_rt_expired = temp;
}
 
/* Set policy on where to add tasks in the runqueue */
#define RQ_ADD_BEHIND		0
#define RQ_ADD_FRONT		1
 
/* Helper for adding a new task to a runqueue */
static void sched_rq_add_task(struct ktcb *task, struct runqueue *rq, int front)
{
	unsigned long irqflags;
	struct scheduler *sched =
		&per_cpu_byid(scheduler, task->affinity);
 
	BUG_ON(!list_empty(&task->rq_list));
 
	/* Lock that particular cpu's runqueue set */
	sched_lock_runqueues(sched, &irqflags);
	if (front)
		list_insert(&task->rq_list, &rq->task_list);
	else
		list_insert_tail(&task->rq_list, &rq->task_list);
	rq->total++;
	task->rq = rq;
 
	/* Unlock that particular cpu's runqueue set */
	sched_unlock_runqueues(sched, irqflags);
}
 
/* Helper for removing a task from its runqueue. */
static inline void sched_rq_remove_task(struct ktcb *task)
{
	unsigned long irqflags;
	struct scheduler *sched =
		&per_cpu_byid(scheduler, task->affinity);
 
	sched_lock_runqueues(sched, &irqflags);
 
	/*
	 * We must lock both, otherwise rqs may swap and
	 * we may get the wrong rq.
	 */
	BUG_ON(list_empty(&task->rq_list));
	list_remove_init(&task->rq_list);
 
	task->rq->total--;
	BUG_ON(task->rq->total < 0);
	task->rq = 0;
 
	sched_unlock_runqueues(sched, irqflags);
}
 
static inline void
sched_run_task(struct ktcb *task, struct scheduler *sched)
{
	if (task->flags & TASK_REALTIME)
		sched_rq_add_task(task, sched->rq_rt_runnable,
				  RQ_ADD_BEHIND);
	else
		sched_rq_add_task(task, sched->rq_runnable,
				  RQ_ADD_BEHIND);
}
 
static inline void
sched_expire_task(struct ktcb *task, struct scheduler *sched)
{
 
	if (task->flags & TASK_REALTIME)
		sched_rq_add_task(current, sched->rq_rt_expired,
				  RQ_ADD_BEHIND);
	else
		sched_rq_add_task(current, sched->rq_expired,
				  RQ_ADD_BEHIND);
}
 
void sched_init_task(struct ktcb *task, int prio)
{
	link_init(&task->rq_list);
	task->priority = prio;
	task->ticks_left = 0;
	task->state = TASK_INACTIVE;
	task->ts_need_resched = 0;
	task->flags |= TASK_RESUMING;
}
 
/* Synchronously resumes a task */
void sched_resume_sync(struct ktcb *task)
{
	BUG_ON(task == current);
	task->state = TASK_RUNNABLE;
	sched_run_task(task, &per_cpu_byid(scheduler, task->affinity));
	schedule();
}
 
/*
 * Asynchronously resumes a task.
 * The task will run in the future, but at
 * the scheduler's discretion. It is possible that current
 * task wakes itself up via this function in the scheduler().
 */
void sched_resume_async(struct ktcb *task)
{
	task->state = TASK_RUNNABLE;
	sched_run_task(task, &per_cpu_byid(scheduler, task->affinity));
}
 
/*
 * Takes all the action that will make a task sleep
 * in the scheduler. If the task is woken up before
 * it schedules, then operations here are simply
 * undone and task remains as runnable.
 */
void sched_prepare_sleep()
{
	preempt_disable();
	sched_rq_remove_task(current);
	current->state = TASK_SLEEPING;
	preempt_enable();
}
 
/*
 * preempt_enable/disable()'s are for avoiding the
 * entry to scheduler during this period - but this
 * is only true for current cpu.
 */
void sched_suspend_sync(void)
{
	preempt_disable();
	sched_rq_remove_task(current);
	current->state = TASK_INACTIVE;
	current->flags &= ~TASK_SUSPENDING;
 
	if (current->pagerid != current->tid)
		wake_up(&current->wqh_pager, 0);
	preempt_enable();
 
	schedule();
}
 
void sched_suspend_async(void)
{
	preempt_disable();
	sched_rq_remove_task(current);
	current->state = TASK_INACTIVE;
	current->flags &= ~TASK_SUSPENDING;
 
	if (current->pagerid != current->tid)
		wake_up(&current->wqh_pager, 0);
	preempt_enable();
 
	need_resched = 1;
}
 
 
extern void arch_context_switch(struct ktcb *cur, struct ktcb *next);
 
static inline void context_switch(struct ktcb *next)
{
	struct ktcb *cur = current;
 
//	printk("Core:%d (%d) to (%d)\n", smp_get_cpuid(), cur->tid, next->tid);
 
	system_account_context_switch();
 
	/* Flush caches and everything */
	BUG_ON(!current);
	BUG_ON(!current->space);
	BUG_ON(!next);
	BUG_ON(!next->space);
	BUG_ON(!next->space);
	if (current->space->spid != next->space->spid)
		arch_space_switch(next);
 
	/* Update utcb region for next task */
	task_update_utcb(next);
 
	/* Switch context */
	arch_context_switch(cur, next);
 
	// printk("Returning from yield. Tid: (%d)\n", cur->tid);
}
 
/*
 * Priority calculation is so simple it is inlined. The task gets
 * the ratio of its priority to total priority of all runnable tasks.
 */
static inline int sched_recalc_ticks(struct ktcb *task, int prio_total)
{
	BUG_ON(prio_total < task->priority);
	BUG_ON(prio_total == 0);
	return task->ticks_assigned =
		CONFIG_SCHED_TICKS * task->priority / prio_total;
}
 
/*
 * Select a real-time task 1/8th of any one selection
 */
static inline int sched_select_rt(struct scheduler *sched)
{
	int ctr = sched->task_select_ctr++ & 0xF;
 
	if (ctr == 0 || ctr == 8 || ctr == 15)
		return 0;
	else
		return 1;
}
 
/*
 * Selection happens as follows:
 *
 * A real-time task is chosen %87.5 of the time. This is evenly
 * distributed to a given interval.
 *
 * Idle task is run once when it is explicitly suggested (e.g.
 * for cleanup after a task exited) but only when no real-time
 * tasks are in the queues.
 *
 * And idle task is otherwise run only when no other tasks are
 * runnable.
 */
struct ktcb *sched_select_next(void)
{
	struct scheduler *sched = &per_cpu(scheduler);
	int realtime = sched_select_rt(sched);
	struct ktcb *next = 0;
 
	for (;;) {
 
		/* Decision to run an RT task? */
		if (realtime && sched->rq_rt_runnable->total > 0) {
			/* Get a real-time task, if available */
			next = link_to_struct(sched->rq_rt_runnable->task_list.next,
					      struct ktcb, rq_list);
			break;
		} else if (realtime && sched->rq_rt_expired->total > 0) {
			/* Swap real-time queues */
			sched_rq_swap_rtqueues();
			/* Get a real-time task */
			next = link_to_struct(sched->rq_rt_runnable->task_list.next,
					      struct ktcb, rq_list);
			break;
		/* Idle flagged for run? */
		} else if (sched->flags & SCHED_RUN_IDLE) {
			/* Clear idle flag */
			sched->flags &= ~SCHED_RUN_IDLE;
			next = sched->idle_task;
			break;
		} else if (sched->rq_runnable->total > 0) {
			/* Get a regular runnable task, if available */
			next = link_to_struct(sched->rq_runnable->task_list.next,
					      struct ktcb, rq_list);
			break;
		} else if (sched->rq_expired->total > 0) {
			/* Swap queues and retry if not */
			sched_rq_swap_queues();
			next = link_to_struct(sched->rq_runnable->task_list.next,
					      struct ktcb, rq_list);
			break;
		} else if (in_process_context()) {
			/* No runnable task. Do idle if in process context */
			next = sched->idle_task;
			break;
		} else {
			/*
			 * Nobody is runnable. Irq calls must return
			 * to interrupted current process to run idle task
			 */
			next = current;
			break;
		}
	}
	return next;
}
 
/* Prepare next runnable task right before switching to it */
void sched_prepare_next(struct ktcb *next)
{
	/* New tasks affect runqueue total priority. */
	if (next->flags & TASK_RESUMING)
		next->flags &= ~TASK_RESUMING;
 
	/* Zero ticks indicates task hasn't ran since last rq swap */
	if (next->ticks_left == 0) {
		/*
		 * Redistribute timeslice. We do this as each task
		 * becomes runnable rather than all at once. It is done
		 * every runqueue swap
		 */
		sched_recalc_ticks(next, per_cpu(scheduler).prio_total);
		next->ticks_left = next->ticks_assigned;
	}
 
	/* Reinitialise task's schedule granularity boundary */
	next->sched_granule = SCHED_GRANULARITY;
}
 
/*
 * Tasks come here, either by setting need_resched (via next irq),
 * or by directly calling it (in process context).
 *
 * The scheduler is similar to Linux's so called O(1) scheduler,
 * although a lot simpler. Task priorities determine task timeslices.
 * Each task gets a ratio of its priority to the total priority of
 * all runnable tasks. When this total changes, (e.g. threads die or
 * are created, or a thread's priority is changed) the timeslices are
 * recalculated on a per-task basis as each thread becomes runnable.
 * Once all runnable tasks expire, runqueues are swapped. Sleeping
 * tasks are removed from the runnable queue, and added back later
 * without affecting the timeslices. Suspended tasks however,
 * necessitate a timeslice recalculation as they are considered to go
 * inactive indefinitely or for a very long time. They are put back
 * to the expired queue if they want to run again.
 *
 * A task is rescheduled either when it hits a SCHED_GRANULARITY
 * boundary, or when its timeslice has expired. SCHED_GRANULARITY
 * ensures context switches do occur at a maximum boundary even if a
 * task's timeslice is very long. In the future, real-time tasks will
 * be added, and they will be able to ignore SCHED_GRANULARITY.
 *
 * In the future, the tasks will be sorted by priority in their
 * runqueue, as well as having an adjusted timeslice.
 *
 * Runqueues are swapped at a single second's interval. This implies
 * the timeslice recalculations would also occur at this interval.
 */
void schedule()
{
	struct ktcb *next;
 
	/* Should not schedule with preemption
	 * disabled or in nested irq */
	BUG_ON(per_cpu(voluntary_preempt));
	BUG_ON(in_nested_irq_context());
 
	/* Should not have more ticks than SCHED_TICKS */
	BUG_ON(current->ticks_left > CONFIG_SCHED_TICKS);
 
	/* If coming from process path, cannot have
	 * any irqs that schedule after this */
	preempt_disable();
 
	/* Reset schedule flag */
	need_resched = 0;
 
	/* Remove from runnable and put into appropriate runqueue */
	if (current->state == TASK_RUNNABLE) {
		sched_rq_remove_task(current);
		if (current->ticks_left)
			sched_run_task(current, &per_cpu(scheduler));
		else
			sched_expire_task(current, &per_cpu(scheduler));
	}
 
	/*
	 * FIXME: Are these smp-safe? BB: On first glance they
	 * should be because runqueues are per-cpu right now.
	 *
	 * If task is about to sleep and
	 * it has pending events, wake it up.
	 */
	if ((current->flags & TASK_PENDING_SIGNAL) &&
	    current->state == TASK_SLEEPING)
		wake_up_task(current, WAKEUP_INTERRUPT);
 
	/*
	 * If task has pending events, and is in userspace
	 * (guaranteed to have no unfinished jobs in kernel)
	 * handle those events
	 */
	if ((current->flags & TASK_PENDING_SIGNAL) &&
	    current->state == TASK_RUNNABLE &&
	    TASK_IN_USER(current)) {
		if (current->flags & TASK_SUSPENDING)
			sched_suspend_async();
	}
 
	/* Hint scheduler to run idle asap to free task */
	if (current->flags & TASK_EXITED) {
		current->flags &= ~TASK_EXITED;
		per_cpu(scheduler).flags |= SCHED_RUN_IDLE;
	}
 
	/* Decide on next runnable task */
	next = sched_select_next();
 
	/* Prepare next task for running */
	sched_prepare_next(next);
 
	/* Finish */
	disable_irqs();
	preempt_enable();
	context_switch(next);
}
 
/*
 * Start the timer and switch to current task
 * for first-ever scheduling.
 */
void scheduler_start()
{
	platform_timer_start();
	switch_to_user(current);
}