Backup Commit

5 files changed, 419 insertions, 89 deletions

diff --git a/include/litmus/litmus.h b/include/litmus/litmus.h
index f550367ddd4b..2081fab6c825 100644
--- a/include/litmus/litmus.h
+++ b/include/litmus/litmus.h
@@ -120,6 +120,7 @@ static inline lt_t litmus_clock(void)
 void preempt_if_preemptable(struct task_struct* t, int on_cpu);
 
 #define bheap2task(hn) ((struct task_struct*) hn->value)
+#define bheap2res(hn) ((struct reservation*) hn->value)
 
 static inline int is_present(struct task_struct* t)
 {
diff --git a/include/litmus/reservations/reservation.h b/include/litmus/reservations/reservation.h
index 1752dac4e698..3dce3a47a2fa 100644
--- a/include/litmus/reservations/reservation.h
+++ b/include/litmus/reservations/reservation.h
@@ -202,6 +202,8 @@ struct sup_reservation_environment {
         lt_t next_scheduler_update;
         /* set to true if a call to sup_dispatch() is imminent */
         bool will_schedule;
+
+        struct res_env_ops ops;
 };
 
 /* Contract:
@@ -221,4 +223,46 @@ struct task_struct* sup_dispatch(struct sup_reservation_environment* sup_env);
 struct reservation* sup_find_by_id(struct sup_reservation_environment* sup_env,
         unsigned int id);
 
+/* ************************************************************************* */
+/* cpu_entry struct */
+typedef struct {
+        int cpu;
+        struct task_struct* linked;
+        struct task_struct* scheduled;
+        struct bheap_node* hn;
+        struct list_node* ln;
+} cpu_entry_t;
+
+/* Hierarchical reservation environment */
+struct ext_reservation_environment {
+        struct reservation environment env;
+
+        /* only used for global reservation environments */
+        raw_spinlock_t lock;
+
+        /* ordered by priority */
+        struct list_head active_reservations;
+
+        /* ordered by next_replenishment */
+        struct list_head depleted_reservations;
+
+        /* unordered */
+        struct list_head inactive_reservations;
+
+        /* list of all reservations */
+        struct list_head all_reservations;
+
+        lt_t next_scheduler_update;
+        bool will_scheduled;
+}
+
+/* Hierarchical reservation */
+struct ext_reservation {
+        /* reservation data */
+        struct reservation res;
+
+        /* reservation environment for child reservations */
+        struct list_head child_envs;
+};
+
 #endif
diff --git a/include/litmus/rt_domain.h b/include/litmus/rt_domain.h
index ac249292e866..5a7fb59bd750 100644
--- a/include/litmus/rt_domain.h
+++ b/include/litmus/rt_domain.h
@@ -5,7 +5,11 @@
 #ifndef __UNC_RT_DOMAIN_H__
 #define __UNC_RT_DOMAIN_H__
 
+#include <linux/rbtree.h>
+
 #include <litmus/bheap.h>
+#include <litmus/binheap.h>
+#include <litmus/reservations/ext_reservation.h>
 
 #define RELEASE_QUEUE_SLOTS 127 /* prime */
 
@@ -15,9 +19,9 @@ typedef int (*check_resched_needed_t)(struct _rt_domain *rt);
 typedef void (*release_jobs_t)(struct _rt_domain *rt, struct bheap* tasks);
 
 struct release_queue {
-        /* each slot maintains a list of release heaps sorted
-         * by release time */
-        struct list_head                slot[RELEASE_QUEUE_SLOTS];
+        struct list_head slot[RELEASE_QUEUE_SLOTS];
+        struct binheap queue;
+        volatile lt_t earliest_release;
 };
 
 typedef struct _rt_domain {
@@ -27,12 +31,19 @@ typedef struct _rt_domain {
 
         /* real-time tasks waiting for release are in here */
         raw_spinlock_t                  release_lock;
-        struct release_queue            release_queue;
+        struct release_queue    release_queue;
 
 #ifdef CONFIG_RELEASE_MASTER
         int                             release_master;
+        /* used to delegate releases.
+         * does not appear to be assigned anywhere in Litmus
+         */
+        struct hrtimer_start_on_info    info;
 #endif
 
+        /* release timer for earliest heap in release_queue */
+        struct hrtimer                  timer;
+
         /* for moving tasks to the release queue */
         raw_spinlock_t                  tobe_lock;
         struct list_head                tobe_released;
@@ -48,22 +59,18 @@ typedef struct _rt_domain {
 } rt_domain_t;
 
 struct release_heap {
-        /* list_head for per-time-slot list */
-        struct list_head                list;
+        /* for enqueueing into release_queue */
+        struct binheap_node node;
+        struct list_head        list;
         lt_t                            release_time;
         /* all tasks to be released at release_time */
         struct bheap                    heap;
-        /* used to trigger the release */
-        struct hrtimer                  timer;
-
-#ifdef CONFIG_RELEASE_MASTER
-        /* used to delegate releases */
-        struct hrtimer_start_on_info    info;
-#endif
-        /* required for the timer callback */
-        rt_domain_t*                    dom;
+        /* list of all tasks, used for release callback in reservation */
+        struct list_head                list_head;
 };
 
+static void suspend_releases(rt_domain_t* rt);
+static void resume_releases(rt_domain_t* rt);
 
 static inline struct task_struct* __next_ready(rt_domain_t* rt)
 {
@@ -74,6 +81,15 @@ static inline struct task_struct* __next_ready(rt_domain_t* rt)
                 return NULL;
 }
 
+static inline struct reservation* __next_ready_res(rt_domain_t* rt)
+{
+        struct bheap_node *n = bheap_peek(rt->order, &rt->ready_queue);
+        if (hn)
+                return bheap2res(hn);
+        else
+                return NULL;
+}
+
 void rt_domain_init(rt_domain_t *rt, bheap_prio_t order,
                     check_resched_needed_t check,
                     release_jobs_t relase);
@@ -82,6 +98,10 @@ void __add_ready(rt_domain_t* rt, struct task_struct *new);
 void __merge_ready(rt_domain_t* rt, struct bheap *tasks);
 void __add_release(rt_domain_t* rt, struct task_struct *task);
 
+void __add_ready_res(rt_domain* rt, struct reservation* new);
+void __merge_ready_res(rt_domain_t* rt, struct bheap *res);
+void __add_release_res(rt_domain_t* rt, struct reservation* res);
+
 static inline struct task_struct* __take_ready(rt_domain_t* rt)
 {
         struct bheap_node* hn = bheap_take(rt->order, &rt->ready_queue);
@@ -91,6 +111,15 @@ static inline struct task_struct* __take_ready(rt_domain_t* rt)
                 return NULL;
 }
 
+static inline struct reservation* __take_ready_res(rt_domain_t* rt)
+{
+        struct bheap_node* hn = bheap_take(rt->order, &rt->ready_queue);
+        if (hn)
+                return bheap2res(hn);
+        else
+                return NULL;
+}
+
 static inline struct task_struct* __peek_ready(rt_domain_t* rt)
 {
         struct bheap_node* hn = bheap_peek(rt->order, &rt->ready_queue);
@@ -100,17 +129,37 @@ static inline struct task_struct* __peek_ready(rt_domain_t* rt)
                 return NULL;
 }
 
+static inline struct reservation* __peek_ready_res(rt_domain_t* rt)
+{
+        struct bheap_node* hn = bheap_peek(rt->order, &rt->ready_queue);
+        if (hn)
+                return bheap2res(hn);
+        else
+                return NULL;
+}
+
 static inline int  is_queued(struct task_struct *t)
 {
         BUG_ON(!tsk_rt(t)->heap_node);
         return bheap_node_in_heap(tsk_rt(t)->heap_node);
 }
 
+static inline int  is_queued_res(struct reservation* res)
+{
+        BUG_ON(!cres->heap_node);
+        return bheap_node_in_heap(res->heap_node);
+}
+
 static inline void remove(rt_domain_t* rt, struct task_struct *t)
 {
         bheap_delete(rt->order, &rt->ready_queue, tsk_rt(t)->heap_node);
 }
 
+static inline void remove_res(rt_domain_t* rt, struct reservation* res)
+{
+        bheap_delete(rt->order, &rt->ready_queue, res->heap_node);
+}
+
 static inline void add_ready(rt_domain_t* rt, struct task_struct *new)
 {
         unsigned long flags;
@@ -120,6 +169,15 @@ static inline void add_ready(rt_domain_t* rt, struct task_struct *new)
         raw_spin_unlock_irqrestore(&rt->ready_lock, flags);
 }
 
+static inline void add_ready_res(rt_domain_t* rt, struct reservation *new)
+{
+        unsigned long flags;
+        /* first we need the write lock for rt_ready_queue */
+        raw_spin_lock_irqsave(&rt->ready_lock, flags);
+        __add_ready_res(rt, new);
+        raw_spin_unlock_irqrestore(&rt->ready_lock, flags);
+}
+
 static inline void merge_ready(rt_domain_t* rt, struct bheap* tasks)
 {
         unsigned long flags;
@@ -128,6 +186,14 @@ static inline void merge_ready(rt_domain_t* rt, struct bheap* tasks)
         raw_spin_unlock_irqrestore(&rt->ready_lock, flags);
 }
 
+static inline void merge_ready_res(rt_domain_t* rt, struct bheap* tasks)
+{
+        unsigned long flags;
+        raw_spin_lock_irqsave(&rt->ready_lock, flags);
+        __merge_ready_res(rt, tasks);
+        raw_spin_unlock_irqrestore(&rt->ready_lock, flags);
+}
+
 static inline struct task_struct* take_ready(rt_domain_t* rt)
 {
         unsigned long flags;
@@ -139,6 +205,16 @@ static inline struct task_struct* take_ready(rt_domain_t* rt)
         return ret;
 }
 
+static inline struct reservation* take_ready_res(rt_domain_t* rt)
+{
+        unsigned long flags;
+        struct reservation* ret;
+        /* first we need the write lock for rt_ready_queue */
+        raw_spin_lock_irqsave(&rt->ready_lock, flags);
+        ret = __take_ready_res(rt);
+        raw_spin_unlock_irqrestore(&rt->ready_lock, flags);
+        return ret;
+}
 
 static inline void add_release(rt_domain_t* rt, struct task_struct *task)
 {
@@ -148,10 +224,21 @@ static inline void add_release(rt_domain_t* rt, struct task_struct *task)
         raw_spin_unlock_irqrestore(&rt->tobe_lock, flags);
 }
 
+static inline void add_release_res(rt_domain_t* rt, struct reservation* res)
+{
+        unsigned long flags;
+        raw_spin_lock_irqsave(&rt->tobe_lock, flags);
+        __add_release_res(rt, task);
+        raw_spin_unlock_irqstore(&rt->tobe_lock, flags);
+}
+
 #ifdef CONFIG_RELEASE_MASTER
 void __add_release_on(rt_domain_t* rt, struct task_struct *task,
                       int target_cpu);
 
+void __add_release_res_on(rt_domain_t* rt, struct reservation* res,
+                          int target_cpu);
+
 static inline void add_release_on(rt_domain_t* rt,
                                   struct task_struct *task,
                                   int target_cpu)
@@ -161,6 +248,16 @@ static inline void add_release_on(rt_domain_t* rt,
         __add_release_on(rt, task, target_cpu);
         raw_spin_unlock_irqrestore(&rt->tobe_lock, flags);
 }
+
+static inline void add_release_res_on(rt_domain_rt* rt,
+                                  struct reservation* res,
+                                  int target_cpu)
+{
+        unsigned long flags;
+        raw_spin_lock_irqsave(&rt->tobe_lock, flags);
+        __add_release_res_on(rt, res, target_cpu);
+        raw_spin_unlock_irqrestore(&rt->tobe_lock, flags);
+}
 #endif
 
 static inline int __jobs_pending(rt_domain_t* rt)
diff --git a/litmus/rt_domain.c b/litmus/rt_domain.c
index 733a483e3084..f90f5718c0ad 100644
--- a/litmus/rt_domain.c
+++ b/litmus/rt_domain.c
@@ -10,6 +10,7 @@
 #include <linux/sched.h>
 #include <linux/list.h>
 #include <linux/slab.h>
+#include <linux/rbtree.h>
 
 #include <litmus/litmus.h>
 #include <litmus/sched_plugin.h>
@@ -17,10 +18,12 @@
 #include <litmus/debug_trace.h>
 
 #include <litmus/rt_domain.h>
+#include <litmus/reservations/ext_reservation.h>
 
 #include <litmus/trace.h>
 
 #include <litmus/bheap.h>
+#include <litmus/binheap.h>
 
 /* Uncomment when debugging timer races... */
 #if 0
@@ -49,38 +52,81 @@ static void default_release_jobs(rt_domain_t* rt, struct bheap* tasks)
 
 static unsigned int time2slot(lt_t time)
 {
-        return (unsigned int) time2quanta(time, FLOOR) % RELEASE_QUEUE_SLOTS;
+                return (unsigned int) time2quanta(time, FLOOR) % RELEASE_QUEUE_SLOTS;
 }
 
-static enum hrtimer_restart on_release_timer(struct hrtimer *timer)
+int release_order(struct binheap_node *a, struct binheap_node *b)
+{
+        return lt_before(binheap_entry(a, struct release_heap, node)->release_time,
+                                         binheap_entry(b, struct release_heap, node)->release_time);
+}
+
+static void release_jobs_before_now(rt_domain_t* rt)
 {
         unsigned long flags;
+        struct rb_node *temp1, *temp2;
         struct release_heap* rh;
-        rh = container_of(timer, struct release_heap, timer);
 
-        TS_RELEASE_LATENCY(rh->release_time);
+        /* remove all heaps with release time earlier than now
+         * from the release queue and call release callback
+         */
+        while(!binheap_empty(&rt->release_queue.queue) &&
+                        lt_before_eq(litmus_clock(), rt->earliest_release)) {
+                raw_spin_lock_irqsave(&rt->release_lock, flags);
+                VTRACE("CB has the release_lock 0x%p\n", &rt->release_lock);
 
-        VTRACE("on_release_timer(0x%p) starts.\n", timer);
+                TS_RELEASE_LATENCY(rh->release_time);
+                TS_RELEASE_START;
 
-        TS_RELEASE_START;
+                /* O(1) operation */
+                rh = binheap_top_entry(&rt->release_queue.queue, struct release_heap, node);
+                list_del_init(&rh->list);
 
+                binheap_delete_root(&rt->release_queue.queue, struct release_heap, node);
+                rt->earliest_release =
+                        binheap_top_entry(&rt->release_queue.queue, struct release_heap, node)
+                        ->release_time;
 
-        raw_spin_lock_irqsave(&rh->dom->release_lock, flags);
-        VTRACE("CB has the release_lock 0x%p\n", &rh->dom->release_lock);
-        /* remove from release queue */
-        list_del(&rh->list);
-        raw_spin_unlock_irqrestore(&rh->dom->release_lock, flags);
-        VTRACE("CB returned release_lock 0x%p\n", &rh->dom->release_lock);
+                raw_spin_unlock_irqrestore(&rt->release_lock, flags);
+                VTRACE("CB returned release_lock 0x%p\n", &rt->release_lock);
 
-        /* call release callback */
-        rh->dom->release_jobs(rh->dom, &rh->heap);
-        /* WARNING: rh can be referenced from other CPUs from now on. */
+                rt->release_jobs(rt, &rh->heap);
 
-        TS_RELEASE_END;
+                TS_RELEASE_END;
+        }
+}
+
+static enum hrtimer_restart on_release_timer(struct hrtimer *timer)
+{
+        rt_domain_t* rt;
+        struct release_heap* rh;
+
+        rt = container_of(timer, rt_domain_t, timer);
+
+        release_jobs_before_now(rt);
 
         VTRACE("on_release_timer(0x%p) ends.\n", timer);
 
-        return  HRTIMER_NORESTART;
+        /* when there are no more jobs to release */
+        if (!rt->first)
+                return HRTIMER_NORESTART;
+        hrtimer_set_expires(timer, ns_to_ktime(rt->earliest_release));
+
+        return HRTIMER_RESTART;
+}
+
+static void suspend_releases(rt_domain_t* rt)
+{
+        hrtimer_try_to_cancel(&rt->timer);
+}
+
+static void resume_releases(rt_domain_t* rt)
+{
+        release_jobs_before_now(rt);
+        if (rt->first) {
+                hrtimer_start(&rh->timer, ns_to_ktime(rt->earliest_release));
+        }
+
 }
 
 /* allocated in litmus.c */
@@ -90,35 +136,31 @@ struct release_heap* release_heap_alloc(int gfp_flags)
 {
         struct release_heap* rh;
         rh= kmem_cache_alloc(release_heap_cache, gfp_flags);
-        if (rh) {
-                /* initialize timer */
-                hrtimer_init(&rh->timer, CLOCK_MONOTONIC, HRTIMER_MODE_ABS);
-                rh->timer.function = on_release_timer;
-        }
         return rh;
 }
 
 void release_heap_free(struct release_heap* rh)
 {
         /* make sure timer is no longer in use */
-        hrtimer_cancel(&rh->timer);
         kmem_cache_free(release_heap_cache, rh);
 }
 
-/* Caller must hold release lock.
+/* For all variants of get_release_heap
+ * Caller must 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,
-                                             struct task_struct* t,
+static struct release_heap* __get_release_heap(rt_domain_t *rt,
+                                             lt_t release_time,
+                                                 struct release_heap th,
                                              int use_task_heap)
 {
         struct list_head* pos;
         struct release_heap* heap = NULL;
         struct release_heap* rh;
-        lt_t release_time = get_release(t);
         unsigned int slot = time2slot(release_time);
 
+        /* loop is for hash collision, O(1) time complexity */
         /* 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]) {
@@ -138,39 +180,59 @@ static struct release_heap* get_release_heap(rt_domain_t *rt,
         }
         if (!heap && use_task_heap) {
                 /* use pre-allocated release heap */
-                rh = tsk_rt(t)->rel_heap;
+                rh = th;
 
-                rh->dom = rt;
                 rh->release_time = release_time;
 
                 /* add to release queue */
                 list_add(&rh->list, pos->prev);
+                /* binheap_add is O(lg n) time complexity. It can't be helped
+                 * if we want to be able to have 1 domain timer that we can disable
+                 * easily upon domain preemption
+                 */
+                binheap_add(&rh->node, ht->release_queue.queue, struct release_heap, node);
+
                 heap = rh;
         }
         return heap;
 }
 
+static struct release_heap* get_release_heap(rt_domain_t *rt,
+                                                 struct reservation* res,
+                                                 int use_task_heap)
+{
+        __get_release_heap(rt, res->next_replenishment, res->rel_heap, use_task_heap);
+}
+
+static struct release_heap* get_release_heap(rt_domain_t *rt,
+                                                 struct task_struct *t,
+                                                 int use_task_heap)
+{
+        __get_release_heap(rt, get_release(t), tsk_rt(t)->rel_heap, use_task_heap);
+}
+
 static void reinit_release_heap(struct task_struct* t)
 {
         struct release_heap* rh;
 
         /* use pre-allocated release heap */
         rh = tsk_rt(t)->rel_heap;
+        INIT_LIST_HEAD(&rh->list_head);
+        /* initialize */
+        bheap_init(&rh->heap);
+}
 
-        /* Make sure it is safe to use.  The timer callback could still
-         * be executing on another CPU; hrtimer_cancel() will wait
-         * until the timer callback has completed.  However, under no
-         * circumstances should the timer be active (= yet to be
-         * triggered).
-         *
-         * WARNING: If the CPU still holds the release_lock at this point,
-         *          deadlock may occur!
-         */
-        BUG_ON(hrtimer_cancel(&rh->timer));
+static void reinit_release_heap(struct reservation* t)
+{
+        struct release_heap* rh;
 
+        /* use pre-allocated release heap */
+        rh = reservation->rel_heap;
+        INIT_LIST_HEAD(&rh->list_head);
         /* initialize */
         bheap_init(&rh->heap);
 }
+
 /* arm_release_timer() - start local release timer or trigger
  *     remote timer (pull timer)
  *
@@ -197,44 +259,46 @@ static void arm_release_timer(rt_domain_t *_rt)
         list_for_each_safe(pos, safe, &list) {
                 /* pick task of work list */
                 t = list_entry(pos, struct task_struct, rt_param.list);
-                sched_trace_task_release(t);
+                //sched_trace_task_release(t);
                 list_del(pos);
 
                 /* put into release heap while holding release_lock */
                 raw_spin_lock(&rt->release_lock);
-                VTRACE_TASK(t, "I have the release_lock 0x%p\n", &rt->release_lock);
+                VTRACE("acquired the release_lock 0x%p\n", &rt->release_lock);
 
                 rh = get_release_heap(rt, t, 0);
                 if (!rh) {
                         /* need to use our own, but drop lock first */
                         raw_spin_unlock(&rt->release_lock);
-                        VTRACE_TASK(t, "Dropped release_lock 0x%p\n",
+                        VTRACE("dropped release_lock 0x%p\n",
                                     &rt->release_lock);
 
                         reinit_release_heap(t);
-                        VTRACE_TASK(t, "release_heap ready\n");
+                        VTRACE("release_heap ready\n");
 
                         raw_spin_lock(&rt->release_lock);
-                        VTRACE_TASK(t, "Re-acquired release_lock 0x%p\n",
+                        VTRACE("re-acquired release_lock 0x%p\n",
                                     &rt->release_lock);
 
                         rh = get_release_heap(rt, t, 1);
                 }
                 bheap_insert(rt->order, &rh->heap, tsk_rt(t)->heap_node);
-                VTRACE_TASK(t, "arm_release_timer(): added to release heap\n");
+                VTRACE("arm_release_timer(): added to release heap\n");
+
+                rh = binheap_top_entry(rt->release_queue.queue, struct release_heap, node);
+                rt->earliest_release = rh->release_time;
 
                 raw_spin_unlock(&rt->release_lock);
-                VTRACE_TASK(t, "Returned the release_lock 0x%p\n", &rt->release_lock);
+                VTRACE("dropped the release_lock 0x%p\n", &rt->release_lock);
 
                 /* To avoid arming the timer multiple times, we only let the
-                 * owner do the arming (which is the "first" task to reference
-                 * this release_heap anyway).
+                 * owner of the new earliest release heap do the arming.
                  */
                 if (rh == tsk_rt(t)->rel_heap) {
-                        VTRACE_TASK(t, "arming timer 0x%p\n", &rh->timer);
+                        VTRACE("arming timer 0x%p\n", &rh->timer);
 
                         if (!hrtimer_is_hres_active(&rh->timer)) {
-                                TRACE_TASK(t, "WARNING: no hires timer!!!\n");
+                                VTRACE("WARNING: no hires timer!!!\n");
                         }
 
                         /* we cannot arm the timer using hrtimer_start()
@@ -246,7 +310,7 @@ static void arm_release_timer(rt_domain_t *_rt)
                         if (rt->release_master == NO_CPU &&
                             target_cpu == NO_CPU)
 #endif
-                                hrtimer_start(&rh->timer,
+                                hrtimer_start(&rt->timer,
                                         ns_to_ktime(rh->release_time),
                                         HRTIMER_MODE_ABS_PINNED);
 #ifdef CONFIG_RELEASE_MASTER
@@ -255,15 +319,112 @@ static void arm_release_timer(rt_domain_t *_rt)
                                         /* target_cpu overrides release master */
                                         (target_cpu != NO_CPU ?
                                          target_cpu : rt->release_master),
-                                        &rh->info, &rh->timer,
+                                        &rt->info, &rt->timer,
                                         ns_to_ktime(rh->release_time),
                                         HRTIMER_MODE_ABS_PINNED);
 #endif
                 } else
-                        VTRACE_TASK(t, "0x%p is not my timer\n", &rh->timer);
+                        VTRACE("timer 0x%p has been armed for earlier time\n", &rh->timer);
         }
 }
 
+/* arm_release_timer_res() - start local release timer or trigger
+ *     remote timer (pull timer)
+ *
+ * Called by add_release_res() with:
+ * - tobe_lock taken
+ * - IRQ disabled
+ *
+ * TODO: find some way to combine this with the task version of this fuction
+ */
+#ifdef CONFIG_RELEASE_MASTER
+#define arm_release_timer_res(t) arm_release_timer_res_on((t), NO_CPU)
+static void arm_release_timer_res_on(rt_domain_t *_rt , int target_cpu)
+#else
+static void arm_release_timer_res(rt_domain_t *_rt)
+#endif
+{
+        rt_domain_t *rt = _rt;
+        struct list_head list;
+        struct list_head *pos, *safe;
+        struct reservation* res;
+        struct release_heap* rh;
+
+        VTRACE("arm_release_timer() at %llu\n", litmus_clock());
+        list_replace_init(&rt->tobe_released, &list);
+
+        list_for_each_safe(pos, safe, &list) {
+                /* pick task of work list */
+                res = list_entry(pos, struct reservation, ln);
+                //sched_trace_task_release(t);
+                list_del(pos);
+
+                /* put into release heap while holding release_lock */
+                raw_spin_lock(&rt->release_lock);
+                VTRACE("acquired the release_lock 0x%p\n", &rt->release_lock);
+
+                rh = get_release_heap(rt, res, 0);
+                if (!rh) {
+                        /* need to use our own, but drop lock first */
+                        raw_spin_unlock(&rt->release_lock);
+                        VTRACE("dropped release_lock 0x%p\n",
+                                    &rt->release_lock);
+
+                        reinit_release_heap(t);
+                        VTRACE("release_heap ready\n");
+
+                        raw_spin_lock(&rt->release_lock);
+                        VTRACE("re-acquired release_lock 0x%p\n",
+                                    &rt->release_lock);
+
+                        rh = get_release_heap(rt, res, 1);
+                }
+                bheap_insert(rt->order, &rh->heap, res->heap_node);
+                list_add_tail(&res->ln, &rh->list_head);
+                VTRACE("arm_release_timer(): added to release heap\n");
+
+                rh = binheap_top_entry(rt->release_queue.queue, struct release_heap, node);
+                rt->earliest_release = rh->release_time;
+
+                raw_spin_unlock(&rt->release_lock);
+                VTRACE("dropped the release_lock 0x%p\n", &rt->release_lock);
+
+                /* To avoid arming the timer multiple times, we only let the
+                 * owner of the new earliest release heap do the arming.
+                 */
+                if (rh == res->rel_heap) {
+                        VTRACE("arming timer 0x%p\n", &rh->timer);
+
+                        if (!hrtimer_is_hres_active(&rh->timer)) {
+                                VTRACE("WARNING: no hires timer!!!\n");
+                        }
+
+                        /* we cannot arm the timer using hrtimer_start()
+                         * as it may deadlock on rq->lock
+                         *
+                         * PINNED mode is ok on both local and remote CPU
+                         */
+#ifdef CONFIG_RELEASE_MASTER
+                        if (rt->release_master == NO_CPU &&
+                            target_cpu == NO_CPU)
+#endif
+                                hrtimer_start(&rt->timer,
+                                        ns_to_ktime(rh->release_time),
+                                        HRTIMER_MODE_ABS_PINNED);
+#ifdef CONFIG_RELEASE_MASTER
+                        else
+                                hrtimer_start_on(
+                                        /* target_cpu overrides release master */
+                                        (target_cpu != NO_CPU ?
+                                         target_cpu : rt->release_master),
+                                        &rt->info, &rt->timer,
+                                        ns_to_ktime(rh->release_time),
+                                        HRTIMER_MODE_ABS_PINNED);
+#endif
+                } else
+                        VTRACE("timer 0x%p has been armed for earlier time\n", &rh->timer);
+        }
+}
 void rt_domain_init(rt_domain_t *rt,
                     bheap_prio_t order,
                     check_resched_needed_t check,
@@ -288,11 +449,16 @@ void rt_domain_init(rt_domain_t *rt,
         INIT_LIST_HEAD(&rt->tobe_released);
         for (i = 0; i < RELEASE_QUEUE_SLOTS; i++)
                 INIT_LIST_HEAD(&rt->release_queue.slot[i]);
+        INIT_BINHEAP_HANDLE(&rt->release_queue.queue, release_order);
+        rt->release_queue.earliest_release = 0;
 
         raw_spin_lock_init(&rt->ready_lock);
         raw_spin_lock_init(&rt->release_lock);
         raw_spin_lock_init(&rt->tobe_lock);
 
+        hrtimer_init(&rt->timer, CLOCK_MONOTONIC, HRTIMER_MODE_ABS);
+        rt->timer.function = on_release_timer;
+
         rt->check_resched       = check;
         rt->release_jobs        = release;
         rt->order               = order;
@@ -315,6 +481,13 @@ void __add_ready(rt_domain_t* rt, struct task_struct *new)
         rt->check_resched(rt);
 }
 
+void __add_ready_res(rt_domain_t* rt, struct reservation* new)
+{
+        BUG_ON(bheap_node_in_heap(new->heap_node));
+
+        bheap_insert(rt->order, &rt->ready_queue, new->heap_node);
+}
+
 /* merge_ready - Add a sorted set of tasks to the rt ready queue. They must be runnable.
  * @tasks      - the newly released tasks
  */
@@ -324,10 +497,15 @@ void __merge_ready(rt_domain_t* rt, struct bheap* tasks)
         rt->check_resched(rt);
 }
 
+void __merge_ready_res(rt_domain_t* rt, struct bheap* res)
+{
+        bheap_union(rt->order, &rt->ready_queue, tasks);
+        rt->check_resched(rt);
+}
 
 #ifdef CONFIG_RELEASE_MASTER
 void __add_release_on(rt_domain_t* rt, struct task_struct *task,
-                      int target_cpu)
+                          int target_cpu)
 {
         TRACE_TASK(task, "add_release_on(), rel=%llu, target=%d\n",
                    get_release(task), target_cpu);
@@ -336,6 +514,14 @@ void __add_release_on(rt_domain_t* rt, struct task_struct *task,
 
         arm_release_timer_on(rt, target_cpu);
 }
+
+void __add_release_res_on(rt_domain_t* rt, struct reservation *res,
+                           int target_cpu)
+{
+        list_add(&res->ln, &rt->tobe_released);
+
+        arm_release_timer_res_on(rt, target_cpu);
+}
 #endif
 
 /* add_release - add a real-time task to the rt release queue.
@@ -349,3 +535,10 @@ void __add_release(rt_domain_t* rt, struct task_struct *task)
 
         arm_release_timer(rt);
 }
+
+void __add_release_res(rt_domain_t* rt, struct reservation *reservation)
+{
+        list_add(&res->ln, &rt->tobe_released);
+
+        arm_release_timer_res(rt);
+}
diff --git a/litmus/sched_ext_res.c b/litmus/sched_ext_res.c
index 0a3270346656..bf4dc151a4d7 100644
--- a/litmus/sched_ext_res.c
+++ b/litmus/sched_ext_res.c
@@ -13,7 +13,7 @@
 #include <litmus/litmus_proc.h>
 #include <litmus/sched_trace.h>
 
-#include <litmus/reservations/reservation.h>
+#include <litmus/reservations/ext_reservation.h>
 #include <litmus/reservations/alloc.h>
 
 struct pres_task_state {
@@ -32,6 +32,8 @@ struct pres_cpu_state {
         struct task_struct* scheduled;
 };
 
+struct gedf_reservation_environment gedf_env;
+
 static DEFINE_PER_CPU(struct pres_cpu_state, pres_cpu_state);
 
 #define cpu_state_for(cpu_id)   (&per_cpu(pres_cpu_state, cpu_id))
@@ -529,25 +531,18 @@ static void pres_setup_domain_proc(void)
         }
 }
 
-static long pres_activate_plugin(void)
+static long ext_res_activate_plugin(void)
 {
         int cpu;
-        struct pres_cpu_state *state;
+
+        gedf_reservation_environment_init(&gedf_env);
 
         for_each_online_cpu(cpu) {
                 TRACE("Initializing CPU%d...\n", cpu);
-
-                state = cpu_state_for(cpu);
-
-                raw_spin_lock_init(&state->lock);
-                state->cpu = cpu;
-                state->scheduled = NULL;
-
-                sup_init(&state->sup_env);
-
-                hrtimer_init(&state->timer, CLOCK_MONOTONIC, HRTIMER_MODE_ABS_PINNED);
-                state->timer.function = on_scheduling_timer;
+                gedf_env->cpu_mapping[cpu] = cpu;
+                gedf_env->cpu_entries[cpu].id = cpu;
         }
+        gedf_env->num_cpus = cpu;
 
         pres_setup_domain_proc();
 
@@ -586,8 +581,8 @@ static long pres_deactivate_plugin(void)
         return 0;
 }
 
-static struct sched_plugin pres_plugin = {
-        .plugin_name            = "P-RES",
+static struct sched_plugin ext_res_plugin = {
+        .plugin_name            = "EXT-RES",
         .schedule               = pres_schedule,
         .task_block             = pres_task_block,
         .task_wake_up           = pres_task_resume,
@@ -597,16 +592,16 @@ static struct sched_plugin pres_plugin = {
         .task_exit              = pres_task_exit,
         .complete_job           = complete_job_oneshot,
         .get_domain_proc_info   = pres_get_domain_proc_info,
-        .activate_plugin        = pres_activate_plugin,
+        .activate_plugin        = ext_res_activate_plugin,
         .deactivate_plugin      = pres_deactivate_plugin,
         .reservation_create     = pres_reservation_create,
         .current_budget         = pres_current_budget,
 };
 
-static int __init init_pres(void)
+static int __init init_ext_res(void)
 {
-        return register_sched_plugin(&pres_plugin);
+        return register_sched_plugin(&ext_res_plugin);
 }
 
-module_init(init_pres);
+module_init(init_ext_res);