X-Git-Url: https://git.stderr.nl/gitweb?a=blobdiff_plain;f=interpreters%2Fglulxe%2Fheap.c;fp=interpreters%2Fglulxe%2Fheap.c;h=ea5bf24afa8e914d604b04b4d3e1ccce49e91fa4;hb=147a8cbf17f2b3379277bf7d37cda9866510f16c;hp=0000000000000000000000000000000000000000;hpb=7de488aa6a1709a4d5c59b5ff59862105c1748c5;p=rodin%2Fchimara.git

diff --git a/interpreters/glulxe/heap.c b/interpreters/glulxe/heap.c
new file mode 100644
index 0000000..ea5bf24
--- /dev/null
+++ b/interpreters/glulxe/heap.c
@@ -0,0 +1,481 @@
+/* heap.c: Glulxe code related to the dynamic allocation heap.
+    Designed by Andrew Plotkin <erkyrath@eblong.com>
+    http://eblong.com/zarf/glulx/index.html
+*/
+
+#include "glk.h"
+#include "glulxe.h"
+
+typedef struct heapblock_struct {
+  glui32 addr;
+  glui32 len;
+  int isfree;
+  struct heapblock_struct *next;
+  struct heapblock_struct *prev;
+} heapblock_t;
+
+static glui32 heap_start = 0; /* zero for inactive heap */
+static int alloc_count = 0;
+
+/* The heap_head/heap_tail is a doubly-linked list of blocks, both
+   free and allocated. It is kept in address order. It should be
+   complete -- that is, the first block starts at heap_start, and each
+   block ends at the beginning of the next block, until the last one,
+   which ends at endmem.
+
+   (Heap_start is never the same as end_mem; if there is no heap space,
+   then the heap is inactive and heap_start is zero.)
+
+   Adjacent free blocks may be merged at heap_alloc() time.
+
+   ### To make alloc more efficient, we could keep a separate
+   free-list. To make free more efficient, we could keep a hash
+   table of allocations.
+ */
+static heapblock_t *heap_head = NULL;
+static heapblock_t *heap_tail = NULL;
+
+/* heap_clear():
+   Set the heap state to inactive, and free the block lists. This is
+   called when the game starts or restarts.
+*/
+void heap_clear()
+{
+  while (heap_head) {
+    heapblock_t *blo = heap_head;
+    heap_head = blo->next;
+    blo->next = NULL;
+    blo->prev = NULL;
+    glulx_free(blo);
+  }
+  heap_tail = NULL;
+
+  if (heap_start) {
+    glui32 res = change_memsize(heap_start, TRUE);
+    if (res)
+      fatal_error_i("Unable to revert memory size when deactivating heap.",
+        heap_start);
+  }
+
+  heap_start = 0;
+  alloc_count = 0;
+  /* heap_sanity_check(); */
+}
+
+/* heap_is_active():
+   Returns whether the heap is active.
+*/
+int heap_is_active() {
+  return (heap_start != 0);
+}
+
+/* heap_get_start():
+   Returns the start address of the heap, or 0 if the heap is not active.
+ */
+glui32 heap_get_start() {
+  return heap_start;
+}
+
+/* heap_alloc(): 
+   Allocate a block. If necessary, activate the heap and/or extend memory.
+   This may not be available at all; #define FIXED_MEMSIZE if you want
+   the interpreter to unconditionally refuse.
+   Returns the memory address of the block, or 0 if the operation failed.
+*/
+glui32 heap_alloc(glui32 len)
+{
+  heapblock_t *blo, *newblo;
+
+#ifdef FIXED_MEMSIZE
+  return 0;
+#else /* FIXED_MEMSIZE */
+
+  if (len <= 0)
+    fatal_error("Heap allocation length must be positive.");
+
+  blo = heap_head;
+  while (blo) {
+    if (blo->isfree && blo->len >= len)
+      break;
+
+    if (!blo->isfree) {
+      blo = blo->next;
+      continue;
+    }
+
+    if (!blo->next || !blo->next->isfree) {
+      blo = blo->next;
+      continue;
+    }
+
+    /* This is a free block, but the next block in the list is also
+       free, so we "advance" by merging rather than by going to
+       blo->next. */
+    newblo = blo->next;
+    blo->len += newblo->len;
+    if (newblo->next) {
+      blo->next = newblo->next;
+      newblo->next->prev = blo;
+    }
+    else {
+      blo->next = NULL;
+      heap_tail = blo;
+    }
+    newblo->next = NULL;
+    newblo->prev = NULL;
+    glulx_free(newblo);
+    newblo = NULL;
+    continue;
+  }
+
+  if (!blo) {
+    /* No free area is visible on the list. Try extending memory. How
+       much? Double the heap size, or by 256 bytes, or by the memory
+       length requested -- whichever is greatest. */
+    glui32 res;
+    glui32 extension;
+    glui32 oldendmem = endmem;
+
+    extension = 0;
+    if (heap_start)
+      extension = endmem - heap_start;
+    if (extension < len)
+      extension = len;
+    if (extension < 256)
+      extension = 256;
+    /* And it must be rounded up to a multiple of 256. */
+    extension = (extension + 0xFF) & (~(glui32)0xFF);
+
+    res = change_memsize(endmem+extension, TRUE);
+    if (res)
+      return 0;
+
+    /* If we just started the heap, note that. */
+    if (heap_start == 0)
+      heap_start = oldendmem;
+
+    if (heap_tail && heap_tail->isfree) {
+      /* Append the new space to the last block. */
+      blo = heap_tail;
+      blo->len += extension;
+    }
+    else {
+      /* Append the new space to the block list, as a new block. */
+      newblo = glulx_malloc(sizeof(heapblock_t));
+      if (!newblo)
+        fatal_error("Unable to allocate record for heap block.");
+      newblo->addr = oldendmem;
+      newblo->len = extension;
+      newblo->isfree = TRUE;
+      newblo->next = NULL;
+      newblo->prev = NULL;
+
+      if (!heap_tail) {
+        heap_head = newblo;
+        heap_tail = newblo;
+      }
+      else {
+        blo = heap_tail;
+        heap_tail = newblo;
+        blo->next = newblo;
+        newblo->prev = blo;
+      }
+
+      blo = newblo;
+      newblo = NULL;
+    }
+
+    /* and continue forwards, using this new block (blo). */
+  }
+
+  /* Something strange happened. */
+  if (!blo || !blo->isfree || blo->len < len)
+    return 0;
+
+  /* We now have a free block of size len or longer. */
+
+  if (blo->len == len) {
+    blo->isfree = FALSE;
+  }
+  else {
+    newblo = glulx_malloc(sizeof(heapblock_t));
+    if (!newblo)
+      fatal_error("Unable to allocate record for heap block.");
+    newblo->isfree = TRUE;
+    newblo->addr = blo->addr + len;
+    newblo->len = blo->len - len;
+    blo->len = len;
+    blo->isfree = FALSE;
+    newblo->next = blo->next;
+    if (newblo->next)
+      newblo->next->prev = newblo;
+    newblo->prev = blo;
+    blo->next = newblo;
+    if (heap_tail == blo)
+      heap_tail = newblo;
+  }
+
+  alloc_count++;
+  /* heap_sanity_check(); */
+  return blo->addr;
+
+#endif /* FIXED_MEMSIZE */
+}
+
+/* heap_free():
+   Free a heap block. If necessary, deactivate the heap.
+*/
+void heap_free(glui32 addr)
+{
+  heapblock_t *blo;
+
+  for (blo = heap_head; blo; blo = blo->next) { 
+    if (blo->addr == addr)
+      break;
+  };
+  if (!blo || blo->isfree)
+    fatal_error_i("Attempt to free unallocated address from heap.", addr);
+
+  blo->isfree = TRUE;
+  alloc_count--;
+  if (alloc_count <= 0) {
+    heap_clear();
+  }
+
+  /* heap_sanity_check(); */
+}
+
+/* heap_get_summary():
+   Create an array of words, in the VM serialization format:
+
+     heap_start
+     alloc_count
+     addr of first block
+     len of first block
+     ...
+
+   (Note that these are glui32 values -- native byte ordering. Also,
+   the blocks will be in address order, which is a stricter guarantee
+   than the VM specifies; that'll help in heap_apply_summary().)
+
+   If the heap is inactive, store NULL. Return 0 for success;
+   otherwise, the operation failed.
+
+   The array returned in summary must be freed with glulx_free() after
+   the caller uses it.
+*/
+int heap_get_summary(glui32 *valcount, glui32 **summary)
+{
+  glui32 *arr, len, pos, lx;
+  heapblock_t *blo;
+
+  *valcount = 0;
+  *summary = NULL;
+
+  if (heap_start == 0)
+    return 0;
+
+  len = 2 + 2*alloc_count;
+  arr = glulx_malloc(len * sizeof(glui32));
+  if (!arr)
+    return 1;
+
+  pos = 0;
+  arr[pos++] = heap_start;
+  arr[pos++] = alloc_count;
+
+  for (blo = heap_head; blo; blo = blo->next) {
+    if (blo->isfree)
+      continue;
+    arr[pos++] = blo->addr;
+    arr[pos++] = blo->len;
+  }
+
+  if (pos != len)
+    fatal_error("Wrong number of active blocks in heap");
+
+  *valcount = len;
+  *summary = arr;
+  return 0;
+}
+
+/* heap_apply_summary():
+   Given an array of words in the above format, set up the heap to
+   contain it. As noted above, the caller must ensure that the blocks
+   are in address order. When this is called, the heap must be
+   inactive.
+
+   Return 0 for success. Otherwise the operation failed (and, most
+   likely, caused a fatal error).
+*/
+int heap_apply_summary(glui32 valcount, glui32 *summary)
+{
+  glui32 lx, jx, lastend;
+
+  if (heap_start)
+    fatal_error("Heap active when heap_apply_summary called");
+
+  if (valcount == 0 || summary == NULL)
+    return 0;
+  if (valcount == 2 && summary[0] == 0 && summary[1] == 0)
+    return 0;
+
+#ifdef FIXED_MEMSIZE
+  return 1;
+#else /* FIXED_MEMSIZE */
+
+  lx = 0;
+  heap_start = summary[lx++];
+  alloc_count = summary[lx++];
+
+  for (jx=lx; jx+2<valcount; jx+=2) {
+    if (summary[jx] >= summary[jx+2])
+      fatal_error("Heap block summary is out of order.");
+  }
+
+  lastend = heap_start;
+
+  while (lx < valcount || lastend < endmem) {
+    heapblock_t *blo;
+
+    blo = glulx_malloc(sizeof(heapblock_t));
+    if (!blo)
+      fatal_error("Unable to allocate record for heap block.");
+
+    if (lx >= valcount) {
+      blo->addr = lastend;
+      blo->len = endmem - lastend;
+      blo->isfree = TRUE;
+    }
+    else {
+      if (lastend < summary[lx]) {
+        blo->addr = lastend;
+        blo->len = summary[lx] - lastend;
+        blo->isfree = TRUE;
+      }
+      else {
+        blo->addr = summary[lx++];
+        blo->len = summary[lx++];
+        blo->isfree = FALSE;
+      }
+    }
+
+    blo->prev = NULL;
+    blo->next = NULL;
+
+    if (!heap_head) {
+      heap_head = blo;
+      heap_tail = blo;
+    }
+    else {
+      heap_tail->next = blo;
+      blo->prev = heap_tail;
+      heap_tail = blo;
+    }
+
+    lastend = blo->addr + blo->len;
+  }
+
+  /* heap_sanity_check(); */
+
+  return 0;
+#endif /* FIXED_MEMSIZE */
+}
+
+#if 0
+#include <stdio.h>
+
+static void heap_dump(void);
+
+/* heap_dump():
+   Print out the heap list (using printf). This exists for debugging,
+   which is why it's ifdeffed out.
+*/
+static void heap_dump()
+{
+  heapblock_t *blo;
+
+  if (heap_start == 0) {
+    printf("# Heap is inactive.\n");
+    return;    
+  }
+
+  printf("# Heap active: %d outstanding blocks\n", alloc_count);
+  printf("# Heap start: %ld\n", heap_start);
+
+  for (blo = heap_head; blo; blo = blo->next) {
+    printf("#  %s at %ld..%ld, len %ld\n", 
+      (blo->isfree ? " free" : "*used"),
+      blo->addr, blo->addr+blo->len, blo->len);
+  }
+
+  printf("# Heap end: %ld\n", endmem);
+}
+
+/* heap_sanity_check():
+   Check the validity of the heap. Throw a fatal error if anything is
+   wrong.
+*/
+void heap_sanity_check()
+{
+  heapblock_t *blo, *last;
+  int livecount;
+
+  heap_dump();
+
+  if (heap_start == 0) {
+    if (heap_head || heap_tail)
+      fatal_error("Heap sanity: nonempty list when heap is inactive.");
+    if (alloc_count)
+      fatal_error_i("Heap sanity: outstanding blocks when heap is inactive.",
+        alloc_count);
+    return;
+  }
+
+#ifdef FIXED_MEMSIZE
+  fatal_error("Heap sanity: heap is active, but interpreter is compiled with no allocation.");
+#endif /* FIXED_MEMSIZE */
+
+  /* When the heap is active there may, briefly, be no heapblocks on the
+     list. */
+
+  last = NULL;
+  livecount = 0;
+
+  for (blo = heap_head; blo; last = blo, blo = blo->next) {
+    glui32 lastend;
+
+    if (blo->prev != last)
+      fatal_error("Heap sanity: prev pointer mismatch.");
+    if (!last) 
+      lastend = heap_start;
+    else
+      lastend = last->addr + last->len;
+    if (lastend != blo->addr)
+      fatal_error("Heap sanity: addr+len mismatch.");
+
+    if (!blo->isfree)
+      livecount++;
+  }
+
+  if (!last) {
+    if (heap_start != endmem)
+      fatal_error_i("Heap sanity: empty list, but endmem is not heap start.",
+        heap_start);
+    if (heap_tail)
+      fatal_error("Heap sanity: empty list, but heap tail exists.");
+  }
+  else {
+    if (last->addr + last->len != endmem)
+      fatal_error_i("Heap sanity: last block does not end at endmem.",
+        last->addr + last->len);
+    if (last != heap_tail)
+      fatal_error("Heap sanity: heap tail points wrong.");
+  }
+
+  if (livecount != alloc_count)
+    fatal_error_i("Heap sanity: wrong number of live blocks.", livecount);
+}
+
+#endif /* 0 */
+