adaptive: introduce fixed point math

Introduces fixed point math header stuff and start of predictor support in
sched_adaptive.c

3 files changed, 143 insertions, 11 deletions

diff --git a/include/linux/fpmath.h b/include/linux/fpmath.h
new file mode 100644
index 0000000000..73d89ba210
--- /dev/null
+++ b/include/linux/fpmath.h
@@ -0,0 +1,79 @@
+#ifndef __FP_MATH_H__
+#define __FP_MATH_H__
+
+#define FP_SHIFT 16
+#define ROUND_BIT (FP_SHIFT - 1)
+#define ONE FP(1)
+
+#define _fp(x) ((fp_t) {x})
+
+static inline fp_t FP(long x)
+{
+        return _fp(((long long) x) << FP_SHIFT);
+}
+
+static inline long _floor(fp_t x)
+{
+        return x.val >> FP_SHIFT;
+}
+
+/* FIXME: negative rounding */
+static inline long _round(fp_t x)
+{
+        return _floor(x) + ((x.val >> ROUND_BIT) & 1);
+}       
+
+/* divide two integers to obtain a fixed point value  */
+static inline fp_t _frac(long a, long b)
+{
+        return _fp(FP(a).val / (b));
+}
+
+/* multiply two fixed point values */
+static inline fp_t _mul(fp_t a, fp_t b)
+{       
+        return _fp((a.val * b.val) >> FP_SHIFT);
+}
+
+static inline fp_t _div(fp_t a, fp_t b)
+{
+        return _fp(FP(a.val).val / b.val);
+}
+
+static inline fp_t _add(fp_t a, fp_t b)
+{
+        return _fp(a.val + b.val);
+}
+
+static inline fp_t _sub(fp_t a, fp_t b)
+{
+        return _fp(a.val - b.val);
+}
+
+static inline fp_t _neg(fp_t x)
+{
+        return _fp(-x.val);
+}
+
+static inline int _leq(fp_t a, fp_t b)
+{
+        return a.val <= b.val;
+}
+
+static inline int _geq(fp_t a, fp_t b)
+{
+        return a.val >= b.val;
+}
+
+static inline int _lt(fp_t a, fp_t b)
+{
+        return a.val < b.val;
+}
+
+static inline int _gt(fp_t a, fp_t b)
+{
+        return a.val > b.val;
+}
+
+
+#endif
diff --git a/include/linux/rt_param.h b/include/linux/rt_param.h
index 69aa781a40..c275565835 100644
--- a/include/linux/rt_param.h
+++ b/include/linux/rt_param.h
@@ -23,14 +23,27 @@ typedef struct rt_param {
         task_class_t    class;
 } rt_param_t;
 
+/* fixed point wrapper to force compiler
+ * errors in case of misuse of a fixed point value
+ */
+typedef struct
+{
+        long long val;
+} fp_t;
+
 typedef struct {
-        unsigned long   exec_cost;      
+        fp_t            weight;
         unsigned long   period;
-        /* fixed point */
-        unsigned long   utility;
+        fp_t            value;
 } service_level_t;
 
 typedef struct {
+        fp_t error;
+        fp_t estimate;
+        fp_t accumulated;       
+} predictor_state_t;
+
+typedef struct {
         /* when will this task be release the next time? */
         jiffie_t        release;
         /* time instant the last job was released  */
@@ -111,14 +124,14 @@ typedef struct task_rt_param {
          * section support. 
          * TODO: What happens on fork?
          */
-        __user short* np_flag;
+        __user short*           np_flag;
 
         /* For the FMLP under PSN-EDF, it is required to make the task
          * non-preemptive from kernel space. In order not to interfere with
          * user space, this counter indicates the kernel space np setting.
          * kernel_np > 0 => task is non-preemptive
          */
-        unsigned int kernel_np;
+        unsigned int            kernel_np;
         
         /* put information for feedback control stuff and 
          * information about the performance of the task here
@@ -126,15 +139,15 @@ typedef struct task_rt_param {
         struct {
                 /* How many non-tardy jobs since the last tardy job? */
                 unsigned int    nontardy_jobs_ctr;
-                long accumulated_error;
+                long            accumulated_error;
         } stats;
         
-        rt_times_t times;
+        rt_times_t              times;
         
         /* This is currently only used by the PFAIR code 
          * and a prime candidate for cleanup.
          */
-        rt_times_t backup;
+        rt_times_t              backup;
 
         /* This field can be used by plugins to store where the task
          * is currently scheduled. It is the responsibility of the
@@ -155,9 +168,13 @@ typedef struct task_rt_param {
         /* Adaptive support. Adaptive tasks will store service levels
          * in this (dynamically allocated) structure.
          */
-        service_level_t* service_level;
-        unsigned int    no_service_levels;
-        unsigned int    cur_service_level;
+        service_level_t*        service_level;
+        unsigned int            no_service_levels;
+        unsigned int            cur_service_level;
+
+        /* Adaptive support. Store state for weight estimation.  
+         */
+        predictor_state_t       predictor_state;
 } task_rt_param_t;
 
 /*      Possible RT flags       */
@@ -180,6 +197,8 @@ typedef struct task_rt_param {
 #define get_deadline(t)         ((t)->rt_param.times.deadline)
 #define get_class(t)            ((t)->rt_param.basic_params.class)
 
+#define get_est_weight(t)       ((t)->rt_param.predictor_state.estimate)
+
 #define is_realtime(t)          ((t)->rt_param.is_realtime)
 #define is_subject_to_srp(t)    ((t)->rt_param.subject_to_srp)
 #define is_hrt(t)               \
diff --git a/include/linux/sched_adaptive.h b/include/linux/sched_adaptive.h
new file mode 100644
index 0000000000..eac2f90652
--- /dev/null
+++ b/include/linux/sched_adaptive.h
@@ -0,0 +1,34 @@
+#ifndef __ADAPTIVE_H__
+#define __ADAPTIVE_H__
+
+static inline unsigned long ideal_allocation(fp_t weight, unsigned long delta_t)
+{
+        return _floor(_mul(weight, FP(delta_t)));
+}
+
+/* this makes a whole bunch of linearity assumptions */
+static inline fp_t weight_transfer(fp_t from_val, fp_t to_val, 
+                                   fp_t slope, fp_t intercept, fp_t act_weight)
+{
+        fp_t rel_from, rel_to;
+        rel_from = _add(intercept, _mul(from_val, slope));
+        rel_to   = _add(intercept, _mul(to_val, slope));
+        return _div(_mul(act_weight, rel_to), rel_from);
+}
+
+static inline void update_estimate(predictor_state_t *state, fp_t actual_weight,
+                                   fp_t a, fp_t b, fp_t c)
+{
+        fp_t err, new, delta_err;
+
+        err                = _sub(actual_weight, state->estimate);
+        state->accumulated = _add(state->accumulated, err);
+        delta_err          = _sub(err, state->error);
+        new = _add(_add(_mul(a, err), 
+                        _mul(b, state->accumulated)), 
+                   _mul(c, delta_err));
+        state->estimate = new;
+        state->error    = err;
+}
+
+#endif