First implementation of G-OMLP.wip-omlp-gedf

This patch implements G-OMLP (OMLP for G-EDF).  It reuses (calls)
much of the code from G-FMLP-Long.  Note that the implementation
here will have to change if/when P-OMLP is implemented.  This is
because P-OMLP uses seperate priority queues (PQ) for each CPU.  The OMLP
code will have to be smarter to figure out when to use a global PQ
or CPU-bound PQ. Also, PQ may be better implemented as a binary
(or binomial) heap.  It is a simple linked-list in this implementation.

10 files changed, 424 insertions, 3 deletions

diff --git a/include/litmus/fdso.h b/include/litmus/fdso.h
index b0e62a9098bd..4c67c87d0e1b 100644
--- a/include/litmus/fdso.h
+++ b/include/litmus/fdso.h
@@ -19,8 +19,9 @@ typedef enum  {
 
         FMLP_SEM        = 0,
         SRP_SEM         = 1,
+        OMLP_SEM        = 2,    
 
-        MAX_OBJ_TYPE    = 1
+        MAX_OBJ_TYPE    = 2
 } obj_type_t;
 
 struct inode_obj_id {
@@ -64,6 +65,7 @@ static inline void* od_lookup(int od, obj_type_t type)
 
 #define lookup_fmlp_sem(od)((struct fmlp_semaphore*)  od_lookup(od, FMLP_SEM))
 #define lookup_srp_sem(od) ((struct srp_semaphore*) od_lookup(od, SRP_SEM))
+#define lookup_omlp_sem(od)((struct omlp_semaphore*) od_lookup(od, OMLP_SEM))
 #define lookup_ics(od)     ((struct ics*)           od_lookup(od, ICS_ID))
 
 
diff --git a/include/litmus/sched_plugin.h b/include/litmus/sched_plugin.h
index 071e809564b2..186e99c6bb88 100644
--- a/include/litmus/sched_plugin.h
+++ b/include/litmus/sched_plugin.h
@@ -41,6 +41,25 @@ static inline struct fmlp_semaphore* to_fmlp(struct pi_semaphore* sem) {
 }
 #endif
 
+#ifdef CONFIG_OMLP
+struct omlp_semaphore {
+        /* NOTE: first part of struct matchs fmlp_semaphore, so
+         * omlp_struct can be cast to fmlp_struct
+         */
+        struct pi_semaphore pi; /* must always be first. */
+
+        /* current lock holder */
+        struct task_struct *holder;
+
+        /* PQ - just a single list since we only support G-EDF for now */
+        struct list_head pq_task_list;
+};
+
+static inline struct omlp_semaphore* to_omlp(struct pi_semaphore* sem) {
+        return (struct omlp_semaphore*)sem;
+}
+#endif
+
 /************************ setup/tear down ********************/
 
 typedef long (*activate_plugin_t) (void);
@@ -149,6 +168,13 @@ struct sched_plugin {
         return_priority_t       fmlp_return_priority;
         pi_block_t          fmlp_pi_block;
 #endif
+
+#ifdef CONFIG_OMLP
+        unsigned int            omlp_active;
+        inherit_priority_t      omlp_inherit_priority;
+        return_priority_t       omlp_return_priority;
+        pi_block_t                      omlp_pi_block;
+#endif
 } __attribute__ ((__aligned__(SMP_CACHE_BYTES)));
 
 
@@ -177,6 +203,14 @@ static inline int fmlp_active(void)
         return 0;
 #endif
 }
+static inline int omlp_active(void)
+{
+#ifdef CONFIG_OMLP
+        return litmus->omlp_active;
+#else
+        return 0;
+#endif
+}
 
 extern struct sched_plugin linux_sched_plugin;
 
diff --git a/include/litmus/unistd_32.h b/include/litmus/unistd_32.h
index dbddc6523f8e..3c55c8331e1b 100644
--- a/include/litmus/unistd_32.h
+++ b/include/litmus/unistd_32.h
@@ -19,5 +19,7 @@
 #define __NR_wait_for_ts_release __LSC(11)
 #define __NR_release_ts         __LSC(12)
 #define __NR_null_call          __LSC(13)
+#define __NR_omlp_down          __LSC(14)
+#define __NR_omlp_up            __LSC(15)
 
-#define NR_litmus_syscalls 14
+#define NR_litmus_syscalls 16
diff --git a/include/litmus/unistd_64.h b/include/litmus/unistd_64.h
index f0618e75348d..dd4b6c928b2c 100644
--- a/include/litmus/unistd_64.h
+++ b/include/litmus/unistd_64.h
@@ -33,5 +33,9 @@ __SYSCALL(__NR_wait_for_ts_release, sys_wait_for_ts_release)
 __SYSCALL(__NR_release_ts, sys_release_ts)
 #define __NR_null_call                          __LSC(13)
 __SYSCALL(__NR_null_call, sys_null_call)
+#define __NR_omlp_down                          __LSC(14)
+__SYSCALL(__NR_omlp_down, sys_omlp_down)
+#define __NR_omlp_up                            __LSC(15)
+__SYSCALL(__NR_omlp_up, sys_omlp_up)
 
-#define NR_litmus_syscalls 14
+#define NR_litmus_syscalls 16
diff --git a/litmus/Kconfig b/litmus/Kconfig
index e00887e672df..9549afbb5591 100644
--- a/litmus/Kconfig
+++ b/litmus/Kconfig
@@ -77,6 +77,22 @@ config FMLP
           Say Yes if you want FMLP long critical section
           synchronization support.
 
+config OMLP
+        bool "OMLP support"
+        depends on FMLP
+        default n
+        help
+          Include support for enhanced deterministic multiprocessor
+          real-time synchronization support.  In contrast to FMLP, which
+          is O(n), OMLP is O(m), where n is the number of tasks sharing a
+          resource and m is the number of processors.  OMLP always
+          lower-bounds FMLP-Long.
+
+          ONLY G-EDF CURRENTLY SUPPORTED!
+
+          Say Yes if you want OMLP critical section synchronization
+          support.
+
 endmenu
 
 menu "Tracing"
diff --git a/litmus/Makefile b/litmus/Makefile
index 1cf2b6267ae3..1d7f27ec568d 100644
--- a/litmus/Makefile
+++ b/litmus/Makefile
@@ -10,6 +10,7 @@ obj-y     = sched_plugin.o litmus.o \
             fdso.o \
             srp.o \
             fmlp.o \
+                omlp.o \
             bheap.o \
             ctrldev.o \
             sched_gsn_edf.o \
diff --git a/litmus/fdso.c b/litmus/fdso.c
index 85be716941d8..0cd0235d1a7e 100644
--- a/litmus/fdso.c
+++ b/litmus/fdso.c
@@ -19,11 +19,13 @@
 #include <litmus/fdso.h>
 
 extern struct fdso_ops fmlp_sem_ops;
+extern struct fdso_ops omlp_sem_ops;
 extern struct fdso_ops srp_sem_ops;
 
 static const struct fdso_ops* fdso_ops[] = {
         &fmlp_sem_ops,
         &srp_sem_ops,
+        &omlp_sem_ops
 };
 
 static void* fdso_create(obj_type_t type)
diff --git a/litmus/omlp.c b/litmus/omlp.c
new file mode 100644
index 000000000000..dbb39dc0c07c
--- /dev/null
+++ b/litmus/omlp.c
@@ -0,0 +1,319 @@
+/*
+ * OMLP implementation.
+ * Much of the code here is borrowed from include/asm-i386/semaphore.h
+ */
+
+#include <asm/atomic.h>
+
+#include <linux/semaphore.h>
+#include <linux/sched.h>
+#include <linux/wait.h>
+#include <linux/spinlock.h>
+
+#include <litmus/litmus.h>
+#include <litmus/sched_plugin.h>
+#include <litmus/edf_common.h>
+
+#include <litmus/fdso.h>
+
+#include <litmus/trace.h>
+
+#ifdef CONFIG_OMLP
+
+static  void* create_omlp_semaphore(void)
+{
+        struct omlp_semaphore* sem;
+        int i;
+
+        sem = kmalloc(sizeof(*sem), GFP_KERNEL);
+        if (!sem)
+                return NULL;
+        atomic_set(&sem->pi.count, 1);
+        sem->pi.sleepers = 0;
+        init_waitqueue_head(&sem->pi.wait);
+        sem->pi.hp.task = NULL;
+        sem->holder = NULL;
+        for (i = 0; i < NR_CPUS; i++)
+                sem->pi.hp.cpu_task[i] = NULL;
+
+        sem->pi.stack_node.inh_task = NULL;
+        INIT_LIST_HEAD(&sem->pi.stack_node.list);
+    
+    
+    INIT_LIST_HEAD(&sem->pq_task_list);
+
+    TRACE_CUR("number of online CPUs: %d", num_online_cpus());
+
+        return sem;
+}
+
+static int open_omlp_semaphore(struct od_table_entry* entry, void* __user arg)
+{
+        if (!omlp_active())
+                return -EBUSY;
+        return 0;
+}
+
+static void destroy_omlp_semaphore(void* sem)
+{
+        /* XXX assert invariants */
+        kfree(sem);
+}
+
+struct fdso_ops omlp_sem_ops = {
+        .create  = create_omlp_semaphore,
+        .open    = open_omlp_semaphore,
+        .destroy = destroy_omlp_semaphore
+};
+
+struct wq_pair {
+        struct task_struct*  tsk;
+        struct omlp_semaphore* sem;
+};
+
+static int rt_pi_wake_up(wait_queue_t *wait, unsigned mode, int sync,
+                           void *key)
+{
+        struct wq_pair* wqp   = (struct wq_pair*) wait->private;
+        set_rt_flags(wqp->tsk, RT_F_EXIT_SEM);
+        litmus->omlp_inherit_priority(to_pi(wqp->sem), wqp->tsk);
+        TRACE_TASK(wqp->tsk,
+                   "woken up by rt_pi_wake_up() (RT_F_SEM_EXIT, PI)\n");
+        /* point to task for default_wake_function() */
+        wait->private = wqp->tsk;
+        default_wake_function(wait, mode, sync, key);
+
+        /* Always return true since we know that if we encountered a task
+         * that was already running the wake_up raced with the schedule in
+         * rt_pi_down(). In that case the task in rt_pi_down() will be scheduled
+         * immediately and own the lock. We must not wake up another task in
+         * any case.
+         */
+        return 1;
+}
+
+typedef int (*list_order_t)(struct wq_pair*, struct wq_pair*);
+static int edf_order(struct wq_pair *a, struct wq_pair *b)
+{
+    return(edf_higher_prio(a->tsk, b->tsk));
+}
+
+static inline void add_list_ordered(
+    struct list_head* pq,
+    wait_queue_t *wait,
+    list_order_t cmp)
+{
+    struct wq_pair       *curr_queued;
+    wait_queue_t        *tmp;
+    struct list_head    *pos, *next;
+    
+    struct wq_pair       *to_insert =
+        (struct wq_pair*) list_entry(&wait->task_list, wait_queue_t, task_list)->private;
+    
+    /* list is empty.  belongs at tail. */
+    if(list_empty(pq)) {
+        list_add_tail(&wait->task_list, pq);
+        return;
+    }   
+    
+    /* new job has the least priority.  belongs at tail. */
+    tmp = list_entry(pq->prev, wait_queue_t, task_list);
+    curr_queued = (struct wq_pair*)tmp->private;
+    if(curr_queued && !cmp(to_insert, curr_queued))
+    {   
+        list_add_tail(&wait->task_list, pq);
+        return;
+    }   
+    
+    /* belongs between nodes.  this is the hardest case
+     * and hence left for last.
+     */
+    list_for_each_safe(pos, next, pq) {
+        tmp = list_entry(pos, wait_queue_t, task_list);
+        curr_queued = (struct wq_pair*)tmp->private;
+        if (curr_queued && cmp(to_insert, curr_queued)) {
+            list_add(&wait->task_list, pos->prev);
+            return;
+        }   
+    }   
+    
+    /* fail-safe?? */
+    list_add_tail(&wait->task_list, pq);
+    return;
+}
+
+static int do_omlp_down(struct omlp_semaphore* sem)
+{
+        unsigned long flags;
+        struct task_struct *tsk = current;
+        struct wq_pair pair;
+        int suspended = 1;
+        int count;
+
+        wait_queue_t wait = {
+        .flags = 0,
+                .private = &pair,
+                .func    = rt_pi_wake_up,
+                .task_list = {NULL, NULL}
+        };
+
+        pair.tsk = tsk;
+        pair.sem = sem;
+    
+        spin_lock_irqsave(&sem->pi.wait.lock, flags);
+
+    count = atomic_dec_return(&sem->pi.count);
+    
+        if (count < 0 || waitqueue_active(&sem->pi.wait)) {
+
+        tsk->state = TASK_UNINTERRUPTIBLE;
+
+        if(count <= -(num_online_cpus()) || !list_empty(&sem->pq_task_list)) {
+            wait.flags |= WQ_FLAG_EXCLUSIVE;
+            /* G-EDF only, so there's one PQ. */
+            add_list_ordered(&sem->pq_task_list, &wait, edf_order);
+            TRACE_CUR("count = %d, suspends (%p) on PI lock (PQ) %p\n", count, tsk, sem);
+        } else {
+            /* we need to suspend on the wait queue */
+            add_wait_queue_exclusive_locked(&sem->pi.wait, &wait);
+            
+            TRACE_CUR("count = %d, suspends (%p) on PI lock (FIFO) %p\n", count, tsk, sem);
+            litmus->omlp_pi_block(to_pi(sem), tsk);            
+        }
+
+        /* release lock before sleeping */
+        spin_unlock_irqrestore(&sem->pi.wait.lock, flags);
+            
+        TS_PI_DOWN_END;
+        preempt_enable_no_resched();
+            
+            
+        /* we depend on the FIFO order
+         * Thus, we don't need to recheck when we wake up, we
+         * are guaranteed to have the lock since there is only one
+         * wake up per release
+         */
+        schedule();
+        
+        TRACE_CUR("woke up (%p), now owns PI lock %p\n", tsk, sem);
+        
+        /* try_to_wake_up() set our state to TASK_RUNNING,
+         * all we need to do is to remove our wait queue entry
+         * We'll now be on pi.wait even if we enqueued on pqwait.
+         */
+        remove_wait_queue(&sem->pi.wait, &wait);
+        } else {
+                /* no priority inheritance necessary, since there are no queued
+                 * tasks.
+                 */
+                suspended = 0;
+                TRACE_CUR("(%p) acquired PI lock %p, no contention\n", tsk, sem);
+                sem->holder  = tsk;
+
+                /* don't know if we're global or partitioned. */
+                sem->pi.hp.task = tsk;
+                sem->pi.hp.cpu_task[get_partition(tsk)] = tsk;
+
+                litmus->omlp_inherit_priority(to_pi(sem), tsk);
+                spin_unlock_irqrestore(&sem->pi.wait.lock, flags);
+        }
+        return suspended;
+}
+
+static void do_omlp_up(struct omlp_semaphore* sem)
+{
+        unsigned long flags;
+
+        spin_lock_irqsave(&sem->pi.wait.lock, flags);
+
+        TRACE_CUR("(%p) releases PI lock %p\n", current, sem);
+        litmus->omlp_return_priority(to_pi(sem));
+        sem->holder = NULL;
+    
+        if (atomic_inc_return(&sem->pi.count) < 1) {
+                if (!list_empty(&sem->pq_task_list)) {  
+            /* Move the head task from pq_task_list to pi.wait.
+             * Do this before waking up the next task so it gets
+             * the proper pi.
+             */
+            wait_queue_t *wait =
+                list_entry(sem->pq_task_list.next, wait_queue_t, task_list);
+            list_del(&wait->task_list);
+            INIT_LIST_HEAD(&wait->task_list);
+            
+            /* we need to suspend on the wait queue */
+            add_wait_queue_exclusive_locked(&sem->pi.wait, wait);
+            
+            TRACE_CUR("moving waiter (%p) to FIFO queue. %p\n", ((struct wq_pair*)(wait->private))->tsk, sem);
+            /* Safe since sem->holder == NULL and pi_block checks
+             * for the case.
+             */
+            litmus->omlp_pi_block(to_pi(sem), ((struct wq_pair*)(wait->private))->tsk);
+        }
+        
+                /* there is a task queued */
+                wake_up_locked(&sem->pi.wait);
+    }
+
+        spin_unlock_irqrestore(&sem->pi.wait.lock, flags);
+}
+
+asmlinkage long sys_omlp_down(int sem_od)
+{
+        long ret = 0;
+        struct omlp_semaphore * sem;
+        int suspended = 0;
+
+        preempt_disable();
+        TS_PI_DOWN_START;
+
+        sem = lookup_omlp_sem(sem_od);
+        if (sem)
+                suspended = do_omlp_down(sem);
+        else
+                ret = -EINVAL;
+
+        if (!suspended) {
+                TS_PI_DOWN_END;
+                preempt_enable();
+        }
+
+        return ret;
+}
+
+asmlinkage long sys_omlp_up(int sem_od)
+{
+        long ret = 0;
+        struct omlp_semaphore * sem;
+
+        preempt_disable();
+        TS_PI_UP_START;
+
+        sem = lookup_omlp_sem(sem_od);
+        if (sem)
+                do_omlp_up(sem);
+        else
+                ret = -EINVAL;
+
+
+        TS_PI_UP_END;
+        preempt_enable();
+
+        return ret;
+}
+
+#else
+
+struct fdso_ops omlp_sem_ops = {};
+
+asmlinkage long sys_omlp_down(int sem_od)
+{
+        return -ENOSYS;
+}
+
+asmlinkage long sys_omlp_up(int sem_od)
+{
+        return -ENOSYS;
+}
+
+#endif
diff --git a/litmus/sched_gsn_edf.c b/litmus/sched_gsn_edf.c
index 4c8a21705810..6b4e4d9aa099 100644
--- a/litmus/sched_gsn_edf.c
+++ b/litmus/sched_gsn_edf.c
@@ -775,9 +775,34 @@ static long gsnedf_fmlp_return_priority(struct pi_semaphore *_sem)
 
         return ret;
 }
+#endif
+
+
+#ifdef CONFIG_OMLP
+/* Reuse FMLP hooks since OMLP implements the G-EDF stuff
+ * already.  May have to do G-EDF specific work here in the
+ * future.  Will probably need additional callback to move
+ * items from PQ to FIFO.
+ */
+static long gsnedf_omlp_pi_block(struct pi_semaphore *_sem,
+                                 struct task_struct *new_waiter)
+{
+    return gsnedf_fmlp_pi_block(_sem, new_waiter);
+}
 
+static long gsnedf_omlp_inherit_priority(struct pi_semaphore *_sem,
+                                         struct task_struct *new_owner)
+{
+    return gsnedf_fmlp_inherit_priority(_sem, new_owner);
+}
+
+static long gsnedf_omlp_return_priority(struct pi_semaphore *_sem)
+{
+    return gsnedf_fmlp_return_priority(_sem);
+}
 #endif
 
+
 static long gsnedf_admit_task(struct task_struct* tsk)
 {
         return 0;
@@ -830,6 +855,12 @@ static struct sched_plugin gsn_edf_plugin __cacheline_aligned_in_smp = {
         .fmlp_inherit_priority  = gsnedf_fmlp_inherit_priority,
         .fmlp_return_priority   = gsnedf_fmlp_return_priority,
 #endif
+#ifdef CONFIG_OMLP
+        .omlp_active            = 1,
+        .omlp_pi_block          = gsnedf_omlp_pi_block,
+        .omlp_inherit_priority  = gsnedf_omlp_inherit_priority,
+        .omlp_return_priority   = gsnedf_omlp_return_priority,
+#endif    
         .admit_task             = gsnedf_admit_task,
         .activate_plugin        = gsnedf_activate_plugin,
 };
diff --git a/litmus/sched_plugin.c b/litmus/sched_plugin.c
index 0ebb677198d5..c240f5236e81 100644
--- a/litmus/sched_plugin.c
+++ b/litmus/sched_plugin.c
@@ -167,6 +167,11 @@ struct sched_plugin linux_sched_plugin = {
         .fmlp_return_priority = litmus_dummy_return_priority,
         .fmlp_pi_block = litmus_dummy_pi_block,
 #endif
+#ifdef CONFIG_OMLP
+        .omlp_inherit_priority = litmus_dummy_inherit_priority,
+        .omlp_return_priority = litmus_dummy_return_priority,
+        .omlp_pi_block = litmus_dummy_pi_block,
+#endif
         .admit_task = litmus_dummy_admit_task
 };
 
@@ -219,6 +224,11 @@ int register_sched_plugin(struct sched_plugin* plugin)
         CHECK_PI(fmlp, return_priority);
         CHECK_PI(fmlp, pi_block);
 #endif
+#ifdef CONFIG_OMLP
+        CHECK_PI(omlp, inherit_priority);
+        CHECK_PI(omlp, return_priority);
+        CHECK_PI(omlp, pi_block);
+#endif
         CHECK(admit_task);
 
         if (!plugin->release_at)