Work towards slack scheduling (compiles, but not yet complete.)

3 files changed, 183 insertions, 51 deletions

diff --git a/include/litmus/rt_param.h b/include/litmus/rt_param.h
index a7ea5e7b775e..3a456e7135d8 100644
--- a/include/litmus/rt_param.h
+++ b/include/litmus/rt_param.h
@@ -101,6 +101,7 @@ struct rt_job {
         unsigned int    job_no;
 
         lt_t    ghost_budget;
+        int     is_ghost;
 };
 
 struct pfair_param;
diff --git a/litmus/jobs.c b/litmus/jobs.c
index 36e314625d86..99b0bd9858f2 100644
--- a/litmus/jobs.c
+++ b/litmus/jobs.c
@@ -13,6 +13,9 @@ void prepare_for_next_period(struct task_struct *t)
         t->rt_param.job_params.release   = t->rt_param.job_params.deadline;
         t->rt_param.job_params.deadline += get_rt_period(t);
         t->rt_param.job_params.exec_time = 0;
+        /* mixed criticality stuff*/
+        t->rt_param.job_params.is_ghost = 0;
+        t->rt_param.job_params.ghost_budget = 0;
         /* update job sequence number */
         t->rt_param.job_params.job_no++;
 
diff --git a/litmus/sched_mc.c b/litmus/sched_mc.c
index 4db519d86aaf..1fad42aaadf2 100644
--- a/litmus/sched_mc.c
+++ b/litmus/sched_mc.c
@@ -95,7 +95,7 @@ typedef struct  {
         struct task_struct*     scheduled;      /* only RT tasks */
         atomic_t                will_schedule;  /* prevent unneeded IPIs */
         struct bheap_node*      hn;
-        task_struct*            ghost_tasks[CRIT_LEVEL_D+1];
+        struct task_struct*     ghost_tasks[CRIT_LEVEL_D+1];
 } cpu_entry_t;
 
 DEFINE_PER_CPU(cpu_entry_t, mc_cpu_entries);
@@ -110,7 +110,7 @@ cpu_entry_t* mc_cpus[NR_CPUS];
         (atomic_read(&per_cpu(mc_cpu_entries, cpu).will_schedule))
 #define remote_cpu_entry(cpu)   (&per_cpu(mc_cpu_entries, cpu))
 
-#define is_ghost(t)             (tsk_rt(t)->job_params.ghost_budget > 0)
+#define is_ghost(t)             (tsk_rt(t)->job_params.is_ghost)
 
 
 /* the cpus queue themselves according to priority in here */
@@ -257,10 +257,41 @@ static cpu_entry_t* lowest_prio_cpu(void)
         return hn->value;
 }
 
+/* Forward Declarations*/
+static noinline void unlink(struct task_struct* t);
+static noinline void job_completion(struct task_struct *t, int forced);
+
+/* update_ghost_time - Do time accounting for a ghost job.
+ * Updates ghost budget and handles expired ghost budget.
+ * Called from unlink(), mc_tick().
+ * TODO: LOCK ACCOUNTING SHOULD BE CONSIDERED
+ */
+static void update_ghost_time(struct task_struct *p)
+{
+        u64 delta;
+        u64 clock;
+        
+        BUG_ON(!is_ghost(p));
+        clock = cpu_clock(p->rt_param.linked_on);
+        delta = clock - p->se.exec_start;
+        if (unlikely ((s64)delta < 0)) {
+                delta = 0;
+        }
+        if (p->rt_param.job_params.ghost_budget <= delta) {
+                p->rt_param.job_params.ghost_budget = 0;
+                job_completion(p, 0);
+        }
+        else{
+                p->rt_param.job_params.ghost_budget -= delta;
+                p->se.exec_start = clock;
+        }
+}
+
 
 /* link_task_to_cpu - Update the link of a CPU.
  *                    Handles the case where the to-be-linked task is already
  *                    scheduled on a different CPU.
+ *                    Also handles ghost jobs and preemption of ghost jobs.
  *      Called from unlink(), prepare_preemption(), and mc_schedule()
  *      Callers hold global lock
  */
@@ -270,71 +301,112 @@ static noinline void link_task_to_cpu(struct task_struct* linked,
         cpu_entry_t *sched;
         struct task_struct* tmp;
         int on_cpu;
+        int i;
 
         BUG_ON(linked && !is_realtime(linked));
         BUG_ON(linked && is_realtime(linked) &&
                 (linked->rt_param.task_params.crit < CRIT_LEVEL_C) &&
                 (linked->rt_param.task_params.cpu != entry->cpu));
 
-        /* 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(mc_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.
-                         *
-                         * We can only safely swap if neither task is
-                         * partitioned.
-                         */
-                        if (entry != sched &&
-                                linked->rt_param.task_params.crit >
-                                        CRIT_LEVEL_B &&
-                                (!sched->linked ||
-                                sched->linked->rt_param.task_params.crit >
-                                        CRIT_LEVEL_B)){
-                                TRACE_TASK(linked,
-                                           "already scheduled on %d, updating link.\n",
-                                           sched->cpu);
+        if (linked && is_ghost(linked)) {
+                BUG_ON(entry->linked &&
+                        entry->linked->rt_param.task_params.crit <
+                        linked->rt_param.task_params.crit);
+                tmp = entry->ghost_tasks[linked->rt_param.task_params.crit];
+                if (tmp) {
+                        unlink(tmp);
+                }
+                /* We shouldn't link a ghost job that is already somewhere
+                 * else - the caller is responsible for unlinking first.
+                 */
+                BUG_ON(linked->rt_param.linked_on != NO_CPU);
+                linked->rt_param.linked_on = entry->cpu;
+                linked->se.exec_start = cpu_clock(entry->cpu);
+                entry->ghost_tasks[linked->rt_param.task_params.crit] = linked;
+        }
+        else{
+                /* 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(mc_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.
+                                 *
+                                 * Also, we can only safely swap if neither
+                                 * task is partitioned.
+                                 */
                                 tmp = sched->linked;
-                                linked->rt_param.linked_on = sched->cpu;
-                                sched->linked = linked;
-                                update_cpu_position(sched);
-                                linked = tmp;
+                                if (entry != sched &&
+                                        linked->rt_param.task_params.crit >
+                                                CRIT_LEVEL_B &&
+                                        (!tmp || tmp->rt_param.task_params.crit
+                                                > CRIT_LEVEL_B)) {
+                                        TRACE_TASK(linked,
+                                                   "already scheduled on %d, updating link.\n",
+                                                   sched->cpu);
+                                        linked->rt_param.linked_on = sched->cpu;
+                                        sched->linked = linked;
+                                        for (i = linked->
+                                                rt_param.task_params.crit;
+                                                i < CRIT_LEVEL_D + 1; i++) {
+                                                if (sched->ghost_tasks[i]){
+                                                        unlink(sched->
+                                                                ghost_tasks[i]);
+                                                }
+                                        }
+                                        update_cpu_position(sched);
+                                        linked = tmp;
+                                }
+                        }
+                        if (linked) { /* might be NULL due to swap */
+                                linked->rt_param.linked_on = entry->cpu;
+                                for (i = linked->rt_param.task_params.crit;
+                                        i < CRIT_LEVEL_D + 1; i++){
+                                        if (entry->ghost_tasks[i]){
+                                                unlink(entry->ghost_tasks[i]);
+                                                /*TODO: make sure booted tasks
+                                                 * get rescheduled if needed
+                                                 */
+                                        }
+                                }
                         }
                 }
-                if (linked) /* might be NULL due to swap */
-                        linked->rt_param.linked_on = entry->cpu;
+                entry->linked = linked;
         }
-        entry->linked = linked;
 #ifdef WANT_ALL_SCHED_EVENTS
-        if (linked)
-                TRACE_TASK(linked, "linked to %d.\n", entry->cpu);
-        else
-                TRACE("NULL linked to %d.\n", entry->cpu);
+                if (linked)
+                        TRACE_TASK(linked, "linked to %d.\n", entry->cpu);
+                else
+                        TRACE("NULL linked to %d.\n", entry->cpu);
 #endif
         update_cpu_position(entry);
 }
 
 /* unlink - Make sure a task is not linked any longer to a cpu entry
  *          where it was linked before.
+ *          Can handle ghost jobs.
  *      Called by schedule, task_block, task_exit, and job_completion
  *      Caller assumed to hold global lock
  */
 static noinline void unlink(struct task_struct* t)
 {
+        int cpu;
         cpu_entry_t *entry;
 
         if (unlikely(!t)) {
@@ -342,11 +414,41 @@ static noinline void unlink(struct task_struct* t)
                 return;
         }
 
-        if (t->rt_param.linked_on != NO_CPU) {
+        cpu = t->rt_param.linked_on;
+        if (cpu != NO_CPU) {
                 /* unlink */
-                entry = &per_cpu(mc_cpu_entries, t->rt_param.linked_on);
+                entry = remote_cpu_entry(cpu);
                 t->rt_param.linked_on = NO_CPU;
-                link_task_to_cpu(NULL, entry);
+                if (is_ghost(t)) {
+                        if (t->rt_param.job_params.ghost_budget > 0){
+                                /* Job isn't finished, so do accounting. */
+                                update_ghost_time(t);
+                                /* Need to check again since accounting might
+                                 * change value.
+                                 */
+                                if (t->rt_param.job_params.ghost_budget > 0) {
+                                        /* Still have budget, so just remove
+                                         * from CPU
+                                         */
+                                        entry->ghost_tasks[
+                                                t->rt_param.task_params.crit]
+                                                = NULL;
+                                        /*TODO: maybe make more efficient by
+                                         * only updating on C/D completion?
+                                         */
+                                        update_cpu_position(entry);
+                                }
+                        }
+                        else{
+                                /* Job finished, so just remove */
+                                entry->ghost_tasks[
+                                        t->rt_param.task_params.crit] = NULL;
+                                update_cpu_position(entry);
+                        }
+                }
+                else {
+                        link_task_to_cpu(NULL, entry);
+                }
         } else if (is_queued(t)) {
                 /* This is an interesting situation: t is scheduled,
                  * but was just recently unlinked.  It cannot be
@@ -473,9 +575,12 @@ static void mc_release_jobs(rt_domain_t* rt, struct bheap* tasks)
 /* caller holds global_lock
  * Called only by mc_schedule() which holds global lock
  * Prepares task for next period, unlinks it, and calls mc_job_arrival
+ * Converts jobs to ghost jobs as necessary, or finishes end of ghost jobs.
 */
 static noinline void job_completion(struct task_struct *t, int forced)
 {
+        cpu_entry_t *cpu;
+        int already_unlinked = 0;
         BUG_ON(!t);
 
         sched_trace_task_completion(t, forced);
@@ -484,18 +589,37 @@ static noinline void job_completion(struct task_struct *t, int forced)
 
         /* set flags */
         set_rt_flags(t, RT_F_SLEEP);
+        /*If it's not a ghost job, do ghost job conversion and return.*/
+        if (!is_ghost(t)) {
+                cpu = remote_cpu_entry(t->rt_param.scheduled_on);
+                /*Unlink first while it's not a ghost job.*/
+                unlink(t);
+                already_unlinked = 1;
+                t->rt_param.job_params.ghost_budget = budget_remaining(t);
+                t->rt_param.job_params.is_ghost = 1;
+                /* If we did just convert the job to ghost, we can safely
+                 * reschedule it and then let schedule() determine a new
+                 * job to run in the slack.
+                 */
+                if (t->rt_param.job_params.ghost_budget > 0){
+                        link_task_to_cpu(t, cpu);
+                        preempt(cpu);
+                        return;
+                }
+        }
         /* prepare for next period */
         if (is_ghost(t)) {
                 t->rt_param.job_params.ghost_budget = 0;
                 prepare_for_next_period(t);
         }
         else {
-                t->rt_param.job_params.ghost_budget = budget_remaining(t)
+                t->rt_param.job_params.ghost_budget = budget_remaining(t);
         }
         if (is_released(t, litmus_clock()))
                 sched_trace_task_release(t);
-        /* unlink */
-        unlink(t);
+        /* unlink if we didn't above */
+        if (!already_unlinked)
+                unlink(t);
         /* requeue
          * But don't requeue a blocking task. */
         if (is_running(t))
@@ -513,6 +637,9 @@ static noinline void job_completion(struct task_struct *t, int forced)
  */
 static void mc_tick(struct task_struct* t)
 {
+        if (is_ghost(t)) {
+                update_ghost_time(t);
+        }
         if (is_realtime(t) && budget_enforced(t) && budget_exhausted(t)) {
                 if (!is_np(t)) {
                         /* np tasks will be preempted when they become
@@ -718,6 +845,7 @@ static void mc_task_new(struct task_struct * t, int on_rq, int running)
         /* setup job params */
         release_at(t, litmus_clock());
         t->rt_param.job_params.ghost_budget = 0;
+        t->rt_param.job_params.is_ghost = 0;
 
         if (running) {
                 entry = &per_cpu(mc_cpu_entries, task_cpu(t));