Initial lv C impl.wip-mc2

4 files changed, 739 insertions, 73 deletions

diff --git a/include/litmus/reservation.h b/include/litmus/reservation.h
index 4eecd3f088e8..0345d3482916 100644
--- a/include/litmus/reservation.h
+++ b/include/litmus/reservation.h
@@ -126,6 +126,9 @@ struct reservation {
         struct reservation_ops *ops;
 
         struct list_head clients;
+        
+        /* for global env. */
+        int scheduled_on;
 };
 
 void reservation_init(struct reservation *res);
@@ -191,4 +194,56 @@ struct task_struct* sup_dispatch(struct sup_reservation_environment* sup_env);
 struct reservation* sup_find_by_id(struct sup_reservation_environment* sup_env,
         unsigned int id);
 
+#define ENV_RESCHEDULE_NOW (0)
+#define ENV_NO_SCHEDULER_UPDATE (ULLONG_MAX)    
+
+struct next_timer_event {
+        lt_t next_event;
+        int timer_armed_on;
+        struct list_head list;
+};
+
+/* A global multiprocessor reservation environment.
+ */
+struct gmp_reservation_environment {
+        //raw_spinlock_t lock;
+        struct reservation_environment env;
+
+        /* ordered by priority */
+        struct list_head active_reservations;
+
+        /* ordered by next_replenishment */
+        struct list_head depleted_reservations;
+
+        /* unordered */
+        struct list_head inactive_reservations;
+
+        /* - ENV_RESCHEDULE_NOW means call gmp_dispatch() now
+         * - ENV_NO_SCHEDULER_UPDATE means nothing to do
+         * any other value means program a timer for the given time
+         */
+        struct list_head next_events;
+        raw_spinlock_t event_lock;
+        bool schedule_now;
+        /* set to true if a call to gmp_dispatch() is imminent */
+        bool will_schedule;
+};
+
+/* Contract:
+ *  - before calling into sup_ code, or any reservation methods,
+ *    update the time with sup_update_time(); and
+ *  - after calling into sup_ code, or any reservation methods,
+ *    check next_scheduler_update and program timer or trigger
+ *    scheduler invocation accordingly.
+ */
+
+void gmp_init(struct gmp_reservation_environment* gmp_env);
+void gmp_add_new_reservation(struct gmp_reservation_environment* gmp_env,
+        struct reservation* new_res);
+void gmp_update_time(struct gmp_reservation_environment* gmp_env, lt_t now);
+struct task_struct* gmp_dispatch(struct gmp_reservation_environment* gmp_env);
+
+struct reservation* gmp_find_by_id(struct gmp_reservation_environment* gmp_env,
+        unsigned int id);
+
 #endif
diff --git a/litmus/polling_reservations.c b/litmus/polling_reservations.c
index 4c07ee74bf39..81f8e0f54ffd 100644
--- a/litmus/polling_reservations.c
+++ b/litmus/polling_reservations.c
@@ -72,6 +72,7 @@ static void periodic_polling_client_departs(
                         /* do nothing */
                         break;
         }
+        res->scheduled_on = NO_CPU;
 }
 
 static void periodic_polling_on_replenishment(
diff --git a/litmus/reservation.c b/litmus/reservation.c
index 0e43479ff2e1..35b3b5de5d0c 100644
--- a/litmus/reservation.c
+++ b/litmus/reservation.c
@@ -1,4 +1,5 @@
 #include <linux/sched.h>
+#include <linux/slab.h>
 
 #include <litmus/litmus.h>
 #include <litmus/reservation.h>
@@ -203,8 +204,7 @@ static void sup_charge_budget(
                 {
                         /* make sure scheduler is invoked when this reservation expires
                          * its remaining budget */
-                         TRACE("requesting scheduler update for reservation %u in %llu nanoseconds\n",
-                                res->id, res->cur_budget);
+                         //TRACE("requesting scheduler update for reservation %u in %llu nanoseconds\n", res->id, res->cur_budget);
                          sup_scheduler_update_after(sup_env, res->cur_budget);
                 }
                 if (encountered_active)
@@ -317,3 +317,302 @@ void sup_init(struct sup_reservation_environment* sup_env)
 
         sup_env->next_scheduler_update = SUP_NO_SCHEDULER_UPDATE;
 }
+
+static void gmp_scheduler_update_at(
+        struct gmp_reservation_environment* gmp_env,
+        lt_t when)
+{
+        struct next_timer_event *nevent;
+        struct list_head *pos;
+        struct next_timer_event *queued;
+        int found = 0;
+        
+        nevent = kzalloc(sizeof(*nevent), GFP_KERNEL);
+        nevent->next_event = when;
+        nevent->timer_armed_on = NO_CPU;
+        
+        list_for_each(pos, &gmp_env->next_events) {
+                queued = list_entry(pos, struct next_timer_event, list);
+                if (queued->next_event > nevent->next_event) {
+                        list_add(&nevent->list, pos->prev);
+                        found = 1;
+                        TRACE("NEXT_EVENT ADDED after %llu\n", queued->next_event);
+                        break;
+                }
+        }
+        
+        if (!found) {
+                list_add_tail(&nevent->list, &gmp_env->next_events);
+                TRACE("NEXT_EVENT ADDED at [0]\n");
+        }
+        
+        TRACE("GMP_SCHEDULER_UPDATE_AT update_time: %llu\n", nevent->next_event);
+}
+
+static void gmp_scheduler_update_after(
+        struct gmp_reservation_environment* gmp_env,
+        lt_t timeout)
+{
+        gmp_scheduler_update_at(gmp_env, gmp_env->env.current_time + timeout);
+}
+
+static int _gmp_queue_depleted(
+        struct gmp_reservation_environment* gmp_env,
+        struct reservation *res)
+{
+        struct list_head *pos;
+        struct reservation *queued;
+        int passed_earlier = 0;
+
+        list_for_each(pos, &gmp_env->depleted_reservations) {
+                queued = list_entry(pos, struct reservation, list);
+                if (queued->next_replenishment > res->next_replenishment) {
+                        list_add(&res->list, pos->prev);
+                        return passed_earlier;
+                } else
+                        passed_earlier = 1;
+        }
+
+        list_add_tail(&res->list, &gmp_env->depleted_reservations);
+
+        return passed_earlier;
+}
+
+static void gmp_queue_depleted(
+        struct gmp_reservation_environment* gmp_env,
+        struct reservation *res)
+{
+        int passed_earlier = _gmp_queue_depleted(gmp_env, res);
+
+        /* check for updated replenishment time */
+        if (!passed_earlier)
+                gmp_scheduler_update_at(gmp_env, res->next_replenishment);
+}
+
+static int _gmp_queue_active(
+        struct gmp_reservation_environment* gmp_env,
+        struct reservation *res)
+{
+        struct list_head *pos;
+        struct reservation *queued;
+        int passed_active = 0;
+
+        list_for_each(pos, &gmp_env->active_reservations) {
+                queued = list_entry(pos, struct reservation, list);
+                if (queued->priority > res->priority) {
+                        list_add(&res->list, pos->prev);
+                        return passed_active;
+                } else if (queued->state == RESERVATION_ACTIVE)
+                        passed_active = 1;
+        }
+
+        list_add_tail(&res->list, &gmp_env->active_reservations);
+        return passed_active;
+}
+
+static void gmp_queue_active(
+        struct gmp_reservation_environment* gmp_env,
+        struct reservation *res)
+{
+        int passed_active = _gmp_queue_active(gmp_env, res);
+
+        /* check for possible preemption */
+        if (res->state == RESERVATION_ACTIVE && !passed_active) {
+                gmp_env->schedule_now = true;