[start adding slub allocator
John Meacham <john@repetae.net>**20100405084227
 Ignore-this: 17366e455b01575df20b273dde5e6235
] hunk ./src/C/FromGrin2.hs 50
+--data AllocInfo = AllocInfo {
+--        allocSize, allocPtrs, allocOffset :: Int
+--    } 
+--    deriving(Eq,Ord)
hunk ./src/C/FromGrin2.hs 59
+--    wAllocs :: Set.Set AllocInfo,
hunk ./src/C/FromGrin2.hs 779
-        --let wmalloc = if not sf && all (nonPtr . getType) as then jhc_malloc_atomic else jhc_malloc
addfile ./src/data/rts/bitarray.h
hunk ./src/data/rts/bitarray.h 1
+#ifndef BITARRAY_H
+#define BITARRAY_H
+
+#include <limits.h>
+#include <stdbool.h>
+
+
+typedef unsigned long bitarray_t;
+
+#define BITS_PER_UNIT (bitarray_t)(CHAR_BIT*sizeof(bitarray_t))
+#define BITARRAY_SIZE(bits) (((bits) + (BITS_PER_UNIT - 1)) / BITS_PER_UNIT)
+#define BITARRAY_SIZE_IN_BYTES(bits) (sizeof(bitarray_t)*BITARRAY_SIZE(bits))
+
+
+#define WHICH_BIT(bit)  \
+    (1UL << ((((bitarray_t)(bit)) % BITS_PER_UNIT)))
+
+#define OFFSET_IN_ARRAY(array,bit) \
+    (((bitarray_t *)(array))[((bitarray_t)(bit)) / BITS_PER_UNIT])
+
+#define BIT_IS_SET(array,bit)  \
+    (OFFSET_IN_ARRAY(array,bit) & WHICH_BIT(bit))
+
+#define BIT_IS_UNSET(array,bit) \
+    (!(BIT_IS_SET(array,bit)))
+
+#define BIT_SET(array,bit) \
+    (OFFSET_IN_ARRAY(array,bit) |= WHICH_BIT(bit))
+
+#define BIT_UNSET(array,bit) \
+    (OFFSET_IN_ARRAY(array,bit) &= ~WHICH_BIT(bit))
+
+#define BIT_TOGGLE(array,bit) \
+    (OFFSET_IN_ARRAY(array,bit) ^= WHICH_BIT(bit))
+
+#define BIT_COPY(dest,src,bit)  \
+    do { BIT_IS_SET((src),(bit)) ? BIT_SET((dest),(bit)) : BIT_UNSET((dest),(bit)) } while(0)
+
+#define BIT_VALUE(array,bit) \
+    (BIT_IS_SET((array),(bit)) ? true : false)
+
+#define BIT_SET_VALUE(array,bit,value) \
+    do { (value) ? BIT_SET((array),(bit)) : BIT_UNSET((array),(bit)) } while(0)
+
+
+#endif
hunk ./src/data/rts/jhc_jgc.c 8
+#include "slub.c"
+
+static struct s_arena *arena;
hunk ./src/data/rts/jhc_jgc.c 196
-                free(e);
+                debugf("Freeing: %p\n", e);
+                s_free(e);
+                //free(e);
hunk ./src/data/rts/jhc_jgc.c 230
-        entry_t *e = malloc((count + 1)*GC_BASE);
+        //entry_t *e = malloc((count + 1)*GC_BASE);
+        entry_t *e = s_alloc(find_cache(arena, GC_BASE*(count + 1), 0));
hunk ./src/data/rts/jhc_jgc.c 255
+        arena = new_arena();
hunk ./src/data/rts/jhc_jgc.c 259
+static void
+jhc_malloc_fini(void) {
+        if(1) {
+                printf("arena: %p\n", arena);
+                printf("  base: %p\n", arena->base);
+                printf("  next_free: %i\n", arena->next_free);
+                printf("  num_used: %i\n", arena->num_used);
+                struct s_cache *sc = SLIST_FIRST(&arena->caches);
+                for(;sc;sc = SLIST_NEXT(sc,next)) {
+                        print_cache(sc);
+                }
+        }
+}
+
hunk ./src/data/rts/jhc_jgc.h 50
-#define GC_MINIMUM_SIZE 3
+#define GC_MINIMUM_SIZE 1
hunk ./src/data/rts/jhc_jgc.h 52
-#define GC_ALIGNMENT (2*sizeof(void *))
+#define GC_ALIGNMENT (sizeof(void *))
hunk ./src/data/rts/jhc_rts.c 80
+
hunk ./src/data/rts/jhc_rts.c 248
-        if(!--hs_init_count)
+        if(!--hs_init_count) {
hunk ./src/data/rts/jhc_rts.c 250
+                jhc_malloc_fini();
+        }
hunk ./src/data/rts/jhc_rts_alloc.c 8
+static void jhc_malloc_fini(void);
addfile ./src/data/rts/slub.c
hunk ./src/data/rts/slub.c 1
+
+#include <sys/queue.h>
+#include <sys/param.h>
+#include <assert.h>
+#include <stdint.h>
+#include <stdlib.h>
+#include <stdio.h>
+#include <string.h>
+#include <stddef.h>
+#include "bitarray.h"
+// #include "slub.h"
+
+#define PAGESIZE 4096
+#define ARENASIZE 65536
+
+#define S_PAGE(val) (struct s_page *)((uintptr_t)(val) & ~ (PAGESIZE - 1))
+
+typedef uint16_t page_num_t;
+
+struct s_arena {
+        void *base;
+        page_num_t next_free,num_used;
+        bitarray_t used[BITARRAY_SIZE(ARENASIZE)];
+        SLIST_HEAD(,s_cache) caches;
+};
+
+struct s_page {
+        TAILQ_ENTRY(s_page) tailq;
+        unsigned short num_free;
+        unsigned short color;
+        unsigned short size;
+        unsigned short next_free;
+        bitarray_t used[];
+};
+
+struct s_cache {
+        SLIST_ENTRY(s_cache) next;
+        struct s_arena *arena;
+        TAILQ_HEAD(,s_page) pages;
+        unsigned short num_entries;
+        unsigned short size;
+        unsigned short num_ptrs;
+        unsigned short color;
+};
+
+
+void print_cache(struct s_cache *sc);
+/* this finds a bit that isn't set, sets it, and returns it */
+
+inline static int
+bitset_find_free(int *next_free,int n,bitarray_t ba[static n]) {
+        assert(*next_free < n);
+        int i = *next_free;
+        for(; i < n; i++) {
+                if(~ba[i]) goto found;
+        }
+        for(i = 0; i < *next_free; i++) {
+                if(~ba[i]) goto found;
+        }
+        return -1;
+found:
+        {
+        int o = __builtin_ffsl(~ba[i]);
+        assert(o);
+        ba[i] |= (1UL << (o - 1));
+        *next_free = i;
+        return (i*BITS_PER_UNIT + (o - 1));
+        }
+}
+
+struct s_page *
+get_free_page(struct s_arena *arena) {
+        int next_free = arena->next_free;
+        int found = bitset_find_free(&next_free, BITARRAY_SIZE(ARENASIZE), arena->used);
+        arena->next_free = next_free;
+        if(found == -1)
+                return NULL;
+        return (struct s_page *)(arena->base + PAGESIZE*found);
+}
+
+void *
+s_alloc(struct s_cache *sc)
+{
+        struct s_page *pg;
+        assert(sc);
+
+        TAILQ_FOREACH(pg,&sc->pages,tailq) {
+                if(pg->num_free > 0)
+                        break;
+        }
+        if(!pg) {
+                pg = get_free_page(sc->arena);
+                assert(pg);
+                pg->num_free = sc->num_entries;
+                pg->color = sc->color;
+                pg->size = sc->size;
+                pg->next_free = 0;
+                memset(pg->used,0,BITARRAY_SIZE_IN_BYTES(sc->num_entries));
+                //int excess = BITARRAY_SIZE(sc->num_entries)*BITS_PER_UNIT - sc->num_entries;
+                for(int i = BITARRAY_SIZE(sc->num_entries)*BITS_PER_UNIT - 1; i >= sc->num_entries; i--)
+                        BIT_SET(pg->used,i);
+
+                TAILQ_INSERT_HEAD(&sc->pages,pg,tailq);
+                //printf("Creating New Page: %p\n", pg);
+        }
+
+        int next_free = pg->next_free;
+        int found = bitset_find_free(&next_free,BITARRAY_SIZE(sc->num_entries),pg->used);
+        pg->next_free = next_free;
+        assert(found != -1);
+        uintptr_t *pgp = (uintptr_t *)pg + pg->color;
+        void *val = &pgp[found * (pg->size/sizeof(uintptr_t))];
+//        printf("s_alloc: val: %p s_page: %p size: %i color: %i found: %i num_free: %i\n", val, pg, pg->size, pg->color, found, pg->num_free);
+        pg->num_free--;
+        if(!pg->num_free) {
+                TAILQ_REMOVE(&sc->pages,pg,tailq);
+                TAILQ_INSERT_TAIL(&sc->pages,pg,tailq);
+        }
+        assert(S_PAGE(val) == pg);
+        return val;
+}
+
+
+void
+s_free(void *val)
+{
+        assert(val);
+        struct s_page *pg = S_PAGE(val);
+        unsigned int offset = ((uintptr_t *)val - (uintptr_t *)pg) - pg->color;
+//        printf("s_free:  val: %p s_page: %p size: %i color: %i num_free: %i offset: %i bit: %i\n", val, pg, pg->size, pg->color, pg->num_free, offset, offset/pg->size);
+        assert(BIT_VALUE(pg->used,offset/(pg->size/sizeof(uintptr_t))));
+        BIT_UNSET(pg->used,offset/(pg->size/sizeof(uintptr_t)));
+        pg->num_free++;
+}
+
+
+struct s_cache *
+new_cache(struct s_arena *arena, unsigned short size, unsigned short num_ptrs)
+{
+        struct s_cache *sc = malloc(sizeof(struct s_cache));
+        sc->arena = arena;
+        sc->size = size;
+        size_t excess = PAGESIZE - sizeof(struct s_page);
+        sc->num_entries = (8*excess) / (8*size + 1) - 1;
+        //sc->num_entries = (8*excess) / (8*size*sizeof(uintptr_t) + 1);
+        sc->color = (sizeof(struct s_page) + BITARRAY_SIZE_IN_BYTES(sc->num_entries) + sizeof(uintptr_t) - 1) / sizeof(uintptr_t);
+        sc->num_ptrs = num_ptrs;
+        TAILQ_INIT(&sc->pages);
+        SLIST_INSERT_HEAD(&arena->caches,sc,next);
+        //print_cache(sc);
+        return sc;
+}
+
+struct s_cache *
+find_cache(struct s_arena *arena, unsigned short size, unsigned short num_ptrs)
+{
+        struct s_cache *sc = SLIST_FIRST(&arena->caches);
+        for(;sc;sc = SLIST_NEXT(sc,next)) {
+                if(sc->size == size && sc->num_ptrs == num_ptrs)
+                        return sc;
+        }
+        return new_cache(arena,size,num_ptrs);
+}
+
+struct s_arena *
+new_arena(void) {
+        struct s_arena *arena = malloc(sizeof(struct s_arena));
+        SLIST_INIT(&arena->caches);
+        int ret = posix_memalign(&arena->base,PAGESIZE,ARENASIZE*PAGESIZE);
+        if(ret != 0) {
+                fprintf(stderr,"Unable to allocate memory with posix_memalign\n");
+                exit(1);
+        }
+        arena->next_free = 0;
+        arena->num_used = 0;
+        memset(arena->used,0,sizeof(arena->used));
+        return arena;
+}
+
+
+void
+print_cache(struct s_cache *sc) {
+        printf("num_entries: %i\n",(int)sc->num_entries);
+        printf("  entries: %i bytes\n",(int)(sc->num_entries*sc->size));
+        printf("  header: %lu bytes\n", sizeof(struct s_page) + BITARRAY_SIZE_IN_BYTES(sc->num_entries));
+     //   printf("excess: %i\n", PAGESIZE - sizeof(struct s_page) - sizeof(bitarray_t));
+        printf("  size: %i bytes\n",(int)sc->size);
+        printf("  color: %i words\n",(int)sc->color);
+        printf("  color_off: %i bytes\n",(int)(sc->color*sizeof(uintptr_t)));
+        printf("  end: %i bytes\n",(int)(sc->color*sizeof(uintptr_t) + sc->num_entries*sc->size));
+        printf("%20s %9s %9s %9s %9s\n", "page", "num_free", "color", "size", "next_free");
+    
+        struct s_page *pg;
+        TAILQ_FOREACH(pg,&sc->pages,tailq) {
+            printf("%20p %9i %9i %9i %9i\n", pg, pg->num_free, pg->color, pg->size, pg->next_free);
+        }
+}
+
+#ifdef SLAB_TEST
+
+#define NUM_CACHES 15
+#define FACTOR (1 << 16)
+
+void
+stress_test(int n) {
+        struct s_arena *arena = new_arena();
+        struct s_cache *caches[NUM_CACHES];
+
+        void *ptrs[n];
+        memset(ptrs,0,n*sizeof(void *));
+        for(int i = 0; i < NUM_CACHES; i++)
+                caches[i] = new_cache(arena,sizeof(void *)*(i + 1), 0);
+        for(int i = 0; i < FACTOR * n; i++) {
+                int wp = rand() % n;
+                if (ptrs[wp]) {
+                        s_free(ptrs[wp]);
+                        //free(ptrs[wp]);
+                        ptrs[wp] = NULL;
+                } else {
+                        ptrs[wp] = s_alloc(caches[rand() % NUM_CACHES]);
+                        //ptrs[wp] = malloc((rand() % NUM_CACHES) * sizeof(uintptr_t));
+                }
+        }
+}
+
+
+int
+main(int argc, char *argv[])
+{
+
+        setbuf(stdout,NULL);
+        stress_test(1 << 8);
+        struct s_arena *arena = new_arena();
+        for(int i = 0;i < 10; i++) {
+        struct s_cache *sc = new_cache(arena,i,0);
+        print_cache(sc);
+        }
+        struct s_cache *sc1 = new_cache(arena,7,4);
+        struct s_cache *sc2 = new_cache(arena,1,3);
+
+        printf("Alloc1: %p\n", s_alloc(sc1));
+        printf("Alloc1: %p\n", s_alloc(sc1));
+        printf("Alloc1: %p\n", s_alloc(sc1));
+        printf("Alloc2: %p\n", s_alloc(sc2));
+        printf("Alloc2: %p\n", s_alloc(sc2));
+        printf("Alloc2: %p\n", s_alloc(sc2));
+
+        print_cache(sc1);
+        print_cache(sc2);
+
+
+        return 0;
+}
+
+#endif