mem.c

   1 #include "gmqcc.h"
   2 /*
   3  * GMQCC does a lot of allocations on shortly lived objects all of which
   4  * call down to malloc/free internally.  The overhead involved with these
   5  * allocations makes GMQCC slow. To combat this, a special allocator was
   6  * in need.  This is an implementation of a user-space buddy allocator
   7  * that sits ontop of malloc/free.  I'd like to thank Lee Salzman for
   8  * guiding me in the right direction for designing this.
   9  */
  10 #define GMQCC_MEM_USED 0xEDCA10A1EDCA10A1
  11 #define GMQCC_MEM_FREE 0xEEF8EEF8EEF8EEF8
  12 #define GMQCC_MEM_CORE 0x00000000000000AA
  13 #define GMQCC_MEM_BSL -1
  14 #define GMQCC_MEM_BSR  1
  15
  16 typedef unsigned long int mem_addr;
  17
  18 static void   *mem_heap = NULL;
  19 static size_t  mem_look = 0;  /* lookup table offset */
  20 static size_t  mem_size = 0;  /* heap size           */
  21
  22 /* read or write to heap */
  23 #define GMQCC_MEM_WRITEHEAP(OFFSET, TYPE, VALUE) *((TYPE *) ((unsigned char*)mem_heap + (OFFSET))) = (VALUE)
  24 #define GMQCC_MEM_READHEAP (OFFSET, TYPE) ((TYPE)*((TYPE *)(((unsigned char*)mem_heap + (OFFSET)))))
  25
  26 /* read of write first block to heap */
  27 #define GMQCC_MEM_WRITEFBA(SIZE, ADDR) GMQCC_MEM_WRITEHEAP(mem_look + (SIZE) * sizeof(mem_addr), mem_addr, ADDR)
  28 #define GMQCC_MEM_READFBA(SIZE)        GMQCC_MEM_READHEAP (mem_look + (SIZE) * sizeof(mem_addr), ADDR)
  29
  30 /* read and write block sizes from heap */
  31 #define GMQCC_MEM_WRITEBS(ADDR, SIZE) GMQCC_MEM_WRITEHEAP(ADDR, mem_addr, (SIZE))
  32 #define GMQCC_MEM_READBS(ADDR)        GMQCC_MEM_READHEAP (ADDR, mem_addr);
  33
  34 /*
  35  * Getting address of previous/following siblings, as well as
  36  * setting address of previous/following siblings.
  37  */
  38 #define GMQCC_MEM_GETADDROFPS(ADDR)   GMQCC_MEM_READHEAP ((ADDR) + 2 * sizeof(mem_addr), mem_addr)
  39 #define GMQCC_MEM_GETADDROFFS(ADDR)   GMQCC_MEM_READHEAP ((ADDR) + 3 * sizeof(mem_addr), mem_addr)
  40 #define GMQCC_MEM_SETADDROFPS(ADDR,V) GMQCC_MEM_WRITEHEAP((ADDR) + 2 * sizeof(mem_addr), mem_addr, V)
  41 #define GMQCC_MEM_SETADDROFFS(ADDR,V) GMQCC_MEM_WRITEHEAP((ADDR) + 3 * sizeof(mem_addr), mem_addr, V)
  42
  43 /* Marking blocks as used or free */
  44 #define GMQCC_MEM_MARKUSED(ADDR) GMQCC_MEM_WRITEHEAP((ADDR) + 1 * sizeof(mem_addr), mem_addr, GMQCC_MEM_USED)
  45 #define GMQCC_MEM_MARKFREE(ADDR) GMQCC_MEM_WRITEHEAP((ADDR) + 1 * sizeof(mem_addr), mem_addr, GMQCC_MEM_FREE)
  46
  47 static void mem_init_table(size_t size) {
  48     size_t i;
  49
  50     mem_look = 8 * ((mem_addr)1 << (size - 1)) + sizeof(mem_addr);
  51
  52     GMQCC_MEM_WRITEHEAP(0,        mem_addr, mem_look);
  53     GMQCC_MEM_WRITEHEAP(mem_look, mem_addr, size);
  54
  55     /* write pointers to first free bock of said size */
  56     for (i = 1; i < size; i++)
  57         GMQCC_MEM_WRITEHEAP(mem_look + sizeof(mem_addr) * i, mem_addr, 0);
  58
  59     GMQCC_MEM_WRITEHEAP(mem_look + sizeof(mem_addr) * size, mem_addr, sizeof(mem_addr));
  60     GMQCC_MEM_WRITEHEAP(sizeof(mem_addr), mem_addr, size);
  61     GMQCC_MEM_MARKFREE (sizeof(mem_addr) << 1);
  62     GMQCC_MEM_WRITEHEAP(sizeof(mem_addr) * 3, mem_addr, 0);
  63     GMQCC_MEM_WRITEHEAP(sizeof(mem_addr) * 4, mem_addr, 0);
  64 }
  65
  66 /* get needed block size */
  67 static size_t mem_getnbs(const size_t need) {
  68     size_t b = 8;
  69     size_t s = 1;
  70
  71     while (need > b) {
  72         b >>= 1;
  73         s ++;
  74     }
  75
  76     return s;
  77 }
  78
  79 void mem_init(size_t size) {
  80     size_t alloc = 0;
  81     size_t count = 1;
  82     size_t block = 1;
  83
  84     if (!(mem_heap = malloc(size)))
  85         abort();
  86
  87     memset(mem_heap, GMQCC_MEM_CORE, size);
  88     mem_size = size;
  89     alloc    = size - (2 * sizeof(mem_addr));
  90
  91     while (alloc + sizeof(mem_addr) > 8 * block) {
  92         alloc  -= sizeof(mem_addr);
  93         block <<= 1;
  94         count  ++;
  95     }
  96
  97     /* over shot ? */
  98     block >>= 1;
  99     count --;
 100
 101     mem_init_table(count);
 102 }
 103
 104 /* doesn't get any simpler :-) */
 105 void mem_destroy() {
 106     free(mem_heap);
 107     mem_heap = NULL;
 108 }
 109
 110 void *mem_alloc(size_t amount) {
 111     size_t   need  = amount + 4 * sizeof(mem_addr);
 112     size_t   size  = mem_getnbs    (need);
 113     mem_addr block = mem_allocblock(size);
 114     if (!block) return NULL;
 115
 116     return mem_heap + block + 4 * sizeof(mem_addr);
 117 }