1 files changed, 330 insertions, 145 deletions

diff --git a/litmus/servers.c b/litmus/servers.c
index a43aad336367..9ee58198b0d6 100644
--- a/litmus/servers.c
+++ b/litmus/servers.c
@@ -1,9 +1,13 @@
+/*
+ * TODO: memory leaks for stopping
+ */
 #include <linux/hrtimer.h>
 #include <linux/percpu.h>
 #include <linux/sched.h>
 #include <linux/uaccess.h>
 #include <linux/ctype.h>
 
+#include <litmus/bheap.h>
 #include <litmus/litmus.h>
 #include <litmus/litmus_proc.h>
 #include <litmus/sched_trace.h>
@@ -11,6 +15,9 @@
 
 #define DEBUG_SERVERS
 
+/*  Not working */
+/* #define COMPLETION_ON_MASTER */
+
 #define TIME(x)                                 \
         ({lt_t y = x;                           \
         do_div(y, NSEC_PER_MSEC);               \
@@ -81,6 +88,7 @@ static inline int timer_cancel(struct hrtimer *timer)
 
 static int completion_timer_arm(server_domain_t* domain, int cpu)
 {
+        int err = 0, on_cpu;
         lt_t now = litmus_clock();
         server_t *server = domain->running[cpu];
         lt_t budget_exhausted = now + server->budget;
@@ -95,13 +103,40 @@ static int completion_timer_arm(server_domain_t* domain, int cpu)
                 return 0;
         }
 
+        if (domain->completion_timers[cpu].armed) {
+                TRACE_SUB(server, "cannot arm completion, waiting for arm");
+                return 0;
+        }
+
+        /* This happens when a server is run late enough that it would complete
+         * after its released. This will almost certainly cause a reschedule,
+         * so we just force the server to complete here and trust the callback
+         * to get things right.
+         */
+        if (lt_before_eq(server->deadline, budget_exhausted)) {
+                budget_exhausted = server->deadline;
+        }
+
         TRACE_SUB(server, "start time: %llu", server->start_time);
 
+#ifdef COMPLETION_ON_MASTER
+        if (domain->release_master != NO_CPU)
+                on_cpu = domain->release_master;
+        else
+#endif
+                on_cpu = cpu;
+
         if (cpu != smp_processor_id()) {
-                hrtimer_start_on(cpu, &domain->completion_timers[cpu].info,
-                                 &domain->completion_timers[cpu].timer,
-                                 ns_to_ktime(budget_exhausted),
-                                 HRTIMER_MODE_ABS_PINNED);
+                err = hrtimer_start_on(on_cpu,
+                                       &domain->completion_timers[cpu].info,
+                                       &domain->completion_timers[cpu].timer,
+                                       ns_to_ktime(budget_exhausted),
+                                       HRTIMER_MODE_ABS_PINNED);
+                if (err) {
+                        TRACE_SUB(server, "failed to arm completion");
+                } else {
+                        TRACE_SUB(server, "success on P%d!", on_cpu);
+                }
         } else {
                 __hrtimer_start_range_ns(&domain->completion_timers[cpu].timer,
                                          ns_to_ktime(budget_exhausted),
@@ -132,9 +167,6 @@ void server_run(server_t *server, struct task_struct *task,
         server->running = 1;
         server->start_time = litmus_clock();
 
-        /* TODO REMOVE ME */
-        server->domain = domain;
-
         domain->running[cpu] = server;
         domain->completion_timers[cpu].armed =completion_timer_arm(domain, cpu);
 
@@ -147,28 +179,26 @@ static enum hrtimer_restart completion_timer_fire(struct hrtimer *timer)
         unsigned long flags;
         enum hrtimer_restart rv;
         struct task_struct *was_running;
-        completion_timer_t *container;
+        completion_timer_t *completion_timer;
         server_domain_t *domain;
         server_t *server;
         lt_t budget_exhausted;
 
         rv  = HRTIMER_NORESTART;
-        cpu = smp_processor_id();
 
-
-        /* Use fancy pointer arithmetic to get the domain */
-        container = container_of(timer, completion_timer_t, timer);
-        domain = container->domain;
+        completion_timer = container_of(timer, completion_timer_t, timer);
+        domain = completion_timer->domain;
+        cpu = completion_timer->cpu;
 
         raw_spin_lock_irqsave(domain->timer_lock, flags);
 
-        server = domain->running[cpu];
-        TRACE_TIMER(server, "completion timer firing on P%d, remaining budget: %llu",
-                    cpu, server->budget);
+        _TRACE_TIMER("completion timer firing on P%d");
 
         /* We got the lock before someone tried to re-arm. Proceed. */
-        if (domain->completion_timers[cpu].armed) {
+        if (completion_timer->armed) {
+                server = domain->running[cpu];
                 TRACE_SUB(server, "completed");
+
                 was_running = server->scheduled;
 
                 server->budget     = 0;
@@ -183,13 +213,17 @@ static enum hrtimer_restart completion_timer_fire(struct hrtimer *timer)
         /* Someone either beat us to the lock or hooked up a new server
          * when we called server_completed. Rearm the timer.
          */
-        if (domain->running[cpu] && !domain->completion_timers[cpu].armed) {
-                TRACE_SUB(server, "rearming on P%d", cpu);
+        if (domain->running[cpu] && !completion_timer->armed) {
                 server = domain->running[cpu];
+                TRACE_SUB(server, "rearming on P%d", cpu);
                 budget_exhausted = server->start_time + server->budget;
                 hrtimer_set_expires(timer, ns_to_ktime(budget_exhausted));
-                domain->completion_timers[cpu].armed = 1;
+                completion_timer->armed = 1;
                 rv = HRTIMER_RESTART;
+        } else {
+                atomic_set(&completion_timer->info.state,
+                           HRTIMER_START_ON_INACTIVE);
+
         }
 
         raw_spin_unlock_irqrestore(domain->timer_lock, flags);
@@ -197,83 +231,48 @@ static enum hrtimer_restart completion_timer_fire(struct hrtimer *timer)
         return rv;
 }
 
-static enum hrtimer_restart release_timer_fire(struct hrtimer *timer)
-{
-        unsigned long flags;
-        int was_running;
-        pserver_t *server = container_of(timer, pserver_t, release_timer);
-        struct task_struct *was_scheduled;
-
-        if (server->server.timer_lock)
-                raw_spin_lock_irqsave(server->server.timer_lock, flags);
-        else
-                local_irq_save(flags);
-
-        was_scheduled = server->server.scheduled;
-
-        TRACE_TIMER(&server->server,
-                    "release timer firing, remaining budget: %llu",
-                    get_server_budget(server));
-
-        was_running = server->server.running;
-
-        /* This would have been armed if the budget would exhaust
-         * after the server release.
-         */
-        if (was_running)
-                timer_cancel(&server->server.domain->completion_timers[
-                            server->server.scheduled->rt_param.linked_on].timer);
-
-
-        pserver_release(server);
-        server->post_release(server);
-
-        /* Need to arm the budget timer if the server continues running
-         * the same task.
-         */
-        if (was_running && was_scheduled == get_server_scheduled(server))
-                completion_timer_arm(server->server.domain, was_scheduled->rt_param.linked_on );
-
-        hrtimer_set_expires(timer, ns_to_ktime(server->deadline));
-
-        if (server->server.timer_lock)
-                raw_spin_unlock_irqrestore(server->server.timer_lock, flags);
-        else
-                local_irq_restore(flags);
+struct kmem_cache *server_release_cache; /* In litmus.c */
+static enum hrtimer_restart release_servers_fire(struct hrtimer *timer);
 
-        return HRTIMER_RESTART;
+/*
+ * Initialize heap.
+ */
+static server_release_heap_t* release_heap_alloc(int gfp_flags)
+{
+        server_release_heap_t *rh;
+        rh = kmem_cache_alloc(server_release_cache, gfp_flags);
+        if (rh) {
+                hrtimer_init(&rh->timer, CLOCK_MONOTONIC, HRTIMER_MODE_ABS);
+                rh->timer.function = release_servers_fire;
+        }
+        return rh;
 }
 
-void server_init(server_t *server, int id, raw_spinlock_t *timer_lock)
+void server_init(server_t *server, int id, lt_t wcet, lt_t period, int grouped)
 {
         server->id = id;
+        server->wcet = wcet;
+        server->period = period;
 
-        server->running = 0;
-        server->budget  = 0;
-        server->job_no  = 1; /* NOT SURE */
+        server->deadline = 0;
+        server->release = 0;
+        server->budget = 0;
         server->start_time = 0;
-        server->scheduled  = NULL;
-        server->timer_lock = timer_lock;
-}
 
-void pserver_init(pserver_t *server, int id, raw_spinlock_t *timer_lock,
-                  lt_t wcet, lt_t period)
-{
-        server_init(&server->server, id, timer_lock);
-
-        server->wcet   = wcet;
-        server->period = period;
+        server->running = 0;
+        server->job_no = 0;
+        server->scheduled = NULL;
 
-        server->deadline = 0;
-        server->post_release = NULL;
+        server->hn = kmalloc(sizeof(struct bheap_node), GFP_ATOMIC);
+        bheap_node_init(&server->hn, server);
+        INIT_LIST_HEAD(&server->list);
 
-        hrtimer_init(&server->release_timer,
-                     CLOCK_MONOTONIC,
-                     HRTIMER_MODE_ABS);
-        server->release_timer.function = release_timer_fire;
+        if (grouped) {
+                server->release_heap = release_heap_alloc(GFP_ATOMIC);
+                INIT_LIST_HEAD(&server->release_list);
+        }
 }
 
-
 /*
  * Handles subtraction of lt_t without underflows.
  */
@@ -297,75 +296,62 @@ void server_stop(server_t *server, server_domain_t *domain)
         }
 
         BUG_ON(!server->running);
-        cpu = server->scheduled->rt_param.linked_on;
-
         TRACE_SUB(server, "stopping server, start: %llu, end: %llu",
                   server->start_time, now);
 
+
+        /* Calculate remaining budget */
         elapsed_time = lt_subtract(now, server->start_time);
         server->budget -= elapsed_time;
 
+        TRACE_SUB(server, "new budget: %llu", TIME(server->budget));
+
+        /* Set domain state */
+        cpu = server->scheduled->rt_param.linked_on;
         domain->completion_timers[cpu].armed = 0;
         domain->running[cpu] = NULL;
         timer_cancel(&domain->completion_timers[cpu].timer);
 
-        TRACE_SUB(server, "new budget: %llu", TIME(server->budget));
-
-        server->running = 0;
-        server->scheduled = NULL;
+        /* Make server inactive */
+        server->running    = 0;
+        server->scheduled  = NULL;
         server->start_time = 0;
 }
 
-void pserver_start_releasing(pserver_t *server, lt_t time)
+void server_release(server_t *server)
 {
-        if (hrtimer_active(&server->release_timer))
-                timer_cancel(&server->release_timer);
+        BUG_ON(!server->deadline);
 
-        server->deadline = time;
-        pserver_release(server);
-
-        __hrtimer_start_range_ns(&server->release_timer,
-                                 ns_to_ktime(server->deadline),
-                                 0 /* delta */,
-                                 HRTIMER_MODE_ABS_PINNED,
-                                 0 /* no wakeup */);
-}
-
-void pserver_start_cpu_releasing(pserver_t *server, lt_t time, int cpu)
-{
-        if (hrtimer_active(&server->release_timer))
-                timer_cancel(&server->release_timer);
-
-        server->deadline = time;
-        pserver_release(server);
+        server->budget    = server->wcet;
+        server->release   = server->deadline;
+        server->deadline += server->period;
+        ++server->job_no;
 
-        hrtimer_start_on_info_init(&per_cpu(server_cpu_infos, cpu));
+        TRACE_SUB(server, "budget: %llu, release: %llu,"
+                  "deadline: %llu, period: %llu, job: %d",
+                  server->budget, server->release, server->deadline,
+                  server->period, server->job_no);
+        TRACE_SUB(server, "budget: %llu, release: %llu,"
+                  "deadline: %llu, period: %llu, job: %d",
+                  TIME(server->budget), TIME(server->release), TIME(server->deadline),
+                  TIME(server->period), server->job_no);
 
-        hrtimer_start_on(cpu, &per_cpu(server_cpu_infos, cpu),
-                         &server->release_timer,
-                         ns_to_ktime(server->deadline),
-                         HRTIMER_MODE_ABS_PINNED);
+        /* Need to reset for budget calculations */
+        if (server->running)
+                server->start_time = litmus_clock();
 }
 
-void pserver_stop_releasing(pserver_t *server)
+void server_release_at(server_t *server, lt_t time)
 {
-        if (hrtimer_active(&server->release_timer))
-                timer_cancel(&server->release_timer);
-
-        BUG_ON(get_server_running(server));
+        server->deadline = time;
+        server_release(server);
 
-        server->deadline = 0;
+        TRACE_SUB(server, "releasing at %llu", time);
 }
 
-void server_release(server_t *server, lt_t budget)
-{
-        server->budget = budget;
-        ++server->job_no;
-
-        /* Need to reset for budget calculations */
-        if (server->running)
-                server->start_time = litmus_clock();
-}
+/******************************************************************************
+ * Proc methods
+ ******************************************************************************/
 
 static int server_proc_read(char* page, char **start, off_t off,
                              int count, int *eof, void *data)
@@ -386,25 +372,21 @@ static int server_proc_read(char* page, char **start, off_t off,
         return length;
 }
 
-void server_proc_read_single(pserver_t *server, int cpu,
-                            struct proc_read_args *args)
+void server_proc_read_single(server_t *server, int cpu,
+                             struct proc_read_args *args)
 {
-        lt_t wcet, period;
-        wcet   = get_server_wcet(server);
-        period = get_server_period(server);
-
         if (cpu == NO_CPU) {
                 args->length +=
                         snprintf(args->page + args->length,
                                  PAGE_SIZE - args->length,
                                  "%8llu    %8llu\n",
-                                 TIME(wcet), TIME(period));
+                                 server->wcet, server->period);
         } else {
                 args->length +=
                         snprintf(args->page + args->length,
                                  PAGE_SIZE - args->length,
                                  "%8llu    %8llu    %3d\n",
-                                 TIME(wcet), TIME(period), cpu);
+                                 server->wcet, server->period, cpu);
         }
 }
 
@@ -509,8 +491,7 @@ static int server_proc_write(struct file *file, const char __user *input,
                 ret = server_param_check(wcet, period, cpu);
                 if (ret) goto loop_end;
 
-                ret = methods->admit_server(wcet * NSEC_PER_MSEC,
-                                            period * NSEC_PER_MSEC, cpu);
+                ret = methods->admit_server(wcet, period, cpu);
                 if (ret) {
                         printk(KERN_WARNING "Litmus plugin rejects server with "
                               "period: %llu, wcet: %llu, cpu: %d\n",
@@ -559,6 +540,10 @@ void server_proc_exit(struct proc_dir_entry *proc_dir, char *file)
         remove_proc_entry(file, proc_dir);
 }
 
+/******************************************************************************
+ * Domain methods
+ ******************************************************************************/
+
 void server_domain_init(server_domain_t *domain,
                         servers_released_t servers_released,
                         server_completed_t server_completed,
@@ -575,7 +560,7 @@ void server_domain_init(server_domain_t *domain,
         raw_spin_lock_init(&domain->tobe_lock);
 
 
-        domain->release_master = NO_CPU;
+        domain->release_master = release_master;
         domain->timer_lock = timer_lock;
         domain->server_completed = server_completed;
         domain->servers_released = servers_released;
@@ -587,6 +572,7 @@ void server_domain_init(server_domain_t *domain,
         for_each_online_cpu(i) {
                 domain->running[i] = NULL;
                 domain->completion_timers[i].armed = 0;
+                domain->completion_timers[i].cpu = i;
                 hrtimer_init(&domain->completion_timers[i].timer,
                              CLOCK_MONOTONIC,
                              HRTIMER_MODE_ABS);
@@ -603,13 +589,212 @@ void server_domain_exit(server_domain_t *domain)
         kfree(domain->running);
 }
 
-void add_server_release(server_t *server, server_domain_t *server_domain)
+static unsigned int time2slot(lt_t time)
+{
+        return (unsigned int) time2quanta(time, FLOOR) %
+                SERVER_RELEASE_QUEUE_SLOTS;
+}
+
+/*
+ * Send a list of servers to a client callback.
+ */
+static enum hrtimer_restart release_servers_fire(struct hrtimer *timer)
+{
+        unsigned long flags;
+        server_release_heap_t *rh;
+
+        _TRACE_SUB("on_release_timer(0x%p) starts.", timer);
+
+        rh = container_of(timer, server_release_heap_t, timer);
+
+        raw_spin_lock_irqsave(&rh->domain->release_lock, flags);
+        _TRACE_SUB("CB has the release_lock");
+
+        /* Remove from release queue */
+        list_del(&rh->list);
+
+        raw_spin_unlock_irqrestore(&rh->domain->release_lock, flags);
+        _TRACE_SUB("CB returned release_lock");
+
+        /* Call release callback */
+        rh->domain->servers_released(&rh->servers);
+        /* WARNING: rh can be referenced from other CPUs from now on. */
+
+        _TRACE_SUB("on_release_timer(0x%p) ends.", timer);
+
+        return HRTIMER_NORESTART;
+}
+
+/*
+ * Caller must hold release lock.
+ * Will return heap for given time. If no such heap exists prior to
+ * the invocation it will be created.
+ */
+static server_release_heap_t* get_release_heap(server_domain_t *rt,
+                                               server_t *server,
+                                               int use_server_heap)
+{
+        struct list_head *pos;
+        server_release_heap_t *heap = NULL;
+        server_release_heap_t *rh;
+        lt_t release_time = server->release;
+        unsigned int slot = time2slot(release_time);
+
+        _TRACE_SUB("searching for release time %llu", release_time);
+
+        /* Initialize pos for the case that the list is empty */
+        pos = rt->release_queue[slot].next;
+        list_for_each(pos, &rt->release_queue[slot]) {
+                rh = list_entry(pos, server_release_heap_t, list);
+                if (release_time == rh->release_time) {
+                        /* Perfect match -- this happens on hyperperiod
+                         * boundaries
+                         */
+                        heap = rh;
+                        break;
+                } else if (lt_before(release_time, rh->release_time)) {
+                        /* We need to insert a new node since rh is
+                         * already in the future
+                         */
+                        break;
+                }
+        }
+        if (!heap && use_server_heap) {
+                /* Use pre-allocated release heap */
+                rh = server->release_heap;
+                rh->domain = rt;
+                rh->release_time = release_time;
+
+                /* Add to release queue */
+                list_add(&rh->list, pos->prev);
+                heap = rh;
+        }
+        return heap;
+}
+
+/*
+ * Prepare a server's release_heap for use.
+ */
+static int reinit_release_heap(server_t *server)
 {
-        TRACE_SUB(server, "adding to release");
+        int rv = 0;
+        server_release_heap_t* rh;
+
+        /* Use pre-allocated release heap */
+        rh = server->release_heap;
+
+        /* WARNING: If the CPU still holds the release_lock at this point,
+         *          deadlock may occur!
+         */
+        rv = hrtimer_try_to_cancel(&rh->timer);
+
+        /* The timer callback is running, it is useless to add
+         * to the release heap now.
+         */
+        if (rv == -1) {
+                rv = 0;
+                goto out;
+        }
+
+        /* Under no cirumstances should the timer have been active
+         * but not running.
+         */
+        /* TODO: stop living dangerously */
+        //BUG_ON(rv == 1);
+        rv = 1;
+
+        /* initialize */
+        INIT_LIST_HEAD(&rh->servers);
+        atomic_set(&rh->info.state, HRTIMER_START_ON_INACTIVE);
+ out:
+        return rv;
 }
 
-void stop_server_releasing(server_domain_t *server_domain)
+/*
+ * Arm the release timer for the next set of servers.
+ */
+static int arm_release_timer(server_domain_t *domain)
 {
+        int rv = 1;
+        struct list_head list;
+        struct list_head *pos, *safe;
+        server_t *server;
+        server_release_heap_t *rh;
+
+        _TRACE_SUB("arm_release_timer() at %llu", litmus_clock());
+        list_replace_init(&domain->tobe_released, &list);
+
+        list_for_each_safe(pos, safe, &list) {
+                /* Pick server from work list */
+                server = list_entry(pos, server_t, release_list);
+                list_del(pos);
+
+                /* Put into release heap while holding release_lock */
+                raw_spin_lock(&domain->release_lock);
+                TRACE_SUB(server, "I have the release_lock");
+
+                rh = get_release_heap(domain, server, 0);
+                if (!rh) {
+                        /* Need to use our own, but drop lock first */
+                        raw_spin_unlock(&domain->release_lock);
+                        TRACE_SUB(server, "Dropped release_lock");
+
+                        rv = reinit_release_heap(server);
+
+                        /* Bail! We missed the release time */
+                        if (!rv) {
+                                TRACE_SUB(server, "missed release");
+                                rv = 0;
+                                goto out;
+                        }
+
+                        TRACE_SUB(server, "release_heap ready");
+
+                        raw_spin_lock(&domain->release_lock);
+                        TRACE_SUB(server, "Re-acquired release_lock");
 
+                        rh = get_release_heap(domain, server, 1);
+                }
+
+                list_add(&server->release_list, &rh->servers);
+                TRACE_SUB(server, "arm_release_timer(): added to release heap");
+
+                raw_spin_unlock(&domain->release_lock);
+                TRACE_SUB(server, "Returned the release_lock");
+
+                /* To avoid arming the timer multiple times, we only let the
+                 * owner do the arming (which is the "first" task to reference
+                 * this release_heap anyway).
+                 */
+                if (rh == server->release_heap) {
+                        TRACE_SUB(server, "arming timer 0x%p at %llu on P%d",
+                                  &rh->timer, rh->release_time,
+                                  domain->release_master);
+                        /* We cannot arm the timer using hrtimer_start()
+                         * as it may deadlock on rq->lock
+                         *
+                         * PINNED mode is ok on both local and remote CPU
+                         */
+                        if (domain->release_master == NO_CPU) {
+                                __hrtimer_start_range_ns(&rh->timer,
+                                                ns_to_ktime(rh->release_time),
+                                                0, HRTIMER_MODE_ABS_PINNED, 0);
+                        } else {
+                                hrtimer_start_on(domain->release_master,
+                                        &rh->info, &rh->timer,
+                                        ns_to_ktime(rh->release_time),
+                                        HRTIMER_MODE_ABS_PINNED);
+                        }
+                } else
+                        TRACE_SUB(server, "0x%p is not my timer", &rh->timer);
+        }
+ out:
+        return rv;
 }
 
+int add_server_release(server_t *server, server_domain_t *domain)
+{
+        TRACE_SUB(server, "adding to release at %llu", server->release);
+        list_add(&server->release_list, &domain->tobe_released);
+        return arm_release_timer(domain);
+}