Adding allocation of colors for processes
authorKevin Klues <klueska@cs.berkeley.edu>
Fri, 23 Oct 2009 06:20:12 +0000 (08:20 +0200)
committerKevin Klues <klueska@cs.berkeley.edu>
Fri, 23 Oct 2009 06:20:12 +0000 (08:20 +0200)
Lots of files changed, mostly for getting things to work both on x86 and sparc.  Fixed a bug in sparc as well.... l2 page table freed too many times.

21 files changed:
apps [new symlink]
kern/arch/i386/atomic.h
kern/arch/i386/bitmask.h
kern/arch/i386/colored_caches.c
kern/arch/i386/ne2k.c
kern/arch/i386/page_alloc.c
kern/arch/i386/pmap.c
kern/arch/sparc/bitmask.h
kern/arch/sparc/colored_caches.c
kern/arch/sparc/env.c
kern/arch/sparc/page_alloc.c
kern/include/colored_caches.h
kern/include/env.h
kern/include/page_alloc.h
kern/include/testing.h
kern/src/colored_caches.c
kern/src/env.c
kern/src/init.c
kern/src/page_alloc.c
kern/src/syscall.c
kern/src/testing.c

diff --git a/apps b/apps
new file mode 120000 (symlink)
index 0000000..4f426ac
--- /dev/null
+++ b/apps
@@ -0,0 +1 @@
+obj/user/apps/parlib
\ No newline at end of file
index ce675e9..9901b93 100644 (file)
@@ -19,6 +19,7 @@ static inline void atomic_set(atomic_t *number, int32_t val);
 static inline void atomic_inc(atomic_t *number);
 static inline void atomic_dec(atomic_t *number);
 static inline void atomic_andb(volatile uint8_t RACY* number, uint8_t mask);
+static inline void atomic_orb(volatile uint8_t RACY* number, uint8_t mask);
 static inline void spin_lock(volatile uint32_t SRACY*COUNT(1) lock);
 static inline void spin_unlock(volatile uint32_t SRACY* lock);
 
@@ -56,6 +57,10 @@ static inline void atomic_andb(volatile uint8_t RACY*number, uint8_t mask)
        asm volatile("lock andb %1,%0" : "=m"(*number) : "r"(mask) : "cc");
 }
 
+static inline void atomic_orb(volatile uint8_t RACY*number, uint8_t mask)
+{
+       asm volatile("lock orb %1,%0" : "=m"(*number) : "r"(mask) : "cc");
+}
 
 static inline void spin_lock(volatile uint32_t* lock)
 {
index ffe4855..a775d9d 100644 (file)
 #include <atomic.h>
 #include <stdio.h>
 
-#define BYTES_FOR_BITMASK(size) (((size) - 1) / 8 + 1)
-#define BYTES_FOR_BITMASK_WITH_CHECK(size) ((size) ? ((size) - (1)) / (8) + (1) : (0))
-#define DECL_BITMASK(name, size) uint8_t (name)[BYTES_FOR_BITMASK((size))]
+#define DECL_BITMASK(name, size) \
+       uint8_t (name)[BYTES_FOR_BITMASK((size))]
 
-#define GET_BITMASK_BIT(name, bit) (((name)[(bit)/8] & (1 << ((bit) % 8))) ? 1 : 0)
-#define SET_BITMASK_BIT(name, bit) ((name)[(bit)/8] |= (1 << ((bit) % 8)))
-#define CLR_BITMASK_BIT(name, bit) ((name)[(bit)/8] &= ~(1 << ((bit) % 8)))
-#define SET_BITMASK_BIT_ATOMIC(name, bit) (atomic_orb(&(name)[(bit)/8], (1 << ((bit) % 8))))
-#define CLR_BITMASK_BIT_ATOMIC(name, bit) (atomic_andb(&(name)[(bit)/8], ~(1 << ((bit) % 8))))
+#define BYTES_FOR_BITMASK(size) \
+       (((size) - 1) / 8 + 1)
+
+#define BYTES_FOR_BITMASK_WITH_CHECK(size) \
+       ((size) ? ((size) - (1)) / (8) + (1) : (0))
+
+static bool GET_BITMASK_BIT(uint8_t* name, size_t bit) 
+{
+       return (((name)[(bit)/8] & (1 << ((bit) % 8))) ? 1 : 0);
+}
+
+#define SET_BITMASK_BIT(name, bit) \
+       ((name)[(bit)/8] |= (1 << ((bit) % 8)));
+/*
+static void SET_BITMASK_BIT(uint8_t* name, size_t bit)
+{
+       ((name)[(bit)/8] |= (1 << ((bit) % 8)));
+}
+*/
+
+#define CLR_BITMASK_BIT(name, bit) \
+       ((name)[(bit)/8] &= ~(1 << ((bit) % 8)));
+/*
+static void CLR_BITMASK_BIT(uint8_t* name, size_t bit) 
+{
+       ((name)[(bit)/8] &= ~(1 << ((bit) % 8)));
+}
+*/
+
+static void SET_BITMASK_BIT_ATOMIC(uint8_t* name, size_t bit) 
+{
+       (atomic_orb(&(name)[(bit)/8], (1 << ((bit) % 8))));
+}
+
+#define CLR_BITMASK_BIT_ATOMIC(name, bit) \
+       (atomic_andb(&(name)[(bit)/8], ~(1 << ((bit) % 8))))
 
 #define CLR_BITMASK(name, size) \
 ({ \
        } \
        clear; })
 
+static inline bool BITMASK_IS_FULL(uint8_t* map, size_t size)
+{
+       int _size = size;
+       for (int i = 0; i < BYTES_FOR_BITMASK(size); i++) {
+               for (int j = 0; j < MIN(8,_size); j++)
+                       if(!((map[i] >> j) &1))
+                               return FALSE;
+                       _size--;
+       }
+       return TRUE;
+}
+
 #define PRINT_BITMASK(name, size) { \
        int i;  \
+       int _size = size; \
        for (i = 0; i < BYTES_FOR_BITMASK(size); i++) { \
                int j;  \
-               for (j = 0; j < 8; j++) \
+               for (j = 0; j < MIN(8,_size); j++) \
                        printk("%x", ((name)[i] >> j) & 1);     \
+                       _size--; \
        } \
        printk("\n"); \
 }
 
+static inline bool BITMASK_IS_SET_IN_RANGE(uint8_t* m, size_t beg, size_t end)
+{
+       for(size_t i=beg; i<end; i++) {
+               if(!GET_BITMASK_BIT(m, i))
+                       return FALSE;
+       }
+       return TRUE;
+}
+
+static inline bool BITMASK_IS_CLR_IN_RANGE(uint8_t* m, size_t beg, size_t end)
+{
+       for(size_t i=beg; i<end; i++) {
+               if(GET_BITMASK_BIT(m, i))
+                       return FALSE;
+       }
+       return TRUE;
+}
+
+static inline void SET_BITMASK_RANGE(uint8_t* m, size_t beg, size_t end)
+{
+       for(size_t i=beg; i<end; i++) {
+               SET_BITMASK_BIT(m, i);
+       }
+}
+
+static inline void CLR_BITMASK_RANGE(uint8_t* m, size_t beg, size_t end)
+{
+       for(size_t i=beg; i<end; i++) {
+               CLR_BITMASK_BIT(m, i);
+       }
+}
 #endif /* ROS_ARCH_BITMASK_H */
index f2da21d..78118dc 100644 (file)
 #define SINIT(x) x
 #endif
 
+#include <ros/error.h>
+#include <arch/bitmask.h>
 #include <colored_caches.h>
+#include <process.h>
+
+// Static global variable of caches to assign to the available caches struct
+static cache_t RO l1,l2,l3;
+
+// Convenient global variable for accessing the last level cache
+cache_t* llc_cache;
 
 // Global variables
-cache_t RO l1,l2,l3;
 available_caches_t RO available_caches;
 
 /************** Cache Related Functions  *****************/
@@ -22,11 +30,20 @@ void cache_init()
        // Initialize the caches available on this system.
        // TODO: Should call out to something reading the acpi tables from 
        // memory, or something similar.  For now, just initialize them inline
+       available_caches.l1 = SINIT(&l1);
+       available_caches.l2 = SINIT(&l2);
+       available_caches.l3 = SINIT(&l3);
+       llc_cache = &l3;
        init_cache_properties(&l1,   32,  8, 64);
        init_cache_properties(&l2,  256,  8, 64);
        init_cache_properties(&l3, 8192, 16, 64);
-       available_caches.l1 = SINIT(TRUE);
-       available_caches.l2 = SINIT(TRUE);
-       available_caches.l3 = SINIT(TRUE);
-       available_caches.llc = SINIT(&l3);
+       printk("Cache init successful\n");
+}
+
+void cache_color_alloc_init()
+{
+       init_free_cache_colors_map(&l1);
+       init_free_cache_colors_map(&l2);
+       init_free_cache_colors_map(&l3);
 }
+
index 2f7bf9b..e469360 100644 (file)
@@ -168,6 +168,7 @@ int ne2k_scan_pci() {
 
 void ne2k_configure_nic() {
        
+       printk("I made it here...\n");
        ne2k_debug("-->Configuring Device.\n");
        
        // Reset. Yes reading from this addr resets it
index 1129be3..feb13ef 100644 (file)
 #include <pmap.h>
 #include <kmalloc.h>
 
-// llc stands for last-level-cache
-uint16_t RO llc_num_colors;
 spinlock_t colored_page_free_list_lock;
 
-page_list_t LCKD(&colored_page_free_list_lock) * CT(llc_num_colors) RO
+page_list_t LCKD(&colored_page_free_list_lock) * CT(llc_cache->num_colors) RO
   colored_page_free_list = NULL;
 
-static void page_alloc_bootstrap(cache_t RO* llc) {
-       // Initialize the properties of the last level cache used by this allocator
-       size_t nc = get_cache_num_page_colors(llc);
-       llc_num_colors = SINIT(nc);
-
+static void page_alloc_bootstrap() {
        // Allocate space for the array required to manage the free lists
-       size_t list_size = llc_num_colors*sizeof(page_list_t);
+       size_t list_size = llc_cache->num_colors*sizeof(page_list_t);
        page_list_t LCKD(&colored_page_free_list_lock)*tmp =
            (page_list_t*)boot_alloc(list_size,PGSIZE);
        colored_page_free_list = SINIT(tmp);
@@ -42,17 +36,15 @@ static void page_alloc_bootstrap(cache_t RO* llc) {
  */
 void page_alloc_init()
 {
-       cache_t RO* llc = available_caches.llc;
-
        // First Bootstrap the page alloc process
        static bool RO bootstrapped = FALSE;
        if(!bootstrapped) {
                bootstrapped = SINIT(TRUE);
-               page_alloc_bootstrap(llc);
+               page_alloc_bootstrap();
        }
 
        // Then, initialize the array required to manage the colored page free list
-       for(int i=0; i<llc_num_colors; i++) {
+       for(int i=0; i<llc_cache->num_colors; i++) {
                LIST_INIT(&(colored_page_free_list[i]));
        }
 
@@ -76,7 +68,8 @@ void page_alloc_init()
        for (i = 2; i < PPN(IOPHYSMEM); i++) {
                pages[i].page_ref = 0;
                LIST_INSERT_HEAD(
-                  &(colored_page_free_list[get_page_color(page2ppn(&pages[i]), llc)]),
+                  &(colored_page_free_list[get_page_color(page2ppn(&pages[i]), 
+                                                              llc_cache)]),
                   &pages[i],
                   page_link
                );
@@ -90,7 +83,8 @@ void page_alloc_init()
        for (i = PPN(physaddr_after_kernel); i < PPN(maxaddrpa); i++) {
                pages[i].page_ref = 0;
                LIST_INSERT_HEAD(
-                  &(colored_page_free_list[get_page_color(page2ppn(&pages[i]), llc)]),
+                  &(colored_page_free_list[get_page_color(page2ppn(&pages[i]), 
+                                                              llc_cache)]),
                   &pages[i],
                   page_link
                );
@@ -100,5 +94,6 @@ void page_alloc_init()
        for (i = PPN(maxaddrpa); i < npages; i++) {
                pages[i].page_ref = 1;
        }
+       printk("Page alloc init successful\n");
 }
 
index 0ead41f..5c33f2a 100644 (file)
@@ -698,7 +698,7 @@ page_check(void)
        assert(pp2 && pp2 != pp1 && pp2 != pp0);
 
        // temporarily steal the rest of the free pages
-       for(int i=0; i<llc_num_colors; i++) {
+       for(int i=0; i<llc_cache->num_colors; i++) {
                fl[i] = colored_page_free_list[i];
                LIST_INIT(&colored_page_free_list[i]);
        }
@@ -817,7 +817,7 @@ page_check(void)
        }
 
        // give free list back
-       for(int i=0; i<llc_num_colors; i++)
+       for(int i=0; i<llc_cache->num_colors; i++)
                colored_page_free_list[i] = fl[i];
 
        // free the pages we took
index 745d485..d427571 100644 (file)
        } \
        clear; })
 
+static inline bool BITMASK_IS_FULL(uint8_t* map, size_t size)
+{
+       int _size = size;
+       for (int i = 0; i < BYTES_FOR_BITMASK(size); i++) {
+               for (int j = 0; j < MIN(8,_size); j++)
+                       if(!GET_BITMASK_BIT(map, i))
+                               return FALSE;
+                       _size--;
+       }
+       return TRUE;
+}
+
 #define PRINT_BITMASK(name, size) { \
        int i;  \
        for (i = 0; i < BYTES_FOR_BITMASK(size); i++) { \
        printk("\n"); \
 }
 
+static inline bool BITMASK_IS_SET_IN_RANGE(uint8_t* m, size_t beg, size_t end)
+{
+       for(size_t i=beg; i<end; i++) {
+               if(!GET_BITMASK_BIT(m, i))
+                       return FALSE;
+       }
+       return TRUE;
+}
+
+static inline bool BITMASK_IS_CLR_IN_RANGE(uint8_t* m, size_t beg, size_t end)
+{
+       for(size_t i=beg; i<end; i++) {
+               if(GET_BITMASK_BIT(m, i))
+                       return FALSE;
+       }
+       return TRUE;
+}
+
+static inline void SET_BITMASK_RANGE(uint8_t* m, size_t beg, size_t end)
+{
+       for(size_t i=beg; i<end; i++) {
+               SET_BITMASK_BIT(m, i);
+       }
+}
+
+static inline void CLR_BITMASK_RANGE(uint8_t* m, size_t beg, size_t end)
+{
+       for(size_t i=beg; i<end; i++) {
+               CLR_BITMASK_BIT(m, i);
+       }
+}
 #endif /* ROS_ARCH_BITMASK_H */
+
index 683881f..e2143ac 100644 (file)
@@ -6,13 +6,15 @@
  */
 
 #include <colored_caches.h>
+#include <stdio.h>
 
 #ifdef __SHARC__
 #pragma nosharc
 #endif
 
 // Global variables
-cache_t l1,l2,l3;
+static cache_t l1,l2,l3;
+cache_t* llc_cache;
 available_caches_t available_caches;
 
 /************** Cache Related Functions  *****************/
@@ -21,9 +23,20 @@ void cache_init()
        // Initialize the caches available on this system.
        // TODO: Should call out to something reading the acpi tables from 
        // memory, or something similar.  For now, just initialize them inline
-       init_cache_properties(&l1, 32,  8, 64);
-       available_caches.l1 = TRUE;
-       available_caches.l2 = FALSE;
-       available_caches.l3 = FALSE;
-       available_caches.llc = &l1;
+       available_caches.l1 = SINIT(&l1);
+       available_caches.l2 = SINIT(&l2);
+       available_caches.l3 = SINIT(&l3);
+       llc_cache = &l3;
+       init_cache_properties(&l1,   32,  8, 64);
+       init_cache_properties(&l2,  256,  8, 64);
+       init_cache_properties(&l3, 8192, 16, 64);
+       printk("Cache init successful\n");
 }
+
+void cache_color_alloc_init()
+{
+       init_free_cache_colors_map(&l1);
+       init_free_cache_colors_map(&l2);
+       init_free_cache_colors_map(&l3);
+}
+
index 042a117..937eb1c 100644 (file)
@@ -128,7 +128,7 @@ env_user_mem_free(env_t* e)
                        l2pt[l2x] = 0;
 
                        // free the L3 PT itself
-                       page_decref(pa2page(l2ptpa));
+                       page_decref(pa2page(l3ptpa));
                }
 
                l1pt[l1x] = 0;
index f0afaf0..ad247b2 100644 (file)
 #include <pmap.h>
 #include <kmalloc.h>
 #include <multiboot.h>
+#include <colored_caches.h>
 
-// llc stands for last-level-cache
-uint16_t llc_num_colors;
-page_list_t *COUNT(llc_num_colors) colored_page_free_list = NULL;
+page_list_t *COUNT(llc_cache->num_colors) colored_page_free_list = NULL;
 spinlock_t colored_page_free_list_lock;
 
-void page_alloc_bootstrap(cache_t* llc) {
-        // Initialize the properties of the last level cache used by this allocator
-        llc_num_colors = get_cache_num_page_colors(llc);
-
+void page_alloc_bootstrap() {
         // Allocate space for the array required to manage the free lists
-        size_t list_size = llc_num_colors*sizeof(page_list_t);
+        size_t list_size = llc_cache->num_colors*sizeof(page_list_t);
         colored_page_free_list = (page_list_t*) boot_alloc(list_size, PGSIZE);
 }
 
@@ -41,17 +37,16 @@ void page_alloc_bootstrap(cache_t* llc) {
  */
 void page_alloc_init() 
 {
-        cache_t* llc = available_caches.llc;
-
         // First Bootstrap the page alloc process
         static bool bootstrapped = FALSE;
         if(!bootstrapped) {
                 bootstrapped = TRUE;
-                page_alloc_bootstrap(llc);
+                page_alloc_bootstrap();
         }
 
-        // Then, initialize the array required to manage the colored page free list
-        for(int i=0; i<llc_num_colors; i++) {
+        // Then, initialize the array required to manage the 
+               // colored page free list
+        for(int i=0; i<llc_cache->num_colors; i++) {
                 LIST_INIT(&(colored_page_free_list[i]));
         }
        
@@ -76,7 +71,8 @@ void page_alloc_init()
        {
                pages[i].page_ref = 0;
                 LIST_INSERT_HEAD(
-                   &(colored_page_free_list[get_page_color(page2ppn(&pages[i]), llc)]),
+                   &(colored_page_free_list[get_page_color(page2ppn(&pages[i]),
+                                                           llc_cache)]),
                    &pages[i],
                    page_link
                 );
@@ -86,3 +82,4 @@ void page_alloc_init()
        for(i = PPN(maxaddrpa); i < npages; i++)
                pages[i].page_ref = 1;
 }
+
index 5d5e6b6..3510f95 100644 (file)
@@ -9,36 +9,43 @@
 #define ROS_KERN_COLORED_CACHES_H
 
 #include <ros/common.h>
+#include <ros/error.h>
+#include <process.h>
 
 /****************** Cache Structures ********************/
 typedef struct Cache {
        size_t wa;
        size_t sz_k;
        size_t clsz;
+       uint8_t* free_colors_map;
        
        //Added as optimization (derived from above);
        size_t num_colors;
 } cache_t;
 
 typedef struct AvailableCaches {
-       uint8_t l1 : 1;
-       uint8_t l2 : 1;
-       uint8_t l3 : 1;
-
-       // Pointer to the last level cache
-       cache_t RO*   llc;
+       cache_t* l1;
+       cache_t* l2;
+       cache_t* l3;
 } available_caches_t;
 
 /******** Externally visible global variables ************/
-extern cache_t RO l1,l2,l3;
 extern available_caches_t RO available_caches;
+extern cache_t* llc_cache;
+extern spinlock_t cache_colors_lock;
 
 /************** Cache Related Functions  *****************/
 void cache_init();
+void cache_color_alloc_init();
 void init_cache_properties(cache_t RO*c, size_t sz_k, size_t wa, size_t clsz);
+void init_free_cache_colors_map(cache_t* c);
 size_t get_page_color(uintptr_t page, cache_t RO*c);
 size_t get_offset_in_cache_line(uintptr_t addr, cache_t RO*c);
 void print_cache_properties(char *NT lstring, cache_t RO*c);
+error_t cache_color_alloc(cache_t* c, struct proc* p);
+error_t cache_color_alloc_specific(size_t color, cache_t* c, struct proc* p);
+void cache_color_free(cache_t* c, struct proc* p);
+void cache_color_free_specific(size_t color, cache_t* c, struct proc* p);
 
 /****************** Cache Properties *********************/
 inline size_t get_cache_ways_associative(cache_t RO*c);
index dc3f080..2d7d128 100644 (file)
@@ -61,11 +61,15 @@ struct Env {
        int32_t vcoremap[MAX_NUM_CPUS];
        uint32_t num_vcores;
 
+       /* Cache color map: bitmap of the cache colors currently allocated to this
+        * process */
+       uint8_t* cache_colors_map;
+
        /* Info about this process's resources (granted, desired) for each type. */
        struct resource resources[MAX_NUM_RESOURCES];
 
        /* Keeps track of this process's current memory allocation 
-         * (i.e. its heap pointer */
+     * (i.e. its heap pointer) */
        void* end_text_segment;
        void* end_data_segment;
 
index 938f785..95ba04e 100644 (file)
@@ -31,7 +31,6 @@ struct Page {
 
 
 /******** Externally visible global variables ************/
-extern uint16_t RO llc_num_colors;
 extern spinlock_t colored_page_free_list_lock;
 extern page_list_t LCKD(&colored_page_free_list_lock) * RO CT(llc_num_colors)
     colored_page_free_list;
index 81d99a2..28c4a3e 100644 (file)
@@ -13,6 +13,7 @@ void test_pic_reception(void);
 void test_ioapic_pit_reroute(void);
 void test_print_info(void);
 void test_page_coloring(void);
+void test_color_alloc(void);
 void test_barrier(void);
 void test_interrupts_irqsave(void);
 void test_bitmasks(void);
index d5dcbad..38bcc12 100644 (file)
 
 #include <ros/common.h>
 #include <arch/mmu.h>
+#include <arch/bitmask.h>
 #include <colored_caches.h>
 #include <stdio.h>
+#include <atomic.h>
+#include <kmalloc.h>
+
+#define l1 (available_caches.l1)
+#define l2 (available_caches.l2)
+#define l3 (available_caches.l3)
+
+spinlock_t cache_colors_lock;
 
 /************** Cache Related Functions  *****************/
 inline void init_cache_properties(cache_t *c, size_t sz_k, size_t wa, size_t clsz) {
        c->wa = SINIT(wa);
        c->sz_k = SINIT(sz_k);
        c->clsz = SINIT(clsz);
-       
+
        //Added as optimization (derived from above);
        size_t nc = get_cache_num_page_colors(c);
        c->num_colors = SINIT(nc);
 }
+
+inline void init_free_cache_colors_map(cache_t* c) 
+{
+       // Initialize the free colors map
+       c->free_colors_map = kmalloc(c->num_colors, 0);
+       FILL_BITMASK(c->free_colors_map, c->num_colors);
+}
+
 inline size_t get_page_color(uintptr_t page, cache_t *c) {
     return (page % c->num_colors);
 }
@@ -115,3 +132,139 @@ inline size_t get_cache_num_page_colors(cache_t *c) {
        return get_cache_pages_per_way(c);
 }
 
+static inline void set_color_range(uint16_t color, uint8_t* map, 
+                                   cache_t* smaller, cache_t* bigger)
+{
+       size_t base, r;
+       if(smaller->num_colors <= bigger->num_colors) {
+               r = bigger->num_colors / smaller->num_colors;
+               base = color*r;
+               SET_BITMASK_RANGE(map, base, base+r);
+       }
+       else {
+               r = smaller->num_colors / bigger->num_colors;
+               base = color/r;
+               if(BITMASK_IS_SET_IN_RANGE(smaller->free_colors_map, 
+                                          base*r, base*r+r-1))
+                       SET_BITMASK_BIT(map, base);
+       }
+}
+
+static inline void clr_color_range(uint16_t color, uint8_t* map, 
+                                   cache_t* smaller, cache_t* bigger)
+{
+       size_t base, r;
+       if(smaller->num_colors <= bigger->num_colors) {
+               r = bigger->num_colors / smaller->num_colors;
+               base = color*r;
+               CLR_BITMASK_RANGE(map, base, base+r);
+       }
+       else {
+               r = smaller->num_colors / bigger->num_colors;
+               base = color/r;
+               CLR_BITMASK_BIT(map, base);
+       }
+}
+
+static inline error_t __cache_color_alloc_specific(size_t color, cache_t* c, 
+                                                              struct proc* p) 
+{
+       if(!GET_BITMASK_BIT(c->free_colors_map, color))
+               return -ENOCACHE;       
+       
+       if(l1)
+               clr_color_range(color, l1->free_colors_map, c, l1);
+       if(l2)
+               clr_color_range(color, l2->free_colors_map, c, l2);
+       if(l3)
+               clr_color_range(color, l3->free_colors_map, c, l3);
+
+       printk("I am here now three...\n");
+       set_color_range(color, p->cache_colors_map, c, llc_cache);
+       return ESUCCESS;
+}
+
+static inline error_t __cache_color_alloc(cache_t* c, struct proc* p) 
+{
+       if(BITMASK_IS_CLEAR(c->free_colors_map, c->num_colors))
+               return -ENOCACHE;       
+
+       int color=0;
+       do {
+               if(GET_BITMASK_BIT(c->free_colors_map, color))
+                       break;
+       } while(++color);
+
+       return __cache_color_alloc_specific(color, c, p);       
+}
+
+static inline void __cache_color_free_specific(size_t color, cache_t* c, 
+                                                          struct proc* p) 
+{
+       if(GET_BITMASK_BIT(c->free_colors_map, color))
+               return;
+       else {
+               size_t r = llc_cache->num_colors / c->num_colors;
+               size_t base = color*r;
+               if(!BITMASK_IS_SET_IN_RANGE(p->cache_colors_map, base, base+r))
+                       return;
+       }
+
+       if(l3)
+               set_color_range(color, l3->free_colors_map, c, l3);
+       if(l2)
+               set_color_range(color, l2->free_colors_map, c, l2);
+       if(l1)
+               set_color_range(color, l1->free_colors_map, c, l1);
+
+       clr_color_range(color, p->cache_colors_map, c, llc_cache);
+}
+
+static inline void __cache_color_free(cache_t* c, struct proc* p) 
+{
+       if(BITMASK_IS_FULL(c->free_colors_map, c->num_colors))
+               return; 
+
+       int color=0;
+       do {
+               if(!GET_BITMASK_BIT(c->free_colors_map, color)) {
+                       size_t r = llc_cache->num_colors / c->num_colors;
+                       size_t base = color*r;
+                       if(BITMASK_IS_SET_IN_RANGE(p->cache_colors_map, base, base+r))
+                               break;
+               }
+       } while(++color < c->num_colors);
+       if(color == c->num_colors)
+               return;
+
+       __cache_color_free_specific(color, c, p);       
+}
+
+error_t cache_color_alloc(cache_t* c, struct proc* p) 
+{
+       spin_lock_irqsave(&cache_colors_lock);
+       error_t e = __cache_color_alloc(c, p);
+       spin_unlock_irqsave(&cache_colors_lock);
+       return e;
+}
+error_t cache_color_alloc_specific(size_t color, cache_t* c, struct proc* p) 
+{
+       spin_lock_irqsave(&cache_colors_lock);
+       error_t e = __cache_color_alloc_specific(color, c, p);
+       spin_unlock_irqsave(&cache_colors_lock);
+       return e;
+}
+
+void cache_color_free(cache_t* c, struct proc* p) 
+{
+       spin_lock_irqsave(&cache_colors_lock);
+       __cache_color_free(c, p);
+       spin_unlock_irqsave(&cache_colors_lock);
+}
+void cache_color_free_specific(size_t color, cache_t* c, struct proc* p) 
+{
+       spin_lock_irqsave(&cache_colors_lock);
+       __cache_color_free_specific(color, c, p);
+       spin_unlock_irqsave(&cache_colors_lock);
+}
+
index 2a55103..d319916 100644 (file)
@@ -6,6 +6,7 @@
 
 #include <arch/arch.h>
 #include <arch/mmu.h>
+#include <arch/bitmask.h>
 #include <elf.h>
 #include <smp.h>
 
@@ -19,6 +20,7 @@
 #include <manager.h>
 #include <stdio.h>
 #include <schedule.h>
+#include <kmalloc.h>
 
 #include <ros/syscall.h>
 #include <ros/error.h>
@@ -108,7 +110,6 @@ env_init(void)
                envs[i].env_id = 0;
                TAILQ_INSERT_HEAD(&proc_freelist, &envs[i], proc_link);
        }
-
 }
 
 //
@@ -284,6 +285,8 @@ env_alloc(env_t **newenv_store, envid_t parent_id)
        e->num_vcores = 0;
        for (int i = 0; i < MAX_NUM_CPUS; i++)
                e->vcoremap[i] = -1;
+       e->cache_colors_map = kmalloc(llc_cache->num_colors, 0);
+       CLR_BITMASK(e->cache_colors_map, llc_cache->num_colors);
        memset(&e->resources, 0, sizeof(e->resources));
 
        memset(&e->env_ancillary_state, 0, sizeof(e->env_ancillary_state));
@@ -509,6 +512,9 @@ env_free(env_t *e)
        e->env_cr3 = 0;
        page_decref(pa2page(pa));
 
+       //Free any memory allocated by this process
+       kfree(e->cache_colors_map);
+
        // return the environment to the free list
        e->state = ENV_FREE;
        spin_lock(&freelist_lock);
index 2c923f4..6da3b6e 100644 (file)
@@ -29,7 +29,9 @@
 #include <kmalloc.h>
 
 #include <arch/init.h>
+#include <arch/bitmask.h>
 #include <slab.h>
+#include <kfs.h>
 
 // zra: flag for Ivy
 int booting = 1;
@@ -67,6 +69,7 @@ void kernel_init(multiboot_info_t *mboot_info)
        page_check();
        kmem_cache_init();
        kmalloc_init();
+       //cache_color_alloc_init();
 
        idt_init();
        sysenter_init();
@@ -74,6 +77,10 @@ void kernel_init(multiboot_info_t *mboot_info)
        
        // At this point our boot paths diverge based on arch. 
        arch_init();
+               
+//     printk("Starting tests....\n");
+//     test_color_alloc();
+//     printk("Testing complete....\n");
 
        // zra: let's Ivy know we're done booting
        booting = 0;
index fcbe64a..ed70f23 100644 (file)
 #include <pmap.h>
 #include <string.h>
 
+#define l1 (available_caches.l1)
+#define l2 (available_caches.l2)
+#define l3 (available_caches.l3)
+
 static void __page_decref(page_t *page);
+static void __page_incref(page_t *page);
 static error_t __page_alloc_specific(page_t** page, size_t ppn);
 static error_t __page_free(page_t* page);
 
+// Global list of colors allocated to the general purpose memory allocator
+static uint8_t* global_colors_map;
+
 /**
  * @brief Clear a Page structure.
  *
@@ -37,7 +45,8 @@ error_t page_alloc_from_color_range(page_t** page,
     //  in the proper range
        int i = base_color;
        spin_lock_irqsave(&colored_page_free_list_lock);
-       for(i; i<(base_color+range); i++) {
+       //for(i; i < (base_color+range); i++) {
+       for (i; i < (base_color+range); i++) {
                if(!LIST_EMPTY(&colored_page_free_list[i]))
                        break;
        }
@@ -67,7 +76,23 @@ error_t page_alloc_from_color_range(page_t** page,
  */
 error_t page_alloc(page_t** page) 
 {
-       return page_alloc_from_color_range(page, 0, llc_num_colors);
+       static size_t next_color = 0;
+       error_t e;
+       for(int i=next_color; i<llc_cache->num_colors; i++) {
+               e = page_alloc_from_color_range(page, i, 1);
+               if(e == ESUCCESS) {
+                       next_color = i+1;
+                       return e;
+               }
+       }
+       for(int i=0; i<next_color; i++) {
+               e = page_alloc_from_color_range(page, i, 1);
+               if(e == ESUCCESS) {
+                       next_color = i+1;
+                       return e;
+               }
+       }
+       return -ENOMEM;
 }
 
 /**
@@ -145,24 +170,12 @@ void free_cont_pages(void *buf, size_t order)
  * RETURNS 
  *   ESUCCESS  -- on success
  *   -ENOMEM   -- otherwise 
- *
- * error_t _cache##_page_alloc(page_t** page, size_t color)
- * {
- *      if(!LIST_EMPTY(&(_cache##_cache_colored_page_list)[(color)])) {
- *       *(page) = LIST_FIRST(&(_cache##_cache_colored_page_list)[(color)]);
- *              LIST_REMOVE(*page, global_link);
- *              REMOVE_CACHE_COLORING_PAGE_FROM_FREE_LISTS(page);
- *              page_clear(*page);
- *              return ESUCCESS;
- *      }
- *      return -ENOMEM;
- * }
  */
 error_t l1_page_alloc(page_t** page, size_t color)
 {
-       if(available_caches.l1)
+       if(l1)
        {
-               uint16_t range = llc_num_colors / get_cache_num_page_colors(&l1);
+               uint16_t range = llc_cache->num_colors / get_cache_num_page_colors(l1);
                uint16_t base_color = color*range;
                return page_alloc_from_color_range(page, base_color, range);
        }
@@ -171,9 +184,9 @@ error_t l1_page_alloc(page_t** page, size_t color)
 
 error_t l2_page_alloc(page_t** page, size_t color)
 {
-       if(available_caches.l2)
+       if(l2)
        {
-               uint16_t range = llc_num_colors / get_cache_num_page_colors(&l2);
+               uint16_t range = llc_cache->num_colors / get_cache_num_page_colors(l2);
                uint16_t base_color = color*range;
                return page_alloc_from_color_range(page, base_color, range);
        }
@@ -182,9 +195,9 @@ error_t l2_page_alloc(page_t** page, size_t color)
 
 error_t l3_page_alloc(page_t** page, size_t color)
 {
-       if(available_caches.l3)
+       if(l3)
        {
-               uint16_t range = llc_num_colors / get_cache_num_page_colors(&l3);
+               uint16_t range = llc_cache->num_colors / get_cache_num_page_colors(l3);
                uint16_t base_color = color*range;
                return page_alloc_from_color_range(page, base_color, range);
        }
@@ -233,10 +246,9 @@ error_t page_alloc_specific(page_t** page, size_t ppn)
 static error_t __page_free(page_t* page) 
 {
        page_clear(page);
-       cache_t* llc = available_caches.llc;
 
        LIST_INSERT_HEAD(
-          &(colored_page_free_list[get_page_color(page2ppn(page), llc)]),
+          &(colored_page_free_list[get_page_color(page2ppn(page), llc_cache)]),
           page,
           page_link
        );
@@ -268,6 +280,11 @@ int page_is_free(size_t ppn) {
  */
 void page_incref(page_t *page)
 {
+       __page_incref(page);
+}
+
+void __page_incref(page_t *page)
+{
        page->page_ref++;
 }
 
@@ -289,7 +306,7 @@ void page_decref(page_t *page)
 static void __page_decref(page_t *page)
 {
        if (page->page_ref == 0) {
-               warn("Trying to Free already freed page...\n");
+               warn("Trying to Free already freed page: %d...\n", page2ppn(page));
                return;
        }
        if (--page->page_ref == 0)
index 67f9c53..840d8fa 100644 (file)
@@ -84,7 +84,7 @@ static ssize_t sys_run_binary(env_t* e, void *DANGEROUS binary_buf,
                               void*DANGEROUS arg, size_t len) {
        uint8_t *CT(len) checked_binary_buf;
        checked_binary_buf = user_mem_assert(e, binary_buf, len, PTE_USER_RO);
-
+       
        uint8_t* new_binary = kmalloc(len, 0);
        if(new_binary == NULL)
                return -ENOMEM;
index 916cd04..2fa3efa 100644 (file)
 #include <slab.h>
 #include <kmalloc.h>
 
+#define l1 (available_caches.l1)
+#define l2 (available_caches.l2)
+#define l3 (available_caches.l3)
+
 #ifdef __i386__
 
 void test_ipi_sending(void)
@@ -113,11 +117,11 @@ void test_print_info(void)
 void test_page_coloring(void) 
 {
        //Print the different cache properties of our machine
-       print_cache_properties("L1", &l1);
+       print_cache_properties("L1", l1);
        cprintf("\n");
-       print_cache_properties("L2", &l2);
+       print_cache_properties("L2", l2);
        cprintf("\n");
-       print_cache_properties("L3", &l3);
+       print_cache_properties("L3", l3);
        cprintf("\n");
 
        //Print some stats about our memory
@@ -128,7 +132,7 @@ void test_page_coloring(void)
        page_t* page;
 
        cprintf("Contents of the page free list:\n");
-       for(int i=0; i<llc_num_colors; i++) {
+       for(int i=0; i<llc_cache->num_colors; i++) {
                cprintf("  COLOR %d:\n", i);
                LIST_FOREACH(page, &colored_page_free_list[i], page_link) {
                        cprintf("    Page: %d\n", page2ppn(page));
@@ -137,7 +141,7 @@ void test_page_coloring(void)
 
        //Run through and allocate all pages through l1_page_alloc
        cprintf("Allocating from L1 page colors:\n");
-       for(int i=0; i<get_cache_num_page_colors(&l1); i++) {
+       for(int i=0; i<get_cache_num_page_colors(l1); i++) {
                cprintf("  COLOR %d:\n", i);
                while(l1_page_alloc(&page, i) != -ENOMEM)
                        cprintf("    Page: %d\n", page2ppn(page));
@@ -148,7 +152,7 @@ void test_page_coloring(void)
        
        //Run through and allocate all pages through l2_page_alloc
        cprintf("Allocating from L2 page colors:\n");
-       for(int i=0; i<get_cache_num_page_colors(&l2); i++) {
+       for(int i=0; i<get_cache_num_page_colors(l2); i++) {
                cprintf("  COLOR %d:\n", i);
                while(l2_page_alloc(&page, i) != -ENOMEM)
                        cprintf("    Page: %d\n", page2ppn(page));
@@ -159,7 +163,7 @@ void test_page_coloring(void)
        
        //Run through and allocate all pages through l3_page_alloc
        cprintf("Allocating from L3 page colors:\n");
-       for(int i=0; i<get_cache_num_page_colors(&l3); i++) {
+       for(int i=0; i<get_cache_num_page_colors(l3); i++) {
                cprintf("  COLOR %d:\n", i);
                while(l3_page_alloc(&page, i) != -ENOMEM)
                        cprintf("    Page: %d\n", page2ppn(page));
@@ -189,6 +193,43 @@ void test_page_coloring(void)
                cprintf("Page: %d\n", page2ppn(page));  
 }
 
+void test_color_alloc() {
+       size_t checkpoint = 0;
+       struct proc* p = kfs_proc_create(kfs_lookup_path("parlib_matrix"));
+       cache_color_alloc(l2, p);
+       cache_color_alloc(l3, p);
+       cache_color_alloc(l3, p);
+       cache_color_alloc(l2, p);
+       cache_color_free(llc_cache, p);
+       cache_color_free(llc_cache, p);
+       cache_color_free(llc_cache, p);
+       cache_color_free(llc_cache, p);
+       cache_color_free(llc_cache, p);
+       cache_color_free(llc_cache, p);
+       cache_color_free(llc_cache, p);
+       cache_color_free(llc_cache, p);
+       cache_color_free(llc_cache, p);
+       cache_color_free(llc_cache, p);
+       cache_color_free(llc_cache, p);
+       cache_color_free(llc_cache, p);
+       cache_color_free(llc_cache, p);
+       cache_color_free(llc_cache, p);
+       cache_color_free(llc_cache, p);
+       cache_color_free(llc_cache, p);
+       cache_color_free(l2, p);
+       cache_color_free(llc_cache, p);
+       cache_color_free(llc_cache, p);
+       printk("L1 free colors, tot colors: %d\n", l1->num_colors);
+       PRINT_BITMASK(l1->free_colors_map, l1->num_colors);
+       printk("L2 free colors, tot colors: %d\n", l2->num_colors);
+       PRINT_BITMASK(l2->free_colors_map, l2->num_colors);
+       printk("L3 free colors, tot colors: %d\n", l3->num_colors);
+       PRINT_BITMASK(l3->free_colors_map, l3->num_colors);
+       printk("Process allocated colors\n");
+       PRINT_BITMASK(p->cache_colors_map, llc_cache->num_colors);
+       printk("test_color_alloc() complete!\n");
+}
+
 barrier_t test_cpu_array;
 
 void test_barrier(void)