Rework objcache
authorJack Miller <jack@codezen.org>
Mon, 25 Apr 2016 04:30:26 +0000 (23:30 -0500)
committerJack Miller <jack@codezen.org>
Mon, 25 Apr 2016 04:30:26 +0000 (23:30 -0500)
Using Mike Pall's quad-color GC arena as inspiration (from the proposed
LuaJIT 3.0 GC) implement an "arena"

The inspiration for this idea was similar to my own with the objcache -
a localized bitmap allocator - but has some definite improvements.

First, it allows variable sized objects, where objcache was single size.

Second, it's efficient for all object sizes, where the objcache would
waste memory at certain object sizes.

Third, it carries bits that will be relevant when implementing a quad
color GC, which is still in the future, but it doesn't hurt to hammer
out the data structure now and use those bits later.

The only down side (which isn't much) is that it has a minimum size of
64k per alloc but who's afraid of a bit of scale?

include/objcache.h
mm/objcache.c
vua/vua_parse.c
vua/vua_str.c

index 1cd1b10..1f769b9 100644 (file)
@@ -9,35 +9,20 @@
 struct objcache {
     u32 obj_size;
 
-    void *start_page;
+    void *data;
+    void *last_alloc;
+    void *next_free;
 
-     DEFINE_SPINLOCK(lock);
+    DEFINE_SPINLOCK(lock);
 };
 
-#define MIN_OBJ_SIZE 8
+#define CELL_SIZE 16
 
-/* How many bits do we need to track every object */
-#define OVERHEAD_BITS(x)               (PAGE_SIZE / (x)->obj_size)
+#define DEFINE_OBJCACHE(n) struct objcache (n) = { .lock = SPINLOCK_UNLOCKED }
 
-/* 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_
-
-#define OBJCACHE(s) { .obj_size = max(s, MIN_OBJ_SIZE) }
-
-#define DEFINE_OBJCACHE(n, t) struct objcache (n) = OBJCACHE(sizeof(t))
-
-#define DEFINE_OBJCACHE_SIZE(n, s) struct objcache (n) = OBJCACHE(s)
-
-void *objcache_get(struct objcache *objcache);
+void *objcache_get(struct objcache *objcache, u32 size);
 void objcache_free(struct objcache *objcache, void *obj);
-void objcache_init(struct objcache *objcache, u32 obj_size);
+void objcache_init(struct objcache *objcache);
 void objcache_destroy(struct objcache *objcache);
 
 #define TEST_OBJCACHE
index 9df36bd..8946149 100644 (file)
  * 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).
+ * This design was inspired by the "arena" concept planned by Mike Pall for the
+ * LuaJIT 3.0 GC. As of yet, that code hasn't landed (4/16), but the concept
+ * was pretty clear.
  *
- * It circumvents the usual issue of bitmap bookkeeping by having a constant
- * allocation size.
+ * An "arena" is a big virtually contiguous allocation of at least 64k and is
+ * comprised of 16 byte cells, which can be combined together to accomodate any
+ * reasonable allocation size. For each of these cells, you carry two bits of
+ * metadata. So in 64k you have (64k/16) = 4096 cells, and thus 8192 bits / 1k
+ * of overhead total.
+ *
+ * The 64k minimum is well chosen too, because at 64k you have enough overhead
+ * that you can assume the first (1/64th overhead of 4096 bits) = 64 bits of
+ * each bitmap is always used, which means that memory can be used for
+ * something else, like a couple of full pointers.
+ *
+ * In the mark bitmap, a garbage collector white / black is stored for each
+ * block. We don't have a GC yet, but we're planning that most of the objects
+ * in the objcache are going to be tracked by the GC eventually.
+ *
+ * In the block bitmap marks the start of each block.
+ *
+ * Block : 1 0 0 | 0 0 | 1 0
+ * Mark  : 0 0 0 | 1 0 | 1 0
+ *
+ * This translates to a white block that's three cells long, two free cells,
+ * and then a black block that's two cells long.
+ *
+ * When you allocate one of those free cells, you mark the block bit and unset
+ * the color mark bit (converting from a free block to a white block) for the
+ * initial cell and then, unless it was a perfect fit, you just set the mark
+ * bit for the first cell after your allocation. 2 or 3 writes total, without
+ * having to touch the intermediate blocks.
+ *
+ * The neat aspect of this is that you can use bit logic to operate on these
+ * many at a time, which will come in handy when we need to do stuff like
+ *
+ * Free all white objects
+ *
+ * B'=M&B  : 0 0 0 | 0 0 | 1 0 (unset all white blocks)
+ * M'=M|B  : 1 0 0 | 1 0 | 1 0 (mark all free - or set black bit again)
+ *
+ * switch all black objects to white objects at the end of a GC sweep.
+ *
+ * Block : 0 0 0 | 0 0 | 1 0
+ * M=B^M : 1 0 0 | 1 0 | 0 0 (color flips, others untouched)
+ *
+ * Anyway, even without a GC yet, this provides some benefits over our initial
+ * objcache implementation which had a variable size bitmap based on a single
+ * object size and would become inefficient with bigger allocation sizes.
  */
 
 #include <kernel.h>
 #include <objcache.h>
 
-static inline int __bitmap_first_zero(u64 val)
-{
-    int ret = 0;
+#define ALLOC_ORDER             4 /* 64k */
+#define ALLOC_SIZE              (1ULL << (PAGE_SHIFT + ALLOC_ORDER))
+#define ALLOC_MASK              (ALLOC_SIZE - 1)
+#define BASE_MASK               ~(ALLOC_MASK)
 
-    if (val == ((u64) - 1))
-        return -1;
+#define TOTAL_CELLS             (ALLOC_SIZE / CELL_SIZE)
 
-    while (val % 2) {
-        val >>= 1;
-        ret++;
-    }
+/* 2 bits per object, mark and block, expressed in different ways */
+#define OVERHEAD_BITS           (2 * TOTAL_CELLS)
+#define OVERHEAD_BYTES          (OVERHEAD_BITS / 8)
+#define OVERHEAD_LONGS          (OVERHEAD_BYTES / 8)
+#define OVERHEAD_CELLS          (OVERHEAD_BYTES / CELL_SIZE)
 
-    return ret;
-}
+#define FREE_CELLS              (TOTAL_CELLS - OVERHEAD_CELLS)
 
-static inline int __bitmap_first_zero_in_page(int bitmap_longs, void *ptr)
-{
-    u64 *page = ptr;
-    int i, ret;
+/* How many bytes of the bitmap can we assume are taken by metadata */
+#define SKIP_BYTES              (OVERHEAD_CELLS / 8)
 
-    for (i = 0; i < bitmap_longs; i++) {
-        ret = __bitmap_first_zero(page[i]);
-        if (ret >= 0)
-            return (i * 64) + ret;
-    }
+/* Given a base allocation pointer, locate various overhead structures */
 
-    return -1;
-}
+/* Yes, this is basically half-assed struct building, but eventually there will
+ * per-objcache allocation order, and these will have to be derived anyway
+ */
+
+#define OBJCACHE_PTR_NEXT(x)    ((u64 *) (x))[0]
+#define OBJCACHE_BLOCK_BMAP(x)  ((u64 *) &((u8 *)(x))[SKIP_BYTES])
+#define OBJCACHE_PTR_2(x)       ((void **) &((u8 *)(x))[OVERHEAD_BYTES / 2])
+#define OBJCACHE_MARK_BMAP(x)   ((u64 *) &((u8 *)(x))[(OVERHEAD_BYTES / 2) + SKIP_BYTES])
+#define OBJCACHE_BMAP_SIZE      ((OVERHEAD_LONGS / 2) - 1) /* To avoid the pointer at the head */
+
+/* Macros for finding base / idx from object pointer */
+#define OBJBASE(x)              ((void *) (((u64) (x)) & BASE_MASK))
+
+/* Macros to convert between idx and object. Note that the bitmap doesn't
+ * include the cells we ignore (and use for our pointer) so idx 0 is the first
+ * cell *after* our overhead, this is the only place we need to adjust for that
+ * fact.
+ */
+
+#define OBJIDX(x)               (((((u64) (x)) & ALLOC_MASK) >> 4) - OVERHEAD_CELLS)
+#define OBJCACHE_CELL(x, n)     ((void *) &((u8 *)(x))[CELL_SIZE * (n + OVERHEAD_CELLS)])
 
-static int __bitmap_overall_first_zero(struct objcache *objcache, void **retptr)
+static int __oc_find_free_cells(struct objcache *objcache, u32 cells, void **alloc)
 {
-    int bitmap_longs = OVERHEAD_LONGS(objcache) - 1;
-    int ret;
-    void *cur;
+    u64 *mark_map, *block_map;
+    u64 curbit;
 
-    cur = objcache->start_page;
+    s32 free_start = -1;
+    u32 free_here = 0;
 
-    while (cur) {
-        ret = __bitmap_first_zero_in_page(bitmap_longs, cur);
+    int i, j;
 
-        if (ret >= 0 && ret < OVERHEAD_BITS(objcache)) {
-            *retptr = cur;
-            return ret;
+    *alloc = objcache->data;
+
+    while (*alloc) {
+        mark_map = (u64 *) OBJCACHE_MARK_BMAP(*alloc);
+        block_map = (u64 *) OBJCACHE_BLOCK_BMAP(*alloc);
+
+        for(i = 0; i < OBJCACHE_BMAP_SIZE; i++) {
+            curbit = 1;
+
+            for(j = 0; j < 64; j++) {
+                if (*block_map & curbit)
+                    free_start = -1;
+                else if (*mark_map & curbit) {
+                    if (free_start >= 0) /* Merge free blocks */
+                        *mark_map &= ~(curbit);
+                    else {
+                        free_start = ((i * 64) + j);
+                        free_here = 1;
+                    }
+                } else if(free_start >= 0)
+                    free_here++;
+
+                if (free_here >= cells)
+                    return free_start;
+
+                curbit <<= 1;
+            }
+
+            mark_map++;
+            block_map++;
         }
 
-        cur = (void *)(((u64 *) cur)[bitmap_longs]);
+        *alloc = (void *) OBJCACHE_PTR_NEXT(*alloc);
     }
 
     return -1;
 }
 
-static int __oc_bump_allocation(struct objcache *objcache, void **page)
+static int __oc_bump_allocation(struct objcache *objcache)
 {
-    int bitmap_longs = OVERHEAD_LONGS(objcache) - 1;
-    u64 *new_page = page_alloc(0);
-    u64 *cur;
+    u64 *new_pages = page_alloc(ALLOC_ORDER);
+    u64 *mark_map, *block_map;
     int i;
 
-    if (!new_page)
+    if (!new_pages)
         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;
+    OBJCACHE_PTR_NEXT(new_pages) = 0x0;
+    mark_map = (u64 *) OBJCACHE_MARK_BMAP(new_pages);
+    block_map = (u64 *) OBJCACHE_BLOCK_BMAP(new_pages);
 
-    if (!objcache->start_page) {
-        objcache->start_page = new_page;
-        return 0;
+    for (i = 0; i <= OBJCACHE_BMAP_SIZE; i++) {
+        block_map[i] = 0x0;
+        mark_map[i] = 0x0;
     }
 
-    cur = objcache->start_page;
-    while (cur) {
-        if (cur[bitmap_longs] == 0) {
-            cur[bitmap_longs] = (u64) new_page;
-            break;
-        }
+    /* Start with a free block definition, mark = 1, block = 0 */
+    mark_map[0] = 0x1;
 
-        cur = (void *)((u64) cur[bitmap_longs]);
-    }
+    if (!objcache->data)
+        objcache->data = new_pages;
+    else
+        OBJCACHE_PTR_NEXT(objcache->last_alloc) = (u64) new_pages;
 
+    objcache->last_alloc = new_pages;
+    objcache->next_free = OBJCACHE_CELL(new_pages, OVERHEAD_CELLS);
     return 0;
 }
 
-static int __oc_page_empty(struct objcache *objcache, u64 * page)
+void *objcache_get(struct objcache *objcache, u32 size)
 {
-    int bitmap_longs = OVERHEAD_LONGS(objcache) - 1;
-    int i;
+    u64 *page;
+    u64 *mark_map, *block_map;
+    int idx;
+    void *ret;
 
-    if (page[0] != INITIAL_MASK(objcache))
-        return 0;
+    idx = __oc_find_free_cells(objcache, size / CELL_SIZE, (void **) &page);
 
-    for (i = 1; i < bitmap_longs; i++) {
-        if (page[i] != 0)
-            return 0;
+    if (idx == -1) {
+        if (__oc_bump_allocation(objcache))
+            return NULL;
+        page = objcache->last_alloc;
+        idx = 0;
     }
 
-    return 1;
+    block_map = OBJCACHE_BLOCK_BMAP(page);
+    mark_map = OBJCACHE_MARK_BMAP(page);
+    ret = OBJCACHE_CELL(page, idx);
+
+    /* Turn this index into a white block */
+    block_map[idx / 64] |= (1UL << (idx % 64));
+    mark_map[idx / 64] &= ~(1UL << (idx % 64));
+
+    /* Turn the following block, if free, into a free header */
+    idx += (size / CELL_SIZE);
+
+    if (!(block_map[idx / 64] & (1UL << (idx % 64))))
+        mark_map[idx / 64] |= (1UL << (idx % 64));
+
+    return ret;
 }
 
-void *objcache_get(struct objcache *objcache)
+/*
+static int __oc_alloc_empty(u64 * page)
 {
-    u64 *page;
-    int ret;
-
-    ret = __bitmap_overall_first_zero(objcache, (void **)&page);
+    u64 *bmap = OBJCACHE_BLOCK_BMAP(page);
+    int i;
 
-    if (ret == -1) {
-        if (__oc_bump_allocation(objcache, (void **)&page))
-            return NULL;
-        ret = OVERHEAD_OBJECTS(objcache);
+    for (i = 0; i < OBJCACHE_BMAP_SIZE; i++) {
+        if (bmap[i] != 0)
+            return 0;
     }
 
-    page[ret / 64] |= (1UL << (ret % 64));
-
-    return (void *)(((u64) page) + (ret * objcache->obj_size));
+    return 1;
 }
+*/
 
 void objcache_free(struct objcache *objcache, void *obj)
 {
-    u64 bitmap_longs = OVERHEAD_LONGS(objcache) - 1;
-    u64 *page = objcache->start_page;
-    u64 *prev = NULL;
-    int idx;
+    void *base = OBJBASE(obj);
+    u64 *block_map = OBJCACHE_BLOCK_BMAP(base);
+    u64 *mark_map = OBJCACHE_MARK_BMAP(base);
 
-    while (page) {
-        if (PAGE_ALIGN((u64) obj) == (u64) page) {
-            idx = ((u64) obj - (u64) page) / objcache->obj_size;
-            page[idx / 64] &= ~(1UL << (idx % 64));
-
-            if (__oc_page_empty(objcache, page)) {
-                if (prev)
-                    prev[bitmap_longs] = page[bitmap_longs];
-                else
-                    objcache->start_page = (void *)page[bitmap_longs];
-                page_alloc_free(page);
-            }
-            break;
-        }
+    int idx = OBJIDX(obj);
+    int longidx = idx / 64;
+    u64 bit = (1UL << (idx % 64));
 
-        prev = page;
-        page = (void *)page[bitmap_longs];
-    }
+    assert(obj == OBJCACHE_CELL(base, idx));
+
+    block_map[longidx] &= ~bit;
+    mark_map[longidx] |= bit;
+
+    /* TODO free whole alloc if __oc_alloc_empty() */
+
+    /* We probably want a better way to check if a page is totally empty than
+     * checking the whole bitmap, perhaps the 64 bit value we're not using
+     * using could be a compressed bitmap we could update?
+     */
 }
 
 void objcache_destroy(struct objcache *objcache)
 {
-    u64 bitmap_longs = OVERHEAD_LONGS(objcache) - 1;
-    u64 *cur = objcache->start_page;
+    u64 *cur = objcache->data;
     u64 *next;
 
     while(cur) {
-        next = (u64 *) cur[bitmap_longs];
+        next = (u64 *) OBJCACHE_PTR_NEXT(cur);
         page_alloc_free(cur);
         cur = next;
     }
 
-    objcache->start_page = NULL;
+    objcache->data = NULL;
 }
 
-void objcache_init(struct objcache *objcache, u32 obj_size)
+void objcache_init(struct objcache *objcache)
 {
-    if (obj_size > MIN_OBJ_SIZE)
-        objcache->obj_size = obj_size;
-    else
-        objcache->obj_size = MIN_OBJ_SIZE;
+    objcache->data = NULL;
+    objcache->last_alloc = NULL;
+    objcache->next_free = NULL;
+
+    spinlock_init(&objcache->lock, 0);
 }
 
 #ifdef TEST_OBJCACHE
 
-struct test_struct {
-    u64 a;
-    u64 b;
-    u64 c;
-    u64 d;
-};
-
-DEFINE_OBJCACHE(test_cache, struct test_struct);
+DEFINE_OBJCACHE(test_cache);
 
 /* Return the count of overhead pages allocated */
 
 static int __objcache_pages(struct objcache *objcache)
 {
-    int bitmap_longs = OVERHEAD_LONGS(objcache) - 1;
-    u64 *pages = objcache->start_page;
+    void *pages = objcache->data;
     int count = 0;
 
     while(pages) {
-        pages = (void *) (pages[bitmap_longs]);
-        count++;
+        count += (1 << ALLOC_ORDER);
+        pages = (void *) OBJCACHE_PTR_NEXT(pages);
     }
 
     return count;
@@ -223,58 +304,59 @@ void test_objcache(void)
      * empty on free.
      */
 
-    struct objcache *a = NULL, *b = NULL;
+    void *a = NULL, *b = NULL, *c = NULL;
     int i;
 
     assert(__objcache_pages(&test_cache) == 0);
 
-    /* Test struct is 32 bytes, which means 128 objects per page, one
-     * of which is taken up by our bitmap, so we should be able to do 127
-     * gets() all in the same page.
+    /* Allocating 32 bytes, which means 2 cells, or 2016 possible allocations
+     * in a single 64k allocation.
      */
 
-    for(i = 0; i < 127; i++) {
+    for(i = 0; i < 2016; i++) {
         b = a;
-        a = objcache_get(&test_cache);
+        a = objcache_get(&test_cache, 32);
 
         if (b) {
-            /* make sure they're same page */
-            assert(PAGE_ALIGN((u64) a) == PAGE_ALIGN((u64) b));
+            /* make sure they're same alloc */
+            assert(OBJBASE(a) == OBJBASE(b));
 
             /* make sure that previous can be freed and re allocated */
             objcache_free(&test_cache, b);
+            c = objcache_get(&test_cache, 32);
 
-            assert(objcache_get(&test_cache) == b);
+            assert(c == b);
         }
 
         /* make sure a is after b, also NULL check */
         assert((u64) a > (u64) b);
 
         /* shouldn't have caused expansion */
-        assert(__objcache_pages(&test_cache) == 1);
+        assert(__objcache_pages(&test_cache) == (1 << ALLOC_ORDER));
     }
 
-    /* The 128th should cause expansion */
-    a = objcache_get(&test_cache);
+    /* The 2017th should cause expansion */
+    a = objcache_get(&test_cache, 32);
 
-    assert(__objcache_pages(&test_cache) == 2);
+    assert(__objcache_pages(&test_cache) == (2 << ALLOC_ORDER));
 
-    /* 126 more, shouldn't expand */
-    for(i = 0; i < 126; i++)
-        objcache_get(&test_cache);
+    /* 2015 more, shouldn't expand */
+    for(i = 0; i < 2015; i++)
+        objcache_get(&test_cache, 32);
 
-    assert(__objcache_pages(&test_cache) == 2);
+    assert(__objcache_pages(&test_cache) == (2 << ALLOC_ORDER));
 
-    a = objcache_get(&test_cache);
+    a = objcache_get(&test_cache, 32);
 
-    assert(__objcache_pages(&test_cache) == 3);
+    assert(__objcache_pages(&test_cache) == (3 << ALLOC_ORDER));
 
-    /* Now we have 3 pages, with only a single object on the last page */
-
-    /* A free of that single object should cause the cache to contract */
+    /* Now we have 3 allocs, with only a single object on the last alloc
+     * A free of that single object should cause the cache to contract, but
+     * currently won't until we settle on an empty check.
+     */
 
-    objcache_free(&test_cache, a);
-    assert(__objcache_pages(&test_cache) == 2);
+    //objcache_free(&test_cache, a);
+    //assert(__objcache_pages(&test_cache) == 2);
 
     /* Test destroy and clean up after our tests */
     objcache_destroy(&test_cache);
index 4de7f10..5f1b3c8 100644 (file)
@@ -18,11 +18,11 @@ int vua_parse_block(parser_state_t *parser)
     return 0;
 }
 
-DEFINE_OBJCACHE(pstate_oc, parser_state_t);
+DEFINE_OBJCACHE(parser_cache);
 
 int vua_parse(u8 *input_data, u64 len)
 {
-    parser_state_t *state = objcache_get(&pstate_oc);
+    parser_state_t *state = objcache_get(&parser_cache, sizeof(parser_state_t));
 
     if(!state)
         return -1;
index 4e319ed..0c69604 100644 (file)
@@ -7,9 +7,7 @@
 #include "vua_str.h"
 #include "vua_hash.h"
 
-DEFINE_OBJCACHE_SIZE(chunk_oc, STRING_CHUNK);
-DEFINE_OBJCACHE(vua_str_chunk_oc, vua_str_chunk_t);
-DEFINE_OBJCACHE(vua_str_oc, vua_str_t);
+DEFINE_OBJCACHE(string_cache);
 
 void vua_str_free(vua_str_t *str)
 {
@@ -18,18 +16,18 @@ void vua_str_free(vua_str_t *str)
     while(cur_chunk) {
         str->first_chunk = cur_chunk->next;
         if(cur_chunk->data)
-            objcache_free(&chunk_oc, cur_chunk->data);
+            objcache_free(&string_cache, cur_chunk->data);
 
-        objcache_free(&vua_str_chunk_oc, cur_chunk);
+        objcache_free(&string_cache, cur_chunk);
         cur_chunk = str->first_chunk;
     }
 
-    objcache_free(&vua_str_oc, str);
+    objcache_free(&string_cache, str);
 }
 
 vua_str_t *vua_str_create(char *init_val, u64 starting_len)
 {
-    vua_str_t *ret = objcache_get(&vua_str_oc);
+    vua_str_t *ret = objcache_get(&string_cache, sizeof(vua_str_t));
     vua_str_chunk_t *prev_chunk = NULL;
     vua_str_chunk_t *cur_chunk = NULL;
 
@@ -51,14 +49,14 @@ vua_str_t *vua_str_create(char *init_val, u64 starting_len)
     remaining = starting_len;
 
     while(remaining) {
-        cur_chunk = objcache_get(&vua_str_chunk_oc);
+        cur_chunk = objcache_get(&string_cache, sizeof(vua_str_chunk_t));
         if(!cur_chunk)
             goto cleanup_chunks;
 
-        cur_chunk->data = objcache_get(&chunk_oc);
+        cur_chunk->data = objcache_get(&string_cache, STRING_CHUNK);
 
         if(!cur_chunk->data) {
-            objcache_free(&vua_str_chunk_oc, cur_chunk);
+            objcache_free(&string_cache, cur_chunk);
             goto cleanup_chunks;
         }