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
9 typedef struct heapblock_struct {
13 struct heapblock_struct *next;
14 struct heapblock_struct *prev;
17 static glui32 heap_start = 0; /* zero for inactive heap */
18 static int alloc_count = 0;
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,
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.)
29 Adjacent free blocks may be merged at heap_alloc() time.
31 ### To make alloc more efficient, we could keep a separate
32 free-list. To make free more efficient, we could keep a hash
35 static heapblock_t *heap_head = NULL;
36 static heapblock_t *heap_tail = NULL;
39 Set the heap state to inactive, and free the block lists. This is
40 called when the game starts or restarts.
45 heapblock_t *blo = heap_head;
46 heap_head = blo->next;
54 glui32 res = change_memsize(heap_start, TRUE);
56 fatal_error_i("Unable to revert memory size when deactivating heap.",
62 /* heap_sanity_check(); */
66 Returns whether the heap is active.
68 int heap_is_active() {
69 return (heap_start != 0);
73 Returns the start address of the heap, or 0 if the heap is not active.
75 glui32 heap_get_start() {
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.
85 glui32 heap_alloc(glui32 len)
87 heapblock_t *blo, *newblo;
91 #else /* FIXED_MEMSIZE */
94 fatal_error("Heap allocation length must be positive.");
98 if (blo->isfree && blo->len >= len)
106 if (!blo->next || !blo->next->isfree) {
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
115 blo->len += newblo->len;
117 blo->next = newblo->next;
118 newblo->next->prev = 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. */
137 glui32 oldendmem = endmem;
141 extension = endmem - heap_start;
146 /* And it must be rounded up to a multiple of 256. */
147 extension = (extension + 0xFF) & (~(glui32)0xFF);
149 res = change_memsize(endmem+extension, TRUE);
153 /* If we just started the heap, note that. */
155 heap_start = oldendmem;
157 if (heap_tail && heap_tail->isfree) {
158 /* Append the new space to the last block. */
160 blo->len += extension;
163 /* Append the new space to the block list, as a new block. */
164 newblo = glulx_malloc(sizeof(heapblock_t));
166 fatal_error("Unable to allocate record for heap block.");
167 newblo->addr = oldendmem;
168 newblo->len = extension;
169 newblo->isfree = TRUE;
188 /* and continue forwards, using this new block (blo). */
191 /* Something strange happened. */
192 if (!blo || !blo->isfree || blo->len < len)
195 /* We now have a free block of size len or longer. */
197 if (blo->len == len) {
201 newblo = glulx_malloc(sizeof(heapblock_t));
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;
209 newblo->next = blo->next;
211 newblo->next->prev = newblo;
214 if (heap_tail == blo)
219 /* heap_sanity_check(); */
222 #endif /* FIXED_MEMSIZE */
226 Free a heap block. If necessary, deactivate the heap.
228 void heap_free(glui32 addr)
232 for (blo = heap_head; blo; blo = blo->next) {
233 if (blo->addr == addr)
236 if (!blo || blo->isfree)
237 fatal_error_i("Attempt to free unallocated address from heap.", addr);
241 if (alloc_count <= 0) {
245 /* heap_sanity_check(); */
248 /* heap_get_summary():
249 Create an array of words, in the VM serialization format:
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().)
261 If the heap is inactive, store NULL. Return 0 for success;
262 otherwise, the operation failed.
264 The array returned in summary must be freed with glulx_free() after
267 int heap_get_summary(glui32 *valcount, glui32 **summary)
269 glui32 *arr, len, pos, lx;
278 len = 2 + 2*alloc_count;
279 arr = glulx_malloc(len * sizeof(glui32));
284 arr[pos++] = heap_start;
285 arr[pos++] = alloc_count;
287 for (blo = heap_head; blo; blo = blo->next) {
290 arr[pos++] = blo->addr;
291 arr[pos++] = blo->len;
295 fatal_error("Wrong number of active blocks in heap");
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
308 Return 0 for success. Otherwise the operation failed (and, most
309 likely, caused a fatal error).
311 int heap_apply_summary(glui32 valcount, glui32 *summary)
313 glui32 lx, jx, lastend;
316 fatal_error("Heap active when heap_apply_summary called");
318 if (valcount == 0 || summary == NULL)
320 if (valcount == 2 && summary[0] == 0 && summary[1] == 0)
325 #else /* FIXED_MEMSIZE */
328 heap_start = summary[lx++];
329 alloc_count = summary[lx++];
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.");
336 lastend = heap_start;
338 while (lx < valcount || lastend < endmem) {
341 blo = glulx_malloc(sizeof(heapblock_t));
343 fatal_error("Unable to allocate record for heap block.");
345 if (lx >= valcount) {
347 blo->len = endmem - lastend;
351 if (lastend < summary[lx]) {
353 blo->len = summary[lx] - lastend;
357 blo->addr = summary[lx++];
358 blo->len = summary[lx++];
371 heap_tail->next = blo;
372 blo->prev = heap_tail;
376 lastend = blo->addr + blo->len;
379 /* heap_sanity_check(); */
382 #endif /* FIXED_MEMSIZE */
388 static void heap_dump(void);
391 Print out the heap list (using printf). This exists for debugging,
392 which is why it's ifdeffed out.
394 static void heap_dump()
398 if (heap_start == 0) {
399 printf("# Heap is inactive.\n");
403 printf("# Heap active: %d outstanding blocks\n", alloc_count);
404 printf("# Heap start: %ld\n", heap_start);
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);
412 printf("# Heap end: %ld\n", endmem);
415 /* heap_sanity_check():
416 Check the validity of the heap. Throw a fatal error if anything is
419 void heap_sanity_check()
421 heapblock_t *blo, *last;
426 if (heap_start == 0) {
427 if (heap_head || heap_tail)
428 fatal_error("Heap sanity: nonempty list when heap is inactive.");
430 fatal_error_i("Heap sanity: outstanding blocks when heap is inactive.",
436 fatal_error("Heap sanity: heap is active, but interpreter is compiled with no allocation.");
437 #endif /* FIXED_MEMSIZE */
439 /* When the heap is active there may, briefly, be no heapblocks on the
445 for (blo = heap_head; blo; last = blo, blo = blo->next) {
448 if (blo->prev != last)
449 fatal_error("Heap sanity: prev pointer mismatch.");
451 lastend = heap_start;
453 lastend = last->addr + last->len;
454 if (lastend != blo->addr)
455 fatal_error("Heap sanity: addr+len mismatch.");
462 if (heap_start != endmem)
463 fatal_error_i("Heap sanity: empty list, but endmem is not heap start.",
466 fatal_error("Heap sanity: empty list, but heap tail exists.");
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.");
476 if (livecount != alloc_count)
477 fatal_error_i("Heap sanity: wrong number of live blocks.", livecount);