Bug fixes
[rodin/chimara.git] / 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