path: root/litmus/sched_gsn_edf.c

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