/*
* litmus/sched_edzl.c
*
* Implementation of the EDZL 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.
*/
#include <linux/spinlock.h>
#include <linux/percpu.h>
#include <linux/sched.h>
#include <litmus/litmus.h>
#include <litmus/jobs.h>
#include <litmus/sched_global_plugin.h>
#include <litmus/edzl_common.h>
#include <litmus/sched_trace.h>
#include <litmus/preempt.h>
#include <litmus/bheap.h>
#include <linux/module.h>
static struct task_struct* __edzl_take_ready(rt_domain_t* rt);
static void __edzl_add_ready(rt_domain_t* rt, struct task_struct *new);
static void edzl_job_arrival(struct task_struct* task);
static void edzl_task_new(struct task_struct * t, int on_rq, int running);
static void edzl_task_wake_up(struct task_struct *task);
static void edzl_task_exit(struct task_struct * t);
static int edzl_preemption_needed(struct task_struct *t);
/* EDZL Plugin object */
static struct sched_global_plugin edzl_plugin __cacheline_aligned_in_smp = {
.plugin = {
.finish_switch = gblv_finish_switch,
.tick = gblv_tick,
.complete_job = complete_job,
.schedule = gblv_schedule,
.task_block = gblv_task_block,
.admit_task = gblv_admit_task,
.activate_plugin = gbl_activate_plugin,
.plugin_name = "EDZL",
.task_new = edzl_task_new,
.task_wake_up = edzl_task_wake_up,
.task_exit = edzl_task_exit,
},
.job_completion = gbl_job_completion,
.prio_order = edzl_higher_prio,
.take_ready = __edzl_take_ready,
.add_ready = __edzl_add_ready,
.job_arrival = edzl_job_arrival,
.preemption_needed = edzl_preemption_needed
};
#define active_gbl_domain (active_gbl_plugin->domain)
#define active_gbl_domain_lock (active_gbl_domain.ready_lock)
DEFINE_PER_CPU(cpu_entry_t, edzl_cpu_entries);
static enum hrtimer_restart on_zero_laxity(struct hrtimer *timer)
{
unsigned long flags;
struct task_struct* t;
lt_t now = litmus_clock();
TRACE("Zero-laxity timer went off!\n");
raw_spin_lock_irqsave(&active_gbl_domain_lock, flags);
t = container_of(container_of(timer, struct rt_param, zl_timer),
struct task_struct,
rt_param);
TRACE_TASK(t, "Reached zero-laxity. (now: %llu, zl-pt: %lld, time remaining (now): %lld)\n",
now,
get_deadline(t) - budget_remaining(t),
get_deadline(t) - now);
set_zerolaxity(t);
gbl_update_queue_position(t);
raw_spin_unlock_irqrestore(&active_gbl_domain_lock, flags);
return HRTIMER_NORESTART;
}
/* __edzl_take_ready - call's __take_ready with EDZL timer cancelation side-effect. */
static struct task_struct* __edzl_take_ready(rt_domain_t* rt)
{
struct task_struct* t = __take_ready(rt);
if(t)
{
if(get_zerolaxity(t) == 0)
{
if(hrtimer_active(&tsk_rt(t)->zl_timer))
{
int cancel_ret;
TRACE_TASK(t, "Canceling zero-laxity timer.\n");
cancel_ret = hrtimer_try_to_cancel(&tsk_rt(t)->zl_timer);
WARN_ON(cancel_ret == 0); /* should never be inactive. */
}
}
else
{
TRACE_TASK(t, "Task already has zero-laxity flagged.\n");
}
}
return t;
}
/* __edzl_add_ready - call's __add_ready with EDZL setting timer side-effect. */
static void __edzl_add_ready(rt_domain_t* rt, struct task_struct *new)
{
__add_ready(rt, new);
if(get_zerolaxity(new) == 0)
{
lt_t when_to_fire;
when_to_fire = get_deadline(new) - budget_remaining(new);
TRACE_TASK(new, "Setting zero-laxity timer for %llu. (deadline: %llu, remaining: %llu)\n",
when_to_fire,
get_deadline(new),
budget_remaining(new));
__hrtimer_start_range_ns(&tsk_rt(new)->zl_timer,
ns_to_ktime(when_to_fire),
0,
HRTIMER_MODE_ABS_PINNED,
0);
}
else
{
TRACE_TASK(new, "Already has zero-laxity when added to ready queue. (deadline: %llu, remaining: %llu))\n",
get_deadline(new),
budget_remaining(new));
}
}
/* edzl_job_arrival: task is either resumed or released */
static void edzl_job_arrival(struct task_struct* task)
{
BUG_ON(!task);
/* clear old laxity flag or tag zero-laxity upon release */
if(laxity_remaining(task))
clear_zerolaxity(task);
else
set_zerolaxity(task);
gbl_requeue(task);
gbl_check_for_preemptions();
}
/* Prepare a task for running in RT mode
*/
static void edzl_task_new(struct task_struct * t, int on_rq, int running)
{
unsigned long flags;
cpu_entry_t* entry;
TRACE("edzl: task new %d\n", t->pid);
raw_spin_lock_irqsave(&active_gbl_domain_lock, flags);
hrtimer_init(&t->rt_param.zl_timer, CLOCK_MONOTONIC, HRTIMER_MODE_ABS);
t->rt_param.zl_timer.function = on_zero_laxity;
/* setup job params */
release_at(t, litmus_clock());
if (running) {
entry = active_gbl_plugin->cpus[task_cpu(t)];
BUG_ON(entry->scheduled);
#ifdef CONFIG_RELEASE_MASTER
if (entry->cpu != active_gbl_domain.release_master) {
#endif
entry->scheduled = t;
tsk_rt(t)->scheduled_on = task_cpu(t);
#ifdef CONFIG_RELEASE_MASTER
} else {
/* do not schedule on release master */
gbl_preempt(entry); /* force resched */
tsk_rt(t)->scheduled_on = NO_CPU;
}
#endif
} else {
t->rt_param.scheduled_on = NO_CPU;
}
t->rt_param.linked_on = NO_CPU;
active_gbl_plugin->job_arrival(t);
raw_spin_unlock_irqrestore(&active_gbl_domain_lock, flags);
}
static void edzl_task_wake_up(struct task_struct *task)
{
unsigned long flags;
lt_t now;
TRACE_TASK(task, "wake_up at %llu\n", litmus_clock());
raw_spin_lock_irqsave(&active_gbl_domain_lock, 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);
}
}
}
active_gbl_plugin->job_arrival(task);
raw_spin_unlock_irqrestore(&active_gbl_domain_lock, flags);
}
static void edzl_task_exit(struct task_struct * t)
{
unsigned long flags;
/* unlink if necessary */
raw_spin_lock_irqsave(&active_gbl_domain_lock, flags);
gbl_unlink(t);
if (tsk_rt(t)->scheduled_on != NO_CPU) {
active_gbl_plugin->cpus[tsk_rt(t)->scheduled_on]->scheduled = NULL;
tsk_rt(t)->scheduled_on = NO_CPU;
}
if(hrtimer_active(&tsk_rt(t)->zl_timer))
{
/* BUG if reached? */
TRACE_TASK(t, "Canceled armed timer while exiting.\n");
hrtimer_cancel(&tsk_rt(t)->zl_timer);
}
raw_spin_unlock_irqrestore(&active_gbl_domain_lock, flags);
BUG_ON(!is_realtime(t));
TRACE_TASK(t, "RIP\n");
}
/* need_to_preempt - check whether the task t needs to be preempted
* call only with irqs disabled and with ready_lock acquired
* THIS DOES NOT TAKE NON-PREEMPTIVE SECTIONS INTO ACCOUNT!
*/
static int edzl_preemption_needed(struct task_struct *t)
{
/* we need the read lock for edf_ready_queue */
/* no need to preempt if there is nothing pending */
if (!__jobs_pending(&active_gbl_domain))
return 0;
/* we need to reschedule if t doesn't exist */
if (!t)
return 1;
/* make sure to get non-rt stuff out of the way */
if (!is_realtime(t))
return 1;
/* NOTE: We cannot check for non-preemptibility since we
* don't know what address space we're currently in.
*/
/* Detect zero-laxity as needed. Easier to do it here than in tick.
(No timer is used to detect zero-laxity while a job is running.) */
if(unlikely(!get_zerolaxity(t) && laxity_remaining(t) == 0))
{
set_zerolaxity(t);
}
return edzl_higher_prio(__next_ready(&active_gbl_domain), t);
}
static int __init init_edzl(void)
{
int cpu;
cpu_entry_t *entry;
bheap_init(&edzl_plugin.cpu_heap);
/* initialize CPU state */
for (cpu = 0; cpu < NR_CPUS; cpu++) {
entry = &per_cpu(edzl_cpu_entries, cpu);
edzl_plugin.cpus[cpu] = entry;
entry->cpu = cpu;
entry->hn = &edzl_plugin.heap_node[cpu];
bheap_node_init(&entry->hn, entry);
}
gbl_domain_init(&edzl_plugin, NULL, gbl_release_jobs);
return register_sched_plugin(&edzl_plugin.plugin);
}
module_init(init_edzl);
