Improved user binary loading
[akaros.git] / kern / src / page_alloc.c
index 93cd9c8..595b478 100644 (file)
@@ -5,10 +5,40 @@
  * Kevin Klues <klueska@cs.berkeley.edu>    
  */
 
+#ifdef __SHARC__
+#pragma nosharc
+#endif
+
 #include <sys/queue.h>
+#include <arch/bitmask.h>
 #include <page_alloc.h>
 #include <pmap.h>
 #include <string.h>
+#include <kmalloc.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
+uint8_t* global_cache_colors_map;
+
+void colored_page_alloc_init()
+{
+       global_cache_colors_map = 
+              kmalloc(BYTES_FOR_BITMASK(llc_cache->num_colors), 0);
+       CLR_BITMASK(global_cache_colors_map, llc_cache->num_colors);
+       cache_color_alloc(llc_cache, global_cache_colors_map);
+       cache_color_alloc(llc_cache, global_cache_colors_map);
+       cache_color_alloc(llc_cache, global_cache_colors_map);
+       cache_color_alloc(llc_cache, global_cache_colors_map);
+       cache_color_alloc(llc_cache, global_cache_colors_map);
+}
 
 /**
  * @brief 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)
+static void __page_clear(page_t *SAFE page)
 {
        memset(page, 0, sizeof(page_t));
 }
 
+#define __PAGE_ALLOC_FROM_RANGE_GENERIC(page, base_color, range, predicate) \
+       /* Find first available color with pages available */                   \
+    /* in the given range */                                                \
+       int i = base_color;                                                     \
+       for (i; i < (base_color+range); i++) {                                  \
+               if((predicate))                                                     \
+                       break;                                                          \
+       }                                                                       \
+       /* Allocate 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);                                                \
+               return i;                                                           \
+       }                                                                       \
+       return -ENOMEM;
+
+static ssize_t __page_alloc_from_color_range(page_t** page,  
+                                           uint16_t base_color,
+                                           uint16_t range) 
+{
+       __PAGE_ALLOC_FROM_RANGE_GENERIC(page, base_color, range, 
+                        !LIST_EMPTY(&colored_page_free_list[i]));
+}
+
+static ssize_t __page_alloc_from_color_map_range(page_t** page, uint8_t* map, 
+                                              size_t base_color, size_t range)
+{  
+       __PAGE_ALLOC_FROM_RANGE_GENERIC(page, base_color, range, 
+                   GET_BITMASK_BIT(map, i) && !LIST_EMPTY(&colored_page_free_list[i]))
+}
+
+static ssize_t __colored_page_alloc(uint8_t* map, page_t** page, 
+                                               size_t next_color)
+{
+       ssize_t ret;
+       if((ret = __page_alloc_from_color_map_range(page, map, 
+                                  next_color, llc_cache->num_colors)) < 0)
+               ret = __page_alloc_from_color_map_range(page, map, 0, next_color);
+       return ret;
+}
+
+/* Internal version of page_alloc_specific.  Grab the lock first. */
+static error_t __page_alloc_specific(page_t** page, size_t ppn)
+{
+       page_t* sp_page = ppn2page(ppn);
+       if( sp_page->page_ref != 0 )
+               return -ENOMEM;
+       *page = sp_page;
+       LIST_REMOVE(*page, page_link);
+
+       __page_clear(*page);
+       return 0;
+}
+
 /**
- * @brief Allocates a physical page from a pool of unused physical memory
+ * @brief Allocates a physical page from a pool of unused physical memory.
  *
- * Does NOT set the contents of the physical page to zero -
- * the caller must do that if necessary.
+ * Zeroes the page.
  *
  * @param[out] page  set to point to the Page struct
  *                   of the newly allocated page
@@ -33,52 +117,94 @@ static void page_clear(page_t *SAFE page)
  * @return ESUCCESS on success
  * @return -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;
+error_t upage_alloc(struct proc* p, page_t** page)
+{
+       spin_lock_irqsave(&colored_page_free_list_lock);
+       ssize_t ret = __colored_page_alloc(p->cache_colors_map, 
+                                            page, p->next_cache_color);
+       spin_unlock_irqsave(&colored_page_free_list_lock);
+
+       memset(page2kva(*page),0,PGSIZE);
+
+       if(ret >= 0)
+               p->next_cache_color = ret;
+       return ret;
+}
+
+error_t kpage_alloc(page_t** page) 
+{
+       static size_t next_color = 0;
+       ssize_t ret;
+       spin_lock_irqsave(&colored_page_free_list_lock);
+       if((ret = __page_alloc_from_color_range(page, next_color, 
+                                   llc_cache->num_colors)) < 0)
+               ret = __page_alloc_from_color_range(page, 0, next_color);
+
+       if(ret >= 0) {
+               next_color = ret;        
+               page_incref(*page);
+               ret = ESUCCESS;
        }
-       return -ENOMEM;
+       spin_unlock_irqsave(&colored_page_free_list_lock);
+       
+       return ret;
 }
 
-/*
- * 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
+/**
+ * @brief Allocated 2^order contiguous physical pages.  Will incrememnt the
+ * reference count for the pages.
  *
- * RETURNS 
- *   ESUCCESS  -- on success
- *   -ENOMEM   -- otherwise 
+ * @param[in] order order of the allocation
+ * @param[in] flags memory allocation flags
  *
- * 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;
- * }
+ * @return The KVA of the first page, NULL otherwise.
  */
-DECLARE_CACHE_COLORED_PAGE_ALLOC_FUNCTIONS();
+void *get_cont_pages(size_t order, int flags)
+{
+       size_t npages = 1 << order;     
+
+       // Find 'npages' free consecutive pages
+       int first = -1;
+       spin_lock_irqsave(&colored_page_free_list_lock);
+       for(int i=(naddrpages-1); i>=(npages-1); i--) {
+               int j;
+               for(j=i; j>=(i-(npages-1)); j--) {
+                       if( !page_is_free(j) ) {
+                               i = j - 1;
+                               break;
+                       }
+               }
+               if( j == (i-(npages-1)-1)) {
+                       first = j+1;
+                       break;
+               }
+       }
+       //If we couldn't find them, return NULL
+       if( first == -1 ) {
+               spin_unlock_irqsave(&colored_page_free_list_lock);
+               return NULL;
+       }
+
+       for(int i=0; i<npages; i++) {
+               page_t* page;
+               __page_alloc_specific(&page, first+i);
+               page_incref(page); 
+       }
+       spin_unlock_irqsave(&colored_page_free_list_lock);
+       return ppn2kva(first);
+}
+
+void free_cont_pages(void *buf, size_t order)
+{
+       size_t npages = 1 << order;     
+       spin_lock_irqsave(&colored_page_free_list_lock);
+       for (int i = kva2ppn(buf); i < kva2ppn(buf) + npages; i++) {
+               __page_decref(ppn2page(i));
+               assert(page_is_free(i));
+       }
+       spin_unlock_irqsave(&colored_page_free_list_lock);
+       return; 
+}
 
 /*
  * Allocates a specific physical page.
@@ -93,37 +219,54 @@ DECLARE_CACHE_COLORED_PAGE_ALLOC_FUNCTIONS();
  *   ESUCCESS  -- on success
  *   -ENOMEM   -- otherwise 
  */
-error_t page_alloc_specific(page_t** page, size_t ppn)
+error_t upage_alloc_specific(struct proc* p, 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);
+       spin_lock_irqsave(&colored_page_free_list_lock);
+       __page_alloc_specific(page, ppn);
+       spin_unlock_irqsave(&colored_page_free_list_lock);
+       return 0;
+}
+
+error_t kpage_alloc_specific(page_t** page, size_t ppn)
+{
+       spin_lock_irqsave(&colored_page_free_list_lock);
+       __page_alloc_specific(page, ppn);
+       page_incref(*page);
+       spin_unlock_irqsave(&colored_page_free_list_lock);
        return 0;
 }
 
 /*
  * Return a page to the free list.
  * (This function should only be called when pp->page_ref reaches 0.)
+ * You must hold the page_free list lock before calling this.
  */
-error_t page_free(page_t* page) 
+static 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);       
+       __page_clear(page);
+
+       LIST_INSERT_HEAD(
+          &(colored_page_free_list[get_page_color(page2ppn(page), llc_cache)]),
+          page,
+          page_link
+       );
+
        return ESUCCESS;
 }
 
+error_t page_free(page_t *SAFE page)
+{
+       error_t retval;
+       spin_lock_irqsave(&colored_page_free_list_lock);
+       retval = __page_free(page);
+       spin_unlock_irqsave(&colored_page_free_list_lock);
+       return retval;
+}
+
 /*
  * 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;
@@ -135,6 +278,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++;
 }
 
@@ -144,8 +292,23 @@ void page_incref(page_t *page)
  */
 void page_decref(page_t *page)
 {
+       spin_lock_irqsave(&colored_page_free_list_lock);
+       __page_decref(page);
+       spin_unlock_irqsave(&colored_page_free_list_lock);
+}
+
+/*
+ * Decrement the reference count on a page,
+ * freeing it if there are no more refs.
+ */
+static void __page_decref(page_t *page)
+{
+       if (page->page_ref == 0) {
+               panic("Trying to Free already freed page: %d...\n", page2ppn(page));
+               return;
+       }
        if (--page->page_ref == 0)
-               page_free(page);
+               __page_free(page);
 }
 
 /*