Merge with git+ssh://cvs.cs.unc.edu/cvs/proj/litmus/repo/litmus

Bjoern's changes + mine. Still need to fill in some stubs and ensure that
nothing broke.

7 files changed, 237 insertions, 44 deletions

diff --git a/include/asm-i386/unistd.h b/include/asm-i386/unistd.h
index 98920efd2c..d6ed041f88 100644
--- a/include/asm-i386/unistd.h
+++ b/include/asm-i386/unistd.h
@@ -336,7 +336,8 @@
 #define __NR_reset_stat         326
 #define __NR_sleep_next_period  327
 #define __NR_scheduler_setup    328
-/* 329-330 reserved for Bjoern... */
+#define __NR_enter_np           329
+#define __NR_exit_np            330
 #define __NR_pi_sema_init       331
 #define __NR_pi_down            332
 #define __NR_pi_up              333
diff --git a/include/linux/edf_common.h b/include/linux/edf_common.h
index 9c00bb1937..3b6a1de457 100644
--- a/include/linux/edf_common.h
+++ b/include/linux/edf_common.h
@@ -25,18 +25,44 @@ typedef struct _edf_domain {
         (list_entry((edf)->ready_queue.next, struct task_struct, rt_list))
 
 void edf_domain_init(edf_domain_t *edf, edf_check_resched_needed_t f);
-void  add_ready(edf_domain_t* edf, struct task_struct *new);
+
+int edf_higher_prio(struct task_struct* first, 
+                    struct task_struct* second);
+
+void __add_ready(edf_domain_t* edf, struct task_struct *new);
+void __add_release(edf_domain_t* edf, struct task_struct *task);
+
 struct task_struct* __take_ready(edf_domain_t* edf);
-void add_release(edf_domain_t* edf, struct task_struct *task);
+
 void try_release_pending(edf_domain_t* edf);
 void __prepare_new_release(struct task_struct *t, jiffie_t start);
 #define prepare_new_release(t) __prepare_new_release(t, jiffies)
 void prepare_for_next_period(struct task_struct *t);
 void prepare_new_releases(edf_domain_t *edf, jiffie_t start);
+void __prepare_new_releases(edf_domain_t *edf, jiffie_t start);
 int preemption_needed(edf_domain_t* edf, struct task_struct *t);
 long edf_sleep_next_period(void);
 
 #define job_completed(t) (!is_be(t) && \
         (t)->rt_param.times.exec_time == (t)->rt_param.basic_params.exec_cost)
 
+static inline void add_ready(edf_domain_t* edf, struct task_struct *new)
+{
+        unsigned long flags;    
+        /* first we need the write lock for edf_ready_queue */  
+        write_lock_irqsave(&edf->ready_lock, flags);
+        __add_ready(edf, new);
+        write_unlock_irqrestore(&edf->ready_lock, flags);
+}
+
+static inline void add_release(edf_domain_t* edf, struct task_struct *task)
+{
+        unsigned long flags;    
+        /* first we need the write lock for edf_ready_queue */  
+        spin_lock_irqsave(&edf->release_lock, flags);
+        __add_release(edf, task);
+        spin_unlock_irqrestore(&edf->release_lock, flags);
+}
+
+
 #endif 
diff --git a/include/linux/litmus.h b/include/linux/litmus.h
index 94c2735422..c325164e93 100644
--- a/include/linux/litmus.h
+++ b/include/linux/litmus.h
@@ -10,22 +10,23 @@
 #include <linux/sched_trace.h>
 
 typedef enum {
-        SCHED_BEG               = 0,
-        SCHED_LINUX             = 0,
-        SCHED_PFAIR             = 1,
-        SCHED_PFAIR_STAGGER     = 2,
-        SCHED_PART_EDF          = 3,
-        SCHED_PART_EEVDF        = 4,
-        SCHED_GLOBAL_EDF        = 5,
-        SCHED_PFAIR_DESYNC      = 6,
-        SCHED_GLOBAL_EDF_NP     = 7,    
-        SCHED_CUSTOM            = 8,
-        SCHED_EDF_HSB           = 9,
+        SCHED_BEG               =  0,
+        SCHED_LINUX             =  0,
+        SCHED_PFAIR             =  1,
+        SCHED_PFAIR_STAGGER     =  2,
+        SCHED_PART_EDF          =  3,
+        SCHED_PART_EEVDF        =  4,
+        SCHED_GLOBAL_EDF        =  5,
+        SCHED_PFAIR_DESYNC      =  6,
+        SCHED_GLOBAL_EDF_NP     =  7,   
+        SCHED_CUSTOM            =  8,
+        SCHED_EDF_HSB           =  9,
+        SCHED_GSN_EDF           = 10,
 
         /*      Add your scheduling policy here */
 
-        SCHED_END               = 9,
-        SCHED_DEFAULT           = 0,
+        SCHED_END               = 10,
+        SCHED_DEFAULT           =  0,
         SCHED_INVALID           = -1,
 } spolicy;
 
@@ -62,6 +63,7 @@ typedef enum {
 #define PLUGIN_PFAIR_DESYNC     "desync"
 #define PLUGIN_GLOBAL_EDF_NP    "global_edf_np"
 #define PLUGIN_EDF_HSB          "edf_hsb"
+#define PLUGIN_GSN_EDF          "gsn_edf"
 
 /*      Additional clone flags  
         Indicates that the thread is to be used in 
@@ -95,6 +97,7 @@ extern atomic_t rt_mode;
 extern  spinlock_t litmus_task_set_lock;
 
 
-#define TRACE(fmt, args...) sched_trace_log_message(fmt, ## args);
+#define TRACE(fmt, args...) \
+        sched_trace_log_message("%d: " fmt, raw_smp_processor_id(), ## args);
 
 #endif  
diff --git a/include/linux/pfair_common.h b/include/linux/pfair_common.h
new file mode 100644
index 0000000000..67e18c601a
--- /dev/null
+++ b/include/linux/pfair_common.h
@@ -0,0 +1,40 @@
+/* PFAIR common data structures and utility functions shared by all PFAIR 
+ * based scheduler plugins
+ */
+
+#ifndef __UNC_PFAIR_COMMON_H__
+#define __UNC_PFAIR_COMMON_H__
+
+#include <linux/queuelock.h>
+#include <linux/cpumask.h>
+
+typedef struct _pfair_domain {
+        /* Global lock to protect the data structures */
+        queuelock_t                     pfair_lock;
+        /* runnable rt tasks are in here */
+        struct list_head                ready_queue; 
+
+        /* real-time tasks waiting for release are in here */
+        struct list_head                release_queue;
+        
+        /*  CPU's in the domain */
+        cpumask_t domain_cpus;
+
+} pfair_domain_t;
+
+#define next_ready(pfair) \
+        (list_entry((pfair)->ready_queue.next, struct task_struct, rt_list))
+void pfair_domain_init(pfair_domain_t *pfair);
+void  pfair_add_ready(pfair_domain_t* pfair, struct task_struct *new);
+struct task_struct* __pfair_take_ready(pfair_domain_t* pfair);
+void pfair_add_release(pfair_domain_t* pfair, struct task_struct *task);
+void pfair_try_release_pending(pfair_domain_t* pfair);
+void __pfair_prepare_new_release(struct task_struct *t, jiffie_t start);
+
+void pfair_prepare_next_job(struct task_struct *t);
+void pfair_prepare_next_subtask(struct task_struct *t);
+
+void pfair_prepare_new_releases(pfair_domain_t *pfair, jiffie_t start);
+
+#endif
+
diff --git a/include/linux/pfair_math.h b/include/linux/pfair_math.h
new file mode 100644
index 0000000000..dab1778f0b
--- /dev/null
+++ b/include/linux/pfair_math.h
@@ -0,0 +1,77 @@
+/*      PFAIR Mathematical functions */
+#ifndef __UNC_PFAIR_MATH_H__
+#define __UNC_PFAIR_MATH_H__
+
+#include <linux/rt_param.h>
+#include <asm/div64.h>
+#include <linux/litmus.h>
+#include <linux/sched.h>
+
+/*
+* This file defines  mathematical functions "ceiling", "floor",
+* and PFAIR specific functions for computing the release and
+* the deadline of a subtask, as well as tie breakers:
+* b-bit and group deadline.
+*/
+static inline quantum_t FLOOR(quantum_t a, unsigned long b)
+{
+        BUG_ON( b == 0);
+        do_div(a, b);
+        return a;       
+}
+static inline quantum_t CEIL(quantum_t a, unsigned long  b)
+{
+        quantum_t t = FLOOR(a, b);
+        return (quantum_t)((t * b == a) ? t : (t + 1));
+}
+
+
+/*
+*       invariant - i-1=get_passed_quanta(t)
+*
+*       release time of i-th subtask of j-th job is
+*       r_{ij}+\lfloor i-1/wt(T) \rfloor
+*       This operation should be robust to wrap-around
+*       so we can compare the result with jiffies safely
+*/
+static inline quantum_t release_time(struct task_struct * t)
+{
+        quantum_t e = get_exec_cost(t);
+        quantum_t p = get_rt_period(t);
+        return FLOOR((get_passed_quanta(t)) * p, e);
+}
+/*
+*       deadline time of i-th subtask of j-th job is
+*       r_{ij}+\lceil i/wt(T) \rceil
+*       This operation should be robust to wrap-around
+*       so we can compare the result with jiffies safely
+*/
+static inline quantum_t pfair_deadline(struct task_struct * t)
+{
+        quantum_t e = get_exec_cost(t);
+        quantum_t p = get_rt_period(t);
+        return CEIL((get_passed_quanta(t) + 1) * p, e);
+}
+/*      In PFAIR b-bit is defined as 
+*       \lceil i/wt(T) \rceil-\lfloor i/wt(T) \rfloor
+*/
+static inline int b_bit(struct task_struct *t)
+{
+        quantum_t e = get_exec_cost(t);
+        quantum_t p = get_rt_period(t);
+        return CEIL((get_passed_quanta(t) + 1) * p, e)-
+                FLOOR((get_passed_quanta(t) + 1) * p, e);
+}
+/*
+*       Group deadline 
+*/
+static inline quantum_t group_deadline(struct task_struct * t)
+{
+        quantum_t p = get_rt_period(t);
+        quantum_t e = get_exec_cost(t);
+        quantum_t stage1 = CEIL((get_passed_quanta(t) + 1) * p, e);
+        quantum_t stage2 = CEIL(stage1 * (p - e), p);
+        return CEIL(stage2 * p, p - e);
+}
+
+#endif /*       __UNC_PFAIR_MATH_H__    */
diff --git a/include/linux/rt_param.h b/include/linux/rt_param.h
index b20f5b44a6..f2d6de639e 100644
--- a/include/linux/rt_param.h
+++ b/include/linux/rt_param.h
@@ -23,6 +23,30 @@ typedef struct rt_param {
         task_class_t    class;
 } rt_param_t;
 
+typedef struct {
+        /* when will this task be release the next time? */
+        jiffie_t        release;
+        /* time instant the last job was released  */
+        jiffie_t        last_release;
+        /* what is the current deadline? */
+        jiffie_t        deadline;
+        /* b-bit tie breaker for PFAIR, it is ignored in EDF */
+        int             b_bit;
+        /* group deadline tie breaker, it is ignored in EDF */
+        jiffie_t        group_deadline;
+        /* how long has this task executed so far? 
+         * In case of capacity sharing a job completion cannot be
+         * detected by checking time_slice == 0 as the job may have
+         * executed while using another capacity. Use this counter
+         * to keep track of the time spent on a CPU by a job.
+         *
+         * In other words: The number of consumed quanta since the
+         *                  last job release.
+         */
+        unsigned int    exec_time;
+} in_times_t;
+
+
 /*      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.
@@ -46,25 +70,8 @@ typedef struct task_rt_param {
          * sem is being held.
          */
         struct task_struct **inh_task;
-        struct {
-                /* when will this task be release the next time? */
-                jiffie_t        release;
-                /* time instant the last job was released  */
-                jiffie_t        last_release;
-                /* what is the current deadline? */
-                jiffie_t        deadline;
-
-                /* how long has this task executed so far? 
-                 * In case of capacity sharing a job completion cannot be
-                 * detected by checking time_slice == 0 as the job may have
-                 * executed while using another capacity. Use this counter
-                 * to keep track of the time spent on a CPU by a job.
-                 *
-                 * In other words: The number of consumed quanta since the
-                 *                  last job release.
-                 */
-                unsigned int    exec_time;
-        } times;
+        
+        unsigned int            is_non_preemptable;
         
         /* put information for feedback control stuff and 
          * information about the performance of the task here
@@ -73,6 +80,9 @@ typedef struct task_rt_param {
                 /* How many non-tardy jobs since the last tardy job? */
                 unsigned int    nontardy_jobs_ctr;
         } stats;
+        
+        in_times_t times;
+        in_times_t backup;
 
         /* for zone-based locking: flag indicating whether task
          * is waiting for the end of the blocking zone
@@ -86,12 +96,19 @@ typedef struct task_rt_param {
          * data structures.
          */
         int                     litmus_controlled;
+
+        /* This field can be used by plugins to store where the task
+         * is currently scheduled. It is the responsibility of the
+         * plugin to avoid race conditions.
+         */
+        int                     scheduled_on;
 } task_rt_param_t;
 
 /*      Possible RT flags       */
-#define RT_F_RUNNING    0x00000000
-#define RT_F_SLEEP      0x00000001
-#define RT_F_EXP_QUANTA 0x00000002
+#define RT_F_RUNNING            0x00000000
+#define RT_F_SLEEP              0x00000001
+#define RT_F_EXP_QUANTA         0x00000002
+#define RT_F_NON_PREEMTABLE     0x00000004
 
 
 /*      Realtime utility macros */
@@ -114,6 +131,7 @@ typedef struct task_rt_param {
         ((t)->rt_param.basic_params.class == RT_CLASS_SOFT)
 #define is_be(t)                \
         ((t)->rt_param.basic_params.class == RT_CLASS_BEST_EFFORT)
+#define is_np(t)                ((t)->rt_param.is_non_preemptable)
 
 #define clear_rt_params(t) \
 memset(&(t)->rt_param,0, sizeof(struct task_rt_param))
@@ -121,6 +139,9 @@ memset(&(t)->rt_param,0, sizeof(struct task_rt_param))
 #define get_last_release_time(t)   ((t)->rt_param.times.last_release)
 #define set_last_release_time(t,r) ((t)->rt_param.times.last_release=(r))
 
+#define get_release(t) ((t)->rt_param.times.release)
+#define set_release(t,r) ((t)->rt_param.times.release=(r))
+
 #define is_running(t)   ((t)->state == TASK_RUNNING)
 #define is_released(t)  (time_before_eq((t)->rt_param.times.release, jiffies))
 #define is_tardy(t)     (time_before_eq((t)->rt_param.times.deadline, jiffies))
@@ -137,6 +158,11 @@ memset(&(t)->rt_param,0, sizeof(struct task_rt_param))
         (a)->rt_param.times.release,\
         (b)->rt_param.times.release))
 
+#define backup_times(t) do { (t)->rt_param.backup=(t)->rt_param.times; \
+                                } while(0);
+#define restore_times(t) do { (t)->rt_param.times=(t)->rt_param.backup; \
+                                } while(0);
+
 /* struct for semaphore with priority inheritance */
 struct pi_semaphore {
         atomic_t count;
diff --git a/include/linux/sched_plugin.h b/include/linux/sched_plugin.h
index 59e9e2f353..ad6cee3b30 100644
--- a/include/linux/sched_plugin.h
+++ b/include/linux/sched_plugin.h
@@ -38,9 +38,8 @@ typedef reschedule_check_t (*scheduler_tick_t) (void);
 typedef int (*schedule_t) (struct task_struct * prev, 
                            struct task_struct ** next,
                            runqueue_t * rq);
-/* clean up after the task switch has occured
- * it is guaranteed that the function is only called if prev is a real-time
- * task
+/* Clean up after the task switch has occured.
+ * This function is called after every (even non-rt) task switch.
  */
 typedef void (*finish_switch_t)(struct task_struct *prev);
 
@@ -57,6 +56,19 @@ typedef void (*task_blocks_t)  (struct task_struct *task);
 /* called when a real-time task exits. Free any allocated resources */
 typedef long (*tear_down_t)    (struct task_struct *);
 
+/* called when a real-time task wants to enter a non-preemptable section */
+typedef long (*enter_np_t) (struct task_struct *);
+/* called when a real-time task wants to leave a non-preemptable section */
+typedef long (*exit_np_t) (struct task_struct *);
+
+
+typedef long (*inherit_priority_t) (struct task_struct *offspring,
+                                    struct task_struct *deceased);
+
+typedef long (*return_priority_t) (struct task_struct *offspring,
+                                   struct task_struct *deceased);
+
+
 
 /********************* sys call backends  ********************/
 /* This function causes the caller to sleep until the next release */
@@ -82,14 +94,22 @@ struct sched_plugin {
         finish_switch_t         finish_switch;
 
         /*      syscall backend         */
-        sleep_next_period_t sleep_next_period;
-        scheduler_setup_t   scheduler_setup;
+        sleep_next_period_t     sleep_next_period;
+        scheduler_setup_t       scheduler_setup;
 
         /*      task state changes      */
         prepare_task_t          prepare_task;
         wake_up_task_t          wake_up_task;
         task_blocks_t           task_blocks;
         tear_down_t             tear_down;
+
+        /*   non-preemptable sections   */
+        enter_np_t              enter_np;
+        exit_np_t               exit_np;
+
+        /*     priority inheritance     */
+        inherit_priority_t      inherit_priority;
+        return_priority_t       return_priority;
 } __attribute__ ((__aligned__(SMP_CACHE_BYTES)));
 
 typedef struct sched_plugin sched_plugin_t;