1 files changed, 174 insertions, 104 deletions

diff --git a/litmus/sched_edf_hsb.c b/litmus/sched_edf_hsb.c
index a00d1df8ba27..eed7f23352fd 100755
--- a/litmus/sched_edf_hsb.c
+++ b/litmus/sched_edf_hsb.c
@@ -54,6 +54,7 @@ struct cpu_entry {
         int                             cpu;
         struct task_struct*             scheduled;
         struct task_struct*             linked;
+        struct bheap_node*              hn;
 
         /* Used to execute timers on remote CPUs */
         struct hrtimer_start_on_info    budget_timer_info;
@@ -65,10 +66,11 @@ struct cpu_entry {
 /*
  * Forward declarations
  */
-static void link_task_to_cpu(struct task_struct*, struct cpu_entry*);
 static struct task_struct* next_eligible_hrt(struct hrt_server*);
 static void preempt(struct task_struct*, struct cpu_entry*);
 static void requeue(struct task_struct*, rt_domain_t*);
+static struct cpu_entry* lowest_prio_cpu(void);
+static void link_task_to_cpu(struct task_struct*, struct cpu_entry*);
 static void unlink(struct task_struct*, rt_domain_t*);
 static enum hrtimer_restart budget_timer_fire(struct hrtimer*);
 static void timer_cancel(struct hrtimer *timer);
@@ -89,7 +91,9 @@ DEFINE_PER_CPU_SHARED_ALIGNED(struct cpu_entry,  cpu_entries);
 /*
  * Global variables
  */
-static rt_domain_t srt_domain;
+static rt_domain_t  srt_domain;
+static struct bheap cpu_heap;
+static struct bheap_node cpu_heap_node[NR_CPUS];
 
 /*
  * Forces a reschedule on the current cpu if there is an eligible hrt task and
@@ -124,23 +128,21 @@ static void check_for_hrt_preempt(void)
  */
 static void check_for_srt_preempt(void)
 {
-        struct cpu_entry *entry;
+        struct cpu_entry   *entry;
         struct task_struct *next_srt;
-        int cpu;
-
-        for_each_online_cpu(cpu) {
-                entry = &per_cpu(cpu_entries, cpu);
 
-                if ((!entry->linked || is_srt(entry->linked)) &&
-                    edf_preemption_needed(&srt_domain, entry->linked)) {
+        /* Ugly! Fix! Should probably create srt_preemption_needed() */
+        for (entry = lowest_prio_cpu();
+             (!entry->linked || is_srt(entry->linked)) &&
+             edf_preemption_needed(&srt_domain, entry->linked);
+             entry = lowest_prio_cpu()) {
 
-                        next_srt = __take_ready(&srt_domain);
+                next_srt = __take_ready(&srt_domain);
 
-                        TRACE("forcing a reschedule with srt task %d at %llu\n",
-                              next_srt->pid, litmus_clock());
+                TRACE("forcing a reschedule with srt task %d at %llu\n",
+                      next_srt->pid, litmus_clock());
 
-                        preempt(next_srt, entry);
-                }
+                preempt(next_srt, entry);
         }
 }
 
@@ -224,7 +226,6 @@ static noinline void job_completion(struct task_struct *task,
         if (is_running(task))
                 job_arrival(domain, task);
 
-
         if (is_hrt(task)) {
                 BUG_ON(task_cpu(task) != entry->cpu);
 
@@ -233,60 +234,6 @@ static noinline void job_completion(struct task_struct *task,
         }
 }
 
-/*
- * Update the link of a CPU.
- * Handles the case where the to-be-linked task is already scheduled on
- * a different CPU.
- */
-static noinline void link_task_to_cpu(struct task_struct *linked,
-                                      struct cpu_entry *entry)
-{
-        struct cpu_entry *sched;
-        struct task_struct* tmp;
-        int on_cpu;
-
-        BUG_ON(linked && !is_realtime(linked));
-
-        /* Currently linked task is set to be unlinked */
-        if (entry->linked) {
-                entry->linked->rt_param.linked_on = NO_CPU;
-        }
-
-        /* Link new task to CPU */
-        if (linked) {
-                set_rt_flags(linked, RT_F_RUNNING);
-                /* Handle task is already scheduled somewhere! */
-                on_cpu = linked->rt_param.scheduled_on;
-                if (on_cpu != NO_CPU) {
-                        sched = &per_cpu(cpu_entries, on_cpu);
-                        /* This should only happen if not linked already */
-                        BUG_ON(sched->linked == linked);
-
-                        /* If we are already scheduled on the CPU to which we
-                         * wanted to link, we don't need to do the swap --
-                         * we just link ourselves to the CPU and depend on
-                         * the caller to get things right
-                         */
-                        if (entry != sched) {
-                                TRACE_TASK(linked,
-                                           "already scheduled on %d, updating link.\n",
-                                           sched->cpu);
-                                tmp = sched->linked;
-                                linked->rt_param.linked_on = sched->cpu;
-                                sched->linked = linked;
-                                linked = tmp;
-                        }
-                }
-                if (linked) /* Might be NULL due to swap */
-                        linked->rt_param.linked_on = entry->cpu;
-        }
-        entry->linked = linked;
-#ifdef WANT_ALL_SCHED_EVENTS
-        if (linked)
-                TRACE_TASK(linked, "linked to %d.\n", entry->cpu);
-#endif
-}
-
 /* If the server is eligible, return the next eligible job. If
  * the server is ineligible or there are no eligible jobs,
  * returns NULL.
@@ -317,12 +264,15 @@ static struct task_struct* next_eligible_hrt(struct hrt_server *server)
         }
 }
 
+/*
+ * Suspend the current task and force a reschedule, if possible.
+ * If task is NULL, this will still force a reschedule if a preemption
+ * is possible.
+ */
 static void preempt(struct task_struct *task,
                     struct cpu_entry *entry)
 {
         struct task_struct *curr = entry->linked;
-        BUG_ON(!task);
-
 
         if (curr && is_hrt(curr))
                 requeue(curr, &entry->hrt_server.domain);
@@ -371,9 +321,11 @@ static noinline void requeue(struct task_struct *task, rt_domain_t *domain)
         BUG_ON(is_queued(task));
 
         if (is_released(task, litmus_clock())) {
+                TRACE_TASK(task, "requeuing on ready");
                 __add_ready(domain, task);
         } else {
                 /* Task needs to wait until it is released */
+                TRACE_TASK(task, "requeueing on release");
                 add_release(domain, task);
         }
 }
@@ -493,6 +445,115 @@ out:
         return rv;
 }
 
+
+/******************************************************************************
+ * CPU linkage methods
+ ******************************************************************************/
+
+static int cpu_lower_prio(struct bheap_node *_a, struct bheap_node *_b)
+{
+        int rv;
+        struct cpu_entry *first, *second;
+        struct task_struct *a, *b;
+
+        /* Clumsy, are casts allowed? */
+        first  = _a->value;
+        second = _b->value;
+        a = first->linked;
+        b = second->linked;
+
+        /* Note that a and b are inverted: we want the lowest-priority CPU at
+         * the top of the heap.
+         */
+        if (a && b) {
+                if (is_hrt(a) && is_srt(b)) {
+                        rv = 0;
+                        goto out;
+                } else if (is_hrt(b) && is_srt(a)) {
+                        rv = 1;
+                        goto out;
+                }
+        }
+
+        rv = edf_higher_prio(b, a);
+ out:
+        return rv;
+}
+
+/*
+ * Move the cpu entry to the correct place in the global cpu queue.
+ */
+static void update_cpu_position(struct cpu_entry* entry)
+{
+        if (bheap_node_in_heap(entry->hn))
+                bheap_delete(cpu_lower_prio, &cpu_heap, entry->hn);
+        bheap_insert(cpu_lower_prio, &cpu_heap, entry->hn);
+}
+
+/* Caller must hold global lock lock */
+static struct cpu_entry* lowest_prio_cpu(void)
+{
+        struct bheap_node  *hn;
+        hn = bheap_peek(cpu_lower_prio, &cpu_heap);
+        return hn->value;
+}
+
+/*
+ * Update the link of a CPU.
+ * Handles the case where the to-be-linked task is already scheduled on
+ * a different CPU.
+ */
+static noinline void link_task_to_cpu(struct task_struct *linked,
+                                      struct cpu_entry *entry)
+{
+        struct cpu_entry *sched;
+        struct task_struct* tmp;
+        int on_cpu;
+
+        BUG_ON(linked && !is_realtime(linked));
+
+        /* Currently linked task is set to be unlinked */
+        if (entry->linked) {
+                entry->linked->rt_param.linked_on = NO_CPU;
+        }
+
+        /* Link new task to CPU */
+        if (linked) {
+                set_rt_flags(linked, RT_F_RUNNING);
+                /* Handle task is already scheduled somewhere! */
+                on_cpu = linked->rt_param.scheduled_on;
+                if (on_cpu != NO_CPU) {
+                        sched = &per_cpu(cpu_entries, on_cpu);
+                        /* This should only happen if not linked already */
+                        BUG_ON(sched->linked == linked);
+
+                        /* If we are already scheduled on the CPU to which we
+                         * wanted to link, we don't need to do the swap --
+                         * we just link ourselves to the CPU and depend on
+                         * the caller to get things right
+                         */
+                        if (entry != sched) {
+                                TRACE_TASK(linked,
+                                           "already scheduled on %d, updating link.\n",
+                                           sched->cpu);
+                                tmp = sched->linked;
+                                linked->rt_param.linked_on = sched->cpu;
+                                sched->linked = linked;
+                                update_cpu_position(sched);
+                                linked = tmp;
+                        }
+                }
+                if (linked) /* Might be NULL due to swap */
+                        linked->rt_param.linked_on = entry->cpu;
+        }
+        entry->linked = linked;
+
+        if (linked)
+                TRACE_TASK(linked, "linked to %d.\n", entry->cpu);
+
+        update_cpu_position(entry);
+}
+
 static noinline void unlink(struct task_struct *task, rt_domain_t *domain)
 {
         struct cpu_entry  *entry;
@@ -523,7 +584,6 @@ static noinline void unlink(struct task_struct *task, rt_domain_t *domain)
         }
 }
 
-
 /******************************************************************************
  * Timer methods
  ******************************************************************************/
@@ -629,8 +689,11 @@ static enum hrtimer_restart budget_timer_fire(struct hrtimer *timer)
                 /* Need to preempt the currently running hrt task because
                  * its server has run out of time.
                  */
+                raw_spin_lock_irqsave(&srt_domain.ready_lock, flags);
                 next = take_next_ready(entry);
                 preempt(next, entry);
+                raw_spin_unlock_irqrestore(&srt_domain.ready_lock, flags);
+
         } else {
                 /* If the budget isn't 0, a task just finished executing */
                 litmus_reschedule_local();
@@ -677,7 +740,8 @@ static enum hrtimer_restart refill_timer_fire(struct hrtimer *timer)
         TRACE("refill timer fired on cpu %d at litmus time: %llu\n",
                         entry->cpu, litmus_clock());
 
-        local_irq_save(flags);
+        /*local_irq_save(flags);*/
+        raw_spin_lock_irqsave(&srt_domain.ready_lock, flags);
 
         server->budget = server->wcet;
         server->deadline += server->period;
@@ -692,14 +756,15 @@ static enum hrtimer_restart refill_timer_fire(struct hrtimer *timer)
         hrtimer_set_expires(timer, ns_to_ktime(server->deadline));
 
         /* Activate scheduler, if necessary */
-        if (curr && is_hrt(curr) && is_eligible(curr, server)) {
+        if (curr && is_hrt(curr) && !is_eligible(curr, server)) {
                 next = take_next_ready(entry);
                 preempt(next, entry);
         } else {
                 check_for_hrt_preempt();
         }
 
-        local_irq_restore(flags);
+        /*local_irq_restore(flags);*/
+        raw_spin_unlock_irqrestore(&srt_domain.ready_lock, flags);
 
         return HRTIMER_RESTART;
 }
@@ -742,7 +807,9 @@ static enum hrtimer_restart slack_timer_fire(struct hrtimer *timer)
         struct cpu_entry  *entry  = &__get_cpu_var(cpu_entries);
         struct hrt_server *server = &entry->hrt_server;
 
-        local_irq_save(flags);
+        /*local_irq_save(flags);*/
+        raw_spin_lock_irqsave(&srt_domain.ready_lock, flags);
+
         server->no_slack = 1;
 
         TRACE("slack timer fired at litmus time: %llu\n", litmus_clock());
@@ -750,7 +817,8 @@ static enum hrtimer_restart slack_timer_fire(struct hrtimer *timer)
         /* activate scheduler, if necessary */
         check_for_hrt_preempt();
 
-        local_irq_restore(flags);
+        /*local_irq_restore(flags);*/
+        raw_spin_unlock_irqrestore(&srt_domain.ready_lock, flags);
 
         return HRTIMER_NORESTART;
 }
@@ -770,7 +838,7 @@ static enum hrtimer_restart slack_timer_fire(struct hrtimer *timer)
 static long edf_hsb_activate_plugin(void)
 {
         lt_t slack_fire, common_server_start = litmus_clock();
-        struct cpu_entry *cpu_entry;
+        struct cpu_entry *entry;
         struct hrt_server* server;
         long rv = 0;
         int  cpu;
@@ -782,10 +850,16 @@ static long edf_hsb_activate_plugin(void)
                 goto out;
         }
 
+        bheap_init(&cpu_heap);
+
         for_each_online_cpu(cpu) {
-                cpu_entry = &per_cpu(cpu_entries, cpu);
-                server = &cpu_entry->hrt_server;
+                entry = &per_cpu(cpu_entries, cpu);
+
+                entry->hn = &cpu_heap_node[cpu];
+                bheap_node_init(&entry->hn, entry);
+                update_cpu_position(entry);
 
+                server = &entry->hrt_server;
                 server->no_slack = 0;
                 server->deadline = common_server_start + server->period;
                 server->budget = server->wcet;
@@ -794,15 +868,15 @@ static long edf_hsb_activate_plugin(void)
 
                 TRACE("setting up cpu %d to have timer deadline %llu\n",
                                 cpu, server->deadline);
-                hrtimer_start_on(cpu, &cpu_entry->budget_timer_info,
-                                &server->refill_timer,
-                                ns_to_ktime(server->deadline),
-                                HRTIMER_MODE_ABS_PINNED);
+                hrtimer_start_on(cpu, &entry->budget_timer_info,
+                                 &server->refill_timer,
+                                 ns_to_ktime(server->deadline),
+                                 HRTIMER_MODE_ABS_PINNED);
 
-                hrtimer_start_on(cpu, &cpu_entry->slack_timer_info,
+                hrtimer_start_on(cpu, &entry->slack_timer_info,
                                  &server->slack_timer,
                                  ns_to_ktime(slack_fire),
-                                HRTIMER_MODE_ABS_PINNED);
+                                 HRTIMER_MODE_ABS_PINNED);
 
         }
 out:
@@ -974,15 +1048,14 @@ static struct task_struct* edf_hsb_schedule(struct task_struct *prev)
  */
 static void edf_hsb_task_block(struct task_struct *task)
 {
-        struct cpu_entry *entry;
-        struct hrt_server *server = NULL;
-        rt_domain_t       *domain;
+        struct cpu_entry  *entry  = &__get_cpu_var(cpu_entries);
+        struct hrt_server *server = &entry->hrt_server;
+        rt_domain_t       *domain = NULL;
         unsigned long      flags;
 
         TRACE_TASK(task, "block at %llu\n", litmus_clock());
         BUG_ON(!is_realtime(task));
 
-        entry = &__get_cpu_var(cpu_entries);
         /*
          * Which domain should we lock?
          */
@@ -993,7 +1066,7 @@ static void edf_hsb_task_block(struct task_struct *task)
         } else
                 domain = &srt_domain;
 
-        raw_spin_lock_irqsave(&domain->ready_lock, flags);
+        raw_spin_lock_irqsave(&srt_domain.ready_lock, flags);
 
         if (is_hrt(task)) {
                 /* If an hrt task is blocked, we must do the work of the
@@ -1006,7 +1079,7 @@ static void edf_hsb_task_block(struct task_struct *task)
         /* Unlink if the task is linked to a CPU */
         unlink(task, domain);
 
-        raw_spin_unlock_irqrestore(&domain->ready_lock, flags);
+        raw_spin_unlock_irqrestore(&srt_domain.ready_lock, flags);
 }
 
 static void edf_hsb_task_exit(struct task_struct *task)
@@ -1028,9 +1101,9 @@ static void edf_hsb_task_exit(struct task_struct *task)
         }
 
         /* Unlink if the task is linked to a CPU */
-        raw_spin_lock_irqsave(&domain->ready_lock, flags);
+        raw_spin_lock_irqsave(&srt_domain.ready_lock, flags);
         unlink(task, domain);
-        raw_spin_unlock_irqrestore(&domain->ready_lock, flags);
+        raw_spin_unlock_irqrestore(&srt_domain.ready_lock, flags);
 
         entry->scheduled = NULL;
 }
@@ -1040,17 +1113,14 @@ static void edf_hsb_task_exit(struct task_struct *task)
  */
 static void edf_hsb_task_new(struct task_struct *task, int on_rq,  int running)
 {
-        struct cpu_entry  *entry;
-        struct hrt_server *server;
-        rt_domain_t       *domain;
         unsigned long      flags;
+        rt_domain_t       *domain;
+        struct cpu_entry  *entry  = &per_cpu(cpu_entries, task_cpu(task));
+        struct hrt_server *server = &entry->hrt_server;
 
         TRACE_TASK(task, "edf_hsb: task new, cpu = %d\n",
                    task->rt_param.task_params.cpu);
 
-        entry = &per_cpu(cpu_entries, task_cpu(task));
-        server = &entry->hrt_server;
-
         if (is_hrt(task)) {
                 BUG_ON(task_cpu(task) != entry->cpu);
                 domain = &server->domain;
@@ -1060,7 +1130,7 @@ static void edf_hsb_task_new(struct task_struct *task, int on_rq,  int running)
                 return;
         }
 
-        raw_spin_lock_irqsave(&domain->ready_lock, flags);
+        raw_spin_lock_irqsave(&srt_domain.ready_lock, flags);
 
         /* Setup job parameters */
         release_at(task, litmus_clock());
@@ -1079,7 +1149,7 @@ static void edf_hsb_task_new(struct task_struct *task, int on_rq,  int running)
 
         job_arrival(domain, task);
 
-        raw_spin_unlock_irqrestore(&domain->ready_lock, flags);
+        raw_spin_unlock_irqrestore(&srt_domain.ready_lock, flags);
 }
 
 static void edf_hsb_task_wake_up(struct task_struct *task)
@@ -1102,7 +1172,7 @@ static void edf_hsb_task_wake_up(struct task_struct *task)
                 domain = &srt_domain;
         }
 
-        raw_spin_lock_irqsave(&domain->ready_lock, flags);
+        raw_spin_lock_irqsave(&srt_domain.ready_lock, flags);
 
         /* If job resumes after being suspended due to acquiring a semaphore,
          * it should never be treated as a job release */
@@ -1126,7 +1196,7 @@ static void edf_hsb_task_wake_up(struct task_struct *task)
 
         requeue(task, domain);
 
-        raw_spin_unlock_irqrestore(&domain->ready_lock, flags);
+        raw_spin_unlock_irqrestore(&srt_domain.ready_lock, flags);
 }
 
 /*