3 files changed, 578 insertions, 45 deletions

diff --git a/include/litmus/binheap.h b/include/litmus/binheap.h
new file mode 100644
index 000000000000..fd4c0a318b96
--- /dev/null
+++ b/include/litmus/binheap.h
@@ -0,0 +1,536 @@
+#ifndef LITMUS_BINARY_HEAP_H
+#define LITMUS_BINARY_HEAP_H
+
+/**
+ * Simple binary heap with add, arbitrary delete, delete_root, and top
+ * operations.
+ *
+ * Style meant to conform with list.h.
+ *
+ * Motivation: Linux's prio_heap.h is of fixed size. Litmus's binomial
+ * heap may be overkill (and perhaps not general enough) for some applications.
+ *
+ * Note: In order to make node swaps fast, a node inserted with a data pointer
+ * may not always hold said data pointer. This is similar to the binomial heap
+ * implementation. This does make node deletion tricky since we have to
+ * (1) locate the node that holds the data pointer to delete, and (2) the
+ * node that was originally inserted with said data pointer. These have to be
+ * coalesced into a single node before removal (see usage of
+ * __binheap_safe_swap()). We have to track node references to accomplish this.
+ */
+
+struct binheap_node {
+        void    *data;
+        struct binheap_node *parent;
+        struct binheap_node *left;
+        struct binheap_node *right;
+
+        /* pointer to binheap_node that holds *data for which this binheap_node
+         * was originally inserted.  (*data "owns" this node)
+         */
+        struct binheap_node *ref;
+        struct binheap_node **ref_ptr;
+};
+
+/**
+ * Signature of compator function.  Assumed 'less-than' (min-heap).
+ * Pass in 'greater-than' for max-heap.
+ *
+ * TODO: Consider macro-based implementation that allows comparator to be
+ * inlined (similar to Linux red/black tree) for greater efficiency.
+ */
+typedef int (*binheap_order_t)(struct binheap_node *a,
+                                                           struct binheap_node *b);
+
+
+struct binheap_handle {
+        struct binheap_node *root;
+
+        /* pointer to node to take next inserted child */
+        struct binheap_node *next;
+
+        /* pointer to last node in complete binary tree */
+        struct binheap_node *last;
+
+        /* comparator function pointer */
+        binheap_order_t compare;
+};
+
+
+/**
+ * binheap_entry - get the struct for this heap node.
+ *  Only valid when called upon heap nodes other than the root handle.
+ * @ptr:        the heap node.
+ * @type:       the type of struct pointed to by binheap_node::data.
+ * @member:     unused.
+ */
+#define binheap_entry(ptr, type, member) \
+((type *)((ptr)->data))
+
+/**
+ * binheap_node_container - get the struct that contains this node.
+ *  Only valid when called upon heap nodes other than the root handle.
+ * @ptr:        the heap node.
+ * @type:       the type of struct the node is embedded in.
+ * @member:     the name of the binheap_struct within the (type) struct.
+ */
+#define binheap_node_container(ptr, type, member) \
+container_of((ptr), type, member)
+
+/**
+ * binheap_top_entry - get the struct for the node at the top of the heap.
+ *  Only valid when called upon the heap handle node.
+ * @ptr:    the special heap-handle node.
+ * @type:   the type of the struct the head is embedded in.
+ * @member:     the name of the binheap_struct within the (type) struct.
+ */
+#define binheap_top_entry(ptr, type, member) \
+binheap_entry((ptr)->root, type, member)
+
+/**
+ * binheap_delete_root - remove the root element from the heap.
+ * @handle:      handle to the heap.
+ * @type:    the type of the struct the head is embedded in.
+ * @member:      the name of the binheap_struct within the (type) struct.
+ */
+#define binheap_delete_root(handle, type, member) \
+__binheap_delete_root((handle), &((type *)((handle)->root->data))->member)
+
+/**
+ * binheap_delete - remove an arbitrary element from the heap.
+ * @to_delete:  pointer to node to be removed.
+ * @handle:      handle to the heap.
+ */
+#define binheap_delete(to_delete, handle) \
+__binheap_delete((to_delete), (handle))
+
+/**
+ * binheap_add - insert an element to the heap
+ * new_node: node to add.
+ * @handle:      handle to the heap.
+ * @type:    the type of the struct the head is embedded in.
+ * @member:      the name of the binheap_struct within the (type) struct.
+ */
+#define binheap_add(new_node, handle, type, member) \
+__binheap_add((new_node), (handle), container_of((new_node), type, member))
+
+/**
+ * binheap_decrease - re-eval the position of a node (based upon its
+ * original data pointer).
+ * @handle: handle to the heap.
+ * @orig_node: node that was associated with the data pointer
+ *             (whose value has changed) when said pointer was
+ *             added to the heap.
+ */
+#define binheap_decrease(orig_node, handle) \
+__binheap_decrease((orig_node), (handle))
+
+#define BINHEAP_NODE_INIT() { NULL, NULL, NULL, NULL , NULL, NULL}
+
+#define BINHEAP_NODE(name) \
+        struct binheap_node name = BINHEAP_NODE_INIT()
+
+
+static inline void INIT_BINHEAP_NODE(struct binheap_node *n)
+{
+        n->data = NULL;
+        n->parent = NULL;
+        n->left = NULL;
+        n->right = NULL;
+        n->ref = NULL;
+        n->ref_ptr = NULL;
+}
+
+static inline void INIT_BINHEAP_HANDLE(
+        struct binheap_handle *handle,
+        binheap_order_t compare)
+{
+        handle->root = NULL;
+        handle->next = NULL;
+        handle->last = NULL;
+        handle->compare = compare;
+}
+
+/* Returns true (1) if binheap is empty. */
+static inline int binheap_empty(struct binheap_handle *handle)
+{
+        return(handle->root == NULL);
+}
+
+
+/* Update the node reference pointers.  Same logic as Litmus binomial heap. */
+static inline void __update_ref(struct binheap_node *parent,
+                                                                struct binheap_node *child)
+{
+        *(parent->ref_ptr) = child;
+        *(child->ref_ptr) = parent;
+
+        swap(parent->ref_ptr, child->ref_ptr);
+}
+
+/* Swaps data between two nodes. */
+static inline void __binheap_swap(struct binheap_node *parent,
+                                                                  struct binheap_node *child)
+{
+        swap(parent->data, child->data);
+        __update_ref(parent, child);
+}
+
+/* Swaps memory and data between two nodes. Actual nodes swap instead of
+ * just data.  Needed when we delete nodes from the heap.
+ */
+static inline void __binheap_swap_safe(struct binheap_handle *handle,
+                                                                           struct binheap_node *a,
+                                                                           struct binheap_node *b)
+{
+        swap(a->data, b->data);
+        __update_ref(a, b);
+
+        if((a->parent != NULL) && (a->parent == b->parent)) {
+                /* special case: shared parent */
+                swap(a->parent->left, a->parent->right);
+        }
+        else {
+                /* Update pointers to swap parents. */
+
+                if(a->parent) {
+                        if(a == a->parent->left) {
+                                a->parent->left = b;
+                        }
+                        else {
+                                a->parent->right = b;
+                        }
+                }
+
+                if(b->parent) {
+                        if(b == b->parent->left) {
+                                b->parent->left = a;
+                        }
+                        else {
+                                b->parent->right = a;
+                        }
+                }
+
+                swap(a->parent, b->parent);
+        }
+
+        /* swap children */
+
+        if(a->left) {
+                a->left->parent = b;
+
+                if(a->right) {
+                        a->right->parent = b;
+                }
+        }
+
+        if(b->left) {
+                b->left->parent = a;
+
+                if(b->right) {
+                        b->right->parent = a;
+                }
+        }
+
+        swap(a->left, b->left);
+        swap(a->right, b->right);
+
+
+        /* update next/last/root pointers */
+
+        if(a == handle->next) {
+                handle->next = b;
+        }
+        else if(b == handle->next) {
+                handle->next = a;
+        }
+
+        if(a == handle->last) {
+                handle->last = b;
+        }
+        else if(b == handle->last) {
+                handle->last = a;
+        }
+
+        if(a == handle->root) {
+                handle->root = b;
+        }
+        else if(b == handle->root) {
+                handle->root = a;
+        }
+}
+
+
+/**
+ * Update the pointer to the last node in the complete binary tree.
+ * Called internally after the root node has been deleted.
+ */
+static inline void __binheap_update_last(struct binheap_handle *handle)
+{
+        struct binheap_node *temp = handle->last;
+
+        /* find a "bend" in the tree. */
+        while(temp->parent && (temp == temp->parent->left)) {
+                temp = temp->parent;
+        }
+
+        /* step over to sibling if we're not at root */
+        if(temp->parent != NULL) {
+                temp = temp->parent->left;
+        }
+
+        /* now travel right as far as possible. */
+        while(temp->right != NULL) {
+                temp = temp->right;
+        }
+
+        /* take one step to the left if we're not at the bottom-most level. */
+        if(temp->left != NULL) {
+                temp = temp->left;
+        }
+
+        //BUG_ON(!(temp->left == NULL && temp->right == NULL));
+
+        handle->last = temp;
+}
+
+/**
+ * Update the pointer to the node that will take the next inserted node.
+ * Called internally after a node has been inserted.
+ */
+static inline void __binheap_update_next(struct binheap_handle *handle)
+{
+        struct binheap_node *temp = handle->next;
+
+        /* find a "bend" in the tree. */
+        while(temp->parent && (temp == temp->parent->right)) {
+                temp = temp->parent;
+        }
+
+        /* step over to sibling if we're not at root */
+        if(temp->parent != NULL) {
+                temp = temp->parent->right;
+        }
+
+        /* now travel left as far as possible. */
+        while(temp->left != NULL) {
+                temp = temp->left;
+        }
+
+        handle->next = temp;
+}
+
+
+
+/* bubble node up towards root */
+static inline void __binheap_bubble_up(
+        struct binheap_handle *handle,
+        struct binheap_node *node)
+{
+        /* Note: NULL data pointers are used internally for arbitrary delete */
+        while((node->parent != NULL) &&
+                        ((node->data == NULL) /* let null data bubble to the top */ ||
+                         handle->compare(node, node->parent))) {
+                __binheap_swap(node->parent, node);
+                node = node->parent;
+        }
+}
+
+
+/* bubble node down, swapping with min-child */
+static inline void __binheap_bubble_down(struct binheap_handle *handle)
+{
+        struct binheap_node *node = handle->root;
+
+        while(node->left != NULL) {
+                if(node->right && handle->compare(node->right, node->left)) {
+                        if(handle->compare(node->right, node)) {
+                                __binheap_swap(node, node->right);
+                                node = node->right;
+                        }
+                        else {
+                                break;
+                        }
+                }
+                else {
+                        if(handle->compare(node->left, node)) {
+                                __binheap_swap(node, node->left);
+                                node = node->left;
+                        }
+                        else {
+                                break;
+                        }
+                }
+        }
+}
+
+
+
+static inline void __binheap_add(struct binheap_node *new_node,
+                                                                 struct binheap_handle *handle,
+                                                                 void *data)
+{
+        /* NULL data pointers are used internally */
+        if(!data) {
+                WARN_ON(!data);
+                return;
+        }
+
+        new_node->data = data;
+        new_node->ref = new_node;
+        new_node->ref_ptr = &(new_node->ref);
+
+        if(!binheap_empty(handle)) {
+                /* insert left side first */
+                if(handle->next->left == NULL) {
+                        handle->next->left = new_node;
+                        new_node->parent = handle->next;
+                        new_node->left = NULL;
+                        new_node->right = NULL;
+
+                        handle->last = new_node;
+
+                        __binheap_bubble_up(handle, new_node);
+                }
+                else {
+                        /* left occupied. insert right. */
+                        handle->next->right = new_node;
+                        new_node->parent = handle->next;
+                        new_node->left = NULL;
+                        new_node->right = NULL;
+
+                        handle->last = new_node;
+
+                        __binheap_update_next(handle);
+                        __binheap_bubble_up(handle, new_node);
+                }
+        }
+        else {
+                /* first node in heap */
+
+                new_node->parent = NULL;
+                new_node->left = NULL;
+                new_node->right = NULL;
+
+                handle->root = new_node;
+                handle->next = new_node;
+                handle->last = new_node;
+        }
+}
+
+
+
+/**
+ * Removes the root node from the heap. The node is removed after coalescing
+ * the binheap_node with its original data pointer at the root of the tree.
+ *
+ * The 'last' node in the tree is then swapped up to the root and bubbled
+ * down.
+ */
+static inline void __binheap_delete_root(struct binheap_handle *handle,
+                                                                                 struct binheap_node *container)
+{
+        struct binheap_node *root = handle->root;
+
+        if(root != container) {
+                /* coalesce */
+                __binheap_swap_safe(handle, root, container);
+                root = container;
+        }
+
+        if(handle->last != root) {
+                /* swap 'last' node up to root and bubble it down. */
+
+                struct binheap_node *to_move = handle->last;
+
+                if(to_move->parent != root) {
+                        handle->next = to_move->parent;
+
+                        if(handle->next->right == to_move) {
+                                /* disconnect from parent */
+                                to_move->parent->right = NULL;
+                                handle->last = handle->next->left;
+                        }
+                        else {
+                                /* find new 'last' before we disconnect */
+                                __binheap_update_last(handle);
+
+                                /* disconnect from parent */
+                                to_move->parent->left = NULL;
+                        }
+                }
+                else {
+                        /* 'last' is direct child of root */
+
+                        handle->next = to_move;
+
+                        if(to_move == to_move->parent->right) {
+                                to_move->parent->right = NULL;
+                                handle->last = to_move->parent->left;
+                        }
+                        else {
+                                to_move->parent->left = NULL;
+                                handle->last = to_move;
+                        }
+                }
+                to_move->parent = NULL;
+
+                /* reconnect as root.  We can't just swap data ptrs since root node
+                 * may be freed after this function returns.
+                 */
+                to_move->left = root->left;
+                to_move->right = root->right;
+                if(to_move->left != NULL) {
+                        to_move->left->parent = to_move;
+                }
+                if(to_move->right != NULL) {
+                        to_move->right->parent = to_move;
+                }
+
+                handle->root = to_move;
+
+                /* bubble down */
+                __binheap_bubble_down(handle);
+        }
+        else {
+                /* removing last node in tree */
+                handle->root = NULL;
+                handle->next = NULL;
+                handle->last = NULL;
+        }
+}
+
+
+/**
+ * Delete an arbitrary node.  Bubble node to delete up to the root,
+ * and then delete to root.
+ */
+static inline void __binheap_delete(
+                                                                struct binheap_node *node_to_delete,
+                                                                struct binheap_handle *handle)
+{
+        struct binheap_node *target = node_to_delete->ref;
+        void *temp_data = target->data;
+
+        /* temporarily set data to null to allow node to bubble up to the top. */
+        target->data = NULL;
+
+        __binheap_bubble_up(handle, target);
+        __binheap_delete_root(handle, node_to_delete);
+
+        node_to_delete->data = temp_data;  /* restore node data pointer */
+}
+
+/**
+ * Bubble up a node whose pointer has decreased in value.
+ */
+static inline void __binheap_decrease(
+                                struct binheap_node *orig_node,
+                                struct binheap_handle *handle)
+{
+        struct binheap_node *target = orig_node->ref;
+        __binheap_bubble_up(handle, target);
+}
+
+#endif
+
diff --git a/litmus/sched_cedf.c b/litmus/sched_cedf.c
index 480c62bc895b..49653f1ea49d 100644
--- a/litmus/sched_cedf.c
+++ b/litmus/sched_cedf.c
@@ -42,6 +42,7 @@
 #include <litmus/clustered.h>
 
 #include <litmus/bheap.h>
+#include <litmus/binheap.h>
 
 #ifdef CONFIG_SCHED_CPU_AFFINITY
 #include <litmus/affinity.h>
@@ -70,7 +71,9 @@ typedef struct  {
         struct task_struct*     linked;         /* only RT tasks */
         struct task_struct*     scheduled;      /* only RT tasks */
         atomic_t                will_schedule;  /* prevent unneeded IPIs */
-        struct bheap_node*      hn;
+
+        int                             in_heap;                /* == 0/1: not in / in heap*/
+        struct binheap_node hn;
 } cpu_entry_t;
 
 /* one cpu_entry_t per CPU */
@@ -96,8 +99,7 @@ typedef struct clusterdomain {
         /* map of this cluster cpus */
         cpumask_var_t   cpu_map;
         /* the cpus queue themselves according to priority in here */
-        struct bheap_node *heap_node;
-        struct bheap      cpu_heap;
+        struct binheap_handle cpu_heap;
         /* lock for this cluster */
 #define cluster_lock domain.ready_lock
 } cedf_domain_t;
@@ -115,11 +117,11 @@ cedf_domain_t *cedf;
  */
 #define VERBOSE_INIT
 
-static int cpu_lower_prio(struct bheap_node *_a, struct bheap_node *_b)
+static int cpu_lower_prio(struct binheap_node *_a, struct binheap_node *_b)
 {
-        cpu_entry_t *a, *b;
-        a = _a->value;
-        b = _b->value;
+        cpu_entry_t *a = binheap_entry(_a, cpu_entry_t, hn);
+        cpu_entry_t *b = binheap_entry(_b, cpu_entry_t, hn);
+
         /* Note that a and b are inverted: we want the lowest-priority CPU at
          * the top of the heap.
          */
@@ -133,20 +135,16 @@ static void update_cpu_position(cpu_entry_t *entry)
 {
         cedf_domain_t *cluster = entry->cluster;
 
-        if (likely(bheap_node_in_heap(entry->hn)))
-                bheap_delete(cpu_lower_prio,
-                                &cluster->cpu_heap,
-                                entry->hn);
-
-        bheap_insert(cpu_lower_prio, &cluster->cpu_heap, entry->hn);
+        if (likely(entry->in_heap))
+                binheap_delete(&entry->hn, &cluster->cpu_heap);
+        binheap_add(&entry->hn, &cluster->cpu_heap, cpu_entry_t, hn);
+        entry->in_heap = 1;
 }
 
 /* caller must hold cedf lock */
 static cpu_entry_t* lowest_prio_cpu(cedf_domain_t *cluster)
 {
-        struct bheap_node* hn;
-        hn = bheap_peek(cpu_lower_prio, &cluster->cpu_heap);
-        return hn->value;
+        return binheap_top_entry(&cluster->cpu_heap, cpu_entry_t, hn);
 }
 
 
@@ -689,7 +687,6 @@ static void cleanup_cedf(void)
         if (clusters_allocated) {
                 for (i = 0; i < num_clusters; i++) {
                         kfree(cedf[i].cpus);
-                        kfree(cedf[i].heap_node);
                         free_cpumask_var(cedf[i].cpu_map);
                 }
 
@@ -749,10 +746,7 @@ static long cedf_activate_plugin(void)
 
                 cedf[i].cpus = kmalloc(cluster_size * sizeof(cpu_entry_t),
                                 GFP_ATOMIC);
-                cedf[i].heap_node = kmalloc(
-                                cluster_size * sizeof(struct bheap_node),
-                                GFP_ATOMIC);
-                bheap_init(&(cedf[i].cpu_heap));
+                INIT_BINHEAP_HANDLE(&(cedf[i].cpu_heap), cpu_lower_prio);
                 edf_domain_init(&(cedf[i].domain), NULL, cedf_release_jobs);
 
                 if(!zalloc_cpumask_var(&cedf[i].cpu_map, GFP_ATOMIC))
@@ -795,8 +789,9 @@ static long cedf_activate_plugin(void)
                                 atomic_set(&entry->will_schedule, 0);
                                 entry->cpu = ccpu;
                                 entry->cluster = &cedf[i];
-                                entry->hn = &(cedf[i].heap_node[cpu_count]);
-                                bheap_node_init(&entry->hn, entry);
+
+                                INIT_BINHEAP_NODE(&entry->hn);
+                                entry->in_heap = 0;
 
                                 cpu_count++;
 
diff --git a/litmus/sched_gsn_edf.c b/litmus/sched_gsn_edf.c
index 91c38bbf695c..6edcc339ea5e 100644
--- a/litmus/sched_gsn_edf.c
+++ b/litmus/sched_gsn_edf.c
@@ -23,6 +23,7 @@
 #include <litmus/preempt.h>
 
 #include <litmus/bheap.h>
+#include <litmus/binheap.h>
 
 #ifdef CONFIG_SCHED_CPU_AFFINITY
 #include <litmus/affinity.h>
@@ -103,15 +104,15 @@ typedef struct  {
         int                     cpu;
         struct task_struct*     linked;         /* only RT tasks */
         struct task_struct*     scheduled;      /* only RT tasks */
-        struct bheap_node*      hn;
+        int                             in_heap;                /* == 0/1: not in / in heap*/
+        struct binheap_node hn;
 } cpu_entry_t;
 DEFINE_PER_CPU(cpu_entry_t, gsnedf_cpu_entries);
 
 cpu_entry_t* gsnedf_cpus[NR_CPUS];
 
 /* the cpus queue themselves according to priority in here */
-static struct bheap_node gsnedf_heap_node[NR_CPUS];
-static struct bheap      gsnedf_cpu_heap;
+static struct binheap_handle gsnedf_cpu_heap;
 
 static rt_domain_t gsnedf;
 #define gsnedf_lock (gsnedf.ready_lock)
@@ -122,33 +123,33 @@ static rt_domain_t gsnedf;
 #define WANT_ALL_SCHED_EVENTS
  */
 
-static int cpu_lower_prio(struct bheap_node *_a, struct bheap_node *_b)
+static int cpu_lower_prio(struct binheap_node *_a, struct binheap_node *_b)
 {
-        cpu_entry_t *a, *b;
-        a = _a->value;
-        b = _b->value;
+        cpu_entry_t *a = binheap_entry(_a, cpu_entry_t, hn);
+        cpu_entry_t *b = binheap_entry(_b, cpu_entry_t, hn);
+        
         /* Note that a and b are inverted: we want the lowest-priority CPU at
          * the top of the heap.
          */
         return edf_higher_prio(b->linked, a->linked);
 }
 
+
 /* update_cpu_position - Move the cpu entry to the correct place to maintain
  *                       order in the cpu queue. Caller must hold gsnedf lock.
  */
 static void update_cpu_position(cpu_entry_t *entry)
 {
-        if (likely(bheap_node_in_heap(entry->hn)))
-                bheap_delete(cpu_lower_prio, &gsnedf_cpu_heap, entry->hn);
-        bheap_insert(cpu_lower_prio, &gsnedf_cpu_heap, entry->hn);
+        if (likely(entry->in_heap))
+                binheap_delete(&entry->hn, &gsnedf_cpu_heap);
+        binheap_add(&entry->hn, &gsnedf_cpu_heap, cpu_entry_t, hn);
+        entry->in_heap = 1;
 }
 
 /* caller must hold gsnedf lock */
 static cpu_entry_t* lowest_prio_cpu(void)
 {
-        struct bheap_node* hn;
-        hn = bheap_peek(cpu_lower_prio, &gsnedf_cpu_heap);
-        return hn->value;
+        return binheap_top_entry(&gsnedf_cpu_heap, cpu_entry_t, hn);
 }
 
 
@@ -665,10 +666,9 @@ static void increase_priority_inheritance(struct task_struct* t, struct task_str
                  * We can't use heap_decrease() here since
                  * the cpu_heap is ordered in reverse direction, so
                  * it is actually an increase. */
-                bheap_delete(cpu_lower_prio, &gsnedf_cpu_heap,
-                            gsnedf_cpus[linked_on]->hn);
-                bheap_insert(cpu_lower_prio, &gsnedf_cpu_heap,
-                            gsnedf_cpus[linked_on]->hn);
+                binheap_delete(&gsnedf_cpus[linked_on]->hn, &gsnedf_cpu_heap);
+                binheap_add(&gsnedf_cpus[linked_on]->hn,
+                                &gsnedf_cpu_heap, cpu_entry_t, hn);
         } else {
                 /* holder may be queued: first stop queue changes */
                 raw_spin_lock(&gsnedf.release_lock);
@@ -1329,14 +1329,15 @@ static long gsnedf_activate_plugin(void)
         int cpu;
         cpu_entry_t *entry;
 
-        bheap_init(&gsnedf_cpu_heap);
+        INIT_BINHEAP_HANDLE(&gsnedf_cpu_heap, cpu_lower_prio);
 #ifdef CONFIG_RELEASE_MASTER
         gsnedf.release_master = atomic_read(&release_master_cpu);
 #endif
 
         for_each_online_cpu(cpu) {
                 entry = &per_cpu(gsnedf_cpu_entries, cpu);
-                bheap_node_init(&entry->hn, entry);
+                INIT_BINHEAP_NODE(&entry->hn);
+                entry->in_heap   = 0;
                 entry->linked    = NULL;
                 entry->scheduled = NULL;
 #ifdef CONFIG_RELEASE_MASTER
@@ -1377,14 +1378,15 @@ static int __init init_gsn_edf(void)
         int cpu;
         cpu_entry_t *entry;
 
-        bheap_init(&gsnedf_cpu_heap);
+        INIT_BINHEAP_HANDLE(&gsnedf_cpu_heap, cpu_lower_prio);
         /* initialize CPU state */
         for (cpu = 0; cpu < NR_CPUS; cpu++)  {
                 entry = &per_cpu(gsnedf_cpu_entries, cpu);
                 gsnedf_cpus[cpu] = entry;
                 entry->cpu       = cpu;
-                entry->hn        = &gsnedf_heap_node[cpu];
-                bheap_node_init(&entry->hn, entry);
+
+                INIT_BINHEAP_NODE(&entry->hn);
+                entry->in_heap   = 0;
         }
         edf_domain_init(&gsnedf, NULL, gsnedf_release_jobs);
         return register_sched_plugin(&gsn_edf_plugin);