1 files changed, 262 insertions, 2 deletions

diff --git a/litmus/sched_psn_edf.c b/litmus/sched_psn_edf.c
index 178ca0b33b04..2e5b9c9d75d7 100644
--- a/litmus/sched_psn_edf.c
+++ b/litmus/sched_psn_edf.c
@@ -540,6 +540,251 @@ static struct litmus_lock* psnedf_new_fmlp(void)
         return &sem->litmus_lock;
 }
 
+
+
+/* ******************** OMLP support **********************/
+
+/* Since jobs spin "virtually" while waiting to acquire a lock,
+ * they first must aquire a local per-cpu resource.
+ */
+static DEFINE_PER_CPU(wait_queue_head_t, omlp_token_wait);
+static DEFINE_PER_CPU(struct task_struct*, omlp_token);
+
+/* called with preemptions off <=> no local modifications */
+static void omlp_grab_token(void)
+{
+        struct task_struct* t = current;
+
+        while (1) {
+                if (__get_cpu_var(omlp_token) == NULL) {
+                        /* take it */
+                        __get_cpu_var(omlp_token) = t;
+                        break;
+                } else {
+                        /* some job is spinning => enqueue in request queue */
+                        prio_wait_queue_t wait;
+                        wait_queue_head_t* token_waiters = &__get_cpu_var(omlp_token_wait);
+                        unsigned long flags;
+
+                        /* ordered by regular priority; break by lower PID */
+                        init_prio_waitqueue_entry_tie(&wait, t, get_deadline(t), t->pid);
+
+                        spin_lock_irqsave(&token_waiters->lock, flags);
+
+                        set_task_state(t, TASK_UNINTERRUPTIBLE);
+
+                        __add_wait_queue_prio_exclusive(token_waiters, &wait);
+
+                        TRACE_CUR("waiting for OMLP token\n");
+
+                        spin_unlock_irqrestore(&token_waiters->lock, flags);
+
+                        TS_LOCK_SUSPEND;
+
+                        preempt_enable_no_resched();
+
+                        schedule();
+
+                        preempt_disable();
+
+                        TS_LOCK_RESUME;
+                        /* Recheck if we got it */
+                }
+        }
+        /* ok, now it is ours */
+        TRACE_CUR("got OMLP token\n");
+}
+
+/* called with preemptions off */
+static void omlp_release_token(void)
+{
+        struct task_struct* t = current, *next;
+        unsigned long flags;
+        wait_queue_head_t* token_waiters = &__get_cpu_var(omlp_token_wait);
+
+        BUG_ON(__get_cpu_var(omlp_token) != t);
+
+        __get_cpu_var(omlp_token) = NULL;
+
+        TRACE_CUR("released OMLP token\n");
+
+        spin_lock_irqsave(&token_waiters->lock, flags);
+        next = __waitqueue_remove_first(token_waiters);
+
+        if (next)
+                wake_up_process(next);
+
+        spin_unlock_irqrestore(&token_waiters->lock, flags);
+}
+
+
+struct omlp_semaphore {
+        struct litmus_lock litmus_lock;
+
+        /* current resource holder */
+        struct task_struct *owner;
+
+        /* FIFO queue of waiting tasks */
+        wait_queue_head_t wait;
+};
+
+static inline struct omlp_semaphore* omlp_from_lock(struct litmus_lock* lock)
+{
+        return container_of(lock, struct omlp_semaphore, litmus_lock);
+}
+int psnedf_omlp_lock(struct litmus_lock* l)
+{
+        struct task_struct* t = current;
+        struct omlp_semaphore *sem = omlp_from_lock(l);
+        wait_queue_t wait;
+        unsigned long flags;
+
+        if (!is_realtime(t))
+                return -EPERM;
+
+        preempt_disable();
+
+        omlp_grab_token();
+
+        /* Priority-boost ourself *before* we suspend so that
+         * our priority is boosted when we resume. */
+        boost_priority(t);
+
+        spin_lock_irqsave(&sem->wait.lock, flags);
+
+        if (sem->owner) {
+                /* resource is not free => must suspend and wait */
+
+                init_waitqueue_entry(&wait, t);
+
+                /* FIXME: interruptible would be nice some day */
+                set_task_state(t, TASK_UNINTERRUPTIBLE);
+
+                __add_wait_queue_tail_exclusive(&sem->wait, &wait);
+
+                /* release lock before sleeping */
+                spin_unlock_irqrestore(&sem->wait.lock, flags);
+
+                /* 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.
+                 */
+                TS_LOCK_SUSPEND;
+
+                preempt_enable_no_resched();
+
+                schedule();
+
+                preempt_disable();
+
+                TS_LOCK_RESUME;
+
+                /* Since we hold the lock, no other task will change
+                 * ->owner. We can thus check it without acquiring the spin
+                 * lock. */
+                BUG_ON(sem->owner != t);
+        } else {
+                /* it's ours now */
+                sem->owner = t;
+
+                spin_unlock_irqrestore(&sem->wait.lock, flags);
+        }
+
+        preempt_enable();
+
+        return 0;
+}
+
+int psnedf_omlp_unlock(struct litmus_lock* l)
+{
+        struct task_struct *t = current, *next;
+        struct omlp_semaphore *sem = omlp_from_lock(l);
+        unsigned long flags;
+        int err = 0;
+
+        preempt_disable();
+
+        spin_lock_irqsave(&sem->wait.lock, flags);
+
+        if (sem->owner != t) {
+                err = -EINVAL;
+                spin_unlock_irqrestore(&sem->wait.lock, flags);
+                goto out;
+        }
+
+        /* we lose the benefit of priority boosting */
+
+        unboost_priority(t);
+
+        /* check if there are jobs waiting for this resource */
+        next = __waitqueue_remove_first(&sem->wait);
+        if (next) {
+                /* next becomes the resouce holder */
+                sem->owner = next;
+
+                /* Wake up next. The waiting job is already priority-boosted. */
+                wake_up_process(next);
+        } else
+                /* resource becomes available */
+                sem->owner = NULL;
+
+        spin_unlock_irqrestore(&sem->wait.lock, flags);
+
+        omlp_release_token();
+
+out:
+        preempt_enable();
+        return err;
+}
+
+int psnedf_omlp_close(struct litmus_lock* l)
+{
+        struct task_struct *t = current;
+        struct omlp_semaphore *sem = omlp_from_lock(l);
+        unsigned long flags;
+
+        int owner;
+
+        spin_lock_irqsave(&sem->wait.lock, flags);
+
+        owner = sem->owner == t;
+
+        spin_unlock_irqrestore(&sem->wait.lock, flags);
+
+        if (owner)
+                psnedf_omlp_unlock(l);
+
+        return 0;
+}
+
+void psnedf_omlp_free(struct litmus_lock* lock)
+{
+        kfree(omlp_from_lock(lock));
+}
+
+static struct litmus_lock_ops psnedf_omlp_lock_ops = {
+        .close  = psnedf_omlp_close,
+        .lock   = psnedf_omlp_lock,
+        .unlock = psnedf_omlp_unlock,
+        .deallocate = psnedf_omlp_free,
+};
+
+static struct litmus_lock* psnedf_new_omlp(void)
+{
+        struct omlp_semaphore* sem;
+
+        sem = kmalloc(sizeof(*sem), GFP_KERNEL);
+        if (!sem)
+                return NULL;
+
+        sem->owner   = NULL;
+        init_waitqueue_head(&sem->wait);
+        sem->litmus_lock.ops = &psnedf_omlp_lock_ops;
+
+        return &sem->litmus_lock;
+}
+
+
 /* **** lock constructor **** */
 
 
@@ -561,6 +806,15 @@ static long psnedf_allocate_lock(struct litmus_lock **lock, int type,
                         err = -ENOMEM;
                 break;
 
+        case OMLP_SEM:
+                /* O(m) Locking Protocol */
+                *lock = psnedf_new_omlp();
+                if (*lock)
+                        err = 0;
+                else
+                        err = -ENOMEM;
+                break;
+
         case SRP_SEM:
                 /* Baker's Stack Resource Policy */
                 srp = allocate_srp_semaphore();
@@ -580,13 +834,19 @@ static long psnedf_allocate_lock(struct litmus_lock **lock, int type,
 
 static long psnedf_activate_plugin(void)
 {
-#ifdef CONFIG_RELEASE_MASTER
+
         int cpu;
 
         for_each_online_cpu(cpu) {
+#ifdef CONFIG_RELEASE_MASTER
                 remote_edf(cpu)->release_master = atomic_read(&release_master_cpu);
-        }
 #endif
+#ifdef CONFIG_LITMUS_LOCKING
+                init_waitqueue_head(&per_cpu(omlp_token_wait, cpu));
+                per_cpu(omlp_token, cpu) = NULL;
+#endif
+        }
+
 
 #ifdef CONFIG_LITMUS_LOCKING
         get_srp_prio = psnedf_get_srp_prio;