11 files changed, 339 insertions, 33 deletions

diff --git a/include/litmus/budget.h b/include/litmus/budget.h
index 732530e63491..6ef0e44effb1 100644
--- a/include/litmus/budget.h
+++ b/include/litmus/budget.h
@@ -1,8 +1,24 @@
 #ifndef _LITMUS_BUDGET_H_
 #define _LITMUS_BUDGET_H_
 
-/* Update the per-processor enforcement timer (arm/reproram/cancel) for
- * the next task. */
+struct enforcement_timer {
+        struct hrtimer          timer;
+        int                     armed;
+};
+
+/**
+ * update_enforcement_timer() - Update per-processor enforcement timer for
+ * the next scheduled task.
+ *
+ * If @t is not NULL and has a precisely enforced budget, the timer will be
+ * armed to trigger a reschedule when the budget is exhausted. Otherwise,
+ * the timer will be cancelled.
+*/
 void update_enforcement_timer(struct task_struct* t);
 
+void init_enforcement_timer(struct enforcement_timer *et);
+
+void arm_enforcement_timer(struct enforcement_timer* et, struct task_struct* t);
+
+void cancel_enforcement_timer(struct enforcement_timer* et);
 #endif
diff --git a/include/litmus/color.h b/include/litmus/color.h
index 998af33cd3ea..250f08a6e1f3 100644
--- a/include/litmus/color.h
+++ b/include/litmus/color.h
@@ -1,6 +1,11 @@
 #ifndef LITMUS_COLOR_H
 #define LITMUS_COLOR_H
 
+#define NUM_COLORS 64
+#define NUM_WAYS   12
+
+#ifdef __KERNEL__
+
 #define ONE_COLOR_LEN 11
 #define ONE_COLOR_FMT "%4lu: %4d\n"
 
@@ -16,6 +21,8 @@ void add_page_to_color_list(struct page*);
 void add_page_to_alloced_list(struct page*, struct vm_area_struct*);
 void reclaim_pages(struct vm_area_struct*);
 
+int color_server_params(int cpu, unsigned long *wcet, unsigned long *period);
+
 int color_add_pages_handler(struct ctl_table *, int, void __user *,
                 size_t *, loff_t *);
 int color_nr_pages_handler(struct ctl_table *, int, void __user *,
@@ -38,3 +45,5 @@ int color_reclaim_pages_handler(struct ctl_table *, int, void __user *,
 #endif
 
 #endif
+
+#endif
diff --git a/include/litmus/dgl.h b/include/litmus/dgl.h
new file mode 100644
index 000000000000..2bf61d4a7547
--- /dev/null
+++ b/include/litmus/dgl.h
@@ -0,0 +1,61 @@
+#ifndef __DGL_H_
+#define __DGL_H_
+
+#include <litmus/color.h>
+#include <linux/list.h>
+
+#define WP(num, word) (num / word + (num % word != 0))
+
+#define NUM_REPLICAS  NUM_WAYS
+#define NUM_RESOURCES NUM_COLORS
+#define MASK_SIZE     (sizeof(unsigned long) * 8)
+#define MASK_WORDS    WP(NUM_RESOURCES, MASK_SIZE)
+
+/*
+ * A request for @replica amount of a single resource.
+ */
+struct dgl_req {
+        unsigned short          replicas;
+        struct list_head        list;
+};
+
+/*
+ * Simultaneous @requests for multiple resources.
+ */
+struct dgl_group_req {
+        int                     cpu;
+        unsigned long           requested[MASK_WORDS];
+        unsigned long           waiting[MASK_WORDS];
+        struct dgl_req          requests[NUM_RESOURCES];
+        unsigned long long      ts;
+};
+
+/*
+ * A single resource.
+ */
+struct dgl_resource {
+        unsigned int            free_replicas;
+        struct list_head        waiting;
+};
+
+/*
+ * A group of resources.
+ */
+struct dgl {
+        struct dgl_resource     resources[NUM_RESOURCES];
+        struct dgl_group_req*   acquired[NR_CPUS];
+
+        char                    requests;
+        char                    running;
+        unsigned long long      ts;
+};
+
+void dgl_init(struct dgl *dgl);
+void dgl_group_req_init(struct dgl_group_req *greq);
+
+void set_req(struct dgl_group_req *greq, int resource, int replicas);
+
+void add_group_req(struct dgl *dgl, struct dgl_group_req *greq, int cpu);
+void remove_group_req(struct dgl *dgl, struct dgl_group_req *greq);
+
+#endif
diff --git a/include/litmus/fifo_common.h b/include/litmus/fifo_common.h
new file mode 100644
index 000000000000..4756f77bd511
--- /dev/null
+++ b/include/litmus/fifo_common.h
@@ -0,0 +1,25 @@
+/*
+ * EDF common data structures and utility functions shared by all EDF
+ * based scheduler plugins
+ */
+
+/* CLEANUP: Add comments and make it less messy.
+ *
+ */
+
+#ifndef __FIFO_COMMON_H__
+#define __FIFO_COMMON_H__
+
+#include <litmus/rt_domain.h>
+
+void fifo_domain_init(rt_domain_t* rt, check_resched_needed_t resched,
+                      release_jobs_t release);
+
+int fifo_higher_prio(struct task_struct* first,
+                    struct task_struct* second);
+
+int fifo_ready_order(struct bheap_node* a, struct bheap_node* b);
+
+int fifo_preemption_needed(rt_domain_t* rt, struct task_struct *t);
+
+#endif
diff --git a/include/litmus/litmus.h b/include/litmus/litmus.h
index 0b071fd359f9..f0ddb89e68dd 100644
--- a/include/litmus/litmus.h
+++ b/include/litmus/litmus.h
@@ -44,6 +44,8 @@ void litmus_exit_task(struct task_struct *tsk);
 
 #define tsk_rt(t)               (&(t)->rt_param)
 
+#define get_server_job(t) (tsk_rt(t)->job_params.fake_job_no)
+
 /*      Realtime utility macros */
 #define get_rt_flags(t)         (tsk_rt(t)->flags)
 #define set_rt_flags(t,f)       (tsk_rt(t)->flags=(f))
@@ -51,10 +53,13 @@ void litmus_exit_task(struct task_struct *tsk);
 #define get_exec_time(t)        (tsk_rt(t)->job_params.exec_time)
 #define get_rt_period(t)        (tsk_rt(t)->task_params.period)
 #define get_rt_phase(t)         (tsk_rt(t)->task_params.phase)
+#define get_rt_job(t)           (tsk_rt(t)->job_params.job_no)
 #define get_partition(t)        (tsk_rt(t)->task_params.cpu)
 #define get_deadline(t)         (tsk_rt(t)->job_params.deadline)
 #define get_release(t)          (tsk_rt(t)->job_params.release)
 #define get_class(t)            (tsk_rt(t)->task_params.cls)
+#define is_server(t)            (tsk_rt(t)->is_server)
+#define get_task_server(task)      (tsk_rt(task)->server)
 
 #define is_priority_boosted(t)  (tsk_rt(t)->priority_boosted)
 #define get_boost_start(t)      (tsk_rt(t)->boost_start_time)
@@ -128,6 +133,16 @@ void srp_ceiling_block(void);
 
 #define bheap2task(hn) ((struct task_struct*) hn->value)
 
+static inline struct control_page* get_control_page(struct task_struct *t)
+{
+        return tsk_rt(t)->ctrl_page;
+}
+
+static inline int has_control_page(struct task_struct* t)
+{
+        return tsk_rt(t)->ctrl_page != NULL;
+}
+
 #ifdef CONFIG_NP_SECTION
 
 static inline int is_kernel_np(struct task_struct *t)
@@ -230,10 +245,6 @@ static inline int is_np(struct task_struct *t)
         int kernel, user;
         kernel = is_kernel_np(t);
         user   = is_user_np(t);
-        if (kernel || user)
-                TRACE_TASK(t, " is non-preemptive: kernel=%d user=%d\n",
-
-                           kernel, user);
         return kernel || user;
 #else
         return unlikely(is_kernel_np(t) || is_user_np(t));
diff --git a/include/litmus/locking.h b/include/litmus/locking.h
index 4d7b870cb443..41991d5af01b 100644
--- a/include/litmus/locking.h
+++ b/include/litmus/locking.h
@@ -9,6 +9,7 @@ struct litmus_lock_ops;
 struct litmus_lock {
         struct litmus_lock_ops *ops;
         int type;
+        int id;
 };
 
 struct litmus_lock_ops {
diff --git a/include/litmus/rt_domain.h b/include/litmus/rt_domain.h
index ac249292e866..b243f998fef7 100644
--- a/include/litmus/rt_domain.h
+++ b/include/litmus/rt_domain.h
@@ -82,6 +82,8 @@ void __add_ready(rt_domain_t* rt, struct task_struct *new);
 void __merge_ready(rt_domain_t* rt, struct bheap *tasks);
 void __add_release(rt_domain_t* rt, struct task_struct *task);
 
+struct release_heap* release_heap_alloc(int gfp_flags);
+
 static inline struct task_struct* __take_ready(rt_domain_t* rt)
 {
         struct bheap_node* hn = bheap_take(rt->order, &rt->ready_queue);
diff --git a/include/litmus/rt_param.h b/include/litmus/rt_param.h
index ed9b7d20a763..2991fff58bc6 100644
--- a/include/litmus/rt_param.h
+++ b/include/litmus/rt_param.h
@@ -5,6 +5,8 @@
 #ifndef _LINUX_RT_PARAM_H_
 #define _LINUX_RT_PARAM_H_
 
+#include <litmus/color.h>
+
 /* Litmus time type. */
 typedef unsigned long long lt_t;
 
@@ -69,7 +71,10 @@ union np_flag {
 struct control_page {
         volatile union np_flag sched;
 
-        /* to be extended */
+        /* locking overhead tracing: time stamp prior to system call */
+        uint64_t ts_syscall_start; /* Feather-Trace cycles */
+
+        int requests[NUM_COLORS];
 };
 
 #ifndef __KERNEL__
@@ -92,6 +97,8 @@ struct color_ctrl_page {
 struct _rt_domain;
 struct bheap_node;
 struct release_heap;
+struct rt_server;
+struct dgl_group_req;
 
 struct rt_job {
         /* Time instant the the job was or will be released.  */
@@ -128,6 +135,8 @@ struct rt_param {
         /* is the task present? (true if it can be scheduled) */
         unsigned int            present:1;
 
+        unsigned int            is_server:1;
+
 #ifdef CONFIG_LITMUS_LOCKING
         /* Is the task being priority-boosted by a locking protocol? */
         unsigned int            priority_boosted:1;
@@ -135,6 +144,8 @@ struct rt_param {
         lt_t                    boost_start_time;
 #endif
 
+        struct rt_server *server;
+
         /* user controlled parameters */
         struct rt_task          task_params;
 
@@ -213,6 +224,7 @@ struct rt_param {
         struct control_page * ctrl_page;
 
         struct color_ctrl_page *color_ctrl_page;
+        struct dgl_group_req *req;
 };
 
 /*      Possible RT flags       */
diff --git a/include/litmus/rt_server.h b/include/litmus/rt_server.h
new file mode 100644
index 000000000000..0f3147707a3b
--- /dev/null
+++ b/include/litmus/rt_server.h
@@ -0,0 +1,39 @@
+#ifndef __RT_SERVER_H
+#define __RT_SERVER_H
+
+#include <linux/sched.h>
+#include <litmus/litmus.h>
+#include <litmus/rt_domain.h>
+
+struct rt_server;
+
+typedef int (*need_preempt_t)(rt_domain_t *rt, struct task_struct *t);
+typedef void (*server_update_t)(struct rt_server *srv);
+typedef void (*server_requeue_t)(struct rt_server *srv, struct task_struct *t);
+typedef struct task_struct* (*server_take_t)(struct rt_server *srv);
+
+struct rt_server {
+        int sid;
+        int cpu;
+        struct task_struct*     linked;
+        rt_domain_t*            domain;
+        int running;
+
+        /* Does this server have a higher-priority task? */
+        need_preempt_t          need_preempt;
+        /* System state has changed, so should server */
+        server_update_t         update;
+        /* Requeue task in domain */
+        server_requeue_t        requeue;
+        /* Take next task from domain */
+        server_take_t           take;
+};
+
+void init_rt_server(struct rt_server *server,
+                    int sid, int cpu, rt_domain_t *domain,
+                    need_preempt_t need_preempt,
+                    server_requeue_t requeue,
+                    server_update_t update,
+                    server_take_t take);
+
+#endif
diff --git a/include/litmus/sched_plugin.h b/include/litmus/sched_plugin.h
index 6e7cabdddae8..0f529fa78b4d 100644
--- a/include/litmus/sched_plugin.h
+++ b/include/litmus/sched_plugin.h
@@ -11,6 +11,8 @@
 #include <litmus/locking.h>
 #endif
 
+struct litmus_lock;
+
 /************************ setup/tear down ********************/
 
 typedef long (*activate_plugin_t) (void);
@@ -67,6 +69,9 @@ typedef long (*admit_task_t)(struct task_struct* tsk);
 
 typedef void (*release_at_t)(struct task_struct *t, lt_t start);
 
+/* TODO remove me */
+typedef void (*release_ts_t)(lt_t time);
+
 struct sched_plugin {
         struct list_head        list;
         /*      basic info              */
@@ -93,6 +98,8 @@ struct sched_plugin {
         task_block_t            task_block;
         task_exit_t             task_exit;
 
+        release_ts_t            release_ts;
+
 #ifdef CONFIG_LITMUS_LOCKING
         /*      locking protocols       */
         allocate_lock_t         allocate_lock;
diff --git a/include/litmus/sched_trace.h b/include/litmus/sched_trace.h
index 7ca34cb13881..96d7666aa22c 100644
--- a/include/litmus/sched_trace.h
+++ b/include/litmus/sched_trace.h
@@ -24,7 +24,8 @@ struct st_param_data {		/* regular params */
         u32     phase;
         u8      partition;
         u8      class;
-        u8      __unused[2];
+        u8      level;
+        u8      __unused[1];
 };
 
 struct st_release_data {        /* A job is was/is going to be released. */
@@ -71,8 +72,8 @@ struct st_resume_data {		/* A task resumes. */
 
 struct st_action_data {
         u64     when;
-        u8      action;
-        u8      __unused[7];
+        u32     action;
+        u8      __unused[4];
 };
 
 struct st_sys_release_data {
@@ -164,34 +165,156 @@ feather_callback void do_sched_trace_sys_release(unsigned long id,
 
 #endif
 
+#ifdef CONFIG_SCHED_LITMUS_TRACEPOINT
+
+#include <trace/events/litmus.h>
+
+#else
+
+#warning this is happeing
+
+/* Override trace macros to actually do nothing */
+#define trace_litmus_task_param(t)
+#define trace_litmus_task_release(t)
+#define trace_litmus_switch_to(t)
+#define trace_litmus_switch_away(prev)
+#define trace_litmus_task_completion(t, forced)
+#define trace_litmus_task_block(t, i)
+#define trace_litmus_task_resume(t, i)
+#define trace_litmus_sys_release(start)
+
+#define trace_litmus_resource_acquire(t, i);
+#define trace_litmus_resource_release(t, i);
+#define trace_litmus_priority_donate(t, d, i)
+
+#define trace_litmus_container_param(cid, name)
+#define trace_litmus_server_param(sid, cid, wcet, time)
+#define trace_litmus_server_switch_to(sid, job, tid, tjob)
+#define trace_litmus_server_switch_away(sid, job, tid, tjob)
+#define trace_litmus_server_release(sid, job, release, deadline)
+#define trace_litmus_server_completion(sid, job)
+
+#endif
+
 
 #define SCHED_TRACE_BASE_ID 500
 
 
-#define sched_trace_task_name(t) \
-        SCHED_TRACE(SCHED_TRACE_BASE_ID + 1, do_sched_trace_task_name, t)
-#define sched_trace_task_param(t) \
-        SCHED_TRACE(SCHED_TRACE_BASE_ID + 2, do_sched_trace_task_param, t)
-#define sched_trace_task_release(t) \
-        SCHED_TRACE(SCHED_TRACE_BASE_ID + 3, do_sched_trace_task_release, t)
-#define sched_trace_task_switch_to(t) \
-        SCHED_TRACE(SCHED_TRACE_BASE_ID + 4, do_sched_trace_task_switch_to, t)
-#define sched_trace_task_switch_away(t) \
-        SCHED_TRACE(SCHED_TRACE_BASE_ID + 5, do_sched_trace_task_switch_away, t)
-#define sched_trace_task_completion(t, forced) \
-        SCHED_TRACE2(SCHED_TRACE_BASE_ID + 6, do_sched_trace_task_completion, t, \
-                     (unsigned long) forced)
-#define sched_trace_task_block(t) \
-        SCHED_TRACE(SCHED_TRACE_BASE_ID + 7, do_sched_trace_task_block, t)
-#define sched_trace_task_resume(t) \
-        SCHED_TRACE(SCHED_TRACE_BASE_ID + 8, do_sched_trace_task_resume, t)
-#define sched_trace_action(t, action) \
-        SCHED_TRACE2(SCHED_TRACE_BASE_ID + 9, do_sched_trace_action, t, \
-                     (unsigned long) action);
-/* when is a pointer, it does not need an explicit cast to unsigned long */
-#define sched_trace_sys_release(when) \
-        SCHED_TRACE(SCHED_TRACE_BASE_ID + 10, do_sched_trace_sys_release, when)
+#define sched_trace_task_name(t)                                        \
+        SCHED_TRACE(SCHED_TRACE_BASE_ID + 1,                            \
+                        do_sched_trace_task_name, t)
+
+#define sched_trace_task_param(t)                                       \
+        do {                                                            \
+                SCHED_TRACE(SCHED_TRACE_BASE_ID + 2,                    \
+                                do_sched_trace_task_param, t);          \
+                trace_litmus_task_param(t);                             \
+        } while (0)
+
+#define sched_trace_task_release(t)                                     \
+        do {                                                            \
+                SCHED_TRACE(SCHED_TRACE_BASE_ID + 3,                    \
+                                do_sched_trace_task_release, t);        \
+                trace_litmus_task_release(t);                           \
+        } while (0)
+
+#define sched_trace_task_switch_to(t)                                   \
+        do {                                                            \
+                SCHED_TRACE(SCHED_TRACE_BASE_ID + 4,                    \
+                        do_sched_trace_task_switch_to, t);              \
+                trace_litmus_switch_to(t);                              \
+        } while (0)
+
+#define sched_trace_task_switch_away(t)                                 \
+        do {                                                            \
+                SCHED_TRACE(SCHED_TRACE_BASE_ID + 5,                    \
+                        do_sched_trace_task_switch_away, t);            \
+                trace_litmus_switch_away(t);                            \
+        } while (0)
+
+#define sched_trace_task_completion(t, forced)                          \
+        do {                                                            \
+                SCHED_TRACE2(SCHED_TRACE_BASE_ID + 6,                   \
+                                do_sched_trace_task_completion, t,      \
+                                (unsigned long) forced);                \
+                trace_litmus_task_completion(t, forced);                \
+        } while (0)
+
+#define sched_trace_task_block(t, i)                                    \
+        do {                                                            \
+                SCHED_TRACE(SCHED_TRACE_BASE_ID + 7,                    \
+                        do_sched_trace_task_block, t);                  \
+                trace_litmus_task_block(t, i);                          \
+        } while (0)
+
+#define sched_trace_task_resume(t, i)                                   \
+        do {                                                            \
+                SCHED_TRACE(SCHED_TRACE_BASE_ID + 8,                    \
+                                do_sched_trace_task_resume, t);         \
+                trace_litmus_task_resume(t, i);                         \
+        } while (0)
+
+#define sched_trace_action(t, action)                                   \
+        SCHED_TRACE2(SCHED_TRACE_BASE_ID + 9,                           \
+                do_sched_trace_action, t, (unsigned long) action);
 
+/* when is a pointer, it does not need an explicit cast to unsigned long */
+#define sched_trace_sys_release(when)                                   \
+        do {                                                            \
+                SCHED_TRACE(SCHED_TRACE_BASE_ID + 10,                   \
+                        do_sched_trace_sys_release, when);              \
+                trace_litmus_sys_release(when);                         \
+        } while (0)
+
+#define QT_START lt_t _qt_start = litmus_clock()
+#define QT_END \
+        sched_trace_log_message("%d P%d      [%s@%s:%d]: Took %llu\n\n", \
+                TRACE_ARGS, litmus_clock() - _qt_start)
+
+#define sched_trace_resource_acquire(t, i)                              \
+        do {                                                            \
+                trace_litmus_resource_acquire(t, i);                    \
+        } while (0)
+
+#define sched_trace_resource_release(t, i)                              \
+        do {                                                            \
+                trace_litmus_resource_release(t, i);                    \
+        } while (0)
+
+#define sched_trace_priority_donate(t, d, i)                            \
+        do {                                                            \
+                trace_litmus_priority_donate(t, d, i);                  \
+        } while (0)
+
+#define sched_trace_container_param(cid, name)                          \
+        do {                                                            \
+                trace_litmus_container_param(cid, name);                \
+        } while (0)
+
+#define sched_trace_server_param(sid, cid, wcet, period)                \
+        do {                                                            \
+                trace_litmus_server_param(sid, cid, wcet, period);      \
+        } while(0)
+
+#define sched_trace_server_switch_to(sid, job, tid, tjob)               \
+        do {                                                            \
+                trace_litmus_server_switch_to(sid, job, tid, tjob);     \
+        } while(0)
+
+#define sched_trace_server_switch_away(sid, job, tid, tjob)             \
+        do {                                                            \
+                trace_litmus_server_switch_away(sid, job, tid, tjob);   \
+        } while (0)
+
+#define sched_trace_server_release(sid, job, rel, dead)                 \
+        do {                                                            \
+                trace_litmus_server_release(sid, job, rel, dead);       \
+        } while (0)
+
+#define sched_trace_server_completion(sid, job)                         \
+        do {                                                            \
+                trace_litmus_server_completion(sid, job);               \
+        } while (0)
 
 #define sched_trace_quantum_boundary() /* NOT IMPLEMENTED */