Created student weenix repository

1 files changed, 550 insertions, 0 deletions

diff --git a/kernel/mm/slab.c b/kernel/mm/slab.c
new file mode 100644
index 0000000..bec70d1
--- /dev/null
+++ b/kernel/mm/slab.c
@@ -0,0 +1,550 @@
+// SMP.1 + SMP.3
+// spinlocks + mask interrupts
+/*
+ * slab_alloc.c - Kernel memory allocator
+ * Jason Lango <jal@cs.brown.edu>
+ *
+ * This implementation is based on the description of slab allocation
+ * (used in Solaris and Linux) from UNIX Internals: The New Frontiers,
+ * by Uresh Vahalia.
+ *
+ * Note that there is no need for locking in allocation and deallocation because
+ * it never blocks nor is used by an interrupt handler. Hurray for non
+ * preemptible kernels!
+ *
+ * darmanio: ^ lol, look at me now :D
+ */
+
+#include "types.h"
+
+#include "mm/mm.h"
+#include "mm/page.h"
+#include "mm/slab.h"
+
+#include "proc/spinlock.h"
+
+#include "util/debug.h"
+#include "util/gdb.h"
+#include "util/string.h"
+
+#ifdef SLAB_REDZONE
+#define front_rz(obj) (*(uintptr_t *)(obj))
+#define rear_rz(cache, obj)                                    \
+    (*(uintptr_t *)(((uintptr_t)(obj)) + (cache)->sa_objsize - \
+                    sizeof(uintptr_t)))
+
+#define VERIFY_REDZONES(cache, obj)                                   \
+    do                                                                \
+    {                                                                 \
+        if (front_rz(obj) != SLAB_REDZONE)                            \
+            panic("alloc: red-zone check failed: *(0x%p)=0x%.8lx\n",  \
+                  (void *)&front_rz(obj), front_rz(obj));             \
+        if (rear_rz(cache, obj) != SLAB_REDZONE)                      \
+            panic("alloc: red-zone check failed: *(0x%p)=0x%.8lx\n",  \
+                  (void *)&rear_rz(cache, obj), rear_rz(cache, obj)); \
+    } while (0);
+
+#endif
+
+struct slab
+{
+    struct slab *s_next; /* link on list of slabs */
+    size_t s_inuse;      /* number of allocated objs */
+    void *s_free;        /* head of obj free list */
+    void *s_addr;        /* start address */
+};
+
+typedef struct slab_allocator
+{
+    const char *sa_name;            /* user-provided name */
+    size_t sa_objsize;              /* object size */
+    struct slab *sa_slabs;          /* head of slab list */
+    size_t sa_order;                /* npages = (1 << order) */
+    size_t sa_slab_nobjs;           /* number of objs per slab */
+    struct slab_allocator *sa_next; /* link on global list of allocators */
+} slab_allocator_t;
+
+/* Stored at the end of every object to keep track of the 
+   associated slab when allocated or a pointer to the next free object */
+typedef struct slab_bufctl
+{
+    union {
+        void *sb_next;        /* next free object */
+        struct slab *sb_slab; /* containing slab */
+    } u;
+#ifdef SLAB_CHECK_FREE
+    uint8_t sb_free; /* true if is object is free */
+#endif
+} slab_bufctl_t;
+#define sb_next u.sb_next
+#define sb_slab u.sb_slab
+
+/* Returns a pointer to the start of the bufctl struct */
+#define obj_bufctl(allocator, obj) \
+    ((slab_bufctl_t *)(((uintptr_t)(obj)) + (allocator)->sa_objsize))
+/* Given a pointer to bufctrl, returns a pointer to the start of the object */
+#define bufctl_obj(allocator, buf) \
+    ((void *)(((uintptr_t)(buf)) - (allocator)->sa_objsize))
+/* Given a pointer to the object, returns a pointer to the next object (after bufctl) */
+#define next_obj(allocator, obj)                             \
+    ((void *)(((uintptr_t)(obj)) + (allocator)->sa_objsize + \
+              sizeof(slab_bufctl_t)))
+
+GDB_DEFINE_HOOK(slab_obj_alloc, void *addr, slab_allocator_t *allocator)
+
+GDB_DEFINE_HOOK(slab_obj_free, void *addr, slab_allocator_t *allocator)
+
+/* Head of global list of slab allocators. This is used in the python gdb script */
+static slab_allocator_t *slab_allocators = NULL;
+
+/* Special case - allocator for allocation of slab_allocator objects. */
+static slab_allocator_t slab_allocator_allocator;
+
+/*
+ * This constant defines how many orders of magnitude (in page block
+ * sizes) we'll search for an optimal slab size (past the smallest
+ * possible slab size).
+ */
+#define SLAB_MAX_ORDER 5
+
+/**
+ * Given the object size and the number of objects, calculates
+ * the size of the slab. Each object includes a slab_bufctl_t, 
+ * and each slab includes a slab struct. 
+*/
+static size_t _slab_size(size_t objsize, size_t nobjs)
+{
+    return (nobjs * (objsize + sizeof(slab_bufctl_t)) + sizeof(struct slab));
+}
+
+/**
+ * Given the object size and the order, calculate how many objects
+ * can fit in a certain number of pages (excluding the slab struct). 
+ * 
+ * PAGE_SIZE << order effectively is just PAGE_SIZE * 2^order. 
+*/
+static size_t _slab_nobjs(size_t objsize, size_t order)
+{
+    return (((PAGE_SIZE << order) - sizeof(struct slab)) /
+            (objsize + sizeof(slab_bufctl_t)));
+}
+
+static size_t _slab_waste(size_t objsize, size_t order)
+{
+    /* Waste is defined as the amount of unused space in the page
+     * block, that is the number of bytes in the page block minus
+     * the optimal slab size for that particular block size.
+     */
+    return ((PAGE_SIZE << order) -
+            _slab_size(objsize, _slab_nobjs(objsize, order)));
+}
+
+static void _calc_slab_size(slab_allocator_t *allocator)
+{
+    size_t best_order;
+    size_t best_waste;
+    size_t order;
+    size_t minorder;
+    size_t minsize;
+    size_t waste;
+
+    /* Find the minimum page block size that this slab requires. */
+    minsize = _slab_size(allocator->sa_objsize, 1);
+    for (minorder = 0; minorder < PAGE_NSIZES; minorder++)
+    {
+        if ((PAGE_SIZE << minorder) >= minsize)
+        {
+            break;
+        }
+    }
+    if (minorder == PAGE_NSIZES)
+        panic("unable to find minorder\n");
+
+    /* Start the search with the minimum block size for this slab. */
+    best_order = minorder;
+    best_waste = _slab_waste(allocator->sa_objsize, minorder);
+
+    dbg(DBG_MM, "calc_slab_size: minorder %lu, waste %lu\n", minorder,
+        best_waste);
+
+    /* Find the optimal number of objects per slab and slab size,
+     * up to a predefined (somewhat arbitrary) limit on the number
+     * of pages per slab.
+     */
+    for (order = minorder + 1; order < SLAB_MAX_ORDER; order++)
+    {
+        if ((waste = _slab_waste(allocator->sa_objsize, order)) < best_waste)
+        {
+            best_waste = waste;
+            best_order = order;
+            dbg(DBG_MM, "calc_slab_size: replacing with order %lu, waste %lu\n",
+                best_order, best_waste);
+        }
+    }
+
+    /* Finally, the best page block size wins.
+     */
+    allocator->sa_order = best_order;
+    allocator->sa_slab_nobjs = _slab_nobjs(allocator->sa_objsize, best_order);
+    KASSERT(allocator->sa_slab_nobjs);
+}
+
+/*
+ * Initializes a given allocator using the name and size passed in. 
+*/
+static void _allocator_init(slab_allocator_t *allocator, const char *name,
+                            size_t size)
+{
+#ifdef SLAB_REDZONE
+    /*
+     * Add space for the front and rear red-zones.
+     */
+    size += 2 * sizeof(uintptr_t);
+#endif
+
+    if (!name)
+    {
+        name = "<unnamed>";
+    }
+
+    allocator->sa_name = name;
+    allocator->sa_objsize = size;
+    allocator->sa_slabs = NULL;
+    // this will set the fields sa_order and the number of objects per slab
+    _calc_slab_size(allocator);
+
+    /* Add cache to global cache list. */
+    allocator->sa_next = slab_allocators;
+    slab_allocators = allocator;
+
+    dbg(DBG_MM, "Initialized new slab allocator:\n");
+    dbgq(DBG_MM, "  Name:          \"%s\" (0x%p)\n", allocator->sa_name,
+         allocator);
+    dbgq(DBG_MM, "  Object Size:   %lu\n", allocator->sa_objsize);
+    dbgq(DBG_MM, "  Order:         %lu\n", allocator->sa_order);
+    dbgq(DBG_MM, "  Slab Capacity: %lu\n", allocator->sa_slab_nobjs);
+}
+
+/*
+ * Given a name and size of object will create a slab_allocator
+ * to manage slabs that store objects of size `size`, along with 
+ * some metadata. 
+*/
+slab_allocator_t *slab_allocator_create(const char *name, size_t size)
+{
+    slab_allocator_t *allocator;
+
+    allocator = (slab_allocator_t *)slab_obj_alloc(&slab_allocator_allocator);
+    if (!allocator)
+    {
+        return NULL;
+    }
+
+    _allocator_init(allocator, name, size);
+    return allocator;
+}
+
+/*
+ * Free a given allocator. 
+*/
+void slab_allocator_destroy(slab_allocator_t *allocator)
+{
+    slab_obj_free(&slab_allocator_allocator, allocator);
+}
+
+/*
+ * In the event that a slab with free objects is not found, 
+ * this routine will be called. 
+*/
+static long _slab_allocator_grow(slab_allocator_t *allocator)
+{
+    void *addr;
+    void *obj;
+    struct slab *slab;
+
+    addr = page_alloc_n(1UL << allocator->sa_order);
+    if (!addr)
+    {
+        return 0;
+    }
+
+    /* Initialize each bufctl to be free and point to the next object. */
+    obj = addr;
+    for (size_t i = 0; i < (allocator->sa_slab_nobjs - 1); i++)
+    {
+#ifdef SLAB_CHECK_FREE
+        obj_bufctl(allocator, obj)->sb_free = 1;
+#endif
+        obj = obj_bufctl(allocator, obj)->sb_next = next_obj(allocator, obj);
+    }
+
+    /* The last bufctl is the tail of the list. */
+#ifdef SLAB_CHECK_FREE
+    obj_bufctl(allocator, obj)->sb_free = 1;
+#endif
+    obj_bufctl(allocator, obj)->sb_next = NULL;
+
+    /* After the last object comes the slab structure itself. */
+    slab = (struct slab *)next_obj(allocator, obj);
+
+    /*
+     * The first object in the slab will be the head of the free
+     * list and the start address of the slab.
+     */
+    slab->s_free = addr;
+    slab->s_addr = addr;
+    slab->s_inuse = 0;
+
+    /* Initialize objects. */
+    obj = addr;
+    for (size_t i = 0; i < allocator->sa_slab_nobjs; i++)
+    {
+#ifdef SLAB_REDZONE
+        front_rz(obj) = SLAB_REDZONE;
+        rear_rz(allocator, obj) = SLAB_REDZONE;
+#endif
+        obj = next_obj(allocator, obj);
+    }
+
+    dbg(DBG_MM, "Growing cache \"%s\" (0x%p), new slab 0x%p (%lu pages)\n",
+        allocator->sa_name, allocator, slab, 1UL << allocator->sa_order);
+
+    /* Place this slab into the cache. */
+    slab->s_next = allocator->sa_slabs;
+    allocator->sa_slabs = slab;
+
+    return 1;
+}
+
+/*
+ * Given an allocator, will allocate an object.  
+*/
+void *slab_obj_alloc(slab_allocator_t *allocator)
+{
+    struct slab *slab;
+    void *obj;
+
+    /* Find a slab with a free object. */
+    for (;;)
+    {
+        slab = allocator->sa_slabs;
+        while (slab && (slab->s_inuse == allocator->sa_slab_nobjs))
+            slab = slab->s_next;
+        if (slab && (slab->s_inuse < allocator->sa_slab_nobjs))
+        {
+            break;
+        }
+        if (!_slab_allocator_grow(allocator))
+        {
+            return NULL;
+        }
+    }
+
+    /*
+     * Remove an object from the slab's free list.  We'll use the
+     * free list pointer to store a pointer back to the containing
+     * slab.
+     */
+    obj = slab->s_free;
+    slab->s_free = obj_bufctl(allocator, obj)->sb_next;
+    obj_bufctl(allocator, obj)->sb_slab = slab;
+#ifdef SLAB_CHECK_FREE
+    obj_bufctl(allocator, obj)->sb_free = 0;
+#endif
+
+    slab->s_inuse++;
+
+    dbg(DBG_MM,
+        "Allocated object 0x%p from \"%s\" (0x%p), "
+        "slab 0x%p, inuse %lu\n",
+        obj, allocator->sa_name, allocator, allocator, slab->s_inuse);
+
+#ifdef SLAB_REDZONE
+    VERIFY_REDZONES(allocator, obj);
+
+    /*
+     * Make object pointer point past the first red-zone.
+     */
+    obj = (void *)((uintptr_t)obj + sizeof(uintptr_t));
+#endif
+
+    GDB_CALL_HOOK(slab_obj_alloc, obj, allocator);
+    return obj;
+}
+
+void slab_obj_free(slab_allocator_t *allocator, void *obj)
+{
+    struct slab *slab;
+    GDB_CALL_HOOK(slab_obj_free, obj, allocator);
+
+#ifdef SLAB_REDZONE
+    /* Move pointer back to verify that the REDZONE is unchanged. */
+    obj = (void *)((uintptr_t)obj - sizeof(uintptr_t));
+
+    VERIFY_REDZONES(allocator, obj);
+#endif
+
+#ifdef SLAB_CHECK_FREE
+    KASSERT(!obj_bufctl(allocator, obj)->sb_free && "INVALID FREE!");
+    obj_bufctl(allocator, obj)->sb_free = 1;
+#endif
+
+    slab = obj_bufctl(allocator, obj)->sb_slab;
+
+    /* Place this object back on the slab's free list. */
+    obj_bufctl(allocator, obj)->sb_next = slab->s_free;
+    slab->s_free = obj;
+
+    slab->s_inuse--;
+
+    dbg(DBG_MM, "Freed object 0x%p from \"%s\" (0x%p), slab 0x%p, inuse %lu\n",
+        obj, allocator->sa_name, allocator, slab, slab->s_inuse);
+}
+
+/*
+ * Reclaims as much memory (up to a target) from
+ * unused slabs as possible
+ * @param target - target number of pages to reclaim. If negative,
+ * try to reclaim as many pages as possible
+ * @return number of pages freed
+ */
+long slab_allocators_reclaim(long target)
+{
+    panic("slab_allocators_reclaim NYI for SMP");
+    // spinlock_lock(&allocator->sa_lock);
+    //     int npages_freed = 0, npages;
+
+    //     slab_allocator_t *a;
+    //     struct slab *s, **prev;
+
+    //     /* Go through all caches */
+    //     for (a = slab_allocators; NULL != a; a = a->sa_next) {
+    //             prev = &(a->sa_slabs);
+    //             s = a->sa_slabs;
+    //             while (NULL != s) {
+    //                     struct slab *next = s->s_next;
+    //                     if (0 == s->s_inuse) {
+    //                             /* Free Slab */
+    //                             (*prev) = next;
+    //                             npages = 1 << a->sa_order;
+
+    //                             page_free_n(s->s_addr, npages);
+    //                             npages_freed += npages;
+    //                     } else {
+    //                             prev = &(s->s_next);
+    //                     }
+    //                     /* Check if target was met */
+    //                     if ((target > 0) && (npages_freed >= target)) {
+    //                             return npages_freed;
+    //                     }
+    //                     s = next;
+    //             }
+    //     }
+    // spinlock_unlock(&allocator->sa_lock);
+    //     return npages_freed;
+}
+
+#define KMALLOC_SIZE_MIN_ORDER (6)
+#define KMALLOC_SIZE_MAX_ORDER (18)
+
+static slab_allocator_t
+    *kmalloc_allocators[KMALLOC_SIZE_MAX_ORDER - KMALLOC_SIZE_MIN_ORDER + 1];
+
+/* Note that kmalloc_allocator_names should be modified to remain consistent
+ * with KMALLOC_SIZE_MIN_ORDER ... KMALLOC_SIZE_MAX_ORDER.
+ */
+static const char *kmalloc_allocator_names[] = {
+    "size-64", "size-128", "size-256", "size-512", "size-1024",
+    "size-2048", "size-4096", "size-8192", "size-16384", "size-32768",
+    "size-65536", "size-131072", "size-262144"};
+
+void *kmalloc(size_t size)
+{
+    size += sizeof(slab_allocator_t *);
+
+    /*
+     * Find the first power of two bucket bigger than the
+     * requested size, and allocate from it.
+     */
+    slab_allocator_t **cs = kmalloc_allocators;
+    for (size_t order = KMALLOC_SIZE_MIN_ORDER; order <= KMALLOC_SIZE_MAX_ORDER;
+         order++, cs++)
+    {
+        if ((1UL << order) >= size)
+        {
+            void *addr = slab_obj_alloc(*cs);
+            if (!addr)
+            {
+                dbg(DBG_MM, "WARNING: kmalloc out of memory\n");
+                return NULL;
+            }
+#ifdef MM_POISON
+            memset(addr, MM_POISON_ALLOC, size);
+#endif /* MM_POISON */
+            *((slab_allocator_t **)addr) = *cs;
+            return (void *)(((slab_allocator_t **)addr) + 1);
+        }
+    }
+
+    panic("size bigger than maxorder %ld\n", size);
+}
+
+__attribute__((used)) static void *malloc(size_t size)
+{
+    /* This function is used by gdb to allocate memory
+     * within the kernel, no code in the kernel should
+     * call it. */
+    return kmalloc(size);
+}
+
+void kfree(void *addr)
+{
+    addr = (void *)(((slab_allocator_t **)addr) - 1);
+    slab_allocator_t *sa = *(slab_allocator_t **)addr;
+
+#ifdef MM_POISON
+    /* If poisoning is enabled, wipe the memory given in
+     * this object, as specified by the cache object size
+     * (minus red-zone overhead, if any).
+     */
+    size_t objsize = sa->sa_objsize;
+#ifdef SLAB_REDZONE
+    objsize -= sizeof(uintptr_t) * 2;
+#endif /* SLAB_REDZONE */
+    memset(addr, MM_POISON_FREE, objsize);
+#endif /* MM_POISON */
+
+    slab_obj_free(sa, addr);
+}
+
+__attribute__((used)) static void free(void *addr)
+{
+    /* This function is used by gdb to free memory allocated
+     * by malloc, no code in the kernel should call it. */
+    kfree(addr);
+}
+
+void slab_init()
+{
+    /* Special case initialization of the allocator for `slab_allocator_t`s */
+    /* In other words, initializes a slab allocator for other slab allocators. */
+    _allocator_init(&slab_allocator_allocator, "slab_allocators",
+                    sizeof(slab_allocator_t));
+
+    /*
+     * Allocate the power of two buckets for generic
+     * kmalloc/kfree.
+     */
+    slab_allocator_t **cs = kmalloc_allocators;
+    for (size_t order = KMALLOC_SIZE_MIN_ORDER; order <= KMALLOC_SIZE_MAX_ORDER;
+         order++, cs++)
+    {
+        if (NULL ==
+            (*cs = slab_allocator_create(
+                 kmalloc_allocator_names[order - KMALLOC_SIZE_MIN_ORDER],
+                 (1UL << order))))
+        {
+            panic("Couldn't create kmalloc allocators!\n");
+        }
+    }
+}