copied global edf scheduler plugin

This will be the GSN-EDF scheduler.

2 files changed, 455 insertions, 1 deletions

diff --git a/kernel/Makefile b/kernel/Makefile
index 5cd2351484..dc4de6314a 100644
--- a/kernel/Makefile
+++ b/kernel/Makefile
@@ -11,7 +11,8 @@ obj-y     = sched.o fork.o exec_domain.o panic.o printk.o profile.o \
             hrtimer.o rwsem.o latency.o nsproxy.o srcu.o \
             sched_plugin.o litmus.o sched_trace.o \
             edf_common.o fifo_common.o pfair_common.o\
-            sched_global_edf.o sched_part_edf.o sched_edf_hsb.o sched_pfair.o
+            sched_global_edf.o sched_part_edf.o sched_edf_hsb.o sched_pfair.o \
+            sched_gsn_edf.o
 
 obj-$(CONFIG_STACKTRACE) += stacktrace.o
 obj-y += time/
diff --git a/kernel/sched_gsn_edf.c b/kernel/sched_gsn_edf.c
new file mode 100644
index 0000000000..c1b4498431
--- /dev/null
+++ b/kernel/sched_gsn_edf.c
@@ -0,0 +1,453 @@
+/*
+ * kernel/sched_gsn_edf.c
+ *
+ * Implementation of the GSN-EDF scheduling algorithm.
+ *
+ * This version works without using the struct queue. It uses the
+ * builtin kernel lists.
+ */
+
+#include <linux/percpu.h>
+#include <linux/sched.h>
+#include <linux/list.h>
+
+#include <linux/litmus.h>
+#include <linux/sched_plugin.h>
+#include <linux/edf_common.h>
+#include <linux/sched_trace.h>
+
+
+/* cpu_entry_t - maintain state of the priority of cpu's current task
+ *               this is needed to check for priority inversions.
+ */
+typedef struct  {
+        int                     cpu;
+        int                     executes_realtime;
+        jiffie_t                cur_deadline;
+        struct list_head        list;
+        atomic_t                will_schedule;
+} cpu_entry_t;
+DEFINE_PER_CPU(cpu_entry_t, gsnedf_cpu_entries);
+
+#define set_will_schedule() \
+        (atomic_set(&__get_cpu_var(gsnedf_cpu_entries).will_schedule, 1))
+#define clear_will_schedule() \
+        (atomic_set(&__get_cpu_var(gsnedf_cpu_entries).will_schedule, 0))
+#define test_will_schedule(cpu) \
+        (atomic_read(&per_cpu(gsnedf_cpu_entries, cpu).will_schedule))
+
+
+/* always acquire the cpu lock as the last lock to avoid deadlocks */
+static spinlock_t gsnedf_cpu_lock = SPIN_LOCK_UNLOCKED;
+/* the cpus queue themselves according to priority in here */
+static LIST_HEAD(gsnedf_cpu_queue);
+
+
+static edf_domain_t gsnedf;
+
+#define DUMP(args...) TRACE(args)
+
+/* adjust_cpu_queue - Move the cpu entry to the correct place to maintain 
+ *                    order in the cpu queue. Caller must hold ready write lock.
+ *
+ */
+static void adjust_cpu_queue(int exec_rt, jiffie_t deadline) 
+{
+        struct list_head *pos;
+        cpu_entry_t *other;
+        cpu_entry_t *entry;
+
+        spin_lock(&gsnedf_cpu_lock);
+
+        entry = &__get_cpu_var(gsnedf_cpu_entries);
+        entry->executes_realtime = exec_rt;
+        entry->cur_deadline      = deadline;
+
+        /* TODO: move instead of del+reinsert */
+        list_del(&entry->list);
+        /* if we do not execute real-time jobs we just move 
+         * to the end of the queue 
+         */
+        if (entry->executes_realtime)
+                list_for_each(pos, &gsnedf_cpu_queue) {
+                        other = list_entry(pos, cpu_entry_t, list);
+                        if (!other->executes_realtime || 
+                            time_before_eq(entry->cur_deadline, 
+                                           other->cur_deadline))
+                        {
+                                __list_add(&entry->list, pos->prev, pos);
+                                goto out;
+                        }
+                }
+        /* if we get this far we have the lowest priority task */
+        list_add_tail(&entry->list, &gsnedf_cpu_queue);                 
+
+ out:
+        spin_unlock(&gsnedf_cpu_lock);
+}
+
+
+/* check_reschedule_needed - Check whether another CPU needs to reschedule.
+ *
+ * The function only checks and kicks the last CPU. It will reschedule and 
+ * kick the next if necessary, and so on. The caller is responsible for making
+ * sure that it is not the last entry or that a reschedule is not necessary.
+ *
+ * TODO: This function is probably way too trigger happy. It should only send
+ *       IPIs if the other CPU is not  going to reschedule anyway. But that is 
+ *       hard to detect reliably. Too many schedules will hurt performance 
+ *       but do not cause incorrect schedules.
+ */
+static int gsnedf_check_resched(edf_domain_t *edf) 
+{
+        cpu_entry_t *last;
+        int ret = 0;
+
+        spin_lock(&gsnedf_cpu_lock);
+
+        if (!list_empty(&edf->ready_queue)) {
+                last = list_entry(gsnedf_cpu_queue.prev, cpu_entry_t, list);
+                if (!last->executes_realtime || 
+                    time_before(next_ready(edf)->rt_param.times.deadline,
+                                last->cur_deadline))
+                {
+                        if (smp_processor_id() == last->cpu)
+                                set_tsk_need_resched(current);
+                        else
+                                if (!test_will_schedule(last->cpu))
+                                    smp_send_reschedule(last->cpu);
+                        ret = 1;
+                }
+        }
+
+        spin_unlock(&gsnedf_cpu_lock);
+        return ret;
+}
+
+
+
+/* gsnedf_scheduler_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 reschedule_check_t gsnedf_scheduler_tick(void)
+{
+        unsigned long flags;
+        struct task_struct *t = current;
+        reschedule_check_t want_resched = NO_RESCHED;
+
+        /* expire tasks even if not in real-time mode
+         * this makes sure that at the end of real-time mode
+         * no tasks "run away forever".
+         */
+        BUG_ON(is_realtime(t) && t->time_slice > 100000);
+        if (is_realtime(t) && (!--t->time_slice)) {
+                /* this task has exhausted its budget in this period */
+                set_rt_flags(t, RT_F_SLEEP);
+                want_resched = FORCE_RESCHED;
+                set_will_schedule();
+                sched_trace_job_completion(t);
+        } 
+        if (get_rt_mode() == MODE_RT_RUN)
+        {
+                /* check whether anything is waiting to be released 
+                 * this could probably be moved to the global timer
+                 * interrupt handler since the state will only change
+                 * once per jiffie
+                 */
+                try_release_pending(&gsnedf);
+                if (want_resched != FORCE_RESCHED)
+                {
+                        read_lock_irqsave(&gsnedf.ready_lock, flags);
+                        if (preemption_needed(&gsnedf, t))
+                        {
+                                want_resched = FORCE_RESCHED;
+                                set_will_schedule();
+                        }
+                        read_unlock_irqrestore(&gsnedf.ready_lock, flags);
+                }
+        }       
+        return want_resched;
+}
+
+/* This is main Global EDF schedule function
+ * 
+ * Assumes the caller holds the lock for rq and that irqs are disabled
+ * This is function only works for indirect switching
+ */
+static int gsnedf_schedule(struct task_struct * prev, 
+                         struct task_struct ** next, 
+                         runqueue_t * rq)
+{
+        int             need_deactivate = 1;
+        int             rt;
+        jiffie_t        deadline;
+        unsigned long   flags;
+
+
+        if (is_realtime(prev) && get_rt_flags(prev) == RT_F_SLEEP)
+        {
+                DUMP("preparing %d for next period\n", prev->pid);
+                prepare_for_next_period(prev);  
+        }
+        
+        if (get_rt_mode() == MODE_RT_RUN) {
+                write_lock_irqsave(&gsnedf.ready_lock, flags);
+
+                clear_will_schedule();
+
+                if (is_realtime(prev) && is_released(prev) && is_running(prev)
+                    && !preemption_needed(&gsnedf, prev)) {
+                        /* Our current task's next job has already been 
+                         * released and has higher priority than the highest
+                         * prioriy waiting task; in other words: it is tardy.
+                         * We just keep it.
+                         */
+                        DUMP("prev will be next, already released\n");
+                        *next = prev;
+                        rt = 1;
+                        deadline = prev->rt_param.times.deadline;
+                        need_deactivate = 0;
+                } else {
+                        /* either not yet released, preempted, or non-rt */
+                        *next = __take_ready(&gsnedf);
+                        if (*next) {
+                                /* mark the task as executing on this cpu */
+                                set_task_cpu(*next, smp_processor_id());
+                                
+                                /* stick the task into the runqueue */
+                                __activate_task(*next, rq);
+                                rt = 1;
+                                deadline = (*next)->rt_param.times.deadline;
+                        } 
+                        else
+                                rt = deadline = 0;                      
+                }
+
+                adjust_cpu_queue(rt, deadline);
+
+                if (rt) {
+                        set_rt_flags(*next, RT_F_RUNNING);
+                        gsnedf.check_resched(&gsnedf);
+                }
+                write_unlock_irqrestore(&gsnedf.ready_lock, flags);
+        } 
+
+        if (is_realtime(prev) && need_deactivate && prev->array) {
+                /* take it out of the run queue */
+                deactivate_task(prev, rq);
+        }
+        
+        /* don't put back into release yet. 
+         * We first need to actually switch 
+         * stacks before we can execute it 
+         * on a different CPU */
+        
+        /* in the current implementation nobody cares about the return value */
+        return 0;
+}
+
+
+/* _finish_switch - we just finished the switch away from prev
+ *                  it is now safe to requeue the task
+ */
+static void gsnedf_finish_switch(struct task_struct *prev) 
+{
+        /*printk(KERN_INFO "gsnedf finish switch for %d\n", prev->pid);*/
+        if (get_rt_flags(prev) == RT_F_SLEEP || 
+            get_rt_mode() != MODE_RT_RUN) {
+                /* this task has expired
+                 * _schedule has already taken care of updating 
+                 * the release and
+                 * deadline. We just must check if has been released.
+                 */
+                if (time_before_eq(prev->rt_param.times.release, jiffies) 
+                    && get_rt_mode() == MODE_RT_RUN) {
+                        /* already released */
+                        add_ready(&gsnedf, prev);
+                        DUMP("%d goes straight to ready queue\n", prev->pid);
+                }
+                else 
+                        /* it has got to wait */
+                        add_release(&gsnedf, prev);             
+        }
+        else {
+                /* this is a forced preemption 
+                 * thus the task stays in the ready_queue
+                 * we only must make it available to others
+                 */
+                add_ready(&gsnedf, prev);
+        }       
+}
+
+
+/*      Prepare a task for running in RT mode
+ *      Enqueues the task into master queue data structure
+ *      returns 
+ *              -EPERM  if task is not TASK_STOPPED
+ */
+static long gsnedf_prepare_task(struct task_struct * t)
+{
+        TRACE("global edf: prepare task %d\n", t->pid);
+
+        if (t->state == TASK_STOPPED) {
+                __setscheduler(t, SCHED_FIFO, MAX_RT_PRIO - 1);
+
+                if (get_rt_mode() == MODE_RT_RUN)
+                        /* The action is already on. 
+                         * Prepare immediate release
+                         */
+                        prepare_new_release(t);
+                /* The task should be running in the queue, otherwise signal 
+                 * code will try to wake it up with fatal consequences.
+                 */
+                t->state = TASK_RUNNING; 
+                add_release(&gsnedf, t);
+                return 0;
+        }
+        else
+                return -EPERM;
+}
+
+static void gsnedf_wake_up_task(struct task_struct *task) 
+{
+        /* We must determine whether task should go into the release       
+         * queue or into the ready queue. It may enter the ready queue 
+         * if it has credit left in its time slice and has not yet reached 
+         * its deadline. If it is now passed its deadline we assume this the 
+         * arrival of a new sporadic job and thus put it in the ready queue 
+         * anyway.If it has zero budget and the next release is in the future 
+         * it has to go to the release queue.
+         */
+        TRACE("global edf: wake up %d with budget=%d\n", 
+              task->pid, task->time_slice);
+        task->state = TASK_RUNNING;
+        if (is_tardy(task)) {
+                /* new sporadic release */
+                prepare_new_release(task);
+                sched_trace_job_release(task);
+                add_ready(&gsnedf, task);
+        }
+        else if (task->time_slice) {
+                /* came back in time before deadline
+                 * TODO: clip budget to fit into period, otherwise it could 
+                 *       cause a deadline overrun in the next period, i.e. 
+                 *       over allocation in the next period.
+                 */
+                set_rt_flags(task, RT_F_RUNNING);
+                add_ready(&gsnedf, task);
+        }
+        else {
+                add_release(&gsnedf, task);
+        }
+                
+}
+
+static void gsnedf_task_blocks(struct task_struct *t)
+{
+        BUG_ON(!is_realtime(t));
+        /* not really anything to do since it can only block if 
+         * it is running, and when it is not running it is not in any 
+         * queue anyway.
+         *
+         * TODO: Check whether the assumption is correct for SIGKILL and 
+         *       SIGSTOP.
+         */
+        TRACE("task %d blocks with budget=%d\n", t->pid, t->time_slice);
+        BUG_ON(t->rt_list.next != LIST_POISON1);
+        BUG_ON(t->rt_list.prev != LIST_POISON2);
+}
+
+
+/* When _tear_down is called, the task should not be in any queue any more
+ * as it must have blocked first. We don't have any internal state for the task,
+ * it is all in the task_struct.
+ */
+static long gsnedf_tear_down(struct task_struct * t)
+{
+        BUG_ON(!is_realtime(t));
+        TRACE("global edf: tear down called for %d \n", t->pid);
+        BUG_ON(t->array);
+        BUG_ON(t->rt_list.next != LIST_POISON1);
+        BUG_ON(t->rt_list.prev != LIST_POISON2);
+        return 0;
+}
+
+
+static int gsnedf_mode_change(int new_mode)
+{
+        int cpu;
+        cpu_entry_t *entry;
+
+/*      printk(KERN_INFO "[%d] global edf: mode changed to %d\n", smp_processor_id(), 
+        new_mode);*/
+        if (new_mode == MODE_RT_RUN) {
+                prepare_new_releases(&gsnedf, jiffies + 10);
+                
+                /* initialize per CPU state 
+                 * we can't do this at boot time because we don't know
+                 * which CPUs will be online and we can't put non-existing
+                 * cpus into the queue
+                 */
+                spin_lock(&gsnedf_cpu_lock);
+                /* get old cruft out of the way in case we reenter real-time
+                 * mode for a second time
+                 */
+                while (!list_empty(&gsnedf_cpu_queue))
+                        list_del(gsnedf_cpu_queue.next);
+                /* reinitialize */
+                for_each_online_cpu(cpu) {
+                        entry = &per_cpu(gsnedf_cpu_entries, cpu);
+                        atomic_set(&entry->will_schedule, 0);
+                        entry->executes_realtime = 0;
+                        entry->cur_deadline      = 0;
+                        entry->cpu               = cpu;
+                        list_add(&entry->list, &gsnedf_cpu_queue);
+                }               
+                spin_unlock(&gsnedf_cpu_lock);
+        }
+        /*printk(KERN_INFO "[%d] global edf: mode change done\n", smp_processor_id()); */
+        return 0;
+}
+
+
+/*      Plugin object   */
+static sched_plugin_t s_plugin __cacheline_aligned_in_smp = {
+        .ready_to_use = 0 
+};
+
+
+/*
+ *      Plugin initialization code.
+ */
+#define INIT_SCHED_PLUGIN (struct sched_plugin){\
+        .plugin_name            = "GSN-EDF",\
+        .ready_to_use           = 1,\
+        .algo_scheduler_tick    = gsnedf_scheduler_tick,\
+        .scheduler_tick         = rt_scheduler_tick,\
+        .prepare_task           = gsnedf_prepare_task,\
+        .sleep_next_period      = edf_sleep_next_period,\
+        .tear_down              = gsnedf_tear_down,\
+        .shutdown_hook          = 0,\
+        .schedule               = gsnedf_schedule,\
+        .finish_switch          = gsnedf_finish_switch,\
+        .mode_change            = gsnedf_mode_change,\
+        .wake_up_task           = gsnedf_wake_up_task,\
+        .task_blocks            = gsnedf_task_blocks \
+        }
+
+
+sched_plugin_t *__init init_gsn_edf_plugin(void)
+{
+        if (!s_plugin.ready_to_use)
+        {
+                set_sched_options(SCHED_NONE);
+                edf_domain_init(&gsnedf, gsnedf_check_resched);
+                s_plugin = INIT_SCHED_PLUGIN;
+        }
+        return &s_plugin;
+}
+
+