Add PD^2 scheduler plugin2015.1

3 files changed, 1240 insertions, 0 deletions

diff --git a/litmus/Kconfig b/litmus/Kconfig
index 38d9e433b345..babb43deffb5 100644
--- a/litmus/Kconfig
+++ b/litmus/Kconfig
@@ -12,6 +12,19 @@ config PLUGIN_CEDF
           On smaller platforms (e.g., ARM PB11MPCore), using C-EDF
           makes little sense since there aren't any shared caches.
 
+config PLUGIN_PFAIR
+        bool "PFAIR"
+        default y
+        help
+          Include the PFAIR plugin (i.e., the PD^2 scheduler) in the kernel.
+          The PFAIR plugin requires high resolution timers (for staggered
+          quanta) and also requires HZ_PERIODIC (i.e., periodic timer ticks
+          even if a processor is idle, as quanta could be missed otherwise).
+          Further, the PFAIR plugin uses the system tick and thus requires
+          HZ=1000 to achive reasonable granularity.
+
+          If unsure, say Yes.
+
 config RELEASE_MASTER
         bool "Release-master Support"
         depends on ARCH_HAS_SEND_PULL_TIMERS && SMP
diff --git a/litmus/Makefile b/litmus/Makefile
index 7d637197d736..7970cd55e7fd 100644
--- a/litmus/Makefile
+++ b/litmus/Makefile
@@ -24,6 +24,7 @@ obj-y     = sched_plugin.o litmus.o \
             sched_pfp.o
 
 obj-$(CONFIG_PLUGIN_CEDF) += sched_cedf.o
+obj-$(CONFIG_PLUGIN_PFAIR) += sched_pfair.o
 
 obj-$(CONFIG_FEATHER_TRACE) += ft_event.o ftdev.o
 obj-$(CONFIG_SCHED_TASK_TRACE) += sched_task_trace.o
diff --git a/litmus/sched_pfair.c b/litmus/sched_pfair.c
new file mode 100644
index 000000000000..3f82378f5ca8
--- /dev/null
+++ b/litmus/sched_pfair.c
@@ -0,0 +1,1226 @@
+/*
+ * kernel/sched_pfair.c
+ *
+ * Implementation of the PD^2 pfair scheduling algorithm. This
+ * implementation realizes "early releasing," i.e., it is work-conserving.
+ *
+ */
+
+#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 <linux/slab.h>
+
+#include <litmus/litmus.h>
+#include <litmus/jobs.h>
+#include <litmus/preempt.h>
+#include <litmus/rt_domain.h>
+#include <litmus/sched_plugin.h>
+#include <litmus/sched_trace.h>
+#include <litmus/trace.h>
+
+#include <litmus/bheap.h>
+
+/* to configure the cluster size */
+#include <litmus/litmus_proc.h>
+
+#include <litmus/clustered.h>
+
+static enum cache_level pfair_cluster_level = GLOBAL_CLUSTER;
+
+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    needs_requeue:1;
+
+        struct pfair_cluster* cluster; /* where this task is scheduled */
+
+        struct subtask subtasks[0];   /* allocate together with pfair_param */
+};
+
+#define tsk_pfair(tsk) ((tsk)->rt_param.pfair)
+
+struct pfair_state {
+        struct cluster_cpu topology;
+
+        struct hrtimer quantum_timer;
+
+        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        */
+
+        struct list_head    out_of_budget; /* list of tasks that exhausted their allocation */
+
+        lt_t offset;                    /* stagger offset */
+        unsigned int missed_updates;
+        unsigned int missed_quanta;
+};
+
+struct pfair_cluster {
+        struct scheduling_cluster topology;
+
+        /* The "global" time in this cluster. */
+        quanta_t pfair_time; /* the "official" PFAIR clock */
+
+        /* The ready queue for this cluster. */
+        rt_domain_t pfair;
+
+        /* The set of jobs that should have their release enacted at the next
+         * quantum boundary.
+         */
+        struct bheap release_queue;
+        raw_spinlock_t release_lock;
+};
+
+static inline struct pfair_cluster* cpu_cluster(struct pfair_state* state)
+{
+        return container_of(state->topology.cluster, struct pfair_cluster, topology);
+}
+
+static inline int cpu_id(struct pfair_state* state)
+{
+        return state->topology.id;
+}
+
+static inline struct pfair_state* from_cluster_list(struct list_head* pos)
+{
+        return list_entry(pos, struct pfair_state, topology.cluster_list);
+}
+
+static inline struct pfair_cluster* from_domain(rt_domain_t* rt)
+{
+        return container_of(rt, struct pfair_cluster, pfair);
+}
+
+static inline raw_spinlock_t* cluster_lock(struct pfair_cluster* cluster)
+{
+        /* The ready_lock is used to serialize all scheduling events. */
+        return &cluster->pfair.ready_lock;
+}
+
+static inline raw_spinlock_t* cpu_lock(struct pfair_state* state)
+{
+        return cluster_lock(cpu_cluster(state));
+}
+
+DEFINE_PER_CPU(struct pfair_state, pfair_state);
+struct pfair_state* *pstate; /* short cut */
+
+static struct pfair_cluster* pfair_clusters;
+static int num_pfair_clusters;
+
+/* 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