Changed candidate queue logic

2 files changed, 84 insertions, 73 deletions

diff --git a/litmus/sched_edf_hsb.c b/litmus/sched_edf_hsb.c
index fd2070c6f94d..d74f4337ac2b 100644
--- a/litmus/sched_edf_hsb.c
+++ b/litmus/sched_edf_hsb.c
@@ -243,7 +243,7 @@ static void remove_slack(server_t *slack)
         if (!slack)
                 return;
         TRACE_SERVER_SUB(slack, "slack removed");
-        //sched_trace_action(NULL, SLACK_EXPIRED_ACTION);
+        //////sched_trace_action(NULL, SLACK_EXPIRED_ACTION);
 
         if (head_in_list(&slack->list))
                 list_del_init(&slack->list);
@@ -288,6 +288,13 @@ static inline struct task_struct* get_candidate(struct list_head *pos)
         return task;
 }
 
+static inline lt_t real_deadline(struct task_struct *task)
+{
+        server_t *server = task_srt_server(task);
+        int job_diff = server->job_no - task_job_no(task);
+        return get_deadline(task) - job_diff * get_rt_period(task);
+}
+
 /*
  * Candidate queue is EDF.
  */
@@ -300,7 +307,7 @@ static void add_slack_candidate(struct task_struct *task)
 
         list_for_each_prev(pos, &slack_candidates) {
                 queued = get_candidate(pos);
-                if (lt_before_eq(get_deadline(queued), get_deadline(task))) {
+                if (lt_before_eq(real_deadline(queued), real_deadline(task))) {
                         __list_add(&task_data(task)->candidate_list,
                                    pos, pos->next);
                         return;
@@ -321,8 +328,6 @@ static void donate_slack(server_t *donator)
                 BUG_ON(!hrt_server->ready);
         }
 
-        BUG_ON(head_in_list(&slack->list));
-
         slack->wcet = donator->budget;
         slack->budget = donator->budget;
         slack->deadline = donator->deadline;
@@ -373,7 +378,7 @@ static noinline void check_donate_slack(server_t *donator, struct task_struct *w
         if (!donate)
                 return;
 
-        sched_trace_action(was_scheduled, SLACK_DONATED_ACTION);
+        ////sched_trace_action(was_scheduled, SLACK_DONATED_ACTION);
 
         donate_slack(donator);
 }
@@ -664,7 +669,7 @@ static void requeue_server(server_t *server, lt_t now)
                         hrt_server->ready = 1;
                         remove_slack(server_slack(server));
                         hrt_server->no_slack = 0;
-                        sched_trace_action(NULL, SERVER_RELEASED_ACTION);
+                        ////sched_trace_action(NULL, SERVER_RELEASED_ACTION);
                 } else if (server->type == S_BE) {
                         TRACE_SERVER_SUB(server, "BE added to ready");
                         bheap_insert(server_order, &be_ready_servers, server->hn);
@@ -686,7 +691,7 @@ static void reclaim_slack(server_t *slack)
                 return;
 
         /* SRT servers do not ever reclaim slack */
-        sched_trace_action(NULL, SLACK_RECLAIM_ACTION);
+        ////sched_trace_action(NULL, SLACK_RECLAIM_ACTION);
 
         exec = slack->wcet - slack->budget;
         TRACE_SERVER_SUB(donator, "reclaiming %llu slack", TIME(exec));
@@ -726,7 +731,7 @@ static noinline void link_server(cpu_entry_t *entry,
                         /* Should have already been removed from slack list */
                         BUG_ON(head_in_list(&task_data(entry->linked)->candidate_list));
                         BUG_ON(is_be(entry->linked) && is_queued(entry->linked));
-                        sched_trace_action(entry->linked, SLACK_RUN_ACTION);
+                        ////sched_trace_action(entry->linked, SLACK_RUN_ACTION);
                         BUG_ON(is_srt(entry->linked) &&
                                task_srt_server(entry->linked)->job_no <=
                                task_job_no(entry->linked));
@@ -734,7 +739,7 @@ static noinline void link_server(cpu_entry_t *entry,
                         /* Should have already been removed from ready heap */
                         BUG_ON(bheap_node_in_heap(next_server->hn));
                         BUG_ON(is_queued(entry->linked));
-                        sched_trace_action(entry->linked, next_server->id);
+                        ////sched_trace_action(entry->linked, next_server->id);
                 }
 
                 if (next_server->type != S_SLACK &&
@@ -773,7 +778,7 @@ static noinline void unlink_server(cpu_entry_t *entry, int requeue)
 
         if (server->type == S_SLACK && server->deadline) {
                 add_slack(server);
-                sched_trace_action(entry->linked, SLACK_STOP_ACTION);
+                ////sched_trace_action(entry->linked, SLACK_STOP_ACTION);
 
                 /* Donator needs to absorb slack execution time */
                 reclaim_slack(server);
@@ -1004,7 +1009,7 @@ static noinline int catchup_srt_server(struct task_struct *task)
 
                 rv = 1;
 
-                sched_trace_action(task, SERVER_RELEASED_ACTION);
+                ////sched_trace_action(task, SERVER_RELEASED_ACTION);
 
         } else if (lt_before(srt_server->deadline, now) &&
                    srt_server->job_no <= 1) {
@@ -1053,7 +1058,7 @@ static noinline struct task_struct* next_eligible_hrt(hrt_server_t *hrt_server)
                         slack = lt_subtract(hrt_server->server.deadline,
                                             hrt_server->server.budget);
 
-                        sched_trace_action(task, SERVER_RELEASED_ACTION);
+                        ////sched_trace_action(task, SERVER_RELEASED_ACTION);
                 }
 
                 /* If the slack timer is active, this is not necessary */
@@ -1063,7 +1068,7 @@ static noinline struct task_struct* next_eligible_hrt(hrt_server_t *hrt_server)
                                 TRACE_SERVER_SUB(&hrt_server->server, "no slack: %llu",
                                                  TIME(slack));
                                 hrt_server->no_slack = 1;
-                                sched_trace_action(task, NO_SLACK_ACTION);
+                                ////sched_trace_action(task, NO_SLACK_ACTION);
                         } else {
                                 slack_timer_arm(hrt_server);
                         }
@@ -1173,7 +1178,8 @@ static noinline server_t* next_eligible_be_server(void)
 
                 if (is_server_linked(be_server)) {
                         TRACE_SERVER_SUB(be_server, "linked");
-                        continue;
+                        be_server = next_be_server();
+                        return NULL;
                 }
 
                 catchup_server(be_server, now);
@@ -1182,7 +1188,7 @@ static noinline server_t* next_eligible_be_server(void)
                              be_server->hn);
                 be_server = next_be_server();
                 TRACE_SERVER_SUB(be_server, "catching up BE server");
-                sched_trace_action(NULL, SERVER_RELEASED_ACTION); /* Release */
+                ////sched_trace_action(NULL, SERVER_RELEASED_ACTION); /* Release */
         }
 
         if (be_server && lt_before(now, be_server->release)) {
@@ -1692,7 +1698,7 @@ static enum hrtimer_restart slack_timer_fire(struct hrtimer *timer)
 
         TRACE_TIMER("slack timer fired for P%d", entry->cpu);
         BUG_ON(!server->ready);
-        sched_trace_action(entry->linked, NO_SLACK_ACTION);
+        ////sched_trace_action(entry->linked, NO_SLACK_ACTION);
 
         /* Set new state of entry */
         server->no_slack = 1;
@@ -1729,9 +1735,7 @@ static void job_completion(cpu_entry_t *entry, struct task_struct* task)
                                       "rel: %llu, dead: %llu",
                                       TIME(get_release(task)),
                                       TIME(get_deadline(task)));
-        }
-
-        if (server->type == S_SRT) {
+        } else if (server->type == S_SRT) {
                 /* If the task is behind the server it must release immediately,
                  * leaving its release time and deadline unchanged.
                  */
@@ -1803,9 +1807,10 @@ static void server_completed(server_t *server, struct task_struct *task)
 
         if (server->type != S_SLACK) {
                 server_release(server);
-                sched_trace_action(task, SERVER_COMPLETED_ACTION);
         }
 
+        sched_trace_action(task, SERVER_COMPLETED_ACTION);
+
         unlink(task);
         requeue(task, get_rt_domain(entry, task));
 
@@ -1853,7 +1858,7 @@ static void servers_released(struct list_head *servers)
 
         raw_spin_lock_irqsave(global_lock, flags);
 
-        sched_trace_action(NULL, SERVER_RELEASED_ACTION);
+        ////sched_trace_action(NULL, SERVER_RELEASED_ACTION);
         TRACE_TIMER("Servers released");
 
         list_for_each_safe(pos, safe, servers) {
@@ -2151,7 +2156,8 @@ static void edf_hsb_task_block(struct task_struct *task)
         struct task_struct *linked;
         server_t *linked_server;
 
-        TRACE_TASK(task, "block at %llu\n", litmus_clock());
+        TRACE_TASK(task, "block at %llu in state %llu\n",
+                   litmus_clock(), task->state);
         set_rt_flags(task, RT_F_BLOCK);
 
         raw_spin_lock_irqsave(global_lock, flags);
diff --git a/litmus/sched_edf_hsb_noslack.c b/litmus/sched_edf_hsb_noslack.c
index 545588dbc915..4d91f99d4094 100644
--- a/litmus/sched_edf_hsb_noslack.c
+++ b/litmus/sched_edf_hsb_noslack.c
@@ -243,7 +243,7 @@ static void remove_slack(server_t *slack)
         if (!slack)
                 return;
         TRACE_SERVER_SUB(slack, "slack removed");
-        //sched_trace_action(NULL, SLACK_EXPIRED_ACTION);
+        //////sched_trace_action(NULL, SLACK_EXPIRED_ACTION);
 
         if (head_in_list(&slack->list))
                 list_del_init(&slack->list);
@@ -288,6 +288,13 @@ static inline struct task_struct* get_candidate(struct list_head *pos)
         return task;
 }
 
+static inline lt_t real_deadline(struct task_struct *task)
+{
+        server_t *server = task_srt_server(task);
+        int job_diff = server->job_no - task_job_no(task);
+        return get_deadline(task) - job_diff * get_rt_period(task);
+}
+
 /*
  * Candidate queue is EDF.
  */
@@ -300,7 +307,7 @@ static void add_slack_candidate(struct task_struct *task)
 
         list_for_each_prev(pos, &slack_candidates) {
                 queued = get_candidate(pos);
-                if (lt_before_eq(get_deadline(queued), get_deadline(task))) {
+                if (lt_before_eq(real_deadline(queued), real_deadline(task))) {
                         __list_add(&task_data(task)->candidate_list,
                                    pos, pos->next);
                         return;
@@ -321,8 +328,6 @@ static void donate_slack(server_t *donator)
                 BUG_ON(!hrt_server->ready);
         }
 
-        BUG_ON(head_in_list(&slack->list));
-
         slack->wcet = donator->budget;
         slack->budget = donator->budget;
         slack->deadline = donator->deadline;
@@ -373,7 +378,7 @@ static noinline void check_donate_slack(server_t *donator, struct task_struct *w
         if (!donate)
                 return;
 
-        sched_trace_action(was_scheduled, SLACK_DONATED_ACTION);
+        ////sched_trace_action(was_scheduled, SLACK_DONATED_ACTION);
 
         donate_slack(donator);
 }
@@ -439,10 +444,9 @@ static noinline server_t* next_eligible_slack_server(void)
  */
 static noinline struct task_struct* next_eligible_slack(void)
 {
-        struct task_struct *next = NULL;
+        struct task_struct *next = get_candidate(slack_candidates.next);
 
-        next = get_candidate(slack_candidates.next);
-        while (next && tsk_rt(next)->linked_on != NO_CPU) {
+        while (next && task_srt_server(next)->job_no <= task_job_no(next)) {
                 list_del_init(&task_data(next)->candidate_list);
                 next = get_candidate(slack_candidates.next);
         }
@@ -454,8 +458,6 @@ static noinline struct task_struct* next_eligible_slack(void)
                 next = __peek_ready(&be_domain);
         }
 
-        BUG_ON(next && tsk_rt(next)->linked_on != NO_CPU);
-
         return next;
 }
 
@@ -667,7 +669,7 @@ static void requeue_server(server_t *server, lt_t now)
                         hrt_server->ready = 1;
                         remove_slack(server_slack(server));
                         hrt_server->no_slack = 0;
-                        sched_trace_action(NULL, SERVER_RELEASED_ACTION);
+                        ////sched_trace_action(NULL, SERVER_RELEASED_ACTION);
                 } else if (server->type == S_BE) {
                         TRACE_SERVER_SUB(server, "BE added to ready");
                         bheap_insert(server_order, &be_ready_servers, server->hn);
@@ -685,11 +687,11 @@ static void reclaim_slack(server_t *slack)
         lt_t exec;
         server_t *donator = server_slack(slack);
 
-        if (!donator)
+        if (!donator || lt_before_eq(slack->deadline, litmus_clock()))
                 return;
 
         /* SRT servers do not ever reclaim slack */
-        sched_trace_action(NULL, SLACK_RECLAIM_ACTION);
+        ////sched_trace_action(NULL, SLACK_RECLAIM_ACTION);
 
         exec = slack->wcet - slack->budget;
         TRACE_SERVER_SUB(donator, "reclaiming %llu slack", TIME(exec));
@@ -721,7 +723,6 @@ static noinline void link_server(cpu_entry_t *entry,
                         BUG_ON(next_server->job_no + 1 < task_job_no(entry->linked));
                         BUG_ON(lt_after(get_deadline(entry->linked),
                                         next_server->deadline));
-                        BUG_ON(head_in_list(&task_data(entry->linked)->candidate_list));
                 } else if (next_server->type == S_HRT) {
                         /* HRT servers should never, ever migrate */
                         BUG_ON(entry->cpu != task_cpu(entry->linked));
@@ -730,12 +731,15 @@ static noinline void link_server(cpu_entry_t *entry,
                         /* Should have already been removed from slack list */
                         BUG_ON(head_in_list(&task_data(entry->linked)->candidate_list));
                         BUG_ON(is_be(entry->linked) && is_queued(entry->linked));
-                        sched_trace_action(entry->linked, SLACK_RUN_ACTION);
+                        ////sched_trace_action(entry->linked, SLACK_RUN_ACTION);
+                        BUG_ON(is_srt(entry->linked) &&
+                               task_srt_server(entry->linked)->job_no <=
+                               task_job_no(entry->linked));
                 } else { /* BE */
                         /* Should have already been removed from ready heap */
                         BUG_ON(bheap_node_in_heap(next_server->hn));
                         BUG_ON(is_queued(entry->linked));
-                        sched_trace_action(entry->linked, next_server->id);
+                        ////sched_trace_action(entry->linked, next_server->id);
                 }
 
                 if (next_server->type != S_SLACK &&
@@ -774,7 +778,7 @@ static noinline void unlink_server(cpu_entry_t *entry, int requeue)
 
         if (server->type == S_SLACK && server->deadline) {
                 add_slack(server);
-                sched_trace_action(entry->linked, SLACK_STOP_ACTION);
+                ////sched_trace_action(entry->linked, SLACK_STOP_ACTION);
 
                 /* Donator needs to absorb slack execution time */
                 reclaim_slack(server);
@@ -940,6 +944,7 @@ static noinline void unlink(struct task_struct* t)
         if (head_in_list(&task_data(t)->candidate_list)) {
                 list_del_init(&task_data(t)->candidate_list);
         }
+
 }
 
 /*
@@ -1004,7 +1009,7 @@ static noinline int catchup_srt_server(struct task_struct *task)
 
                 rv = 1;
 
-                sched_trace_action(task, SERVER_RELEASED_ACTION);
+                ////sched_trace_action(task, SERVER_RELEASED_ACTION);
 
         } else if (lt_before(srt_server->deadline, now) &&
                    srt_server->job_no <= 1) {
@@ -1053,7 +1058,7 @@ static noinline struct task_struct* next_eligible_hrt(hrt_server_t *hrt_server)
                         slack = lt_subtract(hrt_server->server.deadline,
                                             hrt_server->server.budget);
 
-                        sched_trace_action(task, SERVER_RELEASED_ACTION);
+                        ////sched_trace_action(task, SERVER_RELEASED_ACTION);
                 }
 
                 /* If the slack timer is active, this is not necessary */
@@ -1063,7 +1068,7 @@ static noinline struct task_struct* next_eligible_hrt(hrt_server_t *hrt_server)
                                 TRACE_SERVER_SUB(&hrt_server->server, "no slack: %llu",
                                                  TIME(slack));
                                 hrt_server->no_slack = 1;
-                                sched_trace_action(task, NO_SLACK_ACTION);
+                                ////sched_trace_action(task, NO_SLACK_ACTION);
                         } else {
                                 slack_timer_arm(hrt_server);
                         }
@@ -1173,7 +1178,8 @@ static noinline server_t* next_eligible_be_server(void)
 
                 if (is_server_linked(be_server)) {
                         TRACE_SERVER_SUB(be_server, "linked");
-                        continue;
+                        be_server = next_be_server();
+                        return NULL;
                 }
 
                 catchup_server(be_server, now);
@@ -1182,7 +1188,7 @@ static noinline server_t* next_eligible_be_server(void)
                              be_server->hn);
                 be_server = next_be_server();
                 TRACE_SERVER_SUB(be_server, "catching up BE server");
-                sched_trace_action(NULL, SERVER_RELEASED_ACTION); /* Release */
+                ////sched_trace_action(NULL, SERVER_RELEASED_ACTION); /* Release */
         }
 
         if (be_server && lt_before(now, be_server->release)) {
@@ -1279,10 +1285,6 @@ static void next_global_task(cpu_entry_t *entry,
         next_slack = next_eligible_slack();
         slack_server = next_eligible_slack_server();
 
-        BUG_ON(next_slack && tsk_rt(next_slack)->linked_on != NO_CPU);
-        BUG_ON(next_srt && tsk_rt(next_srt)->linked_on != NO_CPU);
-        BUG_ON(next_be && tsk_rt(next_be)->linked_on != NO_CPU);
-
         TRACE_SUB("be_server: %d, next_be: %d, next_srt: %d, slack_server: %d "
                   "next_slack: %d", (be_server) ? be_server->id : -1,
                   (next_be) ? next_be->pid : -1,
@@ -1359,6 +1361,12 @@ static void remove_from_ready(server_t *server, struct task_struct *task,
                         TRACE_TASK_SUB(task, "BE removed from ready");
                         remove(&be_domain, task);
                 }
+
+                /* Remove from consideration of slack servers */
+                if (head_in_list(&task_data(task)->candidate_list)) {
+                        TRACE_TASK_SUB(task, "deleting candidate");
+                        list_del_init(&task_data(task)->candidate_list);
+                }
         } else {
                 slack = server_slack(server);
                 if (slack && head_in_list(&slack->list)) {
@@ -1379,13 +1387,6 @@ static void remove_from_ready(server_t *server, struct task_struct *task,
         }
 
         BUG_ON(!task_data(task));
-
-        /* Remove from consideration of slack servers */
-        if (head_in_list(&task_data(task)->candidate_list)) {
-                TRACE_TASK_SUB(task, "deleting candidate");
-                list_del_init(&task_data(task)->candidate_list);
-        }
-
 }
 
 static void check_for_slack_preempt(struct task_struct*,server_t*,cpu_entry_t*, int);
@@ -1469,11 +1470,21 @@ static noinline void check_for_slack_preempt(struct task_struct *task,
         server_t *slack = server_slack(server);
         struct task_struct *slack_task;
 
-        /* Bad! There is no use trying to move the link of this task as it
-         * is almost always scheduled on another CPU.
-         */
-        BUG_ON(tsk_rt(task)->linked_on != NO_CPU &&
-               tsk_rt(task)->linked_on != next_entry->cpu);
+        /* The task is currently being run by another server */
+        if (tsk_rt(task)->linked_on != NO_CPU) {
+                entry = task_linked_entry(task);
+
+                if (entry != next_entry) {
+                        TRACE_TASK_SUB(task, "was on P%d", entry->cpu);
+
+                        unlink(task);
+
+                        /* if (resched) { */
+                        /*      edf_hsb_pick_next(entry); */
+                        /*      preempt_if_preemptable(entry->scheduled, entry->cpu); */
+                        /* } */
+                }
+        }
 
         /* The server's slack is currently being run */
         if (slack && is_server_linked(slack)) {
@@ -1687,7 +1698,7 @@ static enum hrtimer_restart slack_timer_fire(struct hrtimer *timer)
 
         TRACE_TIMER("slack timer fired for P%d", entry->cpu);
         BUG_ON(!server->ready);
-        sched_trace_action(entry->linked, NO_SLACK_ACTION);
+        ////sched_trace_action(entry->linked, NO_SLACK_ACTION);
 
         /* Set new state of entry */
         server->no_slack = 1;
@@ -1724,15 +1735,7 @@ static void job_completion(cpu_entry_t *entry, struct task_struct* task)
                                       "rel: %llu, dead: %llu",
                                       TIME(get_release(task)),
                                       TIME(get_deadline(task)));
-                check_slack_candidate(task);
-                sched_trace_task_completion(task, 1);
-
-                return;
-        }
-
-        BUG_ON(is_queued(task));
-
-        if (server->type == S_SRT) {
+        } else if (server->type == S_SRT) {
                 /* If the task is behind the server it must release immediately,
                  * leaving its release time and deadline unchanged.
                  */
@@ -1804,9 +1807,10 @@ static void server_completed(server_t *server, struct task_struct *task)
 
         if (server->type != S_SLACK) {
                 server_release(server);
-                sched_trace_action(task, SERVER_COMPLETED_ACTION);
         }
 
+        sched_trace_action(task, SERVER_COMPLETED_ACTION);
+
         unlink(task);
         requeue(task, get_rt_domain(entry, task));
 
@@ -1854,7 +1858,7 @@ static void servers_released(struct list_head *servers)
 
         raw_spin_lock_irqsave(global_lock, flags);
 
-        sched_trace_action(NULL, SERVER_RELEASED_ACTION);
+        ////sched_trace_action(NULL, SERVER_RELEASED_ACTION);
         TRACE_TIMER("Servers released");
 
         list_for_each_safe(pos, safe, servers) {
@@ -2152,7 +2156,8 @@ static void edf_hsb_task_block(struct task_struct *task)
         struct task_struct *linked;
         server_t *linked_server;
 
-        TRACE_TASK(task, "block at %llu\n", litmus_clock());
+        TRACE_TASK(task, "block at %llu in state %llu\n",
+                   litmus_clock(), task->state);
         set_rt_flags(task, RT_F_BLOCK);
 
         raw_spin_lock_irqsave(global_lock, flags);