Merge branch 'mpi-master' into wip-k-fmlpwip-k-fmlp

Conflicts:
	litmus/sched_cedf.c

7 files changed, 174 insertions, 22 deletions

diff --git a/include/litmus/affinity.h b/include/litmus/affinity.h
new file mode 100644
index 000000000000..ca2e442eb547
--- /dev/null
+++ b/include/litmus/affinity.h
@@ -0,0 +1,80 @@
+#ifndef __LITMUS_AFFINITY_H
+#define __LITMUS_AFFINITY_H
+
+#include <linux/cpumask.h>
+
+/*
+  L1 (instr) = depth 0
+  L1 (data)  = depth 1
+  L2 = depth 2
+  L3 = depth 3
+ */
+#define NUM_CACHE_LEVELS 4
+
+struct neighborhood
+{
+        unsigned int size[NUM_CACHE_LEVELS];
+        cpumask_var_t neighbors[NUM_CACHE_LEVELS];
+};
+
+/* topology info is stored redundently in a big array for fast lookups */
+extern struct neighborhood neigh_info[NR_CPUS];
+
+void init_topology(void); /* called by Litmus module's _init_litmus() */
+
+/* Works like:
+void get_nearest_available_cpu(
+        cpu_entry_t **nearest,
+        cpu_entry_t *start,
+        cpu_entry_t *entries,
+        int release_master)
+
+Set release_master = NO_CPU for no Release Master.
+
+We use a macro here to exploit the fact that C-EDF and G-EDF
+have similar structures for their cpu_entry_t structs, even though
+they do not share a common base-struct.  The macro allows us to
+avoid code duplication.
+
+TODO: Factor out the job-to-processor linking from C/G-EDF into
+a reusable "processor mapping".  (See B.B.'s RTSS'09 paper &
+dissertation.)
+ */
+#define get_nearest_available_cpu(nearest, start, entries, release_master) \
+{ \
+        (nearest) = NULL; \
+        if (!(start)->linked) { \
+                (nearest) = (start); \
+        } else { \
+                int __level; \
+                int __cpu; \
+                int __release_master = ((release_master) == NO_CPU) ? -1 : (release_master); \
+                struct neighborhood *__neighbors = &neigh_info[(start)->cpu]; \
+                \
+                for (__level = 0; (__level < NUM_CACHE_LEVELS) && !(nearest); ++__level) { \
+                        if (__neighbors->size[__level] > 1) { \
+                                for_each_cpu(__cpu, __neighbors->neighbors[__level]) { \
+                                        if (__cpu != __release_master) { \
+                                                cpu_entry_t *__entry = &per_cpu((entries), __cpu); \
+                                                if (!__entry->linked) { \
+                                                        (nearest) = __entry; \
+                                                        break; \
+                                                } \
+                                        } \
+                                } \
+                        } else if (__neighbors->size[__level] == 0) { \
+                                break; \
+                        } \
+                } \
+        } \
+        \
+        if ((nearest)) { \
+                TRACE("P%d is closest available CPU to P%d\n", \
+                                (nearest)->cpu, (start)->cpu); \
+        } else { \
+                TRACE("Could not find an available CPU close to P%d\n", \
+                                (start)->cpu); \
+        } \
+}
+
+#endif
diff --git a/include/litmus/ftdev.h b/include/litmus/ftdev.h
index 348387e9adf9..0b959874dd70 100644
--- a/include/litmus/ftdev.h
+++ b/include/litmus/ftdev.h
@@ -16,7 +16,8 @@ typedef int  (*ftdev_can_open_t)(struct ftdev* dev, unsigned int buf_no);
 /* return 0 on success, otherwise -$REASON */
 typedef int  (*ftdev_alloc_t)(struct ftdev* dev, unsigned int buf_no);
 typedef void (*ftdev_free_t)(struct ftdev* dev, unsigned int buf_no);
-
+/* Let devices handle writes from userspace. No synchronization provided. */
+typedef ssize_t (*ftdev_write_t)(struct ft_buffer* buf, size_t len, const char __user *from);
 
 struct ftdev_event;
 
@@ -27,6 +28,7 @@ struct ftdev_minor {
         /* FIXME: filter for authorized events */
         struct ftdev_event*     events;
         struct device*          device;
+        struct ftdev*           ftdev;
 };
 
 struct ftdev {
@@ -39,6 +41,7 @@ struct ftdev {
         ftdev_alloc_t           alloc;
         ftdev_free_t            free;
         ftdev_can_open_t        can_open;
+        ftdev_write_t           write;
 };
 
 struct ft_buffer* alloc_ft_buffer(unsigned int count, size_t size);
diff --git a/include/litmus/litmus.h b/include/litmus/litmus.h
index 3df242bf272f..95d0805519de 100644
--- a/include/litmus/litmus.h
+++ b/include/litmus/litmus.h
@@ -138,7 +138,7 @@ static inline int is_kernel_np(struct task_struct *t)
 
 static inline int is_user_np(struct task_struct *t)
 {
-        return tsk_rt(t)->ctrl_page ? tsk_rt(t)->ctrl_page->np_flag : 0;
+        return tsk_rt(t)->ctrl_page ? tsk_rt(t)->ctrl_page->sched.np.flag : 0;
 }
 
 static inline void request_exit_np(struct task_struct *t)
@@ -148,17 +148,11 @@ static inline void request_exit_np(struct task_struct *t)
                  * into the kernel at the end of a critical section. */
                 if (likely(tsk_rt(t)->ctrl_page)) {
                         TRACE_TASK(t, "setting delayed_preemption flag\n");
-                        tsk_rt(t)->ctrl_page->delayed_preemption = 1;
+                        tsk_rt(t)->ctrl_page->sched.np.preempt = 1;
                 }
         }
 }
 
-static inline void clear_exit_np(struct task_struct *t)
-{
-        if (likely(tsk_rt(t)->ctrl_page))
-                tsk_rt(t)->ctrl_page->delayed_preemption = 0;
-}
-
 static inline void make_np(struct task_struct *t)
 {
         tsk_rt(t)->kernel_np++;
@@ -172,6 +166,34 @@ static inline int take_np(struct task_struct *t)
         return --tsk_rt(t)->kernel_np;
 }
 
+/* returns 0 if remote CPU needs an IPI to preempt, 1 if no IPI is required */
+static inline int request_exit_np_atomic(struct task_struct *t)
+{
+        union np_flag old, new;
+
+        if (tsk_rt(t)->ctrl_page) {
+                old.raw = tsk_rt(t)->ctrl_page->sched.raw;
+                if (old.np.flag == 0) {
+                        /* no longer non-preemptive */
+                        return 0;
+                } else if (old.np.preempt) {
+                        /* already set, nothing for us to do */
+                        return 1;
+                } else {
+                        /* non preemptive and flag not set */
+                        new.raw = old.raw;
+                        new.np.preempt = 1;
+                        /* if we get old back, then we atomically set the flag */
+                        return cmpxchg(&tsk_rt(t)->ctrl_page->sched.raw, old.raw, new.raw) == old.raw;
+                        /* If we raced with a concurrent change, then so be
+                         * it. Deliver it by IPI.  We don't want an unbounded
+                         * retry loop here since tasks might exploit that to
+                         * keep the kernel busy indefinitely. */
+                }
+        } else
+                return 0;
+}
+
 #else
 
 static inline int is_kernel_np(struct task_struct* t)
@@ -190,12 +212,19 @@ static inline void request_exit_np(struct task_struct *t)
         BUG();
 }
 
-static inline void clear_exit_np(struct task_struct* t)
+static inline int request_exit_np_atomic(struct task_struct *t)
 {
+        return 0;
 }
 
 #endif
 
+static inline void clear_exit_np(struct task_struct *t)
+{
+        if (likely(tsk_rt(t)->ctrl_page))
+                tsk_rt(t)->ctrl_page->sched.np.preempt = 0;
+}
+
 static inline int is_np(struct task_struct *t)
 {
 #ifdef CONFIG_SCHED_DEBUG_TRACE
diff --git a/include/litmus/preempt.h b/include/litmus/preempt.h
index 260c6fe17986..380b886d78ff 100644
--- a/include/litmus/preempt.h
+++ b/include/litmus/preempt.h
@@ -10,7 +10,7 @@
 
 extern DEFINE_PER_CPU_SHARED_ALIGNED(atomic_t, resched_state);
 
-#ifdef CONFIG_DEBUG_KERNEL
+#ifdef CONFIG_PREEMPT_STATE_TRACE
 const char* sched_state_name(int s);
 #define TRACE_STATE(fmt, args...) TRACE("SCHED_STATE " fmt, args)
 #else
diff --git a/include/litmus/rt_param.h b/include/litmus/rt_param.h
index 5de422c742f6..d6d799174160 100644
--- a/include/litmus/rt_param.h
+++ b/include/litmus/rt_param.h
@@ -30,7 +30,7 @@ typedef enum {
 typedef enum {
         NO_ENFORCEMENT,      /* job may overrun unhindered */
         QUANTUM_ENFORCEMENT, /* budgets are only checked on quantum boundaries */
-        PRECISE_ENFORCEMENT  /* NOT IMPLEMENTED - enforced with hrtimers */
+        PRECISE_ENFORCEMENT  /* budgets are enforced with hrtimers */
 } budget_policy_t;
 
 struct rt_task {
@@ -42,6 +42,16 @@ struct rt_task {
         budget_policy_t budget_policy; /* ignored by pfair */
 };
 
+union np_flag {
+        uint32_t raw;
+        struct {
+                /* Is the task currently in a non-preemptive section? */
+                uint32_t flag:31;
+                /* Should the task call into the scheduler? */
+                uint32_t preempt:1;
+        } np;
+};
+
 /* The definition of the data that is shared between the kernel and real-time
  * tasks via a shared page (see litmus/ctrldev.c).
  *
@@ -57,11 +67,7 @@ struct rt_task {
  * determining preemption/migration overheads).
  */
 struct control_page {
-        /* Is the task currently in a non-preemptive section? */
-        int np_flag;
-        /* Should the task call into the kernel when it leaves
-         * its non-preemptive section? */
-        int delayed_preemption;
+        volatile union np_flag sched;
 
         /* to be extended */
 };
diff --git a/include/litmus/trace.h b/include/litmus/trace.h
index 05f487263f28..e809376d6487 100644
--- a/include/litmus/trace.h
+++ b/include/litmus/trace.h
@@ -20,7 +20,9 @@ struct timestamp {
         uint32_t                seq_no;
         uint8_t                 cpu;
         uint8_t                 event;
-        uint8_t                 task_type;
+        uint8_t                 task_type:2;
+        uint8_t                 irq_flag:1;
+        uint8_t                 irq_count:5;
 };
 
 /* tracing callbacks */
@@ -28,7 +30,7 @@ feather_callback void save_timestamp(unsigned long event);
 feather_callback void save_timestamp_def(unsigned long event, unsigned long type);
 feather_callback void save_timestamp_task(unsigned long event, unsigned long t_ptr);
 feather_callback void save_timestamp_cpu(unsigned long event, unsigned long cpu);
-
+feather_callback void save_task_latency(unsigned long event, unsigned long when_ptr);
 
 #define TIMESTAMP(id) ft_event0(id, save_timestamp)
 
@@ -40,6 +42,9 @@ feather_callback void save_timestamp_cpu(unsigned long event, unsigned long cpu)
 #define CTIMESTAMP(id, cpu) \
         ft_event1(id, save_timestamp_cpu, (unsigned long) cpu)
 
+#define LTIMESTAMP(id, task) \
+        ft_event1(id, save_task_latency, (unsigned long) task)
+
 #else /* !CONFIG_SCHED_OVERHEAD_TRACE */
 
 #define TIMESTAMP(id)        /* no tracing */
@@ -50,6 +55,8 @@ feather_callback void save_timestamp_cpu(unsigned long event, unsigned long cpu)
 
 #define CTIMESTAMP(id, cpu)  /* no tracing */
 
+#define LTIMESTAMP(id, when_ptr) /* no tracing */
+
 #endif
 
 
@@ -61,6 +68,8 @@ feather_callback void save_timestamp_cpu(unsigned long event, unsigned long cpu)
  * always the next number after the start time event id.
  */
 
+
+
 #define TS_SCHED_START                  DTIMESTAMP(100, TSK_UNKNOWN) /* we only
                                                                       * care
                                                                       * about
@@ -92,12 +101,16 @@ feather_callback void save_timestamp_cpu(unsigned long event, unsigned long cpu)
 #define TS_EXIT_NP_END                  TIMESTAMP(151)
 
 #define TS_LOCK_START                   TIMESTAMP(170)
-#define TS_LOCK_END                     TIMESTAMP(171)
-#define TS_UNLOCK_START                 TIMESTAMP(172)
-#define TS_UNLOCK_END                   TIMESTAMP(173)
+#define TS_LOCK_SUSPEND                 TIMESTAMP(171)
+#define TS_LOCK_RESUME                  TIMESTAMP(172)
+#define TS_LOCK_END                     TIMESTAMP(173)
+
+#define TS_UNLOCK_START                 TIMESTAMP(180)
+#define TS_UNLOCK_END                   TIMESTAMP(181)
 
 #define TS_SEND_RESCHED_START(c)        CTIMESTAMP(190, c)
 #define TS_SEND_RESCHED_END             DTIMESTAMP(191, TSK_UNKNOWN)
 
+#define TS_RELEASE_LATENCY(when)        LTIMESTAMP(208, &(when))
 
 #endif /* !_SYS_TRACE_H_ */
diff --git a/include/litmus/trace_irq.h b/include/litmus/trace_irq.h
new file mode 100644
index 000000000000..f18b127a089d
--- /dev/null
+++ b/include/litmus/trace_irq.h
@@ -0,0 +1,21 @@
+#ifndef _LITMUS_TRACE_IRQ_H_
+#define _LITMUS_TRACE_IRQ_H_
+
+#ifdef CONFIG_SCHED_OVERHEAD_TRACE
+
+extern DEFINE_PER_CPU(atomic_t, irq_fired_count);
+
+static inline void ft_irq_fired(void)
+{
+        /* Only called with preemptions disabled.  */
+        atomic_inc(&__get_cpu_var(irq_fired_count));
+}
+
+
+#else
+
+#define ft_irq_fired() /* nothing to do */
+
+#endif
+
+#endif