GSN-EDF: add global OMLP support

Similar to the FMLP implementation, the
only difference is that it uses a hybrid FIFO/priority queue.

1 files changed, 308 insertions, 8 deletions

diff --git a/litmus/sched_gsn_edf.c b/litmus/sched_gsn_edf.c
index a0f3ba54ed8f..9e3eb22eed74 100644
--- a/litmus/sched_gsn_edf.c
+++ b/litmus/sched_gsn_edf.c
@@ -610,14 +610,14 @@ static long gsnedf_admit_task(struct task_struct* tsk)
 
 #include <litmus/fdso.h>
 
+
+
 /* called with IRQs off */
-static void set_priority_inheritance(struct task_struct* t, struct task_struct* prio_inh)
+static void __set_priority_inheritance(struct task_struct* t, struct task_struct* prio_inh)
 {
         int linked_on;
         int check_preempt = 0;
 
-        raw_spin_lock(&gsnedf_lock);
-
         TRACE_TASK(t, "inherits priority from %s/%d\n", prio_inh->comm, prio_inh->pid);
         tsk_rt(t)->inh_task = prio_inh;
 
@@ -642,7 +642,7 @@ static void set_priority_inheritance(struct task_struct* t, struct task_struct*
                         TRACE_TASK(t, "%s: is queued\n",
                                    __FUNCTION__);
                         /* We need to update the position of holder in some
-                         * heap. Note that this could be a release heap if we
+                         * heap. Note that this could be a release heap if
                          * budget enforcement is used and this job overran. */
                         check_preempt =
                                 !bheap_decrease(edf_ready_order,
@@ -673,15 +673,17 @@ static void set_priority_inheritance(struct task_struct* t, struct task_struct*
                         check_for_preemptions();
                 }
         }
-
-        raw_spin_unlock(&gsnedf_lock);
 }
 
-/* called with IRQs off */
-static void clear_priority_inheritance(struct task_struct* t)
+static void set_priority_inheritance(struct task_struct* t, struct task_struct* prio_inh)
 {
         raw_spin_lock(&gsnedf_lock);
+        __set_priority_inheritance(t, prio_inh);
+        raw_spin_unlock(&gsnedf_lock);
+}
 
+static void __clear_priority_inheritance(struct task_struct* t)
+{
         /* A job only stops inheriting a priority when it releases a
          * resource. Thus we can make the following assumption.*/
         BUG_ON(tsk_rt(t)->scheduled_on == NO_CPU);
@@ -693,6 +695,35 @@ static void clear_priority_inheritance(struct task_struct* t)
          * since the priority was effectively lowered. */
         unlink(t);
         gsnedf_job_arrival(t);
+}
+
+/* called with IRQs off */
+static void clear_priority_inheritance(struct task_struct* t)
+{
+        raw_spin_lock(&gsnedf_lock);
+        __clear_priority_inheritance(t);
+        raw_spin_unlock(&gsnedf_lock);
+}
+
+/* set and clear at the same time to avoid having to
+ * acquire the runqueue lock twice */
+static void update_priority_inheritance(
+        struct task_struct* deprived,
+        struct task_struct* blocker,
+        struct task_struct* blocked)
+{
+        /* things to do:
+         * 1) deprived no longer inherits anything.
+         * 2) blocker gets blocked's priority.
+         */
+
+        raw_spin_lock(&gsnedf_lock);
+
+        if (tsk_rt(deprived)->inh_task)
+                __clear_priority_inheritance(deprived);
+
+        if (blocked)
+                __set_priority_inheritance(blocker, blocked);
 
         raw_spin_unlock(&gsnedf_lock);
 }
@@ -898,6 +929,266 @@ static struct litmus_lock* gsnedf_new_fmlp(void)
         return &sem->litmus_lock;
 }
 
+
+/* ******************** OMLP support ********************** */
+
+/* struct for semaphore with priority inheritance */
+struct omlp_semaphore {
+        struct litmus_lock litmus_lock;
+
+        /* current resource holder */
+        struct task_struct *owner;
+
+        /* highest-priority waiter */
+        struct task_struct *hp_waiter;
+
+        /* FIFO queue of waiting tasks */
+        wait_queue_head_t fifo_wait;
+        /* Priority queue of waiting tasks */
+        wait_queue_head_t prio_wait;
+
+        /* How many slots remaining in FIFO queue? */
+        unsigned int num_free;
+};
+
+static inline struct omlp_semaphore* omlp_from_lock(struct litmus_lock* lock)
+{
+        return container_of(lock, struct omlp_semaphore, litmus_lock);
+}
+
+/* already locked */
+static void omlp_enqueue(struct omlp_semaphore *sem, prio_wait_queue_t* wait)
+{
+        if (sem->num_free) {
+                /* there is space in the FIFO queue */
+                sem->num_free--;
+                __add_wait_queue_tail_exclusive(&sem->fifo_wait, &wait->wq);
+        } else {
+                /* nope, gotta go to the priority queue */
+                __add_wait_queue_prio_exclusive(&sem->prio_wait, wait);
+        }
+}
+
+/* already locked */
+static int omlp_move(struct omlp_semaphore *sem)
+{
+        struct list_head* first;
+
+        if (waitqueue_active(&sem->prio_wait)) {
+                first = sem->prio_wait.task_list.next;
+                list_move_tail(first, &sem->fifo_wait.task_list);
+                return 1;
+        }
+        else
+                return 0;
+}
+
+static struct task_struct* omlp_dequeue(struct omlp_semaphore *sem)
+{
+        struct task_struct* first = __waitqueue_remove_first(&sem->fifo_wait);
+
+        if (first && !omlp_move(sem))
+                sem->num_free++;
+
+        return first;
+}
+
+/* caller is responsible for locking */
+static struct task_struct* omlp_find_hp_waiter(struct omlp_semaphore *sem,
+                                        struct task_struct* skip)
+{
+        struct list_head        *pos;
+        struct task_struct      *queued, *found = NULL;
+
+        /* check FIFO queue first */
+        list_for_each(pos, &sem->fifo_wait.task_list) {
+                queued  = (struct task_struct*) list_entry(pos, wait_queue_t,
+                                                           task_list)->private;
+
+                /* Compare task prios, find high prio task. */
+                if (queued != skip && edf_higher_prio(queued, found))
+                        found = queued;
+        }
+
+        /* check priority queue next */
+        if (waitqueue_active(&sem->prio_wait)) {
+                /* first has highest priority */
+                pos = sem->prio_wait.task_list.next;
+                queued  = (struct task_struct*) list_entry(pos, wait_queue_t,
+                                                           task_list)->private;
+                if (edf_higher_prio(queued, found))
+                        found = queued;
+        }
+
+        return found;
+}
+
+int gsnedf_omlp_lock(struct litmus_lock* l)
+{
+        struct task_struct* t = current;
+        struct omlp_semaphore *sem = omlp_from_lock(l);
+        prio_wait_queue_t wait;
+        unsigned long flags;
+
+        if (!is_realtime(t))
+                return -EPERM;
+
+        spin_lock_irqsave(&sem->fifo_wait.lock, flags);
+
+        if (sem->owner) {
+                /* resource is not free => must suspend and wait */
+
+                init_prio_waitqueue_entry(&wait, t, get_deadline(t));
+
+                set_task_state(t, TASK_UNINTERRUPTIBLE);
+
+                omlp_enqueue(sem, &wait);
+
+                /* check if we need to activate priority inheritance */
+                if (edf_higher_prio(t, sem->hp_waiter)) {
+                        sem->hp_waiter = t;
+                        if (edf_higher_prio(t, sem->owner))
+                                set_priority_inheritance(sem->owner, sem->hp_waiter);
+                }
+
+                TS_LOCK_SUSPEND;
+
+                /* release lock before sleeping */
+                spin_unlock_irqrestore(&sem->fifo_wait.lock, flags);
+
+                schedule();
+
+                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->fifo_wait.lock, flags);
+        }
+
+        return 0;
+}
+
+static int gsnedf_omlp_unlock(struct litmus_lock* l)
+{
+        struct task_struct *t = current, *next, *blocked = NULL;
+        struct omlp_semaphore *sem = omlp_from_lock(l);
+        unsigned long flags;
+        int err = 0;
+
+        spin_lock_irqsave(&sem->fifo_wait.lock, flags);
+
+        if (sem->owner != t) {
+                err = -EINVAL;
+                goto out;
+        }
+
+        /* check if there are jobs waiting for this resource */
+        next = omlp_dequeue(sem);
+        if (next) {
+                /* next becomes the resouce holder */
+                sem->owner = next;
+                TRACE_CUR("lock ownership passed to %s/%d\n", next->comm, next->pid);
+
+                /* determine new hp_waiter if necessary */
+                if (next == sem->hp_waiter) {
+                        TRACE_TASK(next, "was highest-prio waiter\n");
+                        /* next has the highest priority --- it doesn't need to
+                         * inherit.  However, we need to make sure that the
+                         * next-highest priority in the queue is reflected in
+                         * hp_waiter. */
+                        sem->hp_waiter = omlp_find_hp_waiter(sem, next);
+                        if (sem->hp_waiter)
+                                TRACE_TASK(sem->hp_waiter, "is new highest-prio waiter\n");
+                        else
+                                TRACE("no further waiters\n");
+                } else {
+                        /* Well, if next is not the highest-priority waiter,
+                         * then it ought to inherit the highest-priority
+                         * waiter's priority. */
+                        blocked = sem->hp_waiter;
+                }
+
+                /* wake up next */
+                wake_up_process(next);
+        } else
+                /* becomes available */
+                sem->owner = NULL;
+
+        /* we lose the benefit of priority inheritance (if any) */
+        if (tsk_rt(t)->inh_task || blocked)
+                update_priority_inheritance(t, next, blocked);
+
+out:
+        spin_unlock_irqrestore(&sem->fifo_wait.lock, flags);
+
+        return err;
+}
+
+static int gsnedf_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->fifo_wait.lock, flags);
+
+        owner = sem->owner == t;
+
+        spin_unlock_irqrestore(&sem->fifo_wait.lock, flags);
+
+        if (owner)
+                gsnedf_omlp_unlock(l);
+
+        return 0;
+}
+
+static void gsnedf_omlp_free(struct litmus_lock* lock)
+{
+        kfree(omlp_from_lock(lock));
+}
+
+static struct litmus_lock_ops gsnedf_omlp_lock_ops = {
+        .close  = gsnedf_omlp_close,
+        .lock   = gsnedf_omlp_lock,
+        .unlock = gsnedf_omlp_unlock,
+        .deallocate = gsnedf_omlp_free,
+};
+
+static struct litmus_lock* gsnedf_new_omlp(void)
+{
+        struct omlp_semaphore* sem;
+
+        sem = kmalloc(sizeof(*sem), GFP_KERNEL);
+        if (!sem)
+                return NULL;
+
+        sem->owner   = NULL;
+        sem->hp_waiter = NULL;
+        init_waitqueue_head(&sem->fifo_wait);
+        init_waitqueue_head(&sem->prio_wait);
+        sem->litmus_lock.ops = &gsnedf_omlp_lock_ops;
+        /* free = cpus -1 since ->owner is the head and also counted */
+        sem->num_free = num_online_cpus() - 1;
+
+#ifdef CONFIG_RELEASE_MASTER
+        /* If we use dedicated interrupt handling, then there are actually
+         * only m - 1 CPUs around. */
+        if (gsnedf.release_master != NO_CPU)
+                sem->num_free -= 1;
+#endif
+
+        return &sem->litmus_lock;
+}
+
+
 /* **** lock constructor **** */
 
 
@@ -918,6 +1209,15 @@ static long gsnedf_allocate_lock(struct litmus_lock **lock, int type,
                         err = -ENOMEM;
                 break;
 
+        case OMLP_SEM:
+                /* O(m) Multiprocessor Locking Protocol */
+                *lock  = gsnedf_new_omlp();
+                if (*lock)
+                        err = 0;
+                else
+                        err = -ENOMEM;
+                break;
+
         };
 
         return err;