3 files changed, 799 insertions, 9 deletions

diff --git a/include/litmus/rt_param.h b/include/litmus/rt_param.h
index a7dd67a81a..7bb568432e 100644
--- a/include/litmus/rt_param.h
+++ b/include/litmus/rt_param.h
@@ -64,6 +64,8 @@ struct rt_job {
 };
 
 
+struct pfair_param;
+
 /*      RT task parameters for scheduling extensions
  *      These parameters are inherited during clone and therefore must
  *      be explicitly set up before the task set is launched.
@@ -108,15 +110,12 @@ struct rt_param {
          * is currently scheduled. It is the responsibility of the
          * plugin to avoid race conditions.
          *
-         * Used by GSN-EDF.
+         * This used by GSN-EDF and PFAIR.
          */
         volatile int            scheduled_on;
 
-        /* Is the stack of the task currently in use? Currently, this
-         * is the responsibility of the plugin to update this field.
-         * Maybe become part of the LITMUS core some day.
-         * 
-         * Used by GSN-EDF.
+        /* Is the stack of the task currently in use? This is updated by
+         * the LITMUS core.
          *
          * Be careful to avoid deadlocks!
          */
@@ -130,6 +129,9 @@ struct rt_param {
          */
         volatile int            linked_on;
 
+        /* PFAIR/PD^2 state. Allocated on demand. */
+        struct pfair_param*     pfair;
+
         /* Fields saved before BE->RT transition.
          */
         int old_policy;
diff --git a/litmus/Makefile b/litmus/Makefile
index bfe393eb56..545203876a 100644
--- a/litmus/Makefile
+++ b/litmus/Makefile
@@ -3,9 +3,12 @@
 #
 
 obj-y     = sched_plugin.o litmus.o sched_trace.o \
-            edf_common.o jobs.o\
-            sched_gsn_edf.o sched_psn_edf.o sched_cedf.o \
+            edf_common.o jobs.o \
             rt_domain.o fdso.o sync.o \
-            fmlp.o srp.o norqlock.o
+            fmlp.o srp.o norqlock.o \
+            sched_gsn_edf.o \
+            sched_psn_edf.o \
+            sched_cedf.o \
+            sched_pfair.o
 
 obj-$(CONFIG_FEATHER_TRACE) += trace.o ft_event.o
diff --git a/litmus/sched_pfair.c b/litmus/sched_pfair.c
new file mode 100755
index 0000000000..6f95688508
--- /dev/null
+++ b/litmus/sched_pfair.c
@@ -0,0 +1,785 @@
+/*
+ * kernel/sched_pfair.c
+ *
+ * Implementation of the (global) Pfair scheduling algorithm.
+ *
+ */
+
+#include <asm/div64.h>
+#include <linux/delay.h>
+#include <linux/module.h>
+#include <linux/spinlock.h>
+#include <linux/percpu.h>
+#include <linux/sched.h>
+#include <linux/list.h>
+
+#include <litmus/litmus.h>
+#include <litmus/jobs.h>
+#include <litmus/rt_domain.h>
+#include <litmus/sched_plugin.h>
+#include <litmus/sched_trace.h>
+
+#include <litmus/heap.h>
+
+/* Tick period is used to convert ns-specified execution
+ * costs and periods into tick-based equivalents.
+ */
+extern ktime_t tick_period;
+
+/* make the unit explicit */
+typedef unsigned long quanta_t;
+
+struct subtask {
+        /* measured in quanta relative to job release */
+        quanta_t release;
+        quanta_t deadline;
+        quanta_t overlap; /* called "b bit" by PD^2 */
+        quanta_t group_deadline;
+};
+
+struct pfair_param   {
+        quanta_t        quanta;       /* number of subtasks */
+        quanta_t        cur;          /* index of current subtask */
+
+        quanta_t        release;      /* in quanta */
+        quanta_t        period;       /* in quanta */
+
+        quanta_t        last_quantum; /* when scheduled last */
+        int             last_cpu;     /* where scheduled last */
+
+        unsigned int    present;    /* Can the task be scheduled? */
+
+        struct subtask subtasks[0];   /* allocate together with pfair_param */
+};
+
+#define tsk_pfair(tsk) ((tsk)->rt_param.pfair)
+
+struct pfair_state {
+        int cpu;
+        volatile quanta_t cur_tick;    /* updated by the CPU that is advancing
+                                        * the time */
+        volatile quanta_t local_tick;  /* What tick is the local CPU currently
+                                        * executing? Updated only by the local
+                                        * CPU. In QEMU, this may lag behind the
+                                        * current tick. In a real system, with
+                                        * proper timers and aligned quanta,
+                                        * that should only be the
+                                        * case for a very short time after the
+                                        * time advanced. With staggered quanta,
+                                        * it will lag for the duration of the
+                                        * offset.
+                                        */
+
+        struct task_struct* linked;    /* the task that should be executing */
+        struct task_struct* local;     /* the local copy of linked          */
+        struct task_struct* scheduled; /* what is actually scheduled        */
+
+        unsigned long missed_quanta;
+};
+
+/* Currently, we limit the maximum period of any task to 1000 quanta.
+ * The reason is that it makes the implementation easier since we do not
+ * need to reallocate the release wheel on task arrivals.
+ * In the future
+ */
+#define PFAIR_MAX_PERIOD 1000
+
+/* This is the release queue wheel. It is indexed by pfair_time %
+ * PFAIR_MAX_PERIOD.  Each heap is ordered by PFAIR priority, so that it can be
+ * merged with the ready queue.
+ */
+static struct heap release_queue[PFAIR_MAX_PERIOD];
+
+DEFINE_PER_CPU(struct pfair_state, pfair_state);
+struct pfair_state*  pstate[NR_CPUS]; /* short cut */
+
+#define NO_CPU 0xffffffff
+
+static quanta_t pfair_time = 0; /* the "official" PFAIR clock */
+static quanta_t merge_time = 0; /* Updated after the release queue has been
+                                 * merged. Used by drop_all_references().
+                                 */
+
+static rt_domain_t pfair;
+
+/* The pfair_lock is used to serialize all scheduling events.
+ */
+#define pfair_lock pfair.ready_lock
+
+/* Enable for lots of trace info.
+ * #define PFAIR_DEBUG
+ */
+
+#ifdef PFAIR_DEBUG
+#define PTRACE_TASK(t, f, args...)  TRACE_TASK(t, f, # args)
+#define PTRACE(f, args...) TRACE(f, # args)
+#else
+#define PTRACE_TASK(t, f, args...)
+#define PTRACE(f, args...)
+#endif
+
+/* gcc will inline all of these accessor functions... */
+static struct subtask* cur_subtask(struct task_struct* t)
+{
+        return tsk_pfair(t)->subtasks + tsk_pfair(t)->cur;
+}
+
+static quanta_t cur_deadline(struct task_struct* t)
+{
+        return cur_subtask(t)->deadline +  tsk_pfair(t)->release;
+}
+
+static quanta_t cur_release(struct task_struct* t)
+{
+#ifdef EARLY_RELEASE
+        /* only the release of the first subtask counts when we early
+         * release */
+        return tsk_pfair(t)->release;
+#else
+        return cur_subtask(t)->release +  tsk_pfair(t)->release;
+#endif
+}
+
+static quanta_t cur_sub_release(struct task_struct* t)
+{
+        return cur_subtask(t)->release +  tsk_pfair(t)->release;
+}
+
+static quanta_t cur_overlap(struct task_struct* t)
+{
+        return cur_subtask(t)->overlap;
+}
+
+static quanta_t cur_group_deadline(struct task_struct* t)
+{
+        quanta_t gdl = cur_subtask(t)->group_deadline;
+        if (gdl)
+                return gdl + tsk_pfair(t)->release;
+        else
+                return gdl;
+}
+
+e