Major reworking to integrate cache coloring into the kernel.
authorKevin Klues <klueska@eecs.berkeley.edu>
Sun, 16 Aug 2009 03:18:36 +0000 (20:18 -0700)
committerKevin Klues <klueska@eecs.berkeley.edu>
Fri, 21 Aug 2009 23:40:50 +0000 (16:40 -0700)
A number of new files have been introduced to allow kernel functions
to allocate pages based on page color rather than from a general purpose
allocator.  The biggest change was in a massive reorganization of pmap.c
and the inclusion of some new that are used to implement the page coloring
semantics for a given cache.

25 files changed:
kern/arch/i386/Makefrag
kern/arch/i386/colored_caches.c [new file with mode: 0644]
kern/arch/i386/colored_page_alloc.h [new file with mode: 0644]
kern/arch/i386/page_alloc.c [new file with mode: 0644]
kern/arch/i386/pmap.c
kern/arch/i386/smp_boot.c
kern/arch/i386/types.h
kern/arch/sparc/Makefrag
kern/include/colored_caches.h [new file with mode: 0644]
kern/include/colored_page_alloc.h [new file with mode: 0644]
kern/include/kmalloc.h
kern/include/multiboot.h
kern/include/page_alloc.h [new file with mode: 0644]
kern/include/pmap.h
kern/include/testing.h
kern/src/Makefrag
kern/src/colored_caches.c [new file with mode: 0644]
kern/src/env.c
kern/src/init.c
kern/src/kmalloc.c
kern/src/multiboot.c
kern/src/page_alloc.c [new file with mode: 0644]
kern/src/pmap.c
kern/src/testing.c
scripts/mergedep.pl

index 90e105f..3789053 100644 (file)
@@ -5,6 +5,7 @@
 #
 
 KERN_ARCH_SRC_DIR = $(KERN_DIR)/arch/$(TARGET_ARCH)
 #
 
 KERN_ARCH_SRC_DIR = $(KERN_DIR)/arch/$(TARGET_ARCH)
+OBJDIRS += $(KERN_ARCH_SRC_DIR)
 
 # entry.S must be first, so that it's the first code in the text segment!!!
 #
 
 # entry.S must be first, so that it's the first code in the text segment!!!
 #
@@ -15,6 +16,8 @@ KERN_ARCH_SRCFILES := $(KERN_ARCH_SRC_DIR)/entry.S \
                       $(KERN_ARCH_SRC_DIR)/cpuinfo.c \
                       $(KERN_ARCH_SRC_DIR)/console.c \
                       $(KERN_ARCH_SRC_DIR)/smp_boot.c \
                       $(KERN_ARCH_SRC_DIR)/cpuinfo.c \
                       $(KERN_ARCH_SRC_DIR)/console.c \
                       $(KERN_ARCH_SRC_DIR)/smp_boot.c \
+                      $(KERN_ARCH_SRC_DIR)/colored_caches.c \
+                      $(KERN_ARCH_SRC_DIR)/page_alloc.c \
                       $(KERN_ARCH_SRC_DIR)/pmap.c \
                       $(KERN_ARCH_SRC_DIR)/trapentry.S \
                       $(KERN_ARCH_SRC_DIR)/trap.c \
                       $(KERN_ARCH_SRC_DIR)/pmap.c \
                       $(KERN_ARCH_SRC_DIR)/trapentry.S \
                       $(KERN_ARCH_SRC_DIR)/trap.c \
diff --git a/kern/arch/i386/colored_caches.c b/kern/arch/i386/colored_caches.c
new file mode 100644 (file)
index 0000000..ec42145
--- /dev/null
@@ -0,0 +1,26 @@
+/* Copyright (c) 2009 The Regents of the University  of California. 
+ * See the COPYRIGHT files at the top of this source tree for full 
+ * license information.
+ * 
+ * Kevin Klues <klueska@cs.berkeley.edu>    
+ */
+
+#include <colored_caches.h>
+
+// Global variables
+cache_t l1,l2,l3;
+available_caches_t available_caches;
+
+/************** Cache Related Functions  *****************/
+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);
+       init_cache_properties(&l2,  256,  8, 64);
+       init_cache_properties(&l3, 8192, 16, 64);
+       available_caches.l1 = TRUE;
+       available_caches.l2 = TRUE;
+       available_caches.l3 = TRUE;
+}
diff --git a/kern/arch/i386/colored_page_alloc.h b/kern/arch/i386/colored_page_alloc.h
new file mode 100644 (file)
index 0000000..4aa5813
--- /dev/null
@@ -0,0 +1,51 @@
+/*
+ * Copyright (c) 2009 The Regents of the University  of California.  
+ * See the COPYRIGHT files at the top of this source tree for full 
+ * license information.
+ */
+/**
+ * @author Kevin Klues <klueska@cs.berkeley.edu>
+ */
+#ifndef ROS_KERN_ARCH_COLORED_PAGE_ALLOC_H
+#define ROS_KERN_ARCH_COLORED_PAGE_ALLOC_H
+
+/********** Page Coloring Related Macros ************/
+// Define these to make sure that each level of the cache
+// is initialized and managed properly
+#define DECLARE_CACHE_COLORED_PAGE_LINKS()                    \
+       DECLARE_CACHE_COLORED_PAGE_LINK(l1)                       \
+       DECLARE_CACHE_COLORED_PAGE_LINK(l2)                       \
+       DECLARE_CACHE_COLORED_PAGE_LINK(l3)
+
+#define DECLARE_CACHE_COLORED_PAGE_FREE_LISTS()               \
+       DECLARE_CACHE_COLORED_PAGE_FREE_LIST(l1)                  \
+       DECLARE_CACHE_COLORED_PAGE_FREE_LIST(l2)                  \
+       DECLARE_CACHE_COLORED_PAGE_FREE_LIST(l3)
+       
+#define DECLARE_EXTERN_CACHE_COLORED_PAGE_FREE_LISTS()        \
+       DECLARE_EXTERN_CACHE_COLORED_PAGE_FREE_LIST(l1)           \
+       DECLARE_EXTERN_CACHE_COLORED_PAGE_FREE_LIST(l2)           \
+       DECLARE_EXTERN_CACHE_COLORED_PAGE_FREE_LIST(l3)
+       
+#define DECLARE_CACHE_COLORED_PAGE_ALLOC_FUNCTIONS()          \
+       DECLARE_CACHE_COLORED_PAGE_ALLOC_FUNCTION(l1)             \
+       DECLARE_CACHE_COLORED_PAGE_ALLOC_FUNCTION(l2)             \
+       DECLARE_CACHE_COLORED_PAGE_ALLOC_FUNCTION(l3)
+
+#define INIT_CACHE_COLORED_PAGE_FREE_LISTS()                  \
+       INIT_CACHE_COLORED_PAGE_FREE_LIST(l1)                     \
+       INIT_CACHE_COLORED_PAGE_FREE_LIST(l2)                     \
+       INIT_CACHE_COLORED_PAGE_FREE_LIST(l3)
+
+#define REMOVE_CACHE_COLORING_PAGE_FROM_FREE_LISTS(page)      \
+       REMOVE_CACHE_COLORING_PAGE_FROM_FREE_LIST(page, l1)       \
+       REMOVE_CACHE_COLORING_PAGE_FROM_FREE_LIST(page, l2)       \
+       REMOVE_CACHE_COLORING_PAGE_FROM_FREE_LIST(page, l3)
+       
+#define INSERT_CACHE_COLORING_PAGE_ONTO_FREE_LISTS(page)      \
+       INSERT_CACHE_COLORING_PAGE_ONTO_FREE_LIST(page, l1)       \
+       INSERT_CACHE_COLORING_PAGE_ONTO_FREE_LIST(page, l2)       \
+       INSERT_CACHE_COLORING_PAGE_ONTO_FREE_LIST(page, l3)
+
+#endif // CACHE_COLORING_PAGE_ALLOC_H
diff --git a/kern/arch/i386/page_alloc.c b/kern/arch/i386/page_alloc.c
new file mode 100644 (file)
index 0000000..610de7e
--- /dev/null
@@ -0,0 +1,69 @@
+/* Copyright (c) 2009 The Regents of the University  of California. 
+ * See the COPYRIGHT files at the top of this source tree for full 
+ * license information.
+ * 
+ * Kevin Klues <klueska@cs.berkeley.edu>    
+ */
+#ifdef __DEPUTY__
+#pragma nodeputy
+#endif
+
+#include <sys/queue.h>
+#include <page_alloc.h>
+#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
+
+/*
+ * Initialize the memory free lists.
+ * After this point, ONLY use the functions below
+ * to allocate and deallocate physical memory via the 
+ * page_free_lists. 
+ */
+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. 
+       //  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...)
+       //  2) Mark the rest of base memory as free.
+       //  3) Then comes the IO hole [IOPHYSMEM, EXTPHYSMEM).
+       //     Mark it as in use so that it can never be allocated.      
+       //  4) Then extended memory [EXTPHYSMEM, ...).
+       //     Some of it is in use, some is free.
+       int i;
+       physaddr_t physaddr_after_kernel = PADDR(ROUNDUP(boot_freemem, PGSIZE));
+
+       pages[0].page_ref = 1;
+       // alloc the second page, since we will need it later to init the other cores
+       // probably need to be smarter about what page we use (make this dynamic) TODO
+       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]);
+       }
+       for (i = PPN(IOPHYSMEM); i < PPN(EXTPHYSMEM); i++) {
+               pages[i].page_ref = 1;
+       }
+       for (i = PPN(EXTPHYSMEM); i < PPN(physaddr_after_kernel); i++) {
+               pages[i].page_ref = 1;
+       }
+       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]);
+       }
+       // this block out all memory above maxaddrpa.  will need another mechanism
+       // to allocate and map these into the kernel address space
+       for (i = PPN(maxaddrpa); i < npages; i++) {
+               pages[i].page_ref = 1;
+       }
+}
\ No newline at end of file
index c988786..4a91782 100644 (file)
@@ -5,6 +5,7 @@
 #include <arch/apic.h>
 
 #include <ros/error.h>
 #include <arch/apic.h>
 
 #include <ros/error.h>
+#include <sys/queue.h>
 
 #include <atomic.h>
 #include <string.h>
 
 #include <atomic.h>
 #include <string.h>
 #include <kclock.h>
 #include <env.h>
 #include <stdio.h>
 #include <kclock.h>
 #include <env.h>
 #include <stdio.h>
+#include <kmalloc.h>
+#include <page_alloc.h>
 
 // These variables are set in i386_vm_init()
 pde_t* boot_pgdir;             // Virtual address of boot time page directory
 physaddr_t boot_cr3;           // Physical address of boot time page directory
 
 // These variables are set in i386_vm_init()
 pde_t* boot_pgdir;             // Virtual address of boot time page directory
 physaddr_t boot_cr3;           // Physical address of boot time page directory
-char *boot_freemem_base;
-char* boot_freemem;            // Pointer to next byte of free mem
 
 
-page_t *pages;         // Virtual address of physical page array
-page_list_t page_free_list;    // Free list of physical pages
-
-extern env_t *envs;
+// Global variables
+page_t *pages = NULL;          // Virtual address of physical page array
 
 // Global descriptor table.
 //
 
 // Global descriptor table.
 //
@@ -358,17 +357,6 @@ vm_init(void)
                         PTE_PCD | PTE_PWT | PTE_W | PTE_G);
 
        //////////////////////////////////////////////////////////////////////
                         PTE_PCD | PTE_PWT | PTE_W | PTE_G);
 
        //////////////////////////////////////////////////////////////////////
-       // Make 'pages' point to an array of size 'npage' of 'struct Page'.
-       // The kernel uses this structure to keep track of physical pages;
-       // 'npage' equals the number of physical pages in memory.  
-       // No longer mapping UPAGES into the address space
-       
-       // round up to the nearest page
-       size_t page_array_size = ROUNDUP(npage*sizeof(page_t), PGSIZE);
-       pages = /*(page_t *COUNT(npage))*/boot_calloc(page_array_size, 1, PGSIZE);
-       //memset(pages, 0, page_array_size);
-
-       //////////////////////////////////////////////////////////////////////
        // Make 'envs' point to an array of size 'NENV' of 'env_t'.
        // No longer mapping ENVS into the address space
        
        // Make 'envs' point to an array of size 'NENV' of 'env_t'.
        // No longer mapping ENVS into the address space
        
@@ -438,6 +426,29 @@ vm_init(void)
        tlb_flush_global();
 }
 
        tlb_flush_global();
 }
 
+// --------------------------------------------------------------
+// Tracking of physical pages.
+// The 'pages' array has one 'page_t' entry per physical page.
+// Pages are reference counted, and free pages are kept on a linked list.
+// --------------------------------------------------------------
+
+// Initialize page structure and memory free list.
+void page_init(void)
+{
+       // First, make 'pages' point to an array of size 'npages' of 
+       // type 'page_t'.
+       // The kernel uses this structure to keep track of physical pages;
+       // 'npages' equals the number of physical pages in memory.  
+       // round up to the nearest page
+       size_t page_array_size = ROUNDUP(npages*sizeof(page_t), PGSIZE);
+       pages = (page_t*)boot_alloc(page_array_size, PGSIZE);
+       memset(pages, 0, page_array_size);
+       
+       // Now initilaize everything so pages can start to be alloced and freed
+       // from the memory free list
+       page_alloc_init();
+}
+
 //
 // Checks that the kernel part of virtual address space
 // has been setup roughly correctly(by i386_vm_init()).
 //
 // Checks that the kernel part of virtual address space
 // has been setup roughly correctly(by i386_vm_init()).
@@ -568,63 +579,6 @@ get_vaperms(pde_t *COUNT(NPDENTRIES) pgdir, uintptr_t va)
                return 0;
        return PGOFF(*pde & *pte) + PTE_PS & (*pde | *pte);
 }
                return 0;
        return PGOFF(*pde & *pte) + PTE_PS & (*pde | *pte);
 }
-               
-// --------------------------------------------------------------
-// Tracking of physical pages.
-// The 'pages' array has one 'page_t' entry per physical page.
-// Pages are reference counted, and free pages are kept on a linked list.
-// --------------------------------------------------------------
-
-//  
-// Initialize page structure and memory free list.
-// After this point, ONLY use the functions below
-// to allocate and deallocate physical memory via the page_free_list,
-// and NEVER use boot_alloc() or the related boot-time functions above.
-//
-void
-page_init(void)
-{
-       // The example code here marks all pages as free.
-       // However this is not truly the case.  What memory is free?
-       //  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...)
-       //  2) Mark the rest of base memory as free.
-       //  3) Then comes the IO hole [IOPHYSMEM, EXTPHYSMEM).
-       //     Mark it as in use so that it can never be allocated.      
-       //  4) Then extended memory [EXTPHYSMEM, ...).
-       //     Some of it is in use, some is free. Where is the kernel?
-       //     Which pages are used for page tables and other data structures?
-       //
-       // Change the code to reflect this.
-       int i;
-       physaddr_t physaddr_after_kernel = PADDR(ROUNDUP((unsigned int)boot_freemem, PGSIZE));
-       LIST_INIT(&page_free_list);
-
-       pages[0].pp_ref = 1;
-       // alloc the second page, since we will need it later to init the other cores
-       // probably need to be smarter about what page we use (make this dynamic) TODO
-       pages[1].pp_ref = 1;
-       for (i = 2; i < PPN(IOPHYSMEM); i++) {
-               pages[i].pp_ref = 0;
-               LIST_INSERT_HEAD(&page_free_list, &pages[i], pp_link);
-       }
-       for (i = PPN(IOPHYSMEM); i < PPN(EXTPHYSMEM); i++) {
-               pages[i].pp_ref = 1;
-       }
-       for (i = PPN(EXTPHYSMEM); i < PPN(physaddr_after_kernel); i++) {
-               pages[i].pp_ref = 1;
-       }
-       for (i = PPN(physaddr_after_kernel); i < PPN(maxaddrpa); i++) {
-               pages[i].pp_ref = 0;
-               LIST_INSERT_HEAD(&page_free_list, &pages[i], pp_link);
-       }
-       // this block out all memory above maxaddrpa.  will need another mechanism
-       // to allocate and map these into the kernel address space
-       for (i = PPN(maxaddrpa); i < npage; i++) {
-               pages[i].pp_ref = 1;
-       }
-}
 
 /* 
  * Remove the second level page table associated with virtual address va.
 
 /* 
  * Remove the second level page table associated with virtual address va.
@@ -686,7 +640,7 @@ pgdir_walk(pde_t *pgdir, const void *SNT va, int create)
        }
        if (page_alloc(&new_table))
                return NULL;
        }
        if (page_alloc(&new_table))
                return NULL;
-       new_table->pp_ref = 1;
+       new_table->page_ref = 1;
        memset(page2kva(new_table), 0, PGSIZE);
        *the_pde = (pde_t)page2pa(new_table) | PTE_P | PTE_W | PTE_U;
        return &((pde_t*COUNT(NPTENTRIES))KADDR(PTE_ADDR(*the_pde)))[PTX(va)];
        memset(page2kva(new_table), 0, PGSIZE);
        *the_pde = (pde_t)page2pa(new_table) | PTE_P | PTE_W | PTE_U;
        return &((pde_t*COUNT(NPTENTRIES))KADDR(PTE_ADDR(*the_pde)))[PTX(va)];
@@ -749,13 +703,13 @@ page_check(void)
        }
        assert(PTE_ADDR(boot_pgdir[0]) == page2pa(pp0));
        assert(check_va2pa(boot_pgdir, 0x0) == page2pa(pp1));
        }
        assert(PTE_ADDR(boot_pgdir[0]) == page2pa(pp0));
        assert(check_va2pa(boot_pgdir, 0x0) == page2pa(pp1));
-       assert(pp1->pp_ref == 1);
-       assert(pp0->pp_ref == 1);
+       assert(pp1->page_ref == 1);
+       assert(pp0->page_ref == 1);
 
        // should be able to map pp2 at PGSIZE because pp0 is already allocated for page table
        assert(page_insert(boot_pgdir, pp2, (void*SNT) PGSIZE, 0) == 0);
        assert(check_va2pa(boot_pgdir, PGSIZE) == page2pa(pp2));
 
        // should be able to map pp2 at PGSIZE because pp0 is already allocated for page table
        assert(page_insert(boot_pgdir, pp2, (void*SNT) PGSIZE, 0) == 0);
        assert(check_va2pa(boot_pgdir, PGSIZE) == page2pa(pp2));
-       assert(pp2->pp_ref == 1);
+       assert(pp2->page_ref == 1);
 
        // Make sure that pgdir_walk returns a pointer to the pte and
        // not the table or some other garbage
 
        // Make sure that pgdir_walk returns a pointer to the pte and
        // not the table or some other garbage
@@ -770,7 +724,7 @@ page_check(void)
        // should be able to map pp2 at PGSIZE because it's already there
        assert(page_insert(boot_pgdir, pp2, (void*SNT) PGSIZE, PTE_U) == 0);
        assert(check_va2pa(boot_pgdir, PGSIZE) == page2pa(pp2));
        // should be able to map pp2 at PGSIZE because it's already there
        assert(page_insert(boot_pgdir, pp2, (void*SNT) PGSIZE, PTE_U) == 0);
        assert(check_va2pa(boot_pgdir, PGSIZE) == page2pa(pp2));
-       assert(pp2->pp_ref == 1);
+       assert(pp2->page_ref == 1);
 
        // Make sure that we actually changed the permission on pp2 when we re-mapped it
        {
 
        // Make sure that we actually changed the permission on pp2 when we re-mapped it
        {
@@ -792,8 +746,8 @@ page_check(void)
        assert(check_va2pa(boot_pgdir, 0) == page2pa(pp1));
        assert(check_va2pa(boot_pgdir, PGSIZE) == page2pa(pp1));
        // ... and ref counts should reflect this
        assert(check_va2pa(boot_pgdir, 0) == page2pa(pp1));
        assert(check_va2pa(boot_pgdir, PGSIZE) == page2pa(pp1));
        // ... and ref counts should reflect this
-       assert(pp1->pp_ref == 2);
-       assert(pp2->pp_ref == 0);
+       assert(pp1->page_ref == 2);
+       assert(pp2->page_ref == 0);
 
        // pp2 should be returned by page_alloc
        assert(page_alloc(&pp) == 0 && pp == pp2);
 
        // pp2 should be returned by page_alloc
        assert(page_alloc(&pp) == 0 && pp == pp2);
@@ -802,15 +756,15 @@ page_check(void)
        page_remove(boot_pgdir, 0x0);
        assert(check_va2pa(boot_pgdir, 0x0) == ~0);
        assert(check_va2pa(boot_pgdir, PGSIZE) == page2pa(pp1));
        page_remove(boot_pgdir, 0x0);
        assert(check_va2pa(boot_pgdir, 0x0) == ~0);
        assert(check_va2pa(boot_pgdir, PGSIZE) == page2pa(pp1));
-       assert(pp1->pp_ref == 1);
-       assert(pp2->pp_ref == 0);
+       assert(pp1->page_ref == 1);
+       assert(pp2->page_ref == 0);
 
        // unmapping pp1 at PGSIZE should free it
        page_remove(boot_pgdir, (void*SNT) PGSIZE);
        assert(check_va2pa(boot_pgdir, 0x0) == ~0);
        assert(check_va2pa(boot_pgdir, PGSIZE) == ~0);
 
        // unmapping pp1 at PGSIZE should free it
        page_remove(boot_pgdir, (void*SNT) PGSIZE);
        assert(check_va2pa(boot_pgdir, 0x0) == ~0);
        assert(check_va2pa(boot_pgdir, PGSIZE) == ~0);
-       assert(pp1->pp_ref == 0);
-       assert(pp2->pp_ref == 0);
+       assert(pp1->page_ref == 0);
+       assert(pp2->page_ref == 0);
 
        // so it should be returned by page_alloc
        assert(page_alloc(&pp) == 0 && pp == pp1);
 
        // so it should be returned by page_alloc
        assert(page_alloc(&pp) == 0 && pp == pp1);
@@ -821,8 +775,8 @@ page_check(void)
        // forcibly take pp0 back
        assert(PTE_ADDR(boot_pgdir[0]) == page2pa(pp0));
        boot_pgdir[0] = 0;
        // forcibly take pp0 back
        assert(PTE_ADDR(boot_pgdir[0]) == page2pa(pp0));
        boot_pgdir[0] = 0;
-       assert(pp0->pp_ref == 1);
-       pp0->pp_ref = 0;
+       assert(pp0->page_ref == 1);
+       pp0->page_ref = 0;
 
        // Catch invalid pointer addition in pgdir_walk - i.e. pgdir + PDX(va)
        {
 
        // Catch invalid pointer addition in pgdir_walk - i.e. pgdir + PDX(va)
        {
@@ -836,7 +790,7 @@ page_check(void)
 
          // Clean up again
          boot_pgdir[PDX(va)] = 0;
 
          // Clean up again
          boot_pgdir[PDX(va)] = 0;
-         pp0->pp_ref = 0;
+         pp0->page_ref = 0;
        }
 
        // give free list back
        }
 
        // give free list back
index c9775bf..d842b15 100644 (file)
@@ -89,7 +89,7 @@ void smp_boot(void)
        // Allocate a stack for the cores starting up.  One for all, must share
        if (page_alloc(&smp_stack))
                panic("No memory for SMP boot stack!");
        // Allocate a stack for the cores starting up.  One for all, must share
        if (page_alloc(&smp_stack))
                panic("No memory for SMP boot stack!");
-       smp_stack->pp_ref++;
+       page_incref(smp_stack);
        smp_stack_top = (uintptr_t)(page2kva(smp_stack) + PGSIZE);
 
        // Start the IPI process (INIT, wait, SIPI, wait, SIPI, wait)
        smp_stack_top = (uintptr_t)(page2kva(smp_stack) + PGSIZE);
 
        // Start the IPI process (INIT, wait, SIPI, wait, SIPI, wait)
@@ -193,7 +193,7 @@ uint32_t smp_main(void)
        page_t *my_stack;
        if (page_alloc(&my_stack))
                panic("Unable to alloc a per-core stack!");
        page_t *my_stack;
        if (page_alloc(&my_stack))
                panic("Unable to alloc a per-core stack!");
-       my_stack->pp_ref++;
+       page_incref(my_stack);
        memset(page2kva(my_stack), 0, PGSIZE);
 
        // Set up a gdt / gdt_pd for this core, stored at the top of the stack
        memset(page2kva(my_stack), 0, PGSIZE);
 
        // Set up a gdt / gdt_pd for this core, stored at the top of the stack
index 649ddf5..28bc462 100644 (file)
 // Represents true-or-false values
 typedef int bool;
 
 // Represents true-or-false values
 typedef int bool;
 
+#define NUM_ADDR_BITS 32
+#define MAX_VADDR     ((uint64_t)(~0) >> (64-NUM_ADDR_BITS))
+
+//Constants for byte sizes
+#define ONE_KILOBYTE  (1L<<10)
+#define ONE_MEGABYTE  (1L<<20)
+#define ONE_GIGABYTE  (1L<<30)
+
 // Explicitly-sized versions of integer types
 typedef __signed char int8_t;
 typedef unsigned char uint8_t;
 // Explicitly-sized versions of integer types
 typedef __signed char int8_t;
 typedef unsigned char uint8_t;
@@ -82,7 +90,6 @@ typedef int32_t off_t;
        (typeof(a)) (ROUNDDOWN((uint32_t) (a) + __n - 1, __n)); \
 })
 
        (typeof(a)) (ROUNDDOWN((uint32_t) (a) + __n - 1, __n)); \
 })
 
-
 // Round down to the nearest multiple of n
 #define PTRROUNDDOWN(a, n)                                             \
 ({                                                             \
 // Round down to the nearest multiple of n
 #define PTRROUNDDOWN(a, n)                                             \
 ({                                                             \
@@ -96,6 +103,14 @@ typedef int32_t off_t;
        (typeof(a)) (PTRROUNDDOWN((char *) (a) + __n - 1, __n));        \
 })
 
        (typeof(a)) (PTRROUNDDOWN((char *) (a) + __n - 1, __n));        \
 })
 
+// Return the integer logarithm of the value provided rounded up
+static inline uint32_t LOG2(uint32_t value)
+{
+    uint32_t l = 0;
+    while( (value >> l) > 1 ) ++l;
+    return l;
+}
+
 // Return the offset of 'member' relative to the beginning of a struct type
 #ifndef offsetof
 #define offsetof(type, member)  ((size_t) (&((type*)0)->member))
 // Return the offset of 'member' relative to the beginning of a struct type
 #ifndef offsetof
 #define offsetof(type, member)  ((size_t) (&((type*)0)->member))
index 5357327..a923cd0 100644 (file)
@@ -5,6 +5,7 @@
 #
 
 KERN_ARCH_SRC_DIR = $(KERN_DIR)/arch/$(TARGET_ARCH)
 #
 
 KERN_ARCH_SRC_DIR = $(KERN_DIR)/arch/$(TARGET_ARCH)
+OBJDIRS += $(KERN_ARCH_SRC_DIR)
 
 # entry.S must be first, so that it's the first code in the text segment!!!
 #
 
 # entry.S must be first, so that it's the first code in the text segment!!!
 #
diff --git a/kern/include/colored_caches.h b/kern/include/colored_caches.h
new file mode 100644 (file)
index 0000000..5ebf78a
--- /dev/null
@@ -0,0 +1,60 @@
+/* Copyright (c) 2009 The Regents of the University  of California. 
+ * See the COPYRIGHT files at the top of this source tree for full 
+ * license information.
+ * 
+ * Kevin Klues <klueska@cs.berkeley.edu>    
+ */
+#ifndef ROS_KERN_COLORED_CACHES_H
+#define ROS_KERN_COLORED_CACHES_H
+
+#include <arch/types.h>
+
+/****************** Cache Structures ********************/
+typedef struct Cache {
+       size_t wa;
+       size_t sz_k;
+       size_t clsz;
+       
+       //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;
+} available_caches_t;
+
+/******** Externally visible global variables ************/
+extern cache_t l1,l2,l3;
+extern available_caches_t available_caches;
+
+/************** Cache Related Functions  *****************/
+void cache_init();
+void init_cache_properties(cache_t *c, size_t sz_k, size_t wa, size_t clsz);
+size_t get_page_color(uintptr_t page, cache_t *c);
+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);
+
+#endif // ROS_KERN_COLORED_CACHES_H
\ No newline at end of file
diff --git a/kern/include/colored_page_alloc.h b/kern/include/colored_page_alloc.h
new file mode 100644 (file)
index 0000000..91ddbae
--- /dev/null
@@ -0,0 +1,68 @@
+/*
+ * Copyright (c) 2009 The Regents of the University  of California.  
+ * See the COPYRIGHT files at the top of this source tree for full 
+ * license information.
+ */
+/**
+ * @author Kevin Klues <klueska@cs.berkeley.edu>
+ */
+#ifndef ROS_KERN_COLORED_PAGE_ALLOC_H
+#define ROS_KERN_COLORED_PAGE_ALLOC_H
+
+#include <colored_caches.h>
+#include <arch/colored_page_alloc.h>
+#include <stdio.h>
+       
+#define DECLARE_CACHE_COLORED_PAGE_LINK(_cache)                               \
+       page_list_entry_t _cache##_cache_colored_page_link;
+       
+#define DECLARE_CACHE_COLORED_PAGE_FREE_LIST(_cache)                          \
+       page_list_t *COUNT(npages) _cache##_cache_colored_page_list = NULL;
+       
+#define DECLARE_EXTERN_CACHE_COLORED_PAGE_FREE_LIST(_cache)                   \
+       extern page_list_t *COUNT(npages) _cache##_cache_colored_page_list;
+       
+#define DECLARE_CACHE_COLORED_PAGE_ALLOC_FUNCTION(_cache)                     \
+error_t _cache##_page_alloc(page_t** page, size_t color)                      \
+{                                                                             \
+       /*      TODO: Put a lock around this */                                       \
+       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;                                                           \
+}
+
+#define INIT_CACHE_COLORED_PAGE_FREE_LIST(_cache)                             \
+{                                                                             \
+       if(available_caches._cache == TRUE) {                                     \
+           uint8_t num_colors = get_cache_num_page_colors(&(_cache));            \
+           size_t list_size = num_colors*sizeof(page_list_t);                    \
+           _cache##_cache_colored_page_list                                      \
+              = (page_list_t*) boot_alloc(list_size, PGSIZE);                    \
+               for(int i=0; i<num_colors; i++) {                                     \
+                       LIST_INIT(&(_cache##_cache_colored_page_list[i]));                \
+               }                                                                     \
+       }                                                                         \
+}
+
+#define REMOVE_CACHE_COLORING_PAGE_FROM_FREE_LIST(_page, _cache)              \
+       if(available_caches._cache == TRUE)                                       \
+               LIST_REMOVE(*(_page), _cache##_cache_colored_page_link);
+
+
+#define INSERT_CACHE_COLORING_PAGE_ONTO_FREE_LIST(_page, _cache)              \
+       if(available_caches._cache == TRUE) {                                     \
+               LIST_INSERT_HEAD(                                                     \
+                  &(_cache##_cache_colored_page_list                                 \
+                        [get_page_color(page2ppn((_page)), &(_cache))]),             \
+                  (_page),                                                           \
+                  _cache##_cache_colored_page_link                                   \
+               );                                                                    \
+       }
+
+#endif // ROS_KERN_COLORED_PAGE_ALLOC_H
index 902f3e9..29a88d5 100644 (file)
@@ -5,13 +5,14 @@
  * Kevin Klues <klueska@cs.berkeley.edu>    
  */
 
  * Kevin Klues <klueska@cs.berkeley.edu>    
  */
 
-#ifndef KMALLOC_H
-#define KMALLOC_H
+#ifndef ROS_KERN_KMALLOC_H
+#define ROS_KERN_KMALLOC_H
 
 #include <arch/types.h>
 
 void  kmalloc_init();
 
 #include <arch/types.h>
 
 void  kmalloc_init();
-void* kmalloc(size_t size, int flags);
-void  kfree(void*COUNT(PGSIZE) addr);
+void* (DALLOC(size) boot_alloc)(uint32_t size, uint32_t align);
+void* (DALLOC(size) kmalloc)(size_t size, int flags);
+void  (DFREE(addr) kfree)(void *addr);
 
 
-#endif //KMALLOC_H
\ No newline at end of file
+#endif //ROS_KERN_KMALLOC_H
\ No newline at end of file
index fc7e055..b34a5b4 100644 (file)
@@ -5,11 +5,11 @@
 
 #include <arch/types.h>
 
 
 #include <arch/types.h>
 
-extern physaddr_t maxpa;// Maximum physical address
-extern physaddr_t maxaddrpa;    // Maximum directly addressable physical address
+extern physaddr_t maxpa;        // Maximum physical address in the system
+extern physaddr_t maxaddrpa;    // Maximum addressable physical address
 extern void *SNT maxaddrpa_ptr; // same as maxaddrpa, but ptr type for annotations
 extern void *SNT maxaddrpa_ptr; // same as maxaddrpa, but ptr type for annotations
-extern size_t npage;   // Amount of physical memory (in pages)
-extern size_t naddrpage;       // Amount of addressable physical memory (in pages)
+extern size_t npages;           // Total number of physical memory pages
+extern size_t naddrpages;          // Number of addressable physical memory pages
 
 #endif /* !__ASSEMBLER__ */
 
 
 #endif /* !__ASSEMBLER__ */
 
diff --git a/kern/include/page_alloc.h b/kern/include/page_alloc.h
new file mode 100644 (file)
index 0000000..b60679f
--- /dev/null
@@ -0,0 +1,49 @@
+/* Copyright (c) 2009 The Regents of the University  of California. 
+ * See the COPYRIGHT files at the top of this source tree for full 
+ * license information.
+ * 
+ * Kevin Klues <klueska@cs.berkeley.edu>    
+ */
+#ifndef PAGE_ALLOC_H
+#define PAGE_ALLOC_H
+
+#include <sys/queue.h>
+#include <ros/error.h>
+#include <arch/mmu.h>
+#include <colored_page_alloc.h>
+
+/****************** Page Structures *********************/
+struct Page;
+typedef size_t ppn_t;
+typedef struct Page page_t;
+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();
+       
+       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();
+
+/*************** Functional Interface *******************/
+void page_alloc_init(void);
+error_t page_alloc(page_t *SAFE *page);
+error_t page_alloc_specific(page_t *SAFE *page, size_t ppn);
+error_t l1_page_alloc(page_t *SAFE *page, size_t color);
+error_t l2_page_alloc(page_t *SAFE *page, size_t color);
+error_t l3_page_alloc(page_t *SAFE *page, size_t color);
+error_t page_free(page_t *SAFE page);
+void page_incref(page_t *SAFE page);
+void page_decref(page_t *SAFE page);
+void page_refset(page_t *SAFE page, size_t val);
+int page_is_free(size_t ppn);
+
+#endif //PAGE_ALLOC_H
+
index 3d9e34d..c6d4569 100644 (file)
@@ -7,11 +7,13 @@
 #endif
 
 #include <ros/memlayout.h>
 #endif
 
 #include <ros/memlayout.h>
+#include <sys/queue.h>
 #include <multiboot.h>
 #include <atomic.h>
 #include <process.h>
 #include <assert.h>
 #include <multiboot.h>
 #include <atomic.h>
 #include <process.h>
 #include <assert.h>
-#include <sys/queue.h>
+#include <page_alloc.h>
+#include <multiboot.h>
 
 /* This macro takes a kernel virtual address -- an address that points above
  * KERNBASE, where the machine's maximum 256MB of physical memory is mapped --
 
 /* This macro takes a kernel virtual address -- an address that points above
  * KERNBASE, where the machine's maximum 256MB of physical memory is mapped --
 ({                                                             \
        physaddr_t __m_pa = (pa);                               \
        size_t __m_ppn = PPN(__m_pa);                           \
 ({                                                             \
        physaddr_t __m_pa = (pa);                               \
        size_t __m_ppn = PPN(__m_pa);                           \
-       if (__m_ppn >= npage                                  \
+       if (__m_ppn >= npages)                                  \
                warn("KADDR called with invalid pa %08lx", __m_pa);\
        (void*TRUSTED) (__m_pa + KERNBASE);                             \
 })
 
                warn("KADDR called with invalid pa %08lx", __m_pa);\
        (void*TRUSTED) (__m_pa + KERNBASE);                             \
 })
 
-/*
- * Page descriptor structures, mapped at UPAGES.
- * Read/write to the kernel, read-only to user programs.
- *
- * Each Page describes one physical page.
- * You can map a Page * to the corresponding physical address
- * with page2pa() in kern/pmap.h.
- */
-
-struct Page;
-typedef struct Page page_t;
-
-LIST_HEAD(page_list, Page);
-typedef struct page_list page_list_t;
-typedef LIST_ENTRY(Page) page_list_entry_t;
-
-struct Page {
-       page_list_entry_t pp_link;      /* free list link */
-       size_t num_cons_links;
-
-       // pp_ref is the count of pointers (usually in page table entries)
-       // to this page, for pages allocated using page_alloc.
-       // Pages allocated at boot time using pmap.c's
-       // boot_alloc do not have valid reference count fields.
-
-       uint16_t pp_ref;
-};
-
-
 extern char (SNT bootstacktop)[], (SNT bootstack)[];
 
 extern char (SNT bootstacktop)[], (SNT bootstack)[];
 
-extern page_t *COUNT(npage) pages;
-extern size_t npage;
+extern page_t *COUNT(npages) pages; // List of pysical pages
 
 extern physaddr_t boot_cr3;
 extern pde_t *COUNT(NPDENTRIES) boot_pgdir;
 
 
 extern physaddr_t boot_cr3;
 extern pde_t *COUNT(NPDENTRIES) boot_pgdir;
 
-extern char (SNT end)[];
 extern char*BND(end, maxaddrpa_ptr + IVY_KERNBASE) boot_freemem;
 extern char*BND(end, maxaddrpa_ptr + IVY_KERNBASE) boot_freemem;
-extern page_list_t page_free_list;
-
-void*  (DALLOC(n) boot_alloc)(uint32_t n, uint32_t align);
-void*  (DALLOC(_n*sz) boot_calloc)(uint32_t _n, size_t sz, uint32_t align);
 
 void   multiboot_detect_memory(multiboot_info_t *COUNT(1) mbi);
 void   multiboot_print_memory_map(multiboot_info_t *COUNT(1) mbi);
 
 void   multiboot_detect_memory(multiboot_info_t *COUNT(1) mbi);
 void   multiboot_print_memory_map(multiboot_info_t *COUNT(1) mbi);
@@ -88,10 +55,6 @@ void vm_init(void);
 
 void   page_init(void);
 void   page_check(void);
 
 void   page_init(void);
 void   page_check(void);
-int        page_alloc(page_t *COUNT(1) *pp_store);
-int     page_alloc_specific(page_t *COUNT(1) *pp_store, size_t ppn);
-void   page_free(page_t *COUNT(1) pp);
-int            page_is_free(size_t ppn);
 int        page_insert(pde_t *COUNT(NPDENTRIES) pgdir, page_t *pp, void *SNT va, int perm);
 void*COUNT(PGSIZE) page_insert_in_range(pde_t *COUNT(NPDENTRIES) pgdir, page_t *pp, 
                              void *SNT vab, void *SNT vae, int perm);
 int        page_insert(pde_t *COUNT(NPDENTRIES) pgdir, page_t *pp, void *SNT va, int perm);
 void*COUNT(PGSIZE) page_insert_in_range(pde_t *COUNT(NPDENTRIES) pgdir, page_t *pp, 
                              void *SNT vab, void *SNT vae, int perm);
@@ -116,11 +79,13 @@ size_t user_mem_strlcpy(env_t *env, char *NT COUNT(len - 1),
 error_t
 memcpy_from_user(env_t* env, void* COUNT(len) dest,
                  const void *DANGEROUS va, size_t len);
 error_t
 memcpy_from_user(env_t* env, void* COUNT(len) dest,
                  const void *DANGEROUS va, size_t len);
+                 
+pte_t *pgdir_walk(pde_t *COUNT(NPDENTRIES) pgdir, const void *SNT va, int create);                 
 
 
-static inline page_t*COUNT(1) ppn2page(size_t ppn)
+static inline page_t *SAFE ppn2page(size_t ppn)
 {
 {
-       if( ppn >= npage )
-               warn("ppn2page called with ppn (%08u) larger than npage", ppn);
+       if( ppn >= npages )
+               warn("ppn2page called with ppn (%08u) larger than npages", ppn);
        return &(pages[ppn]);
 }
 
        return &(pages[ppn]);
 }
 
@@ -136,8 +101,8 @@ static inline physaddr_t page2pa(page_t *pp)
 
 static inline page_t*COUNT(1) pa2page(physaddr_t pa)
 {
 
 static inline page_t*COUNT(1) pa2page(physaddr_t pa)
 {
-       if (PPN(pa) >= npage)
-               warn("pa2page called with pa (0x%08x) larger than npage", pa);
+       if (PPN(pa) >= npages)
+               warn("pa2page called with pa (0x%08x) larger than npages", pa);
        return &pages[PPN(pa)];
 }
 
        return &pages[PPN(pa)];
 }
 
@@ -156,6 +121,4 @@ static inline page_t* kva2page(void* addr)
        return pa2page(PADDR(addr));
 }
 
        return pa2page(PADDR(addr));
 }
 
-pte_t *pgdir_walk(pde_t *COUNT(NPDENTRIES) pgdir, const void *SNT va, int create);
-
 #endif /* !ROS_KERN_PMAP_H */
 #endif /* !ROS_KERN_PMAP_H */
index 7c58d27..91b05dd 100644 (file)
@@ -11,6 +11,7 @@
 void test_ipi_sending(void);
 void test_pic_reception(void);
 void test_print_info(void);
 void test_ipi_sending(void);
 void test_pic_reception(void);
 void test_print_info(void);
+void test_page_coloring(void);
 void test_barrier(void);
 void test_interrupts_irqsave(void);
 void test_bitmasks(void);
 void test_barrier(void);
 void test_interrupts_irqsave(void);
 void test_bitmasks(void);
index 7a1fae5..5ed6112 100644 (file)
@@ -22,6 +22,8 @@ KERN_SRCFILES := $(KERN_ARCH_SRCFILES) \
                  $(KERN_SRC_DIR)/string.c \
                  $(KERN_SRC_DIR)/atomic.c \
                  $(KERN_SRC_DIR)/workqueue.c \
                  $(KERN_SRC_DIR)/string.c \
                  $(KERN_SRC_DIR)/atomic.c \
                  $(KERN_SRC_DIR)/workqueue.c \
+                 $(KERN_SRC_DIR)/colored_caches.c \
+                 $(KERN_SRC_DIR)/page_alloc.c \
                  $(KERN_SRC_DIR)/pmap.c \
                  $(KERN_SRC_DIR)/env.c \
                  $(KERN_SRC_DIR)/manager.c \
                  $(KERN_SRC_DIR)/pmap.c \
                  $(KERN_SRC_DIR)/env.c \
                  $(KERN_SRC_DIR)/manager.c \
diff --git a/kern/src/colored_caches.c b/kern/src/colored_caches.c
new file mode 100644 (file)
index 0000000..cb8c082
--- /dev/null
@@ -0,0 +1,110 @@
+/* Copyright (c) 2009 The Regents of the University  of California. 
+ * See the COPYRIGHT files at the top of this source tree for full 
+ * license information.
+ * 
+ * Kevin Klues <klueska@cs.berkeley.edu>    
+ */
+
+#include <arch/types.h>
+#include <arch/mmu.h>
+#include <colored_caches.h>
+#include <stdio.h>
+
+/************** Cache Related Functions  *****************/
+inline void init_cache_properties(cache_t *c, size_t sz_k, size_t wa, size_t clsz) {
+       c->wa = wa;
+       c->sz_k = sz_k;
+       c->clsz = clsz;
+       
+       //Added as optimization (derived from above);
+       c->num_colors = get_cache_num_page_colors(c);
+}
+inline size_t get_page_color(uintptr_t page, cache_t *c) {
+    return (page % c->num_colors);
+}
+inline size_t get_offset_in_cache_line(uintptr_t addr, cache_t *c) {
+    return (addr % get_cache_bytes_per_line(c));
+}
+
+void print_cache_properties(char *NT lstring, cache_t *c)
+{
+       printk("%s_WAYS_ASSOCIATIVE: %ld\n", lstring, get_cache_ways_associative(c));
+       printk("%s_LINE_SIZE_BYTES: %ld\n", lstring, get_cache_line_size_bytes(c));
+       printk("%s_SIZE_BYTES: %ld\n", lstring, get_cache_size_bytes(c));
+       printk("%s_SIZE_KILOBYTES: %ld\n", lstring, get_cache_size_kilobytes(c));
+       printk("%s_SIZE_MEGABYTES: %ld\n", lstring, get_cache_size_megabytes(c));
+       printk("%s_OFFSET_BITS: %ld\n", lstring, get_cache_num_offset_bits(c));
+       printk("%s_INDEX_BITS: %ld\n", lstring, get_cache_num_index_bits(c));
+       printk("%s_TAG_BITS: %ld\n", lstring, get_cache_num_tag_bits(c));
+       printk("%s_PAGE_COLOR_BITS: %ld\n", lstring, get_cache_num_page_color_bits(c));
+       printk("%s_BYTES_PER_LINE: %ld\n", lstring, get_cache_bytes_per_line(c));
+       printk("%s_NUM_LINES: %ld\n", lstring, get_cache_num_lines(c));
+       printk("%s_NUM_SETS: %ld\n", lstring, get_cache_num_sets(c));
+       printk("%s_LINES_PER_SET: %ld\n", lstring, get_cache_lines_per_set(c));
+       printk("%s_LINES_PER_PAGE: %ld\n", lstring, get_cache_lines_per_page(c));
+       printk("%s_BYTES_PER_WAY: %ld\n", lstring, get_cache_bytes_per_way(c));
+       printk("%s_LINES_PER_WAY: %ld\n", lstring, get_cache_lines_per_way(c));
+       printk("%s_PAGES_PER_WAY: %ld\n", lstring, get_cache_pages_per_way(c));
+       printk("%s_NUM_PAGE_COLORS: %ld\n", lstring, get_cache_num_page_colors(c));
+}
+
+/****************** Cache Properties *********************/
+inline size_t get_cache_ways_associative(cache_t *c) {
+       return (c->wa);
+}
+inline size_t get_cache_line_size_bytes(cache_t *c) {
+       return (c->clsz);
+}
+inline size_t get_cache_size_bytes(cache_t *c) {
+       return (c->sz_k * ONE_KILOBYTE);
+}
+inline size_t get_cache_size_kilobytes(cache_t *c) {
+       return (c->sz_k);
+}
+inline size_t get_cache_size_megabytes(cache_t *c) {
+       return (c->sz_k / ONE_KILOBYTE);
+}
+inline size_t get_cache_num_offset_bits(cache_t *c) {
+       return (LOG2(get_cache_line_size_bytes(c)));
+}
+inline size_t get_cache_num_index_bits(cache_t *c) {
+       return (LOG2(get_cache_size_bytes(c) 
+                   / get_cache_ways_associative(c)
+                   / get_cache_line_size_bytes(c)));
+}
+inline size_t get_cache_num_tag_bits(cache_t *c) {
+       return (NUM_ADDR_BITS - get_cache_num_offset_bits(c) 
+                          - get_cache_num_index_bits(c));
+}
+inline size_t get_cache_num_page_color_bits(cache_t *c) {
+       return (get_cache_num_offset_bits(c) 
+                  + get_cache_num_index_bits(c) 
+                  - PGSHIFT); 
+}
+inline size_t get_cache_bytes_per_line(cache_t *c) {
+       return (1 << get_cache_num_offset_bits(c));
+}
+inline size_t get_cache_num_lines(cache_t *c) {
+       return (get_cache_size_bytes(c)/get_cache_bytes_per_line(c));  
+}
+inline size_t get_cache_num_sets(cache_t *c) {
+       return (get_cache_num_lines(c)/get_cache_ways_associative(c));
+}
+inline size_t get_cache_lines_per_set(cache_t *c) {
+       return (get_cache_ways_associative(c));
+}
+inline size_t get_cache_lines_per_page(cache_t *c) {
+       return (PGSIZE / get_cache_bytes_per_line(c));
+}
+inline size_t get_cache_bytes_per_way(cache_t *c) {
+       return (get_cache_size_bytes(c)/get_cache_ways_associative(c));
+} 
+inline size_t get_cache_lines_per_way(cache_t *c) {
+       return (get_cache_num_lines(c)/get_cache_ways_associative(c));
+} 
+inline size_t get_cache_pages_per_way(cache_t *c) {
+       return (get_cache_lines_per_way(c)/get_cache_lines_per_page(c));
+}
+inline size_t get_cache_num_page_colors(cache_t *c) {
+       return get_cache_pages_per_way(c);
+}
\ No newline at end of file
index 0122e99..4413a65 100644 (file)
@@ -124,7 +124,7 @@ WRITES(e->env_pgdir, e->env_cr3, e->env_procinfo, e->env_procdata)
         */
        r = page_alloc(&pgdir);
        if(r < 0) return r;
         */
        r = page_alloc(&pgdir);
        if(r < 0) return r;
-       pgdir->pp_ref++;
+       page_incref(pgdir);
 
        /*
         * Next, set up the e->env_pgdir and e->env_cr3 pointers to point
 
        /*
         * Next, set up the e->env_pgdir and e->env_cr3 pointers to point
@@ -195,7 +195,7 @@ WRITES(e->env_pgdir, e->env_cr3, e->env_procinfo, e->env_procdata)
        // Up it, so it never goes away.  One per user, plus one from page_alloc
        // This is necessary, since it's in the per-process range of memory that
        // gets freed during page_free.
        // Up it, so it never goes away.  One per user, plus one from page_alloc
        // This is necessary, since it's in the per-process range of memory that
        // gets freed during page_free.
-       shared_page->pp_ref++;
+       page_incref(shared_page);
        }
 
        // Inserted into every process's address space at UGDATA
        }
 
        // Inserted into every process's address space at UGDATA
index 41a85c8..ba518a1 100644 (file)
@@ -46,6 +46,7 @@ void kernel_init(multiboot_info_t *mboot_info)
 
        vm_init();
 
 
        vm_init();
 
+       cache_init();
        page_init();
        page_check();
 
        page_init();
        page_check();
 
index df337a3..acd811b 100644 (file)
 
 #define kmallocdebug(args...)  printk(args)
 
 
 #define kmallocdebug(args...)  printk(args)
 
+physaddr_t boot_freemem;           // Pointer to next byte of free physical mem
 static page_list_t pages_list; //List of physical pages used by kmalloc
 static page_list_t pages_list; //List of physical pages used by kmalloc
-extern size_t naddrpage;
 
 
-void kmalloc_init() {
+/*
+ * Allocate n bytes of physical memory aligned on an 
+ * align-byte boundary.  Align must be a power of two.
+ * Return kernel virtual address.  Returned memory is uninitialized.
+ *
+ * If we're out of memory, boot_alloc should panic.
+ * This function may ONLY be used during initialization,
+ * before the page_free_list has been set up.
+ */
+void* boot_alloc(uint32_t size, uint32_t align)
+{
+       extern char (COUNT(1) end)[]; //Read in from the linker script
+       void *v;
+
+       // Initialize boot_freemem if this is the first time.
+       // 'end' is a magic symbol automatically generated by the linker,
+       // which points to the end of the kernel's bss segment -
+       // i.e., the first virtual address that the linker
+       // did _not_ assign to any kernel code or global variables.
+       if (boot_freemem == 0)
+               boot_freemem = (physaddr_t) end;
+
+       //      Step 1: round boot_freemem up to be aligned properly
+       boot_freemem = ROUNDUP(boot_freemem, align);
+
+       //      Step 2: save current value of boot_freemem as allocated chunk
+       v = (void *COUNT(size)) TC(boot_freemem);
+       //  Step 2.5: check if we can alloc
+       if (PADDR(boot_freemem + size) > maxaddrpa)
+               panic("Out of memory in boot alloc, you fool!\n");
+       //      Step 3: increase boot_freemem to record allocation
+       boot_freemem += size;   
+       //      Step 4: return allocated chunk
+       return v;
+}
+
+void kmalloc_init() 
+{
        LIST_INIT(&pages_list);
 }
 
        LIST_INIT(&pages_list);
 }
 
-void* kmalloc(size_t size, int flags) {
+void* kmalloc(size_t size, int flags) 
+{
        int npages = ROUNDUP(size, PGSIZE) / PGSIZE;
        
        // Find 'npages' free consecutive pages
        int first = -1;
        int npages = ROUNDUP(size, PGSIZE) / PGSIZE;
        
        // Find 'npages' free consecutive pages
        int first = -1;
-       kmallocdebug("naddrpage: %u\n", naddrpage);
+       kmallocdebug("naddrpages: %u\n", naddrpages);
        kmallocdebug("npages: %u\n", npages);
        kmallocdebug("npages: %u\n", npages);
-       for(int i=(naddrpage-1); i>=(npages-1); i--) {
+       for(int i=(naddrpages-1); i>=(npages-1); i--) {
                int j;
                for(j=i; j>=i-(npages-1); j--) {
                        if( !page_is_free(j) )
                int j;
                for(j=i; j>=i-(npages-1); j--) {
                        if( !page_is_free(j) )
@@ -47,21 +85,23 @@ void* kmalloc(size_t size, int flags) {
                page_t* page;
                page_alloc_specific(&page, first+i);
                page->num_cons_links = npages-i;
                page_t* page;
                page_alloc_specific(&page, first+i);
                page->num_cons_links = npages-i;
-               LIST_INSERT_HEAD(&pages_list, page, pp_link);
+               LIST_INSERT_HEAD(&pages_list, page, global_link);
                kmallocdebug("mallocing page: %u\n", first+i);
                kmallocdebug("at addr: %p\n", ppn2kva(first+i));
        }
        //And return the address of the first one
        return ppn2kva(first);
 }
                kmallocdebug("mallocing page: %u\n", first+i);
                kmallocdebug("at addr: %p\n", ppn2kva(first+i));
        }
        //And return the address of the first one
        return ppn2kva(first);
 }
-void kfree(void *addr) {
+
+void kfree(void *addr)
+{
        kmallocdebug("incoming address: %p\n", addr);
        page_t* page = kva2page(addr);
        int num_links = page->num_cons_links;
        kmallocdebug("getting page: %u\n", page2ppn(page));
        for(int i=0; i<num_links; i++) {
                page_t* p = ppn2page((page2ppn(page) + i));
        kmallocdebug("incoming address: %p\n", addr);
        page_t* page = kva2page(addr);
        int num_links = page->num_cons_links;
        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, pp_link);
+               LIST_REMOVE(p, global_link);
                page_free(p);
                kmallocdebug("freeing page: %d\n", page2ppn(p));
        }
                page_free(p);
                kmallocdebug("freeing page: %d\n", page2ppn(p));
        }
index b66207a..f6e937f 100644 (file)
 #endif
 
 // These variables are set by i386_detect_memory()
 #endif
 
 // These variables are set by i386_detect_memory()
-physaddr_t maxpa;// Maximum physical address
-physaddr_t maxaddrpa;    // Maximum directly addressable physical address
+physaddr_t maxpa;      // Maximum physical address in the system
+physaddr_t maxaddrpa;  // Maximum addressable physical address
 void *SNT maxaddrpa_ptr;
 void *SNT maxaddrpa_ptr;
-size_t npage;   // Amount of physical memory (in pages)
-size_t naddrpage;       // Amount of addressable physical memory (in pages)
+size_t npages;         // Total number of physical memory pages
+size_t naddrpages;       // Number of addressable physical memory pages
+
 static size_t basemem;  // Amount of base memory (in bytes)
 static size_t extmem;   // Amount of extended memory (in bytes)
 
 static size_t basemem;  // Amount of base memory (in bytes)
 static size_t extmem;   // Amount of extended memory (in bytes)
 
@@ -32,14 +33,14 @@ multiboot_detect_memory(multiboot_info_t *mbi)
        else
                maxpa = basemem;
 
        else
                maxpa = basemem;
 
-       npage = maxpa / PGSIZE;
+       npages = maxpa / PGSIZE;
 
        // IOAPIC - KERNBASE is the max amount of virtual addresses we can use
        // for the physical memory mapping (aka - the KERNBASE mapping)
        maxaddrpa = MIN(maxpa, IOAPIC_BASE - KERNBASE);
        maxaddrpa_ptr = (void *SNT)maxaddrpa;
 
 
        // IOAPIC - KERNBASE is the max amount of virtual addresses we can use
        // for the physical memory mapping (aka - the KERNBASE mapping)
        maxaddrpa = MIN(maxpa, IOAPIC_BASE - KERNBASE);
        maxaddrpa_ptr = (void *SNT)maxaddrpa;
 
-       naddrpage = maxaddrpa / PGSIZE;
+       naddrpages = maxaddrpa / PGSIZE;
 
        cprintf("Physical memory: %dK available, ", (int)(maxpa/1024));
        cprintf("base = %dK, extended = %dK\n", (int)(basemem/1024), (int)(extmem/1024));
 
        cprintf("Physical memory: %dK available, ", (int)(maxpa/1024));
        cprintf("base = %dK, extended = %dK\n", (int)(basemem/1024), (int)(extmem/1024));
diff --git a/kern/src/page_alloc.c b/kern/src/page_alloc.c
new file mode 100644 (file)
index 0000000..f19f1d1
--- /dev/null
@@ -0,0 +1,157 @@
+/* Copyright (c) 2009 The Regents of the University  of California. 
+ * See the COPYRIGHT files at the top of this source tree for full 
+ * license information.
+ * 
+ * Kevin Klues <klueska@cs.berkeley.edu>    
+ */
+
+#include <sys/queue.h>
+#include <page_alloc.h>
+#include <pmap.h>
+#include <string.h>
+
+/*
+ * Clear a Page structure.
+ * The result has null links and 0 refcount.
+ * Note that the corresponding physical page is NOT initialized!
+ */
+static void page_clear(page_t *SAFE page)
+{
+       memset(page, 0, sizeof(page_t));
+}
+
+/*
+ * Allocates a physical page.
+ * Does NOT set the contents of the physical page to zero -
+ * the caller must do that if necessary.
+ *
+ * *page       -- is set to point to the Page struct 
+ *                of the newly allocated page
+ *
+ * RETURNS 
+ *   ESUCCESS  -- on success
+ *   -ENOMEM   -- otherwise 
+ */
+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;
+}
+
+/* 
+ * This macro defines multiple functions of the form:
+ * error_t _cache##_page_alloc(page_t** page, size_t color)
+ *
+ * Each of these functions operates on a different level of 
+ * of the cache heirarchy, and allocates a physical page
+ * from the list of pages corresponding to the supplied 
+ * color for the given cache.  
+ * 
+ * Does NOT set the contents of the physical page to zero -
+ * the caller must do that if necessary.
+ *
+ * color       -- the color from which to allocate a page
+ * *page       -- is set to point to the Page struct 
+ *                of the newly allocated page
+ *
+ * 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;
+ * }
+ */
+DECLARE_CACHE_COLORED_PAGE_ALLOC_FUNCTIONS();
+
+/*
+ * Allocates a specific physical page.
+ * Does NOT set the contents of the physical page to zero -
+ * the caller must do that if necessary.
+ *
+ * ppn         -- the page number to allocate
+ * *page       -- is set to point to the Page struct 
+ *                of the newly allocated page
+ *
+ * RETURNS 
+ *   ESUCCESS  -- on success
+ *   -ENOMEM   -- otherwise 
+ */
+error_t page_alloc_specific(page_t** page, size_t ppn)
+{
+       //TODO: Put a lock around this
+       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);
+       page_clear(*page);
+       return 0;
+}
+
+/*
+ * Return a page to the free list.
+ * (This function should only be called when pp->page_ref reaches 0.)
+ */
+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);       
+       return ESUCCESS;
+}
+
+/*
+ * 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;
+       return FALSE;
+}
+
+/*
+ * Increment the reference count on a page
+ */
+void page_incref(page_t *page)
+{
+       page->page_ref++;
+}
+
+/*
+ * Decrement the reference count on a page,
+ * freeing it if there are no more refs.
+ */
+void page_decref(page_t *page)
+{
+       if (--page->page_ref == 0)
+               page_free(page);
+}
+
+/*
+ * Set the reference count on a page to a specific value
+ */
+void page_setref(page_t *page, size_t val)
+{
+       page->page_ref = val;
+}
+
index a1cb625..6ba6330 100644 (file)
 #include <process.h>
 #include <stdio.h>
 
 #include <process.h>
 #include <stdio.h>
 
-//
-// Allocate n bytes of physical memory aligned on an 
-// align-byte boundary.  Align must be a power of two.
-// Return kernel virtual address.  Returned memory is uninitialized.
-//
-// If we're out of memory, boot_alloc should panic.
-// This function may ONLY be used during initialization,
-// before the page_free_list has been set up.
-// 
-void*
-boot_alloc(uint32_t n, uint32_t align)
-{
-       extern char (SNT end)[];
-       void *v;
-
-       // Initialize boot_freemem if this is the first time.
-       // 'end' is a magic symbol automatically generated by the linker,
-       // which points to the end of the kernel's bss segment -
-       // i.e., the first virtual address that the linker
-       // did _not_ assign to any kernel code or global variables.
-       if (boot_freemem == 0) {
-               boot_freemem = TC(end);
-       }
-
-       //      Step 1: round boot_freemem up to be aligned properly
-       boot_freemem = PTRROUNDUP(boot_freemem, align);
-
-       //      Step 2: save current value of boot_freemem as allocated chunk
-       v = boot_freemem;
-       //  Step 2.5: check if we can alloc
-       if (PADDR(boot_freemem + n) > maxaddrpa)
-               panic("Out of memory in boot alloc, you fool!\n");
-       //      Step 3: increase boot_freemem to record allocation
-       boot_freemem += n;      
-       //      Step 4: return allocated chunk
-       return v;
-}
-
-void*
-boot_calloc(uint32_t _n, size_t sz, uint32_t align)
-{
-       extern char (SNT end)[];
-       uint32_t n = _n *sz;
-       void *v;
-
-       // Initialize boot_freemem if this is the first time.
-       // 'end' is a magic symbol automatically generated by the linker,
-       // which points to the end of the kernel's bss segment -
-       // i.e., the first virtual address that the linker
-       // did _not_ assign to any kernel code or global variables.
-       if (boot_freemem == 0)
-               boot_freemem = TC(end);
-
-       //      Step 1: round boot_freemem up to be aligned properly
-       boot_freemem = PTRROUNDUP(boot_freemem, align);
-
-       //      Step 2: save current value of boot_freemem as allocated chunk
-       v = boot_freemem;
-       //  Step 2.5: check if we can alloc
-       if (PADDR(boot_freemem + n) > maxaddrpa)
-               panic("Out of memory in boot alloc, you fool!\n");
-       //      Step 3: increase boot_freemem to record allocation
-       boot_freemem += n;
-       //  Step 4: zero allocated chunk
-       memset(v,0,n);
-       //      Step 5: return allocated chunk
-       return v;
-}
-
-//
-// Initialize a Page structure.
-// The result has null links and 0 refcount.
-// Note that the corresponding physical page is NOT initialized!
-//
-static void
-page_initpp(page_t *COUNT(1) pp)
-{
-       memset(pp, 0, sizeof(*pp));
-}
-
-/*
- * Allocates a physical page.
- * Does NOT set the contents of the physical page to zero -
- * the caller must do that if necessary.
- *
- * *pp_store   -- is set to point to the Page struct 
- *                of the newly allocated page
- *
- * RETURNS 
- *   0         -- on success
- *   -ENOMEM   -- otherwise 
- */
-int page_alloc(page_t *COUNT(1) *pp_store)
-{
-       if (LIST_EMPTY(&page_free_list))
-               return -ENOMEM;
-       *pp_store = LIST_FIRST(&page_free_list);
-       LIST_REMOVE(*pp_store, pp_link);
-       page_initpp(*pp_store);
-       return 0;
-}
-
-/*
- * Allocates a specific physical page.
- * Does NOT set the contents of the physical page to zero -
- * the caller must do that if necessary.
- *
- * *pp_store   -- is set to point to the Page struct 
- *                of the newly allocated page
- *
- * RETURNS 
- *   0         -- on success
- *   -ENOMEM   -- otherwise 
- */
-int page_alloc_specific(page_t **pp_store, size_t ppn)
-{
-       page_t* page = ppn2page(ppn);
-       if( page->pp_ref != 0 )
-               return -ENOMEM;
-       *pp_store = page;
-       LIST_REMOVE(*pp_store, pp_link);
-       page_initpp(*pp_store);
-       return 0;
-}
-
-int page_is_free(size_t ppn) {
-       page_t* page = ppn2page(ppn);
-       if( page->pp_ref == 0 )
-               return TRUE;
-       return FALSE;
-}
-
-//
-// Return a page to the free list.
-// (This function should only be called when pp->pp_ref reaches 0.)
-//
-void page_free(page_t *pp)
-{
-       // this check allows us to call this on null ptrs, which helps when
-       // allocating and checking for errors on several pages at once
-       if (pp) {
-               if (pp->pp_ref)
-                       panic("Attempting to free page with non-zero reference count!");
-               LIST_INSERT_HEAD(&page_free_list, pp, pp_link);
-       }
-}
-
-//
-// Decrement the reference count on a page,
-// freeing it if there are no more refs.
-//
-void
-page_decref(page_t *pp)
-{
-       if (--pp->pp_ref == 0)
-               page_free(pp);
-}
+static void *DANGEROUS user_mem_check_addr;
 
 //
 // Map the physical page 'pp' at virtual address 'va'.
 
 //
 // Map the physical page 'pp' at virtual address 'va'.
@@ -180,7 +24,7 @@ page_decref(page_t *pp)
 //   - If there is already a page mapped at 'va', it is page_remove()d.
 //   - If necessary, on demand, allocates a page table and inserts it into
 //     'pgdir'.
 //   - If there is already a page mapped at 'va', it is page_remove()d.
 //   - If necessary, on demand, allocates a page table and inserts it into
 //     'pgdir'.
-//   - pp->pp_ref should be incremented if the insertion succeeds.
+//   - page_incref() should be called if the insertion succeeds.
 //   - The TLB must be invalidated if a page was formerly present at 'va'.
 //     (this is handled in page_remove)
 //
 //   - The TLB must be invalidated if a page was formerly present at 'va'.
 //     (this is handled in page_remove)
 //
@@ -203,7 +47,7 @@ page_insert(pde_t *pgdir, page_t *pp, void *va, int perm)
        // need to up the ref count in case pp is already mapped at va
        // and we don't want to page_remove (which could free pp) and then 
        // continue as if pp wasn't freed.  moral = up the ref asap
        // need to up the ref count in case pp is already mapped at va
        // and we don't want to page_remove (which could free pp) and then 
        // continue as if pp wasn't freed.  moral = up the ref asap
-       pp->pp_ref++;
+       page_incref(pp);
        if (*pte & PTE_P) {
                page_remove(pgdir, va);
        }
        if (*pte & PTE_P) {
                page_remove(pgdir, va);
        }
@@ -222,7 +66,7 @@ page_insert(pde_t *pgdir, page_t *pp, void *va, int perm)
 //     function returns -ENOMEM.
 //   - If necessary, on demand, this function will allocate a page table 
 //     and inserts it into 'pgdir'.
 //     function returns -ENOMEM.
 //   - If necessary, on demand, this function will allocate a page table 
 //     and inserts it into 'pgdir'.
-//   - pp->pp_ref should be incremented if the insertion succeeds.
+//   - page_incref() should be called if the insertion succeeds.
 //
 // RETURNS: 
 //   NULL, if no free va in the range (vab, vae) could be found
 //
 // RETURNS: 
 //   NULL, if no free va in the range (vab, vae) could be found
@@ -308,8 +152,6 @@ tlb_invalidate(pde_t *pgdir, void *va)
        invlpg(va);
 }
 
        invlpg(va);
 }
 
-static void *DANGEROUS user_mem_check_addr;
-
 //
 // Check that an environment is allowed to access the range of memory
 // [va, va+len) with permissions 'perm | PTE_P'.
 //
 // Check that an environment is allowed to access the range of memory
 // [va, va+len) with permissions 'perm | PTE_P'.
index 1b79796..54f3c37 100644 (file)
@@ -15,6 +15,9 @@
 #include <syscall.h>
 #include <timing.h>
 #include <kfs.h>
 #include <syscall.h>
 #include <timing.h>
 #include <kfs.h>
+#include <multiboot.h>
+#include <pmap.h>
+#include <page_alloc.h>
 
 #define test_vector 0xeb
 
 
 #define test_vector 0xeb
 
@@ -82,6 +85,76 @@ void test_print_info(void)
        cprintf("\nDone!\n");
 }
 
        cprintf("\nDone!\n");
 }
 
+void test_page_coloring(void) 
+{
+       //Print the different cache properties of our machine
+       print_cache_properties("L1", &l1);
+       cprintf("\n");
+       print_cache_properties("L2", &l2);
+       cprintf("\n");
+       print_cache_properties("L3", &l3);
+       cprintf("\n");
+
+       //Print some stats about our memory
+       cprintf("Max Address: %u\n", MAX_VADDR);
+       cprintf("Num Pages: %u\n", npages);
+
+       //Declare a local variable for allocating pages 
+       page_t* 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++) {
+               cprintf("  COLOR %d:\n", i);
+               while(l1_page_alloc(&page, i) != -ENOMEM)
+                       cprintf("    Page: %d\n", page2ppn(page));
+       }
+
+       //Put all the pages back by reinitializing
+       page_init();
+       
+       //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++) {
+               cprintf("  COLOR %d:\n", i);
+               while(l2_page_alloc(&page, i) != -ENOMEM)
+                       cprintf("    Page: %d\n", page2ppn(page));
+       }
+
+       //Put all the pages back by reinitializing
+       page_init();
+       
+       //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++) {
+               cprintf("  COLOR %d:\n", i);
+               while(l3_page_alloc(&page, i) != -ENOMEM)
+                       cprintf("    Page: %d\n", page2ppn(page));
+       }
+       
+       //Put all the pages back by reinitializing
+       page_init();
+       
+       //Run through and allocate all pages through page_alloc
+       cprintf("Allocating from global allocator:\n");
+       while(page_alloc(&page) != -ENOMEM)
+               cprintf("    Page: %d\n", page2ppn(page));
+       
+       if(l2_page_alloc(&page, 0) != -ENOMEM)
+               cprintf("Should not get here, all pages should already be gone!\n");
+       cprintf("All pages gone for sure...\n");
+       
+       //Now lets put a few pages back using page_free..
+       cprintf("Reinserting pages via page_free and reallocating them...\n");
+       page_free(&pages[0]);
+       page_free(&pages[15]);
+       page_free(&pages[7]);
+       page_free(&pages[6]);
+       page_free(&pages[4]);
+
+       while(page_alloc(&page) != -ENOMEM)
+               cprintf("Page: %d\n", page2ppn(page));  
+}
 
 extern uint8_t num_cpus;
 barrier_t test_cpu_array;
 
 extern uint8_t num_cpus;
 barrier_t test_cpu_array;
index 4691742..f942ed1 100644 (file)
@@ -31,10 +31,9 @@ sub readdeps {
        while (<DEPFILE>) {
                if (/([^:]*):([^\\:]*)([\\]?)$/) {
                        my $target = $filename;
        while (<DEPFILE>) {
                if (/([^:]*):([^\\:]*)([\\]?)$/) {
                        my $target = $filename;
-                       chop($target);
-                       $target = $target . "o";
                        my $deplines = $2;
                        my $slash = $3;
                        my $deplines = $2;
                        my $slash = $3;
+                       $target =~ s/\.d/\.o/;
                        while ($slash ne '') {
                                $_ = <DEPFILE>;
                                defined($_) or die
                        while ($slash ne '') {
                                $_ = <DEPFILE>;
                                defined($_) or die