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

Use binary heap to track CPU priorities.

2 files changed, 27 insertions, 24 deletions

diff --git a/include/litmus/binheap.h b/include/litmus/binheap.h
index b8dd8e03da60..9fe5dc13d032 100644
--- a/include/litmus/binheap.h
+++ b/include/litmus/binheap.h
@@ -36,7 +36,7 @@ struct binheap_node {
  * Signature of compator function.  Assumed 'less-than' (min-heap).
  * Pass in 'greater-than' for max-heap.
  *
- * TODO: Consider macor-based implementation that allows comparator to be
+ * 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,
@@ -364,7 +364,7 @@ static inline void __binheap_add(struct binheap_node *new_node,
 {
         /* NULL data pointers are used internally */
         if(!data) {
-                WARN();
+                WARN_ON(!data);
                 return;
         }
 
diff --git a/litmus/sched_gsn_edf.c b/litmus/sched_gsn_edf.c
index 6ed504f4750e..549a4dad037d 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, cpu_entry_t, hn);
+        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,10 @@ static void set_priority_inheritance(struct task_struct* t, struct task_struct*
                  * 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, cpu_entry_t, hn);
+                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);
@@ -965,14 +966,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
@@ -1013,14 +1015,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);