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