Better memory management, removed unnecessary preemptions, moved data out of

rt_params and into plugin data, better list managment logic.

1 files changed, 164 insertions, 105 deletions

diff --git a/litmus/sched_edf_hsb.c b/litmus/sched_edf_hsb.c
index d75f8a04b362..e3cd78d29ce8 100644
--- a/litmus/sched_edf_hsb.c
+++ b/litmus/sched_edf_hsb.c
@@ -20,7 +20,7 @@
  * TODO move slack completion into release
  * TODO fix concurrent arms
  * TODO slack and BE servers
- *
+ * TODO start servers should no longer be cessary
  */
 #include <linux/module.h>
 #include <linux/uaccess.h>
@@ -63,21 +63,22 @@
  * Useful debugging macros. Remove for actual use as they cause
  * a lot of lock contention.
  */
-//#ifdef DEBUG_EDF_HSB
-atomic_t servers_running = ATOMIC_INIT(0);
-/* #define TRACE_SUB(fmt, args...)                                      \ */
-/*      sched_trace_log_message("%d P%d      [%s@%s:%d]: " fmt "\n", \ */
-/*                              TRACE_ARGS,  ## args) */
-/* #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 */
+#ifdef DEBUG_EDF_HSB
+atomic_t servers_running = ATOMIC_INIT(0); /* TODO should be unnecessary */
+#define TRACE_SUB(fmt, args...)                                      \
+        sched_trace_log_message("%d P%d      [%s@%s:%d]: " fmt "\n", \
+                                TRACE_ARGS,  ## args)
+#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
+#endif
+
 typedef enum {
         S_HRT,
         S_SRT,
@@ -88,7 +89,7 @@ typedef enum {
 typedef struct {
         server_t        server;
         rt_domain_t     hrt_domain;  /* EDF for HRT tasks assigned here */
-        int             ready;
+        int             ready;       /* False if waiting for next release */
         int             no_slack;
         struct hrtimer  slack_timer; /* Server has no slack when:
                                       * (deadline - budget) <= current_time.
@@ -108,52 +109,74 @@ typedef struct {
         struct bheap_node*      hn; /* For the cpu_heap */
 } cpu_entry_t;
 
+typedef struct task_data {
+        server_t           *srt_server; /* If the task is SRT, its server */
+        struct list_head    slack_list; /* List of slack canditates */
+        struct task_struct *owner;
+} task_data_t;
+
 /* CPU state */
 DEFINE_PER_CPU_SHARED_ALIGNED(cpu_entry_t, cpu_entries);
 static struct bheap cpu_heap;
 static struct bheap_node cpu_heap_node[NR_CPUS];
 
-static rt_domain_t srt_domain;  /* SRT tasks (and servers) */
-static rt_domain_t be_domain;   /* BE tasks  */
+/* Task domains */
+static rt_domain_t srt_domain;
+static rt_domain_t be_domain;
 
-static server_domain_t server_domain; /* Useful tools for server scheduling */
+/* Useful tools for server scheduling */
+static server_domain_t server_domain;
 
-static struct list_head be_servers;             /* All BE servers */
-static struct bheap     be_ready_servers;       /* Runnable BE servers */
+/* BE server support */
+static struct list_head be_servers;
+static struct bheap     be_ready_servers;
 
+/* Slack support */
 static struct list_head slack_queue;
 static struct list_head slack_candidates;
 
-static int release_master; /* CPU which will release tasks and global servers */
+/* CPU which will release tasks and global servers */
+static int edf_hsb_release_master;
 
+static struct kmem_cache *task_data_cache;
 static struct proc_dir_entry *edf_hsb_proc_dir = NULL;
 static struct sched_plugin edf_hsb_plugin __cacheline_aligned_in_smp;
 
-#define local_cpu_entry         (&__get_cpu_var(cpu_entries))
 #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 task_data(task)         ((task_data_t*)tsk_rt(task)->plugin_data)
+#define task_srt_server(task)   ((server_t*)task_data(task)->srt_server)
+#define local_cpu_entry         (&__get_cpu_var(cpu_entries))
 #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)
+static inline server_t* task_slack_server(struct task_struct *task)
 {
-        if ((list->next == list->prev && list->prev  == list) ||
-            (list->next == LIST_POISON1 && list->prev == LIST_POISON2))
-                return 0;
-        else
-                return 1;
+        server_t *slack_server = NULL;
+        if (task->rt_param.linked_on != NO_CPU) {
+                slack_server = task_linked_entry(task)->linked_server;
+                if (slack_server->type != S_SLACK)
+                        slack_server = NULL;
+        }
+        return slack_server;
+}
+
+static inline int head_in_list(struct list_head *node)
+{
+        return !(node->next == node->prev && node->prev == node);
+}
+
+static task_data_t* task_data_alloc(int gfp_flags)
+{
+        return kmem_cache_alloc(task_data_cache, gfp_flags);
+}
+
+static void task_data_free(task_data_t* data)
+{
+        kmem_cache_free(task_data_cache, data);
 }
 
-/* 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;
@@ -171,11 +194,11 @@ static server_t* next_eligible_slack(void)
                                   SERVER_ARGS(next_slack));
                         sched_trace_action(NULL, 7);
 
-                        list_del(&next_slack->list);
+                        list_del_init(&next_slack->list);
                         donator = (server_t*)next_slack->data;
                         donator->data = NULL;
                         server_destroy(next_slack);
-                        kfree(next_slack);
+                        server_free(next_slack);
 
                         next_slack = NULL;
                 }
@@ -197,8 +220,6 @@ static void add_slack(server_t *slack)
         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)) {
@@ -209,26 +230,33 @@ static void add_slack(server_t *slack)
         list_add(&slack->list, &slack_queue);
 }
 
+static inline struct task_struct* get_candidate(struct list_head *pos)
+{
+        struct task_struct *task = NULL;
+        task_data_t *data;
+        if (!list_empty(pos)) {
+                data = list_entry(pos, task_data_t, slack_list);
+                task = data->owner;
+        }
+        return task;
+}
+
 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);
+                queued = get_candidate(pos);
                 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,
+                        __list_add(&task_data(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);
+        list_add(&task_data(task)->slack_list, &slack_candidates);
 }
 
 static struct task_struct* next_eligible_hrt(hrt_server_t*);
@@ -264,7 +292,7 @@ static void donate_slack(server_t *donator, struct task_struct *was_scheduled)
 
         TRACE_SERVER_SUB(donator, "donated %llu slack", TIME(donator->budget));
         sched_trace_action(was_scheduled, 9);
-        slack = kmalloc(sizeof(server_t), GFP_ATOMIC);
+        slack = server_alloc(GFP_ATOMIC);
         server_init(slack, donator->id, donator->budget,
                     donator->period, 0);
         slack->type = S_SLACK;
@@ -286,8 +314,7 @@ static struct task_struct* pick_next_slack(server_t *slack, cpu_entry_t *entry)
         if (!slack)
                 goto out;
         if (!list_empty(&slack_candidates)) {
-                rv = list_entry(slack_candidates.next, struct task_struct,
-                                rt_param.slack_list);
+                rv = get_candidate(slack_candidates.next);
                 TRACE_TASK_SUB(rv, "is next slack");
         } else if (entry && entry->linked &&
                    entry->linked_server->type == S_SLACK) {
@@ -297,25 +324,29 @@ static struct task_struct* pick_next_slack(server_t *slack, cpu_entry_t *entry)
         return rv;
 }
 
-static void take_next_slack(struct task_struct *task)
+static void take_slack_candidate(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;
+        if (head_in_list(&task_data(task)->slack_list)) {
+                TRACE_TASK_SUB(task, "deleting candidate");
+                list_del_init(&task_data(task)->slack_list);
         } else {
-                TRACE_TASK_SUB(task, "can't delete slack");
+                TRACE_TASK_SUB(task, "can't delete candidate");
         }
 }
 
 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()) &&
+        if (is_srt(task) &&
+            /* The SRT task is not ahead of its server */
+            task_srt_server(task)->job_no >= task_job_no(task) &&
+            /* The task has yet to be released */
+            lt_after(get_release(task), litmus_clock()) &&
+            /* The task didn't just complete */
             get_rt_flags(task) != RT_F_SLEEP &&
-            !tsk_rt(task)->slack_candidate)
-{
+            /* The task hasn't already been added to the list */
+            !head_in_list(&task_data(task)->slack_list)) {
+
                 add_slack_candidate(task);
                 sched_trace_action(task, 8);
         }
@@ -454,8 +485,8 @@ static void slack_timer_arm(hrt_server_t *hrt_server)
         entry = container_of(hrt_server, cpu_entry_t, hrt_server);
 
 #ifdef SLACK_ON_MASTER
-        if (release_master != NO_CPU)
-                cpu = release_master;
+        if (edf_hsb_release_master != NO_CPU)
+                cpu = edf_hsb_release_master;
         else
 #endif
                 cpu = entry->cpu;
@@ -548,12 +579,14 @@ static noinline void link_server(cpu_entry_t *entry,
         if (next_server->type == S_SRT) {
                 TRACE_TASK_SUB(entry->linked, "resuming SRT server,"
                                "budget*: %llu, exec_time: %llu, deadline: %llu,"
-                               "job_no: %d",
+                               "tjob_no: %d, sjob_no: %d sdead: %llu",
                                next_server->budget, get_exec_time(entry->linked),
-                               get_deadline(entry->linked), next_server->job_no);
+                               get_deadline(entry->linked),
+                               task_job_no(entry->linked),
+                               next_server->job_no,
+                               next_server->deadline);
                 BUG_ON(lt_after(next_server->budget,
                                 get_exec_cost(entry->linked)));
-
                 BUG_ON(next_server->job_no < task_job_no(entry->linked));
                 BUG_ON(lt_after(get_deadline(entry->linked),
                                 next_server->deadline));
@@ -563,10 +596,10 @@ static noinline void link_server(cpu_entry_t *entry,
                 slack_timer_cancel(&entry->hrt_server);
         } else if (next_server->type == S_SLACK) {
                 /* Should have already been removed */
-                BUG_ON(tsk_rt(entry->linked)->slack_candidate);
+                BUG_ON(head_in_list(&task_data(entry->linked)->slack_list));
+
                 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(bheap_node_in_heap(next_server->hn));
                 sched_trace_action(entry->linked, 200 + next_server->id);
@@ -610,10 +643,6 @@ 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 &&
@@ -864,17 +893,17 @@ static struct task_struct* next_eligible_srt(void)
          * to overutilization of the system.
          */
         if (next_srt) {
-                srt_server = tsk_rt(next_srt)->plugin_data;
+                srt_server = task_srt_server(next_srt);
                 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);
+                /* Ensure that no slack server will try to schedule this */
+                take_slack_candidate(next_srt);
+        }
 
         return next_srt;
 }
@@ -1016,6 +1045,8 @@ static void preempt(cpu_entry_t *entry, struct task_struct *next,
 {
         rt_domain_t *domain;
 
+        BUG_ON(next == entry->linked);
+
         if (entry->linked) {
                 domain = get_rt_domain(entry, entry->linked);
                 requeue(entry->linked, domain, entry->linked_server);
@@ -1042,12 +1073,17 @@ 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);
+        cpu_entry_t *entry = NULL;
+        server_t *slack_server = NULL;
 
         BUG_ON(!is_srt(task));
 
-        if (!slack_server || !slack_server->running)
+        if (tsk_rt(task)->linked_on != NO_CPU) {
+                entry = task_linked_entry(task);
+                if (entry->linked_server->type == S_SLACK)
+                        slack_server = entry->linked_server;
+        }
+        if (!slack_server)
                 goto out;
 
         TRACE_TASK_SUB(task, "slack preempt");
@@ -1056,7 +1092,7 @@ static cpu_entry_t* check_for_slack_preempt(struct task_struct *task,
         preempted = entry;
 
         unlink(task);
-        take_next_slack(task);
+        take_slack_candidate(task);
  out:
         return preempted;
 }
@@ -1111,8 +1147,8 @@ static void edf_hsb_pick_next(cpu_entry_t *entry)
                         next_slack = pick_next_slack(slack_server, NULL);
 
                         if (next_slack) {
-                                take_next_slack(next_slack);
-                                list_del(&slack_server->list);
+                                take_slack_candidate(next_slack);
+                                list_del_init(&slack_server->list);
                                 TRACE_TASK_SUB(next_slack, "taking");
                                 link_task_to_cpu(entry, next_slack, slack_server);
                         }
@@ -1211,7 +1247,7 @@ static void check_for_global_preempt(void)
                         /* Swap two slack servers here */
                         if (slack_server && entry->linked_server->type == S_SLACK) {
                                 TRACE_SUB("9.5");
-                                list_del(&slack_server->list);
+                                list_del_init(&slack_server->list);
                                 unlink_server(entry, slack_server);
                                 link_server(entry, slack_server);
                                 update_cpu_position(entry);
@@ -1242,7 +1278,7 @@ static void check_for_global_preempt(void)
                 } else { /* Slack */
                         next_task = next_slack;
                         next_server = slack_server;
-                        list_del(&slack_server->list);
+                        list_del_init(&slack_server->list);
                 }
                 BUG_ON(!next_task);
                 TRACE_TASK_SUB(next_task, "preempting on P%d", entry->cpu);
@@ -1250,7 +1286,7 @@ static void check_for_global_preempt(void)
                 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);
+                        take_slack_candidate(next_slack);
                 preempt(entry, next_task, next_server);
 
         loop_end:
@@ -1522,8 +1558,8 @@ static void server_completed(server_t *server, struct task_struct *task)
         requeue(task, get_rt_domain(entry, task), server);
 
         /* Need to pick the next task to run */
-        check_for_global_preempt();
-        if (!entry->linked)
+        edf_hsb_pick_next(entry);
+        if (!entry->linked || entry->linked != task)
                 preempt_if_preemptable(entry->scheduled, entry->cpu);
 }
 
@@ -1542,7 +1578,7 @@ static void hrt_server_released(server_t *server)
         /* Boot off an HRT task which has become uneligible */
         if (entry->linked && is_hrt(entry->linked) &&
             !is_eligible(entry->linked, hrt_server)) {
-
+                /* TODO: necessary?? */
                 requeue(entry->linked, &hrt_server->hrt_domain,
                         entry->linked_server);
                 unlink(entry->linked);
@@ -1622,7 +1658,7 @@ static int admit_be_server(unsigned long long wcet,
                 goto out;
         }
 
-        be_server = kmalloc(sizeof(server_t), GFP_ATOMIC);
+        be_server = server_alloc(GFP_ATOMIC);
         server_init(be_server, BE_SERVER_BASE + ++curr_be,
                     wcet, period, 1);
         be_server->type = S_BE;
@@ -1662,13 +1698,12 @@ static void stop_be_servers(void)
         list_for_each_safe(pos, safe, &be_servers) {
                 be_server = list_entry(pos, server_t, list);
 
-                list_del(pos);
+                list_del_init(pos);
                 if (bheap_node_in_heap(be_server->hn))
                         bheap_delete(server_order, &be_ready_servers,
                                      be_server->hn);
-
-                kfree(be_server->hn);
-                kfree(be_server);
+                server_destroy(be_server);
+                server_free(be_server);
         }
 }
 
@@ -1781,8 +1816,8 @@ static void start_servers(lt_t time)
                           cpu, TIME(slack_fire), &entry->hrt_server.slack_timer);
 
 #ifdef SLACK_ON_MASTER
-                if (release_master != NO_CPU)
-                        slack_cpu = release_master;
+                if (edf_hsb_release_master != NO_CPU)
+                        slack_cpu = edf_hsb_release_master;
                 else
 #endif
                         slack_cpu = cpu;
@@ -1827,11 +1862,11 @@ static long edf_hsb_activate_plugin(void)
 #endif
 
 #ifdef CONFIG_RELEASE_MASTER
-        release_master = atomic_read(&release_master_cpu);
+        edf_hsb_release_master = atomic_read(&release_master_cpu);
 #else
-        release_master = NO_CPU;
+        edf_hsb_release_master = NO_CPU;
 #endif
-        server_domain.release_master = release_master;
+        server_domain.release_master = edf_hsb_release_master;
 
         TRACE("activating EDF-HSB plugin.\n");
         return 0;
@@ -1915,8 +1950,11 @@ static void edf_hsb_task_exit(struct task_struct *task)
                 entry->scheduled = NULL;
                 tsk_rt(task)->scheduled_on = NO_CPU;
         }
-        if (is_srt(task))
-                kfree(tsk_rt(task)->plugin_data);
+        if (is_srt(task)) {
+                server_destroy(task_srt_server(task));
+                server_free(task_srt_server(task));
+                task_data_free(tsk_rt(task)->plugin_data);
+        }
 
         raw_spin_unlock_irqrestore(global_lock, flags);
 }
@@ -1996,7 +2034,8 @@ static struct task_struct* edf_hsb_schedule(struct task_struct *prev)
 static void edf_hsb_task_new(struct task_struct *task, int on_rq,  int running)
 {
         unsigned long flags;
-        server_t *srt_server = NULL;
+        server_t *srt_server;
+        task_data_t *data = NULL;
         cpu_entry_t *entry = task_sched_entry(task);
 
         TRACE_TASK(task, "edf_hsb: task new at %llu\n", TIME(litmus_clock()));
@@ -2006,17 +2045,21 @@ static void edf_hsb_task_new(struct task_struct *task, int on_rq,  int running)
         /* Setup job parameters */
         release_at(task, litmus_clock());
 
-        /* Create struct to store SRT server state on suspension */
         if (is_srt(task)) {
-                srt_server = kmalloc(sizeof(server_t), GFP_ATOMIC);
+                /* Create SRT server */
+                srt_server = server_alloc(GFP_ATOMIC);
                 server_init(srt_server, task->pid, get_exec_cost(task),
                             get_rt_period(task), 0);
                 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));
+                srt_server->job_no = 1;
+
+                data = task_data_alloc(GFP_ATOMIC);
+                data->owner = task;
+                data->srt_server = srt_server;
+                INIT_LIST_HEAD(&data->slack_list);
         }
-        tsk_rt(task)->plugin_data = srt_server;
+        tsk_rt(task)->plugin_data = data;
 
         /* Already running, update the cpu entry.
          * This tends to happen when the first tasks enter the system.
@@ -2122,6 +2165,8 @@ static int __init init_edf_hsb(void)
                               admit_hrt_server, list_hrt_servers,
                               stop_hrt_servers);
 
+        task_data_cache = KMEM_CACHE(task_data, SLAB_PANIC);
+
         /* Global domains */
         edf_domain_init(&srt_domain, NULL, release_srt_jobs);
         rt_domain_init(&be_domain, be_ready_order,
@@ -2165,11 +2210,25 @@ static int __init init_edf_hsb(void)
 
 static void exit_edf_hsb(void)
 {
+        int cpu;
+        cpu_entry_t *entry;
+
+        stop_be_servers();
+        stop_hrt_servers();
+
         server_proc_exit(edf_hsb_proc_dir, BE_PROC_NAME);
         server_proc_exit(edf_hsb_proc_dir, HRT_PROC_NAME);
 
+        server_domain_destroy(&server_domain);
+
+        for_each_online_cpu(cpu) {
+                entry = &per_cpu(cpu_entries, cpu);
+                server_destroy(&entry->hrt_server.server);
+        }
+
         if (edf_hsb_proc_dir) {
                 remove_plugin_proc_dir(&edf_hsb_plugin);
+                /* TODO: is this wrong? */
                 edf_hsb_proc_dir = NULL;
         }
 }