adaptive: Aaron's fixes, clean out debug, and merge header

This patch is a collection of several changes. It includes Aaron's fixes
to prevent division by zero, makes it possible to disable the optimizer
debug output, and merges the header file into the scheduler implementation
since it is not being used anywhere else.

1 files changed, 224 insertions, 31 deletions

diff --git a/kernel/sched_adaptive.c b/kernel/sched_adaptive.c
index 0d524cf258..0f00903fad 100644
--- a/kernel/sched_adaptive.c
+++ b/kernel/sched_adaptive.c
@@ -1,4 +1,5 @@
 
+
 /*
  * kernel/sched_adaptive.c
  *
@@ -26,7 +27,6 @@
 #include <linux/sched_trace.h>
 
 #include <linux/fpmath.h>
-#include <linux/sched_adaptive.h>
 
 /* Overview of GSN-EDF operations.
  *
@@ -143,6 +143,179 @@ jiffie_t 	opt_time;
  */
 static LIST_HEAD(adaptive_inc_list);
 
+/* comment out to disable optimizer debugging */
+#define ENABLE_OPTIMIZER_DEBUGGING
+
+#ifdef ENABLE_OPTIMIZER_DEBUGGING
+#define OPT_DBG TRACE
+#define OPT_DBG_T TRACE_TASK
+#else 
+#define OPT_DBG
+#define OPT_DBG_T OPT_D
+#endif
+
+/******************************************************************************/
+/*                             OPTIMIZER MATH                                 */
+/******************************************************************************/
+
+/* All time dependent functions 
+ * rely on opt_time.
+ * Update in the optimizer before use!
+ */
+
+static inline fp_t ideal(fp_t weight, jiffie_t delta_t)
+{
+        return _mul(weight, FP(delta_t));
+}
+
+static noinline long ideal_exec_time(struct task_struct* t)
+{
+        jiffie_t delta = opt_time - get_last_release(t);
+        return _round(ideal(get_est_weight(t), delta));
+}
+
+/* this makes a whole bunch of linearity assumptions */
+static noinline fp_t weight_transfer(struct task_struct* t,
+                                   unsigned int from, unsigned int to,
+                                   fp_t act_weight)
+{
+        fp_t rel_from, rel_to, ret;
+        rel_from = get_sl(t, from).weight;
+        rel_to   = get_sl(t, to).weight;
+        ret.val = (act_weight.val * rel_to.val) / rel_from.val;
+        OPT_DBG("weight_transfer(%ld, %ld, %ld) => %ld  to=%u from=%u\n", 
+                rel_from.val, rel_to.val, act_weight.val, ret.val, from, to);
+
+        return ret;
+}
+
+static noinline fp_t est_weight_at(struct task_struct* t, unsigned int level)
+{
+        if (t->rt_param.no_service_levels)
+                return weight_transfer(t, get_cur_sl(t), level, 
+                                       get_est_weight(t));
+        else
+                return get_est_weight(t);
+                               
+}
+
+static noinline void update_estimate(predictor_state_t *state, fp_t actual_weight,
+                                     fp_t a, fp_t b)
+{
+        fp_t err, new;
+        
+        OPT_DBG("OLD ESTIMATE Weight" _FP_ " ActWt " _FP_ " A:" _FP_ ", B:" _FP_
+                "\n", fp2str(state->estimate), fp2str(actual_weight), fp2str(a),
+                fp2str(b));
+        err                = _sub(actual_weight, state->estimate);
+        new = _add(_mul(a, err), 
+                   _mul(b, state->accumulated));
+        state->estimate = new;
+        state->accumulated = _add(state->accumulated, err);
+        OPT_DBG("ERROR " _FP_ ", NEW " _FP_ ", ACC" _FP_ "\n", fp2str(err),
+                fp2str(new), fp2str(state->accumulated));
+
+}
+
+static noinline fp_t linear_metric(struct task_struct* t) 
+{
+        fp_t v1, vmax, g1, gmax;
+        fp_t est_w;
+        unsigned int l    = t->rt_param.no_service_levels;
+        unsigned int lcur;
+
+        if (l <= 1)
+                return FP(0);
+
+        lcur  = get_cur_sl(t);;
+        est_w = get_est_weight(t);
+
+        OPT_DBG_T(t, " linear_metric: lcur=%u l=%u est_w=" _FP_ "\n", 
+                   lcur, l, est_w);
+        OPT_DBG_T(t, " linear_metric: est_w.val=%ld\n", est_w.val); 
+
+
+        v1    = t->rt_param.service_level[0].value;
+        vmax  = t->rt_param.service_level[l - 1].value;
+
+        OPT_DBG_T(t, " linear_metric: v1=" _FP_ " vmax=" _FP_  "\n", v1, vmax);
+        OPT_DBG_T(t, " linear_metric: v1=%ld vmax=%ld\n", v1.val, vmax.val);
+
+
+        g1    = weight_transfer(t, lcur, 0, est_w);
+        gmax  = weight_transfer(t, lcur, l - 1, est_w);
+
+        OPT_DBG_T(t, " linear_metric: g1=" _FP_ " gmax=" _FP_  "\n", g1, gmax);
+        OPT_DBG_T(t, " linear_metric: g1=%ld gmax=%ld\n", g1, gmax); 
+
+
+        TRACE_BUG_ON(_eq(_sub(gmax, g1), FP(0)));
+        if (_eq(_sub(gmax, g1), FP(0)))
+                return FP(0);
+        return _div(_sub(vmax, v1),
+                    _sub(gmax, g1));
+}
+
+static noinline  unsigned long reweighted_period(fp_t ow, fp_t nw, unsigned long alloc,
+                                                 jiffie_t deadline, jiffie_t release) 
+{
+        fp_t dl;
+        dl = _mul(FP(deadline - release), ow);
+        dl = _sub(dl, FP(alloc));
+        if(_eq(nw, FP(0)))
+                return 0;
+        dl = _div(dl, nw);
+        return _round(dl);
+}
+
+static noinline int is_under_allocated(struct task_struct* t)
+{
+        return ideal_exec_time(t) >= t->rt_param.times.exec_time;
+}
+
+static noinline jiffie_t dec_equal_point_delay(struct task_struct* t)
+{
+        if (_lt(FP(0), get_est_weight(t)))
+                /* when t was released plus time needed to equalize
+                 * minus now 
+                 */             
+                return get_last_release(t) +  
+                        _round(_div( FP(t->rt_param.times.exec_time), 
+                                     get_est_weight(t))) -
+                        opt_time;
+        else
+                /* if the weight is zero we just take the 
+                 * deadline
+                 */
+                return t->rt_param.times.deadline;
+}
+
+static noinline jiffie_t inc_equal_point_delay(struct task_struct* t)
+{
+        if (_lt(FP(0), t->rt_param.opt_nw))
+                /* when t was released plus time needed to equalize
+                 * minus now 
+                 */
+                return  get_last_release(t) +
+                        _round(_div( FP(t->rt_param.times.exec_time), 
+                                     t->rt_param.opt_nw)) -
+                        opt_time;
+        else
+                /* if the weight is zero we just take the 
+                 * deadline
+                 */
+                return t->rt_param.times.deadline;
+}
+
+static noinline jiffie_t decrease_delay(struct task_struct* t)
+{       
+        if (has_active_job(t) && !is_under_allocated(t))
+                return dec_equal_point_delay(t);        
+        return 0;
+}
+
+
+
 /******************************************************************************/
 /*                             SORT ORDERS                                    */
 /******************************************************************************/
@@ -187,11 +360,10 @@ static void set_service_level(struct task_struct* t, unsigned int level)
         t->rt_param.basic_params.exec_cost = _round(_mul(new->weight, 
                                                          FP(new->period)));
 
-        if (t->rt_param.signal_ready)
-                scheduler_signal(t, SIGUSR1);
+        scheduler_signal(t, SIGUSR1);
 
         sched_trace_service_level_change(t);
-        TRACE_TASK(t, "service level %u activated\n", level);
+        OPT_DBG_T(t, "service level %u activated\n", level);
 }
 
 /* call this _before_ updating deadline and release of t */
@@ -205,16 +377,18 @@ static void update_weight_estimate(struct task_struct* t)
         exec_time = t->rt_param.times.exec_time;
         sl_period = get_sl(t, get_opt_sl(t)).period;
 
-        /*TRACE("ow=" _FP_ " nw=" _FP_ ", r-d " _FP_ ", deadline %d, release %d, exec_time=%ld sl_period=%lu\n",
-          fp2str(ow), fp2str(nw),fp2str(FP(get_deadline(t)-get_last_release(t))), get_deadline(t), get_last_release(t), exec_time, sl_period);*/
+        OPT_DBG("ow=" _FP_ " nw=" _FP_ ", r-d " _FP_ 
+                ", deadline %d, release %d, exec_time=%ld sl_period=%lu\n",
+                fp2str(ow), fp2str(nw), 
+                fp2str(FP(get_deadline(t) - get_last_release(t))), 
+                get_deadline(t), get_last_release(t), exec_time, sl_period);
 
         t->rt_param.predictor_state.estimate = nw;
-        TRACE_TASK(t, "AAAupdate_weight_estimate from " _FP_ " to "_FP_"\n", fp2str(ow), fp2str(nw));
+        OPT_DBG_T(t, "update_weight_estimate from " _FP_ " to "_FP_"\n", fp2str(ow), fp2str(nw));
+        
 
-                /*_div( _max(_mul(nw, FP(sl_period)), FP(exec_time)),
-                      FP(get_deadline(t) - get_last_release(t)));       
-        TRACE_TASK(t, " update_weight_estimate: " _FP_ " => " _FP_ "\n", 
-        fp2str(ow), fp2str(get_est_weight(t)));*/
+        OPT_DBG_T(t, " update_weight_estimate: " _FP_ " => " _FP_ "\n", 
+        fp2str(ow), fp2str(get_est_weight(t)));
 }
 
 
@@ -344,7 +518,7 @@ void adaptive_optimize(void)
         unsigned int l;
         jiffie_t enactment_time;
 
-        TRACE(":::::: running adaptive optimizer\n");
+        OPT_DBG(":::::: running adaptive optimizer\n");
         opt_time = jiffies;
 
         INIT_LIST_HEAD(&list);
@@ -364,7 +538,7 @@ void adaptive_optimize(void)
         for_each_online_cpu(i)
                 M = _add(M, FP(1));     
         _M = M;
-        TRACE("opt: system capacity: " _FP_ "\n", fp2str(M));
+        OPT_DBG("opt: system capacity: " _FP_ "\n", fp2str(M));
 
         /* 3) Compute L value for all tasks, 
          *    and set tasks to service level 0, 
@@ -378,15 +552,15 @@ void adaptive_optimize(void)
                         continue;
                 }
                 t->rt_param.opt_order = linear_metric(t);               
-                TRACE_TASK(t, "est_w = " _FP_ " L = " _FP_ "\n", 
-                           get_est_weight(t),
-                           fp2str(t->rt_param.opt_order));
+                OPT_DBG_T(t, "est_w = " _FP_ " L = " _FP_ "\n", 
+                          get_est_weight(t),
+                          fp2str(t->rt_param.opt_order));
                 t->rt_param.opt_level = 0;
                 M = _sub(M, est_weight_at(t, 0));
                 estU = _add(estU, get_est_weight(t));
         }
-        TRACE("opt: estimated utilization: " _FP_ "\n", fp2str(estU));
-        TRACE("opt: estimated capacity at all sl=0: " _FP_ "\n", fp2str(M));
+        OPT_DBG("opt: estimated utilization: " _FP_ "\n", fp2str(estU));
+        OPT_DBG("opt: estimated capacity at all sl=0: " _FP_ "\n", fp2str(M));
 
         
         /* 4) sort list by decreasing linear metric */
@@ -411,8 +585,9 @@ void adaptive_optimize(void)
                                 break; /* proceed to next task */
                         }
                 }
-                TRACE_TASK(t, " will run at sl=%u, prior=%u dw=" _FP_ "\n",
+                OPT_DBG_T(t, " will run at sl=%u, prior=%u dw=" _FP_ "\n",
                            l, get_cur_sl(t), fp2str(t->rt_param.opt_dw));
+                
         }
         
         /* 6) filter tasks that reweight  */
@@ -467,9 +642,10 @@ void adaptive_optimize(void)
                                 /* opt_dw is negative */
                                 estU = _add(estU, t->rt_param.opt_dw);
                                 list_add(p, &list);
-                                TRACE_TASK(t, " weight decrease at %ld => estU=" 
-                                           _FP_ "\n", enactment_time, 
-                                           fp2str(estU));
+
+                                OPT_DBG_T(t, " weight decrease at %ld => estU=" 
+                                          _FP_ "\n", enactment_time, 
+                                          fp2str(estU));
 
                         } else
                                 /* stop decrease loop */
@@ -488,9 +664,11 @@ void adaptive_optimize(void)
                                 t->rt_param.opt_change = enactment_time;
                                 list_del(p);
                                 list_add(p, &list);
-                                TRACE_TASK(t, " weight increase at %ld => estU=" 
+
+                                OPT_DBG_T(t, " weight increase at %ld => estU=" 
                                            _FP_ "\n", enactment_time, 
                                            fp2str(estU));
+
                         } else
                                 /* stop increase loop */
                                 break;
@@ -516,7 +694,7 @@ void adaptive_optimize(void)
         }
 
         last_optimizer_run = jiffies;
-        TRACE(":::::: optimizer run complete\n");       
+        OPT_DBG(":::::: optimizer run complete\n");     
 }
 
 /* update_cpu_position - Move the cpu entry to the correct place to maintain 
@@ -693,8 +871,10 @@ static void adaptive_job_arrival(struct task_struct* task)
         if (edf_preemption_needed(&adaptive, last->linked)) {
                 /* preemption necessary */
                 task = __take_ready(&adaptive);
+
                 TRACE("job_arrival: task %d linked to %d\n", 
                       task->pid, last->cpu);
+
                 if (last->linked)
                         requeue(last->linked);
                 
@@ -763,7 +943,9 @@ static reschedule_check_t adaptive_scheduler_tick(void)
                 
                 /* (1) run the optimizer if it did not trigger often enough */
                 if (time_before_eq(last_optimizer_run + optimizer_period, jiffies)) {
-                        TRACE("adaptive: optimizing due to period threshold\n");
+
+                        OPT_DBG("adaptive: optimizing due to period threshold\n");
+
                         adaptive_optimize();
                 }
 
@@ -788,13 +970,15 @@ static noinline void job_completion(struct task_struct *t)
 {
         long delta;
         fp_t actual_weight, old_estimate;
+        unsigned int lcurr = get_cur_sl(t);
+        fp_t v = t->rt_param.service_level[lcurr].value;
         BUG_ON(!t);
 
         sched_trace_job_completion(t);
         delta = t->rt_param.times.exec_time - 
                 t->rt_param.basic_params.exec_cost;
 
-        TRACE_TASK(t, "job %d completes, delta WCET = %d\n", 
+        OPT_DBG_T(t, "job %d completes, delta WCET = %d\n", 
                    t->rt_param.times.job_no, delta);
 
         actual_weight = _frac(t->rt_param.times.exec_time, 
@@ -804,13 +988,16 @@ static noinline void job_completion(struct task_struct *t)
         update_estimate(&t->rt_param.predictor_state, actual_weight, 
                         fc_a, fc_b);
 
-        TRACE_TASK(t, " weight estimation: error=" _FP_  " weight=" _FP_ " => " _FP_ "\n",
+        OPT_DBG_T(t, "Job %d completes. Current value " _FP_ 
+                  ", Weight estimation: error=" _FP_  " weight=" 
+                  _FP_ " => " _FP_ "\n",t->rt_param.times.job_no, v,
                    _sub(get_est_weight(t), old_estimate),
                    old_estimate, get_est_weight(t));
-        if (_gt(_div(_abs(_sub(get_est_weight(t), old_estimate)),
-                     get_est_weight(t)), 
-                task_error_threshold)) {
-                TRACE("adaptive: optimizing due to task error threshold\n");
+                        
+        if ( (!_eq(get_est_weight(t),FP(0))) && 
+             (_gt(_div(_abs(_sub(get_est_weight(t), old_estimate)),
+              get_est_weight(t)), task_error_threshold))) {
+                OPT_DBG("adaptive: optimizing due to task error threshold\n");
                 adaptive_optimize();
         }
 
@@ -960,6 +1147,7 @@ static void adaptive_finish_switch(struct task_struct *prev)
 static long adaptive_prepare_task(struct task_struct * t)
 {
         unsigned long           flags;
+
         TRACE("adaptive: prepare task %d\n", t->pid);
 
         if (t->state == TASK_STOPPED) {
@@ -975,6 +1163,7 @@ static long adaptive_prepare_task(struct task_struct * t)
                                 _frac(get_exec_cost(t), get_rt_period(t));
                 
                 TRACE_TASK(t, "est_weight=" _FP_  "\n", get_est_weight(t));
+
                 if (get_rt_mode() == MODE_RT_RUN)
                         /* The action is already on. 
                          * Prepare immediate release
@@ -1005,7 +1194,9 @@ static void adaptive_wake_up_task(struct task_struct *task)
          * anyway.If it has zero budget and the next release is in the future 
          * it has to go to the release queue.
          */
+
         TRACE("adaptive: %d unsuspends\n", task->pid);
+
         task->state = TASK_RUNNING;
 
         if (is_tardy(task)) {
@@ -1032,7 +1223,9 @@ static void adaptive_task_blocks(struct task_struct *t)
         queue_unlock_irqrestore(&adaptive_lock, flags);
 
         BUG_ON(!is_realtime(t));
+
         TRACE("task %d suspends\n", t->pid);
+
         BUG_ON(t->rt_list.next != LIST_POISON1);
         BUG_ON(t->rt_list.prev != LIST_POISON2);
 }