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).

1 files changed, 15 insertions, 11 deletions

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.