PGM supportwip-mc2-new

9 files changed, 296 insertions, 6 deletions

diff --git a/include/litmus/pgm.h b/include/litmus/pgm.h
new file mode 100644
index 000000000000..5682a76b3acb
--- /dev/null
+++ b/include/litmus/pgm.h
@@ -0,0 +1,12 @@
+#ifndef _LITMUS_PGM_H_
+#define _LITMUS_PGM_H_
+
+#include <litmus/litmus.h>
+
+#define is_pgm_waiting(t) (tsk_rt(t)->ctrl_page && tsk_rt(t)->ctrl_page->pgm_waiting)
+#define is_pgm_sending(t) (tsk_rt(t)->ctrl_page && tsk_rt(t)->ctrl_page->pgm_sending)
+#define is_pgm_satisfied(t) (tsk_rt(t)->ctrl_page && tsk_rt(t)->ctrl_page->pgm_satisfied)
+
+int setup_pgm_release(struct task_struct* t);
+
+#endif
diff --git a/include/litmus/rt_param.h b/include/litmus/rt_param.h
index a3dde39753bd..fa0f5f4647bd 100644
--- a/include/litmus/rt_param.h
+++ b/include/litmus/rt_param.h
@@ -51,6 +51,14 @@ typedef enum {
         TASK_EARLY
 } release_policy_t;
 
+typedef enum {
+        PGM_NOT_A_NODE,
+        PGM_SRC,
+        PGM_SINK,
+        PGM_SRC_SINK,
+        PGM_INTERNAL
+} pgm_node_type_t;
+
 /* We use the common priority interpretation "lower index == higher priority",
  * which is commonly used in fixed-priority schedulability analysis papers.
  * So, a numerically lower priority value implies higher scheduling priority,
@@ -122,6 +130,8 @@ struct rt_task {
         task_class_t    cls;
         budget_policy_t  budget_policy;  /* ignored by pfair */
         release_policy_t release_policy;
+        pgm_node_type_t  pgm_type;
+        lt_t             pgm_expected_etoe;
 };
 
 union np_flag {
@@ -162,6 +172,11 @@ struct control_page {
         uint64_t irq_syscall_start; /* Snapshot of irq_count when the syscall
                                      * started. */
 
+        /* Flags from userspace signifying PGM wait states. */
+        volatile uint32_t       pgm_waiting;    /* waiting for tokens */
+        volatile uint32_t       pgm_sending;    /* sending tokens */
+        volatile uint32_t       pgm_satisfied;  /* done waiting/sending */
+
         /* to be extended */
 };
 
diff --git a/include/litmus/sched_trace.h b/include/litmus/sched_trace.h
index 82bde8241298..d3f78a812ef3 100644
--- a/include/litmus/sched_trace.h
+++ b/include/litmus/sched_trace.h
@@ -80,6 +80,19 @@ struct st_sys_release_data {
         u64     release;
 };
 
+struct st_pgm_param_data {
+        u32 node_type;
+        u16 graph_pid;
+        u16 unused;
+        u64 expected_graph_etoe;
+};
+
+struct st_pgm_release_data {
+        u64     release;        /* PGM-adjusted release time */
+        u64     deadline;       /* PGM-adjusted deadline */
+};
+
+
 #define DATA(x) struct st_ ## x ## _data x;
 
 typedef enum {
@@ -94,7 +107,9 @@ typedef enum {
         ST_BLOCK,
         ST_RESUME,
         ST_ACTION,
-        ST_SYS_RELEASE
+        ST_SYS_RELEASE,
+        ST_PGM_PARAM,
+        ST_PGM_RELEASE
 } st_event_record_type_t;
 
 struct st_event_record {
@@ -113,6 +128,8 @@ struct st_event_record {
                 DATA(resume);
                 DATA(action);
                 DATA(sys_release);
+                DATA(pgm_param);
+                DATA(pgm_release);
         } data;
 };
 
@@ -154,6 +171,10 @@ feather_callback void do_sched_trace_action(unsigned long id,
                                             unsigned long action);
 feather_callback void do_sched_trace_sys_release(unsigned long id,
                                                  lt_t* start);
+feather_callback void do_sched_trace_pgm_param(unsigned long id,
+                                                struct task_struct* task);
+feather_callback void do_sched_trace_pgm_release(unsigned long id,
+                                                struct task_struct* task);
 
 #endif
 
@@ -179,6 +200,8 @@ feather_callback void do_sched_trace_sys_release(unsigned long id,
 #define trace_litmus_task_block(t)
 #define trace_litmus_task_resume(t)
 #define trace_litmus_sys_release(start)
+#define trace_litmus_pgm_param(t)
+#define trace_litmus_pgm_release(t)
 
 #endif
 
@@ -252,6 +275,20 @@ feather_callback void do_sched_trace_sys_release(unsigned long id,
                 trace_litmus_sys_release(when);                         \
         } while (0)
 
+#define sched_trace_pgm_param(t)                                        \
+        do {                                                            \
+                SCHED_TRACE(SCHED_TRACE_BASE_ID + 11,                   \
+                                do_sched_trace_pgm_param, t);           \
+                trace_litmus_pgm_param(t);                                      \
+        } while (0)
+
+#define sched_trace_pgm_release(t)                                      \
+        do {                                                            \
+                SCHED_TRACE(SCHED_TRACE_BASE_ID + 12,                   \
+                                do_sched_trace_pgm_release, t);         \
+                trace_litmus_pgm_release(t);                            \
+        } while (0)
+
 #define sched_trace_quantum_boundary() /* NOT IMPLEMENTED */
 
 #endif /* __KERNEL__ */
diff --git a/include/trace/events/litmus.h b/include/trace/events/litmus.h
index 0fffcee02be0..02b4b54f718c 100644
--- a/include/trace/events/litmus.h
+++ b/include/trace/events/litmus.h
@@ -39,7 +39,7 @@ TRACE_EVENT(litmus_task_param,
                 __entry->partition = get_partition(t);
         ),
 
-        TP_printk("period(%d, %Lu).\nwcet(%d, %Lu).\n",
+        TP_printk("period(%u, %Lu).\nwcet(%d, %Lu).\n",
                 __entry->pid, __entry->period,
                 __entry->pid, __entry->wcet)
 );
@@ -225,6 +225,57 @@ TRACE_EVENT(litmus_sys_release,
         TP_printk("SynRelease(%Lu) at %Lu\n", __entry->rel, __entry->when)
 );
 
+/* Tracing PGM node parameters */
+TRACE_EVENT(litmus_pgm_param,
+
+        TP_PROTO(struct task_struct *t),
+
+        TP_ARGS(t),
+
+        TP_STRUCT__entry(
+                __field( pid_t, pid )
+                __field( pgm_node_type_t, node_type )
+                __field( pid_t, graph_pid )
+        ),
+
+        TP_fast_assign(
+                __entry->pid            = t ? t->pid  : 0;
+                __entry->node_type      = t ? t->rt_param.task_params.pgm_type : PGM_NOT_A_NODE;
+                __entry->graph_pid      = t ? t->tgid : 0;
+        ),
+
+        TP_printk("pgm node (%u, node type = %d) in graph (%u)\n",
+                __entry->pid, __entry->node_type, __entry->graph_pid)
+);
+
+/*
+ * Tracing PGM-adjusted job release
+ */
+TRACE_EVENT(litmus_pgm_release,
+
+        TP_PROTO(struct task_struct *t),
+
+        TP_ARGS(t),
+
+        TP_STRUCT__entry(
+                __field( pid_t,         pid     )
+                __field( unsigned int,  job     )
+                __field( lt_t,          release )
+                __field( lt_t,          deadline        )
+        ),
+
+        TP_fast_assign(
+                __entry->pid    = t ? t->pid : 0;
+                __entry->job    = t ? t->rt_param.job_params.job_no : 0;
+                __entry->release        = get_release(t);
+                __entry->deadline       = get_deadline(t);
+        ),
+
+        TP_printk("release(job(%u, %u)): %Lu\ndeadline(job(%u, %u)): %Lu\n",
+                        __entry->pid, __entry->job, __entry->release,
+                        __entry->pid, __entry->job, __entry->deadline)
+);
+
 #endif /* _SCHED_TASK_TRACEPOINT_H */
 
 /* Must stay outside the protection */
diff --git a/litmus/Makefile b/litmus/Makefile
index 3d0de72284f8..c19b6015b02e 100644
--- a/litmus/Makefile
+++ b/litmus/Makefile
@@ -40,3 +40,4 @@ obj-y += reservation.o polling_reservations.o
 
 obj-y += sched_pres.o
 obj-y += mc2_common.o sched_mc2.o
+obj-y += pgm.o
diff --git a/litmus/litmus.c b/litmus/litmus.c
index d72039067689..d2815f52876e 100644
--- a/litmus/litmus.c
+++ b/litmus/litmus.c
@@ -140,10 +140,16 @@ asmlinkage long sys_set_rt_task_param(pid_t pid, struct rt_task __user * param)
         if (tp.relative_deadline == 0)
                 tp.relative_deadline = tp.period;
 
-        if (tp.exec_cost <= 0)
+        if (tp.exec_cost <= 0) {
+                printk(KERN_INFO "litmus: real-time task %d rejected "
+                        "because declared job execution time <= 0.", pid);
                 goto out_unlock;
-        if (tp.period <= 0)
+        }
+        if (tp.period <= 0) {
+                printk(KERN_INFO "litmus: real-time task %d rejected "
+                                "because declared job period <= 0.", pid);
                 goto out_unlock;
+        }
         if (min(tp.relative_deadline, tp.period) < tp.exec_cost) /*density check*/
         {
                 printk(KERN_INFO "litmus: real-time task %d rejected "
@@ -169,6 +175,13 @@ asmlinkage long sys_set_rt_task_param(pid_t pid, struct rt_task __user * param)
                 goto out_unlock;
         }
 
+        if (tp.pgm_type < PGM_NOT_A_NODE || tp.pgm_type > PGM_INTERNAL) {
+                printk(KERN_INFO "litmus: real-time task %d rejected "
+                           "because of unknown PGM node type specified (%d)\n",
+                           pid, tp.pgm_type);
+                goto out_unlock;
+        }
+
         target->rt_param.task_params = tp;
 
         retval = 0;
@@ -549,6 +562,10 @@ long litmus_admit_task(struct task_struct* tsk)
         if (get_rt_relative_deadline(tsk) == 0 ||
             get_exec_cost(tsk) >
                         min(get_rt_relative_deadline(tsk), get_rt_period(tsk)) ) {
+                printk(KERN_INFO "litmus: invalid task parameters "
+                        "(e = %lu, p = %lu, d = %lu)\n",
+                        get_exec_cost(tsk), get_rt_period(tsk),
+                        get_rt_relative_deadline(tsk));
                 TRACE_TASK(tsk,
                         "litmus admit: invalid task parameters "
                         "(e = %lu, p = %lu, d = %lu)\n",
@@ -580,6 +597,7 @@ long litmus_admit_task(struct task_struct* tsk)
         if (!retval) {
                 sched_trace_task_name(tsk);
                 sched_trace_task_param(tsk);
+                sched_trace_pgm_param(tsk);
                 atomic_inc(&rt_task_count);
         }
 
diff --git a/litmus/pgm.c b/litmus/pgm.c
new file mode 100644
index 000000000000..db3378ff803d
--- /dev/null
+++ b/litmus/pgm.c
@@ -0,0 +1,61 @@
+/* litmus/pgm.c - common pgm control code
+ */
+
+#include <linux/sched.h>
+#include <litmus/litmus.h>
+#include <litmus/pgm.h>
+#include <litmus/sched_trace.h>
+
+/* Only readjust release/deadline if difference is over a given threshold.
+   It's a weak method for accounting overheads. Ideally, we'd know the last
+   time t was woken up by its last predecessor, rather than having to look
+   at 'now'. Adjustment threshold currently set to 200us. */
+#define ADJUSTMENT_THRESH_NS (200*1000LL)
+
+int setup_pgm_release(struct task_struct* t)
+{
+        int shifted_release = 0;
+
+        /* approximate time last predecessor gave us tokens */
+        lt_t now = litmus_clock();
+
+        TRACE_TASK(t, "is starting a new PGM job: waiting:%d\n",
+                tsk_rt(t)->ctrl_page->pgm_waiting);
+
+        BUG_ON(!tsk_rt(t)->ctrl_page->pgm_waiting);
+
+        /* Adjust release time if we got the last tokens after release of this job.
+           This is possible since PGM jobs are early-released. Don't shift our
+           deadline if we got the tokens earlier than expected. */
+        if (now > tsk_rt(t)->job_params.release) {
+                long long diff_ns = now - tsk_rt(t)->job_params.release;
+                if (diff_ns > ADJUSTMENT_THRESH_NS) {
+                        lt_t adj_deadline = now + get_rt_relative_deadline(t);
+
+                        TRACE_TASK(t, "adjusting PGM release time from (r = %llu, d = %llu) "
+                                "to (r = %llu, d = %llu)\n",
+                                tsk_rt(t)->job_params.release, tsk_rt(t)->job_params.deadline,
+                                now, adj_deadline);
+
+                        tsk_rt(t)->job_params.release = now;
+                        tsk_rt(t)->job_params.deadline = adj_deadline;
+                        shifted_release = 1;
+                }
+                else {
+                        TRACE_TASK(t, "adjustment falls below threshold. %lld < %lld\n",
+                                diff_ns, ADJUSTMENT_THRESH_NS);
+                }
+        }
+        else {
+                TRACE_TASK(t, "got tokens early--no need to adjust release. "
+                        "cur time = %llu, release time = %llu\n",
+                        now, tsk_rt(t)->job_params.release);
+        }
+
+        /* possible that there can be multiple instances of pgm_release logged.
+           analysis tools should filter out all but the last pgm_release for
+           a given job release */
+        sched_trace_pgm_release(t);
+
+        return shifted_release;
+}
diff --git a/litmus/sched_mc2.c b/litmus/sched_mc2.c
index a310723dce24..9ed92d355d7a 100644
--- a/litmus/sched_mc2.c
+++ b/litmus/sched_mc2.c
@@ -25,6 +25,7 @@
 #include <litmus/mc2_common.h>
 #include <litmus/reservation.h>
 #include <litmus/polling_reservations.h>
+#include <litmus/pgm.h>
 
 #define BUDGET_ENFORCEMENT_AT_C 0
 
@@ -614,14 +615,82 @@ static struct task_struct* mc2_schedule(struct task_struct * prev)
         /* next == NULL means "schedule background work". */
         lt_t now;
         struct mc2_cpu_state *state = local_cpu_state();
+        int sleep, preempt, np, exists, blocks;
 
         pre_schedule(prev, state->cpu);
         
         raw_spin_lock(&_global_env.lock);
         raw_spin_lock(&state->lock);
         
-        //BUG_ON(state->scheduled && state->scheduled != prev);
-        //BUG_ON(state->scheduled && !is_realtime(prev));
+        /* sanity check */
+        BUG_ON(state->scheduled && state->scheduled != prev);
+        BUG_ON(state->scheduled && !is_realtime(prev));
+        BUG_ON(is_realtime(prev) && !state->scheduled);
+
+        /* (0) Determine state */
+        exists          = state->scheduled != NULL;
+        blocks          = exists && !is_running(state->scheduled);
+        sleep           = exists && is_completed(state->scheduled);
+        np                      = exists && is_np(state->scheduled);    
+        preempt         = _lowest_prio_cpu.cpu_entries[state->cpu].will_schedule;
+    
+    if (exists) {
+        if (is_pgm_sending(state->scheduled)) {
+            if (!is_pgm_satisfied(state->scheduled)) {
+                if (!is_priority_boosted(state->scheduled)) {
+                    TRACE_TASK(state->scheduled, "is sending PGM tokens and needs boosting.\n");
+                    BUG_ON(is_pgm_satisfied(state->scheduled));
+
+                    /* We are either sending tokens or waiting for tokes.
+                       If waiting: Boost priority so we'll be scheduled
+                        immediately when needed tokens arrive.
+                       If sending: Boost priority so no one (specifically, our
+                        consumers) will preempt us while signalling the token
+                        transmission.
+                    */
+                    tsk_rt(state->scheduled)->priority_boosted = 1;
+                    tsk_rt(state->scheduled)->boost_start_time = litmus_clock();
+
+                    if (likely(!blocks)) {
+                                                task_departs(state->scheduled, is_completed(prev));
+                        task_arrives(state, state->scheduled);
+                        /* we may regain the processor */
+                        if (preempt) {
+                            //preempt = resched_cpu[state->cpu];
+                                                        litmus_reschedule_local();
+                            if (!preempt) {
+                                TRACE_TASK(state->scheduled, "blocked preemption by lazy boosting.\n");
+                            }
+                        }
+                    }
+                }
+            }
+            else { /* sending is satisfied */
+                tsk_rt(state->scheduled)->ctrl_page->pgm_sending = 0;
+                tsk_rt(state->scheduled)->ctrl_page->pgm_satisfied = 0;
+
+                if (is_priority_boosted(state->scheduled)) {
+                    TRACE_TASK(state->scheduled,
+                            "is done sending PGM tokens must relinquish boosting.\n");
+                    /* clear boosting */
+                    tsk_rt(state->scheduled)->priority_boosted = 0;
+                    if(likely(!blocks)) {
+                        /* recheck priority */
+                                                task_departs(state->scheduled, is_completed(prev));
+                        task_arrives(state, state->scheduled);
+                        /* we may lose the processor */
+                        if (!preempt) {
+                            //preempt = resched_cpu[state->cpu];
+                                                        litmus_reschedule_local();
+                            if (preempt) {
+                                TRACE_TASK(state->scheduled, "preempted by lazy unboosting.\n");
+                            }
+                        }
+                    }
+                }
+            }
+        }
+    }
 
         /* update time */
         state->sup_env.will_schedule = true;
@@ -701,6 +770,9 @@ static void resume_legacy_task_model_updates(struct task_struct *tsk)
                         sched_trace_task_release(tsk);
                 }
         }
+        //if (is_pgm_waiting(tsk)) {
+        //      setup_pgm_release(tsk);
+        //}
 }
 
 /* mc2_task_resume - Called when the state of tsk changes back to 
diff --git a/litmus/sched_task_trace.c b/litmus/sched_task_trace.c
index 3a6756deb32f..784b18ecfd8b 100644
--- a/litmus/sched_task_trace.c
+++ b/litmus/sched_task_trace.c
@@ -238,3 +238,26 @@ feather_callback void do_sched_trace_action(unsigned long id,
                 put_record(rec);
         }
 }
+
+feather_callback void do_sched_trace_pgm_param(unsigned long id, unsigned long _task)
+{
+        struct task_struct *t = (struct task_struct*) _task;
+        struct st_event_record* rec = get_record(ST_PGM_PARAM, t);
+        if (rec) {
+                rec->data.pgm_param.node_type = tsk_rt(t)->task_params.pgm_type;
+                rec->data.pgm_param.graph_pid = t->tgid;
+                rec->data.pgm_param.expected_graph_etoe = tsk_rt(t)->task_params.pgm_expected_etoe;
+                put_record(rec);
+        }
+}
+
+feather_callback void do_sched_trace_pgm_release(unsigned long id, unsigned long _task)
+{
+        struct task_struct *t = (struct task_struct*) _task;
+        struct st_event_record* rec = get_record(ST_PGM_RELEASE, t);
+        if (rec) {
+                rec->data.pgm_release.release  = get_release(t);
+                rec->data.pgm_release.deadline = get_deadline(t);
+                put_record(rec);
+        }
+}