slack stealing

1 files changed, 525 insertions, 160 deletions

diff --git a/litmus/sched_edf_hsb.c b/litmus/sched_edf_hsb.c
index 12abe3def2d3..4b2c58ec6b75 100644
--- a/litmus/sched_edf_hsb.c
+++ b/litmus/sched_edf_hsb.c
@@ -16,6 +16,10 @@
  * admit_[hrt|be]_server
  *
  * TODO BE SERVER TASK PREEMPTGION A;SDIFHSAKEUHFLKH
+ * TODO BE server heap needed?
+ * TODO move slack completion into release
+ * TODO fix concurrent arms
+ * TODO slack and BE servers
  *
  */
 #include <linux/module.h>
@@ -34,7 +38,6 @@
 #include <litmus/edf_common.h>
 #include <litmus/sched_trace.h>
 #include <litmus/servers.h>
-
 #define DEBUG_EDF_HSB
 
 /* DOES NOT WORK */
@@ -43,6 +46,7 @@
 #define BE_PROC_NAME    "be_servers"
 #define HRT_PROC_NAME   "hrt_servers"
 #define BE_SERVER_BASE  100
+#define SLACK_MIN       NSEC_PER_MSEC
 
 #define TIME(x)                                 \
         ({lt_t y = x;                           \
@@ -67,11 +71,21 @@ atomic_t servers_running = ATOMIC_INIT(0);
 #define TRACE_TASK_SUB(t, fmt, args...)                           \
         TRACE_SUB("(%s/%d:%d) " fmt, (t)->comm, (t)->pid,         \
               (t)->rt_param.job_params.job_no,  ##args)
+#define TRACE_SERVER_SUB(s, fmt, args...)       \
+        TRACE_SUB(SERVER_FMT " " fmt, SERVER_ARGS(s), ##args)
 #else
 #define TRACE_SUB(fmt, args...)
 #define TRACE_TASK_SUB(t, fmt, args...)
+#define TRACE_SERVER_SUB(s, fmt, args...)
 #endif
 
+typedef enum {
+        S_HRT,
+        S_SRT,
+        S_BE,
+        S_SLACK
+} server_type_t;
+
 typedef struct {
         server_t        server;
         rt_domain_t     hrt_domain;  /* EDF for HRT tasks assigned here */
@@ -108,6 +122,9 @@ static server_domain_t server_domain; /* Useful tools for server scheduling */
 static struct list_head be_servers;             /* All BE servers */
 static struct bheap     be_ready_servers;       /* Runnable BE servers */
 
+static struct list_head slack_queue;
+static struct list_head slack_candidates;
+
 static int release_master; /* CPU which will release tasks and global servers */
 
 static struct proc_dir_entry *edf_hsb_proc_dir = NULL;
@@ -117,9 +134,194 @@ static struct sched_plugin edf_hsb_plugin __cacheline_aligned_in_smp;
 #define task_sched_entry(task)  (&per_cpu(cpu_entries, task_cpu(task)))
 #define task_linked_entry(task) (&per_cpu(cpu_entries, task->rt_param.linked_on))
 #define task_job_no(task)       (tsk_rt(task)->job_params.job_no)
+#define task_srt_server(task)   ((server_t*)tsk_rt(task)->plugin_data)
+#define task_slack_server(task) ((server_t*)tsk_rt(task)->slack_server)
 #define global_lock             (&srt_domain.ready_lock)
 #define is_active_plugin        (litmus == &edf_hsb_plugin)
 
+static inline int head_in_list(struct list_head *list)
+{
+        if ((list->next == list->prev && list->prev  == list) ||
+            (list->next == LIST_POISON1 && list->prev == LIST_POISON2))
+                return 0;
+        else
+                return 1;
+}
+
+/* In the next methods check to see if have donated. If so, do what?
+ * Server_stop. in check for hrt, need to make sure a check for global is
+ * called. in the other one, just need to make sure we unlink and crap and
+ * then call for it again.
+ * What happens if an srt is released that is scheduled?
+ * Then the effective deadline will mark it.
+ */
+static server_t* next_eligible_slack(void)
+{
+        server_t *next_slack = NULL, *donator;
+        lt_t now = litmus_clock();
+
+        while (!list_empty(&slack_queue)) {
+                next_slack = list_entry(slack_queue.next, server_t, list);
+
+                if (lt_after(next_slack->deadline, now) &&
+                    next_slack->budget > SLACK_MIN) {
+                        break;
+                } else {
+                        /* Slack has expired or has too little time */
+                        TRACE_SUB("slack " SERVER_FMT " has expired",
+                                  SERVER_ARGS(next_slack));
+                        sched_trace_action(NULL, 7);
+
+                        list_del(&next_slack->list);
+                        donator = (server_t*)next_slack->data;
+                        donator->data = NULL;
+                        server_destroy(next_slack);
+                        kfree(next_slack);
+
+                        next_slack = NULL;
+                }
+        }
+
+        if (next_slack)
+                TRACE_SERVER_SUB(next_slack, "found eligible slack, "
+                                 "now: %llu, dead: %llu", now,
+                                 next_slack->deadline);
+        else
+                TRACE_SUB("no eligible slack");
+
+        return next_slack;
+}
+
+static void add_slack(server_t *slack)
+{
+        struct list_head *pos;
+        server_t *queued;
+        TRACE_SERVER_SUB(slack, "adding");
+
+        BUG_ON(head_in_list(&slack->list));
+
+        list_for_each_prev(pos, &slack_queue) {
+                queued = list_entry(pos, server_t, list);
+                if (lt_before_eq(queued->deadline, slack->deadline)) {
+                        __list_add(&slack->list, pos, pos->next);
+                        return;
+                }
+        }
+        list_add(&slack->list, &slack_queue);
+}
+
+static void add_slack_candidate(struct task_struct *task)
+{
+        struct list_head *pos;
+        struct task_struct *queued;
+
+        tsk_rt(task)->slack_candidate = 1;
+        INIT_LIST_HEAD(&tsk_rt(task)->slack_list);
+
+        list_for_each_prev(pos, &slack_candidates) {
+                queued = list_entry(pos, struct task_struct,
+                                    rt_param.slack_list);
+                if (lt_before_eq(get_deadline(queued), get_deadline(task))) {
+                        TRACE_TASK_SUB(task, "adding after %d", queued->pid);
+                        __list_add(&tsk_rt(task)->slack_list,
+                                   pos, pos->next);
+                        return;
+                }
+        }
+        TRACE_TASK_SUB(task, "adding to end of list");
+        list_add(&tsk_rt(task)->slack_list, &slack_candidates);
+}
+
+static struct task_struct* next_eligible_hrt(hrt_server_t*);
+
+static void donate_slack(server_t *donator, struct task_struct *was_scheduled)
+{
+        server_t *slack;
+        hrt_server_t *hrt_server;
+        int donate = 0;
+
+        if (donator->budget < SLACK_MIN) {
+                TRACE_SERVER_SUB(donator, "cannot donate slack");
+                return;
+        }
+
+        if (donator->type == S_SRT &&
+            donator->job_no <= task_job_no(was_scheduled)) {
+                donate = 1;
+        } else if (donator->type == S_HRT &&
+                   lt_before_eq(litmus_clock(), get_deadline(was_scheduled))) {
+                hrt_server = container_of(donator, hrt_server_t, server);
+                if (!next_eligible_hrt(hrt_server)) {
+                        donate = 1;
+                }
+        } else if (donator-> type == S_BE && !__jobs_pending(&be_domain)) {
+                donate = 1;
+        }
+
+        if (!donate) {
+                TRACE_SERVER_SUB(donator, "doesn't want to donate slack");
+                return;
+        }
+
+        TRACE_SERVER_SUB(donator, "donated %llu slack", TIME(donator->budget));
+        sched_trace_action(was_scheduled, 9);
+        slack = kmalloc(sizeof(server_t), GFP_ATOMIC);
+        server_init(slack, donator->id, donator->budget,
+                    donator->period, 0);
+        slack->type = S_SLACK;
+        server_release_at(slack, donator->release);
+        slack->data = donator;
+        donator->data = slack;
+
+        add_slack(slack);
+}
+
+static void reclaim_slack(server_t *donator)
+{
+        TRACE_SERVER_SUB(donator, "wants to reclaim slack");
+}
+
+static struct task_struct* pick_next_slack(server_t *slack, cpu_entry_t *entry)
+{
+        struct task_struct *rv = NULL;
+        if (!slack)
+                goto out;
+        if (!list_empty(&slack_candidates)) {
+                rv = list_entry(slack_candidates.next, struct task_struct,
+                                rt_param.slack_list);
+                TRACE_TASK_SUB(rv, "is next slack");
+        } else if (entry && entry->linked &&
+                   entry->linked_server->type == S_SLACK) {
+                rv = entry->linked;
+        }
+ out:
+        return rv;
+}
+
+static void take_next_slack(struct task_struct *task)
+{
+        if (tsk_rt(task)->slack_candidate) {
+                TRACE_TASK_SUB(task, "deleting slack");
+                list_del(&tsk_rt(task)->slack_list);
+                tsk_rt(task)->slack_candidate = 0;
+        } else {
+                TRACE_TASK_SUB(task, "can't delete slack");
+        }
+}
+
+static void check_slack_candidate(struct task_struct *task)
+{
+        TRACE_TASK_SUB(task, "checking");
+        if (is_srt(task) && task_srt_server(task)->job_no >=
+            task_job_no(task) && lt_after(get_release(task), litmus_clock()) &&
+            get_rt_flags(task) != RT_F_SLEEP &&
+            !tsk_rt(task)->slack_candidate)
+{
+                add_slack_candidate(task);
+                sched_trace_action(task, 8);
+        }
+}
+
 /*
  * FIFO for BE tasks.
  */
@@ -334,37 +536,38 @@ static inline void slack_timer_cancel(hrt_server_t *hrt_server)
  * tasks as this method cannot determine which BE server to use.
  */
 static noinline void link_server(cpu_entry_t *entry,
-                                 server_t    *be_server)
+                                 server_t    *next_server)
 {
-        server_t *srt_server;
+        BUG_ON(!next_server);
 
-        if (is_srt(entry->linked)) {
-                srt_server = tsk_rt(entry->linked)->plugin_data;
+        if (next_server->type == S_SRT) {
                 TRACE_TASK_SUB(entry->linked, "resuming SRT server,"
                                "budget*: %llu, exec_time: %llu, deadline: %llu,"
                                "job_no: %d",
-                               srt_server->budget, get_exec_time(entry->linked),
-                               get_deadline(entry->linked), srt_server->job_no);
-                BUG_ON(lt_after(srt_server->budget,
+                               next_server->budget, get_exec_time(entry->linked),
+                               get_deadline(entry->linked), next_server->job_no);
+                BUG_ON(lt_after(next_server->budget,
                                 get_exec_cost(entry->linked)));
 
-                BUG_ON(srt_server->job_no < task_job_no(entry->linked));
+                BUG_ON(next_server->job_no < task_job_no(entry->linked));
                 BUG_ON(lt_after(get_deadline(entry->linked),
-                                srt_server->deadline));
-
-                entry->linked_server = srt_server;
+                                next_server->deadline));
         } else if (is_hrt(entry->linked)) {
                 /* HRT servers should never, ever migrate */
                 BUG_ON(entry->cpu != task_cpu(entry->linked));
                 slack_timer_cancel(&entry->hrt_server);
-                entry->linked_server = &entry->hrt_server.server;
+        } else if (next_server->type == S_SLACK) {
+                /* Should have already been removed */
+                BUG_ON(tsk_rt(entry->linked)->slack_candidate);
+                TRACE_SERVER_SUB(next_server, "linking slack server");
+                sched_trace_action(entry->linked, 5);
+                tsk_rt(entry->linked)->slack_server = next_server;
         } else { /* BE */
-                BUG_ON(!be_server);
-                BUG_ON(bheap_node_in_heap(be_server->hn));
-                entry->linked_server = be_server;
-                sched_trace_action(entry->linked, 200 + be_server->id);
+                BUG_ON(bheap_node_in_heap(next_server->hn));
+                sched_trace_action(entry->linked, 200 + next_server->id);
         }
 
+        entry->linked_server = next_server;
         server_run(entry->linked_server, entry->linked, &server_domain);
 }
 
@@ -374,7 +577,7 @@ static noinline void link_server(cpu_entry_t *entry,
  * This must be called BEFORE a task is unlinked.
  */
 static noinline void unlink_server(cpu_entry_t *entry,
-                                   server_t *be_server)
+                                   server_t *next_server)
 {
         lt_t now;
         int added;
@@ -402,8 +605,21 @@ static noinline void unlink_server(cpu_entry_t *entry,
 
         }
 
+        if (entry->linked_server->type == S_SLACK) {
+                tsk_rt(entry->linked)->slack_server = NULL;
+        }
+
+        /* Requeue SRT servers, they will be garbage collected later */
+        if (entry->linked_server->type == S_SLACK &&
+            next_server != entry->linked_server &&
+            next_server) {
+                add_slack(entry->linked_server);
+                sched_trace_action(entry->linked, 6);
+                check_slack_candidate(entry->linked);
+        }
+
         /* Requeue eligible BE servers if they are not about to run again */
-        if (is_be(entry->linked) && entry->linked_server != be_server) {
+        if (is_be(entry->linked) && entry->linked_server != next_server) {
                 if (lt_before(entry->linked_server->release, now)) {
                         TRACE_SUB("inserting %d", entry->linked_server->id);
                         bheap_insert(server_order, &be_ready_servers,
@@ -428,6 +644,7 @@ static noinline void unlink_server(cpu_entry_t *entry,
                         slack_timer_arm(&entry->hrt_server);
                 }
         }
+        entry->linked_server = NULL;
 }
 
 /* Update the link of a CPU.
@@ -437,7 +654,7 @@ static noinline void unlink_server(cpu_entry_t *entry,
  */
 static noinline void link_task_to_cpu(cpu_entry_t *entry,
                                       struct task_struct* linked,
-                                      server_t* be_server)
+                                      server_t* next_server)
 {
         cpu_entry_t *sched;
         server_t *tmp_server;
@@ -449,7 +666,7 @@ static noinline void link_task_to_cpu(cpu_entry_t *entry,
 
         /* Currently linked task is set to be unlinked. */
         if (entry->linked) {
-                unlink_server(entry, be_server);
+                unlink_server(entry, next_server);
                 entry->linked->rt_param.linked_on = NO_CPU;
                 entry->linked = NULL;
         }
@@ -484,13 +701,12 @@ static noinline void link_task_to_cpu(cpu_entry_t *entry,
 
                                 linked->rt_param.linked_on = sched->cpu;
                                 sched->linked = linked;
-                                link_server(sched, be_server);
+                                link_server(sched, next_server);
 
                                 update_cpu_position(sched);
-                                BUG_ON(!entry->linked && entry->linked_server);
 
                                 linked = tmp_task;
-                                be_server = tmp_server;
+                                next_server = tmp_server;
                         }
                 }
                 if (linked) /* might be NULL due to swap */
@@ -498,7 +714,7 @@ static noinline void link_task_to_cpu(cpu_entry_t *entry,
         }
         entry->linked = linked;
         if (linked)
-                link_server(entry, be_server);
+                link_server(entry, next_server);
         else
                 entry->linked_server = NULL;
         BUG_ON(!entry->linked && entry->linked_server);
@@ -627,6 +843,30 @@ static struct task_struct* next_eligible_hrt(hrt_server_t *hrt_server)
         return task;
 }
 
+static struct task_struct* next_eligible_srt(void)
+{
+        struct task_struct *next_srt = __peek_ready(&srt_domain);
+        server_t *srt_server;
+
+        /* Catch up srt server. This happens when the job is tardy due
+         * to overutilization of the system.
+         */
+        if (next_srt) {
+                srt_server = tsk_rt(next_srt)->plugin_data;
+                if (srt_server->deadline < get_deadline(next_srt)) {
+                        TRACE_SUB("catching up SRT to %llu",
+                                  get_release(next_srt));
+                        server_release_at(srt_server, get_release(next_srt));
+                        srt_server->job_no = task_job_no(next_srt);
+                }
+        }
+
+        if (next_srt && tsk_rt(next_srt)->slack_candidate)
+                take_next_slack(next_srt);
+
+        return next_srt;
+}
+
 /*
  * The highest priority BE server.
  */
@@ -636,27 +876,11 @@ static inline server_t* next_be_server(void)
         return (hn) ? hn->value : NULL;
 }
 
-/*
- * Either an srt task or a be server is next. The deadline of the chosen
- * task / server is put into deadline.
- * TODO: remove this class business.
- */
-static task_class_t next_global_task(struct task_struct **task_srt,
-                                     server_t **server_be,
-                                     lt_t *deadline)
+static server_t* next_eligible_be_server(void)
 {
-        task_class_t rv = RT_CLASS_HARD; /* Represents invalid here */
-        struct task_struct *next_srt;
-        server_t *be_server, *srt_server;
+        server_t *be_server = next_be_server();
         lt_t now = litmus_clock();
 
-        *task_srt  = NULL;
-        *server_be = NULL;
-        *deadline  = 0;
-
-        be_server = next_be_server();
-        next_srt = __peek_ready(&srt_domain);
-
         /* Catch up any late be servers. This happens when the servers
          * could not find tasks to schedule or if the system is
          * overutilized.
@@ -670,56 +894,87 @@ static task_class_t next_global_task(struct task_struct **task_srt,
                              be_server->hn);
                 be_server = next_be_server();
         }
+        return be_server;
+}
 
-        /* Catch up srt server. This happens when the job is tardy due
-         * to overutilization of the system.
-         */
-        if (next_srt) {
-                srt_server = tsk_rt(next_srt)->plugin_data;
-                if (srt_server->deadline < get_deadline(next_srt)) {
-                        TRACE_SUB("catching up SRT to %llu",
-                                  get_release(next_srt));
-                        server_release_at(srt_server, get_release(next_srt));
-                        srt_server->job_no = task_job_no(next_srt);
-                }
-        }
+static inline server_t* earlier_server(server_t *first, server_t *second)
+{
+        if (!first)
+                return second;
+        if (!second)
+                return first;
+        return (lt_before_eq(first->deadline, second->deadline)) ?
+                first : second;
+}
 
-        TRACE_SUB("be_server: %d, next_srt: %d",
+/*
+ * Either an srt task or a be server is next. The deadline of the chosen
+ * task / server is put into deadline.
+ * TODO: remove this class business.
+ */
+static lt_t next_global_task(struct task_struct **task_srt,
+                             server_t **server_be,
+                             server_t **server_slack)
+{
+        struct task_struct *next_srt;
+        server_t *be_server, *slack_server, *first_server;
+        lt_t deadline = 0;
+
+        *task_srt  = NULL;
+        *server_be = NULL;
+        *server_slack = NULL;
+
+        be_server = next_eligible_be_server();
+        next_srt = next_eligible_srt();
+        slack_server = next_eligible_slack();
+
+        TRACE_SUB("be_server: %d, next_srt: %d, next_slack: %d",
                   (be_server) ? be_server->id : -1,
-                  (next_srt) ? next_srt->pid : -1);
+                  (next_srt) ? next_srt->pid : -1,
+                  (slack_server) ? slack_server->id : -1);
         BUG_ON(next_srt && !is_srt(next_srt));
 
-        if (next_srt && (!be_server ||
+        first_server = earlier_server(be_server, slack_server);
+        first_server = be_server;
+
+        if (next_srt && (!first_server ||
                          lt_before(get_deadline(next_srt),
-                                   be_server->deadline))) {
+                                   first_server->deadline))) {
                 /* SRT is next task */
                 *server_be = NULL;
+                *server_slack = NULL;
                 *task_srt = next_srt;
-                *deadline = get_deadline(next_srt);
-                rv = RT_CLASS_SOFT;
-        } else if (be_server) {
+                deadline = get_deadline(next_srt);
+        } else if (be_server && be_server == first_server) {
                 /* BE is next task */
                 *server_be = be_server;
+                *server_slack = NULL;
+                *task_srt = NULL;
+                deadline = be_server->deadline;
+        } else if (slack_server) {
+                /* Slack is next task */
+                *server_be = NULL;
+                *server_slack = slack_server;
                 *task_srt = NULL;
-                *deadline = be_server->deadline;
-                rv = RT_CLASS_BEST_EFFORT;
+                deadline = slack_server->deadline;
         }
 
-        return rv;
+        return deadline;
 }
 
 /*
  * Adds a task to the appropriate queue (ready / release) in a domain.
  */
-static noinline void requeue(struct task_struct *task, rt_domain_t *domain)
+static noinline void requeue(struct task_struct *task, rt_domain_t *domain,
+                             server_t *server)
 {
         int was_added;
         BUG_ON(!is_realtime(task));
-        BUG_ON(is_queued(task));
-        BUG_ON(is_be(task) && domain != &be_domain);
-        BUG_ON(is_srt(task) && domain != &srt_domain);
 
-        if (is_released(task, litmus_clock())) {
+        if (is_queued(task)) {
+                if (!is_released(task, litmus_clock()))
+                        check_slack_candidate(task);
+        } else if (is_released(task, litmus_clock())) {
                 TRACE_TASK_SUB(task, "requeuing on ready");
                 __add_ready(domain, task);
         } else {
@@ -745,25 +1000,134 @@ static noinline void requeue(struct task_struct *task, rt_domain_t *domain)
  * be tasks. For other tasks, the server can be calculated later.
  */
 static void preempt(cpu_entry_t *entry, struct task_struct *next,
-                    server_t *be_server)
+                    server_t *next_server)
 {
         rt_domain_t *domain;
 
         if (entry->linked) {
                 domain = get_rt_domain(entry, entry->linked);
-                requeue(entry->linked, domain);
+                requeue(entry->linked, domain, entry->linked_server);
         }
 
-        link_task_to_cpu(entry, next, be_server);
+        link_task_to_cpu(entry, next, next_server);
         preempt_if_preemptable(entry->scheduled, entry->cpu);
 }
 
+static inline struct task_struct* pick_next_be(server_t *be_server,
+                                               cpu_entry_t *entry)
+{
+        struct task_struct *next_be = NULL;
+        if (!be_server)
+                goto out;
+        next_be = __peek_ready(&be_domain);
+        if (!next_be && entry->linked && is_be(entry->linked))
+                next_be = entry->linked;
+ out:
+        return next_be;
+}
+
+static cpu_entry_t* check_for_slack_preempt(struct task_struct *task,
+                                            cpu_entry_t *next_entry)
+{
+        cpu_entry_t *preempted = NULL;
+        cpu_entry_t *entry = task_linked_entry(task);
+        server_t *slack_server = task_slack_server(task);
+
+        BUG_ON(!is_srt(task));
+
+        if (!slack_server || !slack_server->running)
+                goto out;
+
+        TRACE_TASK_SUB(task, "slack preempt");
+        sched_trace_action(task, 10);
+
+        preempted = entry;
+
+        unlink(task);
+        take_next_slack(task);
+ out:
+        return preempted;
+}
+
+/*
+ * Selects and links the next task for the given CPU.
+ * TODO: this method is terrible
+ */
+static void edf_hsb_pick_next(cpu_entry_t *entry)
+{
+        lt_t deadline;
+        struct task_struct *next_hrt, *next_srt, *next_be, *next_slack;
+        server_t *be_server, *slack_server;
+        cpu_entry_t *preempted;
+
+        BUG_ON(entry->linked);
+
+        next_hrt = next_eligible_hrt(&entry->hrt_server);
+
+        if (next_hrt) {
+                /* HRT is next task */
+                link_task_to_cpu(entry, next_hrt, &entry->hrt_server.server);
+                remove(&entry->hrt_server.hrt_domain, next_hrt);
+        } else {
+                deadline = next_global_task(&next_srt,
+                                            &be_server,
+                                            &slack_server);
+
+                if (next_srt) {
+                        remove(&srt_domain, next_srt);
+
+                        preempted = check_for_slack_preempt(next_srt, entry);
+                        if (preempted) {
+                                edf_hsb_pick_next(preempted);
+                                preempt_if_preemptable(preempted->scheduled,
+                                                       preempted->cpu);
+                        }
+
+                        link_task_to_cpu(entry, next_srt,
+                                         task_srt_server(next_srt));
+                } else if (be_server) {
+                        next_be = __take_ready(&be_domain);
+
+                        if (next_be) {
+                                TRACE_SUB("deleting be server %d",
+                                          be_server->id);
+                                bheap_delete(server_order, &be_ready_servers,
+                                             be_server->hn);
+                                link_task_to_cpu(entry, next_be, be_server);
+                        }
+                } else if (slack_server) {
+                        next_slack = pick_next_slack(slack_server, NULL);
+
+                        if (next_slack) {
+                                take_next_slack(next_slack);
+                                list_del(&slack_server->list);
+                                TRACE_TASK_SUB(next_slack, "taking");
+                                link_task_to_cpu(entry, next_slack, slack_server);
+                        }
+                }
+        }
+
+        /* Try SRT again */
+        if (!entry->linked) {
+                next_srt = __take_ready(&srt_domain);
+                if (!next_srt)
+                        return;
+                preempted = check_for_slack_preempt(next_srt, entry);
+                if (preempted) {
+                        edf_hsb_pick_next(preempted);
+                        preempt_if_preemptable(preempted->scheduled,
+                                               preempted->cpu);
+                }
+
+                link_task_to_cpu(entry, next_srt, task_srt_server(next_srt));
+        }
+}
+
 static void check_for_global_preempt(void)
 {
-        task_class_t class;
         cpu_entry_t *entry;
-        server_t *be_server = NULL;
-        struct task_struct *next_srt, *next_be;
+        server_t *be_server = NULL, *slack_server = NULL, *next_server;
+        struct task_struct *next_srt, *next_be, *next_slack;
         struct task_struct *next_task = (struct task_struct*)1; /* Not null */
         lt_t deadline;
 
@@ -775,21 +1139,27 @@ static void check_for_global_preempt(void)
                 BUG_ON(entry->linked && is_hrt(entry->linked));
 
                 /* Get the potential challengers */
-                class = next_global_task(&next_srt,
-                                         &be_server,
-                                         &deadline);
-                next_be = __peek_ready(&be_domain);
+                deadline = next_global_task(&next_srt,
+                                            &be_server,
+                                            &slack_server);
+                next_be = pick_next_be(be_server, entry);
+                next_slack = pick_next_slack(slack_server, entry);
 
                 /* If there is no existing BE, then the server must have
-                 * a new BE task to schedule. If it doesn't, try SRT.
+                 * a new BE task to schedule. If it doesn't, others.
                  */
-                if (be_server && !next_be &&
-                    (!entry->linked || !is_be(entry->linked))) {
+                if (be_server && !next_be) {
                         TRACE_SUB("2");
                         be_server = NULL;
-                        next_srt  = __peek_ready(&srt_domain);
+                        next_srt  = next_eligible_srt();
+                        deadline = (next_srt) ?get_deadline(next_srt) : 0;
+                }
+
+                if (slack_server && !next_slack) {
+                        TRACE_SUB("3");
+                        slack_server = NULL;
+                        next_srt  = next_eligible_srt();
                         deadline = (next_srt) ?get_deadline(next_srt) : 0;
-                        class = RT_CLASS_SOFT;
                 }
 
                 TRACE_SUB("4");
@@ -815,8 +1185,7 @@ static void check_for_global_preempt(void)
                     lt_before(deadline, entry->linked_server->deadline)){
                         TRACE_SUB("8");
                         /* Swap two BE servers here */
-                        if ((class & get_class(entry->linked)) ==
-                            RT_CLASS_BEST_EFFORT) {
+                        if (be_server && entry->linked_server->type == S_BE) {
                                 TRACE_SUB("9");
                                 bheap_delete(server_order,
                                              &be_ready_servers,
@@ -827,6 +1196,16 @@ static void check_for_global_preempt(void)
                                 next_task = entry->linked;
                                 goto loop_end;
                         }
+                        /* Swap two slack servers here */
+                        if (slack_server && entry->linked_server->type == S_SLACK) {
+                                TRACE_SUB("9.5");
+                                list_del(&slack_server->list);
+                                unlink_server(entry, slack_server);
+                                link_server(entry, slack_server);
+                                update_cpu_position(entry);
+                                next_task = entry->linked;
+                                goto loop_end;
+                        }
                         TRACE_SUB("10");
                         goto loop_end_preempt;
                 }
@@ -835,9 +1214,11 @@ static void check_for_global_preempt(void)
 
         loop_end_preempt:
                 TRACE_SUB("13");
-                if (class == RT_CLASS_SOFT) {
+                if (next_srt) {
                         next_task = next_srt;
-                } else {
+                        next_server = task_srt_server(next_task);
+                        check_for_slack_preempt(next_srt, entry);
+                } else if (next_be) {
                         next_task = next_be;
                         if (bheap_node_in_heap(be_server->hn)) {
                                 TRACE_SUB("deleting be server %d",
@@ -845,11 +1226,20 @@ static void check_for_global_preempt(void)
                                 bheap_delete(server_order, &be_ready_servers,
                                              be_server->hn);
                         }
+                        next_server = be_server;
+                } else { /* Slack */
+                        next_task = next_slack;
+                        next_server = slack_server;
+                        list_del(&slack_server->list);
                 }
                 BUG_ON(!next_task);
                 TRACE_TASK_SUB(next_task, "preempting on P%d", entry->cpu);
-                remove(get_rt_domain(entry, next_task), next_task);
-                preempt(entry, next_task, be_server);
+
+                if (next_server != slack_server && is_queued(next_task))
+                        remove(get_rt_domain(entry, next_task), next_task);
+                else if (next_slack)
+                        take_next_slack(next_slack);
+                preempt(entry, next_task, next_server);
 
         loop_end:
                 TRACE_SUB("14");
@@ -868,15 +1258,18 @@ static void check_for_hrt_preempt(cpu_entry_t *entry)
 
         TRACE_SUB("checking for HRT preempt on P%d", entry->cpu);
 
+        if (next_hrt)
+                reclaim_slack(&server->server);
+
         if (next_hrt &&
             (!entry->linked || !is_hrt(entry->linked) ||
              edf_preemption_needed(&server->hrt_domain, entry->linked))) {
 
                 TRACE_TASK_SUB(next_hrt, "preempting on CPU %d", entry->cpu);
                 remove(&server->hrt_domain, next_hrt);
-                preempt(entry, next_hrt, NULL);
+                preempt(entry, next_hrt, &server->server);
 
-                /* We might have just kicked off an SRT. Check to see if it
+                /* We might have just kicked off something. Check to see if it
                  * preempts anything.
                  */
                 if (curr && !is_hrt(curr))
@@ -900,14 +1293,14 @@ static void job_arrival(struct task_struct *task, cpu_entry_t *entry)
         TRACE_TASK_SUB(task, "Arriving on P%d", entry->cpu);
 
         if (is_hrt(task)) {
-                requeue(task, &entry->hrt_server.hrt_domain);
+                requeue(task, &entry->hrt_server.hrt_domain, NULL);
                 check_for_hrt_preempt(entry);
         } else if (is_srt(task)) {
-                requeue(task, &srt_domain);
+                requeue(task, &srt_domain, NULL);
                 check_for_global_preempt();
         } else /* BE */ {
                 was_empty = !__jobs_pending(&be_domain);
-                requeue(task, &be_domain);
+                requeue(task, &be_domain, NULL);
 
                 /* Only way this could cause a preemption is if
                  * an eligible BE server could not queue up a task.
@@ -917,51 +1310,6 @@ static void job_arrival(struct task_struct *task, cpu_entry_t *entry)
         }
 }
 
-/*
- * Selects and links the next task for the given CPU.
- */
-static void edf_hsb_pick_next(cpu_entry_t *entry)
-{
-        task_class_t class;
-        lt_t deadline;
-        struct task_struct *next_hrt, *next_srt, *next_be;
-        server_t *be_server;
-
-        BUG_ON(entry->linked);
-
-        next_hrt = next_eligible_hrt(&entry->hrt_server);
-
-        if (next_hrt) {
-                /* HRT is next task */
-                link_task_to_cpu(entry, next_hrt, NULL);
-                remove(&entry->hrt_server.hrt_domain, next_hrt);
-        } else {
-                class = next_global_task(&next_srt,
-                                         &be_server,
-                                         &deadline);
-                if (next_srt) {
-                        remove(&srt_domain, next_srt);
-                        link_task_to_cpu(entry, next_srt, NULL);
-                } else if (be_server) {
-                        next_be = __take_ready(&be_domain);
-
-                        if (next_be) {
-                                TRACE_SUB("deleting be server %d",
-                                          be_server->id);
-                                bheap_delete(server_order, &be_ready_servers,
-                                             be_server->hn);
-                                link_task_to_cpu(entry, next_be, be_server);
-                        } else {
-                                /* Nothing to schedule! Try SRT */
-                                next_srt = __take_ready(&srt_domain);
-                                if (!next_srt)
-                                        return;
-                                link_task_to_cpu(entry, next_srt, NULL);
-                        }
-                }
-        }
-}
-
 /******************************************************************************
  * Timer methods
  ******************************************************************************/
@@ -1069,26 +1417,37 @@ static enum hrtimer_restart slack_timer_fire(struct hrtimer *timer)
 
 static void job_completion(cpu_entry_t *entry, struct task_struct* task)
 {
-        server_t *srt_server;
+        server_t *server = entry->linked_server;
         set_rt_flags(task, RT_F_SLEEP);
 
         TRACE_TASK_SUB(task, "completed");
 
         unlink(task);
 
-        if (is_srt(task)) {
-                srt_server = tsk_rt(task)->plugin_data;
+        donate_slack(server, task);
+
+        if (server->type == S_SLACK && is_srt(task)) {
+                TRACE_TASK_SUB(task, "slack server catching up");
+                tsk_rt(task)->job_params.job_no++;
+                add_slack(server);
+                check_slack_candidate(task);
+                sched_trace_task_completion(task, 1);
+                return;
+        }
+
+        BUG_ON(is_queued(task));
 
+        if (server->type == S_SRT) {
                 /* If the task is behind the server it must release immediately,
                  * leaving its release time and deadline unchanged.
                  */
-                if (srt_server->job_no > tsk_rt(task)->job_params.job_no) {
+                if (server->job_no > tsk_rt(task)->job_params.job_no) {
                         TRACE_TASK_SUB(task, "catching up");
                         tsk_rt(task)->job_params.job_no++;
                 } else {
                         /* Otherwise release them both */
                         prepare_for_next_period(task);
-                        server_release(srt_server);
+                        server_release(server);
                 }
         } else {
                 prepare_for_next_period(task);
@@ -1115,9 +1474,9 @@ static void server_completed(server_t *server, struct task_struct *task)
         TRACE_TASK_TIMER(task, "server %d completed, task exec: %llu",
                          server->id, get_exec_time(task));
         BUG_ON(entry->linked != task);
-        sched_trace_action(entry->linked, 1);
+        //sched_trace_action(entry->linked, 1);
 
-        if (is_srt(task)) {
+        if (server->type == S_SRT) {
                 TRACE_TASK_SUB(task, "must wait on server");
 
                 /* The job must now take the priority and release time
@@ -1131,6 +1490,8 @@ static void server_completed(server_t *server, struct task_struct *task)
                 tsk_rt(task)->job_params.release  = server->deadline;
                 tsk_rt(task)->job_params.deadline = server->deadline +
                         get_rt_period(task);
+
+                check_slack_candidate(task);
         }
 
         /* Someone else may have brought this server forward.
@@ -1143,14 +1504,15 @@ static void server_completed(server_t *server, struct task_struct *task)
                 hrt_server = container_of(server, hrt_server_t, server);
                 TRACE_SUB("P%d no longer ready", entry->cpu);
                 hrt_server->ready = 0;
-                }
+        }
 
         unlink(task);
-        requeue(task, get_rt_domain(entry, task));
+        requeue(task, get_rt_domain(entry, task), server);
 
         /* Need to pick the next task to run */
-        edf_hsb_pick_next(entry);
-        preempt_if_preemptable(entry->scheduled, entry->cpu);
+        check_for_global_preempt();
+        if (!entry->linked)
+                preempt_if_preemptable(entry->scheduled, entry->cpu);
 }
 
 static void hrt_server_released(server_t *server)
@@ -1169,14 +1531,16 @@ static void hrt_server_released(server_t *server)
         if (entry->linked && is_hrt(entry->linked) &&
             !is_eligible(entry->linked, hrt_server)) {
 
-                requeue(entry->linked, &hrt_server->hrt_domain);
+                requeue(entry->linked, &hrt_server->hrt_domain,
+                        entry->linked_server);
                 unlink(entry->linked);
 
                 server_release(server);
                 edf_hsb_pick_next(entry);
                 preempt_if_preemptable(entry->scheduled, entry->cpu);
         } else {
-                /* Otherwise check to see if a different task should                                                                                   * be running.
+                /* Otherwise check to see if a different task should
+                 * be running.
                  */
                 check_for_hrt_preempt(entry);
 
@@ -1204,7 +1568,7 @@ static void servers_released(struct list_head *servers)
         list_for_each(pos, servers) {
                 server = list_entry(pos, server_t, release_list);
 
-                if (server->type == RT_CLASS_BEST_EFFORT) {
+                if (server->type == S_BE) {
                         was_be = 1;
                         BUG_ON(bheap_node_in_heap(server->hn));
                         TRACE_SUB("inserting be server %d", server->id);
@@ -1249,7 +1613,7 @@ static int admit_be_server(unsigned long long wcet,
         be_server = kmalloc(sizeof(server_t), GFP_ATOMIC);
         server_init(be_server, BE_SERVER_BASE + ++curr_be,
                     wcet, period, 1);
-        be_server->type = RT_CLASS_BEST_EFFORT;
+        be_server->type = S_BE;
 
         TRACE("created BE server %d (%llu, %llu)\n", be_server->id,
               wcet, period);
@@ -1314,7 +1678,7 @@ static int admit_hrt_server(unsigned long long wcet,
         hrt_server->no_slack = 0;
 
         server_init(&hrt_server->server, cpu, wcet, period, 1);
-        hrt_server->server.type = RT_CLASS_HARD;
+        hrt_server->server.type = S_HRT;
 
         edf_domain_init(&hrt_server->hrt_domain, NULL,
                         release_hrt_jobs);
@@ -1603,8 +1967,6 @@ static struct task_struct* edf_hsb_schedule(struct task_struct *prev)
         entry->scheduled = entry->linked;
         sched_state_task_picked();
 
-        BUG_ON(entry->scheduled && is_queued(entry->scheduled));
-
         if (entry->scheduled)
                 TRACE_TASK(entry->scheduled, "scheduled at %llu\n",
                            TIME(litmus_clock()));
@@ -1637,7 +1999,8 @@ static void edf_hsb_task_new(struct task_struct *task, int on_rq,  int running)
                 srt_server = kmalloc(sizeof(server_t), GFP_ATOMIC);
                 server_init(srt_server, task->pid, get_exec_cost(task),
                             get_rt_period(task), 0);
-                srt_server->type = RT_CLASS_SOFT;
+                srt_server->type = S_SRT;
+                srt_server->data = task;
                 srt_server->job_no = tsk_rt(task)->job_params.job_no;
                 server_release_at(srt_server, get_release(task));
         }
@@ -1758,6 +2121,8 @@ static int __init init_edf_hsb(void)
         bheap_init(&cpu_heap);
         bheap_init(&be_ready_servers);
         INIT_LIST_HEAD(&be_servers);
+        INIT_LIST_HEAD(&slack_queue);
+        INIT_LIST_HEAD(&slack_candidates);
 
         for_each_online_cpu(cpu) {
                 entry      = &per_cpu(cpu_entries, cpu);