path: root/kernel/sched_gsn_edf.c

/*
 * kernel/sched_gsn_edf.c
 *
 * Implementation of the GSN-EDF scheduling algorithm.
 *
 * This version uses the simple approach and serializes all scheduling
 * decisions by the use of a queue lock. This is probably not the
 * best way to do it, but it should suffice for now. It should not
 * affect the benchmarks since all synchronization primitives will
 * take the same performance hit, if any.
 */

#include <linux/percpu.h>
#include <linux/sched.h>
#include <linux/list.h>

#include <linux/queuelock.h>
#include <linux/litmus.h>
#include <linux/sched_plugin.h>
#include <linux/edf_common.h>
#include <linux/sched_trace.h>

int in_gsnedf_schedule[NR_CPUS] = {0, 0, 0, 0};
int in_gsnedf_scheduler_tick[NR_CPUS] = {0, 0, 0, 0};
int in_gsnedf_finish_switch[NR_CPUS] = {0, 0, 0, 0};

/* cpu_entry_t - maintain the linked and scheduled state
 */
typedef struct  {
	int 			cpu;
	struct task_struct*	linked;		/* only RT tasks */
	struct task_struct*	scheduled;	/* only RT tasks */
	struct list_head	list;
	atomic_t		will_schedule;	/* prevent unneeded IPIs */
} cpu_entry_t;
DEFINE_PER_CPU(cpu_entry_t, gsnedf_cpu_entries);

#define set_will_schedule() \
	(atomic_set(&__get_cpu_var(gsnedf_cpu_entries).will_schedule, 1))
#define clear_will_schedule() \
	(atomic_set(&__get_cpu_var(gsnedf_cpu_entries).will_schedule, 0))
#define test_will_schedule(cpu) \
	(atomic_read(&per_cpu(gsnedf_cpu_entries, cpu).will_schedule))


#define NO_CPU 0xffffffff

/* The gsnedf_lock is used to serialize all scheduling events.
 * It protects
 */
static queuelock_t gsnedf_lock;
/* the cpus queue themselves according to priority in here */
static LIST_HEAD(gsnedf_cpu_queue);

static edf_domain_t gsnedf;


/* update_cpu_position - Move the cpu entry to the correct place to maintain 
 *                       order in the cpu queue. Caller must hold gsnedf lock.
 */
static void update_cpu_position(cpu_entry_t *entry) 
{
	cpu_entry_t *other;
	struct list_head *pos;
	list_del(&entry->list);
	/* if we do not execute real-time jobs we just move 
	 * to the end of the queue 
	 */
	if (entry->linked) {
		list_for_each(pos, &gsnedf_cpu_queue) {
			other = list_entry(pos, cpu_entry_t, list);
			if (edf_higher_prio(entry->linked, other->linked)) {
				__list_add(&entry->list, pos->prev, pos);
				return;
			}
		}		
	}
	/* if we get this far we have the lowest priority job */
	list_add_tail(&entry->list, &gsnedf_cpu_queue);
}

/* link_task_to_cpu - Update the link of a CPU.
 *                    Handles the case where the to-be-linked task is already
 *                    scheduled on a different CPU.
 */
static noinline void link_task_to_cpu(struct task_struct* linked,
			     cpu_entry_t *entry)
			     
{
	cpu_entry_t *sched;
	struct task_struct* tmp;
	int on_cpu;

	BUG_ON(linked && !is_realtime(linked));

	/* Currently linked task is set to be unlinked. */
	if (entry->linked) {
		entry->linked->rt_param.linked_on = NO_CPU;
	}

	/* Link new task to CPU. */
	if (linked) {		
		set_rt_flags(linked, RT_F_RUNNING);
		/* handle task is already scheduled somewhere! */
		on_cpu = linked->rt_param.scheduled_on;
		if (on_cpu != NO_CPU) {
			sched = &per_cpu(gsnedf_cpu_entries, on_cpu);
			/* this should only happen if not linked already */
			BUG_ON(sched->linked == linked);
			
			/* If we are already scheduled on the CPU to which we
			 * wanted to link, we don't need to do the swap --
			 * we just link ourselves to the CPU and depend on
			 * the caller to get things right.
			 */
			if (entry != sched) {
				tmp = sched->linked;
				linked->rt_param.linked_on = sched->cpu;
				sched->linked = linked;
				update_cpu_position(sched);
				linked = tmp;
			}
		}
		if (linked) /* might be NULL due to swap */
			linked->rt_param.linked_on = entry->cpu;
	}
	entry->linked = linked;
	update_cpu_position(entry);
}

/* unlink - Make sure a task is not linked any longer to an entry
 *          where it was linked before. Must hold gsnedf_lock.
 */
static noinline void unlink(struct task_struct* t)
{
    	cpu_entry_t *entry;

	BUG_ON(!t);

	if (t->rt_param.linked_on != NO_CPU) {
		/* unlink */
		entry = &per_cpu(gsnedf_cpu_entries, t->rt_param.linked_on);
		t->rt_param.linked_on = NO_CPU;
		link_task_to_cpu(NULL, entry);
	} else if (in_list(&t->rt_list)) {
		/* This is an interesting situation: t is scheduled,
		 * but was just recently unlinked.  It cannot be
		 * linked anywhere else (because then it would have
		 * been relinked to this CPU), thus it must be in some
		 * queue. We must remove it from the list in this
		 * case.
		 */
		list_del(&t->rt_list);
	}
} 


/* preempt - force a CPU to reschedule
 */
static noinline void preempt(cpu_entry_t *entry)
{
	if (entry->scheduled && is_np(entry->scheduled))
		return;
	if (smp_processor_id() == entry->cpu)
		set_tsk_need_resched(current);
	else
		if (!test_will_schedule(entry->cpu))
			smp_send_reschedule(entry->cpu);
}

/* requeue - Put an unlinked task into gsn-edf domain.
 *           Caller must hold gsnedf_lock.
 */
static noinline void requeue(struct task_struct* task)
{
	BUG_ON(!task);
	/* sanity check rt_list before insertion */
	BUG_ON(in_list(&task->rt_list));

	if (get_rt_flags(task) == RT_F_SLEEP || 
	    get_rt_mode() != MODE_RT_RUN) {
		/* this task has expired
		 * _schedule has already taken care of updating 
		 * the release and
		 * deadline. We just must check if it has been released.
		 */
		if (is_released(task) && get_rt_mode() == MODE_RT_RUN)
			__add_ready(&gsnedf, task);
		else { 
			/* it has got to wait */
			__add_release(&gsnedf, task);
		}

	} else 
		/* this is a forced preemption 
		 * thus the task stays in the ready_queue
		 * we only must make it available to others
		 */
		__add_ready(&gsnedf, task);
}

/* gsnedf_job_arrival: task is either resumed or released */
static noinline void gsnedf_job_arrival(struct task_struct* task)
{
	cpu_entry_t* last;

	BUG_ON(list_empty(&gsnedf_cpu_queue));
	BUG_ON(!task);

	/* first queue arriving job */
	requeue(task);

	/* then check for any necessary preemptions */
	last = list_entry(gsnedf_cpu_queue.prev, cpu_entry_t, list);
	if (preemption_needed(&gsnedf, last->linked)) {
		/* preemption necessary */
		task = __take_ready(&gsnedf);
		TRACE("job_arrival: task %d linked to %d\n", task->pid, last->cpu);
		if (last->linked)
			requeue(last->linked);
		
		link_task_to_cpu(task, last);
		preempt(last);
	}
}

/* check for current job releases */
static noinline  void gsnedf_release_jobs(void)
{
	struct list_head *pos, *save;
	struct task_struct   *queued;

	list_for_each_safe(pos, save, &gsnedf.release_queue) {
		queued = list_entry(pos, struct task_struct, rt_list);
		if (likely(is_released(queued))) {
			/* this one is ready to go*/
			list_del(pos);
			set_rt_flags(queued, RT_F_RUNNING);
			
			sched_trace_job_release(queued);
			gsnedf_job_arrival(queued);
		} 
		else
			/* the release queue is ordered */
			break;			
	}
}

/* gsnedf_scheduler_tick - this function is called for every local timer 
 *                       interrupt.
 *
 *                   checks whether the current task has expired and checks
 *                   whether we need to preempt it if it has not expired
 */
static reschedule_check_t gsnedf_scheduler_tick(void)
{
	unsigned long 		flags;
	struct task_struct*	t = current;
	reschedule_check_t 	want_resched = NO_RESCHED;
	cpu_entry_t* 		entry = &__get_cpu_var(gsnedf_cpu_entries);

	/* debug */
	in_gsnedf_scheduler_tick[smp_processor_id()] = 1;

	/* expire tasks even if not in real-time mode
	 * this makes sure that at the end of real-time mode
	 * no task  "runs away forever".
	 */
	if (is_realtime(t))
		TRACE_TASK(t, "scheduler tick\n");

	if (is_realtime(t) && t->time_slice && !--t->time_slice) {
		if (!is_np(t)) { /* np tasks will be preempted when they become
				    preemptable again */
			set_rt_flags(t, RT_F_SLEEP);
			want_resched = FORCE_RESCHED;
			set_will_schedule();
			sched_trace_job_completion(t);
			/* prepare for next period */
			prepare_for_next_period(t);	
			queue_lock_irqsave(&gsnedf_lock, flags);
			/* unlink */
			unlink(t);
			/* requeue */
			gsnedf_job_arrival(t);
			queue_unlock_irqrestore(&gsnedf_lock, flags);
		} else
			TRACE("gsnedf_scheduler_tick: "
			      "%d is non-preemptable, "
			      "preemption delayed.\n", t->pid);			
		
	} 
	if (get_rt_mode() == MODE_RT_RUN) {
		in_gsnedf_scheduler_tick[smp_processor_id()] = 666;

		queue_lock_irqsave(&gsnedf_lock, flags);
		
		/* (1) try to release pending jobs */
		gsnedf_release_jobs();

		/* (2) check if we need to reschedule */
		if (entry->linked != entry->scheduled && 
		    (!entry->scheduled || !is_np(entry->scheduled))) {
			want_resched = FORCE_RESCHED;
			set_will_schedule(); 
		}
		queue_unlock_irqrestore(&gsnedf_lock, flags);		
	}

	/* debug */
	in_gsnedf_scheduler_tick[smp_processor_id()] = 0;

	return want_resched;
}

/* This is main Global EDF schedule function
 * 
 * Assumes the caller holds the lock for rq and that irqs are disabled
 */
static int gsnedf_schedule(struct task_struct * prev, 
			 struct task_struct ** next, 
			 runqueue_t * rq)
{
	cpu_entry_t* 	entry = &__get_cpu_var(gsnedf_cpu_entries);

	in_gsnedf_schedule[smp_processor_id()] = 1;

	/* will be released in finish_switch */
	queue_lock(&gsnedf_lock);
	clear_will_schedule();

	/* (1) check for blocking jobs */
	if (prev == entry->linked && 
	    (get_rt_mode() != MODE_RT_RUN || !is_running(prev))) {
		link_task_to_cpu(NULL, entry);
	}

	/* (2) if not linked then get rt task */	
	if (get_rt_mode() == MODE_RT_RUN && !entry->linked) {
		link_task_to_cpu(__take_ready(&gsnedf), entry);
	}

	/* (3) if linked different from scheduled 
	 *     select linked as next
	 */ 
	BUG_ON(entry->scheduled && entry->scheduled != prev);
	if (entry->linked != entry->scheduled) {
		/* do we need to take care of a previously scheduled
		 * job? */
		if (entry->scheduled) {
			BUG_ON(!is_realtime(prev));
			if (prev->array)
				/* take it out of the run queue */
				deactivate_task(prev, rq);
		}
		/* do we need to schedule a linked job? */
		if (entry->linked) {
			*next = entry->linked;
			/* mark the task as executing on this cpu */
			set_task_cpu(*next, smp_processor_id());
			/* stick the task into the runqueue */
			__activate_task(*next, rq);
		}
	} else
		*next = entry->linked;

	/* unlock in case that we don't affect real-time tasks or
	 * if nothing changed and finish_switch won't be called 
	 */
	if (prev == *next || (!is_realtime(prev) && !*next))
		queue_unlock(&gsnedf_lock);

	in_gsnedf_schedule[smp_processor_id()] = 0;

	return 0;
}


/* _finish_switch - we just finished the switch away from prev
 */
static void gsnedf_finish_switch(struct task_struct *prev) 
{
	cpu_entry_t* 	entry = &__get_cpu_var(gsnedf_cpu_entries);

	in_gsnedf_finish_switch[smp_processor_id()] = 1;

	if (is_realtime(current))
		entry->scheduled = current;		
	else
		entry->scheduled = NULL;

	prev->rt_param.scheduled_on    = NO_CPU;
	current->rt_param.scheduled_on = smp_processor_id();

	/* unlock in case schedule() left it locked */
	if (is_realtime(current) || is_realtime(prev))
			queue_unlock(&gsnedf_lock);
	

	in_gsnedf_finish_switch[smp_processor_id()] = 0;
}


/*	Prepare a task for running in RT mode
 *	Enqueues the task into master queue data structure
 *	returns 
 *		-EPERM  if task is not TASK_STOPPED
 */
static long gsnedf_prepare_task(struct task_struct * t)
{
	unsigned long 		flags;
	TRACE("gsn edf: prepare task %d\n", t->pid);

	if (t->state == TASK_STOPPED) {
		__setscheduler(t, SCHED_FIFO, MAX_RT_PRIO - 1);

		t->rt_param.scheduled_on       = NO_CPU;
		t->rt_param.linked_on          = NO_CPU;
		t->rt_param.is_non_preemptable = 0;
		if (get_rt_mode() == MODE_RT_RUN)
			/* The action is already on. 
			 * Prepare immediate release
			 */
			prepare_new_release(t);
		/* The task should be running in the queue, otherwise signal 
		 * code will try to wake it up with fatal consequences.
		 */
		t->state = TASK_RUNNING; 
		
		queue_lock_irqsave(&gsnedf_lock, flags);
		requeue(t);
		queue_unlock_irqrestore(&gsnedf_lock, flags);		
		return 0;
	}
	else
		return -EPERM;
}

static void gsnedf_wake_up_task(struct task_struct *task) 
{
	unsigned long flags;
	/* We must determine whether task should go into the release 	   
	 * queue or into the ready queue. It may enter the ready queue 
	 * if it has credit left in its time slice and has not yet reached 
	 * its deadline. If it is now passed its deadline we assume this the 
	 * arrival of a new sporadic job and thus put it in the ready queue 
	 * anyway.If it has zero budget and the next release is in the future 
	 * it has to go to the release queue.
	 */
	TRACE("gsnedf: %d unsuspends with budget=%d\n", 
	      task->pid, task->time_slice);
	task->state = TASK_RUNNING;

	/* We need to take suspensions because of semaphores into
	 * account! If a job resumes after being suspended due to acquiring
	 * a semaphore, it should never be treated as a new job release.
	 */
	if (get_rt_flags(task) == RT_F_EXIT_SEM) {
		set_rt_flags(task, RT_F_RUNNING);
	} else {
		if (is_tardy(task)) {
			/* new sporadic release */
			prepare_new_release(task);
 			sched_trace_job_release(task);
		}
		else if (task->time_slice)
			/* came back in time before deadline
			 */
			set_rt_flags(task, RT_F_RUNNING);
	}

	queue_lock_irqsave(&gsnedf_lock, flags);
	gsnedf_job_arrival(task);
	queue_unlock_irqrestore(&gsnedf_lock, flags);	
}

static void gsnedf_task_blocks(struct task_struct *t)
{
	unsigned long flags;

	/* unlink if necessary */
	queue_lock_irqsave(&gsnedf_lock, flags);
	unlink(t);
	queue_unlock_irqrestore(&gsnedf_lock, flags);

	BUG_ON(!is_realtime(t));
	TRACE("task %d suspends with budget=%d\n", t->pid, t->time_slice);
	BUG_ON(t->rt_list.next != LIST_POISON1);
	BUG_ON(t->rt_list.prev != LIST_POISON2);
}


/* When _tear_down is called, the task should not be in any queue any more
 * as it must have blocked first. We don't have any internal state for the task,
 * it is all in the task_struct.
 */
static long gsnedf_tear_down(struct task_struct * t)
{
	BUG_ON(!is_realtime(t));
        TRACE_TASK(t, "tear down called");
	BUG_ON(t->array);
	BUG_ON(t->rt_list.next != LIST_POISON1);
	BUG_ON(t->rt_list.prev != LIST_POISON2);
	return 0;
}


static long gsnedf_enter_np(struct task_struct * t)
{
	unsigned long 		flags;

	queue_lock_irqsave(&gsnedf_lock, flags);
	t->rt_param.is_non_preemptable++;
	queue_unlock_irqrestore(&gsnedf_lock, flags);
	return 0;
}

static long gsnedf_exit_np(struct task_struct * t)
{
	unsigned long 		flags;
	int ret = 0;
	cpu_entry_t *entry;

	queue_lock_irqsave(&gsnedf_lock, flags);
	if (is_np(t)) {
		t->rt_param.is_non_preemptable--;
		entry = &__get_cpu_var(gsnedf_cpu_entries);
		if (!is_np(t) && (!t->time_slice ||  entry->linked != t)) {
			BUG_ON(t != entry->scheduled);			
			/* t is now preemptable and not linked */
			set_will_schedule();
			if (!t->time_slice) {
				set_rt_flags(t, RT_F_SLEEP);
				sched_trace_job_completion(t);
				/* prepare for next period */
				prepare_for_next_period(t);	
			}
			/* unlink */
			unlink(t);
			/* requeue */
			gsnedf_job_arrival(t);
			/* reschedule if necessary */
			if (entry->linked != entry->scheduled) {
				TRACE("gsnedf_exit_np: delayed "
				      "preemption of %d\n",
				      t->pid);
				set_tsk_need_resched(current);
			} else
				TRACE("gsnedf_exit_np: no preemption-necessary, "
				      " %s/%d got relinked\n",  
				      entry->scheduled->comm, 
				      entry->scheduled->pid);
		}
	} else 
		ret = -EPERM;
	queue_unlock_irqrestore(&gsnedf_lock, flags);
	return ret;
}

static long gsnedf_pi_block(struct pi_semaphore *sem,
			    struct task_struct *new_waiter)
{
	/* This callback has to handle the situation where a new waiter is 
	 * added to the wait queue of the semaphore.
	 * 
	 * We must check if has a higher priority than the currently 
	 * highest-priority task, and then potentially reschedule.
	 */

	BUG_ON(!new_waiter);

	if (edf_higher_prio(new_waiter, sem->hp.task)) {
		TRACE_TASK(new_waiter, " boosts priority\n");
		/* called with IRQs disabled */
		queue_lock(&gsnedf_lock);
		/* store new highest-priority task */
		sem->hp.task = new_waiter;
		if (sem->holder) {
			/* let holder inherit */
			sem->holder->rt_param.inh_task = new_waiter;
			unlink(sem->holder);
			gsnedf_job_arrival(sem->holder);
		}
		queue_unlock(&gsnedf_lock);	
	}

	return 0;
}

static long gsnedf_inherit_priority(struct pi_semaphore *sem,
				    struct task_struct *new_owner)
{
	/* We don't need to acquire the gsnedf_lock since at the time of this
	 * call new_owner isn't actually scheduled yet (it's still sleeping) 
	 * and since the calling function already holds sem->wait.lock, which 
	 * prevents concurrent sem->hp.task changes.
	 */

	if (sem->hp.task && sem->hp.task != new_owner) {	
		new_owner->rt_param.inh_task = sem->hp.task;
		TRACE_TASK(new_owner, "inherited priority from %s/%d\n", 
			   sem->hp.task->comm, sem->hp.task->pid);
	} else
		TRACE_TASK(new_owner, 
			   "cannot inherit priority, "
			   "no higher priority job waits.\n");
	return 0;
}

/* This function is called on a semaphore release, and assumes that
 * the current task is also the semaphore holder.
 */
static long gsnedf_return_priority(struct pi_semaphore *sem)
{
	struct task_struct* t = current;
	int ret = 0;

        /* Find new highest-priority semaphore task
	 * if holder task is the current hp.task.
	 *
	 * Calling function holds sem->wait.lock.
	 */
	if (t == sem->hp.task)
		edf_set_hp_task(sem);

	TRACE_CUR("gsnedf_return_priority for lock %p\n", sem);

	if (t->rt_param.inh_task) {
		/* interrupts already disabled by PI code */
		queue_lock(&gsnedf_lock);
		
		/* Reset inh_task to NULL. */
		t->rt_param.inh_task = NULL;
		
		/* Check if rescheduling is necessary */
		unlink(t);
		gsnedf_job_arrival(t);
		queue_unlock(&gsnedf_lock);
	}	

	return ret;
}

/*
 *	Deactivate current task until the beginning of the next period.
 */
static  long gsnedf_sleep_next_period(void)
{
	unsigned long flags;
	struct task_struct* t = current;

	queue_lock_irqsave(&gsnedf_lock, flags);

	/* Mark that we do not excute anymore */
	set_rt_flags(t, RT_F_SLEEP);
	sched_trace_job_completion(t);
	/* prepare for next period */
	prepare_for_next_period(t);	

        /* unlink */
	unlink(t);
	/* requeue */
	gsnedf_job_arrival(t);

	/* will reschedule on return to user mode */
	set_tsk_need_resched(t);

	queue_unlock_irqrestore(&gsnedf_lock, flags);

	return 0;
}


static int gsnedf_mode_change(int new_mode)
{
	unsigned long flags;
	int cpu;
	cpu_entry_t *entry;

	if (new_mode == MODE_RT_RUN) {
		queue_lock_irqsave(&gsnedf_lock, flags);

		__prepare_new_releases(&gsnedf, jiffies + 10);

		/* get old cruft out of the way in case we reenter real-time
		 * mode for a second time
		 */
		while (!list_empty(&gsnedf_cpu_queue))
			list_del(gsnedf_cpu_queue.next);
		/* reinitialize */
		for_each_online_cpu(cpu) {
			entry = &per_cpu(gsnedf_cpu_entries, cpu);
			atomic_set(&entry->will_schedule, 0);
			entry->linked    = NULL;
			entry->scheduled = NULL;
			list_add(&entry->list, &gsnedf_cpu_queue);
		}		

		queue_unlock_irqrestore(&gsnedf_lock, flags);

	}
	return 0;
}


/*	Plugin object	*/
static sched_plugin_t s_plugin __cacheline_aligned_in_smp = {
	.ready_to_use = 0 
};


/*
 *	Plugin initialization code.
 */
#define INIT_SCHED_PLUGIN (struct sched_plugin){		\
	.plugin_name		= "GSN-EDF",			\
	.ready_to_use		= 1,				\
	.algo_scheduler_tick	= gsnedf_scheduler_tick,	\
	.scheduler_tick		= rt_scheduler_tick,		\
	.prepare_task		= gsnedf_prepare_task,		\
	.sleep_next_period	= gsnedf_sleep_next_period,	\
	.tear_down		= gsnedf_tear_down,		\
	.schedule		= gsnedf_schedule,		\
	.finish_switch 		= gsnedf_finish_switch,		\
	.mode_change		= gsnedf_mode_change,		\
	.wake_up_task		= gsnedf_wake_up_task,		\
	.task_blocks		= gsnedf_task_blocks, 		\
	.enter_np		= gsnedf_enter_np, 		\
	.exit_np		= gsnedf_exit_np, 		\
	.inherit_priority	= gsnedf_inherit_priority, 	\
	.return_priority	= gsnedf_return_priority, 	\
	.pi_block		= gsnedf_pi_block		\
}


sched_plugin_t *__init init_gsn_edf_plugin(void)
{
	int cpu;
	cpu_entry_t *entry;

	if (!s_plugin.ready_to_use)
	{
		/* initialize CPU state */
		for (cpu = 0; cpu < NR_CPUS; cpu++)  {
			entry = &per_cpu(gsnedf_cpu_entries, cpu);
			atomic_set(&entry->will_schedule, 0);
			entry->linked    = NULL;
			entry->scheduled = NULL;
			entry->cpu 	 = cpu;
		}		

		queue_lock_init(&gsnedf_lock);
		set_sched_options(SCHED_NONE);
		edf_domain_init(&gsnedf, NULL);
		s_plugin = INIT_SCHED_PLUGIN;
	}
	return &s_plugin;
}