MC2 scheduler and partition modules

8 files changed, 408 insertions, 2 deletions

diff --git a/include/litmus/cache_proc.h b/include/litmus/cache_proc.h
index 586224118435..962851da34cc 100644
--- a/include/litmus/cache_proc.h
+++ b/include/litmus/cache_proc.h
@@ -4,6 +4,11 @@
 #ifdef __KERNEL__
 
 void litmus_setup_lockdown(void __iomem*, u32);
+void enter_irq_mode(void);
+void exit_irq_mode(void);
+void flush_cache(int all);
+
+extern struct page *new_alloc_page_color(unsigned long color);
 
 #endif
 
diff --git a/include/litmus/litmus.h b/include/litmus/litmus.h
index a6eb534ee0fa..441210c84ed8 100644
--- a/include/litmus/litmus.h
+++ b/include/litmus/litmus.h
@@ -113,6 +113,13 @@ static inline lt_t litmus_clock(void)
         ((current)->state == TASK_RUNNING ||    \
          preempt_count() & PREEMPT_ACTIVE)
 
+#define is_running(t)                   \
+        ((t)->state == TASK_RUNNING ||  \
+         task_thread_info(t)->preempt_count & PREEMPT_ACTIVE)
+
+#define is_blocked(t)       \
+        (!is_running(t))
+
 #define is_released(t, now)     \
         (lt_before_eq(get_release(t), now))
 #define is_tardy(t, now)    \
diff --git a/include/litmus/mc2_common.h b/include/litmus/mc2_common.h
new file mode 100644
index 000000000000..e3c0af28f1b9
--- /dev/null
+++ b/include/litmus/mc2_common.h
@@ -0,0 +1,31 @@
+/*
+ * MC^2 common data structures
+ */
+ 
+#ifndef __UNC_MC2_COMMON_H__
+#define __UNC_MC2_COMMON_H__
+
+enum crit_level {
+        CRIT_LEVEL_A = 0,
+        CRIT_LEVEL_B = 1,
+        CRIT_LEVEL_C = 2,
+        NUM_CRIT_LEVELS = 3,
+};
+
+struct mc2_task {
+        enum crit_level crit;
+        unsigned int res_id;
+};
+
+#ifdef __KERNEL__
+
+#include <litmus/reservation.h>
+
+#define tsk_mc2_data(t)         (tsk_rt(t)->mc2_data)
+
+long mc2_task_client_init(struct task_client *tc, struct mc2_task *mc2_param, struct task_struct *tsk,
+                                                        struct reservation *res);
+        
+#endif /* __KERNEL__ */
+
+#endif
\ No newline at end of file
diff --git a/include/litmus/polling_reservations.h b/include/litmus/polling_reservations.h
new file mode 100644
index 000000000000..66c9b1e31f20
--- /dev/null
+++ b/include/litmus/polling_reservations.h
@@ -0,0 +1,36 @@
+#ifndef LITMUS_POLLING_RESERVATIONS_H
+#define LITMUS_POLLING_RESERVATIONS_H
+
+#include <litmus/reservation.h>
+
+struct polling_reservation {
+        /* extend basic reservation */
+        struct reservation res;
+
+        lt_t max_budget;
+        lt_t period;
+        lt_t deadline;
+        lt_t offset;
+};
+
+void polling_reservation_init(struct polling_reservation *pres, int use_edf_prio,
+        int use_periodic_polling, lt_t budget, lt_t period, lt_t deadline, lt_t offset);
+
+struct table_driven_reservation {
+        /* extend basic reservation */
+        struct reservation res;
+
+        lt_t major_cycle;
+        unsigned int next_interval;
+        unsigned int num_intervals;
+        struct lt_interval *intervals;
+
+        /* info about current scheduling slot */
+        struct lt_interval cur_interval;
+        lt_t major_cycle_start;
+};
+
+void table_driven_reservation_init(struct table_driven_reservation *tdres,
+        lt_t major_cycle, struct lt_interval *intervals, unsigned int num_intervals);
+
+#endif
diff --git a/include/litmus/reservation.h b/include/litmus/reservation.h
new file mode 100644
index 000000000000..7e022b34470f
--- /dev/null
+++ b/include/litmus/reservation.h
@@ -0,0 +1,256 @@
+#ifndef LITMUS_RESERVATION_H
+#define LITMUS_RESERVATION_H
+
+#include <linux/list.h>
+#include <linux/hrtimer.h>
+
+struct reservation_client;
+struct reservation_environment;
+struct reservation;
+
+typedef enum {
+        /* reservation has no clients, is not consuming budget */
+        RESERVATION_INACTIVE = 0,
+
+        /* reservation has clients, consumes budget when scheduled */
+        RESERVATION_ACTIVE,
+
+        /* reservation has no clients, but may be consuming budget */
+        RESERVATION_ACTIVE_IDLE,
+
+        /* Reservation has no budget and waits for
+         * replenishment. May or may not have clients. */
+        RESERVATION_DEPLETED,
+} reservation_state_t;
+
+
+/* ************************************************************************** */
+
+/* Select which task to dispatch. If NULL is returned, it means there is nothing
+ * to schedule right now and background work can be scheduled. */
+typedef struct task_struct * (*dispatch_t)  (
+        struct reservation_client *client
+);
+
+/* Something that can be managed in a reservation and that can yield
+ * a process for dispatching. Contains a pointer to the reservation
+ * to which it "belongs". */
+struct reservation_client {
+        struct list_head list;
+        struct reservation* reservation;
+        dispatch_t dispatch;
+};
+
+
+/* ************************************************************************** */
+
+/* Called by reservations to request state change. */
+typedef void (*reservation_change_state_t)  (
+        struct reservation_environment* env,
+        struct reservation *res,
+        reservation_state_t new_state
+);
+
+/* The framework within wich reservations operate. */
+struct reservation_environment {
+        lt_t time_zero;
+        lt_t current_time;
+
+        /* services invoked by reservations */
+        reservation_change_state_t change_state;
+};
+
+
+/* ************************************************************************** */
+
+/* A new client is added or an existing client resumes. */
+typedef void (*client_arrives_t)  (
+        struct reservation *reservation,
+        struct reservation_client *client
+);
+
+/* A client suspends or terminates. */
+typedef void (*client_departs_t)  (
+        struct reservation *reservation,
+        struct reservation_client *client,
+        int did_signal_job_completion
+);
+
+/* A previously requested replenishment has occurred. */
+typedef void (*on_replenishment_timer_t)  (
+        struct reservation *reservation
+);
+
+/* Update the reservation's budget to reflect execution or idling. */
+typedef void (*drain_budget_t) (
+        struct reservation *reservation,
+        lt_t how_much
+);
+
+/* Select a ready task from one of the clients for scheduling. */
+typedef struct task_struct* (*dispatch_client_t)  (
+        struct reservation *reservation,
+        lt_t *time_slice /* May be used to force rescheduling after
+                            some amount of time. 0 => no limit */
+);
+
+
+struct reservation_ops {
+        dispatch_client_t dispatch_client;
+
+        client_arrives_t client_arrives;
+        client_departs_t client_departs;
+
+        on_replenishment_timer_t replenish;
+        drain_budget_t drain_budget;
+};
+
+struct reservation {
+        /* used to queue in environment */
+        struct list_head list;
+
+        reservation_state_t state;
+        unsigned int id;
+
+        /* exact meaning defined by impl. */
+        lt_t priority;
+        lt_t cur_budget;
+        lt_t next_replenishment;
+
+        /* budget stats */
+        lt_t budget_consumed; /* how much budget consumed in this allocation cycle? */
+        lt_t budget_consumed_total;
+
+        /* interaction with framework */
+        struct reservation_environment *env;
+        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);
+
+/* Default implementations */
+
+/* simply select the first client in the list, set *for_at_most to zero */
+struct task_struct* default_dispatch_client(
+        struct reservation *res,
+        lt_t *for_at_most
+);
+
+/* "connector" reservation client to hook up tasks with reservations */
+struct task_client {
+        struct reservation_client client;
+        struct task_struct *task;
+};
+
+void task_client_init(struct task_client *tc, struct task_struct *task,
+        struct reservation *reservation);
+
+#define SUP_RESCHEDULE_NOW (0)
+#define SUP_NO_SCHEDULER_UPDATE (ULLONG_MAX)
+
+/* A simple uniprocessor (SUP) flat (i.e., non-hierarchical) reservation
+ * environment.
+ */
+struct sup_reservation_environment {
+        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;
+
+        /* - SUP_RESCHEDULE_NOW means call sup_dispatch() now
+         * - SUP_NO_SCHEDULER_UPDATE means nothing to do
+         * any other value means program a timer for the given time
+         */
+        lt_t next_scheduler_update;
+        /* set to true if a call to sup_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 sup_init(struct sup_reservation_environment* sup_env);
+void sup_add_new_reservation(struct sup_reservation_environment* sup_env,
+        struct reservation* new_res);
+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/include/litmus/rt_param.h b/include/litmus/rt_param.h
index 7b9a90965c25..998762051a6b 100644
--- a/include/litmus/rt_param.h
+++ b/include/litmus/rt_param.h
@@ -62,6 +62,7 @@ typedef enum {
 #define LITMUS_MAX_PRIORITY     512
 #define LITMUS_HIGHEST_PRIORITY   1
 #define LITMUS_LOWEST_PRIORITY    (LITMUS_MAX_PRIORITY - 1)
+#define LITMUS_NO_PRIORITY              UINT_MAX
 
 /* Provide generic comparison macros for userspace,
  * in case that we change this later. */
@@ -71,6 +72,46 @@ typedef enum {
         ((p) >= LITMUS_HIGHEST_PRIORITY &&      \
          (p) <= LITMUS_LOWEST_PRIORITY)
 
+/* reservation support */
+
+typedef enum {
+        PERIODIC_POLLING,
+        SPORADIC_POLLING,
+        TABLE_DRIVEN,
+} reservation_type_t;
+
+struct lt_interval {
+        lt_t start;
+        lt_t end;
+};
+
+#ifndef __KERNEL__
+#define __user
+#endif
+
+struct reservation_config {
+        unsigned int id;
+        lt_t priority;
+        int  cpu;
+
+        union {
+                struct {
+                        lt_t period;
+                        lt_t budget;
+                        lt_t relative_deadline;
+                        lt_t offset;
+                } polling_params;
+
+                struct {
+                        lt_t major_cycle_length;
+                        unsigned int num_intervals;
+                        struct lt_interval __user *intervals;
+                } table_driven_params;
+        };
+};
+
+/* regular sporadic task support */
+
 struct rt_task {
         lt_t            exec_cost;
         lt_t            period;
@@ -165,6 +206,7 @@ struct rt_job {
 };
 
 struct pfair_param;
+struct mc2_task;
 
 /*      RT task parameters for scheduling extensions
  *      These parameters are inherited during clone and therefore must
@@ -246,7 +288,10 @@ struct rt_param {
         volatile int            linked_on;
 
         /* PFAIR/PD^2 state. Allocated on demand. */
-        struct pfair_param*     pfair;
+        union {
+                void *plugin_state;
+                struct pfair_param *pfair;
+        };
 
         /* Fields saved before BE->RT transition.
          */
@@ -275,6 +320,10 @@ struct rt_param {
 
         /* Pointer to the page shared between userspace and kernel. */
         struct control_page * ctrl_page;
+
+        /* Mixed-criticality specific data */
+        struct mc2_task* mc2_data;
+        unsigned long addr_ctrl_page;
 };
 
 #endif
diff --git a/include/litmus/sched_plugin.h b/include/litmus/sched_plugin.h
index f36bb3875f58..4c8aaa6b6674 100644
--- a/include/litmus/sched_plugin.h
+++ b/include/litmus/sched_plugin.h
@@ -83,6 +83,10 @@ typedef void (*synchronous_release_at_t)(lt_t time_zero);
  * reservation-specific values. */
 typedef void (*current_budget_t)(lt_t *used_so_far, lt_t *remaining);
 
+/* Reservation creation/removal backends. Meaning of reservation_type and
+ * reservation_id are entirely plugin-specific. */
+typedef long (*reservation_create_t)(int reservation_type, void* __user config);
+typedef long (*reservation_destroy_t)(unsigned int reservation_id, int cpu);
 
 /************************ misc routines ***********************/
 
@@ -118,6 +122,10 @@ struct sched_plugin {
 
         current_budget_t        current_budget;
 
+        /* Reservation support */
+        reservation_create_t    reservation_create;
+        reservation_destroy_t   reservation_destroy;
+
 #ifdef CONFIG_LITMUS_LOCKING
         /*      locking protocols       */
         allocate_lock_t         allocate_lock;
diff --git a/include/litmus/trace.h b/include/litmus/trace.h
index 601787214037..24ca412e1184 100644
--- a/include/litmus/trace.h
+++ b/include/litmus/trace.h
@@ -118,6 +118,9 @@ feather_callback void save_cpu_task_latency(unsigned long event, unsigned long w
 #define TS_TICK_START(t)                CPU_TTIMESTAMP(110, t)
 #define TS_TICK_END(t)                  CPU_TTIMESTAMP(111, t)
 
+#define TS_RELEASE_C_START              CPU_DTIMESTAMP(108, TSK_RT)
+#define TS_RELEASE_C_END                CPU_DTIMESTAMP(109, TSK_RT)
+
 #define TS_QUANTUM_BOUNDARY_START       CPU_TIMESTAMP_CUR(112)
 #define TS_QUANTUM_BOUNDARY_END         CPU_TIMESTAMP_CUR(113)
 
@@ -137,6 +140,17 @@ feather_callback void save_cpu_task_latency(unsigned long event, unsigned long w
 #define TS_SEND_RESCHED_START(c)        MSG_TIMESTAMP_SENT(190, c)
 #define TS_SEND_RESCHED_END             MSG_TIMESTAMP_RECEIVED(191)
 
-#define TS_RELEASE_LATENCY(when)        CPU_LTIMESTAMP(208, &(when))
+#define TS_ISR_START                    CPU_TIMESTAMP_CUR(192)
+#define TS_ISR_END                              CPU_TIMESTAMP_CUR(193)
+
+#define TS_RELEASE_LATENCY(when)    CPU_LTIMESTAMP(208, &(when))
+#define TS_RELEASE_LATENCY_A(when)  CPU_LTIMESTAMP(209, &(when))
+#define TS_RELEASE_LATENCY_B(when)  CPU_LTIMESTAMP(210, &(when))
+#define TS_RELEASE_LATENCY_C(when)  CPU_LTIMESTAMP(211, &(when))
+
+#define TS_SCHED_A_START                        CPU_DTIMESTAMP(212, TSK_UNKNOWN)
+#define TS_SCHED_A_END(t)                       CPU_TTIMESTAMP(213, t)
+#define TS_SCHED_C_START                        CPU_DTIMESTAMP(214, TSK_UNKNOWN)
+#define TS_SCHED_C_END(t)                       CPU_TTIMESTAMP(215, t)
 
 #endif /* !_SYS_TRACE_H_ */