sched_color: group locks guarantee timestamp order, have better state checks

5 files changed, 102 insertions, 36 deletions

diff --git a/include/litmus/color.h b/include/litmus/color.h
index fb109c4f5b14..8f66bf50d5b7 100644
--- a/include/litmus/color.h
+++ b/include/litmus/color.h
@@ -1,6 +1,9 @@
 #ifndef LITMUS_COLOR_H
 #define LITMUS_COLOR_H
 
+#define NUM_COLORS 10
+#define NUM_WAYS   5
+
 int color_server_params(int cpu, unsigned long *wcet, unsigned long *period);
 
 #endif
diff --git a/include/litmus/dgl.h b/include/litmus/dgl.h
index 989f6c7d5e8e..2bf61d4a7547 100644
--- a/include/litmus/dgl.h
+++ b/include/litmus/dgl.h
@@ -1,12 +1,15 @@
 #ifndef __DGL_H_
 #define __DGL_H_
 
+#include <litmus/color.h>
 #include <linux/list.h>
 
-#define NUM_REPLICAS  4
-#define NUM_RESOURCES 4
+#define WP(num, word) (num / word + (num % word != 0))
+
+#define NUM_REPLICAS  NUM_WAYS
+#define NUM_RESOURCES NUM_COLORS
 #define MASK_SIZE     (sizeof(unsigned long) * 8)
-#define MASK_WORDS    (NUM_RESOURCES/MASK_SIZE + (NUM_RESOURCES%MASK_SIZE != 0))
+#define MASK_WORDS    WP(NUM_RESOURCES, MASK_SIZE)
 
 /*
  * A request for @replica amount of a single resource.
@@ -24,6 +27,7 @@ struct dgl_group_req {
         unsigned long           requested[MASK_WORDS];
         unsigned long           waiting[MASK_WORDS];
         struct dgl_req          requests[NUM_RESOURCES];
+        unsigned long long      ts;
 };
 
 /*
@@ -40,6 +44,10 @@ struct dgl_resource {
 struct dgl {
         struct dgl_resource     resources[NUM_RESOURCES];
         struct dgl_group_req*   acquired[NR_CPUS];
+
+        char                    requests;
+        char                    running;
+        unsigned long long      ts;
 };
 
 void dgl_init(struct dgl *dgl);
diff --git a/include/litmus/rt_param.h b/include/litmus/rt_param.h
index e56aab006cc1..2eec39c7678c 100644
--- a/include/litmus/rt_param.h
+++ b/include/litmus/rt_param.h
@@ -5,7 +5,7 @@
 #ifndef _LINUX_RT_PARAM_H_
 #define _LINUX_RT_PARAM_H_
 
-#include <litmus/dgl.h>
+#include <litmus/color.h>
 
 /* Litmus time type. */
 typedef unsigned long long lt_t;
@@ -68,7 +68,7 @@ struct control_page {
         /* locking overhead tracing: time stamp prior to system call */
         uint64_t ts_syscall_start; /* Feather-Trace cycles */
 
-        int requests[NUM_RESOURCES];
+        int requests[NUM_COLORS];
 };
 
 /* don't export internal data structures to user space (liblitmus) */
diff --git a/litmus/dgl.c b/litmus/dgl.c
index 9749597aa769..e09d57cc2672 100644
--- a/litmus/dgl.c
+++ b/litmus/dgl.c
@@ -27,27 +27,48 @@ static inline void mask_idx(int resource, int *word, int *bit)
         *bit  = resource % MASK_SIZE;
 }
 
+
+static void print_waiting(struct dgl *dgl, struct dgl_resource *resource)
+{
+        struct dgl_req *pos;
+        struct dgl_group_req *greq;
+        int rid = resource_id(dgl, resource);
+        unsigned long long last = 0;
+
+        TRACE("List for rid %d\n", resource_id(dgl, resource));
+        list_for_each_entry(pos, &resource->waiting, list) {
+                greq = req_group(pos, rid);
+                TRACE("  0x%p with timestamp %llu\n", greq, greq->ts);
+                BUG_ON(greq->ts < last);
+                last = greq->ts;
+        }
+}
+
 void dgl_init(struct dgl *dgl)
 {
         int i;
         struct dgl_resource *resource;
 
-        for (i = 0; i < NR_CPUS; i++)
+        for (i = 0; i < NR_CPUS; ++i)
                 dgl->acquired[i] = NULL;
 
-        for (i = 0; i < NUM_RESOURCES; i++) {
+        for (i = 0; i < NUM_RESOURCES; ++i) {
                 resource = &dgl->resources[i];
 
                 INIT_LIST_HEAD(&resource->waiting);
                 resource->free_replicas = NUM_REPLICAS;
         }
+
+        dgl->requests = 0;
+        dgl->running  = 0;
+        dgl->ts = 0;
 }
 
 void dgl_group_req_init(struct dgl_group_req *greq)
 {
         int i;
         greq->cpu = NO_CPU;
-        for (i = 0; i < MASK_WORDS; i++) {
+        for (i = 0; i < MASK_WORDS; ++i) {
                 greq->requested[i] = 0;
                 greq->waiting[i]   = 0;
         }
@@ -64,9 +85,6 @@ void set_req(struct dgl_group_req *greq, int resource, int replicas)
         BUG_ON(replicas > NUM_REPLICAS);
 
         mask_idx(resource, &word, &bit);
-        TRACE("0x%p will request resource %d, word %d, bit %d\n",
-              greq, resource, word, bit);
-
         __set_bit(bit, &greq->requested[word]);
 
         req = &greq->requests[resource];
@@ -82,25 +100,31 @@ void set_req(struct dgl_group_req *greq, int resource, int replicas)
 static unsigned long try_acquire(struct dgl *dgl, struct dgl_resource *resource,
                                  struct dgl_req *req)
 {
-        int word, bit, rid;
+        int word, bit, rid, head, empty, room;
         unsigned long waiting;
         struct dgl_group_req *greq;
 
-        if (resource->free_replicas < req->replicas) {
-                TRACE("0x%p cannot acquire %d replicas, only %d free\n",
-                      greq, req->replicas, resource->free_replicas);
+        rid  = resource_id(dgl, resource);
+        greq = req_group(req, rid);
+
+        head  = resource->waiting.next == &req->list;
+        empty = list_empty(&resource->waiting);
+        room  = resource->free_replicas >= req->replicas;
+
+        if (! (room && (head || empty)) ) {
+                TRACE("0x%p cannot acquire %d replicas, %d free\n",
+                      greq, req->replicas, resource->free_replicas,
+                      room, head, empty);
                 return 0;
         }
 
         resource->free_replicas -= req->replicas;
+        BUG_ON(resource->free_replicas > NUM_REPLICAS);
 
-        rid  = resource_id(dgl, resource);
-        greq = req_group(req, rid);
-        mask_idx(rid, &word, &bit);
-
-        TRACE("0x%p acquired rid %d, word %d, bit %d\n",
-              greq, rid, word, bit);
+        TRACE("0x%p acquired %d replicas of rid %d\n",
+              greq, req->replicas, rid);
 
+        mask_idx(rid, &word, &bit);
         clear_bit(bit, &greq->waiting[word]);
 
         waiting = 0;
@@ -115,6 +139,7 @@ static unsigned long try_acquire(struct dgl *dgl, struct dgl_resource *resource,
                 BUG_ON(dgl->acquired[greq->cpu]);
                 dgl->acquired[greq->cpu] = greq;
                 litmus_reschedule(greq->cpu);
+                dgl->running++;
         }
 
         return 1;
@@ -130,10 +155,13 @@ void add_group_req(struct dgl *dgl, struct dgl_group_req *greq, int cpu)
         struct dgl_resource *resource;
 
         greq->cpu = cpu;
+        greq->ts = dgl->ts++;
 
         TRACE("0x%p group request added for CPU %d\n", greq, cpu);
         BUG_ON(dgl->acquired[cpu] == greq);
 
+        ++dgl->requests;
+
         for_each_resource(greq->requested, w, b, i) {
                 __set_bit(b, &greq->waiting[w]);
         }
@@ -146,10 +174,19 @@ void add_group_req(struct dgl *dgl, struct dgl_group_req *greq, int cpu)
                 all_succ &= succ;
 
                 if (!succ) {
-                        TRACE("0x%p waiting on resource %d\n", greq, i);
+                        TRACE("0x%p waiting on rid %d\n", greq, i);
                         list_add_tail(&req->list, &resource->waiting);
                 }
         }
+
+        /* Grant empty requests */
+        if (all_succ && !dgl->acquired[cpu]) {
+                TRACE("0x%p empty group request acquired cpu %d\n", greq, cpu);
+                dgl->acquired[cpu] = greq;
+                ++dgl->running;
+        }
+
+        BUG_ON(dgl->requests && !dgl->running);
 }
 
 /**
@@ -165,9 +202,12 @@ void remove_group_req(struct dgl *dgl, struct dgl_group_req *greq)
 
         TRACE("0x%p removing group request for CPU %d\n", greq, greq->cpu);
 
+        --dgl->requests;
+
         if (dgl->acquired[greq->cpu] == greq) {
                 TRACE("0x%p no longer acquired on CPU %d\n", greq, greq->cpu);
                 dgl->acquired[greq->cpu] = NULL;
+                --dgl->running;
         }
 
         for_each_resource(greq->requested, w, b, i) {
@@ -178,20 +218,31 @@ void remove_group_req(struct dgl *dgl, struct dgl_group_req *greq)
                         /* Waiting on resource */
                         clear_bit(b, &greq->waiting[w]);
                         list_del_init(&req->list);
-                        TRACE("0x%p quit waiting for resource %d\n", greq, i);
+                        TRACE("Quitting 0x%p from rid %d\n",
+                              req, i);
                 } else {
                         /* Have resource */
                         resource->free_replicas += req->replicas;
-                        TRACE("0x%p releasing resource %d\n", greq, i);
+                        BUG_ON(resource->free_replicas > NUM_REPLICAS);
+                        TRACE("0x%p releasing %d of %d replicas, rid %d\n",
+                              greq, req->replicas, resource->free_replicas, i);
 
                         if (!list_empty(&resource->waiting)) {
                                 /* Give it to the next guy */
                                 next = list_first_entry(&resource->waiting,
                                                         struct dgl_req,
                                                         list);
-                                if (try_acquire(dgl, resource, next))
+
+                                BUG_ON(req_group(next, i)->ts < greq->ts);
+
+                                if (try_acquire(dgl, resource, next)) {
                                         list_del_init(&next->list);
+                                        print_waiting(dgl, resource);
+
+                                }
                         }
                 }
         }
+
+        BUG_ON(dgl->requests && !dgl->running);
 }
diff --git a/litmus/sched_color.c b/litmus/sched_color.c
index 61a28da1ef6c..d5408c645644 100644
--- a/litmus/sched_color.c
+++ b/litmus/sched_color.c
@@ -459,7 +459,8 @@ static struct task_struct* color_schedule(struct task_struct *prev)
                 } else {
                         TRACE_TASK(next, "Does not have lock, 0x%p does\n",
                                    group_lock.acquired[entry->server.cpu]);
-                        sched_trace_task_block(next, 1);
+                        if (next != prev)
+                                sched_trace_task_block(next, 1);
                         next = NULL;
                         server_running = 0;
                 }
@@ -509,20 +510,16 @@ static void color_task_new(struct task_struct *t, int on_rq, int running)
         req = kmalloc(sizeof(*req), GFP_ATOMIC);
         dgl_group_req_init(req);
         for (i = 0; i < NUM_RESOURCES; i++) {
-                /* /\* Testing *\/ */
-                /* set_req(req, i, 2); */
-                /* /\* Real *\/ */
-                /* replicas = get_control_page(t)->requests[i]; */
-                /* if (replicas) { */
-                /*      set_req(req, i, replicas); */
-                /* } */
+                replicas = get_control_page(t)->requests[i];
+                if (replicas)
+                        set_req(req, i, replicas);
         }
         tsk_rt(t)->req = req;
 
         /* Join system */
         raw_spin_lock(lock);
         if (running) {
-                TRACE_TASK(t, "Already scheduled on %d\n", entry->cpu);
+                TRACE_TASK(t, "Already scheduled on %d\n", entry->server.cpu);
                 BUG_ON(entry->scheduled);
                 entry->scheduled = t;
                 tsk_rt(t)->scheduled_on = entry->server.cpu;
@@ -630,7 +627,12 @@ static void color_task_exit(struct task_struct * t)
  */
 static long color_admit_task(struct task_struct* t)
 {
-        return is_be(t) || task_cpu(t) == get_partition(t) ? 0 : -EINVAL;
+        int ret = is_be(t) || task_cpu(t) == get_partition(t) ? 0 : -EINVAL;
+        if (!ret) {
+                printk(KERN_WARNING "Task failed to migrate to CPU %d\n",
+                       get_partition(t));
+        }
+        return ret;
 }
 
 /*
@@ -668,10 +670,12 @@ static long color_activate_plugin(void)
 
                 /* Make runnable */
                 release_at(server_task, now);
-                requeue(&entry->edf_domain, server_task);
                 entry->fifo_server.start_time = 0;
                 entry->scheduled = NULL;
 
+                if (!is_queued(server_task))
+                        requeue(&entry->edf_domain, server_task);
+
                 TRACE_TASK(server_task, "Created server with wcet: %llu, "
                            "period: %llu\n", tp.exec_cost, tp.period);