Add an example jumbo page allocator
[akaros.git] / kern / src / page_alloc.c
index 539993c..cfb295e 100644 (file)
-/* Copyright (c) 2009, 2010 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>    
- * Barret Rhoden <brho@cs.berkeley.edu> */
-
-#ifdef __SHARC__
-#pragma nosharc
-#endif
+/* Copyright (c) 2009, 2010 The Regents of the University of California.
+ * Copyright (c) 2016 Google Inc
+ * See LICENSE for details.
+ *
+ * Barret Rhoden <brho@cs.berkeley.edu>
+ * Kevin Klues <klueska@cs.berkeley.edu> */
 
-#include <sys/queue.h>
-#include <arch/bitmask.h>
 #include <page_alloc.h>
 #include <pmap.h>
-#include <string.h>
 #include <kmalloc.h>
-#include <blockdev.h>
-
-#define l1 (available_caches.l1)
-#define l2 (available_caches.l2)
-#define l3 (available_caches.l3)
-
-static void __page_decref(page_t *CT(1) page);
-static error_t __page_alloc_specific(page_t** page, size_t ppn);
-
-#ifdef __CONFIG_PAGE_COLORING__
-#define NUM_KERNEL_COLORS 8
-#else
-#define NUM_KERNEL_COLORS 1
-#endif
-
-
-// Global list of colors allocated to the general purpose memory allocator
-uint8_t* global_cache_colors_map;
-size_t global_next_color = 0;
-
-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);
-       for(int i = 0; i < llc_cache->num_colors/NUM_KERNEL_COLORS; i++)
-               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)
-{
-       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, pg_link);                                        \
-               __page_clear(*page);                                                \
-               page_setref((*page), 1);                                            \
-               return i;                                                           \
-       }                                                                       \
-       return -ENOMEM;
+#include <arena.h>
 
-static ssize_t __page_alloc_from_color_range(page_t** page,  
-                                           uint16_t base_color,
-                                           uint16_t range) 
+/* Helper, allocates a free page. */
+static struct page *get_a_free_page(void)
 {
-       __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]))
-}
+       void *addr;
 
-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 - next_color)) < 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 (!page_is_free(ppn))
-               return -ENOMEM;
-       *page = sp_page;
-       LIST_REMOVE(*page, pg_link);
-       __page_clear(*page);
-       page_setref(*page, 1);
-       return 0;
+       addr = kpages_alloc(PGSIZE, MEM_ATOMIC);
+       if (!addr)
+               return NULL;
+       return kva2page(addr);
 }
 
 /**
  * @brief Allocates a physical page from a pool of unused physical memory.
- * Note, the page IS reference counted.
  *
  * Zeroes the page.
  *
@@ -123,198 +32,130 @@ static error_t __page_alloc_specific(page_t** page, size_t ppn)
  * @return ESUCCESS on success
  * @return -ENOMEM  otherwise
  */
-error_t upage_alloc(struct proc* p, page_t** page, int zero)
+error_t upage_alloc(struct proc *p, page_t **page, bool zero)
 {
-       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);
+       struct page *pg = get_a_free_page();
 
-       if (ret >= 0) {
-               if(zero)
-                       memset(page2kva(*page),0,PGSIZE);
-               p->next_cache_color = (ret + 1) & (llc_cache->num_colors-1);
-               return 0;
-       }
-       return ret;
+       if (!pg)
+               return -ENOMEM;
+       *page = pg;
+       if (zero)
+               memset(page2kva(*page), 0, PGSIZE);
+       return 0;
 }
 
-/* Allocates a refcounted page of memory for the kernel's use */
-error_t kpage_alloc(page_t** page) 
+error_t kpage_alloc(page_t **page)
 {
-       ssize_t ret;
-       spin_lock_irqsave(&colored_page_free_list_lock);
-       if ((ret = __page_alloc_from_color_range(page, global_next_color, 
-                                   llc_cache->num_colors - global_next_color)) < 0)
-               ret = __page_alloc_from_color_range(page, 0, global_next_color);
+       struct page *pg = get_a_free_page();
 
-       if (ret >= 0) {
-               global_next_color = ret;        
-               ret = ESUCCESS;
-       }
-       spin_unlock_irqsave(&colored_page_free_list_lock);
-       
-       return ret;
+       if (!pg)
+               return -ENOMEM;
+       *page = pg;
+       return 0;
 }
 
-/**
- * @brief Allocated 2^order contiguous physical pages.  Will increment the
- * reference count for the pages.
- *
- * @param[in] order order of the allocation
- * @param[in] flags memory allocation flags
- *
- * @return The KVA of the first page, NULL otherwise.
- */
-void *get_cont_pages(size_t order, int flags)
+/* Helper: allocates a refcounted page of memory for the kernel's use and
+ * returns the kernel address (kernbase), or 0 on error. */
+void *kpage_alloc_addr(void)
 {
-       size_t npages = 1 << order;     
+       struct page *pg = get_a_free_page();
 
-       // 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;
-       }
+       if (!pg)
+               return 0;
+       return page2kva(pg);
+}
 
-       for(int i=0; i<npages; i++) {
-               page_t* page;
-               __page_alloc_specific(&page, first+i);
-       }
-       spin_unlock_irqsave(&colored_page_free_list_lock);
-       return ppn2kva(first);
+void *kpage_zalloc_addr(void)
+{
+       void *retval = kpage_alloc_addr();
+       if (retval)
+               memset(retval, 0, PGSIZE);
+       return retval;
 }
 
-void free_cont_pages(void *buf, size_t order)
+/* Helper function for allocating from the kpages_arena.  This may be useful
+ * later since we might send the caller to a different NUMA domain. */
+void *kpages_alloc(size_t size, int flags)
 {
-       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; 
+       return arena_alloc(kpages_arena, size, flags);
 }
 
-/*
- * 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 upage_alloc_specific(struct proc* p, page_t** page, size_t ppn)
+void *kpages_zalloc(size_t size, int flags)
 {
-       spin_lock_irqsave(&colored_page_free_list_lock);
-       __page_alloc_specific(page, ppn);
-       spin_unlock_irqsave(&colored_page_free_list_lock);
-       return 0;
+       void *ret = arena_alloc(kpages_arena, size, flags);
+
+       if (!ret)
+               return NULL;
+       memset(ret, 0, size);
+       return ret;
 }
 
-error_t kpage_alloc_specific(page_t** page, size_t ppn)
+void kpages_free(void *addr, size_t size)
 {
-       spin_lock_irqsave(&colored_page_free_list_lock);
-       __page_alloc_specific(page, ppn);
-       spin_unlock_irqsave(&colored_page_free_list_lock);
-       return 0;
+       arena_free(kpages_arena, addr, size);
 }
 
-/* Check if a page with the given physical page # is free. */
-int page_is_free(size_t ppn) {
-       page_t* page = ppn2page(ppn);
-       if (kref_refcnt(&page->pg_kref))
-               return FALSE;
-       return TRUE;
+/* Returns naturally aligned, contiguous pages of amount PGSIZE << order.  Linux
+ * code might assume its allocations are aligned. (see dma_alloc_coherent and
+ * bnx2x). */
+void *get_cont_pages(size_t order, int flags)
+{
+       return arena_xalloc(kpages_arena, PGSIZE << order, PGSIZE << order,
+                           0, 0, NULL, NULL, flags);
 }
 
-/*
- * Increment the reference count on a page
- */
-void page_incref(page_t *page)
+void free_cont_pages(void *buf, size_t order)
 {
-       kref_get(&page->pg_kref, 1);
+       arena_xfree(kpages_arena, buf, PGSIZE << order);
 }
 
-/* Decrement the reference count on a page, freeing it if there are no more
- * refs. */
+/* Frees the 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);
+       kpages_free(page2kva(page), PGSIZE);
 }
 
-/* Decrement the reference count on a page, freeing it if there are no more
- * refs.  Don't call this without holding the lock already. */
-static void __page_decref(page_t *page)
+/* Attempts to get a lock on the page for IO operations.  If it is already
+ * locked, it will block the kthread until it is unlocked.  Note that this is
+ * really a "sleep on some event", not necessarily the IO, but it is "the page
+ * is ready". */
+void lock_page(struct page *page)
 {
-       kref_put(&page->pg_kref);
+       /* when this returns, we have are the ones to have locked the page */
+       sem_down(&page->pg_sem);
+       assert(!(atomic_read(&page->pg_flags) & PG_LOCKED));
+       atomic_or(&page->pg_flags, PG_LOCKED);
 }
 
-/* Kref release function. */
-static void page_release(struct kref *kref)
+/* Unlocks the page, and wakes up whoever is waiting on the lock */
+void unlock_page(struct page *page)
 {
-       struct page *page = container_of(kref, struct page, pg_kref);
+       atomic_and(&page->pg_flags, ~PG_LOCKED);
+       sem_up(&page->pg_sem);
+}
 
-       if (page->pg_flags & PG_BUFFER)
-               free_bhs(page);
-       /* Probably issues with this, get rid of it on a future review */
-       __page_clear(page);
-       /* Give our page back to the free list.  The protections for this are that
-        * the list lock is grabbed by page_decref. */
-       LIST_INSERT_HEAD(
-          &(colored_page_free_list[get_page_color(page2ppn(page), llc_cache)]),
-          page,
-          pg_link
-       );
+static void *__jumbo_pml2_alloc(struct arena *a, size_t size, int flags)
+{
+       return arena_xalloc(a, size, PML2_PTE_REACH, 0, 0, NULL, NULL, flags);
 }
 
-/* Helper when initializing a page - just to prevent the proliferation of
- * page_release references (and because this function is sitting around in the
- * code).  Sets the reference count on a page to a specific value, usually 1. */
-void page_setref(page_t *page, size_t val)
+static struct arena *jumbo_pml2_arena;
+
+/* Just for example; we could add qcaches too.  Do this after kmalloc_init(). */
+void jumbo_arena_init(void)
 {
-       kref_init(&page->pg_kref, page_release, val); 
+       jumbo_pml2_arena = arena_create("jumbo_pml2", NULL, 0, PML2_PTE_REACH,
+                                       __jumbo_pml2_alloc, arena_xfree,
+                                       base_arena, 0, MEM_WAIT);
+       assert(jumbo_pml2_arena);
 }
 
-/* Attempts to get a lock on the page for IO operations.  If it is already
- * locked, it will block the thread until it is unlocked. */
-void lock_page(struct page *page)
+void *jumbo_page_alloc(size_t nr, int flags)
 {
-       /* TODO: (BLK) actually do something!  And this has a race!  Not a big deal
-        * right now, since the only users of this are serialized, but once we have
-        * any sort of real IO, this will be an issue. */
-       assert(!(page->pg_flags & PG_LOCKED));
-       page->pg_flags |= PG_LOCKED;
+       return arena_alloc(jumbo_pml2_arena, nr * PML2_PTE_REACH, flags);
 }
 
-/* Unlocks the page, and wakes up whoever is waiting on the lock */
-void unlock_page(struct page *page)
+void jumbo_page_free(void *buf, size_t nr)
 {
-       /* TODO: (BLK) actually do something!  However this unlock works, it will
-        * need to know who to unlock, and it will have to be called in response to
-        * a basic interrupt...  */
-       page->pg_flags &= ~PG_LOCKED;
+       arena_free(jumbo_pml2_arena, buf, nr * PML2_PTE_REACH);
 }