DRAIN_SIMPLE_IO: drain on execution or I/O suspend

New budget drain policy drains while task is executing
or suspends for a non-litmus-lock (non-real-time, such
as for I/O) reason.

6 files changed, 249 insertions, 10 deletions

diff --git a/include/litmus/budget.h b/include/litmus/budget.h
index b70364e53582..d5d4d61eb06a 100644
--- a/include/litmus/budget.h
+++ b/include/litmus/budget.h
@@ -75,6 +75,18 @@ void simple_on_sleep(struct task_struct* t);
 void simple_on_exit(struct task_struct* t);
 
 
+/* Functions for DRAIN_SIMPLE_IO policy common
+ * to every scheduler. Scheduler must provide
+ * implementation for simple_io_on_exhausted().
+ */
+#define simple_io_on_scheduled  simple_on_scheduled
+void simple_io_on_blocked(struct task_struct* t);
+void simple_io_on_wakeup(struct task_struct* t);
+#define simple_io_on_preempt    simple_on_preempt
+#define simple_io_on_sleep      simple_on_sleep
+#define simple_io_on_exit       simple_on_exit
+
+
 /* Functions for DRAIN_SOBLIV policy common
  * to every scheduler. Scheduler must provide
  * implementation for sobliv_on_exhausted().
@@ -89,7 +101,7 @@ void sobliv_on_disinherit(struct task_struct* t, struct task_struct* prio_inh);
 void sobliv_on_enter_top_m(struct task_struct* t);
 void sobliv_on_exit_top_m(struct task_struct* t);
 
-void sobliv_revaluate_task(struct task_struct* t);
+void reevaluate_inheritance(struct task_struct* t);
 
 #define budget_state_machine(t, evt) \
         do { \
diff --git a/include/litmus/jobs.h b/include/litmus/jobs.h
index 4f311a4a2a4b..ec73cc6ae7f8 100644
--- a/include/litmus/jobs.h
+++ b/include/litmus/jobs.h
@@ -22,7 +22,7 @@ typedef struct
 #define DECLARE_WORKER_VIS_FLAGS(symb) \
         worker_visibility_t symb = {0, 0, 0, 0}
 #else
-#define DECLARE_WORKER_VIS_FLAGS(var) \
+#define DECLARE_WORKER_VIS_FLAGS(symb) \
         worker_visibility_t symb = {0, 0}
 #endif
 
diff --git a/include/litmus/rt_param.h b/include/litmus/rt_param.h
index 7828117a61a8..c480d95690f8 100644
--- a/include/litmus/rt_param.h
+++ b/include/litmus/rt_param.h
@@ -39,6 +39,7 @@ typedef enum {
         /* all drain mechanisms are ignored if budget enforcement or signalling
            is not in use. */
         DRAIN_SIMPLE,   /* drains while task is linked */
+        DRAIN_SIMPLE_IO, /* drains while task is linked or blocked (not waiting for Litmus lock) */
         DRAIN_SAWARE,   /* drains according to suspension-aware analysis */
         DRAIN_SOBLIV,   /* drains according to suspension-obliv analysis */
 } budget_drain_policy_t;
diff --git a/litmus/budget.c b/litmus/budget.c
index 4b464c4d8507..9ae530ad3b2b 100644
--- a/litmus/budget.c
+++ b/litmus/budget.c
@@ -157,6 +157,68 @@ void simple_on_exit(struct task_struct* t)
 }
 
 /*
+ * DRAIN_SIMPLE_IO
+ */
+
+void simple_io_on_blocked(struct task_struct* t)
+{
+        // hiding is turned on by locking protocols, so if there isn't any
+        // hiding, then we're blocking for some other reason.  assume it's I/O.
+
+        int for_io = !tsk_rt(t)->blocked_lock || (0
+#ifdef CONFIG_REALTIME_AUX_TASKS
+                || (tsk_rt(t)->has_aux_tasks && !tsk_rt(t)->hide_from_aux_tasks)
+#endif
+#ifdef CONFIG_LITMUS_NVIDIA
+                || (tsk_rt(t)->held_gpus && !tsk_rt(t)->hide_from_gpu)
+#endif
+                );
+
+        /* we drain budget for io-based suspensions */
+        if (for_io) {
+                /* there is a fraction of time where we're double-counting the
+                 * time tracked by the rq and suspension time.
+                 * TODO: Do this recording closer to suspension time. */
+                tsk_rt(t)->budget.suspend_timestamp = litmus_clock();
+
+                TRACE_TASK(t, "blocking for I/O.\n");
+
+                if (!tsk_rt(t)->budget.timer.armed) {
+                        bt_flag_clear(t, BTF_BUDGET_EXHAUSTED);
+
+                        if (likely(!bt_flag_is_set(t, BTF_WAITING_FOR_RELEASE))) {
+                                TRACE_TASK(t, "budget timer not armed. "
+                                                   "Raced with exhaustion-resched? Re-arming.\n");
+                                arm_enforcement_timer(t, 1);
+                        }
+                        else {
+                                TRACE_TASK(t, "not arming timer because task is waiting "
+                                                   "for release.\n");
+                        }
+                }
+        }
+        else {
+                TRACE_TASK(t, "blocking for litmus lock. stop draining.\n");
+                simple_on_blocked(t);
+        }
+}
+
+void simple_io_on_wakeup(struct task_struct* t)
+{
+        /* we're waking up from an io-based suspension */
+        if (tsk_rt(t)->budget.suspend_timestamp) {
+                lt_t suspend_cost = litmus_clock() - tsk_rt(t)->budget.suspend_timestamp;
+                tsk_rt(t)->budget.suspend_timestamp = 0;
+                TRACE_TASK(t, "budget consumed while io-suspended: %llu\n", suspend_cost);
+                get_exec_time(t) += suspend_cost;
+        }
+        else {
+                TRACE_TASK(t, "waking from non-io blocking\n");
+        }
+}
+
+
+/*
  * DRAIN_SOBLIV
  */
 
@@ -208,6 +270,7 @@ void sobliv_on_wakeup(struct task_struct* t)
                  * blocked. */
                 if (tsk_rt(t)->budget.suspend_timestamp) {
                         lt_t suspend_cost = litmus_clock() - tsk_rt(t)->budget.suspend_timestamp;
+                        tsk_rt(t)->budget.suspend_timestamp = 0;
                         TRACE_TASK(t, "budget consumed while suspended: %llu\n", suspend_cost);
                         get_exec_time(t) += suspend_cost;
                 }
@@ -290,7 +353,7 @@ void sobliv_on_exit_top_m(struct task_struct* t)
 }
 
 
-void sobliv_revaluate_task(struct task_struct* t)
+void reevaluate_inheritance(struct task_struct* t)
 {
 #ifdef CONFIG_LITMUS_NESTED_LOCKING
         struct litmus_lock *blocked_lock = NULL;
diff --git a/litmus/sched_cedf.c b/litmus/sched_cedf.c
index aab30a786515..50eb4d446303 100644
--- a/litmus/sched_cedf.c
+++ b/litmus/sched_cedf.c
@@ -703,6 +703,150 @@ static enum hrtimer_restart cedf_simple_on_exhausted(struct task_struct *t)
 }
 
 
+static enum hrtimer_restart cedf_simple_io_on_exhausted(struct task_struct *t)
+{
+        enum hrtimer_restart restart = HRTIMER_NORESTART;
+
+        /* t may or may not be scheduled */
+
+        if (budget_signalled(t) && !bt_flag_is_set(t, BTF_SIG_BUDGET_SENT)) {
+                /* signal exhaustion */
+
+                /* Tasks should block SIG_BUDGET if they cannot gracefully respond to
+                 * the signal while suspended. SIG_BUDGET is an rt-signal, so it will
+                 * be queued and received when SIG_BUDGET is unblocked */
+                send_sigbudget(t); /* will set BTF_SIG_BUDGET_SENT */
+        }
+
+        if (budget_enforced(t) && !bt_flag_is_set(t, BTF_BUDGET_EXHAUSTED)) {
+                int cpu = (tsk_rt(t)->linked_on != NO_CPU) ?
+                tsk_rt(t)->linked_on : tsk_rt(t)->scheduled_on;
+
+                if (is_np(t) && is_user_np(t)) {
+                        TRACE_TASK(t, "is non-preemptable, preemption delayed.\n");
+                        bt_flag_set(t, BTF_BUDGET_EXHAUSTED);
+                        request_exit_np(t);
+                }
+                /* where do we need to call resched? */
+                else if (cpu == smp_processor_id()) {
+                        TRACE_TASK(t, "is preemptable => FORCE_RESCHED\n");
+                        bt_flag_set(t, BTF_BUDGET_EXHAUSTED);
+                        litmus_reschedule_local();
+                        set_will_schedule();
+                }
+                else if (cpu != NO_CPU) {
+                        TRACE_TASK(t, "is preemptable on remote cpu (%d) => FORCE_RESCHED\n", cpu);
+                        bt_flag_set(t, BTF_BUDGET_EXHAUSTED);
+                        litmus_reschedule(cpu);
+                }
+                else if (unlikely(tsk_rt(t)->blocked_lock)) {
+                        /* we shouldn't be draining while waiting for litmus lock, but we
+                         * could have raced with the budget timer (?). */
+                        WARN_ON(1);
+                }
+                else {
+                        lt_t remaining;
+                        cedf_domain_t *cluster;
+                        unsigned long flags;
+
+                        cluster = task_cpu_cluster(t);
+
+                        // 1) refresh budget through job completion
+                        // 2) if holds locks, tell the locking protocol to re-eval priority
+                        // 3) -- the LP must undo any inheritance relations if appropriate
+
+                        /* force job completion */
+                        TRACE_TASK(t, "blocked, postponing deadline\n");
+
+                        /* Outermost lock of the cluster. Recursive lock calls are
+                         * possible on this code path. This should be the _ONLY_
+                         * scenario where recursive calls are made. */
+#ifdef CONFIG_LITMUS_DGL_SUPPORT
+                        /* Unfortunately, we _might_ need to grab the DGL lock, so we
+                         * must grab it every time since it must be take before the
+                         * cluster lock. */
+                        raw_spin_lock_irqsave(&cluster->dgl_lock, flags);
+                        raw_readyq_lock(&cluster->cluster_lock);
+#else
+                        raw_readyq_lock_irqsave(&cluster->cluster_lock, flags);
+#endif
+
+                        job_completion(t, 1); /* refreshes budget and pushes out deadline */
+
+#ifdef CONFIG_LITMUS_LOCKING
+                        {
+                                int i;
+                                /* any linked task that inherits from 't' needs to have their
+                                 * cpu-position re-evaluated. we have to do this in two passes.
+                                 * pass 1: remove nodes from heap s.t. heap is in known good state.
+                                 * pass 2: re-add nodes.
+                                 *
+                                 */
+                                for (i = find_first_bit(&tsk_rt(t)->used_linkback_slots, BITS_PER_BYTE*sizeof(&tsk_rt(t)->used_linkback_slots));
+                                         i < BITS_PER_LONG;
+                                         i = find_next_bit(&tsk_rt(t)->used_linkback_slots, BITS_PER_BYTE*sizeof(&tsk_rt(t)->used_linkback_slots), i+1))
+                                {
+                                        struct task_struct *to_update = tsk_rt(t)->inh_task_linkbacks[i];
+                                        BUG_ON(!to_update);
+                                        if (tsk_rt(to_update)->linked_on != NO_CPU) {
+                                                cpu_entry_t *entry = &per_cpu(cedf_cpu_entries, tsk_rt(to_update)->linked_on);
+                                                BUG_ON(!binheap_is_in_heap(&entry->hn));
+                                                binheap_delete(&entry->hn, &cluster->cpu_heap);
+                                        }
+                                }
+                                for (i = find_first_bit(&tsk_rt(t)->used_linkback_slots, BITS_PER_BYTE*sizeof(&tsk_rt(t)->used_linkback_slots));
+                                         i < BITS_PER_LONG;
+                                         i = find_next_bit(&tsk_rt(t)->used_linkback_slots, BITS_PER_BYTE*sizeof(&tsk_rt(t)->used_linkback_slots), i+1))
+                                {
+                                        struct task_struct *to_update = tsk_rt(t)->inh_task_linkbacks[i];
+                                        BUG_ON(!to_update);
+                                        if (tsk_rt(to_update)->linked_on != NO_CPU) {
+                                                cpu_entry_t *entry = &per_cpu(cedf_cpu_entries, tsk_rt(to_update)->linked_on);
+                                                binheap_add(&entry->hn, &cluster->cpu_heap, cpu_entry_t, hn);
+                                        }
+                                }
+                        }
+
+                        /* Check our inheritance and propagate any changes forward. */
+                        reevaluate_inheritance(t);
+#endif
+                        /* No need to recheck priority of AUX tasks. They will always
+                         * inherit from 't' if they are enabled. Their prio change was
+                         * captured by the cpu-heap operations above. */
+
+#ifdef CONFIG_LITMUS_NVIDIA
+                        /* Re-eval priority of GPU interrupt threads. */
+                        if(tsk_rt(t)->held_gpus && !tsk_rt(t)->hide_from_gpu)
+                                gpu_owner_decrease_priority(t);
+#endif
+
+#ifdef CONFIG_LITMUS_LOCKING
+                        /* double-check that everything is okay */
+                        check_for_preemptions(cluster);
+#endif
+
+                        /* should be the outermost unlock call */
+#ifdef CONFIG_LITMUS_DGL_SUPPORT
+                        raw_readyq_unlock(&cluster->cluster_lock);
+                        raw_spin_unlock_irqrestore(&cluster->dgl_lock, flags);
+#else
+                        raw_readyq_unlock_irqrestore(&cluster->cluster_lock, flags);
+#endif
+
+                        /* we need to set up the budget timer since we're within the callback. */
+                        hrtimer_forward_now(&get_budget_timer(t).timer.timer,
+                                                                        ns_to_ktime(budget_remaining(t)));
+                        remaining = hrtimer_get_expires_ns(&get_budget_timer(t).timer.timer);
+
+                        TRACE_TASK(t, "rearmed timer to %ld\n", remaining);
+                        restart = HRTIMER_RESTART;
+                }
+        }
+
+        return restart;
+}
+
+
 #ifdef CONFIG_LITMUS_LOCKING
 static void __cedf_trigger_vunlock(struct task_struct *t)
 {
@@ -841,7 +985,7 @@ static enum hrtimer_restart cedf_sobliv_on_exhausted(struct task_struct *t)
                         }
 
                         /* Check our inheritance and propagate any changes forward. */
-                        sobliv_revaluate_task(t);
+                        reevaluate_inheritance(t);
 
                         if (tsk_rt(t)->outermost_lock && tsk_rt(t)->outermost_lock->ops->is_omlp_family)
                                 __cedf_trigger_vunlock(t);
@@ -854,7 +998,6 @@ static enum hrtimer_restart cedf_sobliv_on_exhausted(struct task_struct *t)
                         /* Re-eval priority of GPU interrupt threads. */
                         if(tsk_rt(t)->held_gpus && !tsk_rt(t)->hide_from_gpu)
                                 gpu_owner_decrease_priority(t);
-//                              recheck_gpu_owner(t);
 #endif
 
 #ifdef CONFIG_LITMUS_LOCKING
@@ -1647,6 +1790,23 @@ static struct budget_tracker_ops cedf_drain_simple_ops =
         .on_exhausted = cedf_simple_on_exhausted,
 };
 
+static struct budget_tracker_ops cedf_drain_simple_io_ops =
+{
+        .on_scheduled = simple_io_on_scheduled,
+        .on_blocked = simple_io_on_blocked,
+        .on_preempt = simple_io_on_preempt,
+        .on_sleep = simple_io_on_sleep,
+        .on_exit = simple_io_on_exit,
+
+        .on_wakeup = simple_io_on_wakeup,
+        .on_inherit = NULL,
+        .on_disinherit = NULL,
+        .on_enter_top_m = NULL,
+        .on_exit_top_m = NULL,
+
+        .on_exhausted = cedf_simple_io_on_exhausted,
+};
+
 static struct budget_tracker_ops cedf_drain_sobliv_ops =
 {
         .on_scheduled = NULL,
@@ -1678,6 +1838,9 @@ static long cedf_admit_task(struct task_struct* tsk)
                 case DRAIN_SIMPLE:
                         ops = &cedf_drain_simple_ops;
                         break;
+                case DRAIN_SIMPLE_IO:
+                        ops = &cedf_drain_simple_io_ops;
+                        break;
                 case DRAIN_SOBLIV:
                         /* budget_policy and budget_signal_policy cannot be quantum-based */
                         if (!budget_quantum_tracked(tsk) && budget_precisely_tracked(tsk)) {
@@ -1695,6 +1858,7 @@ static long cedf_admit_task(struct task_struct* tsk)
                 }
         }
 
+        /* always init the budget tracker, even if we're not using timers */
         init_budget_tracker(&tsk_rt(tsk)->budget, ops);
 
 #ifdef CONFIG_LITMUS_NESTED_LOCKING
diff --git a/litmus/sched_task_trace.c b/litmus/sched_task_trace.c
index af318058f379..931028fcf4a4 100644
--- a/litmus/sched_task_trace.c
+++ b/litmus/sched_task_trace.c
@@ -211,15 +211,14 @@ feather_callback void do_sched_trace_task_block(unsigned long id,
 
                 // hiding is turned on by locking protocols, so if there isn't any
                 // hiding, then we're blocking for some other reason.  assume it's I/O.
-                rec->data.block.for_io = 0
+                rec->data.block.for_io  = !tsk_rt(t)->blocked_lock || (0
 #ifdef CONFIG_REALTIME_AUX_TASKS
-                || (tsk_rt(t)->has_aux_tasks && !tsk_rt(t)->hide_from_aux_tasks)
+                        || (tsk_rt(t)->has_aux_tasks && !tsk_rt(t)->hide_from_aux_tasks)
 #endif
 #ifdef CONFIG_LITMUS_NVIDIA
-                || (tsk_rt(t)->held_gpus && !tsk_rt(t)->hide_from_gpu)
+                        || (tsk_rt(t)->held_gpus && !tsk_rt(t)->hide_from_gpu)
 #endif
-                ;
-
+                        );
                 put_record(rec);
         }
 }