1 files changed, 384 insertions, 6 deletions

diff --git a/litmus/sched_gsn_edf.c b/litmus/sched_gsn_edf.c
index b76e46372c6a..d4635c74df1c 100644
--- a/litmus/sched_gsn_edf.c
+++ b/litmus/sched_gsn_edf.c
@@ -14,6 +14,7 @@
 #include <linux/sched/signal.h>
 #include <linux/sched/topology.h>
 #include <linux/slab.h>
+#include <linux/sched/signal.h>
 
 #include <litmus/debug_trace.h>
 #include <litmus/litmus.h>
@@ -22,6 +23,7 @@
 #include <litmus/edf_common.h>
 #include <litmus/sched_trace.h>
 #include <litmus/trace.h>
+#include <litmus/wait.h>
 
 #include <litmus/preempt.h>
 #include <litmus/budget.h>
@@ -757,6 +759,9 @@ struct fmlp_semaphore {
 
         /* FIFO queue of waiting tasks */
         wait_queue_head_t wait;
+
+        struct hrtimer budgeting_timer;
+        lt_t enforce_time;
 };
 
 static inline struct fmlp_semaphore* fmlp_from_lock(struct litmus_lock* lock)
@@ -764,6 +769,27 @@ static inline struct fmlp_semaphore* fmlp_from_lock(struct litmus_lock* lock)
         return container_of(lock, struct fmlp_semaphore, litmus_lock);
 }
 
+static enum hrtimer_restart bfmlp_budget_enforce(struct hrtimer *timer)
+{
+        struct fmlp_semaphore* sem =
+                container_of(timer, struct fmlp_semaphore, budgeting_timer);
+        struct task_struct* t = sem->owner;
+
+
+        if (t == current)
+                send_sig(31, t, 0);
+        /* up to the task to:
+         *      -detect if CS completed
+         *      -perform fix_state if needed
+         *      -unlock
+         *      -set job to preemptive again
+         *      -decide what to do next
+         */
+        TS_TIMER_LATENCY(sem->enforce_time);
+
+        return HRTIMER_NORESTART;
+}
+
 /* caller is responsible for locking */
 struct task_struct* find_hp_waiter(struct fmlp_semaphore *sem,
                                    struct task_struct* skip)
@@ -903,6 +929,25 @@ out:
         return err;
 }
 
+int gsnedf_fmlp_tstart(struct litmus_lock* l, lt_t budget)
+{
+        struct fmlp_semaphore* sem = fmlp_from_lock(l);
+
+        sem->enforce_time = litmus_clock() + budget;
+        hrtimer_start(&sem->budgeting_timer,
+                ns_to_ktime(sem->enforce_time),
+                HRTIMER_MODE_ABS_PINNED_HARD);
+        return 0;
+}
+
+int gsnedf_fmlp_tstop(struct litmus_lock* l)
+{
+        struct fmlp_semaphore* sem = fmlp_from_lock(l);
+
+        hrtimer_cancel(&sem->budgeting_timer);
+        return 0;
+}
+
 int gsnedf_fmlp_close(struct litmus_lock* l)
 {
         struct task_struct *t = current;
@@ -929,10 +974,12 @@ void gsnedf_fmlp_free(struct litmus_lock* lock)
 }
 
 static struct litmus_lock_ops gsnedf_fmlp_lock_ops = {
-        .close  = gsnedf_fmlp_close,
-        .lock   = gsnedf_fmlp_lock,
-        .unlock = gsnedf_fmlp_unlock,
-        .deallocate = gsnedf_fmlp_free,
+        .close                  = gsnedf_fmlp_close,
+        .lock                   = gsnedf_fmlp_lock,
+        .unlock                 = gsnedf_fmlp_unlock,
+        .timer_start    = gsnedf_fmlp_tstart,
+        .timer_stop             = gsnedf_fmlp_tstop,
+        .deallocate     = gsnedf_fmlp_free,
 };
 
 static struct litmus_lock* gsnedf_new_fmlp(void)
@@ -947,6 +994,331 @@ static struct litmus_lock* gsnedf_new_fmlp(void)
         sem->hp_waiter = NULL;
         init_waitqueue_head(&sem->wait);
         sem->litmus_lock.ops = &gsnedf_fmlp_lock_ops;
+        hrtimer_init(&sem->budgeting_timer, CLOCK_MONOTONIC, HRTIMER_MODE_ABS_PINNED_HARD);
+        sem->budgeting_timer.function = bfmlp_budget_enforce;
+
+        return &sem->litmus_lock;
+}
+
+/* ****************************** B-OMLP support ************************** */
+
+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;
+        /* Prio queue of waiting tasks */
+        wait_queue_head_t prio_wait;
+
+        /* How many slots remaining in FIFO queue? */
+        unsigned int num_free;
+
+        /* budgeting support */
+        struct hrtimer budgeting_timer;
+        lt_t enforce_time;
+};
+
+static inline struct omlp_semaphore* omlp_from_lock(struct litmus_lock* lock)
+{
+        return container_of(lock, struct omlp_semaphore, litmus_lock);
+}
+
+static enum hrtimer_restart bomlp_budget_enforce(struct hrtimer *timer)
+{
+        struct omlp_semaphore* sem =
+                container_of(timer, struct omlp_semaphore, budgeting_timer);
+        struct task_struct* t = sem->owner;
+
+        if (t == current)
+                send_sig(31, t, 0);
+        /* up to the task to:
+         *      -detect if CS completed
+         *      -perform fix_state if needed
+         *      -unlock
+         *      -set job to preemptive again
+         *      -decide what to do next
+         */
+        TS_TIMER_LATENCY(sem->enforce_time);
+
+        return HRTIMER_NORESTART;
+}
+
+/* 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.head) {
+                queued = (struct task_struct*) list_entry(pos, wait_queue_entry_t,
+                                                                entry)->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.head.next;
+                queued = (struct task_struct*) list_entry(pos, wait_queue_entry_t,
+                                                                entry)->private;
+                if (edf_higher_prio(queued, found))
+                        found = queued;
+        }
+
+        return found;
+}
+
+/* already locked */
+static void omlp_enqueue(struct omlp_semaphore* sem, prio_wait_queue_t* wait)
+{
+        if (sem->num_free > 0) {
+                /* there is space in the FIFO queue */
+                sem->num_free--;
+                __add_wait_queue_entry_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.head.next;
+                list_move_tail(first, &sem->fifo_wait.head);
+                return 1;
+        }
+        return 0;
+}
+
+/* already locked */
+static struct task_struct* omlp_dequeue(struct omlp_semaphore* sem)
+{
+        struct task_struct* first = __waitqueue_remove_first(&sem->fifo_wait);
+
+        /* don't replace tmp with omlp_move! shortcircuiting will break omlp for m=1 */
+        int tmp = omlp_move(sem);
+        if (first && !tmp)
+                sem->num_free++;
+        if (!first && tmp)
+                first = __waitqueue_remove_first(&sem->fifo_wait);
+        return first;
+}
+
+int gsnedf_omlp_budgeted_lock(struct litmus_lock* l, lt_t fz_len)
+{
+        struct task_struct* t = current;
+        struct omlp_semaphore* sem = omlp_from_lock(l);
+        unsigned long flags;
+        lt_t budget_used;
+        lt_t budget_remaining;
+        prio_wait_queue_t pwq;
+        
+        if (!is_realtime(t))
+                return -EPERM;
+
+        /* prevent nested lock acquisition -- not supported by global OMLP by default */
+        if (tsk_rt(t)->num_locks_held)
+                return -EBUSY;
+
+        spin_lock_irqsave(&sem->fifo_wait.lock, flags);
+
+        if (sem->owner) {
+                /* resource is not free => must suspend and wait */
+                litmus_current_budget(&budget_used, &budget_remaining);
+                if (fz_len < budget_remaining) {
+                        /* Not enough budget for the CS => deny forbidden zone access */
+                        TRACE_CUR("failed forbidden zone check, %llu / %llu budget needed\n",
+                                budget_remaining, fz_len);
+                        spin_unlock_irqrestore(&sem->fifo_wait.lock, flags);
+                        return -EACCES;
+                }
+
+                init_prio_waitqueue_entry(&pwq, t, get_deadline(t));
+
+                omlp_enqueue(sem, &pwq);
+
+                /* check if we need to activate priority inheritance */
+                if (edf_higher_prio(t, sem->hp_waiter)) {
+                        sem->hp_waiter = t;
+                        if (edf_higher_prio(sem->hp_waiter, sem->owner))
+                                set_priority_inheritance(sem->owner, sem->hp_waiter);
+                }
+
+                set_current_state(TASK_UNINTERRUPTIBLE);
+
+                TS_LOCK_SUSPEND;
+
+                /* release lock before sleeping */
+                spin_unlock_irqrestore(&sem->fifo_wait.lock, flags);
+
+                schedule();
+
+                TS_LOCK_RESUME;
+        } else {
+                /* we now have lock */
+                sem->owner = t;
+                spin_unlock_irqrestore(&sem->fifo_wait.lock, flags);
+        }
+
+        make_np(t);
+        tsk_rt(t)->num_locks_held++;
+
+        return 0;
+}
+
+int gsnedf_omlp_lock(struct litmus_lock* l)
+{
+        return gsnedf_omlp_budgeted_lock(l, ULLONG_MAX);
+}
+
+int gsnedf_omlp_unlock(struct litmus_lock* l)
+{
+        struct task_struct* t = current;
+        struct omlp_semaphore* sem = omlp_from_lock(l);
+        struct task_struct* next;
+        unsigned long flags;
+
+        if (sem->owner != t)
+                return -EINVAL;
+
+        hrtimer_cancel(&sem->budgeting_timer);
+
+        spin_lock_irqsave(&sem->fifo_wait.lock, flags);
+
+        tsk_rt(t)->num_locks_held--;
+
+        next = omlp_dequeue(sem);
+        /* check if there are jobs waiting for this resource */
+        if (next) {
+                /* next becomes the resource holder */
+                sem->owner = next;
+                TRACE_CUR("lock ownership passed to %s/%d\n", next->comm, next->pid);
+
+                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. */
+                        set_priority_inheritance(next, sem->hp_waiter);
+                }
+
+                /* wake up next */
+                wake_up_process(next);
+        } else {
+                /* become available */
+                sem->owner = NULL;
+        }
+
+        /* we make ourself preemptive again and lose priority inheritance (if any) */
+        take_np(t);
+        clear_priority_inheritance(t);
+
+        spin_unlock_irqrestore(&sem->fifo_wait.lock, flags);
+
+        return 0;
+}
+
+int gsnedf_omlp_tstart(struct litmus_lock* l, lt_t budget)
+{
+        struct omlp_semaphore* sem = omlp_from_lock(l);
+
+        sem->enforce_time = litmus_clock() + budget;
+        hrtimer_start(&sem->budgeting_timer,
+                ns_to_ktime(sem->enforce_time),
+                HRTIMER_MODE_ABS_PINNED_HARD);
+        return 0;
+}
+
+int gsnedf_omlp_tstop(struct litmus_lock* l)
+{
+        struct omlp_semaphore* sem = omlp_from_lock(l);
+
+        hrtimer_cancel(&sem->budgeting_timer);
+        return 0;
+}
+
+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;
+}
+
+void gsnedf_omlp_free(struct litmus_lock* l)
+{
+        kfree(omlp_from_lock(l));
+}
+
+static struct litmus_lock_ops gsnedf_omlp_lock_ops = {
+        .close                          = gsnedf_omlp_close,
+        .lock                           = gsnedf_omlp_lock,
+        .budgeted_lock          = gsnedf_omlp_budgeted_lock,
+        .unlock                         = gsnedf_omlp_unlock,
+        .timer_start            = gsnedf_omlp_tstart,
+        .timer_stop                     = gsnedf_omlp_tstop,
+        .deallocate                     = gsnedf_omlp_free,
+};
+
+static struct litmus_lock* gsnedf_new_omlp(void)
+{
+        struct omlp_semaphore* sem;
+        int release_master =
+#ifdef CONFIG_RELEASE_MASTER
+                        atomic_read(&release_master_cpu);
+#else
+                NO_CPU;
+#endif
+        int num_rt_cpus = num_online_cpus() - (release_master != NO_CPU);
+        
+        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;
+        sem->num_free = num_rt_cpus;
+        hrtimer_init(&sem->budgeting_timer, CLOCK_MONOTONIC, HRTIMER_MODE_ABS_PINNED_HARD);
+        sem->budgeting_timer.function = bomlp_budget_enforce;
 
         return &sem->litmus_lock;
 }
@@ -970,7 +1342,13 @@ static long gsnedf_allocate_lock(struct litmus_lock **lock, int type,
                 else
                         err = -ENOMEM;
                 break;
-
+        case OMLP_SEM:
+                /* Optimal Multiprocessor Locking Protocol */
+                *lock = gsnedf_new_omlp();
+                if (*lock)
+                        err = 0;
+                else
+                        err = -ENOMEM;
         };
 
         return err;
@@ -1057,7 +1435,7 @@ static long gsnedf_deactivate_plugin(void)
 
 /*      Plugin object   */
 static struct sched_plugin gsn_edf_plugin __cacheline_aligned_in_smp = {
-        .plugin_name            = "GSN-EDF",
+        .plugin_name            = "GSN-EDF-BUDGETED",
         .finish_switch          = gsnedf_finish_switch,
         .task_new               = gsnedf_task_new,
         .complete_job           = complete_job,