/*
* litmus/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.
*/
#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/edf_common.h>
#include <litmus/sched_trace.h>
#include <litmus/preempt.h>
#include <litmus/bheap.h>
#include <linux/module.h>
DEFINE_PER_CPU(cpu_entry_t, gsnedf_cpu_entries);
#define gsnedf_lock (gsn_edf_plugin.domain.ready_lock)
#ifdef CONFIG_FMLP
static long gsnedf_pi_block(struct pi_semaphore *sem,
struct task_struct *new_waiter);
static long gsnedf_inherit_priority(struct pi_semaphore *sem,
struct task_struct *new_owner);
static long gsnedf_return_priority(struct pi_semaphore *sem);
#endif
/* GSN-EDF Plugin object */
static struct sched_global_plugin gsn_edf_plugin __cacheline_aligned_in_smp = {
.plugin = {
.plugin_name = "GSN-EDF",
.finish_switch = gblv_finish_switch,
.tick = gblv_tick,
.task_new = gblv_task_new,
.complete_job = complete_job,
.task_exit = gblv_task_exit,
.schedule = gblv_schedule,
.task_wake_up = gblv_task_wake_up,
.task_block = gblv_task_block,
#ifdef CONFIG_FMLP
.fmlp_active = 1,
.pi_block = gsnedf_pi_block,
.inherit_priority = gsnedf_inherit_priority,
.return_priority = gsnedf_return_priority,
#endif
.admit_task = gblv_admit_task,
.activate_plugin = gbl_activate_plugin
},
.prio_order = edf_higher_prio,
.take_ready = __take_ready,
.add_ready = __add_ready,
.job_arrival = gblv_job_arrival,
.job_completion = gbl_job_completion,
.preemption_needed = gblv_preemption_needed
};
#ifdef CONFIG_FMLP
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 via %p\n", sem);
/* called with IRQs disabled */
raw_spin_lock(&gsnedf_lock);
/* store new highest-priority task */
sem->hp.task = new_waiter;
if (sem->holder) {
TRACE_TASK(sem->holder,
" holds %p and will inherit from %s/%d\n",
sem,
new_waiter->comm, new_waiter->pid);
/* let holder inherit */
sem->holder->rt_param.inh_task = new_waiter;
gbl_update_queue_position(sem->holder);
}
raw_spin_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 */
raw_spin_lock(&gsnedf_lock);
/* Reset inh_task to NULL. */
t->rt_param.inh_task = NULL;
/* Check if rescheduling is necessary */
gbl_unlink(t);
gsn_edf_plugin.job_arrival(t);
raw_spin_unlock(&gsnedf_lock);
}
return ret;
}
#endif
static int __init init_gsn_edf(void)
{
int cpu;
cpu_entry_t *entry;
bheap_init(&gsn_edf_plugin.cpu_heap);
/* initialize CPU state */
for (cpu = 0; cpu < NR_CPUS; cpu++) {
entry = &per_cpu(gsnedf_cpu_entries, cpu);
gsn_edf_plugin.cpus[cpu] = entry;
entry->cpu = cpu;
entry->hn = &gsn_edf_plugin.heap_node[cpu];
bheap_node_init(&entry->hn, entry);
}
gbl_domain_init(&gsn_edf_plugin, NULL, gbl_release_jobs);
return register_sched_plugin(&gsn_edf_plugin.plugin);
}
module_init(init_gsn_edf);