Use binomial heaps as priority queues.

The list-based priority queues did not perform well on the Niagara T2000.
This heap-based implementation should perform much faster when queues
are long.

12 files changed, 413 insertions, 75 deletions

diff --git a/include/linux/sched.h b/include/linux/sched.h
index 9541cc8fe8..76e28f19e9 100644
--- a/include/linux/sched.h
+++ b/include/linux/sched.h
@@ -1187,11 +1187,6 @@ struct task_struct {
         /* litmus parameters and state */
         struct rt_param rt_param;
 
-        /* allow scheduler plugins to queue in release lists, etc.
-         * Cleanup: Move this into the rt_param struct.
-         */
-        struct list_head rt_list;
-
         /* references to PI semaphores, etc. */
         struct od_table_entry* od_table;
 };
diff --git a/include/litmus/edf_common.h b/include/litmus/edf_common.h
index 37630e5c26..4dff77ae48 100644
--- a/include/litmus/edf_common.h
+++ b/include/litmus/edf_common.h
@@ -18,8 +18,6 @@ void edf_domain_init(rt_domain_t* rt, check_resched_needed_t resched,
 int edf_higher_prio(struct task_struct* first,
                     struct task_struct* second);
 
-int edf_ready_order(struct list_head* a, struct list_head* b);
-
 int  edf_preemption_needed(rt_domain_t* rt, struct task_struct *t);
 
 int edf_set_hp_task(struct pi_semaphore *sem);
diff --git a/include/litmus/heap.h b/include/litmus/heap.h
new file mode 100644
index 0000000000..b26804f879
--- /dev/null
+++ b/include/litmus/heap.h
@@ -0,0 +1,301 @@
+/* heaps.h -- Binomial Heaps
+ *
+ * (c) 2008 Bjoern Brandenburg
+ */
+
+#ifndef HEAP_H
+#define HEAP_H
+
+#define NOT_IN_HEAP UINT_MAX
+
+struct heap_node {
+        struct heap_node*       parent;
+        struct heap_node*       next;
+        struct heap_node*       child;
+
+        unsigned int            degree;
+        void*                   value;
+        struct heap_node**      ref;
+};
+
+struct heap {
+        struct heap_node*       head;
+        /* We cache the minimum of the heap.
+         * This speeds up repeated peek operations.
+         */
+        struct heap_node*       min;
+};
+
+typedef int (*heap_prio_t)(struct heap_node* a, struct heap_node* b);
+
+static inline void heap_init(struct heap* heap)
+{
+        heap->head = NULL;
+        heap->head = NULL;
+}
+
+static inline void heap_node_init(struct heap_node** _h, void* value)
+{
+        struct heap_node* h = *_h;
+        h->parent = NULL;
+        h->next   = NULL;
+        h->child  = NULL;
+        h->degree = NOT_IN_HEAP;
+        h->value  = value;
+        h->ref    = _h;
+}
+
+static inline int heap_node_in_heap(struct heap_node* h)
+{
+        return h->degree != NOT_IN_HEAP;
+}
+
+static inline int heap_empty(struct heap* heap)
+{
+        return heap->head == NULL && heap->min == NULL;
+}
+
+/* make child a subtree of root */
+static inline void __heap_link(struct heap_node* root,
+                               struct heap_node* child)
+{
+        child->parent = root;
+        child->next   = root->child;
+        root->child   = child;
+        root->degree++;
+}
+
+/* merge root lists */
+static inline struct heap_node* __heap_merge(struct heap_node* a,
+                                             struct heap_node* b)
+{
+        struct heap_node* head = NULL;
+        struct heap_node** pos = &head;
+
+        while (a && b) {
+                if (a->degree < b->degree) {
+                        *pos = a;
+                        a = a->next;
+                } else {
+                        *pos = b;
+                        b = b->next;
+                }
+                pos = &(*pos)->next;
+        }
+        if (a)
+                *pos = a;
+        else
+                *pos = b;
+        return head;
+}
+
+/* reverse a linked list of nodes. also clears parent pointer */
+static inline struct heap_node* __heap_reverse(struct heap_node* h)
+{
+        struct heap_node* tail = NULL;
+        struct heap_node* next;
+
+        if (!h)
+                return h;
+
+        h->parent = NULL;
+        while (h->next) {
+                next    = h->next;
+                h->next = tail;
+                tail    = h;
+                h       = next;
+                h->parent = NULL;
+        }
+        h->next = tail;
+        return h;
+}
+
+static inline void __heap_min(heap_prio_t higher_prio, struct heap* heap,
+                              struct heap_node** prev, struct heap_node** node)
+{
+        struct heap_node *_prev, *cur;
+        *prev = NULL;
+
+        if (!heap->head) {
+                *node = NULL;
+                return;
+        }
+
+        *node = heap->head;
+        _prev = heap->head;
+        cur   = heap->head->next;
+        while (cur) {
+                if (higher_prio(cur, *node)) {
+                        *node = cur;
+                        *prev = _prev;
+                }
+                _prev = cur;
+                cur   = cur->next;
+        }
+}
+
+static inline void __heap_union(heap_prio_t higher_prio, struct heap* heap,
+                                struct heap_node* h2)
+{
+        struct heap_node* h1;
+        struct heap_node *prev, *x, *next;
+        if (!h2)
+                return;
+        h1 = heap->head;
+        if (!h1) {
+                heap->head = h2;
+                return;
+        }
+        h1 = __heap_merge(h1, h2);
+        prev = NULL;
+        x    = h1;
+        next = x->next;
+        while (next) {
+                if (x->degree != next->degree ||
+                    (next->next && next->next->degree == x->degree)) {
+                        /* nothing to do, advance */
+                        prev = x;
+                        x    = next;
+                } else if (higher_prio(x, next)) {
+                        /* x becomes the root of next */
+                        x->next = next->next;
+                        __heap_link(x, next);
+                } else {
+                        /* next becomes the root of x */
+                        if (prev)
+                                prev->next = next;
+                        else
+                                h1 = next;
+                        __heap_link(next, x);
+                        x = next;
+                }
+                next = x->next;
+        }
+        heap->head = h1;
+}
+
+static inline struct heap_node* __heap_extract_min(heap_prio_t higher_prio,
+                                                   struct heap* heap)
+{
+        struct heap_node *prev, *node;
+        __heap_min(higher_prio, heap, &prev, &node);
+        if (!node)
+                return NULL;
+        if (prev)
+                prev->next = node->next;
+        else
+                heap->head = node->next;
+        __heap_union(higher_prio, heap, __heap_reverse(node->child));
+        return node;
+}
+
+/* insert (and reinitialize) a node into the heap */
+static inline void heap_insert(heap_prio_t higher_prio, struct heap* heap,
+                               struct heap_node* node)
+{
+        struct heap_node *min;
+        node->child  = NULL;
+        node->parent = NULL;
+        node->next   = NULL;
+        node->degree = 0;
+        if (heap->min && higher_prio(node, heap->min)) {
+                /* swap min cache */
+                min = heap->min;
+                min->child  = NULL;
+                min->parent = NULL;
+                min->next   = NULL;
+                min->degree = 0;
+                __heap_union(higher_prio, heap, min);
+                heap->min   = node;
+        } else
+                __heap_union(higher_prio, heap, node);
+}
+
+static inline void __uncache_min(heap_prio_t higher_prio, struct heap* heap)
+{
+        struct heap_node* min;
+        if (heap->min) {
+                min = heap->min;
+                heap->min = NULL;
+                heap_insert(higher_prio, heap, min);
+        }
+}
+
+/* merge addition into target */
+static inline void heap_union(heap_prio_t higher_prio,
+                              struct heap* target, struct heap* addition)
+{
+        /* first insert any cached minima, if necessary */
+        __uncache_min(higher_prio, target);
+        __uncache_min(higher_prio, addition);
+        __heap_union(higher_prio, target, addition->head);
+        /* this is a destructive merge */
+        addition->head = NULL;
+}
+
+static inline struct heap_node* heap_peek(heap_prio_t higher_prio,
+                                          struct heap* heap)
+{
+        if (!heap->min)
+                heap->min = __heap_extract_min(higher_prio, heap);
+        return heap->min;
+}
+
+static inline struct heap_node* heap_take(heap_prio_t higher_prio,
+                                          struct heap* heap)
+{
+        struct heap_node *node;
+        if (!heap->min)
+                heap->min = __heap_extract_min(higher_prio, heap);
+        node = heap->min;
+        heap->min = NULL;
+        if (node)
+                node->degree = NOT_IN_HEAP;
+        return node;
+}
+
+static inline void heap_delete(heap_prio_t higher_prio, struct heap* heap,
+                               struct heap_node* node)
+{
+        struct heap_node *parent, *prev, *pos;
+        struct heap_node** tmp_ref;
+        void* tmp;
+
+        if (heap->min != node) {
+                /* bubble up */
+                parent = node->parent;
+                while (parent) {
+                        /* swap parent and node */
+                        tmp           = parent->value;
+                        parent->value = node->value;
+                        node->value   = tmp;
+                        /* swap references */
+                        *(parent->ref) = node;
+                        *(node->ref)   = parent;
+                        tmp_ref        = parent->ref;
+                        parent->ref    = node->ref;
+                        node->ref      = tmp_ref;
+                        /* step up */
+                        node   = parent;
+                        parent = node->parent;
+                }
+                /* now delete:
+                 * first find prev */
+                prev = NULL;
+                pos  = heap->head;
+                while (pos != node) {
+                        prev = pos;
+                        pos  = pos->next;
+                }
+                /* we have prev, now remove node */
+                if (prev)
+                        prev->next = node->next;
+                else
+                        heap->head = node->next;
+                __heap_union(higher_prio, heap, __heap_reverse(node->child));
+        } else
+                heap->min = NULL;
+        node->degree = NOT_IN_HEAP;
+}
+
+#endif
diff --git a/include/litmus/litmus.h b/include/litmus/litmus.h
index bd92f44030..ca9d3c8d88 100644
--- a/include/litmus/litmus.h
+++ b/include/litmus/litmus.h
@@ -181,4 +181,6 @@ static inline lt_t litmus_clock(void)
 
 void srp_ceiling_block(void);
 
+#define heap2task(hn) ((struct task_struct*) hn->value)
+
 #endif
diff --git a/include/litmus/rt_domain.h b/include/litmus/rt_domain.h
index 6489b0c0fd..47cd123b76 100644
--- a/include/litmus/rt_domain.h
+++ b/include/litmus/rt_domain.h
@@ -6,6 +6,7 @@
 #define __UNC_RT_DOMAIN_H__
 
 #include <litmus/norqlock.h>
+#include <litmus/heap.h>
 
 struct _rt_domain;
 
@@ -17,7 +18,7 @@ typedef struct _rt_domain {
 
         /* runnable rt tasks are in here */
         spinlock_t                      ready_lock;
-        struct list_head                ready_queue;
+        struct heap                     ready_queue;
 
         /* real-time tasks waiting for release are in here */
         spinlock_t                      release_lock;
@@ -30,24 +31,52 @@ typedef struct _rt_domain {
         release_job_t                   release_job;
 
         /* how are tasks ordered in the ready queue? */
-        list_cmp_t                      order;
+        heap_prio_t                     order;
 } rt_domain_t;
 
-#define next_ready(rt) \
-        (list_entry((rt)->ready_queue.next, struct task_struct, rt_list))
-
-#define ready_jobs_pending(rt) \
-        (!list_empty(&(rt)->ready_queue))
+static inline struct task_struct* __next_ready(rt_domain_t* rt)
+{
+        struct heap_node *hn = heap_peek(rt->order, &rt->ready_queue);
+        if (hn)
+                return heap2task(hn);
+        else
+                return NULL;
+}
 
-void rt_domain_init(rt_domain_t *rt, list_cmp_t order, 
+void rt_domain_init(rt_domain_t *rt, heap_prio_t order,
                     check_resched_needed_t check,
                     release_job_t relase);
 
 void __add_ready(rt_domain_t* rt, struct task_struct *new);
 void __add_release(rt_domain_t* rt, struct task_struct *task);
 
-struct task_struct* __take_ready(rt_domain_t* rt);
-struct task_struct* __peek_ready(rt_domain_t* rt);
+static inline struct task_struct* __take_ready(rt_domain_t* rt)
+{
+        struct heap_node* hn = heap_take(rt->order, &rt->ready_queue);
+        if (hn)
+                return heap2task(hn);
+        else
+                return NULL;
+}
+
+static inline struct task_struct* __peek_ready(rt_domain_t* rt)
+{
+        struct heap_node* hn = heap_peek(rt->order, &rt->ready_queue);
+        if (hn)
+                return heap2task(hn);
+        else
+                return NULL;
+}
+
+static inline int  is_queued(struct task_struct *t)
+{
+        return heap_node_in_heap(tsk_rt(t)->heap_node);
+}
+
+static inline void remove(rt_domain_t* rt, struct task_struct *t)
+{
+        heap_delete(rt->order, &rt->ready_queue, tsk_rt(t)->heap_node);
+}
 
 static inline void add_ready(rt_domain_t* rt, struct task_struct *new)
 {
@@ -81,7 +110,7 @@ static inline void add_release(rt_domain_t* rt, struct task_struct *task)
 
 static inline int __jobs_pending(rt_domain_t* rt)
 {
-        return !list_empty(&rt->ready_queue);
+        return !heap_empty(&rt->ready_queue);
 }
 
 static inline int jobs_pending(rt_domain_t* rt)
@@ -90,7 +119,7 @@ static inline int jobs_pending(rt_domain_t* rt)
         int ret;
         /* first we need the write lock for rt_ready_queue */
         spin_lock_irqsave(&rt->ready_lock, flags);
-        ret = __jobs_pending(rt);
+        ret = !heap_empty(&rt->ready_queue);
         spin_unlock_irqrestore(&rt->ready_lock, flags);
         return ret;
 }
diff --git a/include/litmus/rt_param.h b/include/litmus/rt_param.h
index a5e939daa5..a7dd67a81a 100644
--- a/include/litmus/rt_param.h
+++ b/include/litmus/rt_param.h
@@ -39,6 +39,7 @@ struct rt_task {
 #ifdef __KERNEL__
 
 struct _rt_domain;
+struct heap_node;
 
 struct rt_job {
         /* Time instant the the job was or will be released.  */
@@ -139,6 +140,22 @@ struct rt_param {
 
         /* ready queue for this task */
         struct _rt_domain* domain;
+
+        /* heap element for this task
+         *
+         * Warning: Don't statically allocate this node. The heap
+         *          implementation swaps these between tasks, thus after
+         *          dequeuing from a heap you may end up with a different node
+         *          then the one you had when enqueuing the task.  For the same
+         *          reason, don't obtain and store references to this node
+         *          other than this pointer (which is updated by the heap
+         *          implementation).
+         */
+        struct heap_node*       heap_node;
+
+        /* Used by rt_domain to queue task in release list.
+         */
+        struct list_head list;
 };
 
 /*      Possible RT flags       */
diff --git a/litmus/edf_common.c b/litmus/edf_common.c
index 68c6a401af..d7567ac98e 100644
--- a/litmus/edf_common.c
+++ b/litmus/edf_common.c
@@ -60,11 +60,9 @@ int edf_higher_prio(struct task_struct* first,
                  !second->rt_param.inh_task)));
 }
 
-int edf_ready_order(struct list_head* a, struct list_head* b)
+int edf_ready_order(struct heap_node* a, struct heap_node* b)
 {
-        return edf_higher_prio(
-                list_entry(a, struct task_struct, rt_list),
-                list_entry(b, struct task_struct, rt_list));
+        return edf_higher_prio(heap2task(a), heap2task(b));
 }
 
 void edf_domain_init(rt_domain_t* rt, check_resched_needed_t resched,
@@ -81,7 +79,7 @@ int edf_preemption_needed(rt_domain_t* rt, struct task_struct *t)
 {
         /* we need the read lock for edf_ready_queue */
         /* no need to preempt if there is nothing pending */
-        if (!ready_jobs_pending(rt))
+        if (!__jobs_pending(rt))
                 return 0;
         /* we need to reschedule if t doesn't exist */
         if (!t)
@@ -92,5 +90,5 @@ int edf_preemption_needed(rt_domain_t* rt, struct task_struct *t)
          */
 
         /* make sure to get non-rt stuff out of the way */
-        return !is_realtime(t) || edf_higher_prio(next_ready(rt), t);
+        return !is_realtime(t) || edf_higher_prio(__next_ready(rt), t);
 }
diff --git a/litmus/litmus.c b/litmus/litmus.c
index 2084bb7de8..0dec4342ba 100644
--- a/litmus/litmus.c
+++ b/litmus/litmus.c
@@ -7,12 +7,14 @@
 
 #include <linux/module.h>
 #include <linux/proc_fs.h>
-
+#include <linux/slab.h>
 
 #include <litmus/litmus.h>
 #include <linux/sched.h>
 #include <litmus/sched_plugin.h>
 
+#include <litmus/heap.h>
+
 #include <litmus/trace.h>
 
 /* Number of RT tasks that exist in the system */
@@ -28,6 +30,8 @@ atomic_t __log_seq_no = ATOMIC_INIT(0);
 static LIST_HEAD(sched_sig_list);
 static DEFINE_SPINLOCK(sched_sig_list_lock);
 
+static struct kmem_cache * heap_node_cache;
+
 /*
  * sys_set_task_rt_param
  * @pid: Pid of the task which scheduling parameters must be changed
@@ -503,14 +507,22 @@ long litmus_admit_task(struct task_struct* tsk)
                 return -EINVAL;
         }
 
-        INIT_LIST_HEAD(&tsk->rt_list);
+        INIT_LIST_HEAD(&tsk_rt(tsk)->list);
 
         /* avoid scheduler plugin changing underneath us */
         spin_lock_irqsave(&task_transition_lock, flags);
         retval = litmus->admit_task(tsk);
 
+        /* allocate heap node for this task */
+        tsk_rt(tsk)->heap_node = kmem_cache_alloc(heap_node_cache, GFP_ATOMIC);
+        if (!tsk_rt(tsk)->heap_node)
+                retval = -ENOMEM;
+        else
+                heap_node_init(&tsk_rt(tsk)->heap_node, tsk);
+
         if (!retval)
                 atomic_inc(&rt_task_count);
+
         spin_unlock_irqrestore(&task_transition_lock, flags);
 
         return retval;
@@ -521,6 +533,8 @@ void litmus_exit_task(struct task_struct* tsk)
 {
         if (is_realtime(tsk)) {
                 litmus->task_exit(tsk);
+                BUG_ON(heap_node_in_heap(tsk_rt(tsk)->heap_node));
+                kmem_cache_free(heap_node_cache, tsk_rt(tsk)->heap_node);
                 atomic_dec(&rt_task_count);
                 reinit_litmus_state(tsk, 1);
         }
@@ -771,6 +785,10 @@ static int __init _init_litmus(void)
 
         register_sched_plugin(&linux_sched_plugin);
 
+        heap_node_cache = KMEM_CACHE(heap_node, 0);
+        if (!heap_node_cache)
+                return -ENOMEM;
+
 #ifdef CONFIG_MAGIC_SYSRQ
         /* offer some debugging help */
         if (!register_sysrq_key('q', &sysrq_kill_rt_tasks_op))
@@ -787,6 +805,7 @@ static int __init _init_litmus(void)
 static void _exit_litmus(void)
 {
         exit_litmus_proc();
+        kmem_cache_destroy(heap_node_cache);
 }
 
 module_init(_init_litmus);
diff --git a/litmus/rt_domain.c b/litmus/rt_domain.c
index 0134947ee6..b85bb9e38d 100644
--- a/litmus/rt_domain.c
+++ b/litmus/rt_domain.c
@@ -22,7 +22,7 @@ static int dummy_resched(rt_domain_t *rt)
         return 0;
 }
 
-static int dummy_order(struct list_head* a, struct list_head* b)
+static int dummy_order(struct heap_node* a, struct heap_node* b)
 {
         return 0;
 }
@@ -75,7 +75,7 @@ static void arm_release_timers(unsigned long _rt)
         spin_unlock_irqrestore(&rt->release_lock, flags);
         
         list_for_each_safe(pos, safe, &alt) {
-                t = list_entry(pos, struct task_struct, rt_list);
+                t = list_entry(pos, struct task_struct, rt_param.list);
                 list_del(pos);
                 setup_job_release_timer(t);
         }
@@ -83,7 +83,7 @@ static void arm_release_timers(unsigned long _rt)
 
 
 void rt_domain_init(rt_domain_t *rt,
-                    list_cmp_t order,
+                    heap_prio_t order,
                     check_resched_needed_t check,
                     release_job_t release
                    )
@@ -95,7 +95,7 @@ void rt_domain_init(rt_domain_t *rt,
                 release = default_release_job;
         if (!order)
                 order = dummy_order;
-        INIT_LIST_HEAD(&rt->ready_queue);
+        heap_init(&rt->ready_queue);
         INIT_LIST_HEAD(&rt->release_queue);
         spin_lock_init(&rt->ready_lock);
         spin_lock_init(&rt->release_lock);
@@ -114,26 +114,10 @@ void __add_ready(rt_domain_t* rt, struct task_struct *new)
               new->comm, new->pid, get_exec_cost(new), get_rt_period(new),
               get_release(new), litmus_clock());
 
-        if (!list_insert(&new->rt_list, &rt->ready_queue, rt->order))
-                rt->check_resched(rt);
-}
-
-struct task_struct* __take_ready(rt_domain_t* rt)
-{
-        struct task_struct *t = __peek_ready(rt);
+        BUG_ON(heap_node_in_heap(tsk_rt(new)->heap_node));
 
-        /* kick it out of the ready list */
-        if (t)
-                list_del(&t->rt_list);
-        return t;
-}
-
-struct task_struct* __peek_ready(rt_domain_t* rt)
-{
-        if (!list_empty(&rt->ready_queue))
-                return next_ready(rt);
-        else
-                return NULL;
+        heap_insert(rt->order, &rt->ready_queue, tsk_rt(new)->heap_node);
+        rt->check_resched(rt);
 }
 
 /* add_release - add a real-time task to the rt release queue.
@@ -142,7 +126,7 @@ struct task_struct* __peek_ready(rt_domain_t* rt)
 void __add_release(rt_domain_t* rt, struct task_struct *task)
 {
         TRACE_TASK(task, "add_release(), rel=%llu\n", get_release(task));
-        list_add(&task->rt_list, &rt->release_queue);
+        list_add(&tsk_rt(task)->list, &rt->release_queue);
         task->rt_param.domain = rt;
         do_without_rqlock(&rt->arm_timers);
 }
diff --git a/litmus/sched_cedf.c b/litmus/sched_cedf.c
index 2cfa0b38ac..bc29ca4ed4 100755
--- a/litmus/sched_cedf.c
+++ b/litmus/sched_cedf.c
@@ -43,7 +43,7 @@
  *                                will link NULL to that CPU. If it is
  *                                currently queued in the cedf queue for
  *                                a partition, it will be removed from
- *                                the T->rt_list. It is safe to call
+ *                                the rt_domain. It is safe to call
  *                                unlink(T) if T is not linked. T may not
  *                                be NULL.
  *
@@ -250,7 +250,7 @@ static noinline void unlink(struct task_struct* t)
                 entry = &per_cpu(cedf_cpu_entries, t->rt_param.linked_on);
                 t->rt_param.linked_on = NO_CPU;
                 link_task_to_cpu(NULL, entry);
-        } else if (in_list(&t->rt_list)) {
+        } else if (is_queued(t)) {
                 /* This is an interesting situation: t is scheduled,
                  * but was just recently unlinked.  It cannot be
                  * linked anywhere else (because then it would have
@@ -258,7 +258,7 @@ static noinline void unlink(struct task_struct* t)
                  * queue. We must remove it from the list in this
                  * case.
                  */
-                list_del(&t->rt_list);
+                remove(task_edf(t), t);
         }
 }
 
@@ -298,7 +298,7 @@ static noinline void requeue(struct task_struct* task)
 
         BUG_ON(!task);
         /* sanity check rt_list before insertion */
-        BUG_ON(in_list(&task->rt_list));
+        BUG_ON(is_queued(task));
 
         /* Get correct real-time domain. */
         cedf = task_cedf(task);
@@ -625,8 +625,6 @@ static void cedf_task_block(struct task_struct *t)
         spin_unlock_irqrestore(&task_cedf(t)->slock, flags);
 
         BUG_ON(!is_realtime(t));
-        BUG_ON(t->rt_list.next != LIST_POISON1);
-        BUG_ON(t->rt_list.prev != LIST_POISON2);
 }
 
 static void cedf_task_exit(struct task_struct * t)
@@ -642,8 +640,6 @@ static void cedf_task_exit(struct task_struct * t)
 
         BUG_ON(!is_realtime(t));
         TRACE_TASK(t, "RIP\n");
-        BUG_ON(t->rt_list.next != LIST_POISON1);
-        BUG_ON(t->rt_list.prev != LIST_POISON2);
 }
 
 static long cedf_admit_task(struct task_struct* tsk)
diff --git a/litmus/sched_gsn_edf.c b/litmus/sched_gsn_edf.c
index 5d61fe053c..fb2200bc93 100644
--- a/litmus/sched_gsn_edf.c
+++ b/litmus/sched_gsn_edf.c
@@ -44,7 +44,7 @@
  *                                structures. If it is linked to some CPU it
  *                                will link NULL to that CPU. If it is
  *                                currently queued in the gsnedf queue it will
- *                                be removed from the T->rt_list. It is safe to
+ *                                be removed from the rt_domain. It is safe to
  *                                call unlink(T) if T is not linked. T may not
  *                                be NULL.
  *
@@ -217,7 +217,7 @@ static noinline void unlink(struct task_struct* t)
                 entry = &per_cpu(gsnedf_cpu_entries, t->rt_param.linked_on);
                 t->rt_param.linked_on = NO_CPU;
                 link_task_to_cpu(NULL, entry);
-        } else if (in_list(&t->rt_list)) {
+        } else if (is_queued(t)) {
                 /* This is an interesting situation: t is scheduled,
                  * but was just recently unlinked.  It cannot be
                  * linked anywhere else (because then it would have
@@ -225,7 +225,7 @@ static noinline void unlink(struct task_struct* t)
                  * queue. We must remove it from the list in this
                  * case.
                  */
-                list_del(&t->rt_list);
+                remove(&gsnedf, t);
         }
 }
 
@@ -261,8 +261,8 @@ static noinline void preempt(cpu_entry_t *entry)
 static noinline void requeue(struct task_struct* task)
 {
         BUG_ON(!task);
-        /* sanity check rt_list before insertion */
-        BUG_ON(in_list(&task->rt_list));
+        /* sanity check before insertion */
+        BUG_ON(is_queued(task));
 
         if (get_rt_flags(task) == RT_F_SLEEP) {
                 /* this task has expired
@@ -573,8 +573,6 @@ static void gsnedf_task_block(struct task_struct *t)
         spin_unlock_irqrestore(&gsnedf_lock, flags);
 
         BUG_ON(!is_realtime(t));
-        BUG_ON(t->rt_list.next != LIST_POISON1);
-        BUG_ON(t->rt_list.prev != LIST_POISON2);
 }
 
 
@@ -589,8 +587,6 @@ static void gsnedf_task_exit(struct task_struct * t)
 
         BUG_ON(!is_realtime(t));
         TRACE_TASK(t, "RIP\n");
-        BUG_ON(t->rt_list.next != LIST_POISON1);
-        BUG_ON(t->rt_list.prev != LIST_POISON2);
 }
 
 static long gsnedf_pi_block(struct pi_semaphore *sem,
diff --git a/litmus/sched_psn_edf.c b/litmus/sched_psn_edf.c
index 290654bb8d..a36a350160 100644
--- a/litmus/sched_psn_edf.c
+++ b/litmus/sched_psn_edf.c
@@ -249,7 +249,7 @@ static void psnedf_task_wake_up(struct task_struct *task)
 
         TRACE_TASK(task, "wake up\n");
         spin_lock_irqsave(&pedf->slock, flags);
-        BUG_ON(in_list(&task->rt_list));
+        BUG_ON(is_queued(task));
         /* We need to take suspensions because of semaphores into
          * account! If a job resumes after being suspended due to acquiring
          * a semaphore, it should never be treated as a new job release.
@@ -273,19 +273,21 @@ static void psnedf_task_block(struct task_struct *t)
         /* only running tasks can block, thus t is in no queue */
         TRACE_TASK(t, "block, state=%d\n", t->state);
         BUG_ON(!is_realtime(t));
-        BUG_ON(in_list(&t->rt_list));
+        BUG_ON(is_queued(t));
 }
 
 static void psnedf_task_exit(struct task_struct * t)
 {
         unsigned long flags;
         psnedf_domain_t*        pedf = task_pedf(t);
+        rt_domain_t*            edf;
 
         spin_lock_irqsave(&pedf->slock, flags);
-
-        if (in_list(&t->rt_list))
+        if (is_queued(t)) {
                 /* dequeue */
-                list_del(&t->rt_list);
+                edf  = task_edf(t);
+                remove(edf, t);
+        }
         preempt(pedf);
         spin_unlock_irqrestore(&pedf->slock, flags);
 }
@@ -315,10 +317,11 @@ static long psnedf_pi_block(struct pi_semaphore *sem,
                         /* let holder inherit */
                         sem->holder->rt_param.inh_task = new_waiter;
                         t = sem->holder;
-                        if (in_list(&t->rt_list)) {
+                        if (is_queued(t)) {
                                 /* queued in domain*/
-                                list_del(&t->rt_list);
+                                remove(edf, t);
                                 /* readd to make priority change take place */
+                                /* FIXME: this looks outdated */
                                 if (is_released(t, litmus_clock()))
                                         __add_ready(edf, t);
                                 else