C-EDF: Use binary heap instead of binomial heap.

Use binary heap for ordering priority of CPUs.

1 files changed, 18 insertions, 23 deletions

diff --git a/litmus/sched_cedf.c b/litmus/sched_cedf.c
index 480c62bc895b..d498bf39d4df 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, cpu_entry_t, hn);
+        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++;