Added a priority heap for the cpus.

This heap is used for SRT preemptions. Without it, odd behavior and unnecessary
scheduling can result. This also forces all locking methods to use the same
lock as link_to_cpu needs to update the queue without worrying about any queue
modification.

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);
 }
 
 /*