mem.c

   1 #include "gmqcc.h"
   2 #include <assert.h>
   3 /*
   4  * GMQCC does a lot of allocations on shortly lived objects all of which
   5  * call down to malloc/free internally.  The overhead involved with these
   6  * allocations makes GMQCC slow. To combat this, a special allocator was
   7  * in need.  This is an implementation of a user-space buddy allocator
   8  * that sits ontop of malloc/free.  I'd like to thank Lee Salzman for
   9  * guiding me in the right direction for designing this.
  10  */
  11 #define GMQCC_MEM_USED  0xEDCA10A1EDCA10A1
  12 #define GMQCC_MEM_FREE  0xEEF8EEF8EEF8EEF8
  13 #define GMQCC_MEM_CORE  0x00000000000000AA
  14 #define GMQCC_MEM_BSL  -1
  15 #define GMQCC_MEM_BSR   1
  16 #define GMQCC_MEM_DEBUG 1
  17
  18 #ifdef  GMQCC_MEM_DEBUG
  19 #   include <stdio.h>
  20 #   define GMQCC_MEM_TRACE(TAG, ...)            \
  21     do {                                        \
  22         printf("[mem:%s]: %s ", TAG, __func__); \
  23         printf(__VA_ARGS__);                    \
  24         printf("\n");                           \
  25     } while (0)
  26 #else
  27 #   define GMQCC_MEM_TRACE(TAG, ...)
  28 #endif
  29
  30 typedef unsigned long int mem_addr;
  31
  32 static void   *mem_heap = NULL;
  33 static size_t  mem_look = 0;  /* lookup table offset */
  34 static size_t  mem_size = 0;  /* heap size           */
  35
  36 /* read or write to heap */
  37 #define GMQCC_MEM_WRITEHEAP(OFFSET, TYPE, VALUE) *((TYPE *) ((unsigned char*)mem_heap + (OFFSET))) = (VALUE)
  38 #define GMQCC_MEM_READHEAP(OFFSET, TYPE)  ((TYPE)*((TYPE *)(((unsigned char*)mem_heap + (OFFSET)))))
  39
  40 /* read of write first block to heap */
  41 #define GMQCC_MEM_WRITEFBA(SIZE, ADDR) GMQCC_MEM_WRITEHEAP(mem_look + (SIZE) * sizeof(mem_addr), mem_addr, ADDR)
  42 #define GMQCC_MEM_READFBA(SIZE)        GMQCC_MEM_READHEAP (mem_look + (SIZE) * sizeof(mem_addr), mem_addr)
  43
  44 /* read and write block sizes from heap */
  45 #define GMQCC_MEM_WRITEBS(ADDR, SIZE) GMQCC_MEM_WRITEHEAP(ADDR, mem_addr, (SIZE))
  46 #define GMQCC_MEM_READBS(ADDR)        GMQCC_MEM_READHEAP (ADDR, mem_addr);
  47
  48 /*
  49  * Getting address of previous/following siblings, as well as
  50  * setting address of previous/following siblings.
  51  */
  52 #define GMQCC_MEM_GETADDROFPS(ADDR)   GMQCC_MEM_READHEAP ((ADDR) + 2 * sizeof(mem_addr), mem_addr)
  53 #define GMQCC_MEM_GETADDROFFS(ADDR)   GMQCC_MEM_READHEAP ((ADDR) + 3 * sizeof(mem_addr), mem_addr)
  54 #define GMQCC_MEM_SETADDROFPS(ADDR,V) GMQCC_MEM_WRITEHEAP((ADDR) + 2 * sizeof(mem_addr), mem_addr, V)
  55 #define GMQCC_MEM_SETADDROFFS(ADDR,V) GMQCC_MEM_WRITEHEAP((ADDR) + 3 * sizeof(mem_addr), mem_addr, V)
  56
  57 /* Marking blocks as used or free */
  58 #define GMQCC_MEM_MARKUSED(ADDR) GMQCC_MEM_WRITEHEAP((ADDR) + 1 * sizeof(mem_addr), mem_addr, GMQCC_MEM_USED)
  59 #define GMQCC_MEM_MARKFREE(ADDR) GMQCC_MEM_WRITEHEAP((ADDR) + 1 * sizeof(mem_addr), mem_addr, GMQCC_MEM_FREE)
  60
  61 /* Has block? */
  62 #define GMQCC_MEM_HASBLOCK(SIZE) (GMQCC_MEM_READFBA(size) != 0)
  63
  64 static void mem_init_table(size_t size) {
  65     GMQCC_MEM_TRACE("flow", "(%lu)", size);
  66     size_t i;
  67
  68     mem_look = 8 * ((mem_addr)1 << (size - 1)) + sizeof(mem_addr);
  69
  70     GMQCC_MEM_WRITEHEAP(0,        mem_addr, mem_look);
  71     GMQCC_MEM_WRITEHEAP(mem_look, mem_addr, size);
  72
  73     /* write pointers to first free bock of said size */
  74     for (i = 1; i < size; i++)
  75         GMQCC_MEM_WRITEHEAP(mem_look + sizeof(mem_addr) * i, mem_addr, 0);
  76
  77     GMQCC_MEM_WRITEHEAP(mem_look + sizeof(mem_addr) * size, mem_addr, sizeof(mem_addr));
  78     GMQCC_MEM_WRITEHEAP(sizeof(mem_addr), mem_addr, size);
  79     GMQCC_MEM_MARKFREE (sizeof(mem_addr) * 2);
  80     GMQCC_MEM_WRITEHEAP(sizeof(mem_addr) * 3, mem_addr, 0);
  81     GMQCC_MEM_WRITEHEAP(sizeof(mem_addr) * 4, mem_addr, 0);
  82 }
  83
  84 /* get needed block size */
  85 static size_t mem_getnbs(const size_t need) {
  86     size_t b = 8;
  87     size_t s = 1;
  88
  89     while (need > b) {
  90         b *= 2;
  91         s ++;
  92     }
  93
  94     return s;
  95 }
  96
  97 static void mem_removeblock(mem_addr a, size_t size) {
  98     mem_addr p = GMQCC_MEM_GETADDROFPS(a);
  99     mem_addr n = GMQCC_MEM_GETADDROFFS(a);
 100
 101     GMQCC_MEM_SETADDROFPS(a, ~((mem_addr)0));
 102     GMQCC_MEM_SETADDROFFS(a, ~((mem_addr)0));
 103
 104     /* handle singles in list */
 105     if ((p == 0) && (n == 0)) {
 106         GMQCC_MEM_WRITEFBA(size, 0);
 107         return;
 108     }
 109
 110     /* first in list has different sibling semantics */
 111     if (p == 0) {
 112         GMQCC_MEM_WRITEFBA   (size, n);
 113         GMQCC_MEM_SETADDROFPS(n, 0);
 114         return;
 115     }
 116
 117     /* last item also has special meaning :) */
 118     if (n == 0) {
 119         GMQCC_MEM_SETADDROFFS(p, 0);
 120         return;
 121     }
 122
 123     /* middle of list */
 124     GMQCC_MEM_SETADDROFPS(n, p);
 125     GMQCC_MEM_SETADDROFFS(p, n);
 126 }
 127
 128 static int mem_createblock(const size_t size) {
 129     mem_addr parent;
 130     int      test;
 131
 132     GMQCC_MEM_TRACE("flow", "(%lu)", size);
 133     if (GMQCC_MEM_HASBLOCK(size))
 134         return 0;
 135
 136     if (size > GMQCC_MEM_READHEAP(mem_look, mem_addr))
 137         abort();
 138
 139     /* recrusive ... */
 140     if ((test = mem_createblock(size + 1)) != 0)
 141         return test;
 142
 143     /* safe splits assured */
 144     parent = GMQCC_MEM_READFBA(size + 1);
 145     mem_removeblock(parent, size + 1);
 146
 147     /* split it */
 148     GMQCC_MEM_WRITEFBA(size, parent);
 149     {
 150         /* find center and split */
 151         mem_addr block = parent + 8 * ((mem_addr)1 << (size - 1));
 152         mem_addr left  = parent;
 153         mem_addr right = block;
 154
 155         GMQCC_MEM_TRACE(
 156             "dump",
 157             "block info:\n    left  addr: %lu\n    right addr: %lu\n    prev  addr: %lu",
 158             left, right, parent
 159         );
 160
 161         /* left half  */
 162         GMQCC_MEM_WRITEHEAP  (left, mem_addr, size);
 163         GMQCC_MEM_MARKFREE   (left);
 164         GMQCC_MEM_SETADDROFPS(left, 0);
 165         GMQCC_MEM_SETADDROFFS(left, right);
 166         /* right half */
 167         GMQCC_MEM_WRITEHEAP  (right, mem_addr, size);
 168         GMQCC_MEM_MARKFREE   (right);
 169         GMQCC_MEM_SETADDROFPS(right, left);
 170         GMQCC_MEM_SETADDROFPS(right, 0);
 171     }
 172     return 0;
 173 }
 174
 175 static mem_addr mem_allocblock(const size_t size) {
 176     GMQCC_MEM_TRACE("flow", "(%lu)", size);
 177     int      test = mem_createblock(size);
 178     mem_addr first;
 179     mem_addr next;
 180
 181     if (test != 0)
 182         return 0;
 183
 184     /* first free one */
 185     first = GMQCC_MEM_READFBA    (size);
 186     next  = GMQCC_MEM_GETADDROFFS(first);
 187
 188     mem_removeblock(first, size);
 189
 190     GMQCC_MEM_WRITEFBA(next, size);
 191     GMQCC_MEM_MARKUSED(first);
 192
 193     return first;
 194 }
 195
 196 static int mem_getside(mem_addr addr, const size_t size) {
 197     size_t  real = addr - sizeof(mem_addr);
 198     size_t  next = ((mem_addr)1 << (size));
 199     assert((real % 8) == 0); /* blow up */
 200     real /= 8;
 201
 202     return ((real % next) == 0)? GMQCC_MEM_BSL : GMQCC_MEM_BSR;
 203 }
 204
 205 static mem_addr mem_getaddr(mem_addr start, const size_t size) {
 206     size_t length = (((mem_addr)1 << (size - 1)) * 8);
 207
 208     switch (mem_getside(start, size)) {
 209         case GMQCC_MEM_BSL: return start + length;
 210         case GMQCC_MEM_BSR: return start - length;
 211     }
 212     /* if reached blow up */
 213     return (abort(), 1);
 214 }
 215
 216 static void mem_addblock(mem_addr a, size_t s) {
 217     mem_addr first = GMQCC_MEM_READFBA(s);
 218     if (first == 0) {
 219         /* only block */
 220         GMQCC_MEM_WRITEFBA   (s, a);
 221         GMQCC_MEM_SETADDROFPS(a, 0);
 222         GMQCC_MEM_SETADDROFFS(a, 0);
 223     } else {
 224         /* add to front */
 225         GMQCC_MEM_WRITEFBA   (s, a);
 226         GMQCC_MEM_SETADDROFPS(a, 0);
 227         GMQCC_MEM_SETADDROFFS(a, first);
 228         GMQCC_MEM_SETADDROFPS(first, a);
 229     }
 230 }
 231
 232 void mem_init(size_t size) {
 233     size_t alloc = size;
 234     size_t count = 1;
 235     size_t block = 1;
 236
 237     /* blow up if too small */
 238     assert (sizeof(void*) == sizeof(mem_addr));
 239
 240     if (!(mem_heap = malloc(size)))
 241         abort();
 242
 243     memset(mem_heap, GMQCC_MEM_CORE, size);
 244     mem_size = size;
 245     alloc    -= 2 * sizeof(mem_addr);
 246
 247     while (alloc + sizeof(mem_addr) > 8 * block) {
 248         alloc -= sizeof(mem_addr);
 249         block *= 2;
 250         count ++;
 251     }
 252
 253     /* over shot ? */
 254     block /= 2;
 255     count --;
 256
 257     mem_init_table(count);
 258 }
 259
 260 /* doesn't get any simpler :-) */
 261 void mem_destroy() {
 262     free(mem_heap);
 263     mem_heap = NULL;
 264 }
 265
 266 void *mem_alloc(size_t amount) {
 267     GMQCC_MEM_TRACE("flow", "(%lu)", amount);
 268     size_t   need  = amount + 4 * sizeof(mem_addr);
 269     size_t   size  = mem_getnbs    (need);
 270     mem_addr block = mem_allocblock(size);
 271
 272     GMQCC_MEM_TRACE("dump", "will allocate %lu size block", size);
 273     /* standard behaviour */
 274     if (block == 0)
 275         return NULL;
 276     GMQCC_MEM_TRACE("dump", "returning offset %lu", block);
 277     return mem_heap + block + 4 * sizeof(mem_addr);
 278 }
 279
 280 void mem_free(void *ptr) {
 281     mem_addr start = (mem_addr)(ptr - mem_heap) - 4 * sizeof(mem_addr);
 282     size_t   size  = GMQCC_MEM_READHEAP(start, mem_addr);
 283     mem_addr addr  = mem_getaddr(start, size);
 284     int      side  = mem_getside(start, size);
 285
 286
 287     GMQCC_MEM_TRACE (
 288         "dump",
 289         "deallocating %s buddy (neighbour at %lu)",
 290         (side == GMQCC_MEM_BSL) ? "left" : "right",
 291         addr
 292     );
 293     GMQCC_MEM_MARKFREE(start);
 294
 295     /* while free block merge */
 296     while ((GMQCC_MEM_READHEAP(addr + 1 * sizeof(mem_addr), mem_addr)) == (mem_addr)GMQCC_MEM_FREE) {
 297         GMQCC_MEM_TRACE("dump", "merging ...");
 298         mem_removeblock(addr, size);
 299
 300         /* find new start */
 301         start = addr < start ? addr : start;
 302         size ++;
 303
 304         if (size == GMQCC_MEM_READHEAP(mem_look, mem_addr))
 305             break; /* blow up */
 306
 307         addr = mem_getaddr(start, size);
 308         GMQCC_MEM_TRACE("dump", "new block start is %lu, buddy at %lu", start, addr);
 309     }
 310
 311     /* add it */
 312     GMQCC_MEM_WRITEBS(start, size);
 313     mem_addblock     (start, size);
 314 }
 315
 316 #include <stdio.h>
 317 int main() {
 318     mem_init(1330);
 319     char *p = mem_alloc(sizeof(char) * 5);
 320     mem_free(p);
 321     mem_destroy();
 322     /* blows up on second alloc, why?  char *x = mem_alloc(200); */
 323 }