interpreters/git/heap.c

   1 /* heap.c: Glulxe code related to the dynamic allocation heap.
   2     Designed by Andrew Plotkin <erkyrath@eblong.com>
   3     http://eblong.com/zarf/glulx/index.html
   4 */
   5
   6 #define glulx_malloc malloc
   7 #define glulx_free free
   8
   9 #ifndef TRUE
  10 #define TRUE 1
  11 #endif
  12 #ifndef FALSE
  13 #define FALSE 0
  14 #endif
  15
  16 #include "glk.h"
  17 #include "git.h"
  18
  19 typedef struct heapblock_struct {
  20   glui32 addr;
  21   glui32 len;
  22   int isfree;
  23   struct heapblock_struct *next;
  24   struct heapblock_struct *prev;
  25 } heapblock_t;
  26
  27 static glui32 heap_start = 0; /* zero for inactive heap */
  28 static int alloc_count = 0;
  29
  30 /* The heap_head/heap_tail is a doubly-linked list of blocks, both
  31    free and allocated. It is kept in address order. It should be
  32    complete -- that is, the first block starts at heap_start, and each
  33    block ends at the beginning of the next block, until the last one,
  34    which ends at gEndMem.
  35
  36    (Heap_start is never the same as end_mem; if there is no heap space,
  37    then the heap is inactive and heap_start is zero.)
  38
  39    Adjacent free blocks may be merged at heap_alloc() time.
  40
  41    ### To make alloc more efficient, we could keep a separate
  42    free-list. To make free more efficient, we could keep a hash
  43    table of allocations.
  44  */
  45 static heapblock_t *heap_head = NULL;
  46 static heapblock_t *heap_tail = NULL;
  47
  48 /* heap_clear():
  49    Set the heap state to inactive, and free the block lists. This is
  50    called when the game starts or restarts.
  51 */
  52 void heap_clear()
  53 {
  54   while (heap_head) {
  55     heapblock_t *blo = heap_head;
  56     heap_head = blo->next;
  57     blo->next = NULL;
  58     blo->prev = NULL;
  59     glulx_free(blo);
  60   }
  61   heap_tail = NULL;
  62
  63   if (heap_start) {
  64     glui32 res = resizeMemory(heap_start, 1);
  65     if (res)
  66       fatalError("Unable to revert memory size when deactivating heap.");
  67   }
  68
  69   heap_start = 0;
  70   alloc_count = 0;
  71   /* heap_sanity_check(); */
  72 }
  73
  74 /* heap_is_active():
  75    Returns whether the heap is active.
  76 */
  77 int heap_is_active() {
  78   return (heap_start != 0);
  79 }
  80
  81 /* heap_get_start():
  82    Returns the start address of the heap, or 0 if the heap is not active.
  83  */
  84 glui32 heap_get_start() {
  85   return heap_start;
  86 }
  87
  88 /* heap_alloc():
  89    Allocate a block. If necessary, activate the heap and/or extend memory.
  90    Returns the memory address of the block, or 0 if the operation failed.
  91 */
  92 glui32 heap_alloc(glui32 len)
  93 {
  94   heapblock_t *blo, *newblo;
  95
  96   if (len <= 0)
  97     fatalError("Heap allocation length must be positive.");
  98
  99   blo = heap_head;
 100   while (blo) {
 101     if (blo->isfree && blo->len >= len)
 102       break;
 103
 104     if (!blo->isfree) {
 105       blo = blo->next;
 106       continue;
 107     }
 108
 109     if (!blo->next || !blo->next->isfree) {
 110       blo = blo->next;
 111       continue;
 112     }
 113
 114     /* This is a free block, but the next block in the list is also
 115        free, so we "advance" by merging rather than by going to
 116        blo->next. */
 117     newblo = blo->next;
 118     blo->len += newblo->len;
 119     if (newblo->next) {
 120       blo->next = newblo->next;
 121       newblo->next->prev = blo;
 122     }
 123     else {
 124       blo->next = NULL;
 125       heap_tail = blo;
 126     }
 127     newblo->next = NULL;
 128     newblo->prev = NULL;
 129     glulx_free(newblo);
 130     newblo = NULL;
 131     continue;
 132   }
 133
 134   if (!blo) {
 135     /* No free area is visible on the list. Try extending memory. How
 136        much? Double the heap size, or by 256 bytes, or by the memory
 137        length requested -- whichever is greatest. */
 138     glui32 res;
 139     glui32 extension;
 140     glui32 oldendmem = gEndMem;
 141
 142     extension = 0;
 143     if (heap_start)
 144       extension = gEndMem - heap_start;
 145     if (extension < len)
 146       extension = len;
 147     if (extension < 256)
 148       extension = 256;
 149     /* And it must be rounded up to a multiple of 256. */
 150     extension = (extension + 0xFF) & (~(glui32)0xFF);
 151
 152     res = resizeMemory(gEndMem+extension, 1);
 153     if (res)
 154       return 0;
 155
 156     /* If we just started the heap, note that. */
 157     if (heap_start == 0)
 158       heap_start = oldendmem;
 159
 160     if (heap_tail && heap_tail->isfree) {
 161       /* Append the new space to the last block. */
 162       blo = heap_tail;
 163       blo->len += extension;
 164     }
 165     else {
 166       /* Append the new space to the block list, as a new block. */
 167       newblo = glulx_malloc(sizeof(heapblock_t));
 168       if (!newblo)
 169         fatalError("Unable to allocate record for heap block.");
 170       newblo->addr = oldendmem;
 171       newblo->len = extension;
 172       newblo->isfree = TRUE;
 173       newblo->next = NULL;
 174       newblo->prev = NULL;
 175
 176       if (!heap_tail) {
 177         heap_head = newblo;
 178         heap_tail = newblo;
 179       }
 180       else {
 181         blo = heap_tail;
 182         heap_tail = newblo;
 183         blo->next = newblo;
 184         newblo->prev = blo;
 185       }
 186
 187       blo = newblo;
 188       newblo = NULL;
 189     }
 190
 191     /* and continue forwards, using this new block (blo). */
 192   }
 193
 194   /* Something strange happened. */
 195   if (!blo || !blo->isfree || blo->len < len)
 196     return 0;
 197
 198   /* We now have a free block of size len or longer. */
 199
 200   if (blo->len == len) {
 201     blo->isfree = FALSE;
 202   }
 203   else {
 204     newblo = glulx_malloc(sizeof(heapblock_t));
 205     if (!newblo)
 206       fatalError("Unable to allocate record for heap block.");
 207     newblo->isfree = TRUE;
 208     newblo->addr = blo->addr + len;
 209     newblo->len = blo->len - len;
 210     blo->len = len;
 211     blo->isfree = FALSE;
 212     newblo->next = blo->next;
 213     if (newblo->next)
 214       newblo->next->prev = newblo;
 215     newblo->prev = blo;
 216     blo->next = newblo;
 217     if (heap_tail == blo)
 218       heap_tail = newblo;
 219   }
 220
 221   alloc_count++;
 222   /* heap_sanity_check(); */
 223   return blo->addr;
 224 }
 225
 226 /* heap_free():
 227    Free a heap block. If necessary, deactivate the heap.
 228 */
 229 void heap_free(glui32 addr)
 230 {
 231   heapblock_t *blo;
 232
 233   for (blo = heap_head; blo; blo = blo->next) {
 234     if (blo->addr == addr)
 235       break;
 236   };
 237   if (!blo || blo->isfree)
 238     fatalError("Attempt to free unallocated address from heap.");
 239
 240   blo->isfree = TRUE;
 241   alloc_count--;
 242   if (alloc_count <= 0) {
 243     heap_clear();
 244   }
 245
 246   /* heap_sanity_check(); */
 247 }
 248
 249 /* heap_get_summary():
 250    Create an array of words, in the VM serialization format:
 251
 252      heap_start
 253      alloc_count
 254      addr of first block
 255      len of first block
 256      ...
 257
 258    (Note that these are glui32 values -- native byte ordering. Also,
 259    the blocks will be in address order, which is a stricter guarantee
 260    than the VM specifies; that'll help in heap_apply_summary().)
 261
 262    If the heap is inactive, store NULL. Return 0 for success;
 263    otherwise, the operation failed.
 264
 265    The array returned in summary must be freed with glulx_free() after
 266    the caller uses it.
 267 */
 268 int heap_get_summary(glui32 *valcount, glui32 **summary)
 269 {
 270   glui32 *arr, len, pos;
 271   heapblock_t *blo;
 272
 273   *valcount = 0;
 274   *summary = NULL;
 275
 276   if (heap_start == 0)
 277     return 0;
 278
 279   len = 2 + 2*alloc_count;
 280   arr = glulx_malloc(len * sizeof(glui32));
 281   if (!arr)
 282     return 1;
 283
 284   pos = 0;
 285   arr[pos++] = heap_start;
 286   arr[pos++] = alloc_count;
 287
 288   for (blo = heap_head; blo; blo = blo->next) {
 289     if (blo->isfree)
 290       continue;
 291     arr[pos++] = blo->addr;
 292     arr[pos++] = blo->len;
 293   }
 294
 295   if (pos != len)
 296     fatalError("Wrong number of active blocks in heap");
 297
 298   *valcount = len;
 299   *summary = arr;
 300   return 0;
 301 }
 302
 303 /* heap_apply_summary():
 304    Given an array of words in the above format, set up the heap to
 305    contain it. As noted above, the caller must ensure that the blocks
 306    are in address order. When this is called, the heap must be
 307    inactive.
 308
 309    Return 0 for success. Otherwise the operation failed (and, most
 310    likely, caused a fatal error).
 311 */
 312 int heap_apply_summary(glui32 valcount, glui32 *summary)
 313 {
 314   glui32 lx, jx, lastend;
 315
 316   if (heap_start)
 317     fatalError("Heap active when heap_apply_summary called");
 318
 319   if (valcount == 0 || summary == NULL)
 320     return 0;
 321   if (valcount == 2 && summary[0] == 0 && summary[1] == 0)
 322     return 0;
 323
 324   lx = 0;
 325   heap_start = summary[lx++];
 326   alloc_count = summary[lx++];
 327
 328   for (jx=lx; jx+2<valcount; jx+=2) {
 329     if (summary[jx] >= summary[jx+2])
 330       fatalError("Heap block summary is out of order.");
 331   }
 332
 333   lastend = heap_start;
 334
 335   while (lx < valcount || lastend < gEndMem) {
 336     heapblock_t *blo;
 337
 338     blo = glulx_malloc(sizeof(heapblock_t));
 339     if (!blo)
 340       fatalError("Unable to allocate record for heap block.");
 341
 342     if (lx >= valcount) {
 343       blo->addr = lastend;
 344       blo->len = gEndMem - lastend;
 345       blo->isfree = TRUE;
 346     }
 347     else {
 348       if (lastend < summary[lx]) {
 349         blo->addr = lastend;
 350         blo->len = summary[lx] - lastend;
 351         blo->isfree = TRUE;
 352       }
 353       else {
 354         blo->addr = summary[lx++];
 355         blo->len = summary[lx++];
 356         blo->isfree = FALSE;
 357       }
 358     }
 359
 360     blo->prev = NULL;
 361     blo->next = NULL;
 362
 363     if (!heap_head) {
 364       heap_head = blo;
 365       heap_tail = blo;
 366     }
 367     else {
 368       heap_tail->next = blo;
 369       blo->prev = heap_tail;
 370       heap_tail = blo;
 371     }
 372
 373     lastend = blo->addr + blo->len;
 374   }
 375
 376   /* heap_sanity_check(); */
 377
 378   return 0;
 379 }
 380