1 files changed, 364 insertions, 5 deletions

diff --git a/litmus/reservation.c b/litmus/reservation.c
index 0bc551e2e67b..08c74f9005b3 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>
@@ -52,7 +53,8 @@ static void sup_scheduler_update_at(
                 sup_env->next_scheduler_update = when;
 }
 
-static void sup_scheduler_update_after(
+/* changed from non-static to static function because it's used outside */
+void sup_scheduler_update_after(
         struct sup_reservation_environment* sup_env,
         lt_t timeout)
 {
@@ -192,8 +194,12 @@ static void sup_charge_budget(
                 /* charge all ACTIVE_IDLE up to the first ACTIVE reservation */
                 res = list_entry(pos, struct reservation, list);
                 if (res->state == RESERVATION_ACTIVE) {
-                        res->ops->drain_budget(res, delta);
-                        encountered_active = 1;
+                        TRACE("sup_charge_budget ACTIVE R%u drain %llu\n", res->id, delta);
+                        if (encountered_active == 0 && res->blocked_by_ghost == 0) {
+                                TRACE("DRAIN !!\n");
+                                res->ops->drain_budget(res, delta);
+                                encountered_active = 1;
+                        }
                 } else {
                         BUG_ON(res->state != RESERVATION_ACTIVE_IDLE);
                         res->ops->drain_budget(res, delta);
@@ -207,9 +213,9 @@ static void sup_charge_budget(
                                 res->id, res->cur_budget);
                          sup_scheduler_update_after(sup_env, res->cur_budget);
                 }
-                if (encountered_active)
+                //if (encountered_active)
                         /* stop at the first ACTIVE reservation */
-                        break;
+                        //break;
         }
         TRACE("finished charging budgets\n");
 }
@@ -317,3 +323,356 @@ void sup_init(struct sup_reservation_environment* sup_env)
 
         sup_env->next_scheduler_update = SUP_NO_SCHEDULER_UPDATE;
 }
+
+/* NOTE: Namhoon's implementation starts below. */
+struct reservation* gmp_find_by_id(struct gmp_reservation_environment* gmp_env,
+        unsigned int id)
+{
+        struct reservation *res;
+
+        list_for_each_entry(res, &gmp_env->active_reservations, list) {
+                if (res->id == id)
+                        return res;
+        }
+        list_for_each_entry(res, &gmp_env->inactive_reservations, list) {
+                if (res->id == id)
+                        return res;
+        }
+        list_for_each_entry(res, &gmp_env->depleted_reservations, list) {
+                if (res->id == id)
+                        return res;
+        }
+
+        return NULL;
+}
+
+
+struct next_timer_event* gmp_find_event_by_id(struct gmp_reservation_environment* gmp_env,
+        unsigned int id)
+{
+        struct next_timer_event *event;
+
+        list_for_each_entry(event, &gmp_env->next_events, list) {
+                if (event->id == id)
+                        return event;
+        }
+
+        return NULL;
+}
+
+
+struct next_timer_event* gmp_find_event_by_time(struct gmp_reservation_environment* gmp_env,
+        lt_t when)
+{
+        struct next_timer_event *event;
+
+        list_for_each_entry(event, &gmp_env->next_events, list) {
+                if (event->next_update == when)
+                        return event;
+        }
+
+        return NULL;
+}
+
+#define TIMER_RESOLUTION 100000L
+
+static void gmp_add_event(
+        struct gmp_reservation_environment* gmp_env,
+        lt_t when, unsigned int id, event_type_t type)
+{
+        struct next_timer_event *nevent, *queued;
+        struct list_head *pos;
+        int found = 0;
+
+        //when = div64_u64(when, TIMER_RESOLUTION);
+        //when *= TIMER_RESOLUTION;
+//printk(KERN_ALERT "GMP_ADD id=%d type=%d when=%llu\n", id, type, when);
+        nevent = gmp_find_event_by_id(gmp_env, id);
+
+        if (!nevent || nevent->type != type) {
+                nevent = kzalloc(sizeof(*nevent), GFP_ATOMIC);
+                BUG_ON(!nevent);
+                nevent->next_update = when;
+                nevent->id = id;
+                nevent->type = type;
+                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_update > nevent->next_update) {
+                                list_add(&nevent->list, pos->prev);
+                                found = 1;
+                                TRACE("NEXT_EVENT id=%d type=%d update=%llu ADDED at before %llu\n", nevent->id, nevent->type, nevent->next_update, queued->next_update);
+                                break;
+                        }
+                }
+
+                if (!found) {
+                        list_add_tail(&nevent->list, &gmp_env->next_events);
+                        TRACE("NEXT_EVENT id=%d type=%d update=%llu ADDED at TAIL\n", nevent->id, nevent->type, nevent->next_update);
+                }
+        } else {
+                //TRACE("EVENT FOUND id = %d type=%d when=%llu, NEW EVENT type=%d when=%llu\n", nevent->id, nevent->type, nevent->next_update, type, when);
+; //printk(KERN_ALERT "EVENT FOUND id = %d type=%d when=%llu, NEW EVENT type=%d when=%llu\n", nevent->id, nevent->type, nevent->next_update, type, when);
+        }
+
+        //TRACE("======START PRINTING EVENT LIST======\n");
+        //gmp_print_events(gmp_env, litmus_clock());
+        //TRACE("======FINISH PRINTING EVENT LIST======\n");
+}
+
+void gmp_add_event_after(struct gmp_reservation_environment* gmp_env,
+                         lt_t timeout, unsigned int id, event_type_t type)
+{
+        //printk(KERN_ALERT "ADD_EVENT_AFTER id = %d\n", id);
+        gmp_add_event(gmp_env, gmp_env->env.current_time + timeout, id, type);
+}
+
+static void gmp_queue_depleted(
+        struct gmp_reservation_environment* gmp_env,
+        struct reservation *res)
+{
+        struct list_head *pos;
+        struct reservation *queued;
+        int found = 0;
+
+//printk(KERN_ALERT "R%d request to enqueue depleted_list\n", res->id);
+
+        list_for_each(pos, &gmp_env->depleted_reservations) {
+                queued = list_entry(pos, struct reservation, list);
+                if (queued && (queued->next_replenishment > res->next_replenishment)) {
+//printk(KERN_ALERT "QUEUED R%d %llu\n", queued->id, queued->next_replenishment);
+                        list_add(&res->list, pos->prev);
+                        found = 1;
+                        break;
+                }
+        }
+
+        if (!found)
+                list_add_tail(&res->list, &gmp_env->depleted_reservations);
+
+        TRACE("R%d queued to depleted_list\n", res->id);
+//printk(KERN_ALERT "R%d queued to depleted_list\n", res->id);
+        gmp_add_event(gmp_env, res->next_replenishment, res->id, EVENT_REPLENISH);
+}
+
+static void gmp_queue_active(
+        struct gmp_reservation_environment* gmp_env,
+        struct reservation *res)
+{
+        struct list_head *pos;
+        struct reservation *queued;
+        int check_preempt = 1, found = 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);
+                        found = 1;
+                        break;
+                } else if (queued->scheduled_on == NO_CPU)
+                        check_preempt = 0;
+        }
+
+        if (!found)
+                list_add_tail(&res->list, &gmp_env->active_reservations);
+
+        /* check for possible preemption */
+        if (res->state == RESERVATION_ACTIVE && check_preempt)
+                gmp_env->schedule_now++;
+
+        gmp_add_event_after(gmp_env, res->cur_budget, res->id, EVENT_DRAIN);
+        res->event_added = 1;
+}
+
+static void gmp_queue_reservation(
+        struct gmp_reservation_environment* gmp_env,
+        struct reservation *res)
+{
+
+//printk(KERN_ALERT "DEBUG: Passed %s %d %p R%d STATE %d\n",__FUNCTION__,__LINE__, gmp_env, res->id, res->state);
+        switch (res->state) {
+                case RESERVATION_INACTIVE:
+                        list_add(&res->list, &gmp_env->inactive_reservations);
+                        break;
+
+                case RESERVATION_DEPLETED:
+                        gmp_queue_depleted(gmp_env, res);
+                        break;
+
+                case RESERVATION_ACTIVE_IDLE:
+                case RESERVATION_ACTIVE:
+                        gmp_queue_active(gmp_env, res);
+                        break;
+        }
+}
+
+void gmp_add_new_reservation(
+        struct gmp_reservation_environment* gmp_env,
+        struct reservation* new_res)
+{
+        new_res->env = &gmp_env->env;
+        gmp_queue_reservation(gmp_env, new_res);
+}
+
+static void gmp_charge_budget(
+        struct gmp_reservation_environment* gmp_env,
+        lt_t delta)
+{
+        struct list_head *pos, *next;
+        struct reservation *res;
+
+        list_for_each_safe(pos, next, &gmp_env->active_reservations) {
+                int drained = 0;
+                /* charge all ACTIVE_IDLE up to the first ACTIVE reservation */
+                res = list_entry(pos, struct reservation, list);
+                if (res->state == RESERVATION_ACTIVE) {
+                        TRACE("gmp_charge_budget ACTIVE R%u scheduled_on=%d drain %llu\n", res->id, res->scheduled_on, delta);
+                        if (res->scheduled_on != NO_CPU
+                            && res->blocked_by_ghost == 0) {
+                                TRACE("DRAIN !!\n");
+                                drained = 1;
+                                res->ops->drain_budget(res, delta);
+                        } else {
+                                TRACE("NO DRAIN (not scheduled)!!\n");
+                        }
+                } else {
+                        //BUG_ON(res->state != RESERVATION_ACTIVE_IDLE);
+                        if (res->state != RESERVATION_ACTIVE_IDLE)
+                                TRACE("BUG!!!!!!!!!!!! gmp_charge_budget()\n");
+                        TRACE("gmp_charge_budget INACTIVE R%u drain %llu\n",
+                              res->id, delta);
+                        //if (res->is_ghost == 1) {
+                                TRACE("DRAIN !!\n");
+                                drained = 1;
+                                res->ops->drain_budget(res, delta);
+                        //}
+                }
+                if ((res->state == RESERVATION_ACTIVE ||
+                        res->state == RESERVATION_ACTIVE_IDLE) && (drained == 1))
+                {
+                        /* make sure scheduler is invoked when this reservation expires
+                         * its remaining budget */
+                         TRACE("requesting gmp_scheduler update for reservation %u in %llu nanoseconds\n", res->id, res->cur_budget);
+                         gmp_add_event_after(gmp_env, res->cur_budget, res->id, EVENT_DRAIN);
+                         res->event_added = 1;
+                }
+                //if (encountered_active == 2)
+                        /* stop at the first ACTIVE reservation */
+                //      break;
+        }
+        TRACE("finished charging budgets\n");
+}
+
+static void gmp_replenish_budgets(struct gmp_reservation_environment* gmp_env)
+{
+        struct list_head *pos, *next;
+        struct reservation *res;
+
+        list_for_each_safe(pos, next, &gmp_env->depleted_reservations) {
+                res = list_entry(pos, struct reservation, list);
+                if (res->next_replenishment <= gmp_env->env.current_time) {
+                        res->ops->replenish(res);
+                } else {
+                        /* list is ordered by increasing depletion times */
+                        break;
+                }
+        }
+        TRACE("finished replenishing budgets\n");
+}
+
+#define EPSILON 50
+
+/* return schedule_now */
+int gmp_update_time(
+        struct gmp_reservation_environment* gmp_env,
+        lt_t now)
+{
+        struct next_timer_event *event, *next;
+        lt_t delta, ret;
+
+        /* If the time didn't advance, there is nothing to do.
+         * This check makes it safe to call sup_advance_time() potentially
+         * multiple times (e.g., via different code paths. */
+        //TRACE("(gmp_update_time) now: %llu, current_time: %llu\n", now, gmp_env->env.current_time);
+        if (unlikely(now <= gmp_env->env.current_time + EPSILON))
+                return 0;
+
+        delta = now - gmp_env->env.current_time;
+        gmp_env->env.current_time = now;
+
+
+        //gmp_print_events(gmp_env, now);
+        /* deplete budgets by passage of time */
+        //TRACE("CHARGE###\n");
+        gmp_charge_budget(gmp_env, delta);
+
+        /* check if any budgets where replenished */
+        //TRACE("REPLENISH###\n");
+        gmp_replenish_budgets(gmp_env);
+
+
+        list_for_each_entry_safe(event, next, &gmp_env->next_events, list) {
+                if (event->next_update < now) {
+                        list_del(&event->list);
+                        TRACE("EVENT at %llu IS DELETED\n", event->next_update);
+                        kfree(event);
+                } else {
+                        break;
+                }
+        }
+
+        //gmp_print_events(gmp_env, litmus_clock());
+
+        ret = min(gmp_env->schedule_now, NR_CPUS);
+        gmp_env->schedule_now = 0;
+
+        return ret;
+}
+
+void gmp_print_events(struct gmp_reservation_environment* gmp_env, lt_t now)
+{
+        struct next_timer_event *event, *next;
+
+        TRACE("GLOBAL EVENTS now=%llu\n", now);
+        list_for_each_entry_safe(event, next, &gmp_env->next_events, list) {
+                TRACE("at %llu type=%d id=%d armed_on=%d\n", event->next_update, event->type, event->id, event->timer_armed_on);
+        }
+}
+
+static void gmp_res_change_state(
+        struct reservation_environment* env,
+        struct reservation *res,
+        reservation_state_t new_state)
+{
+        struct gmp_reservation_environment* gmp_env;
+
+        gmp_env = container_of(env, struct gmp_reservation_environment, env);
+
+        TRACE("GMP reservation R%d state %d->%d at %llu\n",
+                res->id, res->state, new_state, env->current_time);
+
+        list_del(&res->list);
+        /* check if we need to reschedule because we lost an active reservation */
+        if (res->state == RESERVATION_ACTIVE)
+                gmp_env->schedule_now++;
+        res->state = new_state;
+        gmp_queue_reservation(gmp_env, res);
+}
+
+void gmp_init(struct gmp_reservation_environment* gmp_env)
+{
+        memset(gmp_env, sizeof(*gmp_env), 0);
+
+        INIT_LIST_HEAD(&gmp_env->active_reservations);
+        INIT_LIST_HEAD(&gmp_env->depleted_reservations);
+        INIT_LIST_HEAD(&gmp_env->inactive_reservations);
+        INIT_LIST_HEAD(&gmp_env->next_events);
+
+        gmp_env->env.change_state = gmp_res_change_state;
+
+        gmp_env->schedule_now = 0;
+        gmp_env->will_schedule = false;
+
+        raw_spin_lock_init(&gmp_env->lock);
+}