objcache: Actually bump allocate
authorJack Miller <jack@codezen.org>
Sat, 27 Aug 2016 17:00:38 +0000 (12:00 -0500)
committerJack Miller <jack@codezen.org>
Sat, 27 Aug 2016 18:31:38 +0000 (13:31 -0500)
The intention of this data structure was always to be high performance,
but of course early on stability is more important so it's been acting
as a glorified bitmap. However, now that we're using objcache in our
interpreter/compiler, it's rather important to be quick.

I added the TSC support to get a better idea on the performance, and
still need to characterize non-sequential, and freeing BUT preliminary
numbers:

bitmap objcache: 100000 sequential allocs in 145 seconds
bump objcache:   100000 sequential allocs in 92 milliseconds

Which isn't too surprising considering the bitmap objcache is worse than
the worst case of the bump objcache implementation, but nonetheless a
1500x speedup is nice.

TODO
include/objcache.h
mm/objcache.c

diff --git a/TODO b/TODO
index 9cd80f3..1224cbc 100644 (file)
--- a/TODO
+++ b/TODO
@@ -25,10 +25,6 @@ would effectively amount to "support all hardware" which goes without saying.
 - Objcache won't automatically free memory back to the page allocators when all
   of the objects have been freed. Currently, will only release on destroy().
 
-- Objcache also has empty space in its control structure that can be used to
-  enhance the bitmap information, and should also be made to actually bump
-  allocate instead of searching the bitmaps every time.
-
 = EFI =
 
 - the EFI stub copies out the GOP information to a hard-coded offset, that
index 5af1b93..7b422ea 100644 (file)
@@ -11,7 +11,9 @@ struct objcache {
 
     void *data;
     void *last_alloc;
-    void *next_free;
+
+    /* Free cells at end of last_alloc */
+    u32 free_cells;
 
     DEFINE_SPINLOCK(lock);
 };
index f13b60d..9c99d1c 100644 (file)
@@ -76,6 +76,9 @@
 #define FREE_CELLS              (TOTAL_CELLS - OVERHEAD_CELLS)
 #define OBJCACHE_MAXSIZE        (FREE_CELLS * OC_CELL_SIZE)
 
+/* Assert that we can store meta bitmap information in 8 bytes */
+STATIC_ASSERT((FREE_CELLS / 64) <= 64);
+
 /* How many bytes of the bitmap can we assume are taken by metadata */
 #define SKIP_BYTES              (OVERHEAD_CELLS / 8)
 
 
 #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_META_BMAP(x)   ((u64 *) &((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 */
 
+#define FIRST_BIT (1UL << 63)
+
 /* Macros for finding base / idx from object pointer */
 #define OBJBASE(x)              ((void *) (((u64) (x)) & BASE_MASK))
 
  * fact.
  */
 
-#define OBJIDX(x)               (((((u64) (x)) & ALLOC_MASK) >> 4) - OVERHEAD_CELLS)
+#define OBJIDX(x)               (((((u64) (x)) & ALLOC_MASK) >> ALLOC_ORDER) - OVERHEAD_CELLS)
 #define OBJCACHE_CELL(x, n)     ((void *) &((u8 *)(x))[OC_CELL_SIZE * (n + OVERHEAD_CELLS)])
 
 static int __oc_find_free_cells(struct objcache *objcache, u32 cells, void **alloc)
 {
-    u64 *mark_map, *block_map;
+    u64 *mark_map, *block_map, *meta_map;
     u64 curbit;
 
     s32 free_start = -1;
@@ -116,11 +121,15 @@ static int __oc_find_free_cells(struct objcache *objcache, u32 cells, void **all
     *alloc = objcache->data;
 
     while (*alloc) {
-        mark_map = (u64 *) OBJCACHE_MARK_BMAP(*alloc);
         block_map = (u64 *) OBJCACHE_BLOCK_BMAP(*alloc);
+        mark_map = (u64 *) OBJCACHE_MARK_BMAP(*alloc);
+        meta_map = (u64 *) OBJCACHE_META_BMAP(*alloc);
+
+        if (*meta_map == 0)
+            return 0;
 
         for(i = 0; i < OBJCACHE_BMAP_SIZE; i++) {
-            curbit = 1;
+            curbit = FIRST_BIT;
 
             for(j = 0; j < 64; j++) {
                 if (*block_map & curbit)
@@ -138,11 +147,11 @@ static int __oc_find_free_cells(struct objcache *objcache, u32 cells, void **all
                 if (free_here >= cells)
                     return free_start;
 
-                curbit <<= 1;
+                curbit >>= 1;
             }
 
-            mark_map++;
             block_map++;
+            mark_map++;
         }
 
         *alloc = (void *) OBJCACHE_PTR_NEXT(*alloc);
@@ -163,6 +172,8 @@ static int __oc_bump_allocation(struct objcache *objcache)
     /* Init bitmap and next ptr */
 
     OBJCACHE_PTR_NEXT(new_pages) = 0x0;
+    *OBJCACHE_META_BMAP(new_pages) = 0x0;
+
     mark_map = (u64 *) OBJCACHE_MARK_BMAP(new_pages);
     block_map = (u64 *) OBJCACHE_BLOCK_BMAP(new_pages);
 
@@ -172,7 +183,7 @@ static int __oc_bump_allocation(struct objcache *objcache)
     }
 
     /* Start with a free block definition, mark = 1, block = 0 */
-    mark_map[0] = 0x1;
+    mark_map[0] = FIRST_BIT;
 
     if (!objcache->data)
         objcache->data = new_pages;
@@ -180,45 +191,63 @@ static int __oc_bump_allocation(struct objcache *objcache)
         OBJCACHE_PTR_NEXT(objcache->last_alloc) = (u64) new_pages;
 
     objcache->last_alloc = new_pages;
-    objcache->next_free = OBJCACHE_CELL(new_pages, OVERHEAD_CELLS);
+    objcache->free_cells = FREE_CELLS;
     return 0;
 }
 
 void *objcache_get(struct objcache *objcache, u32 size)
 {
     u64 *page;
-    u64 *mark_map, *block_map;
+    u64 *mark_map, *block_map, *meta_map;
+    u64 longidx, metabit;
     int idx;
     void *ret;
 
-    if (size > OBJCACHE_MAXSIZE)
+    if ((!size) || (size > OBJCACHE_MAXSIZE))
         return NULL;
 
     /* Convert size from bytes to cells */
     size = (size + (OC_CELL_SIZE - 1)) / OC_CELL_SIZE;
 
-    idx = __oc_find_free_cells(objcache, size, (void **) &page);
-
-    if (idx == -1) {
-        if (__oc_bump_allocation(objcache))
-            return NULL;
+    if (size <= objcache->free_cells) {
+        idx = FREE_CELLS - objcache->free_cells;
         page = objcache->last_alloc;
-        idx = 0;
+        objcache->free_cells -= size;
+    } else {
+        idx = __oc_find_free_cells(objcache, size, (void **) &page);
+
+        if (idx == -1) {
+            if (__oc_bump_allocation(objcache))
+                return NULL;
+            page = objcache->last_alloc;
+            objcache->free_cells -= size;
+            idx = 0;
+        }
     }
 
     block_map = OBJCACHE_BLOCK_BMAP(page);
     mark_map = OBJCACHE_MARK_BMAP(page);
+    meta_map = OBJCACHE_META_BMAP(page);
+
     ret = OBJCACHE_CELL(page, idx);
 
+    longidx = idx / 64;
+    metabit = FIRST_BIT >> longidx;
+
     /* Turn this index into a white block */
-    block_map[idx / 64] |= (1UL << (idx % 64));
-    mark_map[idx / 64] &= ~(1UL << (idx % 64));
+    block_map[longidx] |= (FIRST_BIT >> (idx % 64));
+    mark_map[longidx] &= ~(FIRST_BIT >> (idx % 64));
+    *meta_map |= metabit;
+
+    /* If there's a following block and it's free, turn it into a free header */
 
-    /* Turn the following block, if free, into a free header */
     idx += size;
 
-    if (!(block_map[idx / 64] & (1UL << (idx % 64))))
-        mark_map[idx / 64] |= (1UL << (idx % 64));
+    if (idx >= FREE_CELLS)
+        return ret;
+
+    if (!(block_map[idx / 64] & (FIRST_BIT >> (idx % 64))))
+        mark_map[idx / 64] |= (FIRST_BIT >> (idx % 64));
 
     return ret;
 }
@@ -243,22 +272,37 @@ void objcache_free(struct objcache *objcache, void *obj)
     void *base = OBJBASE(obj);
     u64 *block_map = OBJCACHE_BLOCK_BMAP(base);
     u64 *mark_map = OBJCACHE_MARK_BMAP(base);
+    u64 *meta_map = OBJCACHE_META_BMAP(base);
 
     int idx = OBJIDX(obj);
     int longidx = idx / 64;
-    u64 bit = (1UL << (idx % 64));
+    u64 bit = FIRST_BIT >> (idx % 64);
+
+    u64 meta_bit = (FIRST_BIT >> longidx);
+    u64 meta_mask = meta_bit - 1;
 
     assert(obj == OBJCACHE_CELL(base, idx));
+    assert(block_map[longidx] & bit);
 
     block_map[longidx] &= ~bit;
     mark_map[longidx] |= bit;
 
-    /* TODO free whole alloc if __oc_alloc_empty() */
+    /* Convert bit to mask of following bits in this longidx */
+    bit--;
 
-    /* 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?
+    /* If all of the following bits are also clear, see if we're free up to
+     * free_cells and update if possible
      */
+
+    if ((block_map[longidx] & bit) == 0) {
+        if (block_map[longidx] == 0)
+            *meta_map &= ~meta_bit;
+
+        if (*meta_map == 0) {
+            objcache->free_cells = FREE_CELLS; // TODO: Free last_alloc
+        } else if ((*meta_map & meta_mask) == 0)
+            objcache->free_cells = FREE_CELLS - idx;
+    }
 }
 
 void objcache_destroy(struct objcache *objcache)
@@ -279,7 +323,7 @@ void objcache_init(struct objcache *objcache)
 {
     objcache->data = NULL;
     objcache->last_alloc = NULL;
-    objcache->next_free = NULL;
+    objcache->free_cells = 0;
 
     spinlock_init(&objcache->lock, 0);
 }
@@ -310,7 +354,8 @@ void test_objcache(void)
      * empty on free.
      */
 
-    void *a = NULL, *b = NULL, *c = NULL;
+    void *a = NULL, *b = NULL;
+    u64 *meta;
     int i;
 
     assert(__objcache_pages(&test_cache) == 0);
@@ -323,22 +368,18 @@ void test_objcache(void)
         b = a;
         a = objcache_get(&test_cache, 32);
 
-        if (b) {
-            /* make sure they're same alloc */
+        if (b)
             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(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 << ALLOC_ORDER));
+
+        /* should have set meta bitmap */
+        meta = OBJCACHE_META_BMAP(test_cache.last_alloc);
+        assert(*meta & (FIRST_BIT >> (i / 64)));
     }
 
     /* The 2017th should cause expansion */
@@ -352,16 +393,39 @@ void test_objcache(void)
 
     assert(__objcache_pages(&test_cache) == (2 << ALLOC_ORDER));
 
+    /* With a full objcache last_alloc, free some in the middle and make sure
+     * it will fallback on the bitmap if the bump allocator is at the end
+     * of an alloc, as well as checking the meta bitmap is correct
+     */
+
+    for (i = 32; i < 64; i++) {
+        /* Make sure that the meta bitmap is still set */
+        meta = OBJCACHE_META_BMAP(test_cache.last_alloc);
+        assert(*meta & (FIRST_BIT >> 1));
+        objcache_free(&test_cache, OBJCACHE_CELL(test_cache.last_alloc, i * 2));
+    }
+
+    /* After last free, meta bitmap should be unset */
+    meta = OBJCACHE_META_BMAP(test_cache.last_alloc);
+    assert(!(*meta & (FIRST_BIT >> 1)));
+
+    for (i = 32; i < 64; i++) {
+        assert(objcache_get(&test_cache, 32) == OBJCACHE_CELL(test_cache.last_alloc, i * 2));
+        assert(__objcache_pages(&test_cache) == (2 << ALLOC_ORDER));
+    }
+
     a = objcache_get(&test_cache, 32);
 
     assert(__objcache_pages(&test_cache) == (3 << ALLOC_ORDER));
 
-    /* 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.
-     */
+    meta = OBJCACHE_META_BMAP(test_cache.last_alloc);
+    assert(*meta == FIRST_BIT);
+
+    objcache_free(&test_cache, a);
+
+    meta = OBJCACHE_META_BMAP(test_cache.last_alloc);
+    assert(*meta == 0x0);
 
-    //objcache_free(&test_cache, a);
     //assert(__objcache_pages(&test_cache) == 2);
 
     /* Test destroy and clean up after our tests */