Implement background scheduling

This turned out to be incredibly complicated. High-level changes are:
1. Container completion in g_job_completion() has been completely
   reworked. We now check for and appropriately handle all possible
   states of a background scheduled task.
2. edfsc_cschedule() has had its fixed task scheduling logic overhauled
   to be easier to follow. This fixes the logic for when a fixed task
   preempts a background scheduled task, but may also fix other bugs.
3. When a task blocks while being background scheduled, remove that
   task, NOT the container scheduling that task.
4. Update `entry->scheduled` at the end of edfsc_gschedule(). We will
   not run g_finish_switch() if we continue scheduling the same task,
   but we still need entry->scheduled to be updated in the case when
   we stop background scheduling and switch to normal scheduling. The
   original code that sets `entry->scheduled` in g_finish_switch()
   may no longer be needed and further investigation of its removal
   is encouraged.
5. If a task exits while being background scheduled, remove it from
   the container rather than `entry->scheduled`.

1 files changed, 64 insertions, 31 deletions

diff --git a/litmus/sched_edfsc.c b/litmus/sched_edfsc.c
index a91951480f33..8ae94f2dc1df 100644
--- a/litmus/sched_edfsc.c
+++ b/litmus/sched_edfsc.c
@@ -436,10 +436,6 @@ static void c_release(struct task_struct *t) {
                 if (!bheap_node_in_heap(entry->hn))
                         add_cpu_to_global(entry);
                 // Note that container's aren't real tasks and thus can't block
-                if (tsk_rt(t)->edfsc_params.domain->scheduled) {
-                        requeue(tsk_rt(t)->edfsc_params.domain->scheduled);
-                        tsk_rt(t)->edfsc_params.domain->scheduled = NULL;
-                }
                 // Let g_preempt_check() decide what to run, don't impose
                 unlink(t);
                 // Request to be scheduled globally again
@@ -482,12 +478,44 @@ static noinline void g_job_completion(struct task_struct* t, int forced)
                         requeue(t);
                         g_preempt_check();
                 }
-        // When a container job finishes late
-        } else if (is_container(t) && tsk_rt(t)->edfsc_params.can_release) {
-                tsk_rt(t)->edfsc_params.can_release = 0;
-                c_release(t);
-                if (get_rt_utilization(t) == to_fp(1))
-                        manage_idle_enforcement_timer(t);
+        /* A container may be in several different states when it finishes. It may:
+         * - Be scheduling a migrating task that is finished, blocked, or out of budget
+         * - Be scheduling a fixed task
+         * - Be scheduling nothing
+         * If there's a migrating task being scheduled, we can't unconditionally
+         * requeue it. Often, we may actually have to call g_job_completion() on
+         * that migrating task. If we finish while running a fixed task, we just
+         * "freeze" it in the container - edfsc_cschedule() will take care of
+         * processing its state when the container is rescheduled.
+         *
+         * If the container is tardy, we process its scheduled task as in the non-
+         * tardy case, then just immediately call c_release() on the container.
+         */
+        } else if (is_container(t)) {
+                struct task_struct** child = &tsk_rt(t)->edfsc_params.domain->scheduled;
+                // No need to handle fixed tasks, cschedule will do that when it runs next
+                if (*child && is_migrating(*child)) {
+                        BUG_ON(is_queued(*child));
+                        // If migrating and done
+                        if (is_completed(*child) || (budget_enforced(*child) && budget_exhausted(*child))) {
+                                g_job_completion(*child, budget_enforced(*child) && budget_exhausted(*child));
+                        // If migrating and blocked
+                        } else if (!is_current_running()) {
+                                unlink(*child);
+                        // Otherwise it can keep running globally
+                        } else {
+                                requeue(*child);
+                        }
+                        // Regardless, we never "freeze" a migrating task in a container
+                        *child = NULL;
+                }
+                // When a container job finishes late, release it immediately
+                if (tsk_rt(t)->edfsc_params.can_release) {
+                        tsk_rt(t)->edfsc_params.can_release = 0;
+                        c_release(t);
+                        if (get_rt_utilization(t) == to_fp(1))
+                                manage_idle_enforcement_timer(t);
+                }
         }
 }
 
@@ -585,11 +613,6 @@ static void edfsc_cschedule(cont_domain_t* cedf, struct task_struct * prev)
          */
         resched = preempt;
 
-        /* If a task blocks we have no choice but to reschedule.
-         */
-        if (blocks)
-                resched = 1;
-
         /* Request a sys_exit_np() call if we would like to preempt but cannot.
          * Multiple calls to request_exit_np() don't hurt.
          */
@@ -608,24 +631,24 @@ static void edfsc_cschedule(cont_domain_t* cedf, struct task_struct * prev)
                 resched = 1;
         }
 
+        // Deschedule any background jobs if a fixed task is ready
+        if (is_migrating(cedf->scheduled) && preempt) {
+                if (!sleep && !out_of_time && !blocks && !is_queued(cedf->scheduled))
+                        requeue(cedf->scheduled);
+                resched = 1;
+        }
+
         /* The final scheduling decision. Do we need to switch for some reason?
          * Switch if we are in RT mode and have no task or if we need to
          * resched.
          */
         next = NULL;
-        if ((!np || blocks) && (resched || !exists)) {
-                /* When preempting a task that does not block, then
-                 * re-insert it into either the ready queue or the
-                 * release queue (if it completed). requeue() picks
-                 * the appropriate queue.
-                 */
+        if (blocks || !exists || (!np && resched)) {
                 next = __take_ready(edf);
         } else if (exists) {
-                BUG_ON(!is_realtime(prev));
-                /* Only override Linux scheduler if we have a real-time task
-                 * scheduled that needs to continue.
-                 */
-                next = prev;
+                // This is safe when background scheduling, as we can only get here if
+                // there were no other fixed tasks ready to run.
+                next = cedf->scheduled;
         }
 
         if (next) {
@@ -706,10 +729,10 @@ static struct task_struct *edfsc_gschedule(struct task_struct *prev)
 
 
         /* If a task blocks we have no choice but to reschedule.
-         * Note: containers never block
+         * Note: containers never block, so if blocks is true and we're background
+         * scheduling, we want to unlink `prev` NOT `entry->scheduled`.
          */
-        if (blocks)
-                unlink(entry->scheduled);
+                unlink(prev);
 
         /* Request a sys_exit_np() call if we would like to preempt but cannot.
          * We need to make sure to update the link structure anyway in case
@@ -788,6 +811,10 @@ static struct task_struct *edfsc_gschedule(struct task_struct *prev)
 
         // Tell LITMUS^RT that we choose a task and are done scheduling after return
         sched_state_task_picked();
+        // When we transition from doing background scheduling to doing normal
+        // scheduling, we may schedule the same task. Unfortunately, when this
+        // happens, g_finish_switch() will /not/ be called. Fix the state manually.
+        entry->scheduled = next;
 
         // if no fixed tasks to be scheduled by the container, then container->scheduled
         // should be the previous non-rt task if any
@@ -1091,8 +1118,14 @@ static void edfsc_task_exit(struct task_struct* t)
                 BUG_ON(t != current);
                 list_del(&t->edfsc_qnode);
                 entry = &per_cpu(edfsc_cpu_entries, task_cpu(t));
-                BUG_ON(entry->scheduled != t);
-                entry->scheduled = NULL;
+                // Handle the case where we exit while being background scheduled
+                if (is_container(entry->scheduled)) {
+                        BUG_ON(entry->scheduled->rt_param.edfsc_params.domain->scheduled != t);
+                        entry->scheduled->rt_param.edfsc_params.domain->scheduled = NULL;
+                } else {
+                        BUG_ON(entry->scheduled != t);
+                        entry->scheduled = NULL;
+                }
         }
 
         /* To preserve EDF-sc scheduling invariants, we can only release a task's