A queue for reading in pages.

This is not tested and probably won't work.

Signed-off-by: Christopher Kenna <cjk@cs.unc.edu>

6 files changed, 447 insertions, 17 deletions

diff --git a/litmus/Makefile b/litmus/Makefile
index fab72b14eac8..d63a8eb51280 100644
--- a/litmus/Makefile
+++ b/litmus/Makefile
@@ -10,6 +10,7 @@ obj-y     = sched_plugin.o litmus.o \
             color.o \
             color_dev.o \
             color_proc.o \
+            color_queue.o \
             ctrldev.o \
             dgl.o \
             domain.o \
diff --git a/litmus/color.c b/litmus/color.c
index 96ccf3efd228..9888c3f1599c 100644
--- a/litmus/color.c
+++ b/litmus/color.c
@@ -15,6 +15,7 @@
 #include <litmus/color.h>
 #include <litmus/litmus.h> /* for in_list(...) */
 #include <litmus/clock.h>
+#include <litmus/color_queue.h>
 
 #define PAGES_PER_COLOR 1024
 
@@ -146,6 +147,9 @@ static int do_add_pages(void)
                 list_del(&page->lru);
                 __free_page(page);
         }
+
+        /* setup the color queue stuff */
+        ret = setup_flusher_array();
 out:
         return ret;
 }
diff --git a/litmus/color_dev.c b/litmus/color_dev.c
index df43c9f1e37d..278c8829c8fa 100644
--- a/litmus/color_dev.c
+++ b/litmus/color_dev.c
@@ -5,12 +5,14 @@
 #include <linux/spinlock.h>
 #include <linux/module.h>
 #include <linux/highmem.h>
+#include <linux/slab.h>
 #include <asm/io.h> /* page_to_phys on SPARC */
 
 /* #include <asm/glue-cache.h> */
 
 #include <litmus/litmus.h>
 #include <litmus/color.h>
+#include <litmus/color_queue.h>
 
 #define ALLOC_NAME      "litmus/color_alloc"
 #define CTRL_NAME       "litmus/color_ctrl"
@@ -185,6 +187,42 @@ out:
  * Allocation device
 ***********************************************************/
 
+static int create_color_page_info(int color, struct page *page)
+{
+        struct color_page_info *info;
+        void *vaddr;
+        int i, err = 0;
+
+        vaddr = page_address(page);
+        if (!vaddr) {
+                TRACE_CUR("Could not get apge address.\n");
+                err = -EINVAL;
+                goto out;
+        }
+
+        info = (struct color_page_info*) kmalloc(sizeof(*info), GFP_KERNEL);
+        if (!info) {
+                TRACE_CUR("Could not kmalloc\n");
+                err = -EINVAL;
+                goto out;
+        }
+
+        INIT_LIST_HEAD(&info->list);
+        info->color = color;
+        info->vaddr = vaddr;
+
+        for (i = 0; i < COLOR_REQUESTS_PER_PAGE; i++) {
+                struct color_queue_request *req = &info->requests[i];
+                INIT_LIST_HEAD(&req->list);
+                req->color_page_info = info;
+                req->request_type = COLOR_QUEUE_IDLE;
+        }
+
+        list_add_tail(&info->list, &tsk_rt(current)->color_page_info_list);
+out:
+        return err;
+}
+
 #define vma_nr_pages(vma) \
         ({unsigned long v = ((vma->vm_end - vma->vm_start) >> PAGE_SHIFT); v;})
 
@@ -213,6 +251,12 @@ static int do_map_colored_page_set(struct vm_area_struct *vma,
                 /* TODO For some reason this causes problems on ARM. */
                 /* clear_user_highpage(page, addr); */
 
+                err = create_color_page_info(color_no, page);
+                if (err) {
+                        /* TODO cleanup? */
+                        goto out;
+                }
+
                 TRACE_CUR("inserting page (pa: 0x%"FMT_PA") at vaddr: 0x%10lx  "
                                 "flags: 0x%10lx  prot: 0x%10lx\n",
                                 page_to_phys(page), addr,
@@ -304,12 +348,23 @@ out:
 
 static void litmus_color_alloc_vm_close(struct vm_area_struct *vma)
 {
+        struct color_page_info *cur, *tmp;
+
         TRACE_CUR("flags=0x%lx prot=0x%lx\n",
                         vma->vm_flags, pgprot_val(vma->vm_page_prot));
 
         TRACE_CUR("%p:%p vma:%p vma->vm_private_data:%p closed.\n",
                         (void*) vma->vm_start, (void*) vma->vm_end, vma,
                         vma->vm_private_data);
+
+        /* clean up the color_page_infos */
+        list_for_each_entry_safe(cur, tmp,
+                        &tsk_rt(current)->color_page_info_list,
+                        list)
+        {
+                kfree(cur);
+        }
+
         reclaim_pages(vma);
 }
 
diff --git a/litmus/color_queue.c b/litmus/color_queue.c
new file mode 100644
index 000000000000..a5a702332da8
--- /dev/null
+++ b/litmus/color_queue.c
@@ -0,0 +1,361 @@
+#include <linux/slab.h>
+#include <linux/mm.h>
+#include <linux/sched.h>
+
+#include <litmus/color_queue.h>
+#include <litmus/color.h>
+#include <litmus/lockdown.h>
+#include <litmus/color.h>
+#include <litmus/litmus.h>
+
+struct cpu_entry {
+        int phase;
+        /* what phase a CPU is in */
+
+        struct list_head enqueue;
+        /* used as a PENDING list of work to enqueue in the color queue */
+
+        int nr_work;
+        /* outstanding work elements this CPU has */
+
+        raw_spinlock_t lock;
+        /* guard nr_work when CPU is "inside" the queue (its work is added) */
+};
+
+DEFINE_PER_CPU(struct cpu_entry, cpu_entries);
+/* Per-CPU state. */
+
+extern u32 unlocked_way[];
+/* Index i means way i is unlocked. Comes from litmus/lockdown.c */
+
+struct color_queue color_queue;
+/* The queue. */
+
+static u32 lockdown_value;
+/* Cached lockdown value so that we don't need to look it up each time.
+ * Should agree with color_queue.way.
+ */
+
+static u32 lockdown_value_idle = UNLOCK_ALL;
+/* Lockdown state when the queue is inactive. Lets us lock down some ways
+ * if we choose to.
+ */
+
+static void ***flusher_pages;
+/* One page per [way, color] pair used for flushing. */
+
+/*
+ * Add work to the cpu_entry's PENDING list of work for the color queue.
+ */
+static void cpu_add_work(struct color_queue_request *req)
+{
+        struct cpu_entry *entry = &__get_cpu_var(cpu_entries);
+        struct list_head *new = &req->list;
+        list_add_tail(new, &entry->enqueue);
+        entry->nr_work++;
+}
+
+/*
+ * Add a pending read in of a page. Does the chunking into work units.
+ *
+ * You should already set @way (in @color_page_info) by the time you
+ * call this!
+ *
+ * @vaddr_start changes depending upon if this is a read-in or a "flush".
+ */
+static void color_page_info_add_work(struct color_page_info *info,
+                void *vaddr_start)
+{
+        int i;
+
+        for (i = 0; i < COLOR_REQUESTS_PER_PAGE; i++) {
+                struct color_queue_request *req = &info->requests[i];
+                void *work_vaddr = vaddr_start + i * COLOR_QUEUE_REQ_SIZE;
+                
+                WARN(req->request_type != COLOR_QUEUE_IDLE,
+                                "request was not idle!\n");
+
+                req->request_type = COLOR_QUEUE_READ;
+                req->cpu = smp_processor_id();
+                req->request_data.read.vaddr = work_vaddr;
+                cpu_add_work(req);
+        }
+}
+
+static void color_queue_submit_work(void);
+
+/*
+ * Assumes this is called on the CPU that @ts ran on and that this CPU that is
+ * requesting the work. Do not try and schedule work for someone else!
+ *
+ * Also assumes that @way set for each color_page_info before calling!
+ */
+void color_queue_enqueue_read(struct task_struct *ts)
+{
+        struct color_page_info *cur_info;
+
+        list_for_each_entry(cur_info,
+                        &tsk_rt(ts)->color_page_info_list,
+                        list)
+        {
+                void *vaddr_start = cur_info->vaddr;
+                /* since this is a read, uses the page's address */
+
+                color_page_info_add_work(cur_info, vaddr_start);
+        }
+
+        color_queue_submit_work();
+}
+
+/*
+ * Assumes this is called on the CPU that @ts ran on and that this CPU that is
+ * requesting the work. Do not try and schedule work for someone else!
+ *
+ * Also assumes that @way is still set to the way this page was read into to
+ * find the proper address to flush.
+ */
+void color_queue_enqueue_flush(struct task_struct *ts)
+{
+        struct color_page_info *cur_info;
+
+        list_for_each_entry(cur_info,
+                        &tsk_rt(ts)->color_page_info_list,
+                        list)
+        {
+                void *vaddr_start;
+                vaddr_start = flusher_pages[cur_info->way][cur_info->color];
+                /* now we use the corresponding flusher page */
+                color_page_info_add_work(cur_info, vaddr_start);
+        }
+
+        color_queue_submit_work();
+}
+
+static void do_work_read(struct color_queue_request *request)
+{
+        void *vaddr = request->request_data.read.vaddr;
+
+        /* Don't know which CPU is first to do work in a given phase, so have
+         * all CPUs set the lockdown register to the same value. Also, the
+         * "unlock_val" is also the lock value, since we don't know if other
+         * CPUs are still reading. We could take the unlock out of the read_in
+         * function, but it's one store operation and probably takes a few
+         * nanoseconds...
+         */
+        color_read_in_mem(lockdown_value, lockdown_value,
+                        vaddr, vaddr + COLOR_QUEUE_REQ_SIZE);
+}
+
+/*
+ * This just does a unit of work, ... son.
+ */
+static void do_work_son(struct color_queue_request *request)
+{
+        struct cpu_entry *entry;
+
+        switch (request->request_type) {
+                case COLOR_QUEUE_IDLE:
+                        WARN(1, "Idle work in the queue!\n");
+                        break;
+                case COLOR_QUEUE_READ:
+                        do_work_read(request);
+                        break;
+        }
+
+        /* Tell the (possibly remote) CPU that we're a bro and helped out. */
+        entry = &per_cpu(cpu_entries, request->cpu);
+        raw_spin_lock(&entry->lock);
+        entry->nr_work--;
+        raw_spin_unlock(&entry->lock);
+
+        /* work is done, set it idle */
+        request->request_type = COLOR_QUEUE_IDLE;
+}
+
+static void wait_next_phase(void)
+{
+        struct cpu_entry *entry = &__get_cpu_var(cpu_entries);
+        struct color_queue_request *request;
+
+        for (;;) {
+                raw_spin_lock(&color_queue.lock);
+                if (entry->phase < color_queue.phase) {
+                        /* Move on to the next phase (or later). Another CPU already
+                         * set up the lockdown value and updated the queue phase.
+                         */
+                        entry->phase = color_queue.phase;
+                        raw_spin_unlock(&color_queue.lock);
+                        return;
+                }
+
+                if (color_queue.nr_cpus == color_queue.at_barrier) {
+                        int next_way;
+
+                        /* Ready to start the next phase. */
+                        if (unlikely(list_empty(&color_queue.queue))) {
+                                /* This should not happen! Will loop forever? */
+                                WARN(1, "color queue list was empty!\n");
+                                raw_spin_unlock(&color_queue.lock);
+                                continue;
+                        }
+                        request = list_first_entry(&color_queue.queue,
+                                        struct color_queue_request, list);
+                        next_way = request->color_page_info->way;
+                        lockdown_value = unlocked_way[next_way];
+                        color_queue.way = next_way;
+                        color_queue.at_barrier = 0;
+                        color_queue.phase++;
+                        raw_spin_unlock(&color_queue.lock);
+                        return;
+                } else {
+                        /* Wait for work from the last phase to complete. */
+                        raw_spin_unlock(&color_queue.lock);
+                        cpu_relax();
+                }
+        }
+}
+
+static void color_queue_loop(void)
+{
+        struct cpu_entry *entry = &__get_cpu_var(cpu_entries);
+        struct color_queue_request *request;
+        int nr_work;
+
+        for (;;) {
+                raw_spin_lock(&entry->lock);
+                nr_work = entry->nr_work;
+                raw_spin_unlock(&entry->lock);
+
+                if (0 == nr_work) {
+                        /* All the work is done for this CPU. We can leave. */
+                        raw_spin_lock(&color_queue.lock);
+                        color_queue.nr_cpus--;
+                        if (0 == color_queue.nr_cpus) {
+                                /* Queue is going idle. Restore lockdown state. */
+                                set_lockdown(lockdown_value_idle);
+                        }
+                        raw_spin_unlock(&color_queue.lock);
+                        return;
+                }
+
+                /* Our work is not done, so continue processing more work. */
+
+                raw_spin_lock(&color_queue.lock);
+                if (unlikely(list_empty(&color_queue.queue))) {
+                        /* can this happen? */
+                        WARN(1, "color queue list was empty...\n");
+                        raw_spin_unlock(&color_queue.lock);
+                        continue;
+                }
+                request = list_first_entry(&color_queue.queue,
+                                struct color_queue_request, list);
+                if (color_queue.way == request->color_page_info->way) {
+                        /* we're going to do this work */
+                        list_del(&request->list);
+                        raw_spin_unlock(&color_queue.lock);
+                        do_work_son(request);
+                } else {
+                        /* we need to wait for the next phase */
+                        color_queue.at_barrier++;
+                        raw_spin_unlock(&color_queue.lock);
+                        wait_next_phase();
+                }
+        }
+}
+
+/*
+ * Actually enqueues the work on the color queue and enters the work loop.
+ */
+static void color_queue_submit_work(void)
+{
+        struct cpu_entry *entry = &__get_cpu_var(cpu_entries);
+
+        raw_spin_lock(&color_queue.lock);
+        entry->phase = color_queue.phase;
+        color_queue.nr_cpus++;
+        list_splice_tail_init(&entry->enqueue, &color_queue.queue);
+        raw_spin_unlock(&color_queue.lock);
+        color_queue_loop();
+}
+
+/* called when user does add_pages proc handler */
+int setup_flusher_array(void)
+{
+        int color, way, ret = 0;
+        struct page *page;
+
+        if (0 == color_cache_info.ways || 0 == color_cache_info.nr_colors) {
+                WARN(1, "Cache information not initialized!\n");
+                ret = -EINVAL;
+                goto out;
+        }
+
+        flusher_pages = (void***) kmalloc(color_cache_info.ways
+                        * sizeof(*flusher_pages), GFP_KERNEL);
+        if (!flusher_pages) {
+                printk(KERN_WARNING "No memory for flusher array!\n");
+                ret = -EINVAL;
+                goto out;
+        }
+
+        for (way = 0; way < color_cache_info.ways; way++) {
+                void **flusher_color_arr;
+                flusher_color_arr = (void**) kmalloc(sizeof(**flusher_pages)
+                                * color_cache_info.nr_colors, GFP_KERNEL);
+                if (!flusher_color_arr) {
+                        printk(KERN_WARNING "No memory for flusher array!\n");
+                        ret = -ENOMEM;
+                        goto out_free;
+                }
+
+                flusher_pages[way] = flusher_color_arr;
+
+                for (color = 0; color < color_cache_info.nr_colors; color++) {
+                        page = get_colored_page(color);
+                        if (!page) {
+                                printk(KERN_WARNING "no more colored pages\n");
+                                ret = -EINVAL;
+                                goto out_free;
+                        }
+                        flusher_pages[way][color] = page_address(page);
+                        if (!flusher_pages[way][color]) {
+                                printk(KERN_WARNING "bad page address\n");
+                                ret = -EINVAL;
+                                goto out_free;
+                        }
+                }
+        }
+out:
+        return ret;
+out_free:
+        for (way = 0; way < color_cache_info.ways; way++) {
+                for (color = 0; color < color_cache_info.nr_colors; color++) {
+                        /* not bothering to try and give back colored pages */
+                }
+                kfree(flusher_pages[way]);
+        }
+        kfree(flusher_pages);
+        return ret;
+}
+
+static int __init init_color_queue(void)
+{
+        struct cpu_entry *cpu_entry;
+        int cpu;
+
+        BUILD_BUG_ON((PAGE_SIZE % COLOR_QUEUE_REQ_SIZE) != 0);
+
+        for_each_online_cpu(cpu) {      
+                cpu_entry = &per_cpu(cpu_entries, cpu);
+                INIT_LIST_HEAD(&cpu_entry->enqueue);
+                cpu_entry->nr_work = 0;
+                raw_spin_lock_init(&cpu_entry->lock);
+        }
+
+        raw_spin_lock_init(&color_queue.lock);
+        INIT_LIST_HEAD(&color_queue.queue);
+
+        return 0;
+}
+
+module_init(init_color_queue);
diff --git a/litmus/litmus.c b/litmus/litmus.c
index ba6397a461d5..74e798992fa0 100644
--- a/litmus/litmus.c
+++ b/litmus/litmus.c
@@ -466,6 +466,8 @@ long litmus_admit_task(struct task_struct* tsk)
         tsk_rt(tsk)->heap_node = bheap_node_alloc(GFP_ATOMIC);
         tsk_rt(tsk)->rel_heap = release_heap_alloc(GFP_ATOMIC);
 
+        INIT_LIST_HEAD(&tsk_rt(tsk)->color_page_info_list);
+
         if (!tsk_rt(tsk)->heap_node || !tsk_rt(tsk)->rel_heap) {
                 printk(KERN_WARNING "litmus: no more heap node memory!?\n");
 
diff --git a/litmus/lockdown.c b/litmus/lockdown.c
index ac7b9a24a512..f1da7b4145d5 100644
--- a/litmus/lockdown.c
+++ b/litmus/lockdown.c
@@ -17,6 +17,7 @@
 
 #include <litmus/color.h>
 #include <litmus/debug_trace.h>
+#include <litmus/lockdown.h>
 
 static void __iomem *cache_base;
 static void __iomem *lockreg_d;
@@ -38,7 +39,11 @@ struct mutex lockdown_proc;
                         __cpu * L2X0_LOCKDOWN_STRIDE; __v; })
 
 #define MAX_NR_WAYS     16
-#define UNLOCK_ALL      0x00000000 /* allocation in any way */
+
+void set_lockdown(u32 lockdown_state)
+{
+        writel_relaxed(lockdown_state, lockreg_d);
+}
 
 /*
  * Prefetch by reading the first word of each cache line in a page.
@@ -51,10 +56,7 @@ struct mutex lockdown_proc;
  *
  * Assumes: addr < end_addr AND addr != end_addr
  */
-static u32 read_in_page(u32 lock_val,
-                  u32 unlock_val,
-                  void *start,
-                  void *end)
+u32 color_read_in_mem(u32 lock_val, u32 unlock_val, void *start, void *end)
 {
         unsigned long flags;
         u32 v = 0;
@@ -90,12 +92,12 @@ void color_flush_page(void *vaddr)
 }
 
 /*
- * unlocked[i] : allocation can occur in way i
+ * unlocked_way[i] : allocation can occur in way i
  *
  * 0 = allocation can occur in the corresponding way
  * 1 = allocation cannot occur in the corresponding way
  */
-static u32 unlocked[MAX_NR_WAYS]  = {
+u32 unlocked_way[MAX_NR_WAYS]  = {
         0xFFFFFFFE, /* way 0 unlocked */
         0xFFFFFFFD,
         0xFFFFFFFB,
@@ -334,7 +336,7 @@ static void thrash(void *vaddr)
         v7_flush_kern_dcache_area(vaddr, CTRL_PAGES * PAGE_SIZE);
 
         /* thrash. don't lock down, we want to fill the dcache with these */
-        read_in_page(UNLOCK_ALL, UNLOCK_ALL, thrash_pages,
+        color_read_in_mem(UNLOCK_ALL, UNLOCK_ALL, thrash_pages,
                         thrash_pages + THRASH_PAGES * PAGE_SIZE);
 }
 
@@ -386,7 +388,7 @@ static int test_read_in(void)
                 preempt_disable();
                 local_irq_save(flags);
                 start = litmus_get_cycles();
-                read_in_page(unlocked[WAY_OFFSET], UNLOCK_ALL,
+                color_read_in_mem(unlocked_way[WAY_OFFSET], UNLOCK_ALL,
                                 remapped, remapped + i);
                 stop = litmus_get_cycles();
                 local_irq_restore(flags);
@@ -421,7 +423,7 @@ static int test_read_in(void)
                         vaddr_start = remapped + PAGE_SIZE * read_start;
                         vaddr_end   = remapped + PAGE_SIZE * read_end;
 
-                        read_in_page(unlocked[way], UNLOCK_ALL,
+                        color_read_in_mem(unlocked_way[way], UNLOCK_ALL,
                                         vaddr_start, vaddr_end);
 
                         READ_TRACE("i:%d  j:%d  read_start:%d  read_end:%d  way:%d\n",
@@ -500,9 +502,9 @@ static void test_lockdown(void *ignore)
         for (i = 0; i < MAX_NR_WAYS; i++) {
                 unsigned long expected = 0xFFFFFFFF;
                 clear_bit(i, &expected);
-                if (expected != unlocked[i]) {
+                if (expected != unlocked_way[i]) {
                         WARN(1, "Unlock %2d: expected 0x%8x but got 0x%8x\n",
-                                        i, ((u32)expected), unlocked[i]);
+                                        i, ((u32)expected), unlocked_way[i]);
                 }
         }
 
@@ -538,12 +540,12 @@ static int perf_test(void) {
         time = update_timeval(before, after);
         printk("Average for flushes without re-reading: %ld\n", time / TRIALS);
 
-        read_in_page(unlocked[0], UNLOCK_ALL, vaddr, vaddr + PAGE_SIZE);
+        color_read_in_mem(unlocked_way[0], UNLOCK_ALL, vaddr, vaddr + PAGE_SIZE);
         barrier();
         getnstimeofday(&before);
         barrier();
         for (i = 0; i < TRIALS; i++) {
-                read_in_page(unlocked[0], UNLOCK_ALL, vaddr, vaddr + PAGE_SIZE);
+                color_read_in_mem(unlocked_way[0], UNLOCK_ALL, vaddr, vaddr + PAGE_SIZE);
         }
         barrier();
         getnstimeofday(&after);
@@ -553,7 +555,7 @@ static int perf_test(void) {
         getnstimeofday(&before);
         barrier();
         for (i = 0; i < TRIALS; i++) {
-                read_in_page(unlocked[0], UNLOCK_ALL, vaddr, vaddr + PAGE_SIZE);
+                color_read_in_mem(unlocked_way[0], UNLOCK_ALL, vaddr, vaddr + PAGE_SIZE);
                 color_flush_page(vaddr);
         }
         barrier();
@@ -574,8 +576,10 @@ int litmus_test_prefetch_proc_handler(struct ctl_table *table, int write,
         u32 *data;
         int i;
 
-        if (!write)
+        if (!write) {
+                *lenp = 0;
                 return 0;
+        }
 
         page = alloc_page(__GFP_MOVABLE);
         if (!page) {
@@ -591,7 +595,7 @@ int litmus_test_prefetch_proc_handler(struct ctl_table *table, int write,
         for (i = 0; i < PAGE_SIZE / sizeof(u32); i++)
                 data[i] = i;
 
-        read_in_page(UNLOCK_ALL, LOCKREG_TEST_VAL, vaddr, vaddr + PAGE_SIZE);
+        color_read_in_mem(UNLOCK_ALL, LOCKREG_TEST_VAL, vaddr, vaddr + PAGE_SIZE);
 
         if (LOCKREG_TEST_VAL != readl_relaxed(lockreg_d)) {
                 printk("%s: Expected lockreg value 0x%8x but got 0x%8x!\n",
@@ -632,5 +636,8 @@ void litmus_setup_lockdown(void __iomem *base, u32 id)
         mutex_init(&l2x0_prefetch_mutex);
         mutex_init(&lockdown_proc);
 
+        WARN(MAX_NR_WAYS < color_cache_info.ways,
+                        "Statically defined way maximum too small.\n");
+
         test_lockdown(NULL);
 }