path: root/litmus/sched_cedf.c

/*
 * kernel/sched_cedf.c
 *
 * Implementation of the Clustered EDF (C-EDF) scheduling algorithm.
 * Linking is included so that support for synchronization (e.g., through
 * the implementation of a "CSN-EDF" algorithm) can be added later if desired.
 *
 * 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.
 */

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

#include <litmus/litmus.h>
#include <litmus/jobs.h>
#include <litmus/sched_plugin.h>
#include <litmus/edf_common.h>
#include <litmus/sched_trace.h>
#include <litmus/bheap.h>

#include <linux/module.h>

/* Overview of C-EDF operations.
 *
 * link_task_to_cpu(T, cpu) 	- Low-level operation to update the linkage
 *                                structure (NOT the actually scheduled
 *                                task). If there is another linked task To
 *                                already it will set To->linked_on = NO_CPU
 *                                (thereby removing its association with this
 *                                CPU). However, it will not requeue the
 *                                previously linked task (if any). It will set
 *                                T's state to RT_F_RUNNING and check whether
 *                                it is already running somewhere else. If T
 *                                is scheduled somewhere else it will link
 *                                it to that CPU instead (and pull the linked
 *                                task to cpu). T may be NULL.
 *
 * unlink(T)			- Unlink removes T from all scheduler data
 *                                structures. If it is linked to some CPU it
 *                                will link NULL to that CPU. If it is
 *                                currently queued in the cedf queue for
 *                                a partition, it will be removed from
 *                                the rt_domain. It is safe to call
 *                                unlink(T) if T is not linked. T may not
 *                                be NULL.
 *
 * requeue(T)			- Requeue will insert T into the appropriate
 *                                queue. If the system is in real-time mode and
 *                                the T is released already, it will go into the
 *                                ready queue. If the system is not in
 *                                real-time mode is T, then T will go into the
 *                                release queue. If T's release time is in the
 *                                future, it will go into the release
 *                                queue. That means that T's release time/job
 *                                no/etc. has to be updated before requeue(T) is
 *                                called. It is not safe to call requeue(T)
 *                                when T is already queued. T may not be NULL.
 *
 * cedf_job_arrival(T)		- This is the catch-all function when T enters
 *                                the system after either a suspension or at a
 *                                job release. It will queue T (which means it
 *                                is not safe to call cedf_job_arrival(T) if
 *                                T is already queued) and then check whether a
 *                                preemption is necessary. If a preemption is
 *                                necessary it will update the linkage
 *                                accordingly and cause scheduled to be called
 *                                (either with an IPI or need_resched). It is
 *                                safe to call cedf_job_arrival(T) if T's
 *                                next job has not been actually released yet
 *                                (release time in the future). T will be put
 *                                on the release queue in that case.
 *
 * job_completion(T)		- Take care of everything that needs to be done
 *                                to prepare T for its next release and place
 *                                it in the right queue with
 *                                cedf_job_arrival().
 *
 *
 * When we now that T is linked to CPU then link_task_to_cpu(NULL, CPU) is
 * equivalent to unlink(T). Note that if you unlink a task from a CPU none of
 * the functions will automatically propagate pending task from the ready queue
 * to a linked task. This is the job of the calling function ( by means of
 * __take_ready).
 */

/* 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, cedf_cpu_entries);

cpu_entry_t* *cedf_cpu_entries_array;

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

/* Cluster size -- currently four. This is a variable to allow for
 * the possibility of changing the cluster size online in the future.
 */
int cluster_size = 4;

int do_cleanup = 1;

typedef struct {
	rt_domain_t 		domain;
	int          		first_cpu;
	int			last_cpu;

	/* the cpus queue themselves according to priority in here */
	struct list_head	cedf_cpu_queue;

	/* per-partition spinlock: protects the domain and
	 * serializes scheduling decisions
	 */
#define slock domain.ready_lock
} cedf_domain_t;

DEFINE_PER_CPU(cedf_domain_t*, cedf_domains) = NULL;

cedf_domain_t* *cedf_domains_array;


/* These are defined similarly to partitioning, except that a
 * tasks partition is any cpu of the cluster to which it
 * is assigned, typically the lowest-numbered cpu.
 */
#define local_edf		(&__get_cpu_var(cedf_domains)->domain)
#define local_cedf		__get_cpu_var(cedf_domains)
#define remote_edf(cpu)		(&per_cpu(cedf_domains, cpu)->domain)
#define remote_cedf(cpu)	per_cpu(cedf_domains, cpu)
#define task_edf(task)		remote_edf(get_partition(task))
#define task_cedf(task)		remote_cedf(get_partition(task))

/* update_cpu_position - Move the cpu entry to the correct place to maintain
 *                       order in the cpu queue. Caller must hold cedf lock.
 *
 *						This really should be a heap.
 */
static void update_cpu_position(cpu_entry_t *entry)
{
	cpu_entry_t *other;
	struct list_head *cedf_cpu_queue =
		&(remote_cedf(entry->cpu))->cedf_cpu_queue;
	struct list_head *pos;

	BUG_ON(!cedf_cpu_queue);

	if (likely(in_list(&entry->list)))
		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, cedf_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, cedf_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));

	/* Cannot link task to a CPU that doesn't belong to its partition... */
	BUG_ON(linked && remote_cedf(entry->cpu) != task_cedf(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(cedf_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;

	if (entry->linked)
		TRACE_TASK(entry->linked, "linked to CPU %d, state:%d\n",
			   entry->cpu, entry->linked->state);
	else
		TRACE("NULL linked to CPU %d\n", entry->cpu);

	update_cpu_position(entry);
}

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

	if (unlikely(!t)) {
		TRACE_BUG_ON(!t);
		return;
	}

	if (t->rt_param.linked_on != NO_CPU) {
		/* unlink */
		entry = &per_cpu(cedf_cpu_entries, t->rt_param.linked_on);
		t->rt_param.linked_on = NO_CPU;
		link_task_to_cpu(NULL, entry);
	} else if (is_queued(t)) {
		/* 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.
		 */
		remove(task_edf(t), t);
	}
}


/* preempt - force a CPU to reschedule
 */
static noinline void preempt(cpu_entry_t *entry)
{
	preempt_if_preemptable(entry->scheduled, entry->cpu);
}

/* requeue - Put an unlinked task into c-edf domain.
 *           Caller must hold cedf_lock.
 */
static noinline void requeue(struct task_struct* task)
{
	cedf_domain_t* cedf;
	rt_domain_t* edf;

	BUG_ON(!task);
	/* sanity check rt_list before insertion */
	BUG_ON(is_queued(task));

	/* Get correct real-time domain. */
	cedf = task_cedf(task);
	edf = &cedf->domain;

	if (is_released(task, litmus_clock()))
		__add_ready(edf, task);
	else {
		/* it has got to wait */
		add_release(edf, task);
	}
}

static void check_for_preemptions(cedf_domain_t* cedf)
{
	cpu_entry_t *last;
	struct task_struct *task;
	struct list_head *cedf_cpu_queue;
	cedf_cpu_queue = &cedf->cedf_cpu_queue;

	for(last = list_entry(cedf_cpu_queue->prev, cpu_entry_t, list);
	    edf_preemption_needed(&cedf->domain, last->linked);
	    last = list_entry(cedf_cpu_queue->prev, cpu_entry_t, list)) {
		/* preemption necessary */
		task = __take_ready(&cedf->domain);
		TRACE("check_for_preemptions: task %d linked to %d, state:%d\n",
		      task->pid, last->cpu, task->state);
		if (last->linked)
			requeue(last->linked);
		link_task_to_cpu(task, last);
		preempt(last);
	}

}

/* cedf_job_arrival: task is either resumed or released */
static noinline void cedf_job_arrival(struct task_struct* task)
{
	cedf_domain_t* cedf;
	rt_domain_t* edf;

	BUG_ON(!task);

	/* Get correct real-time domain. */
	cedf = task_cedf(task);
	edf = &cedf->domain;

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

	/* then check for any necessary preemptions */
	check_for_preemptions(cedf);
}

/* check for current job releases */
static void cedf_release_jobs(rt_domain_t* rt, struct bheap* tasks)
{
        cedf_domain_t*          cedf = container_of(rt, cedf_domain_t, domain);
	unsigned long 		flags;

	spin_lock_irqsave(&cedf->slock, flags);

	__merge_ready(&cedf->domain, tasks);
	check_for_preemptions(cedf);
	spin_unlock_irqrestore(&cedf->slock, flags);
}

/* cedf_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 void cedf_tick(struct task_struct* t)
{
	BUG_ON(!t);

	if (is_realtime(t) && budget_exhausted(t)) {
		if (!is_np(t)) {
			/* np tasks will be preempted when they become
			 * preemptable again
			 */
			set_tsk_need_resched(t);
			set_will_schedule();
			TRACE("cedf_scheduler_tick: "
			      "%d is preemptable (state:%d) "
			      " => FORCE_RESCHED\n", t->pid, t->state);
		} else if(is_user_np(t)) {
			TRACE("cedf_scheduler_tick: "
			      "%d is non-preemptable (state:%d), "
			      "preemption delayed.\n", t->pid, t->state);
			request_exit_np(t);
		}
	}
}

/* caller holds cedf_lock */
static noinline void job_completion(struct task_struct *t, int forced)
{
	BUG_ON(!t);

	sched_trace_task_completion(t, forced);

	TRACE_TASK(t, "job_completion(). [state:%d]\n", t->state);

	/* set flags */
	set_rt_flags(t, RT_F_SLEEP);
	/* prepare for next period */
	prepare_for_next_period(t);
	/* unlink */
	unlink(t);
	/* requeue
	 * But don't requeue a blocking task. */
	if (is_running(t))
		cedf_job_arrival(t);
}

/* Getting schedule() right is a bit tricky. schedule() may not make any
 * assumptions on the state of the current task since it may be called for a
 * number of reasons. The reasons include a scheduler_tick() determined that it
 * was necessary, because sys_exit_np() was called, because some Linux
 * subsystem determined so, or even (in the worst case) because there is a bug
 * hidden somewhere. Thus, we must take extreme care to determine what the
 * current state is.
 *
 * The CPU could currently be scheduling a task (or not), be linked (or not).
 *
 * The following assertions for the scheduled task could hold:
 *
 *      - !is_running(scheduled)        // the job blocks
 *	- scheduled->timeslice == 0	// the job completed (forcefully)
 *	- get_rt_flag() == RT_F_SLEEP	// the job completed (by syscall)
 * 	- linked != scheduled		// we need to reschedule (for any reason)
 * 	- is_np(scheduled)		// rescheduling must be delayed,
 *					   sys_exit_np must be requested
 *
 * Any of these can occur together.
 */
static struct task_struct* cedf_schedule(struct task_struct * prev)
{
	cedf_domain_t* 		cedf = local_cedf;
	rt_domain_t*		edf  = &cedf->domain;
	cpu_entry_t* 		entry = &__get_cpu_var(cedf_cpu_entries);
	int 			out_of_time, sleep, preempt, np,
				exists, blocks;
	struct task_struct* 	next = NULL;

	BUG_ON(!prev);
	BUG_ON(!cedf);
	BUG_ON(!edf);
	BUG_ON(!entry);
	BUG_ON(cedf != remote_cedf(entry->cpu));
	BUG_ON(is_realtime(prev) && cedf != task_cedf(prev));

	/* Will be released in finish_switch. */
	spin_lock(&cedf->slock);
	clear_will_schedule();

	/* sanity checking */
	BUG_ON(entry->scheduled && entry->scheduled != prev);
	BUG_ON(entry->scheduled && !is_realtime(prev));
	BUG_ON(is_realtime(prev) && !entry->scheduled);

	/* (0) Determine state */
	exists      = entry->scheduled != NULL;
	blocks      = exists && !is_running(entry->scheduled);
	out_of_time = exists && budget_exhausted(entry->scheduled);
	np 	    = exists && is_np(entry->scheduled);
	sleep	    = exists && get_rt_flags(entry->scheduled) == RT_F_SLEEP;
	preempt     = entry->scheduled != entry->linked;

	/* If a task blocks we have no choice but to reschedule.
	 */
	if (blocks)
		unlink(entry->scheduled);

	/* Request a sys_exit_np() call if we would like to preempt but cannot.
	 * We need to make sure to update the link structure anyway in case
	 * that we are still linked. Multiple calls to request_exit_np() don't
	 * hurt.
	 */
	if (np && (out_of_time || preempt || sleep)) {
		unlink(entry->scheduled);
		request_exit_np(entry->scheduled);
	}

	/* Any task that is preemptable and either exhausts its execution
	 * budget or wants to sleep completes. We may have to reschedule after
	 * this. Don't do a job completion if blocks (can't have timers
	 * running for blocked jobs). Preemption go first for the same reason.
	 */
	if (!np && (out_of_time || sleep) && !blocks && !preempt)
		job_completion(entry->scheduled, !sleep);

	/* Link pending task if we became unlinked.
	 */
	if (!entry->linked)
		link_task_to_cpu(__take_ready(edf), entry);

	/* The final scheduling decision. Do we need to switch for some reason?
	 * If linked different from scheduled select linked as next.
	 */
	if ((!np || blocks) &&
	    entry->linked != entry->scheduled) {
		/* Schedule a linked job? */
		if (entry->linked) {
			entry->linked->rt_param.scheduled_on = entry->cpu;
			next = entry->linked;
		}
                if (entry->scheduled) {
			/* not gonna be scheduled soon */
			entry->scheduled->rt_param.scheduled_on = NO_CPU;
			TRACE_TASK(entry->scheduled, "cedf_schedule: scheduled_on = NO_CPU\n");
		}
	} else
		/* Only override Linux scheduler if we have real-time task
		 * scheduled that needs to continue.
		 */
		if (exists)
			next = prev;

	spin_unlock(&cedf->slock);

	return next;
}

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

	BUG_ON(!prev);
	BUG_ON(!entry);

	entry->scheduled = is_realtime(current) ? current : NULL;
}

/*	Prepare a task for running in RT mode
 */
static void cedf_task_new(struct task_struct *t, int on_rq, int running)
{
	unsigned long 		flags;
	cedf_domain_t*	 	cedf = task_cedf(t);
	cpu_entry_t* 		entry;

	BUG_ON(!cedf);

	spin_lock_irqsave(&cedf->slock, flags);
	if (running) {
		entry = &per_cpu(cedf_cpu_entries, task_cpu(t));
		BUG_ON(!entry);
		BUG_ON(entry->scheduled);
		entry->scheduled = t;
		t->rt_param.scheduled_on = task_cpu(t);
	} else
		t->rt_param.scheduled_on = NO_CPU;
	t->rt_param.linked_on = NO_CPU;

	/* setup job params */
	release_at(t, litmus_clock());

	cedf_job_arrival(t);
	spin_unlock_irqrestore(&cedf->slock, flags);
}


static void cedf_task_wake_up(struct task_struct *task)
{
	unsigned long		flags;
	cedf_domain_t*	 	cedf;
	lt_t 			now;

	BUG_ON(!task);

	cedf = task_cedf(task);
	BUG_ON(!cedf);

	spin_lock_irqsave(&cedf->slock, flags);
	/* 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 {
		now = litmus_clock();
		if (is_tardy(task, now)) {
			/* new sporadic release */
			release_at(task, now);
			sched_trace_task_release(task);
		}
		else if (task->rt.time_slice)
			/* came back in time before deadline
			 */
			set_rt_flags(task, RT_F_RUNNING);
	}
	cedf_job_arrival(task);
	spin_unlock_irqrestore(&cedf->slock, flags);
}


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

	BUG_ON(!t);

	/* unlink if necessary */
	spin_lock_irqsave(&task_cedf(t)->slock, flags);

	t->rt_param.scheduled_on = NO_CPU;
	unlink(t);

	spin_unlock_irqrestore(&task_cedf(t)->slock, flags);

	BUG_ON(!is_realtime(t));
}

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

	BUG_ON(!t);

	/* unlink if necessary */
	spin_lock_irqsave(&task_cedf(t)->slock, flags);
	unlink(t);
	if (tsk_rt(t)->scheduled_on != NO_CPU) {
		cedf_cpu_entries_array[tsk_rt(t)->scheduled_on]->
			scheduled = NULL;
		tsk_rt(t)->scheduled_on = NO_CPU;
	}
	spin_unlock_irqrestore(&task_cedf(t)->slock, flags);

	BUG_ON(!is_realtime(t));
        TRACE_TASK(t, "RIP\n");
}

static long cedf_admit_task(struct task_struct* tsk)
{
	return (task_cpu(tsk) >= task_cedf(tsk)->first_cpu &&
	        task_cpu(tsk) <= task_cedf(tsk)->last_cpu) ? 0 : -EINVAL;
}


/*	Plugin object	*/
static struct sched_plugin cedf_plugin __cacheline_aligned_in_smp = {
	.plugin_name		= "C-EDF",
	.finish_switch		= cedf_finish_switch,
	.tick			= cedf_tick,
	.task_new		= cedf_task_new,
	.complete_job		= complete_job,
	.task_exit		= cedf_task_exit,
	.schedule		= cedf_schedule,
	.task_wake_up		= cedf_task_wake_up,
	.task_block		= cedf_task_block,
	.admit_task		= cedf_admit_task
};

static void cedf_domain_init(int first_cpu, int last_cpu)
{
	int cpu;

	/* Create new domain for this cluster. */
	cedf_domain_t *new_cedf_domain = kmalloc(sizeof(*new_cedf_domain),
						     GFP_KERNEL);

	/* Initialize cluster domain. */
	edf_domain_init(&new_cedf_domain->domain, NULL,
			cedf_release_jobs);
	new_cedf_domain->first_cpu	= first_cpu;
	new_cedf_domain->last_cpu	= last_cpu;
	INIT_LIST_HEAD(&new_cedf_domain->cedf_cpu_queue);

	/* Assign all cpus in cluster to point to this domain. */
	for (cpu = first_cpu; cpu <= last_cpu; cpu++) {
		remote_cedf(cpu) = new_cedf_domain;
		cedf_domains_array[cpu] = new_cedf_domain;
	}
}

static int __init init_cedf(void)
{
	int cpu;
	cpu_entry_t *entry;

	/* num_online_cpus() should have been set already
	 * if the number of available cpus is less then the cluster
	 * size (currently 4) then it is pointless trying to use
	 * CEDF, so we disable this plugin
	 */
	if(num_online_cpus() < cluster_size) {
		printk(KERN_INFO "Not registering C-EDF plugin: "
			"Num Online Cpus (%d) < Min Cluster Size (%d)\n",
			num_online_cpus(), cluster_size);
		do_cleanup = 0;
		return 0;
	}

	/*
	 * initialize short_cut for per-cpu cedf state;
	 * there may be a problem here if someone removes a cpu
	 * while we are doing this initialization... and if cpus
	 * are added / removed later... is it a _real_ problem for cedf?
	 */
	cedf_cpu_entries_array = kmalloc(
			sizeof(cpu_entry_t *) * num_online_cpus(),
			GFP_KERNEL);

	cedf_domains_array = kmalloc(
			sizeof(cedf_domain_t *) * num_online_cpus(),
			GFP_KERNEL);

	/* initialize CPU state */
	for (cpu = 0; cpu < num_online_cpus(); cpu++)  {
		entry = &per_cpu(cedf_cpu_entries, cpu);
		cedf_cpu_entries_array[cpu] = entry;
		atomic_set(&entry->will_schedule, 0);
		entry->linked    = NULL;
		entry->scheduled = NULL;
		entry->cpu 	 = cpu;
		INIT_LIST_HEAD(&entry->list);
	}

	/* initialize all cluster domains */
	for (cpu = 0; cpu < num_online_cpus(); cpu += cluster_size)
		cedf_domain_init(cpu, cpu+cluster_size-1);

	return register_sched_plugin(&cedf_plugin);
}

static void clean_cedf(void)
{
	if(do_cleanup) {
		kfree(cedf_cpu_entries_array);
		kfree(cedf_domains_array);
	}
}

module_init(init_cedf);
module_exit(clean_cedf);