rt_domain: make release queue handling more efficient

Instead of having hrtimers for each task, we now have only
one hrtimer per rt_domain. To-be-released tasks are grouped in
mergable heaps and presented as a bunch on each release.

This approach should allow us to reduce the worst-case overhead
at hyperperiod boundaries significantly.

	1) less hrtimer overhead
	2) less calls to the active plugin
	3) only one CPU handles releases at a time
	4) (2) & (3) should bring down lock contention significantly

11 files changed, 355 insertions, 127 deletions

diff --git a/include/litmus/edf_common.h b/include/litmus/edf_common.h
index 4dff77ae48..32dcf9bd6b 100644
--- a/include/litmus/edf_common.h
+++ b/include/litmus/edf_common.h
@@ -12,8 +12,8 @@
 #include <litmus/rt_domain.h>
 
 
-void edf_domain_init(rt_domain_t* rt, check_resched_needed_t resched, 
-                     release_job_t release);
+void edf_domain_init(rt_domain_t* rt, check_resched_needed_t resched,
+                     release_jobs_t release);
 
 int edf_higher_prio(struct task_struct* first,
                     struct task_struct* second);
diff --git a/include/litmus/heap.h b/include/litmus/heap.h
index 0b0ede4542..508e0b9f16 100644
--- a/include/litmus/heap.h
+++ b/include/litmus/heap.h
@@ -298,4 +298,38 @@ static inline void heap_delete(heap_prio_t higher_prio, struct heap* heap,
         node->degree = NOT_IN_HEAP;
 }
 
+/* un-inline, make it a kmemcache_t */
+static inline struct heap_node* alloc_heap_node(int gfp_flags)
+{
+        return kmalloc(sizeof(struct heap_node), gfp_flags);
+}
+
+static inline void free_heap_node(struct heap_node* hn)
+{
+        kfree(hn);
+}
+
+/* allocate a heap node for value and insert into the heap */
+static inline int heap_add(heap_prio_t higher_prio, struct heap* heap,
+                            void* value, int gfp_flags)
+{
+        struct heap_node* hn = alloc_heap_node(gfp_flags);
+        if (likely(hn)) {
+                heap_node_init(&hn, value);
+                heap_insert(higher_prio, heap, hn);
+        }
+        return hn != NULL;
+}
+
+static inline void* heap_take_del(heap_prio_t higher_prio,
+                                  struct heap* heap)
+{
+        struct heap_node* hn = heap_take(higher_prio, heap);
+        void* ret = NULL;
+        if (hn) {
+                ret = hn->value;
+                free_heap_node(hn);
+        }
+        return ret;
+}
 #endif
diff --git a/include/litmus/litmus.h b/include/litmus/litmus.h
index de2a3c2547..d3cd6e4437 100644
--- a/include/litmus/litmus.h
+++ b/include/litmus/litmus.h
@@ -141,10 +141,6 @@ static inline lt_t litmus_clock(void)
 /* A macro to convert from nanoseconds to ktime_t. */
 #define ns_to_ktime(t)          ktime_add_ns(ktime_set(0, 0), t)
 
-/* The high-resolution release timer for a task. */
-#define release_timer(t) (tsk_rt(t)->release_timer)
-
-/* The high-resolution release timer for a task. */
 #define get_domain(t) (tsk_rt(t)->domain)
 
 /* Honor the flag in the preempt_count variable that is set
@@ -201,5 +197,27 @@ static inline int is_np(struct task_struct *t)
 
 #endif
 
+/* make the unit explicit */
+typedef unsigned long quanta_t;
+
+enum round {
+        FLOOR,
+        CEIL
+};
+
+
+/* Tick period is used to convert ns-specified execution
+ * costs and periods into tick-based equivalents.
+ */
+extern ktime_t tick_period;
+
+static inline quanta_t time2quanta(lt_t time, enum round round)
+{
+        s64  quantum_length = ktime_to_ns(tick_period);
+
+        if (do_div(time, quantum_length) && round == CEIL)
+                time++;
+        return (quanta_t) time;
+}
 
 #endif
diff --git a/include/litmus/rt_domain.h b/include/litmus/rt_domain.h
index 47cd123b76..84d71d40d9 100644
--- a/include/litmus/rt_domain.h
+++ b/include/litmus/rt_domain.h
@@ -8,13 +8,36 @@
 #include <litmus/norqlock.h>
 #include <litmus/heap.h>
 
+#define RELEASE_QUEUE_SLOTS 127 /* prime */
+
 struct _rt_domain;
 
 typedef int (*check_resched_needed_t)(struct _rt_domain *rt);
-typedef void (*release_job_t)(struct task_struct *t, struct _rt_domain *rt);
+typedef void (*release_jobs_t)(struct _rt_domain *rt, struct heap* tasks);
+
+int heap_earlier_release(struct heap_node *_a, struct heap_node *_b);
+
+struct release_heap {
+        struct list_head                list;
+        lt_t                            release_time;
+        struct heap                     heap;
+};
+
+struct release_queue {
+        /* each slot maintains a list of release heaps sorted by release time */
+        struct list_head                slot[RELEASE_QUEUE_SLOTS];
+        /* the heap of heaps orderd by release time */
+        struct heap                     rel_heap;
+        /* the actual timer used to trigger releases */
+        struct hrtimer                  timer;
+        /* used to determine when to start the timer */
+        int                             timer_armed;
+        /* when will it go off? */
+        lt_t                            timer_time;
+};
 
 typedef struct _rt_domain {
-        struct no_rqlock_work           arm_timers;
+        struct no_rqlock_work           arm_timer;
 
         /* runnable rt tasks are in here */
         spinlock_t                      ready_lock;
@@ -22,18 +45,32 @@ typedef struct _rt_domain {
 
         /* real-time tasks waiting for release are in here */
         spinlock_t                      release_lock;
-        struct list_head                release_queue;
+        struct release_queue            release_queue;
+
+        /* for moving tasks to the release queue */
+        spinlock_t                      tobe_lock;
+        struct list_head                tobe_released;
 
         /* how do we check if we need to kick another CPU? */
         check_resched_needed_t          check_resched;
 
         /* how do we release a job? */
-        release_job_t                   release_job;
+        release_jobs_t                  release_jobs;
 
         /* how are tasks ordered in the ready queue? */
         heap_prio_t                     order;
 } rt_domain_t;
 
+/* caller must hold release_lock */
+static inline int next_release(rt_domain_t *rt, lt_t *time)
+{
+        struct heap_node* top = heap_peek(heap_earlier_release,
+                                          &rt->release_queue.rel_heap);
+        if (top)
+                *time = ((struct release_heap*) top->value)->release_time;
+        return top != NULL;
+}
+
 static inline struct task_struct* __next_ready(rt_domain_t* rt)
 {
         struct heap_node *hn = heap_peek(rt->order, &rt->ready_queue);
@@ -45,9 +82,10 @@ static inline struct task_struct* __next_ready(rt_domain_t* rt)
 
 void rt_domain_init(rt_domain_t *rt, heap_prio_t order,
                     check_resched_needed_t check,
-                    release_job_t relase);
+                    release_jobs_t relase);
 
 void __add_ready(rt_domain_t* rt, struct task_struct *new);
+void __merge_ready(rt_domain_t* rt, struct heap *tasks);
 void __add_release(rt_domain_t* rt, struct task_struct *task);
 
 static inline struct task_struct* __take_ready(rt_domain_t* rt)
@@ -87,6 +125,14 @@ static inline void add_ready(rt_domain_t* rt, struct task_struct *new)
         spin_unlock_irqrestore(&rt->ready_lock, flags);
 }
 
+static inline void merge_ready(rt_domain_t* rt, struct heap* tasks)
+{
+        unsigned long flags;
+        spin_lock_irqsave(&rt->ready_lock, flags);
+        __merge_ready(rt, tasks);
+        spin_unlock_irqrestore(&rt->ready_lock, flags);
+}
+
 static inline struct task_struct* take_ready(rt_domain_t* rt)
 {
         unsigned long flags;
@@ -103,9 +149,9 @@ static inline void add_release(rt_domain_t* rt, struct task_struct *task)
 {
         unsigned long flags;
         /* first we need the write lock for rt_ready_queue */
-        spin_lock_irqsave(&rt->release_lock, flags);
+        spin_lock_irqsave(&rt->tobe_lock, flags);
         __add_release(rt, task);
-        spin_unlock_irqrestore(&rt->release_lock, flags);
+        spin_unlock_irqrestore(&rt->tobe_lock, flags);
 }
 
 static inline int __jobs_pending(rt_domain_t* rt)
diff --git a/include/litmus/rt_param.h b/include/litmus/rt_param.h
index 7bb568432e..403ebc8cc9 100644
--- a/include/litmus/rt_param.h
+++ b/include/litmus/rt_param.h
@@ -137,9 +137,6 @@ struct rt_param {
         int old_policy;
         int old_prio;
 
-        /* The high-resolution timer used to control its release. */
-        struct hrtimer release_timer;
-
         /* ready queue for this task */
         struct _rt_domain* domain;
 
diff --git a/litmus/edf_common.c b/litmus/edf_common.c
index d7567ac98e..253641de4f 100644
--- a/litmus/edf_common.c
+++ b/litmus/edf_common.c
@@ -66,7 +66,7 @@ int edf_ready_order(struct heap_node* a, struct heap_node* b)
 }
 
 void edf_domain_init(rt_domain_t* rt, check_resched_needed_t resched,
-                      release_job_t release)
+                      release_jobs_t release)
 {
         rt_domain_init(rt,  edf_ready_order, resched, release);
 }
diff --git a/litmus/rt_domain.c b/litmus/rt_domain.c
index 28803087b3..27bc9143e7 100644
--- a/litmus/rt_domain.c
+++ b/litmus/rt_domain.c
@@ -18,6 +18,8 @@
 
 #include <litmus/trace.h>
 
+#include <litmus/heap.h>
+
 static int dummy_resched(rt_domain_t *rt)
 {
         return 0;
@@ -29,89 +31,228 @@ static int dummy_order(struct heap_node* a, struct heap_node* b)
 }
 
 /* default implementation: use default lock */
-static void default_release_job(struct task_struct* t, rt_domain_t* rt)
+static void default_release_jobs(rt_domain_t* rt, struct heap* tasks)
+{
+        merge_ready(rt, tasks);
+}
+
+static unsigned int time2slot(lt_t time)
+{
+        return (unsigned int) time2quanta(time, FLOOR) % RELEASE_QUEUE_SLOTS;
+}
+
+int heap_earlier_release(struct heap_node *_a, struct heap_node *_b)
 {
-        add_ready(rt, t);
+        struct release_heap *a = _a->value;
+        struct release_heap *b = _b->value;
+        return lt_before(a->release_time, b->release_time);
 }
 
-static enum hrtimer_restart release_job_timer(struct hrtimer *timer)
+/* Caller most hold release lock.
+ * Will return heap for given time. If no such heap exists prior to the invocation
+ * it will be created.
+ */
+static struct release_heap* get_release_heap(rt_domain_t *rt, lt_t release_time)
 {
-        struct task_struct *t;
+        struct list_head* pos;
+        struct release_heap* heap = NULL;
+        struct release_heap* rh;
+        unsigned int slot = time2slot(release_time);
+        int inserted;
+
+        /* initialize pos for the case that the list is empty */
+        pos = rt->release_queue.slot[slot].next;
+        list_for_each(pos, &rt->release_queue.slot[slot]) {
+                rh = list_entry(pos, struct release_heap, list);
+                if (release_time == rh->release_time) {
+                        /* perfect match -- this happens on hyperperiod
+                         * boundaries
+                         */
+                        heap = rh;
+                        break;
+                } else if (lt_before(release_time, rh->release_time)) {
+                        /* we need to insert a new node since rh is
+                         * already in the future
+                         */
+                        break;
+                }
+        }
+        if (!heap) {
+                /* must create new node */
+                /* FIXME: use a kmemcache_t */
+                rh = kmalloc(sizeof(struct release_heap), GFP_ATOMIC);
+                if (unlikely(!rh))
+                        /* Should be handled somehow.
+                         * For now, let's just hope there is
+                         * sufficient memory.
+                         */
+                        panic("rt_domain: no more memory?");
+                rh->release_time = release_time;
+                heap_init(&rh->heap);
+                list_add(&rh->list, pos->prev);
+                inserted = heap_add(heap_earlier_release,
+                                    &rt->release_queue.rel_heap, rh,
+                                    GFP_ATOMIC);
+                if (unlikely(!inserted))
+                        panic("rt_domain: no more heap memory?");
+                heap = rh;
+        }
+        return heap;
+}
+
+static enum hrtimer_restart on_release_timer(struct hrtimer *timer)
+{
+        long flags;
+        rt_domain_t *rt;
+        struct release_heap* rh;
+        struct heap tasks;
+        struct list_head list, *pos, *safe;
+        lt_t release = 109;
+        int pending;
+        int repeat;
+        enum hrtimer_mode ret = HRTIMER_NORESTART;
 
         TS_RELEASE_START;
 
-        t = container_of(timer, struct task_struct, 
-                         rt_param.release_timer);
+        INIT_LIST_HEAD(&list);
+        heap_init(&tasks);
 
-        get_domain(t)->release_job(t, get_domain(t));
+        rt = container_of(timer, rt_domain_t,
+                         release_queue.timer);
 
-        TS_RELEASE_END;
+        do {
+                list_for_each_safe(pos, safe, &list) {
+                        rh = list_entry(pos, struct release_heap, list);
+                        heap_union(rt->order, &tasks, &rh->heap);
+                        list_del(pos);
+                        kfree(rh);
+                }
 
-        return HRTIMER_NORESTART;
-}
+                /* call release callback */
+                rt->release_jobs(rt, &tasks);
 
-static void setup_job_release_timer(struct task_struct *task)
-{
-        hrtimer_init(&release_timer(task), CLOCK_MONOTONIC, HRTIMER_MODE_ABS);
-        release_timer(task).function = release_job_timer;
-#ifdef CONFIG_HIGH_RES_TIMERS
-        release_timer(task).cb_mode = HRTIMER_CB_IRQSAFE_NO_RESTART;
-#endif
-        /* Expiration time of timer is release time of task. */
-        release_timer(task).expires = ns_to_ktime(get_release(task));
 
-        TRACE_TASK(task, "arming release timer rel=%llu at %llu\n",
-                   get_release(task), litmus_clock());
+                spin_lock_irqsave(&rt->release_lock, flags);
+                while ((pending = next_release(rt, &release))) {
+                        if (lt_before(release, litmus_clock())) {
+                                /* pick for release */
+                                rh = heap_take_del(heap_earlier_release,
+                                                   &rt->release_queue.rel_heap);
+                                list_move(&rh->list, &list);
+                        } else
+                                break;
+                }
+                repeat = !list_empty(&list);
+                if (!repeat) {
+                        /* last iteration, setup timers, etc. */
+                        if (!pending) {
+                                rt->release_queue.timer_armed = 0;
+                                ret = HRTIMER_NORESTART;
+                        } else {
+                                rt->release_queue.timer_time = release;
+                                timer->expires = ns_to_ktime(release);
+                                ret = HRTIMER_RESTART;
+                        }
+                }
+                spin_unlock_irqrestore(&rt->release_lock, flags);
+        } while (repeat);
 
-        hrtimer_start(&release_timer(task), release_timer(task).expires,
-                      HRTIMER_MODE_ABS);
+        TS_RELEASE_END;
+
+        return ret;
 }
 
-static void arm_release_timers(unsigned long _rt)
+static void arm_release_timer(unsigned long _rt)
 {
         rt_domain_t *rt = (rt_domain_t*) _rt;
         unsigned long flags;
-        struct list_head alt;
+        struct list_head list;
         struct list_head *pos, *safe;
         struct task_struct* t;
+        struct release_heap* rh;
+        int earlier, armed;
+        lt_t release = 0;
+
+        local_irq_save(flags);
+        spin_lock(&rt->tobe_lock);
+        list_replace_init(&rt->tobe_released, &list);
+        spin_unlock(&rt->tobe_lock);
 
-        spin_lock_irqsave(&rt->release_lock, flags);
-        list_replace_init(&rt->release_queue, &alt);
-        spin_unlock_irqrestore(&rt->release_lock, flags);
-        
-        list_for_each_safe(pos, safe, &alt) {
+        /* We only have to defend against the ISR since norq callbacks
+         * are serialized.
+         */
+        spin_lock(&rt->release_lock);
+
+        list_for_each_safe(pos, safe, &list) {
                 t = list_entry(pos, struct task_struct, rt_param.list);
                 list_del(pos);
-                setup_job_release_timer(t);
+                rh = get_release_heap(rt, get_release(t));
+                heap_add(rt->order, &rh->heap, t, GFP_ATOMIC);
         }
-}
 
+        next_release(rt, &release);
+        armed   = rt->release_queue.timer_armed;
+        earlier = lt_before(release, rt->release_queue.timer_time);
+        /* We'll do the actual arming in a sec. The ISR doesn't care what these
+         * flags say, and it'll be true before another instance of this
+         * function can observe the flag due to the sequential nature of norq
+         * work.
+         */
+        rt->release_queue.timer_armed = 1;
+        rt->release_queue.timer_time  = release;
+        spin_unlock(&rt->release_lock);
+        if (!armed || earlier) {
+                if (armed) {
+                        /* need to cancel first */
+                        hrtimer_cancel(&rt->release_queue.timer);
+                }
+                hrtimer_start(&rt->release_queue.timer,
+                              ns_to_ktime(release),
+                              HRTIMER_MODE_ABS);
+        }
+        local_irq_restore(flags);
+}
 
 void rt_domain_init(rt_domain_t *rt,
                     heap_prio_t order,
                     check_resched_needed_t check,
-                    release_job_t release
+                    release_jobs_t release
                    )
 {
+        int i;
+
         BUG_ON(!rt);
         if (!check)
                 check = dummy_resched;
         if (!release)
-                release = default_release_job;
+                release = default_release_jobs;
         if (!order)
                 order = dummy_order;
+
         heap_init(&rt->ready_queue);
-        INIT_LIST_HEAD(&rt->release_queue);
+        INIT_LIST_HEAD(&rt->tobe_released);
+        rt->release_queue.timer_armed = 0;
+        for (i = 0; i < RELEASE_QUEUE_SLOTS; i++)
+                INIT_LIST_HEAD(&rt->release_queue.slot[i]);
+
+        hrtimer_init(&rt->release_queue.timer, CLOCK_MONOTONIC, HRTIMER_MODE_ABS);
+        rt->release_queue.timer.function = on_release_timer;
+#ifdef CONFIG_HIGH_RES_TIMERS
+        rt->release_queue.timer.cb_mode = HRTIMER_CB_IRQSAFE;
+#endif
+
         spin_lock_init(&rt->ready_lock);
         spin_lock_init(&rt->release_lock);
+        spin_lock_init(&rt->tobe_lock);
+
         rt->check_resched       = check;
-        rt->release_job         = release;
+        rt->release_jobs        = release;
         rt->order               = order;
-        init_no_rqlock_work(&rt->arm_timers, arm_release_timers, (unsigned long) rt);
+        init_no_rqlock_work(&rt->arm_timer, arm_release_timer, (unsigned long) rt);
 }
 
 /* add_ready - add a real-time task to the rt ready queue. It must be runnable.
- * @new:      the newly released task
+ * @new:       the newly released task
  */
 void __add_ready(rt_domain_t* rt, struct task_struct *new)
 {
@@ -125,14 +266,23 @@ void __add_ready(rt_domain_t* rt, struct task_struct *new)
         rt->check_resched(rt);
 }
 
+/* merge_ready - Add a sorted set of tasks to the rt ready queue. They must be runnable.
+ * @tasks      - the newly released tasks
+ */
+void __merge_ready(rt_domain_t* rt, struct heap* tasks)
+{
+        heap_union(rt->order, &rt->ready_queue, tasks);
+        rt->check_resched(rt);
+}
+
 /* add_release - add a real-time task to the rt release queue.
  * @task:        the sleeping task
  */
 void __add_release(rt_domain_t* rt, struct task_struct *task)
 {
         TRACE_TASK(task, "add_release(), rel=%llu\n", get_release(task));
-        list_add(&tsk_rt(task)->list, &rt->release_queue);
+        list_add(&tsk_rt(task)->list, &rt->tobe_released);
         task->rt_param.domain = rt;
-        do_without_rqlock(&rt->arm_timers);
+        do_without_rqlock(&rt->arm_timer);
 }
 
diff --git a/litmus/sched_cedf.c b/litmus/sched_cedf.c
index 2ac14cded9..bebb2c7ba5 100755
--- a/litmus/sched_cedf.c
+++ b/litmus/sched_cedf.c
@@ -325,56 +325,57 @@ static noinline void requeue(struct task_struct* task)
                 __add_ready(edf, task);
 }
 
+static void check_for_preemptions(cedf_domain_t* cedf)
+{
+        cpu_entry_t *last;
+        struct task_struct *task;
+        struct list_head *cedf_cpu_queue;
+        cedf_cpu_queue = &cedf->cedf_cpu_queue;
+
+        for(last = list_entry(cedf_cpu_queue->prev, cpu_entry_t, list);
+            edf_preemption_needed(&cedf->domain, last->linked);
+            last = list_entry(cedf_cpu_queue->prev, cpu_entry_t, list)) {
+                /* preemption necessary */
+                task = __take_ready(&cedf->domain);
+                TRACE("check_for_preemptions: task %d linked to %d, state:%d\n",
+                      task->pid, last->cpu, task->state);
+                if (last->linked)
+                        requeue(last->linked);
+                link_task_to_cpu(task, last);
+                preempt(last);
+        }
+
+}
+
 /* cedf_job_arrival: task is either resumed or released */
 static noinline void cedf_job_arrival(struct task_struct* task)
 {
-        cpu_entry_t* last;
         cedf_domain_t* cedf;
         rt_domain_t* edf;
-        struct list_head *cedf_cpu_queue;
 
         BUG_ON(!task);
 
         /* Get correct real-time domain. */
         cedf = task_cedf(task);
         edf = &cedf->domain;
-        cedf_cpu_queue = &cedf->cedf_cpu_queue;
-
-        BUG_ON(!cedf);
-        BUG_ON(!edf);
-        BUG_ON(!cedf_cpu_queue);
-        BUG_ON(list_empty(cedf_cpu_queue));
 
         /* first queue arriving job */
         requeue(task);
 
         /* then check for any necessary preemptions */
-        last = list_entry(cedf_cpu_queue->prev, cpu_entry_t, list);
-        if (edf_preemption_needed(edf, last->linked)) {
-                /* preemption necessary */
-                task = __take_ready(edf);
-                TRACE("job_arrival: task %d linked to %d, state:%d\n",
-                      task->pid, last->cpu, task->state);
-                if (last->linked)
-                        requeue(last->linked);
-
-                link_task_to_cpu(task, last);
-                preempt(last);
-        }
+        check_for_preemptions(cedf);
 }
 
 /* check for current job releases */
-static void cedf_job_release(struct task_struct* t, rt_domain_t* _)
+static void cedf_release_jobs(rt_domain_t* rt, struct heap* tasks)
 {
-        cedf_domain_t*          cedf = task_cedf(t);
+        cedf_domain_t*          cedf = container_of(rt, cedf_domain_t, domain);
         unsigned long           flags;
 
-        BUG_ON(!t);
-        BUG_ON(!cedf);
-
         spin_lock_irqsave(&cedf->slock, flags);
-        sched_trace_job_release(queued);
-        cedf_job_arrival(t);
+
+        __merge_ready(&cedf->domain, tasks);
+        check_for_preemptions(cedf);
         spin_unlock_irqrestore(&cedf->slock, flags);
 }
 
@@ -678,7 +679,7 @@ static void cedf_domain_init(int first_cpu, int last_cpu)
 
         /* Initialize cluster domain. */
         edf_domain_init(&new_cedf_domain->domain, NULL,
-                        cedf_job_release);
+                        cedf_release_jobs);
         new_cedf_domain->first_cpu      = first_cpu;
         new_cedf_domain->last_cpu       = last_cpu;
         INIT_LIST_HEAD(&new_cedf_domain->cedf_cpu_queue);
diff --git a/litmus/sched_gsn_edf.c b/litmus/sched_gsn_edf.c
index e32a4e8458..caaf58db67 100644
--- a/litmus/sched_gsn_edf.c
+++ b/litmus/sched_gsn_edf.c
@@ -285,41 +285,45 @@ static noinline void requeue(struct task_struct* task)
                 __add_ready(&gsnedf, task);
 }
 
-/* gsnedf_job_arrival: task is either resumed or released */
-static noinline void gsnedf_job_arrival(struct task_struct* task)
+
+/* check for any necessary preemptions */
+static void check_for_preemptions(void)
 {
+        struct task_struct *task;
         cpu_entry_t* last;
 
-        BUG_ON(list_empty(&gsnedf_cpu_queue));
-        BUG_ON(!task);
-
-        /* first queue arriving job */
-        requeue(task);
-
-        /* then check for any necessary preemptions */
-        last = list_entry(gsnedf_cpu_queue.prev, cpu_entry_t, list);
-        if (edf_preemption_needed(&gsnedf, last->linked)) {
+        for(last = list_entry(gsnedf_cpu_queue.prev, cpu_entry_t, list);
+            edf_preemption_needed(&gsnedf, last->linked);
+            last = list_entry(gsnedf_cpu_queue.prev, cpu_entry_t, list)) {
                 /* preemption necessary */
                 task = __take_ready(&gsnedf);
-                TRACE("job_arrival: attempting to link task %d to %d\n",
+                TRACE("check_for_preemptions: attempting to link task %d to %d\n",
                       task->pid, last->cpu);
                 if (last->linked)
                         requeue(last->linked);
-
                 link_task_to_cpu(task, last);
                 preempt(last);
         }
 }
 
-/* check for current job releases */
-static void gsnedf_job_release(struct task_struct* t, rt_domain_t* _)
+/* gsnedf_job_arrival: task is either resumed or released */
+static noinline void gsnedf_job_arrival(struct task_struct* task)
+{
+        BUG_ON(list_empty(&gsnedf_cpu_queue));
+        BUG_ON(!task);
+
+        requeue(task);
+        check_for_preemptions();
+}
+
+static void gsnedf_release_jobs(rt_domain_t* rt, struct heap* tasks)
 {
         unsigned long flags;
 
         spin_lock_irqsave(&gsnedf_lock, flags);
 
-        sched_trace_job_release(queued);
-        gsnedf_job_arrival(t);
+        __merge_ready(rt, tasks);
+        check_for_preemptions();
 
         spin_unlock_irqrestore(&gsnedf_lock, flags);
 }
@@ -723,7 +727,7 @@ static int __init init_gsn_edf(void)
                 INIT_LIST_HEAD(&entry->list);
         }
 
-        edf_domain_init(&gsnedf, NULL, gsnedf_job_release);
+        edf_domain_init(&gsnedf, NULL, gsnedf_release_jobs);
         return register_sched_plugin(&gsn_edf_plugin);
 }
 
diff --git a/litmus/sched_pfair.c b/litmus/sched_pfair.c
index beb303c352..9adf9c835c 100755
--- a/litmus/sched_pfair.c
+++ b/litmus/sched_pfair.c
@@ -21,14 +21,6 @@
 
 #include <litmus/heap.h>
 
-/* Tick period is used to convert ns-specified execution
- * costs and periods into tick-based equivalents.
- */
-extern ktime_t tick_period;
-
-/* make the unit explicit */
-typedef unsigned long quanta_t;
-
 struct subtask {
         /* measured in quanta relative to job release */
         quanta_t release;
@@ -160,20 +152,6 @@ static quanta_t cur_group_deadline(struct task_struct* t)
                 return gdl;
 }
 
-enum round {
-        FLOOR,
-        CEIL
-};
-
-static quanta_t time2quanta(lt_t time, enum round round)
-{
-        s64  quantum_length = ktime_to_ns(tick_period);
-
-        if (do_div(time, quantum_length) && round == CEIL)
-                time++;
-        return (quanta_t) time;
-}
-
 static int pfair_higher_prio(struct task_struct* first,
                              struct task_struct* second)
 {
@@ -244,7 +222,7 @@ static void pfair_add_release(struct task_struct* t)
 /* pull released tasks from the release queue */
 static void poll_releases(quanta_t time)
 {
-        heap_union(pfair_ready_order, &pfair.ready_queue, relq(time));
+        __merge_ready(&pfair, relq(time));
         merge_time = time;
 }
 
diff --git a/litmus/sched_psn_edf.c b/litmus/sched_psn_edf.c
index 0e9c9dd80a..71dcfa1fcd 100644
--- a/litmus/sched_psn_edf.c
+++ b/litmus/sched_psn_edf.c
@@ -47,7 +47,7 @@ DEFINE_PER_CPU(psnedf_domain_t, psnedf_domains);
 
 static void psnedf_domain_init(psnedf_domain_t* pedf,
                                check_resched_needed_t check,
-                               release_job_t release,
+                               release_jobs_t release,
                                int cpu)
 {
         edf_domain_init(&pedf->domain, check, release);