interpreters/glulxe/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 #include "glk.h"
   7 #include "glulxe.h"
   8
   9 typedef struct heapblock_struct {
  10   glui32 addr;
  11   glui32 len;
  12   int isfree;
  13   struct heapblock_struct *next;
  14   struct heapblock_struct *prev;
  15 } heapblock_t;
  16
  17 static glui32 heap_start = 0; /* zero for inactive heap */
  18 static int alloc_count = 0;
  19
  20 /* The heap_head/heap_tail is a doubly-linked list of blocks, both
  21    free and allocated. It is kept in address order. It should be
  22    complete -- that is, the first block starts at heap_start, and each
  23    block ends at the beginning of the next block, until the last one,
  24    which ends at endmem.
  25
  26    (Heap_start is never the same as end_mem; if there is no heap space,
  27    then the heap is inactive and heap_start is zero.)
  28
  29    Adjacent free blocks may be merged at heap_alloc() time.
  30
  31    ### To make alloc more efficient, we could keep a separate
  32    free-list. To make free more efficient, we could keep a hash
  33    table of allocations.
  34  */
  35 static heapblock_t *heap_head = NULL;
  36 static heapblock_t *heap_tail = NULL;
  37
  38 /* heap_clear():
  39    Set the heap state to inactive, and free the block lists. This is
  40    called when the game starts or restarts.
  41 */
  42 void heap_clear()
  43 {
  44   while (heap_head) {
  45     heapblock_t *blo = heap_head;
  46     heap_head = blo->next;
  47     blo->next = NULL;
  48     blo->prev = NULL;
  49     glulx_free(blo);
  50   }
  51   heap_tail = NULL;
  52
  53   if (heap_start) {
  54     glui32 res = change_memsize(heap_start, TRUE);
  55     if (res)
  56       fatal_error_i("Unable to revert memory size when deactivating heap.",
  57         heap_start);
  58   }
  59
  60   heap_start = 0;
  61   alloc_count = 0;
  62   /* heap_sanity_check(); */
  63 }
  64
  65 /* heap_is_active():
  66    Returns whether the heap is active.
  67 */
  68 int heap_is_active() {
  69   return (heap_start != 0);
  70 }
  71
  72 /* heap_get_start():
  73    Returns the start address of the heap, or 0 if the heap is not active.
  74  */
  75 glui32 heap_get_start() {
  76   return heap_start;
  77 }
  78
  79 /* heap_alloc():
  80    Allocate a block. If necessary, activate the heap and/or extend memory.
  81    This may not be available at all; #define FIXED_MEMSIZE if you want
  82    the interpreter to unconditionally refuse.
  83    Returns the memory address of the block, or 0 if the operation failed.
  84 */
  85 glui32 heap_alloc(glui32 len)
  86 {
  87   heapblock_t *blo, *newblo;
  88
  89 #ifdef FIXED_MEMSIZE
  90   return 0;
  91 #else /* FIXED_MEMSIZE */
  92
  93   if (len <= 0)
  94     fatal_error("Heap allocation length must be positive.");
  95
  96   blo = heap_head;
  97   while (blo) {
  98     if (blo->isfree && blo->len >= len)
  99       break;
 100
 101     if (!blo->isfree) {
 102       blo = blo->next;
 103       continue;
 104     }
 105
 106     if (!blo->next || !blo->next->isfree) {
 107       blo = blo->next;
 108       continue;
 109     }
 110
 111     /* This is a free block, but the next block in the list is also
 112        free, so we "advance" by merging rather than by going to
 113        blo->next. */
 114     newblo = blo->next;
 115     blo->len += newblo->len;
 116     if (newblo->next) {
 117       blo->next = newblo->next;
 118       newblo->next->prev = blo;
 119     }
 120     else {
 121       blo->next = NULL;
 122       heap_tail = blo;
 123     }
 124     newblo->next = NULL;
 125     newblo->prev = NULL;
 126     glulx_free(newblo);
 127     newblo = NULL;
 128     continue;
 129   }
 130
 131   if (!blo) {
 132     /* No free area is visible on the list. Try extending memory. How
 133        much? Double the heap size, or by 256 bytes, or by the memory
 134        length requested -- whichever is greatest. */
 135     glui32 res;
 136     glui32 extension;
 137     glui32 oldendmem = endmem;
 138
 139     extension = 0;
 140     if (heap_start)
 141       extension = endmem - heap_start;
 142     if (extension < len)
 143       extension = len;
 144     if (extension < 256)
 145       extension = 256;
 146     /* And it must be rounded up to a multiple of 256. */
 147     extension = (extension + 0xFF) & (~(glui32)0xFF);
 148
 149     res = change_memsize(endmem+extension, TRUE);
 150     if (res)
 151       return 0;
 152
 153     /* If we just started the heap, note that. */
 154     if (heap_start == 0)
 155       heap_start = oldendmem;
 156
 157     if (heap_tail && heap_tail->isfree) {
 158       /* Append the new space to the last block. */
 159       blo = heap_tail;
 160       blo->len += extension;
 161     }
 162     else {
 163       /* Append the new space to the block list, as a new block. */
 164       newblo = glulx_malloc(sizeof(heapblock_t));
 165       if (!newblo)
 166         fatal_error("Unable to allocate record for heap block.");
 167       newblo->addr = oldendmem;
 168       newblo->len = extension;
 169       newblo->isfree = TRUE;
 170       newblo->next = NULL;
 171       newblo->prev = NULL;
 172
 173       if (!heap_tail) {
 174         heap_head = newblo;
 175         heap_tail = newblo;
 176       }
 177       else {
 178         blo = heap_tail;
 179         heap_tail = newblo;
 180         blo->next = newblo;
 181         newblo->prev = blo;
 182       }
 183
 184       blo = newblo;
 185       newblo = NULL;
 186     }
 187
 188     /* and continue forwards, using this new block (blo). */
 189   }
 190
 191   /* Something strange happened. */
 192   if (!blo || !blo->isfree || blo->len < len)
 193     return 0;
 194
 195   /* We now have a free block of size len or longer. */
 196
 197   if (blo->len == len) {
 198     blo->isfree = FALSE;
 199   }
 200   else {
 201     newblo = glulx_malloc(sizeof(heapblock_t));
 202     if (!newblo)
 203       fatal_error("Unable to allocate record for heap block.");
 204     newblo->isfree = TRUE;
 205     newblo->addr = blo->addr + len;
 206     newblo->len = blo->len - len;
 207     blo->len = len;
 208     blo->isfree = FALSE;
 209     newblo->next = blo->next;
 210     if (newblo->next)
 211       newblo->next->prev = newblo;
 212     newblo->prev = blo;
 213     blo->next = newblo;
 214     if (heap_tail == blo)
 215       heap_tail = newblo;
 216   }
 217
 218   alloc_count++;
 219   /* heap_sanity_check(); */
 220   return blo->addr;
 221
 222 #endif /* FIXED_MEMSIZE */
 223 }
 224
 225 /* heap_free():
 226    Free a heap block. If necessary, deactivate the heap.
 227 */
 228 void heap_free(glui32 addr)
 229 {
 230   heapblock_t *blo;
 231
 232   for (blo = heap_head; blo; blo = blo->next) {
 233     if (blo->addr == addr)
 234       break;
 235   };
 236   if (!blo || blo->isfree)
 237     fatal_error_i("Attempt to free unallocated address from heap.", addr);
 238
 239   blo->isfree = TRUE;
 240   alloc_count--;
 241   if (alloc_count <= 0) {
 242     heap_clear();
 243   }
 244
 245   /* heap_sanity_check(); */
 246 }
 247
 248 /* heap_get_summary():
 249    Create an array of words, in the VM serialization format:
 250
 251      heap_start
 252      alloc_count
 253      addr of first block
 254      len of first block
 255      ...
 256
 257    (Note that these are glui32 values -- native byte ordering. Also,
 258    the blocks will be in address order, which is a stricter guarantee
 259    than the VM specifies; that'll help in heap_apply_summary().)
 260
 261    If the heap is inactive, store NULL. Return 0 for success;
 262    otherwise, the operation failed.
 263
 264    The array returned in summary must be freed with glulx_free() after
 265    the caller uses it.
 266 */
 267 int heap_get_summary(glui32 *valcount, glui32 **summary)
 268 {
 269   glui32 *arr, len, pos, lx;
 270   heapblock_t *blo;
 271
 272   *valcount = 0;
 273   *summary = NULL;
 274
 275   if (heap_start == 0)
 276     return 0;
 277
 278   len = 2 + 2*alloc_count;
 279   arr = glulx_malloc(len * sizeof(glui32));
 280   if (!arr)
 281     return 1;
 282
 283   pos = 0;
 284   arr[pos++] = heap_start;
 285   arr[pos++] = alloc_count;
 286
 287   for (blo = heap_head; blo; blo = blo->next) {
 288     if (blo->isfree)
 289       continue;
 290     arr[pos++] = blo->addr;
 291     arr[pos++] = blo->len;
 292   }
 293
 294   if (pos != len)
 295     fatal_error("Wrong number of active blocks in heap");
 296
 297   *valcount = len;
 298   *summary = arr;
 299   return 0;
 300 }
 301
 302 /* heap_apply_summary():
 303    Given an array of words in the above format, set up the heap to
 304    contain it. As noted above, the caller must ensure that the blocks
 305    are in address order. When this is called, the heap must be
 306    inactive.
 307
 308    Return 0 for success. Otherwise the operation failed (and, most
 309    likely, caused a fatal error).
 310 */
 311 int heap_apply_summary(glui32 valcount, glui32 *summary)
 312 {
 313   glui32 lx, jx, lastend;
 314
 315   if (heap_start)
 316     fatal_error("Heap active when heap_apply_summary called");
 317
 318   if (valcount == 0 || summary == NULL)
 319     return 0;
 320   if (valcount == 2 && summary[0] == 0 && summary[1] == 0)
 321     return 0;
 322
 323 #ifdef FIXED_MEMSIZE
 324   return 1;
 325 #else /* FIXED_MEMSIZE */
 326
 327   lx = 0;
 328   heap_start = summary[lx++];
 329   alloc_count = summary[lx++];
 330
 331   for (jx=lx; jx+2<valcount; jx+=2) {
 332     if (summary[jx] >= summary[jx+2])
 333       fatal_error("Heap block summary is out of order.");
 334   }
 335
 336   lastend = heap_start;
 337
 338   while (lx < valcount || lastend < endmem) {
 339     heapblock_t *blo;
 340
 341     blo = glulx_malloc(sizeof(heapblock_t));
 342     if (!blo)
 343       fatal_error("Unable to allocate record for heap block.");
 344
 345     if (lx >= valcount) {
 346       blo->addr = lastend;
 347       blo->len = endmem - lastend;
 348       blo->isfree = TRUE;
 349     }
 350     else {
 351       if (lastend < summary[lx]) {
 352         blo->addr = lastend;
 353         blo->len = summary[lx] - lastend;
 354         blo->isfree = TRUE;
 355       }
 356       else {
 357         blo->addr = summary[lx++];
 358         blo->len = summary[lx++];
 359         blo->isfree = FALSE;
 360       }
 361     }
 362
 363     blo->prev = NULL;
 364     blo->next = NULL;
 365
 366     if (!heap_head) {
 367       heap_head = blo;
 368       heap_tail = blo;
 369     }
 370     else {
 371       heap_tail->next = blo;
 372       blo->prev = heap_tail;
 373       heap_tail = blo;
 374     }
 375
 376     lastend = blo->addr + blo->len;
 377   }
 378
 379   /* heap_sanity_check(); */
 380
 381   return 0;
 382 #endif /* FIXED_MEMSIZE */
 383 }
 384
 385 #if 0
 386 #include <stdio.h>
 387
 388 static void heap_dump(void);
 389
 390 /* heap_dump():
 391    Print out the heap list (using printf). This exists for debugging,
 392    which is why it's ifdeffed out.
 393 */
 394 static void heap_dump()
 395 {
 396   heapblock_t *blo;
 397
 398   if (heap_start == 0) {
 399     printf("# Heap is inactive.\n");
 400     return;
 401   }
 402
 403   printf("# Heap active: %d outstanding blocks\n", alloc_count);
 404   printf("# Heap start: %ld\n", heap_start);
 405
 406   for (blo = heap_head; blo; blo = blo->next) {
 407     printf("#  %s at %ld..%ld, len %ld\n",
 408       (blo->isfree ? " free" : "*used"),
 409       blo->addr, blo->addr+blo->len, blo->len);
 410   }
 411
 412   printf("# Heap end: %ld\n", endmem);
 413 }
 414
 415 /* heap_sanity_check():
 416    Check the validity of the heap. Throw a fatal error if anything is
 417    wrong.
 418 */
 419 void heap_sanity_check()
 420 {
 421   heapblock_t *blo, *last;
 422   int livecount;
 423
 424   heap_dump();
 425
 426   if (heap_start == 0) {
 427     if (heap_head || heap_tail)
 428       fatal_error("Heap sanity: nonempty list when heap is inactive.");
 429     if (alloc_count)
 430       fatal_error_i("Heap sanity: outstanding blocks when heap is inactive.",
 431         alloc_count);
 432     return;
 433   }
 434
 435 #ifdef FIXED_MEMSIZE
 436   fatal_error("Heap sanity: heap is active, but interpreter is compiled with no allocation.");
 437 #endif /* FIXED_MEMSIZE */
 438
 439   /* When the heap is active there may, briefly, be no heapblocks on the
 440      list. */
 441
 442   last = NULL;
 443   livecount = 0;
 444
 445   for (blo = heap_head; blo; last = blo, blo = blo->next) {
 446     glui32 lastend;
 447
 448     if (blo->prev != last)
 449       fatal_error("Heap sanity: prev pointer mismatch.");
 450     if (!last)
 451       lastend = heap_start;
 452     else
 453       lastend = last->addr + last->len;
 454     if (lastend != blo->addr)
 455       fatal_error("Heap sanity: addr+len mismatch.");
 456
 457     if (!blo->isfree)
 458       livecount++;
 459   }
 460
 461   if (!last) {
 462     if (heap_start != endmem)
 463       fatal_error_i("Heap sanity: empty list, but endmem is not heap start.",
 464         heap_start);
 465     if (heap_tail)
 466       fatal_error("Heap sanity: empty list, but heap tail exists.");
 467   }
 468   else {
 469     if (last->addr + last->len != endmem)
 470       fatal_error_i("Heap sanity: last block does not end at endmem.",
 471         last->addr + last->len);
 472     if (last != heap_tail)
 473       fatal_error("Heap sanity: heap tail points wrong.");
 474   }
 475
 476   if (livecount != alloc_count)
 477     fatal_error_i("Heap sanity: wrong number of live blocks.", livecount);
 478 }
 479
 480 #endif /* 0 */
 481