path: root/litmus/sched_edf_hsb.c

#include <linux/module.h>
#include <linux/kernel.h>	/* for sscanf, prink, etc. */
#include <linux/uaccess.h>	/* for copy_from_user */
#include <linux/percpu.h>
#include <linux/spinlock.h>
#include <linux/smp.h>
#include <linux/ctype.h>
#include <linux/time.h>
#include <linux/string.h>
#include <linux/sched.h>
#include <linux/hrtimer.h>

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

struct hrt_server {
	/* lt_t is nanoseconds (as of now, anyway...) */
	lt_t		wcet;
	lt_t		budget;
	lt_t		period;
	lt_t            deadline;

	rt_domain_t	domain;

	/* lock for setting wcet and period */
	rwlock_t	param_lock;

	/* timer for refilling the budget */
	struct hrtimer  refill_timer;

	/* timer for decrementing the budget */
	struct hrtimer  budget_timer;

	/* timer to set the no_slack flag when we have no slack */
	struct hrtimer	slack_timer;

	/* stores a task's initial execution time */
	lt_t            start_exec_time;

	/*
	 * The server has no slack time left when:
	 * (deadline - budget) <= current_time
	 */
	int		no_slack;
};

struct cpu_entry {
	int				cpu;
	struct task_struct*		scheduled;
	struct task_struct*		linked;
	struct hrtimer_start_on_info	hrtimer_info;
	struct hrt_server		hrt_server;
};

/*
 * Forward declarations
 */
static noinline void requeue(struct task_struct*, rt_domain_t*);
static noinline void unlink(struct task_struct*, rt_domain_t*);
static enum hrtimer_restart budget_timer_fire(struct hrtimer*);
static void timer_cancel(struct hrtimer *timer);
static void decrement_server_budget(struct hrt_server*, struct task_struct*);
static enum hrtimer_restart refill_timer_fire(struct hrtimer*);
static void slack_timer_arm(struct hrt_server*);
static enum hrtimer_restart slack_timer_fire(struct hrtimer*);
static void edf_hsb_release_jobs(rt_domain_t*, struct bheap*);
static struct sched_plugin edf_hsb_plugin __cacheline_aligned_in_smp;
#define is_active_plugin (litmus == &edf_hsb_plugin)

/*
 * Per-CPU variables
 */
DEFINE_PER_CPU_SHARED_ALIGNED(struct cpu_entry,  cpu_entries);

/*
 * Global variables
 */
static rt_domain_t srt_domain;

/*
 * Do all hrt_servers have a non-zero WCET and period? Return 0 if so.
 */
static int check_hrt_servers_initialized(void)
{
	struct hrt_server* hrt_server;
	int cpu, all_init = 1;

	for_each_online_cpu(cpu) {
		hrt_server = &per_cpu(cpu_entries, cpu).hrt_server;
		read_lock_irq(&hrt_server->param_lock);

		/* if any parameter is zero, all_init will become zero */
		all_init = all_init && hrt_server->wcet &&
			hrt_server->period;

		read_unlock_irq(&hrt_server->param_lock);
	}


	/* inverted because zero is success */
	return !all_init;
}

/*
 * 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,
				      struct cpu_entry *entry)
{
	struct cpu_entry *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(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) {
				TRACE_TASK(linked,
					   "already scheduled on %d, updating link.\n",
					   sched->cpu);
				tmp = sched->linked;
				linked->rt_param.linked_on = sched->cpu;
				sched->linked = linked;
				linked = tmp;
			}
		}
		if (linked) /* Might be NULL due to swap */
			linked->rt_param.linked_on = entry->cpu;
	}
	entry->linked = linked;
#ifdef WANT_ALL_SCHED_EVENTS
	if (linked)
		TRACE_TASK(linked, "linked to %d.\n", entry->cpu);
#endif
}

/*
 * Updates task properties and requeues it, if necessary.
 */
static noinline void job_completion(struct task_struct *task,
				    int forced, rt_domain_t *domain)
{
	struct cpu_entry *entry = &__get_cpu_var(cpu_entries);
	struct hrt_server *server = &entry->hrt_server;

	BUG_ON(task == NULL);
	BUG_ON(domain == NULL);

	sched_trace_task_completion(task, forced);
	TRACE_TASK(task, "job_completion(),\n");

	set_rt_flags(task, RT_F_SLEEP);
	prepare_for_next_period(task);

	if (is_released(task, litmus_clock()))
		sched_trace_task_release(task);

	BUG_ON(task_cpu(task) != entry->cpu);
	BUG_ON(task->rt_param.linked_on != NO_CPU &&
	       task->rt_param.linked_on != entry->cpu);
	unlink(task, domain);

	/* Requeue the task if it is not blocking */
	if (is_running(task))
		requeue(task, domain);

	if (is_hrt(task)) {
		BUG_ON(task_cpu(task) != entry->cpu);

		timer_cancel(&server->budget_timer);
		decrement_server_budget(server, task);
	}
}

/* If the server is eligible, return the next eligible job. If
 * the server is ineligible or there are no eligible jobs,
 * returns NULL.
 *
 * From the paper: A job generated by a HRT task is eligible if either the
 * job's deadline is earlier than the server's next deadline, or the server
 * has zero slack time in its current period.
 *
 * No locks here, because this method accesses only CPU-local state, and is
 * called from schedule(), which disables interrupts.
 *
 * Assumes called with local IRQs disabled.
 */
static struct task_struct* next_eligible_hrt_task(struct hrt_server *server)
{
	struct task_struct *task = NULL;
	lt_t svr_deadline = server->deadline, svr_budget = server->budget;

	if (svr_budget > 0)
		task = __peek_ready(&server->domain);

	if (task && (server->no_slack || get_deadline(task) < svr_deadline))
		remove(&server->domain, task);
	else
		task = NULL;

	return task;
}

/*
 * Adds a task to the appropriate queue (ready / release) in a domain.
 */
static noinline void requeue(struct task_struct *task, rt_domain_t *domain)
{
	BUG_ON(!task);
	BUG_ON(!is_realtime(task));
	BUG_ON(is_queued(task));

	if (is_released(task, litmus_clock())) {
		__add_ready(domain, task);
	} else {
		/* Task needs to wait until it is released */
		add_release(domain, task);
	}
}

void initialize_cpu_variables(void)
{
	struct cpu_entry  *cpu_entry;
	struct hrt_server *hrt_server;
	struct hrtimer    *budget_timer, *refill_timer, *slack_timer;
	int cpu;

	printk("Initializing HRT servers\n");

	for_each_online_cpu(cpu) {
		cpu_entry = &per_cpu(cpu_entries, cpu);
		hrt_server = &cpu_entry->hrt_server;

		/* CPU entries */
		cpu_entry->cpu = cpu;
		hrtimer_start_on_info_init(&cpu_entry->hrtimer_info);

		/* HRT servers */
		rwlock_init(&hrt_server->param_lock);
		hrt_server->wcet = hrt_server->period = hrt_server->budget = 0;

		/* Domains */
		edf_domain_init(&hrt_server->domain, NULL,
				edf_hsb_release_jobs);

		/* Timers */
		budget_timer = &hrt_server->budget_timer;
		refill_timer = &hrt_server->refill_timer;
		slack_timer  = &hrt_server->slack_timer;

                hrtimer_init(budget_timer,
			     CLOCK_MONOTONIC,
			     HRTIMER_MODE_ABS);
                budget_timer->function = budget_timer_fire;

                hrtimer_init(refill_timer,
			     CLOCK_MONOTONIC,
			     HRTIMER_MODE_ABS);
                refill_timer->function = refill_timer_fire;

		hrtimer_init(slack_timer,
				CLOCK_MONOTONIC,
				HRTIMER_MODE_ABS);
		slack_timer->function = slack_timer_fire;

		BUG_ON(hrtimer_active(&hrt_server->budget_timer));
	}
}

/*
 * Set the WCET and period for an HRT server on a specific CPU.
 * Times are given in milliseconds.
 * There is a small race condition in checking we're not the active plugin
 * before setting parameters, but we are not worried about that so much.
 */
int set_hrt_params(unsigned long long cpu, unsigned long long wcet,
		unsigned long long period)
{
	struct hrt_server *hrt_server;
	int rv = 0;

	/* do some sanity checking first */
	if (wcet <= 0) {
		printk(KERN_WARNING "Invalid WCET in %s\n", __func__);
		rv = -EINVAL;
		goto out;
	}

	if (period < wcet) {
		printk(KERN_WARNING "Invalid period in %s\n", __func__);
		rv = -EINVAL;
		goto out;
	}

	if (cpu < 0 || cpu >= nr_cpu_ids) {
		printk(KERN_WARNING "Invalid CPU in %s\n", __func__);
		rv = -EINVAL;
		goto out;
	}

	if (is_active_plugin) {
		printk(KERN_WARNING "Can't set params on active plugin.\n");
		rv = -EPERM;
		goto out;
	}

	hrt_server = &per_cpu(cpu_entries, cpu).hrt_server;
	write_lock_irq(&hrt_server->param_lock);
	hrt_server->wcet = wcet * NSEC_PER_MSEC;
	hrt_server->period = period * NSEC_PER_MSEC;
	write_unlock_irq(&hrt_server->param_lock);
out:
	return rv;
}

static noinline void unlink(struct task_struct *task, rt_domain_t *domain)
{
	struct cpu_entry  *entry;

	BUG_ON(task == NULL);
	BUG_ON(domain == NULL);

	/* Macro used for better branch prediction */
	if (unlikely(!task)) {
		/* TRACE_BUG_ON(!task); */
		return;
	}

	if (task->rt_param.linked_on != NO_CPU) {
		/* Unlink task from CPU */
		entry = &per_cpu(cpu_entries, task->rt_param.linked_on);
		task->rt_param.linked_on = NO_CPU;
		link_task_to_cpu(NULL, entry);
	} else if (is_queued(task)) {
                /* 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(domain, task);
	}
}


/******************************************************************************
 * Timer methods
 ******************************************************************************/
/*
 * Arms a timer to go off when a task will exhaust the HRT server budget.
 * The case when the server reaches the deadline is handled by the refill
 * timer, which calls into the scheduler when that happens.
 *
 * This also sets the execution time used by this task at the beginning of the
 * timer.
 *
 * By the eligibility rules, the job's deadline must be less than the server's
 * next deadline. It shouldn't be tardy (b/c this is HRT), but we'll use
 * budget_remaining instead of deadline in case.
 *
 * Called from schedule(), so IRQs are off.
 */
static void budget_timer_arm(struct hrt_server *server, struct task_struct* t)
{
	lt_t svr_deadline, svr_budget_exhausted;

	BUG_ON(hrtimer_active(&server->budget_timer));
	BUG_ON(hrtimer_active(&server->slack_timer));

	server->start_exec_time = get_exec_time(t);

	if (lt_after(server->budget, budget_remaining(t)))
		return;

	svr_deadline = server->deadline;
	svr_budget_exhausted = litmus_clock() + server->budget;

	/*
	 * Timer is not needed if the HRT server deadline is before this task
	 * would use all the HRT budget.
	 */
	if (lt_after(svr_budget_exhausted, svr_deadline))
		return;

	TRACE_TASK(t,
		   "budget armed to fire at %llu\n", svr_budget_exhausted);


	__hrtimer_start_range_ns(&server->budget_timer,
				 ns_to_ktime(svr_budget_exhausted),
				 0 /* delta */,
				 HRTIMER_MODE_ABS_PINNED,
				 0 /* no wakeup */);
}

/*
 * Decrements a server's budget by the time consumed by a task.
 * Assumes called with IRQs off
 */
static void decrement_server_budget(struct hrt_server *server,
				    struct task_struct *t)
{
	lt_t start_exec_time = server->start_exec_time;
	lt_t end_exec_time = get_exec_time(t);
	lt_t elapsed_time;

	/* This method has already been called for this job */
	if (start_exec_time == 0)
		return;

	BUG_ON(server == NULL || t == NULL);

	elapsed_time = end_exec_time - start_exec_time;

	if ( (((long long)end_exec_time)  - ((long long)start_exec_time)) < 0 ||
	     (((long long)server->budget) - ((long long)elapsed_time)) < 0   )
		server->budget = 0;
	else
		server->budget -= elapsed_time;

	/*
	 * Cancel and re-arm the slack timer, because we changed the budget
	 */
	timer_cancel(&server->slack_timer);
	slack_timer_arm(server);

	TRACE_TASK(t, "server budget: %llu", server->budget);
	server->start_exec_time = 0;
}

/*
 * The budget timer should never fire if an HRT task is no longer scheduled.
 */
static enum hrtimer_restart budget_timer_fire(struct hrtimer *timer)
{
	struct cpu_entry   *entry;
	struct task_struct *curr;
	struct hrt_server  *server;
	unsigned long flags;

	local_irq_save(flags);

	entry  = &__get_cpu_var(cpu_entries);
	curr = entry->scheduled;
	server = &entry->hrt_server;

	BUG_ON(curr == NULL || !is_hrt(curr));
	decrement_server_budget(server, curr);

	/* activate scheduler */
	litmus_reschedule_local();

	local_irq_restore(flags);

	return HRTIMER_NORESTART;
}

/*
 * Okay to call if the timer is not armed.
 * Assumes called with IRQs off
 */
static void timer_cancel(struct hrtimer *timer)
{
	int ret;

	TRACE("cancelling a timer.\n");

	BUG_ON(timer == NULL);

	if (hrtimer_active(timer)) {
		ret = hrtimer_try_to_cancel(timer);
		/* should never be inactive */
		BUG_ON(ret == 0);
		/* should never be running concurrently */
		BUG_ON(ret == -1);
	}
}

/*
 * Refills a server's budget and clears the no_slack flag.
 * Resets the timer itself.
 */
static enum hrtimer_restart refill_timer_fire(struct hrtimer *timer)
{
	unsigned long flags;
	struct cpu_entry *entry =  &__get_cpu_var(cpu_entries);
	struct hrt_server *server = &entry->hrt_server;

	TRACE("refill timer fired on cpu %d at litmus time: %llu\n",
			entry->cpu, litmus_clock());

	local_irq_save(flags);

	server->budget = server->wcet;
	server->deadline += server->period;

	if (likely(server->no_slack)) {
		server->no_slack = 0;

		BUG_ON(hrtimer_active(&server->slack_timer));
		slack_timer_arm(server);
	}

	hrtimer_set_expires(timer, ns_to_ktime(server->deadline));

	/* activate scheduler */
	litmus_reschedule_local();

	local_irq_restore(flags);

	return HRTIMER_RESTART;
}

/*
 * Assumes called with local IRQs off
 *
 * This method arms the slack timer if the following conditions are true:
 *	- There is server budget remaining.
 *	- The no_slack flag is not already set.
 */
static void slack_timer_arm(struct hrt_server *server)
{
	struct hrtimer *timer = &server->slack_timer;
	struct cpu_entry *entry = container_of(server,
					       struct cpu_entry,
					       hrt_server);
	lt_t when_to_fire = server->deadline - server->budget;

	if (server->no_slack || server->budget <= 0) {
		TRACE("cancel slack timer arm");
		return;
	}


	BUG_ON(hrtimer_active(timer));
	BUG_ON(hrtimer_active(&server->budget_timer));

	/* kind of ridiculous to check this, but whatever... */
	BUG_ON(server->budget >= server->deadline);
	/* Can this happen? */
	BUG_ON(lt_after_eq(litmus_clock(), when_to_fire));

	TRACE("slack armed to fire at %llu", when_to_fire);

	hrtimer_start_on(entry->cpu, &entry->hrtimer_info,
			 timer,
			 ns_to_ktime(when_to_fire),
			 HRTIMER_MODE_ABS_PINNED);
}

static enum hrtimer_restart slack_timer_fire(struct hrtimer *timer)
{
	unsigned long flags;
	struct cpu_entry *entry = &__get_cpu_var(cpu_entries);
	struct hrt_server *server = &entry->hrt_server;

	local_irq_save(flags);
	server->no_slack = 1;

	TRACE("slack timer fired on cpu %d at litmus time: %llu\n",
			entry->cpu, litmus_clock());

	/* activate scheduler */
	litmus_reschedule_local();

	local_irq_restore(flags);

	return HRTIMER_NORESTART;
}

/******************************************************************************
 * Plugin methods
 ******************************************************************************/

/*
 * There is a small race condition in checking that all the server parameters
 * are valid, then having one of them change before setting the active plugin,
 * but oh well.
 */
static long edf_hsb_activate_plugin(void)
{
	lt_t common_server_start = litmus_clock();
	struct cpu_entry *cpu_entry;
	struct hrt_server* server;
	long rv = 0;
	int  cpu;

	TRACE("activating EDF-HSB plugin.\n");

	if (check_hrt_servers_initialized()) {
		rv = -EINVAL;
		goto out;
	}

	for_each_online_cpu(cpu) {
		cpu_entry = &per_cpu(cpu_entries, cpu);
		server = &cpu_entry->hrt_server;

		server->no_slack = 0;
		server->deadline = common_server_start + server->period;
		server->budget = server->wcet;
		server->start_exec_time = 0;

		TRACE("setting up cpu %d to have timer deadline %llu\n",
				cpu, server->deadline);
		hrtimer_start_on(cpu, &cpu_entry->hrtimer_info,
				&server->refill_timer,
				ns_to_ktime(server->deadline),
				HRTIMER_MODE_ABS_PINNED);

		slack_timer_arm(server);
	}
out:
	return rv;
}

/*
 * Requires a processor be specified for any task run on the system.
 */
static long edf_hsb_admit_task(struct task_struct *task)
{
	if (is_hrt(task)) {
		return task_cpu(task) == task->rt_param.task_params.cpu ? 0 : -EINVAL;
	} else {
		/* If the task is not HRT, we don't want to force the user
		 * to specify a CPU.
		 */
		return 0;
	}
}

static long edf_hsb_deactivate_plugin(void)
{
	struct cpu_entry  *cpu_entry;
	struct hrt_server *hrt_server;
	unsigned long flags;
	int cpu;

	local_irq_save(flags);

	/*
	 * XXX We should probably disable IRQs on the remote CPUs as well so
	 * that we can cancel the timers without worrying about them firing.
	 */
	for_each_online_cpu(cpu) {
		cpu_entry = &per_cpu(cpu_entries, cpu);
		hrt_server = &cpu_entry->hrt_server;

		timer_cancel(&hrt_server->budget_timer);
		timer_cancel(&hrt_server->refill_timer);
		timer_cancel(&hrt_server->slack_timer);
	}

	local_irq_restore(flags);

	return 0;
}

/*
 * Simply merges a heap of tasks into a domain's ready queue.
 * This is used by the edf domains.
 */
static void edf_hsb_release_jobs(rt_domain_t *domain, struct bheap *tasks)
{
	unsigned long flags;

	raw_spin_lock_irqsave(&domain->ready_lock, flags);
	__merge_ready(domain, tasks);
	/* check_for_preemptions(); */
	raw_spin_unlock_irqrestore(&domain->ready_lock, flags);
}

static struct task_struct* edf_hsb_schedule(struct task_struct *prev)
{
	struct cpu_entry   *entry;
	struct hrt_server  *server;
	struct task_struct *next, *curr, *next_ready;
	rt_domain_t        *current_domain = NULL;
	int                 blocks, exists, sleep, out_of_time;
	unsigned long flags;

	entry  = &__get_cpu_var(cpu_entries);
	server = &entry->hrt_server;

	/*
	 * Since HRT servers are not shared between CPUs, do not bother
	 * locking it. Just make sure interrupts are disabled.
	 */
	raw_spin_lock_irqsave(&srt_domain.ready_lock, flags);

	curr = entry->scheduled;

	BUG_ON(curr && curr != prev);
	BUG_ON(curr && !is_realtime(curr));
	BUG_ON(is_realtime(prev) && !curr);

	/* Determine state */
	exists		= curr != NULL;
	blocks		= exists && !is_running(curr);
	out_of_time	= exists && budget_enforced(curr) &&
				budget_exhausted(curr);
	sleep		= exists && get_rt_flags(curr) == RT_F_SLEEP;

	if (exists && is_hrt(curr)) {
		current_domain = &server->domain;
		blocks = out_of_time && server->budget > 0;
	}

	if (exists && is_srt(curr))
		current_domain = &srt_domain;

 	if (exists)
		TRACE_TASK(prev,
			   "blocks:%d out_of_time:%d sleep:%d "
			   "state:%d sig:%d\n",
			   blocks, out_of_time, sleep,
			   prev->state, signal_pending(prev));

	/* Must reschedule blocked task */
	if (blocks)
		unlink(curr, current_domain);

	if ((out_of_time || sleep) && !blocks)
		job_completion(curr, !sleep, current_domain);

	/* If the cpu entry has no linked task, select the next ready task */
	if (!entry->linked) {
		next_ready = next_eligible_hrt_task(server);

		/* Select an SRT task if the server was ineligible */
		if (!next_ready)
			next_ready = __take_ready(&srt_domain);

		link_task_to_cpu(next_ready, entry);
	}

	/* Switch current task if we are in RT mode and have no task
	 * or if linked is different from scheduled */
	next = NULL;
	if (curr != entry->linked) {
		if (entry->linked) {
			entry->linked->rt_param.scheduled_on = entry->cpu;
			next = entry->linked;
		}

		if (curr) {
			/* not gonna be scheduled soon */
			curr->rt_param.scheduled_on = NO_CPU;
			TRACE_TASK(curr, "scheduled_on = NO_CPU\n");
		}
	} else if (exists) {
		next = prev;
	}

	entry->scheduled = next;
	sched_state_task_picked();

	if (next && is_hrt(next)) {
		 /* Don't need a slack timer if we're scheduling an HRT task */
		timer_cancel(&server->slack_timer);

		/* Set up timer to deal with HRT server budget expiring */
		budget_timer_arm(server, next);
	}

	raw_spin_unlock_irqrestore(&srt_domain.ready_lock, flags);

	if (next)
		TRACE_TASK(next, "scheduled at %llu\n", litmus_clock());
	else if (exists && !next)
		TRACE("becomes idle at %llu.\n", litmus_clock());

	return next;
}

/*
 * If the blocked task was HRT, cancels the budget update timer
 * and decrements the task's server's budget.
 */
static void edf_hsb_task_block(struct task_struct *task)
{
	struct cpu_entry *entry;
	struct hrt_server *server = NULL;
	rt_domain_t       *domain;
	unsigned long      flags;

	TRACE_TASK(task, "block at %llu\n", litmus_clock());
	BUG_ON(!is_realtime(task));

	entry = &__get_cpu_var(cpu_entries);
	/*
	 * Which domain should we lock?
	 */
	if (is_hrt(task)) {
		server = &entry->hrt_server;
		BUG_ON(task_cpu(task) != entry->cpu);
		domain = &server->domain;
	} else
		domain = &srt_domain;

	raw_spin_lock_irqsave(&domain->ready_lock, flags);

	if (is_hrt(task)) {
		/* If an hrt task is blocked, we must do the work of the
		 * budget timer ourselves
		 */
		timer_cancel(&server->budget_timer);
		decrement_server_budget(server, task);
	}

	/* Unlink if the task is linked to a CPU */
	unlink(task, domain);

	raw_spin_unlock_irqrestore(&domain->ready_lock, flags);
}

static void edf_hsb_task_exit(struct task_struct *task)
{
	struct hrt_server *server;
	struct cpu_entry  *entry;
	rt_domain_t       *domain;
	unsigned long      flags;

	TRACE_TASK(task, "RIP at %llu\n", litmus_clock());
	BUG_ON(!is_realtime(task));

	entry = &per_cpu(cpu_entries, task_cpu(task));
	if (is_hrt(task)) {
		server = &entry->hrt_server;
		domain = &server->domain;
	} else {
		domain = &srt_domain;
	}

	/* Unlink if the task is linked to a CPU */
	raw_spin_lock_irqsave(&domain->ready_lock, flags);
	unlink(task, domain);
	raw_spin_unlock_irqrestore(&domain->ready_lock, flags);

	entry->scheduled = NULL;
}

/*
 * Prepare a task for running in RT mode
 */
static void edf_hsb_task_new(struct task_struct *task, int on_rq,  int running)
{
	struct cpu_entry  *entry;
	struct hrt_server *server;
	rt_domain_t       *domain;
	unsigned long      flags;

	TRACE_TASK(task, "edf_hsb: task new, cpu = %d\n",
		   task->rt_param.task_params.cpu);

	entry = &per_cpu(cpu_entries, task_cpu(task));
	server = &entry->hrt_server;

	if (is_hrt(task)) {
		BUG_ON(task_cpu(task) != entry->cpu);
		domain = &server->domain;
	} else if (is_srt(task)){
		domain = &srt_domain;
	} else {
		return;
	}

	raw_spin_lock_irqsave(&domain->ready_lock, flags);

	/* Setup job parameters */
	release_at(task, litmus_clock());
	if (running) {
		BUG_ON(entry->scheduled);

		entry->scheduled = task;
		tsk_rt(task)->scheduled_on = task_cpu(task);
	} else {
		task->rt_param.scheduled_on = NO_CPU;
	}

	BUG_ON(task_cpu(task) != entry->cpu);

	task->rt_param.linked_on = NO_CPU;

	requeue(task, domain);

	raw_spin_unlock_irqrestore(&domain->ready_lock, flags);
}

static void edf_hsb_task_wake_up(struct task_struct *task)
{
	struct cpu_entry  *entry;
	struct hrt_server *server;
	rt_domain_t       *domain;
	unsigned long      flags;
	lt_t               now;

	TRACE_TASK(task, "wake_up at %llu\n", litmus_clock());

	entry = &per_cpu(cpu_entries, task_cpu(task));

	if (is_hrt(task)) {
		server = &entry->hrt_server;
		BUG_ON(task_cpu(task) != entry->cpu);
		domain = &server->domain;
	} else {
		domain = &srt_domain;
	}

	raw_spin_lock_irqsave(&domain->ready_lock, flags);

	/* If job resumes after being suspended due to acquiring a semaphore,
	 * it should never be treated as a 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)) {
			/* Re-release the task */
			/* Is this a preemption?? */
			release_at(task, now);
			sched_trace_task_release(task);
		} else {
			if (task->rt.time_slice) {
				/* Woke up before its deadline */
				set_rt_flags(task, RT_F_RUNNING);
			}
		}
	}

	requeue(task, domain);

	raw_spin_unlock_irqrestore(&domain->ready_lock, flags);
}

/*
 * Checks if the current task has expered and whether or not it needs to
 * be preempted.
 */
static void edf_hsb_tick(struct task_struct *t)
{
	/* Reschedule the task if it has run out of time */
	if (is_realtime(t) && budget_enforced(t) && budget_exhausted(t)) {
		if (!is_np(t)) {
			/* Non-preemptable tasks will be preempted when they
			 * become preemptable again */
			litmus_reschedule_local();

			TRACE("edf_hsb_tick: "
			      "%d is preemptable "
			      " => FORCE)RESCHED\n", t->pid);
		} else if (is_user_np(t)) {
			TRACE("edf_hsb_tick: "
			      "%d is non-preemptable, "
			      "preemption delayed.\n", t->pid);
			request_exit_np(t);
		}
	}
}


/******************************************************************************
 * Proc methods
 ******************************************************************************/

static struct proc_dir_entry *edf_hsb_proc_dir = NULL, *hrt_server_proc = NULL;

static int hrt_proc_read(char* page, char **start, off_t off, int count,
		int *eof, void *data)
{
	lt_t wcet, period;
	int cpu, len = 0;
	struct hrt_server *hrt_server;

	for_each_online_cpu(cpu) {

		hrt_server = &per_cpu(cpu_entries, cpu).hrt_server;

		read_lock_irq(&hrt_server->param_lock);

		wcet = hrt_server->wcet;
		period = hrt_server->period;

		/* do_div(x, y) stores the result in x */
		do_div(wcet, NSEC_PER_MSEC);
		do_div(period, NSEC_PER_MSEC);

		read_unlock_irq(&hrt_server->param_lock);

		len += snprintf(page + len, PAGE_SIZE - len,
				"%3d    %8llu    %8llu\n", cpu, wcet, period);
	}

	*eof = 1;
	return len;
}

/* macro to see if we are in the buffer's range and not at the null byte */
#define buf_in_range(buf, pos, max) (buf <= pos && pos < (buf + max)  && *pos)

#define find_newline(buf, pos, max)					\
	do {								\
		while (buf_in_range(buf, pos, max) &&			\
				*pos != '\n')				\
			++pos;						\
	} while (0)

static int hrt_proc_write(struct file *file, const char __user *input,
		unsigned long count, void *data)
{
#define HRT_PROC_BUF 512
	char buffer[HRT_PROC_BUF];
	unsigned long long cpu, wcet, period;
	char *pos, *newline, *space_check;
	int nums_converted, chars_seen, ret;

	if (count >= HRT_PROC_BUF){
		printk(KERN_WARNING "proc buffer possibly too small in %s.\n",
				__func__);
		return -ENOSPC;
	}

	memset(buffer, 0, HRT_PROC_BUF);

	/* input is definitely < HRT_PROC_BUF (see above check) */
	if (copy_from_user(buffer, input, count))
		return -EFAULT;

	buffer[HRT_PROC_BUF-1] = '\0'; /* just making sure :) */

	pos = buffer;

	while (buf_in_range(buffer, pos, HRT_PROC_BUF)) {

		newline = pos;
		find_newline(buffer, newline, HRT_PROC_BUF);
		if (buf_in_range(buffer, newline, HRT_PROC_BUF)) {
			/* if there was a newline character */
			*newline = '\0';
		}

		nums_converted = sscanf(pos, "%llu %llu %llu%n", &cpu, &wcet,
				&period, &chars_seen);
		if (nums_converted != 3) {
			printk(KERN_WARNING "Didn't see 3 integers for HRT "
					"server config: %s\n", pos);
			goto loop_end;
		}

		space_check = pos + chars_seen;
		if (space_check != newline) {
			/*
			 * if the newline was not right after the numbers
			 * converted, ensure extra characters are just space
			 */
			for (; *space_check; space_check++) {
				if (!isspace(*space_check)) {
					printk(KERN_WARNING "Extra characters "
							"in line: %s\n", pos);
					goto loop_end;
				}
			}
		}

		/* finally, set the params */
		ret = set_hrt_params(cpu, wcet, period);
		if (ret) goto loop_end; /* currently, this does nothing */
loop_end:
		pos = newline + 1; /* consider next line */
	}

	return count;
}

#define HRT_SERVER_PROC_NAME "hrt_server"

static void exit_proc(void)
{
	if (hrt_server_proc) {
		remove_proc_entry(HRT_SERVER_PROC_NAME, edf_hsb_proc_dir);
		hrt_server_proc = NULL;
	}

	if (edf_hsb_proc_dir) {
		remove_plugin_proc_dir(&edf_hsb_plugin);
		edf_hsb_proc_dir = NULL;
	}
}


/******************************************************************************
 * Plugin
 ******************************************************************************/

static struct sched_plugin edf_hsb_plugin __cacheline_aligned_in_smp = {
	.plugin_name		= "EDF-HSB",

	/* need not implement all these methods (there are dummy methods) */

	/* setup */
	.activate_plugin	= edf_hsb_activate_plugin,
	.deactivate_plugin	= edf_hsb_deactivate_plugin,

	.schedule		= edf_hsb_schedule,
	.admit_task		= edf_hsb_admit_task,
	.complete_job		= complete_job,
	.release_at		= release_at,
	.task_block		= edf_hsb_task_block,
	.task_exit		= edf_hsb_task_exit,
	.task_new		= edf_hsb_task_new,
	.task_wake_up		= edf_hsb_task_wake_up,
	.tick                   = edf_hsb_tick,
#if 0
	/* scheduler invocation */
	.finish_switch		=,
	/* syscall backend */
	/* task state changes */


#endif
};

static int __init init_edf_hsb(void)
{
	int rv;

	rv = register_sched_plugin(&edf_hsb_plugin);
	if (rv) {
		printk(KERN_ERR "Could not register plugin %s.\n",
				edf_hsb_plugin.plugin_name);
		goto out;
	}

	rv = make_plugin_proc_dir(&edf_hsb_plugin, &edf_hsb_proc_dir);
	if (rv) {
		printk(KERN_ERR "Could not create %s procfs dir.\n",
				edf_hsb_plugin.plugin_name);
		goto out;
	}

	hrt_server_proc = create_proc_entry(HRT_SERVER_PROC_NAME,
			0644, edf_hsb_proc_dir);
	if (!hrt_server_proc) {
		printk(KERN_ERR "Could not create proc entry: %s.\n",
				HRT_SERVER_PROC_NAME);
		rv = -ENOENT;
		goto out_clean_proc;
	}

	hrt_server_proc->read_proc = hrt_proc_read;
	hrt_server_proc->write_proc = hrt_proc_write;

	edf_domain_init(&srt_domain, NULL, edf_hsb_release_jobs);

	initialize_cpu_variables();

	goto out;

out_clean_proc:
	exit_proc();
out:
	return rv;
}

static void exit_edf_hsb(void)
{
	exit_proc();
}

module_init(init_edf_hsb);
module_exit(exit_edf_hsb);