Rewrote cache colored page allocation functions
authorKevin Klues <klueska@eecs.berkeley.edu>
Sat, 12 Sep 2009 09:26:22 +0000 (02:26 -0700)
committerKevin Klues <klueska@eecs.berkeley.edu>
Sat, 12 Sep 2009 09:26:22 +0000 (02:26 -0700)
This rewrite now allocates pages from the proper "shade" of color when trying to allocate from a cache that isn't the last level cache.  Implementing things this way allowed me to rip out the multiple linked lists I was useing for managing the free lists for each cache color.  I now only maintain one list per color on the last level cache.  All allocations come out of these lists, and the proper shades are maintained when requesting colors from lower level caches.

Additionally, I fixed up some warnings that resulted from my newer version of gcc.

18 files changed:
GNUmakefile
kern/arch/i386/colored_caches.c
kern/arch/i386/page_alloc.c
kern/arch/i386/pmap.c
kern/arch/sparc/colored_caches.c
kern/include/colored_caches.h
kern/include/page_alloc.h
kern/include/ros/error.h
kern/src/init.c
kern/src/kmalloc.c
kern/src/page_alloc.c
kern/src/printf.c
kern/src/printfmt.c
kern/src/testing.c
user/parlib/src/debug.c
user/roslib/inc/sys~88b8671ba3a11748b50b03007ef263be90e0b490 [new symlink]
user/roslib/src/printf.c
user/roslib/src/printfmt.c

index c44f8ca..2ace0e3 100644 (file)
@@ -59,7 +59,7 @@ KERN_CFLAGS := --deputy\
 USER_CFLAGS := --deputy --enable-error-db
 CC         := ivycc --gcc=$(GCCPREFIX)gcc
 else
-CC         := $(GCCPREFIX)gcc -std=gnu99
+CC         := $(GCCPREFIX)gcc -std=gnu99 -fgnu89-inline
 endif
 
 AS         := $(GCCPREFIX)as
index 2136e6d..f437954 100644 (file)
@@ -27,4 +27,5 @@ void cache_init()
        available_caches.l1 = TRUE;
        available_caches.l2 = TRUE;
        available_caches.l3 = TRUE;
+       available_caches.llc = &l3;
 }
index 4fb6049..abaf22c 100644 (file)
 #include <pmap.h>
 #include <kmalloc.h>
 
-page_list_t page_free_list;    // Free list of physical pages
-DECLARE_CACHE_COLORED_PAGE_FREE_LISTS(); // Free list of pages filed by color
+// llc stands for last-level-cache
+uint16_t llc_num_colors;
+page_list_t *COUNT(llc_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);
+
+       // Allocate space for the array required to manage the free lists
+       size_t list_size = llc_num_colors*sizeof(page_list_t);
+       colored_page_free_list = (page_list_t*) boot_alloc(list_size, PGSIZE);
+}
 
 /*
  * Initialize the memory free lists.
@@ -25,11 +36,21 @@ DECLARE_CACHE_COLORED_PAGE_FREE_LISTS(); // Free list of pages filed by color
  */
 void page_alloc_init() 
 {
-       // Now, initialize the lists required to manage the page free lists
-       LIST_INIT(&page_free_list);
-       INIT_CACHE_COLORED_PAGE_FREE_LISTS();
-       
-       //  Finally, mark the pages already in use by the kernel. 
+       cache_t* llc = available_caches.llc;
+
+       // First Bootstrap the page alloc process
+       static bool bootstrapped = FALSE;
+       if(!bootstrapped) {
+               bootstrapped = TRUE;
+               page_alloc_bootstrap(llc);
+       }
+
+       // Then, initialize the array required to manage the colored page free list
+       for(int i=0; i<llc_num_colors; i++) {
+               LIST_INIT(&(colored_page_free_list[i]));
+       }
+
+       //  Then, mark the pages already in use by the kernel. 
        //  1) Mark page 0 as in use.
        //     This way we preserve the real-mode IDT and BIOS structures
        //     in case we ever need them.  (Currently we don't, but...)
@@ -48,8 +69,11 @@ void page_alloc_init()
        pages[1].page_ref = 1;
        for (i = 2; i < PPN(IOPHYSMEM); i++) {
                pages[i].page_ref = 0;
-               LIST_INSERT_HEAD(&page_free_list, &pages[i], global_link);
-               INSERT_CACHE_COLORING_PAGE_ONTO_FREE_LISTS(&pages[i]);
+               LIST_INSERT_HEAD(
+                  &(colored_page_free_list[get_page_color(page2ppn(&pages[i]), llc)]),
+                  &pages[i],
+                  page_link
+               );
        }
        for (i = PPN(IOPHYSMEM); i < PPN(EXTPHYSMEM); i++) {
                pages[i].page_ref = 1;
@@ -59,8 +83,11 @@ void page_alloc_init()
        }
        for (i = PPN(physaddr_after_kernel); i < PPN(maxaddrpa); i++) {
                pages[i].page_ref = 0;
-               LIST_INSERT_HEAD(&page_free_list, &pages[i], global_link);
-               INSERT_CACHE_COLORING_PAGE_ONTO_FREE_LISTS(&pages[i]);
+               LIST_INSERT_HEAD(
+                  &(colored_page_free_list[get_page_color(page2ppn(&pages[i]), llc)]),
+                  &pages[i],
+                  page_link
+               );
        }
        // this block out all memory above maxaddrpa.  will need another mechanism
        // to allocate and map these into the kernel address space
index 16cff72..53da017 100644 (file)
@@ -683,7 +683,7 @@ void
 page_check(void)
 {
        page_t *pp, *pp0, *pp1, *pp2;
-       page_list_t fl;
+       page_list_t fl[1024];
        pte_t *ptep;
 
        // should be able to allocate three pages
@@ -697,8 +697,10 @@ page_check(void)
        assert(pp2 && pp2 != pp1 && pp2 != pp0);
 
        // temporarily steal the rest of the free pages
-       fl = page_free_list;
-       LIST_INIT(&page_free_list);
+       for(int i=0; i<llc_num_colors; i++) {
+               fl[i] = colored_page_free_list[i];
+               LIST_INIT(&colored_page_free_list[i]);
+       }
 
        // should be no free memory
        assert(page_alloc(&pp) == -ENOMEM);
@@ -814,7 +816,8 @@ page_check(void)
        }
 
        // give free list back
-       page_free_list = fl;
+       for(int i=0; i<llc_num_colors; i++)
+               colored_page_free_list[i] = fl[i];
 
        // free the pages we took
        page_free(pp0);
index ba7a01d..679c4e2 100644 (file)
@@ -18,9 +18,8 @@ void cache_init()
        // 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);
-       init_cache_properties(&l2,  256,  8, 64);
-       init_cache_properties(&l3, 8192, 16, 64);
        available_caches.l1 = TRUE;
        available_caches.l2 = FALSE;
        available_caches.l3 = FALSE;
+       available_caches.llc = &l1;
 }
index 691336a..14cc093 100644 (file)
@@ -24,6 +24,9 @@ typedef struct AvailableCaches {
        uint8_t l1 : 1;
        uint8_t l2 : 1;
        uint8_t l3 : 1;
+
+       // Pointer to the last level cache
+       cache_t*   llc;
 } available_caches_t;
 
 /******** Externally visible global variables ************/
@@ -38,24 +41,24 @@ size_t get_offset_in_cache_line(uintptr_t addr, cache_t *c);
 void print_cache_properties(char *NT lstring, cache_t *c);
 
 /****************** Cache Properties *********************/
-size_t get_cache_ways_associative(cache_t *c);
-size_t get_cache_line_size_bytes(cache_t *c);
-size_t get_cache_size_bytes(cache_t *c);
-size_t get_cache_size_kilobytes(cache_t *c);
-size_t get_cache_size_megabytes(cache_t *c);
-size_t get_cache_num_offset_bits(cache_t *c);
-size_t get_cache_num_index_bits(cache_t *c);
-size_t get_cache_num_tag_bits(cache_t *c);
-size_t get_cache_num_page_color_bits(cache_t *c);
-size_t get_cache_bytes_per_line(cache_t *c);
-size_t get_cache_num_lines(cache_t *c);
-size_t get_cache_num_sets(cache_t *c);
-size_t get_cache_lines_per_set(cache_t *c);
-size_t get_cache_lines_per_page(cache_t *c);
-size_t get_cache_bytes_per_way(cache_t *c);
-size_t get_cache_lines_per_way(cache_t *c);
-size_t get_cache_pages_per_way(cache_t *c);
-size_t get_cache_num_page_colors(cache_t *c);
+inline size_t get_cache_ways_associative(cache_t *c);
+inline size_t get_cache_line_size_bytes(cache_t *c);
+inline size_t get_cache_size_bytes(cache_t *c);
+inline size_t get_cache_size_kilobytes(cache_t *c);
+inline size_t get_cache_size_megabytes(cache_t *c);
+inline size_t get_cache_num_offset_bits(cache_t *c);
+inline size_t get_cache_num_index_bits(cache_t *c);
+inline size_t get_cache_num_tag_bits(cache_t *c);
+inline size_t get_cache_num_page_color_bits(cache_t *c);
+inline size_t get_cache_bytes_per_line(cache_t *c);
+inline size_t get_cache_num_lines(cache_t *c);
+inline size_t get_cache_num_sets(cache_t *c);
+inline size_t get_cache_lines_per_set(cache_t *c);
+inline size_t get_cache_lines_per_page(cache_t *c);
+inline size_t get_cache_bytes_per_way(cache_t *c);
+inline size_t get_cache_lines_per_way(cache_t *c);
+inline size_t get_cache_pages_per_way(cache_t *c);
+inline size_t get_cache_num_page_colors(cache_t *c);
 
 #endif // ROS_KERN_COLORED_CACHES_H
 
index 8be20ce..ed0d141 100644 (file)
@@ -8,6 +8,7 @@
 #ifndef PAGE_ALLOC_H
 #define PAGE_ALLOC_H
 
+#include <atomic.h>
 #include <sys/queue.h>
 #include <ros/error.h>
 #include <arch/mmu.h>
@@ -21,16 +22,17 @@ typedef LIST_HEAD(PageList, Page) page_list_t;
 typedef LIST_ENTRY(Page) page_list_entry_t;
 
 struct Page {
-       page_list_entry_t global_link;
-       DECLARE_CACHE_COLORED_PAGE_LINKS();
+       page_list_entry_t page_link;
        
        size_t num_cons_links;
     size_t page_ref;
 };
 
+
 /******** Externally visible global variables ************/
-extern page_list_t page_free_list;
-DECLARE_EXTERN_CACHE_COLORED_PAGE_FREE_LISTS();
+extern uint16_t llc_num_colors;
+extern page_list_t *COUNT(llc_num_colors) colored_page_free_list;
+extern spinlock_t colored_page_free_list_lock;
 
 /*************** Functional Interface *******************/
 void page_alloc_init(void);
index 4d3b894..318a954 100644 (file)
@@ -16,6 +16,7 @@ typedef enum {
        EDEADLOCK,               // Would cause deadlock
        EBUSY,                   // Currently busy, try again later
        ENOMEM,                  // No memory available
+       ENOCACHE,                // No cache available
        EINVAL,                  // Invalid arguments
        EFAULT,                  // Segmentation fault
        EBADENV,                 // Bad environment 
@@ -40,6 +41,7 @@ static const char *NTS const error_string[NUMERRORS] =
        "Would cause deadlock",
        "Currently busy, try again later",
        "No memory available",
+       "No cache available",
        "Invalid arguments",
        "Segmentation fault",
        "Bad environment",
index a3dd45d..d0b94b8 100644 (file)
@@ -25,6 +25,7 @@
 #include <syscall.h>
 #include <kclock.h>
 #include <manager.h>
+#include <testing.h>
 
 void kernel_init(multiboot_info_t *mboot_info)
 {
@@ -57,6 +58,7 @@ void kernel_init(multiboot_info_t *mboot_info)
        cache_init();
        page_init();
        page_check();
+       //test_page_coloring();
 
        idt_init();
        sysenter_init();
index 51d81ce..30ad21b 100644 (file)
@@ -124,7 +124,7 @@ void* kmalloc(size_t size, int flags)
                page_alloc_specific(&page, first+i);
                page_incref(page);
                page->num_cons_links = npages-i;
-               LIST_INSERT_HEAD(&pages_list, page, global_link);
+               LIST_INSERT_HEAD(&pages_list, page, page_link);
                kmallocdebug("mallocing page: %u\n", first+i);
                kmallocdebug("at addr: %p\n", ppn2kva(first+i));
        }
@@ -140,7 +140,7 @@ void kfree(void *addr)
        kmallocdebug("getting page: %u\n", page2ppn(page));
        for(int i=0; i<num_links; i++) {
                page_t* p = ppn2page((page2ppn(page) + i));
-               LIST_REMOVE(p, global_link);
+               LIST_REMOVE(p, page_link);
                page_free(p);
                kmallocdebug("freeing page: %d\n", page2ppn(p));
        }
index ac4831b..0eb6da4 100644 (file)
@@ -25,6 +25,30 @@ static void page_clear(page_t *SAFE page)
        memset(page, 0, sizeof(page_t));
 }
 
+error_t page_alloc_from_color_range(page_t** page,  
+                                    uint16_t base_color,
+                                    uint16_t range) {
+
+       // Find first available color with pages available
+    //  in the proper range
+       int i = base_color;
+       spin_lock_irqsave(&colored_page_free_list_lock);
+       for(i; i<(base_color+range); i++) {
+               if(!LIST_EMPTY(&colored_page_free_list[i]))
+                       break;
+       }
+       // Alocate a page from that color
+       if(i < (base_color+range)) {
+               *page = LIST_FIRST(&colored_page_free_list[i]);
+               LIST_REMOVE(*page, page_link);
+               page_clear(*page);
+               spin_unlock_irqsave(&colored_page_free_list_lock);
+               return ESUCCESS;
+       }
+       spin_unlock_irqsave(&colored_page_free_list_lock);
+       return -ENOMEM;
+}
+
 /**
  * @brief Allocates a physical page from a pool of unused physical memory
  *
@@ -39,15 +63,7 @@ static void page_clear(page_t *SAFE page)
  */
 error_t page_alloc(page_t** page) 
 {
-       //TODO: Put a lock around this
-       if(!LIST_EMPTY(&page_free_list)) {
-               *page = LIST_FIRST(&page_free_list);
-               LIST_REMOVE(*page, global_link);
-               REMOVE_CACHE_COLORING_PAGE_FROM_FREE_LISTS(page);
-               page_clear(*page);
-               return ESUCCESS;
-       }
-       return -ENOMEM;
+       return page_alloc_from_color_range(page, 0, llc_num_colors);
 }
 
 /*
@@ -82,7 +98,38 @@ error_t page_alloc(page_t** page)
  *      return -ENOMEM;
  * }
  */
-DECLARE_CACHE_COLORED_PAGE_ALLOC_FUNCTIONS();
+error_t l1_page_alloc(page_t** page, size_t color)
+{
+       if(available_caches.l1)
+       {
+               uint16_t range = llc_num_colors / get_cache_num_page_colors(&l1);
+               uint16_t base_color = color*range;
+               return page_alloc_from_color_range(page, base_color, range);
+       }
+       return -ENOCACHE;
+}
+
+error_t l2_page_alloc(page_t** page, size_t color)
+{
+       if(available_caches.l2)
+       {
+               uint16_t range = llc_num_colors / get_cache_num_page_colors(&l2);
+               uint16_t base_color = color*range;
+               return page_alloc_from_color_range(page, base_color, range);
+       }
+       return -ENOCACHE;
+}
+
+error_t l3_page_alloc(page_t** page, size_t color)
+{
+       if(available_caches.l3)
+       {
+               uint16_t range = llc_num_colors / get_cache_num_page_colors(&l3);
+               uint16_t base_color = color*range;
+               return page_alloc_from_color_range(page, base_color, range);
+       }
+       return -ENOCACHE;
+}
 
 /*
  * Allocates a specific physical page.
@@ -99,13 +146,14 @@ DECLARE_CACHE_COLORED_PAGE_ALLOC_FUNCTIONS();
  */
 error_t page_alloc_specific(page_t** page, size_t ppn)
 {
-       //TODO: Put a lock around this
+       spin_lock_irqsave(&colored_page_free_list_lock);
        page_t* sp_page = ppn2page(ppn);
        if( sp_page->page_ref != 0 )
                return -ENOMEM;
        *page = sp_page;
-       LIST_REMOVE(*page, global_link);
-       REMOVE_CACHE_COLORING_PAGE_FROM_FREE_LISTS(page);
+       LIST_REMOVE(*page, page_link);
+       spin_unlock_irqsave(&colored_page_free_list_lock);
+
        page_clear(*page);
        return 0;
 }
@@ -118,8 +166,16 @@ error_t page_free(page_t* page)
 {
        //TODO: Put a lock around this
        page_clear(page);
-       LIST_INSERT_HEAD(&page_free_list, page, global_link);
-       INSERT_CACHE_COLORING_PAGE_ONTO_FREE_LISTS(page);       
+       cache_t* llc = available_caches.llc;
+
+       spin_lock_irqsave(&colored_page_free_list_lock);
+       LIST_INSERT_HEAD(
+          &(colored_page_free_list[get_page_color(page2ppn(page), llc)]),
+          page,
+          page_link
+       );
+       spin_unlock_irqsave(&colored_page_free_list_lock);
+
        return ESUCCESS;
 }
 
@@ -127,7 +183,6 @@ error_t page_free(page_t* page)
  * Check if a page with the given pyhysical page # is free
  */
 int page_is_free(size_t ppn) {
-       //TODO: Put a lock around this
        page_t* page = ppn2page(ppn);
        if( page->page_ref == 0 )
                return TRUE;
index 2cf6ed2..4f4730a 100644 (file)
@@ -55,7 +55,7 @@ int vcprintf(const char *fmt, va_list ap)
        #ifdef __DEPUTY__
        vprintfmt(buffered_putch, &cntp, fmt, ap);
        #else
-       vprintfmt((void*)buffered_putch, (void**)&cntp, fmt, ap);
+       vprintfmt((void*)buffered_putch, (void*)&cntp, fmt, ap);
        #endif
 
        // write out remaining chars in the buffer
index ea18876..030df80 100644 (file)
@@ -286,7 +286,7 @@ int vsnprintf(char *buf, int n, const char *fmt, va_list ap)
        #ifdef __DEPUTY__
        vprintfmt((void*)sprintputch, (sprintbuf_t *NONNULL*NONNULL)&bp, fmt, ap);
        #else
-       vprintfmt((void*)sprintputch, (void**)&bp, fmt, ap);
+       vprintfmt((void*)sprintputch, (void*)&bp, fmt, ap);
        #endif
 
        // null terminate the buffer
index 1c369b2..621e38e 100644 (file)
@@ -106,6 +106,14 @@ void test_page_coloring(void)
        //Declare a local variable for allocating pages 
        page_t* page;
 
+       cprintf("Contents of the page free list:\n");
+       for(int i=0; i<llc_num_colors; i++) {
+               cprintf("  COLOR %d:\n", i);
+               LIST_FOREACH(page, &colored_page_free_list[i], page_link) {
+                       cprintf("    Page: %d\n", page2ppn(page));
+               }
+       }
+
        //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++) {
index 08e0639..fc8a753 100644 (file)
@@ -42,7 +42,7 @@ int vdebug(const char *fmt, va_list ap)
        #ifdef __DEPUTY__
        vdebugfmt(putch, &bp, fmt, ap);
        #else
-       vdebugfmt((void*)putch, (void**)&bp, fmt, ap);
+       vdebugfmt((void*)putch, (void*)&bp, fmt, ap);
        #endif
        sys_cputs(b.buf, b.idx);
 
diff --git a/user/roslib/inc/sys~88b8671ba3a11748b50b03007ef263be90e0b490 b/user/roslib/inc/sys~88b8671ba3a11748b50b03007ef263be90e0b490
new file mode 120000 (symlink)
index 0000000..9692909
--- /dev/null
@@ -0,0 +1 @@
+../../../kern/include/sys
\ No newline at end of file
index 26dbc39..efcd384 100644 (file)
@@ -44,7 +44,7 @@ int vcprintf(const char *fmt, va_list ap)
        #ifdef __DEPUTY__
        vprintfmt(putch, &bp, fmt, ap);
        #else
-       vprintfmt((void*)putch, (void**)&bp, fmt, ap);
+       vprintfmt((void*)putch, (void*)&bp, fmt, ap);
        #endif
        sys_cputs(b.buf, b.idx);
 
@@ -110,7 +110,7 @@ static int vcprintf_async(const char *NTS fmt, va_list ap)
        #ifdef __DEPUTY__
        vprintfmt(putch_async, &b, fmt, ap);
        #else
-       vprintfmt((void*)putch_async, (void**)&b, fmt, ap);
+       vprintfmt((void*)putch_async, (void*)&b, fmt, ap);
        #endif
        // TODO - should check for a return value for sys_
        sys_cputs_async(b->buf, b->idx, get_sys_desc(current_async_desc),
index 74b47e5..a4d86a4 100644 (file)
@@ -278,7 +278,7 @@ int vsnprintf(char *buf, int n, const char *fmt, va_list ap)
        #ifdef __DEPUTY__
        vprintfmt((void*)sprintputch, (sprintbuf_t *NONNULL*NONNULL)&bp, fmt, ap);
        #else
-       vprintfmt((void*)sprintputch, (void**)&bp, fmt, ap);
+       vprintfmt((void*)sprintputch, (void*)&bp, fmt, ap);
        #endif
 
        // null terminate the buffer