Per-task budget high-resolution timers (hrtimers).

As a step towards implementing more complex budget tracking
method (ex. BWI, VXR, etc.), we need per-task budget trackers
because we may be required to drain budget from a task, even
while it is suspended or blocked.
This patch does:
1) Replaces the per-CPU hrtimers with per-task hrtimers.
2) Plugin architecture for different budget policies.

This patch creates three budget draining policies:
SIMPLE, SAWARE (suspension-aware), and SOBLIV (suspension-oblivious).
However, only SIMPLE is supported by this patch.

SIMPLE (default):
Budget drains while the task is scheduled. Budget is preserved
across self-suspensions (but not job completions, of course).
Only SIMPLE is supported in this patch. (Maintaining current Litmus
functionality.)

SAWARE:
Draining according to suspension-aware analysis. Budget should drain
whenever a task is among the top-m tasks in its cluster, where
m is the number of processors in said cluster. This draining should
happen whether or not the task is actually scheduled.

SOBLIV:
Draining according to suspension-oblivious analysis. Budget should
drain whenever the task is scheduled or suspended (but not due to
preemption). Exception: Draining should halt when we can prove that
the task is not among the top-m tasks blocked on the same lock (i.e.,
on the PQ in the OMLP-family locking protocols).

6 files changed, 106 insertions, 39 deletions

diff --git a/include/litmus/budget.h b/include/litmus/budget.h
index 763b31c0e9f6..2a3511245f7a 100644
--- a/include/litmus/budget.h
+++ b/include/litmus/budget.h
@@ -1,26 +1,14 @@
 #ifndef _LITMUS_BUDGET_H_
 #define _LITMUS_BUDGET_H_
 
-/* Update the per-processor enforcement timer (arm/reproram/cancel) for
- * the next task. */
-void update_enforcement_timer(struct task_struct* t);
+#include <linux/hrtimer.h>
+#include <linux/semaphore.h>
 
-/* Send SIG_BUDGET to a real-time task. */
-void send_sigbudget(struct task_struct* t);
+#define budget_exhausted(t) \
+        (get_exec_time(t) >= get_exec_cost(t))
 
-inline static int budget_exhausted(struct task_struct* t)
-{
-        return get_exec_time(t) >= get_exec_cost(t);
-}
-
-inline static lt_t budget_remaining(struct task_struct* t)
-{
-        if (!budget_exhausted(t))
-                return get_exec_cost(t) - get_exec_time(t);
-        else
-                /* avoid overflow */
-                return 0;
-}
+#define budget_remaining(t) \
+        ((!budget_exhausted(t)) ? (get_exec_cost(t) - get_exec_time(t)) : 0)
 
 #define budget_enforced(t) (\
         tsk_rt(t)->task_params.budget_policy != NO_ENFORCEMENT)
@@ -29,21 +17,87 @@ inline static lt_t budget_remaining(struct task_struct* t)
         tsk_rt(t)->task_params.budget_policy == PRECISE_ENFORCEMENT || \
         tsk_rt(t)->task_params.budget_signal_policy == PRECISE_SIGNALS)
 
+#define budget_quantum_tracked(t) (\
+        tsk_rt(t)->task_params.budget_policy == QUANTUM_ENFORCEMENT || \
+        tsk_rt(t)->task_params.budget_signal_policy == QUANTUM_SIGNALS)
+
 #define budget_signalled(t) (\
         tsk_rt(t)->task_params.budget_signal_policy != NO_SIGNALS)
 
 #define budget_precisely_signalled(t) (\
         tsk_rt(t)->task_params.budget_policy == PRECISE_SIGNALS)
 
-#define sigbudget_sent(t) (\
-        test_bit(RT_JOB_SIG_BUDGET_SENT, &tsk_rt(t)->job_params.flags))
+#define bt_flag_is_set(t, flag_nr) (\
+        test_bit(flag_nr, &tsk_rt(t)->budget.flags))
+
+#define bt_flag_test_and_set(t, flag_nr) (\
+        test_and_set_bit(flag_nr, &tsk_rt(t)->budget.flags))
+
+#define bt_flag_set(t, flag_nr) (\
+        set_bit(flag_nr, &tsk_rt(t)->budget.flags))
+
+#define bt_flag_clear(t, flag_nr) (\
+        clear_bit(flag_nr, &tsk_rt(t)->budget.flags))
+
+#define bt_flags_reset(t) (\
+        tsk_rt(t)->budget.flags = 0)
+
+#define requeue_preempted_job(t) \
+        (t && (!budget_exhausted(t) || !budget_enforced(t)))
+
+struct enforcement_timer
+{
+        raw_spinlock_t lock;
+        struct hrtimer timer;
+        int armed:1;
+};
+
+typedef void (*scheduled_t)(struct task_struct* t);
+typedef void (*blocked_t)(struct task_struct* t);
+typedef void (*preempt_or_sleep_t)(struct task_struct* t);
+typedef void (*exhausted_t)(struct task_struct* t);
+typedef void (*exit_t)(struct task_struct* t);
 
-static inline int requeue_preempted_job(struct task_struct* t)
+struct budget_tracker_ops
 {
-        /* Add task to ready queue only if not subject to budget enforcement or
-         * if the job has budget remaining. t may be NULL.
-         */
-        return t && (!budget_exhausted(t) || !budget_enforced(t));
-}
+        scheduled_t                     on_scheduled;   /* called from litmus_schedule(). */
+        blocked_t                       on_blocked;             /* called from plugin::schedule() */
+        preempt_or_sleep_t      on_preempt_or_sleep;    /* called from plugin::schedule() */
+
+        exit_t                          on_exit;                /* task exiting rt mode */
+
+        exhausted_t                     on_exhausted;   /* called by plugin::tick() or timer interrupt */
+};
+
+struct budget_tracker
+{
+        struct enforcement_timer timer;
+        const struct budget_tracker_ops* ops;
+        unsigned long flags;
+};
+
+/* budget tracker flags */
+enum BT_FLAGS
+{
+        BTF_BUDGET_EXHAUSTED = 0,
+        BTF_SIG_BUDGET_SENT     = 1,
+};
+
+/* Functions for simple DRAIN_SIMPLE policy common
+ * to every scheduler. Scheduler must provided
+ * implementation for simple_on_exhausted().
+ */
+void simple_on_scheduled(struct task_struct* t);
+void simple_on_blocked(struct task_struct* t);
+void simple_on_preempt_or_sleep(struct task_struct* t);
+void simple_on_exit(struct task_struct* t);
+
+
+void init_budget_tracker(struct budget_tracker* bt,
+                                const struct budget_tracker_ops* ops);
+
+
+/* Send SIG_BUDGET to a real-time task. */
+void send_sigbudget(struct task_struct* t);
 
 #endif
diff --git a/include/litmus/fdso.h b/include/litmus/fdso.h
index f7887288d8f5..2d8e6c43d908 100644
--- a/include/litmus/fdso.h
+++ b/include/litmus/fdso.h
@@ -36,7 +36,7 @@ typedef enum  {
         KFMLP_GPU_AFF_OBS                       = 12,
 
         PRIOQ_MUTEX = 13,
-        
+
         MAX_OBJ_TYPE    = 13
 } obj_type_t;
 
diff --git a/include/litmus/gpu_affinity.h b/include/litmus/gpu_affinity.h
index 47da725717b0..f610f58b1f3b 100644
--- a/include/litmus/gpu_affinity.h
+++ b/include/litmus/gpu_affinity.h
@@ -11,6 +11,7 @@ gpu_migration_dist_t gpu_migration_distance(int a, int b);
 static inline void reset_gpu_tracker(struct task_struct* t)
 {
         t->rt_param.accum_gpu_time = 0;
+        t->rt_param.gpu_time_stamp = 0;
 }
 
 static inline void start_gpu_tracker(struct task_struct* t)
@@ -22,11 +23,16 @@ static inline void stop_gpu_tracker(struct task_struct* t)
 {
         lt_t now = litmus_clock();
         t->rt_param.accum_gpu_time += (now - t->rt_param.gpu_time_stamp);
+        t->rt_param.gpu_time_stamp = 0;
 }
 
 static inline lt_t get_gpu_time(struct task_struct* t)
 {
-        return t->rt_param.accum_gpu_time;
+        lt_t accum = t->rt_param.accum_gpu_time;
+        if (t->rt_param.gpu_time_stamp != 0) {
+                accum += (litmus_clock() - t->rt_param.gpu_time_stamp);
+        }
+        return accum;
 }
 
 static inline lt_t get_gpu_estimate(struct task_struct* t, gpu_migration_dist_t dist)
diff --git a/include/litmus/litmus.h b/include/litmus/litmus.h
index 70b421d59d34..f6ea5f6e80ee 100644
--- a/include/litmus/litmus.h
+++ b/include/litmus/litmus.h
@@ -62,6 +62,7 @@ void litmus_exit_task(struct task_struct *tsk);
 #define get_priority(t)         (tsk_rt(t)->task_params.priority)
 #define get_class(t)        (tsk_rt(t)->task_params.cls)
 #define get_release_policy(t) (tsk_rt(t)->task_params.release_policy)
+#define get_drain_policy(t) (tsk_rt(t)->task_params.drain_policy)
 
 /* job_param macros */
 #define get_exec_time(t)    (tsk_rt(t)->job_params.exec_time)
@@ -69,6 +70,7 @@ void litmus_exit_task(struct task_struct *tsk);
 #define get_period(t)           (tsk_rt(t)->task_params.period)
 #define get_release(t)          (tsk_rt(t)->job_params.release)
 #define get_lateness(t)         (tsk_rt(t)->job_params.lateness)
+#define get_budget_timer(t) (tsk_rt(t)->job_params.budget_timer)
 
 #define effective_priority(t) ((!(tsk_rt(t)->inh_task)) ? t : tsk_rt(t)->inh_task)
 #define base_priority(t) (t)
diff --git a/include/litmus/rt_param.h b/include/litmus/rt_param.h
index bf0ee8dbae6e..887075b908ca 100644
--- a/include/litmus/rt_param.h
+++ b/include/litmus/rt_param.h
@@ -36,6 +36,14 @@ typedef enum {
 } budget_policy_t;
 
 typedef enum {
+        /* all drain mechanisms are ignored if budget enforcement or signalling
+           is not in use. */
+        DRAIN_SIMPLE,   /* drains while task is linked */
+        DRAIN_SAWARE,   /* drains according to suspension-aware analysis */
+        DRAIN_SOBLIV,   /* drains according to suspension-obliv analysis */
+} budget_drain_policy_t;
+
+typedef enum {
         NO_SIGNALS,                     /* job receives no signals when it exhausts its budget */
         QUANTUM_SIGNALS,        /* budget signals are only sent on quantum boundaries */
         PRECISE_SIGNALS,        /* budget signals are triggered with hrtimers */
@@ -132,6 +140,7 @@ struct rt_task {
         unsigned int    priority;
         task_class_t    cls;
         budget_policy_t budget_policy; /* ignored by pfair */
+        budget_drain_policy_t drain_policy;
         budget_signal_policy_t budget_signal_policy; /* currently ignored by pfair */
         release_policy_t release_policy;
 };
@@ -213,8 +222,9 @@ struct control_page {
 /* don't export internal data structures to user space (liblitmus) */
 #ifdef __KERNEL__
 
-#include <litmus/binheap.h>
 #include <linux/semaphore.h>
+#include <litmus/budget.h>
+#include <litmus/binheap.h>
 
 #ifdef CONFIG_LITMUS_SOFTIRQD
 #include <linux/interrupt.h>
@@ -247,15 +257,8 @@ struct rt_job {
          * Increase this sequence number when a job is released.
          */
         unsigned int    job_no;
-
-        /* bits:
-         * 0th: Set if a budget exhaustion signal has already been sent for
-         *      the current job. */
-        unsigned long   flags;
 };
 
-#define RT_JOB_SIG_BUDGET_SENT  0
-
 struct pfair_param;
 
 enum klmirqd_sem_status
@@ -278,12 +281,12 @@ typedef enum gpu_migration_dist
         MIG_LAST = MIG_NONE
 } gpu_migration_dist_t;
 
-typedef struct feedback_est{
+typedef struct feedback_est
+{
         fp_t est;
         fp_t accum_err;
 } feedback_est_t;
 
-
 #define AVG_EST_WINDOW_SIZE 20
 
 typedef int (*notify_rsrc_exit_t)(struct task_struct* tsk);
@@ -417,7 +420,6 @@ struct rt_param {
         struct binheap_node     aux_task_owner_node;
 #endif
 
-
 #ifdef CONFIG_NP_SECTION
         /* For the FMLP under PSN-EDF, it is required to make the task
          * non-preemptive from kernel space. In order not to interfere with
@@ -427,6 +429,8 @@ struct rt_param {
         unsigned int    kernel_np;
 #endif
 
+        struct budget_tracker budget;
+
         /* This field can be used by plugins to store where the task
          * is currently scheduled. It is the responsibility of the
          * plugin to avoid race conditions.
diff --git a/include/litmus/sched_plugin.h b/include/litmus/sched_plugin.h
index 78cec30866ac..6e7d6df2fb78 100644
--- a/include/litmus/sched_plugin.h
+++ b/include/litmus/sched_plugin.h
@@ -130,6 +130,7 @@ struct sched_plugin {
         schedule_t              schedule;
         finish_switch_t         finish_switch;
 
+
         /*      syscall backend         */
         complete_job_t          complete_job;
         release_at_t            release_at;