Slab allocator
authorBarret Rhoden <brho@cs.berkeley.edu>
Mon, 19 Oct 2009 00:09:04 +0000 (17:09 -0700)
committerBarret Rhoden <brho@cs.berkeley.edu>
Mon, 19 Oct 2009 00:20:02 +0000 (17:20 -0700)
Introduces a slab allocator, and uses it to back kmalloc allocations
less than 32 pages.  Kmalloc only guarantees 16 byte alignment, so if
you want something better (like page alignment), use get_cont_pages().

13 files changed:
kern/include/kmalloc.h
kern/include/page_alloc.h
kern/include/pmap.h
kern/include/ros/common.h
kern/include/slab.h [new file with mode: 0644]
kern/include/testing.h
kern/src/Makefrag
kern/src/colored_caches.c
kern/src/init.c
kern/src/kmalloc.c
kern/src/page_alloc.c
kern/src/slab.c [new file with mode: 0644]
kern/src/testing.c

index 2aa7171..c09e70c 100644 (file)
 
 #include <ros/common.h>
 
-void  kmalloc_init();
+#define NUM_KMALLOC_CACHES 13
+#define KMALLOC_ALIGNMENT 16
+#define KMALLOC_SMALLEST 32
+#define KMALLOC_LARGEST KMALLOC_SMALLEST << NUM_KMALLOC_CACHES
+#define KMALLOC_OFFSET ROUNDUP(sizeof(struct kmalloc_tag), KMALLOC_ALIGNMENT)
 
 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* (DALLOC(n*sz) boot_calloc)(uint32_t n, size_t sz, uint32_t align);
 
+void kmalloc_init(void);
 void* (DALLOC(size) kmalloc)(size_t size, int flags);
 void* (DALLOC(size) krealloc)(void* buf, size_t size, int flags);
 void  (DFREE(addr) kfree)(void *addr);
 
+#define KMALLOC_TAG_CACHE 1
+#define KMALLOC_TAG_PAGES 2
+
+struct kmalloc_tag {
+       int flags;
+       union {
+               struct kmem_cache *my_cache;
+               size_t num_pages;
+       };
+};
+
 #endif //ROS_KERN_KMALLOC_H
 
index 90bd4c9..938f785 100644 (file)
@@ -21,10 +21,11 @@ typedef struct Page page_t;
 typedef LIST_HEAD(PageList, Page) page_list_t;
 typedef LIST_ENTRY(Page) page_list_entry_t;
 
+/* TODO: this struct is not protected from concurrent operations in any
+ * function.  We may want a lock, but a better thing would be a good use of
+ * reference counting and atomic operations. */
 struct Page {
        page_list_entry_t LCKD(&colored_page_free_list_lock)page_link;
-
-       size_t num_cons_links;
     size_t page_ref;
 };
 
@@ -38,6 +39,8 @@ extern page_list_t LCKD(&colored_page_free_list_lock) * RO CT(llc_num_colors)
 /*************** Functional Interface *******************/
 void page_alloc_init(void);
 error_t page_alloc(page_t *SAFE *page);
+void *get_cont_pages(size_t order, int flags);
+void free_cont_pages(void *buf, size_t order);
 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);
index 052f6b1..7cbaed2 100644 (file)
@@ -139,4 +139,9 @@ static inline page_t* kva2page(void* addr)
        return pa2page(PADDR(addr));
 }
 
+static inline ppn_t kva2ppn(void* addr) 
+{
+       return page2ppn(kva2page(addr));
+}
+
 #endif /* !ROS_KERN_PMAP_H */
index 4f25030..b85be8d 100644 (file)
@@ -72,12 +72,27 @@ typedef int bool;
        (typeof(a)) (PTRROUNDDOWN((char *) (a) + __n - 1, __n));        \
 })
 
+// Return the integer logarithm of the value provided rounded down
+static inline uint32_t LOG2_DOWN(uint32_t value)
+{
+       uint32_t l = 0;
+       while( (value >> l) > 1 ) ++l;
+       return l;
+}
+
 // Return the integer logarithm of the value provided rounded up
-static inline uint32_t LOG2(uint32_t value)
+static inline uint32_t LOG2_UP(uint32_t value)
+{
+       uint32_t _v = LOG2_DOWN(value);
+       if (value ^ (1 << _v))
+               return _v + 1;
+       else
+               return _v;
+}
+
+static inline uint32_t ROUNDUPPWR2(uint32_t value)
 {
-    uint32_t l = 0;
-    while( (value >> l) > 1 ) ++l;
-    return l;
+       return 1 << LOG2_UP(value);
 }
 
 // Return the offset of 'member' relative to the beginning of a struct type
diff --git a/kern/include/slab.h b/kern/include/slab.h
new file mode 100644 (file)
index 0000000..79787e9
--- /dev/null
@@ -0,0 +1,104 @@
+/*
+ * Copyright (c) 2009 The Regents of the University of California
+ * Barret Rhoden <brho@cs.berkeley.edu>
+ * Kevin Klues <klueska@cs.berkeley.edu>
+ * See LICENSE for details.
+ *
+ * Slab allocator, based on the SunOS 5.4 allocator paper.
+ *
+ * There is a list of kmem_cache, which are the caches of objects of a given
+ * size.  This list is sorted in order of size.  Each kmem_cache has three
+ * lists of slabs: full, partial, and empty.  
+ *
+ * For large objects, the kmem_slabs point to bufctls, which have the address
+ * of their large buffers.  These slabs can consist of more than one contiguous
+ * page.
+ *
+ * For small objects, the slabs do not use the bufctls.  Instead, they point to
+ * the next free object in the slab.  The free objects themselves hold the
+ * address of the next free item.  The slab structure is stored at the end of
+ * the page.  There is only one page per slab.
+ *
+ * TODO: Note, that this is a minor pain in the ass, and worth thinking about
+ * before implementing.  To keep the constructor's state valid, we can't just
+ * overwrite things, so we need to add an extra 4-8 bytes per object for the
+ * pointer, and then pass over that data when we return the actual object's
+ * address.  This also might fuck with alignment.
+ */
+
+#ifndef ROS_KERN_SLAB_H
+#define ROS_KERN_SLAB_H
+
+#include <ros/common.h>
+#include <arch/mmu.h>
+#include <sys/queue.h>
+#include <atomic.h>
+
+/* Back in the day, their cutoff for "large objects" was 512B, based on
+ * measurements and on not wanting more than 1/8 of internal fragmentation. */
+#define NUM_BUF_PER_SLAB 8
+#define SLAB_LARGE_CUTOFF (PGSIZE / NUM_BUF_PER_SLAB)
+
+struct kmem_slab;
+
+/* Control block for buffers for large-object slabs */
+struct kmem_bufctl {
+       TAILQ_ENTRY(kmem_bufctl) link;
+       void *buf_addr;
+       struct kmem_slab *my_slab;
+};
+TAILQ_HEAD(kmem_bufctl_list, kmem_bufctl);
+
+/* Slabs contain the objects.  Can be either full, partial, or empty,
+ * determined by checking the number of objects busy vs total.  For large
+ * slabs, the bufctl list is used to find a free buffer.  For small, the void*
+ * is used instead.*/
+struct kmem_slab {
+       TAILQ_ENTRY(kmem_slab) link;
+       size_t obj_size;
+       size_t num_busy_obj;
+       size_t num_total_obj;
+       union {
+               struct kmem_bufctl_list bufctl_freelist;
+               void *free_small_obj;
+       };
+};
+TAILQ_HEAD(kmem_slab_list, kmem_slab);
+
+/* Actual cache */
+struct kmem_cache {
+       SLIST_ENTRY(kmem_cache) link;
+       spinlock_t cache_lock;
+       const char *name;
+       size_t obj_size;
+       int align;
+       int flags;
+       struct kmem_slab_list full_slab_list;
+       struct kmem_slab_list partial_slab_list;
+       struct kmem_slab_list empty_slab_list;
+       void (*ctor)(void *, size_t);
+       void (*dtor)(void *, size_t);
+};
+
+/* List of all kmem_caches, sorted in order of size */
+SLIST_HEAD(kmem_cache_list, kmem_cache);
+extern struct kmem_cache_list kmem_caches;
+
+/* Cache management */
+struct kmem_cache *kmem_cache_create(const char *name, size_t obj_size,
+                                     int align, int flags,
+                                     void (*ctor)(void *, size_t),
+                                     void (*dtor)(void *, size_t));
+void kmem_cache_destroy(struct kmem_cache *cp);
+/* Front end: clients of caches use these */
+void *kmem_cache_alloc(struct kmem_cache *cp, int flags);
+void kmem_cache_free(struct kmem_cache *cp, void *buf);
+/* Back end: internal functions */
+void kmem_cache_init(void);
+void kmem_cache_grow(struct kmem_cache *cp);
+void kmem_cache_reap(struct kmem_cache *cp);
+
+/* Debug */
+void print_kmem_cache(struct kmem_cache *kc);
+void print_kmem_slab(struct kmem_slab *slab);
+#endif // !ROS_KERN_SLAB_H
index 7b83224..81d99a2 100644 (file)
@@ -23,6 +23,8 @@ void test_lapic_status_bit(void);
 void test_run_measurements(uint32_t job_num);
 void test_circ_buffer(void);
 void test_active_messages(void);
+void test_slab(void);
+void test_kmalloc(void);
 
 struct trapframe_t;
 
index 531c032..5352eaf 100644 (file)
@@ -42,6 +42,7 @@ KERN_SRCFILES := $(KERN_ARCH_SRCFILES) \
                  $(KERN_SRC_DIR)/schedule.c \
                  $(KERN_SRC_DIR)/mm.c \
                  $(KERN_SRC_DIR)/resource.c \
+                 $(KERN_SRC_DIR)/slab.c \
                  $(KERN_SRC_DIR)/testing.c
 
 # Only build files if they exist.
index 4871121..d5dcbad 100644 (file)
@@ -71,10 +71,10 @@ 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)));
+       return (LOG2_UP(get_cache_line_size_bytes(c)));
 }
 inline size_t get_cache_num_index_bits(cache_t *c) {
-       return (LOG2(get_cache_size_bytes(c) 
+       return (LOG2_UP(get_cache_size_bytes(c) 
                    / get_cache_ways_associative(c)
                    / get_cache_line_size_bytes(c)));
 }
index 95600a5..2c923f4 100644 (file)
 #include <kclock.h>
 #include <manager.h>
 #include <testing.h>
+#include <kmalloc.h>
 
 #include <arch/init.h>
+#include <slab.h>
 
 // zra: flag for Ivy
 int booting = 1;
@@ -63,7 +65,8 @@ void kernel_init(multiboot_info_t *mboot_info)
        cache_init();
        page_init();
        page_check();
-       //test_page_coloring();
+       kmem_cache_init();
+       kmalloc_init();
 
        idt_init();
        sysenter_init();
index cd08c27..17fbc94 100644 (file)
@@ -15,6 +15,8 @@
 #include <pmap.h>
 #include <kmalloc.h>
 #include <stdio.h>
+#include <slab.h>
+#include <assert.h>
 
 #define kmallocdebug(args...)  //printk(args)
 
@@ -62,104 +64,77 @@ void* boot_alloc(uint32_t n, uint32_t align)
        return v;
 }
 
-void* boot_calloc(uint32_t _n, size_t sz, uint32_t align)
+void *boot_calloc(uint32_t n, size_t sz, uint32_t align)
 {
-       extern char (SNT RO 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 = SINIT(TC(end));
-
-       //      Step 1: round boot_freemem up to be aligned properly
-       char RO*tmp = PTRROUNDUP(boot_freemem, align);
-       boot_freemem = SINIT(tmp);
-
-       //      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 = SINIT(boot_freemem + n);
-       //  Step 4: zero allocated chunk
-       memset(v,0,n);
-       //      Step 5: return allocated chunk
+       void *v = boot_alloc(n * sz, align);    
+       memset(v, 0, n * sz);
        return v;
 }
 
-void kmalloc_init() 
+struct kmem_cache *kmalloc_caches[NUM_KMALLOC_CACHES];
+void kmalloc_init(void)
 {
-       LIST_INIT(&pages_list);
+       // build caches of common sizes
+       size_t ksize = KMALLOC_SMALLEST;
+       for (int i = 0; i < NUM_KMALLOC_CACHES; i++) {
+               kmalloc_caches[i] = kmem_cache_create("kmalloc_cache", ksize,
+                                                     KMALLOC_ALIGNMENT, 0, 0, 0);
+               ksize <<= 1;
+       }
 }
 
-voidkmalloc(size_t size, int flags) 
+void *kmalloc(size_t size, int flags) 
 {
-       if (size == 0)
-               return NULL;
-
-       int npages = ROUNDUP(size, PGSIZE) / PGSIZE;
-       
-       // Find 'npages' free consecutive pages
-       int first = -1;
-       kmallocdebug("naddrpages: %u\n", naddrpages);
-       kmallocdebug("npages: %u\n", npages);
-       for(int i=(naddrpages-1); i>=(npages-1); i--) {
-               int j;
-               for(j=i; j>=(i-(npages-1)); j--) {
-                       if( !page_is_free(j) )
-                               break;
-               }
-               if( j == (i-(npages-1)-1)) {
-                       first = j+1;
-                       break;
-               }
+       // reserve space for bookkeeping and preserve alignment
+       size_t ksize = size + KMALLOC_OFFSET;
+       void *buf;
+       int cache_id;
+       // determine cache to pull from
+       if (ksize <= KMALLOC_SMALLEST)
+               cache_id = 0;
+       else
+               cache_id = LOG2_UP(ksize) - LOG2_UP(KMALLOC_SMALLEST);
+       // if we don't have a cache to handle it, alloc cont pages
+       if (cache_id >= NUM_KMALLOC_CACHES) {
+               size_t num_pgs = ROUNDUP(size + sizeof(struct kmalloc_tag), PGSIZE) /
+                                          PGSIZE;
+               buf = get_cont_pages(LOG2_UP(num_pgs), flags);
+               if (!buf)
+                       panic("Kmalloc failed!  Handle me!");
+               // fill in the kmalloc tag
+               struct kmalloc_tag *tag = buf;
+               tag->flags = KMALLOC_TAG_PAGES;
+               tag->num_pages = num_pgs;
+               return buf + KMALLOC_OFFSET;
        }
-       //If we couldn't find them, return NULL
-       if( first == -1 )
-               return NULL;
-               
-       //Otherwise go ahead and allocate them to ourselves now
-       for(int i=0; i<npages; i++) {
-               page_t* page;
-
-               page_alloc_specific(&page, first+i);
-               // Kevin doesn't like this next line 
-               page_incref(page); 
-               page->num_cons_links = npages-i;
-
-               spin_lock_irqsave(&pages_list_lock);
-               LIST_INSERT_HEAD(&pages_list, page, page_link);
-               spin_unlock_irqsave(&pages_list_lock);
-
-               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);
+       // else, alloc from the appropriate cache
+       buf = kmem_cache_alloc(kmalloc_caches[cache_id], flags);
+       if (!buf)
+               panic("Kmalloc failed!  Handle me!");
+       // store a pointer to the buffers kmem_cache in it's bookkeeping space
+       struct kmalloc_tag *tag = buf;
+       tag->flags = KMALLOC_TAG_CACHE;
+       tag->my_cache = kmalloc_caches[cache_id];
+       return buf + KMALLOC_OFFSET;
 }
 
-void* krealloc(void* buf, size_t size, int flags) {
+void *krealloc(void* buf, size_t size, int flags) {
+       struct kmalloc_tag *tag = (struct kmalloc_tag*)(buf - KMALLOC_OFFSET);
+       if (tag->my_cache->obj_size >= size)
+               return buf;
        kfree(buf);
        return kmalloc(size, flags);
 }
 
 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));
-               LIST_REMOVE(p, page_link);
-               page_free(p);
-               kmallocdebug("freeing page: %d\n", page2ppn(p));
-       }
+       assert(addr);
+       struct kmalloc_tag *tag = (struct kmalloc_tag*)(addr - KMALLOC_OFFSET);
+       if (tag->flags & KMALLOC_TAG_CACHE)
+               kmem_cache_free(tag->my_cache, addr - KMALLOC_OFFSET);
+       else if (tag->flags & KMALLOC_TAG_PAGES) {
+               free_cont_pages(addr - KMALLOC_OFFSET, LOG2_UP(tag->num_pages));
+       } else 
+               panic("[Italian Accent]: Che Cazzo! BO! Flag in kmalloc!!!");
 }
 
index 0eb6da4..6dcba14 100644 (file)
 #include <pmap.h>
 #include <string.h>
 
+static void __page_decref(page_t *page);
+static error_t __page_alloc_specific(page_t** page, size_t ppn);
+static error_t __page_free(page_t* page);
+
 /**
  * @brief Clear a Page structure.
  *
@@ -66,6 +70,62 @@ error_t page_alloc(page_t** page)
        return page_alloc_from_color_range(page, 0, llc_num_colors);
 }
 
+/**
+ * @brief Allocated 2^order contiguous physical pages.  Will incrememnt 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)
+{
+       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; 
+}
+
 /*
  * This macro defines multiple functions of the form:
  * error_t _cache##_page_alloc(page_t** page, size_t color)
@@ -131,6 +191,19 @@ error_t l3_page_alloc(page_t** page, size_t color)
        return -ENOCACHE;
 }
 
+/* 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;
+}
+
 /*
  * Allocates a specific physical page.
  * Does NOT set the contents of the physical page to zero -
@@ -147,38 +220,39 @@ error_t l3_page_alloc(page_t** page, size_t color)
 error_t page_alloc_specific(page_t** page, size_t ppn)
 {
        spin_lock_irqsave(&colored_page_free_list_lock);
-       page_t* sp_page = ppn2page(ppn);
-       if( sp_page->page_ref != 0 )
-               return -ENOMEM;
-       *page = sp_page;
-       LIST_REMOVE(*page, page_link);
+       __page_alloc_specific(page, ppn);
        spin_unlock_irqsave(&colored_page_free_list_lock);
-
-       page_clear(*page);
        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);
        cache_t* llc = available_caches.llc;
 
-       spin_lock_irqsave(&colored_page_free_list_lock);
        LIST_INSERT_HEAD(
           &(colored_page_free_list[get_page_color(page2ppn(page), llc)]),
           page,
           page_link
        );
-       spin_unlock_irqsave(&colored_page_free_list_lock);
 
        return ESUCCESS;
 }
 
+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
  */
@@ -203,8 +277,19 @@ 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)
-               page_free(page);
+               __page_free(page);
 }
 
 /*
diff --git a/kern/src/slab.c b/kern/src/slab.c
new file mode 100644 (file)
index 0000000..e6d1ab4
--- /dev/null
@@ -0,0 +1,350 @@
+/*
+ * Copyright (c) 2009 The Regents of the University of California
+ * Barret Rhoden <brho@cs.berkeley.edu>
+ * Kevin Klues <klueska@cs.berkeley.edu>
+ * See LICENSE for details.
+ *
+ * Slab allocator, based on the SunOS 5.4 allocator paper.
+ *
+ * Note that we don't have a hash table for buf to bufctl for the large buffer
+ * objects, so we use the same style for small objects: store the pointer to the
+ * controlling bufctl at the top of the slab object.  Fix this with TODO (BUF).
+ */
+
+#include <slab.h>
+#include <stdio.h>
+#include <assert.h>
+#include <pmap.h>
+
+struct kmem_cache_list kmem_caches;
+spinlock_t kmem_caches_lock;
+
+/* Cache of the kmem_cache objects, needed for bootstrapping */
+struct kmem_cache kmem_cache_cache;
+struct kmem_cache *kmem_slab_cache, *kmem_bufctl_cache;
+
+static void __kmem_cache_create(struct kmem_cache *kc, const char *name,
+                                size_t obj_size, int align, int flags,
+                                void (*ctor)(void *, size_t),
+                                void (*dtor)(void *, size_t))
+{
+       assert(kc);
+       assert(align);
+       kc->cache_lock = 0;
+       kc->name = name;
+       kc->obj_size = obj_size;
+       kc->align = align;
+       kc->flags = flags;
+       TAILQ_INIT(&kc->full_slab_list);
+       TAILQ_INIT(&kc->partial_slab_list);
+       TAILQ_INIT(&kc->empty_slab_list);
+       kc->ctor = ctor;
+       kc->dtor = dtor;
+       
+       /* put in cache list based on it's size */
+       struct kmem_cache *i, *prev = NULL;
+       spin_lock(&kmem_caches_lock);
+       /* find the kmem_cache before us in the list.  yes, this is O(n). */
+       SLIST_FOREACH(i, &kmem_caches, link) {
+               if (i->obj_size < kc->obj_size)
+                       prev = i;
+               else
+                       break;
+       }
+       if (prev)
+               SLIST_INSERT_AFTER(prev, kc, link);
+       else
+               SLIST_INSERT_HEAD(&kmem_caches, kc, link);
+       spin_unlock(&kmem_caches_lock);
+}
+
+void kmem_cache_init(void)
+{
+       kmem_caches_lock = 0;
+       SLIST_INIT(&kmem_caches);
+       /* We need to call the __ version directly to bootstrap the global
+        * kmem_cache_cache. */
+       __kmem_cache_create(&kmem_cache_cache, "kmem_cache",
+                           sizeof(struct kmem_cache),
+                           __alignof__(struct kmem_cache), 0, NULL, NULL);
+       /* Build the slab and bufctl caches */
+       kmem_slab_cache = kmem_cache_create("kmem_slab", sizeof(struct kmem_slab),
+                              __alignof__(struct kmem_slab), 0, NULL, NULL); 
+       kmem_bufctl_cache = kmem_cache_create("kmem_bufctl",
+                                sizeof(struct kmem_bufctl),
+                                __alignof__(struct kmem_bufctl), 0, NULL, NULL); 
+}
+
+/* Cache management */
+struct kmem_cache *kmem_cache_create(const char *name, size_t obj_size,
+                                     int align, int flags,
+                                     void (*ctor)(void *, size_t),
+                                     void (*dtor)(void *, size_t))
+{
+       struct kmem_cache *kc = kmem_cache_alloc(&kmem_cache_cache, 0);
+       __kmem_cache_create(kc, name, obj_size, align, flags, ctor, dtor);
+       return kc;
+}
+
+static void kmem_slab_destroy(struct kmem_cache *cp, struct kmem_slab *a_slab)
+{
+       if (cp->obj_size <= SLAB_LARGE_CUTOFF) {
+               /* Deconstruct all the objects, if necessary */
+               if (cp->dtor) {
+                       void *buf = a_slab->free_small_obj;
+                       for (int i = 0; i < a_slab->num_total_obj; i++) {
+                               cp->dtor(buf, cp->obj_size);
+                               buf += a_slab->obj_size;
+                       }
+               }
+               page_decref(kva2page(ROUNDDOWN(a_slab, PGSIZE)));
+       } else {
+               struct kmem_bufctl *i;
+               void *page_start = (void*)-1;
+               // compute how many pages are allocated, given a power of two allocator
+               size_t num_pages = ROUNDUPPWR2(a_slab->num_total_obj * a_slab->obj_size)
+                                               / PGSIZE;
+               TAILQ_FOREACH(i, &a_slab->bufctl_freelist, link) {
+                       // Track the lowest buffer address, which is the start of the buffer
+                       page_start = MIN(page_start, i->buf_addr);
+                       /* Deconstruct all the objects, if necessary */
+                       if (cp->dtor) // TODO: (BUF)
+                               cp->dtor(i->buf_addr, cp->obj_size);
+                       kmem_cache_free(kmem_bufctl_cache, i);
+               }
+               // free the pages for the slab's buffer
+               free_cont_pages(page_start, LOG2_UP(num_pages));
+               // free the slab object
+               kmem_cache_free(kmem_slab_cache, a_slab);
+       }
+}
+
+/* Once you call destroy, never use this cache again... o/w there may be weird
+ * races, and other serious issues.  */
+void kmem_cache_destroy(struct kmem_cache *cp)
+{
+       struct kmem_slab *a_slab, *next;
+
+       spin_lock(&cp->cache_lock);
+       assert(TAILQ_EMPTY(&cp->full_slab_list));
+       assert(TAILQ_EMPTY(&cp->partial_slab_list));
+       /* Clean out the empty list.  We can't use a regular FOREACH here, since the
+        * link element is stored in the slab struct, which is stored on the page
+        * that we are freeing. */
+       a_slab = TAILQ_FIRST(&cp->empty_slab_list);
+       while (a_slab) {
+               next = TAILQ_NEXT(a_slab, link);
+               kmem_slab_destroy(cp, a_slab);
+               a_slab = next;
+       }
+       spin_lock(&kmem_caches_lock);
+       SLIST_REMOVE(&kmem_caches, cp, kmem_cache, link);
+       spin_unlock(&kmem_caches_lock);
+       kmem_cache_free(&kmem_cache_cache, cp); 
+       spin_unlock(&cp->cache_lock);
+}
+
+/* Front end: clients of caches use these */
+void *kmem_cache_alloc(struct kmem_cache *cp, int flags)
+{
+       void *retval = NULL;
+       spin_lock(&cp->cache_lock);
+       // look at partial list
+       struct kmem_slab *a_slab = TAILQ_FIRST(&cp->partial_slab_list);
+       //      if none, go to empty list and get an empty and make it partial
+       if (!a_slab) {
+               if (TAILQ_EMPTY(&cp->empty_slab_list))
+                       // TODO: think about non-sleeping flags
+                       kmem_cache_grow(cp);
+               // move to partial list
+               a_slab = TAILQ_FIRST(&cp->empty_slab_list);
+               TAILQ_REMOVE(&cp->empty_slab_list, a_slab, link);
+               TAILQ_INSERT_HEAD(&cp->partial_slab_list, a_slab, link);
+       } 
+       // have a partial now (a_slab), get an item, return item
+       if (cp->obj_size <= SLAB_LARGE_CUTOFF) {
+               retval = a_slab->free_small_obj;
+               /* adding the size of the cache_obj to get to the pointer at end of the
+                * buffer pointing to the next free_small_obj */
+               a_slab->free_small_obj = *(uintptr_t**)(a_slab->free_small_obj +
+                                                       cp->obj_size);
+       } else {
+               // rip the first bufctl out of the partial slab's buf list
+               struct kmem_bufctl *a_bufctl = TAILQ_FIRST(&a_slab->bufctl_freelist);
+               TAILQ_REMOVE(&a_slab->bufctl_freelist, a_bufctl, link);
+               retval = a_bufctl->buf_addr;
+       }
+       a_slab->num_busy_obj++;
+       // Check if we are full, if so, move to the full list
+       if (a_slab->num_busy_obj == a_slab->num_total_obj) {
+               TAILQ_REMOVE(&cp->partial_slab_list, a_slab, link);
+               TAILQ_INSERT_HEAD(&cp->full_slab_list, a_slab, link);
+       }
+       spin_unlock(&cp->cache_lock);
+       return retval;
+}
+
+static inline struct kmem_bufctl *buf2bufctl(void *buf, size_t offset)
+{
+       // TODO: hash table for back reference (BUF)
+       return *((struct kmem_bufctl**)(buf + offset));
+}
+
+void kmem_cache_free(struct kmem_cache *cp, void *buf)
+{
+       struct kmem_slab *a_slab;
+       struct kmem_bufctl *a_bufctl;
+
+       spin_lock(&cp->cache_lock);
+       if (cp->obj_size <= SLAB_LARGE_CUTOFF) {
+               // find its slab
+               a_slab = (struct kmem_slab*)(ROUNDDOWN(buf, PGSIZE) + PGSIZE -
+                                            sizeof(struct kmem_slab));
+               /* write location of next free small obj to the space at the end of the
+                * buffer, then list buf as the next free small obj */
+               *(uintptr_t**)(buf + cp->obj_size) = a_slab->free_small_obj;
+               a_slab->free_small_obj = buf;
+       } else {
+               /* Give the bufctl back to the parent slab */
+               // TODO: (BUF) change the interface to not take an offset
+               a_bufctl = buf2bufctl(buf, cp->obj_size);
+               a_slab = a_bufctl->my_slab;
+               TAILQ_INSERT_HEAD(&a_slab->bufctl_freelist, a_bufctl, link);
+       }
+       a_slab->num_busy_obj--;
+       // if it was full, move it to partial
+       if (a_slab->num_busy_obj + 1 == a_slab->num_total_obj) {
+               TAILQ_REMOVE(&cp->full_slab_list, a_slab, link);
+               TAILQ_INSERT_HEAD(&cp->partial_slab_list, a_slab, link);
+       } else if (!a_slab->num_busy_obj) {
+               // if there are none, move to from partial to empty
+               TAILQ_REMOVE(&cp->partial_slab_list, a_slab, link);
+               TAILQ_INSERT_HEAD(&cp->empty_slab_list, a_slab, link);
+       }
+       spin_unlock(&cp->cache_lock);
+}
+
+/* Back end: internal functions */
+/* When this returns, the cache has at least one slab in the empty list.  If
+ * page_alloc fails, there are some serious issues.  This only grows by one slab
+ * at a time.
+ *
+ * Grab the cache lock before calling this.
+ *
+ * TODO: think about page colouring issues with kernel memory allocation. */
+void kmem_cache_grow(struct kmem_cache *cp)
+{
+       struct kmem_slab *a_slab;
+       struct kmem_bufctl *a_bufctl;
+       spin_unlock(&cp->cache_lock);
+       if (cp->obj_size <= SLAB_LARGE_CUTOFF) {
+               // Just get a single page for small slabs
+               page_t *a_page;
+               if (page_alloc(&a_page))
+                       panic("[German Accent]: OOM!!!");
+               page_incref(a_page);
+               // the slab struct is stored at the end of the page
+               a_slab = (struct kmem_slab*)(page2kva(a_page) + PGSIZE -
+                                            sizeof(struct kmem_slab));
+               // Need to add room for the next free item pointer in the object buffer.
+               a_slab->obj_size = ROUNDUP(cp->obj_size + sizeof(uintptr_t), cp->align);
+               a_slab->num_busy_obj = 0;
+               a_slab->num_total_obj = (PGSIZE - sizeof(struct kmem_slab)) /
+                                       a_slab->obj_size;
+               // TODO: consider staggering this IAW section 4.3
+               a_slab->free_small_obj = page2kva(a_page);
+               /* Walk and create the free list, which is circular.  Each item stores
+                * the location of the next one at the end of the block. */
+               void *buf = a_slab->free_small_obj;
+               for (int i = 0; i < a_slab->num_total_obj - 1; i++) {
+                       // Initialize the object, if necessary
+                       if (cp->ctor)
+                               cp->ctor(buf, cp->obj_size);
+                       *(uintptr_t**)(buf + cp->obj_size) = buf + a_slab->obj_size;
+                       buf += a_slab->obj_size;
+               }
+               *((uintptr_t**)(buf + cp->obj_size)) = NULL;
+       } else {
+               a_slab = kmem_cache_alloc(kmem_slab_cache, 0);
+               // TODO: hash table for back reference (BUF)
+               a_slab->obj_size = ROUNDUP(cp->obj_size + sizeof(uintptr_t), cp->align);
+               // alloc n pages, such that it can hold at least 8 items
+               size_t num_pgs = ROUNDUP(NUM_BUF_PER_SLAB * a_slab->obj_size, PGSIZE) /
+                                          PGSIZE;
+               // round up for the contiguous page allocator
+               void *buf = get_cont_pages(LOG2_UP(num_pgs), 0);
+               a_slab->num_busy_obj = 0;
+               a_slab->num_total_obj = ROUNDUPPWR2(num_pgs)*PGSIZE / a_slab->obj_size;
+               TAILQ_INIT(&a_slab->bufctl_freelist);
+               /* for each buffer, set up a bufctl and point to the buffer */
+               for (int i = 0; i < a_slab->num_total_obj; i++) {
+                       // Initialize the object, if necessary
+                       if (cp->ctor)
+                               cp->ctor(buf, cp->obj_size);
+                       a_bufctl = kmem_cache_alloc(kmem_bufctl_cache, 0);      
+                       TAILQ_INSERT_HEAD(&a_slab->bufctl_freelist, a_bufctl, link);
+                       a_bufctl->buf_addr = buf;
+                       a_bufctl->my_slab = a_slab;
+                       // TODO: (BUF) write the bufctl reference at the bottom of the buffer.
+                       *(struct kmem_bufctl**)(buf + cp->obj_size) = a_bufctl;
+                       buf += a_slab->obj_size;
+               }
+       }
+       // add a_slab to the empty_list
+       TAILQ_INSERT_HEAD(&cp->empty_slab_list, a_slab, link);
+       spin_unlock(&cp->cache_lock);
+}
+
+/* This deallocs every slab from the empty list.  TODO: think a bit more about
+ * this.  We can do things like not free all of the empty lists to prevent
+ * thrashing.  See 3.4 in the paper. */
+void kmem_cache_reap(struct kmem_cache *cp)
+{
+       struct kmem_slab *a_slab, *next;
+       
+       // Destroy all empty slabs.  Refer to the notes about the while loop
+       spin_lock(&cp->cache_lock);
+       a_slab = TAILQ_FIRST(&cp->empty_slab_list);
+       while (a_slab) {
+               next = TAILQ_NEXT(a_slab, link);
+               kmem_slab_destroy(cp, a_slab);
+               a_slab = next;
+       }
+       spin_unlock(&cp->cache_lock);
+}
+
+void print_kmem_cache(struct kmem_cache *cp)
+{
+       spin_lock(&cp->cache_lock);
+       printk("\nPrinting kmem_cache:\n---------------------\n");
+       printk("Name: %s\n", cp->name);
+       printk("Objsize: %d\n", cp->obj_size);
+       printk("Align: %d\n", cp->align);
+       printk("Flags: 0x%08x\n", cp->flags);
+       printk("Constructor: 0x%08x\n", cp->ctor);
+       printk("Destructor: 0x%08x\n", cp->dtor);
+       printk("Slab Full: 0x%08x\n", cp->full_slab_list);
+       printk("Slab Partial: 0x%08x\n", cp->partial_slab_list);
+       printk("Slab Empty: 0x%08x\n", cp->empty_slab_list);
+       spin_unlock(&cp->cache_lock);
+}
+
+void print_kmem_slab(struct kmem_slab *slab)
+{
+       printk("\nPrinting kmem_slab:\n---------------------\n");
+       printk("Objsize: %d (%p)\n", slab->obj_size, slab->obj_size);
+       printk("NumBusy: %d\n", slab->num_busy_obj);
+       printk("Num_total: %d\n", slab->num_total_obj);
+       if (slab->obj_size + sizeof(uintptr_t) < SLAB_LARGE_CUTOFF) {
+               printk("Free Small obj: 0x%08x\n", slab->free_small_obj);
+               void *buf = slab->free_small_obj;
+               for (int i = 0; i < slab->num_total_obj; i++) {
+                       printk("Addr of buf: 0x%08x, Addr of next: 0x%08x\n", buf,
+                              *((uintptr_t**)buf));
+                       buf += slab->obj_size;
+               }
+       } else {
+               printk("This is a big slab!\n");
+       }
+}
+
index 6ef113b..916cd04 100644 (file)
@@ -26,6 +26,8 @@
 #include <pmap.h>
 #include <page_alloc.h>
 #include <pmap.h>
+#include <slab.h>
+#include <kmalloc.h>
 
 #ifdef __i386__
 
@@ -793,3 +795,60 @@ void test_active_messages(void)
        return;
 }
 #endif // __i386__
+
+static void test_single_cache(int iters, size_t size, int align, int flags,
+                              void (*ctor)(void *, size_t),
+                              void (*dtor)(void *, size_t))
+{
+       struct kmem_cache *test_cache;
+       void *objects[iters];
+       test_cache = kmem_cache_create("test_cache", size, align, flags, ctor, dtor);
+       printk("Testing Kmem Cache:\n");
+       print_kmem_cache(test_cache);
+       for (int i = 0; i < iters; i++) {
+               objects[i] = kmem_cache_alloc(test_cache, 0);
+               printk("Buffer %d addr = %p\n", i, objects[i]);
+       }
+       for (int i = 0; i < iters; i++) {
+               kmem_cache_free(test_cache, objects[i]);
+       }
+       kmem_cache_destroy(test_cache);
+       printk("\n\n\n\n");
+}
+
+void test_slab(void)
+{
+       void a_ctor(void *buf, size_t size)
+       {
+               printk("constructin tests\n");
+       }
+       void a_dtor(void *buf, size_t size)
+       {
+               printk("destructin tests\n");
+       }
+       test_single_cache(10, 128, 512, 0, 0, 0);
+       test_single_cache(10, 128, 4, 0, a_ctor, a_dtor);
+       test_single_cache(10, 1024, 16, 0, 0, 0);
+}
+
+void test_kmalloc(void)
+{
+       printk("Testing Kmalloc\n");
+       void *bufs[NUM_KMALLOC_CACHES + 1];     
+       size_t size;
+       for (int i = 0; i < NUM_KMALLOC_CACHES + 1; i++){
+               size = (KMALLOC_SMALLEST << i) - KMALLOC_OFFSET;
+               bufs[i] = kmalloc(size, 0);
+               printk("Size %d, Addr = %p\n", size, bufs[i]);
+       }
+       for (int i = 0; i < NUM_KMALLOC_CACHES; i++) {
+               printk("Freeing buffer %d\n", i);
+               kfree(bufs[i]);
+       }
+       printk("Testing a large kmalloc\n");
+       size = (KMALLOC_LARGEST << 2);
+       bufs[0] = kmalloc(size, 0);
+       printk("Size %d, Addr = %p\n", size, bufs[0]);
+       kfree(bufs[0]);
+}
+