Patched reservation implementation of MC^2 version

Patched using Namhoon's implementation of reservation for MC^2 to
support global multiprocessor scheduling.
Patched compiler-gcc5 to support gcc v5 compiler.

Bug fixed regarding user input big cpu id number causing kernel crash.

4 files changed, 498 insertions, 7 deletions

diff --git a/include/linux/compiler-gcc5.h b/include/linux/compiler-gcc5.h
new file mode 100644
index 000000000000..cec40d7428cf
--- /dev/null
+++ b/include/linux/compiler-gcc5.h
@@ -0,0 +1,66 @@
+#ifndef __LINUX_COMPILER_H
+#error "Please don't include <linux/compiler-gcc5.h> directly, include <linux/compiler.h> instead."
+#endif
+
+#define __used                         __attribute__((__used__))
+#define __must_check                   __attribute__((warn_unused_result))
+#define __compiler_offsetof(a, b)      __builtin_offsetof(a, b)
+
+/* Mark functions as cold. gcc will assume any path leading to a call
+   to them will be unlikely.  This means a lot of manual unlikely()s
+   are unnecessary now for any paths leading to the usual suspects
+   like BUG(), printk(), panic() etc. [but let's keep them for now for
+   older compilers]
+
+   Early snapshots of gcc 4.3 don't support this and we can't detect this
+   in the preprocessor, but we can live with this because they're unreleased.
+   Maketime probing would be overkill here.
+
+   gcc also has a __attribute__((__hot__)) to move hot functions into
+   a special section, but I don't see any sense in this right now in
+   the kernel context */
+#define __cold                 __attribute__((__cold__))
+
+#define __UNIQUE_ID(prefix) __PASTE(__PASTE(__UNIQUE_ID_, prefix), __COUNTER__)
+
+#ifndef __CHECKER__
+# define __compiletime_warning(message) __attribute__((warning(message)))
+# define __compiletime_error(message) __attribute__((error(message)))
+#endif /* __CHECKER__ */
+
+/*
+ * Mark a position in code as unreachable.  This can be used to
+ * suppress control flow warnings after asm blocks that transfer
+ * control elsewhere.
+ *
+ * Early snapshots of gcc 4.5 don't support this and we can't detect
+ * this in the preprocessor, but we can live with this because they're
+ * unreleased.  Really, we need to have autoconf for the kernel.
+ */
+#define unreachable() __builtin_unreachable()
+
+/* Mark a function definition as prohibited from being cloned. */
+#define __noclone      __attribute__((__noclone__))
+
+/*
+ * Tell the optimizer that something else uses this function or variable.
+ */
+#define __visible __attribute__((externally_visible))
+
+/*
+ * GCC 'asm goto' miscompiles certain code sequences:
+ *
+ *   http://gcc.gnu.org/bugzilla/show_bug.cgi?id=58670
+ *
+ * Work it around via a compiler barrier quirk suggested by Jakub Jelinek.
+ * Fixed in GCC 4.8.2 and later versions.
+ *
+ * (asm goto is automatically volatile - the naming reflects this.)
+ */
+#define asm_volatile_goto(x...)        do { asm goto(x); asm (""); } while (0)
+
+#ifdef CONFIG_ARCH_USE_BUILTIN_BSWAP
+#define __HAVE_BUILTIN_BSWAP32__
+#define __HAVE_BUILTIN_BSWAP64__
+#define __HAVE_BUILTIN_BSWAP16__
+#endif /* CONFIG_ARCH_USE_BUILTIN_BSWAP */
diff --git a/include/litmus/reservation.h b/include/litmus/reservation.h
index 4eecd3f088e8..af1fba297bf5 100644
--- a/include/litmus/reservation.h
+++ b/include/litmus/reservation.h
@@ -126,6 +126,14 @@ struct reservation {
         struct reservation_ops *ops;
 
         struct list_head clients;
+
+        /* for global env. */
+        int scheduled_on;
+        int event_added;
+        /* for blocked by ghost. Do not charge budget when ACTIVE */
+        int blocked_by_ghost;
+        /* ghost_job. If it is clear, do not charge budget when ACTIVE_IDLE */
+        int is_ghost;
 };
 
 void reservation_init(struct reservation *res);
@@ -185,10 +193,67 @@ struct sup_reservation_environment {
 void sup_init(struct sup_reservation_environment* sup_env);
 void sup_add_new_reservation(struct sup_reservation_environment* sup_env,
         struct reservation* new_res);
+/*
+ * TODO this function is added from Namhoon's implementation for MC^2.
+ * The need of this declaration is that it's used explicitly outside.
+ */
+void sup_scheduler_update_after(struct sup_reservation_environment* sup_env,
+        lt_t timeout);
 void sup_update_time(struct sup_reservation_environment* sup_env, lt_t now);
 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);
 
+/* A global multiprocessor reservation environment. */
+
+typedef enum {
+        EVENT_REPLENISH = 0,
+        EVENT_DRAIN,
+        EVENT_OTHERS,
+} event_type_t;
+
+
+struct next_timer_event {
+        lt_t next_update;
+        int timer_armed_on;
+        unsigned int id;
+        event_type_t type;
+        struct list_head list;
+};
+
+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;
+
+        /* timer event ordered by next_update */
+        struct list_head next_events;
+
+        /* (schedule_now == true) means call gmp_dispatch() now */
+        int schedule_now;
+        /* set to true if a call to gmp_dispatch() is imminent */
+        bool will_schedule;
+};
+
+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_add_event_after(struct gmp_reservation_environment* gmp_env,
+        lt_t timeout, unsigned int id, event_type_t type);
+void gmp_print_events(struct gmp_reservation_environment* gmp_env, lt_t now);
+int gmp_update_time(struct gmp_reservation_environment* gmp_env, lt_t now);
+struct task_struct* gmp_dispatch(struct gmp_reservation_environment* gmp_env);
+struct next_timer_event* gmp_find_event_by_id(struct gmp_reservation_environment* gmp_env, unsigned int id);
+struct next_timer_event* gmp_find_event_by_time(struct gmp_reservation_environment* gmp_env, lt_t when);
+struct reservation* gmp_find_by_id(struct gmp_reservation_environment* gmp_env,
+        unsigned int id);
 #endif
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);
+}
diff --git a/litmus/sched_pres.c b/litmus/sched_pres.c
index e2d48101c890..23fe8f3ebfa9 100644
--- a/litmus/sched_pres.c
+++ b/litmus/sched_pres.c
@@ -392,7 +392,6 @@ static long create_polling_reservation(
         int use_edf  = config->priority == LITMUS_NO_PRIORITY;
         int periodic =  res_type == PERIODIC_POLLING;
         long err = -EINVAL;
-
         if (config->polling_params.budget >
             config->polling_params.period) {
                 printk(KERN_ERR "invalid polling reservation (%u): "
@@ -558,7 +557,9 @@ static long pres_reservation_create(int res_type, void* __user _config)
         if (copy_from_user(&config, _config, sizeof(config)))
                 return -EFAULT;
 
-        if (config.cpu < 0 || !cpu_online(config.cpu)) {
+        if (config.cpu < 0
+            || config.cpu >= nr_cpu_ids /* in case big number causes crash */
+            || !cpu_online(config.cpu)) {
                 printk(KERN_ERR "invalid polling reservation (%u): "
                        "CPU %d offline\n", config.id, config.cpu);
                 return -EINVAL;