First draft of objcache code
authorJack Miller <jack@codezen.org>
Mon, 28 Mar 2016 21:46:42 +0000 (16:46 -0500)
committerJack Miller <jack@codezen.org>
Mon, 28 Mar 2016 21:46:42 +0000 (16:46 -0500)
TODO:
    - free and destroy, move tests

include/kernel.h
include/math.h [new file with mode: 0644]
include/objcache.h [new file with mode: 0644]
kernel/main.c
mm/objcache.c [new file with mode: 0644]

index 0fbb1b5..3781b5d 100644 (file)
@@ -7,3 +7,4 @@
 #include <page_alloc.h>
 #include <errno.h>
 #include <string.h>
+#include <math.h>
diff --git a/include/math.h b/include/math.h
new file mode 100644 (file)
index 0000000..7c05e88
--- /dev/null
@@ -0,0 +1,6 @@
+#pragma once
+
+#define min(x, y) (((x) < (y)) ? (x) : (y))
+#define max(x, y) (((x) > (y)) ? (x) : (y))
+
+#define DIV_ROUND_UP(x, y) (((x) / (y)) + min((x) % (y), 1))
diff --git a/include/objcache.h b/include/objcache.h
new file mode 100644 (file)
index 0000000..aef5535
--- /dev/null
@@ -0,0 +1,34 @@
+/* vim: set ts=4 sw=4 sts=4 noet : */
+
+#pragma once
+
+#include <kernel.h>
+
+#include <asm/spinlock.h>
+
+struct objcache {
+    u32 obj_size;
+
+       void *current_page;
+
+       DEFINE_SPINLOCK(lock);  
+};
+
+#define MIN_OBJ_SIZE 8
+
+/* How many bits do we need to track every object */
+#define OVERHEAD_BITS(x)               (PAGE_SIZE / (x)->obj_size)
+
+/* How many u64s does that translate into? +1 for next ptr */
+#define OVERHEAD_LONGS(x)              (DIV_ROUND_UP(OVERHEAD_BITS(x), 64) + 1)
+
+/* How many objects is that ? */
+#define OVERHEAD_OBJECTS(x)            DIV_ROUND_UP(OVERHEAD_LONGS(x), ((x)->obj_size / 8))
+
+#define INITIAL_MASK(x)                        ((1 << OVERHEAD_OBJECTS(x)) - 1)
+
+#define OBJCACHE(t) { .obj_size = max(sizeof(t), MIN_OBJ_SIZE) }
+
+#define DEFINE_OBJCACHE(n, t) struct objcache (n) = OBJCACHE(t)
+
+void *objcache_get(struct objcache *objcache);
index d04c940..f57fffe 100644 (file)
@@ -9,8 +9,22 @@
 
 #include <asm/cpuid.h>
 
+#include <objcache.h>
+
+struct test_struct {
+       u64 a;
+       u64 b;
+       u64 c;
+       u64 d;
+};
+
+DEFINE_OBJCACHE(test_cache, struct test_struct);
+
 void main (void *info_phys, unsigned long end_structures)
 {
+       struct test_struct *ta, *tb;
+       int i;
+
        page_alloc_init(info_phys, end_structures);
 
        vga_init();
@@ -31,6 +45,17 @@ void main (void *info_phys, unsigned long end_structures)
        /* ACPI init probes ACPI tables and generates smp_wake calls */
        acpi_init();
 
+       /* test struct is 32 bytes, with one object worth of overhead in the cache
+        * which means 128 allocs should get us to roll over into another page
+        */
+
+       for (i = 0; i < 128; i++) {
+               tb = ta;
+               ta = objcache_get(&test_cache);
+               if (PAGE_ALIGN((u64) tb) != PAGE_ALIGN((u64) ta))
+                       printk("[%d]\n", i);
+       }
+
        asm ("sti" : : );
 
        asm ("hlt" : : );
diff --git a/mm/objcache.c b/mm/objcache.c
new file mode 100644 (file)
index 0000000..5b9c7b1
--- /dev/null
@@ -0,0 +1,136 @@
+/* vim: set ts=4 sw=4 sts=4 noet : */
+
+/* Objcache is an implementation of a localized general memory allocator */
+
+/* Where the domain allocator is designed to deal with arbitrary sized
+ * allocations over huge ranges of numbers, the objcache is designed to
+ * efficiently pack small(ish) objects into pages with as little overhead as
+ * possible.
+ *
+ * It achieve the bare minimum of overhead by using a sized bitmap at the top
+ * of each page and a next ptr, leading to between 16 and 72 bytes of overhead
+ * per page depending on the object size (min 8 bytes).
+ *
+ * It circumvents the usual issue of bitmap bookkeeping by having a constant
+ * allocation size.
+ */
+
+#include <kernel.h>
+#include <objcache.h>
+
+static inline int __bitmap_first_zero(u64 val)
+{
+       int ret = 0;
+
+       if (val == ((u64) -1))
+               return -1;
+
+       while (val % 2) {
+               val >>= 1;
+               ret++;
+       }
+
+       return ret;
+}
+
+static inline int __bitmap_first_zero_in_page(int bitmap_longs, void *ptr)
+{
+       u64 *page = ptr;
+       int i, ret;
+
+       for (i = 0; i < bitmap_longs; i++) {
+               ret = __bitmap_first_zero(page[i]);
+               if (ret >= 0)
+                       return (i * 64) + ret;
+       }
+
+       return -1;
+}
+
+static int __bitmap_overall_first_zero(struct objcache *objcache, void **retptr)
+{
+       int bitmap_longs = OVERHEAD_LONGS(objcache) - 1;
+       int ret;
+       void *cur;
+
+       cur = objcache->current_page;
+
+       while(cur) {
+               ret = __bitmap_first_zero_in_page(bitmap_longs, cur);
+
+               if (ret >= 0) {
+                       *retptr = cur;
+                       return ret;
+               }
+
+               cur = (void *) (((u64 *) cur)[bitmap_longs]);
+       }
+
+       return -1;
+}
+
+static int __oc_bump_allocation(struct objcache *objcache, void **page)
+{
+       int bitmap_longs = OVERHEAD_LONGS(objcache) - 1;
+       u64 *new_page = page_alloc(0);
+       u64 *cur;
+       int i;
+
+       if (!new_page)
+               return -1;
+
+       /* Init bitmap and next ptr */
+
+       new_page[0] = INITIAL_MASK(objcache);
+       for (i = 1; i <= bitmap_longs; i++)
+               new_page[i] = 0;
+
+       *page = new_page;
+
+       if (!objcache->current_page) {
+               objcache->current_page = new_page;
+               return 0;
+       }
+
+       cur = objcache->current_page;
+       while (cur) {
+               if (cur[bitmap_longs] == 0) {
+                       cur[bitmap_longs] = (u64) new_page;
+                       break;
+               }
+
+               cur = (void *) ((u64) cur[bitmap_longs]);
+       }
+
+       return 0;
+}
+
+void *objcache_get(struct objcache *objcache)
+{
+       u64 *page;
+       int ret;
+
+       ret = __bitmap_overall_first_zero(objcache, (void **) &page);
+
+       if (ret == -1) {
+               if (__oc_bump_allocation(objcache, (void **) &page))
+                       return NULL;
+               ret = OVERHEAD_OBJECTS(objcache);
+       }
+
+       page[ret / 64] |= (1UL << (ret % 64));
+
+       return (void *) (((u64) page) + (ret * objcache->obj_size));
+}
+
+void objcache_free(struct objcache *objcache, void *obj)
+{
+}
+
+void objcache_init(struct objcache *objcache, u32 obj_size)
+{
+    if (obj_size > MIN_OBJ_SIZE)
+        objcache->obj_size = obj_size;
+    else
+        objcache->obj_size = MIN_OBJ_SIZE;
+}