6 void factorvm::clear_free_list(heap *heap)
8 memset(&heap->free,0,sizeof(heap_free_list));
12 /* This malloc-style heap code is reasonably generic. Maybe in the future, it
13 will be used for the data heap too, if we ever get incremental
14 mark/sweep/compact GC. */
15 void factorvm::new_heap(heap *heap, cell size)
17 heap->seg = alloc_segment(align_page(size));
19 fatal_error("Out of memory in new_heap",size);
21 clear_free_list(heap);
25 void factorvm::add_to_free_list(heap *heap, free_heap_block *block)
27 if(block->size < free_list_count * block_size_increment)
29 int index = block->size / block_size_increment;
30 block->next_free = heap->free.small_blocks[index];
31 heap->free.small_blocks[index] = block;
35 block->next_free = heap->free.large_blocks;
36 heap->free.large_blocks = block;
41 /* Called after reading the code heap from the image file, and after code GC.
43 In the former case, we must add a large free block from compiling.base + size to
45 void factorvm::build_free_list(heap *heap, cell size)
47 heap_block *prev = NULL;
49 clear_free_list(heap);
51 size = (size + block_size_increment - 1) & ~(block_size_increment - 1);
53 heap_block *scan = first_block(heap);
54 free_heap_block *end = (free_heap_block *)(heap->seg->start + size);
56 /* Add all free blocks to the free list */
57 while(scan && scan < (heap_block *)end)
62 add_to_free_list(heap,(free_heap_block *)scan);
67 critical_error("Invalid scan->status",(cell)scan);
72 scan = next_block(heap,scan);
75 /* If there is room at the end of the heap, add a free block. This
76 branch is only taken after loading a new image, not after code GC */
77 if((cell)(end + 1) <= heap->seg->end)
80 end->size = heap->seg->end - (cell)end;
82 /* add final free block */
83 add_to_free_list(heap,end);
85 /* This branch is taken if the newly loaded image fits exactly, or
89 /* even if there's no room at the end of the heap for a new
90 free block, we might have to jigger it up by a few bytes in
91 case prev + prev->size */
92 if(prev) prev->size = heap->seg->end - (cell)prev;
98 void factorvm::assert_free_block(free_heap_block *block)
100 if(block->status != B_FREE)
101 critical_error("Invalid block in free list",(cell)block);
105 free_heap_block *factorvm::find_free_block(heap *heap, cell size)
109 while(attempt < free_list_count * block_size_increment)
111 int index = attempt / block_size_increment;
112 free_heap_block *block = heap->free.small_blocks[index];
115 assert_free_block(block);
116 heap->free.small_blocks[index] = block->next_free;
123 free_heap_block *prev = NULL;
124 free_heap_block *block = heap->free.large_blocks;
128 assert_free_block(block);
129 if(block->size >= size)
132 prev->next_free = block->next_free;
134 heap->free.large_blocks = block->next_free;
139 block = block->next_free;
146 free_heap_block *factorvm::split_free_block(heap *heap, free_heap_block *block, cell size)
148 if(block->size != size )
150 /* split the block in two */
151 free_heap_block *split = (free_heap_block *)((cell)block + size);
152 split->status = B_FREE;
153 split->size = block->size - size;
154 split->next_free = block->next_free;
156 add_to_free_list(heap,split);
163 /* Allocate a block of memory from the mark and sweep GC heap */
164 heap_block *factorvm::heap_allot(heap *heap, cell size)
166 size = (size + block_size_increment - 1) & ~(block_size_increment - 1);
168 free_heap_block *block = find_free_block(heap,size);
171 block = split_free_block(heap,block,size);
173 block->status = B_ALLOCATED;
181 /* Deallocates a block manually */
182 void factorvm::heap_free(heap *heap, heap_block *block)
184 block->status = B_FREE;
185 add_to_free_list(heap,(free_heap_block *)block);
189 void factorvm::mark_block(heap_block *block)
191 /* If already marked, do nothing */
192 switch(block->status)
197 block->status = B_MARKED;
200 critical_error("Marking the wrong block",(cell)block);
206 /* If in the middle of code GC, we have to grow the heap, data GC restarts from
207 scratch, so we have to unmark any marked blocks. */
208 void factorvm::unmark_marked(heap *heap)
210 heap_block *scan = first_block(heap);
214 if(scan->status == B_MARKED)
215 scan->status = B_ALLOCATED;
217 scan = next_block(heap,scan);
222 /* After code GC, all referenced code blocks have status set to B_MARKED, so any
223 which are allocated and not marked can be reclaimed. */
224 void factorvm::free_unmarked(heap *heap, heap_iterator iter)
226 clear_free_list(heap);
228 heap_block *prev = NULL;
229 heap_block *scan = first_block(heap);
237 memset(scan + 1,0,scan->size - sizeof(heap_block));
239 if(prev && prev->status == B_FREE)
240 prev->size += scan->size;
243 scan->status = B_FREE;
248 if(prev && prev->status == B_FREE)
249 prev->size += scan->size;
254 if(prev && prev->status == B_FREE)
255 add_to_free_list(heap,(free_heap_block *)prev);
256 scan->status = B_ALLOCATED;
261 critical_error("Invalid scan->status",(cell)scan);
264 scan = next_block(heap,scan);
267 if(prev && prev->status == B_FREE)
268 add_to_free_list(heap,(free_heap_block *)prev);
272 /* Compute total sum of sizes of free blocks, and size of largest free block */
273 void factorvm::heap_usage(heap *heap, cell *used, cell *total_free, cell *max_free)
279 heap_block *scan = first_block(heap);
289 *total_free += scan->size;
290 if(scan->size > *max_free)
291 *max_free = scan->size;
294 critical_error("Invalid scan->status",(cell)scan);
297 scan = next_block(heap,scan);
302 /* The size of the heap, not including the last block if it's free */
303 cell factorvm::heap_size(heap *heap)
305 heap_block *scan = first_block(heap);
307 while(next_block(heap,scan) != NULL)
308 scan = next_block(heap,scan);
310 /* this is the last block in the heap, and it is free */
311 if(scan->status == B_FREE)
312 return (cell)scan - heap->seg->start;
313 /* otherwise the last block is allocated */
315 return heap->seg->size;
319 /* Compute where each block is going to go, after compaction */
320 cell factorvm::compute_heap_forwarding(heap *heap, unordered_map<heap_block *,char *> &forwarding)
322 heap_block *scan = first_block(heap);
323 char *address = (char *)first_block(heap);
327 if(scan->status == B_ALLOCATED)
329 forwarding[scan] = address;
330 address += scan->size;
332 else if(scan->status == B_MARKED)
333 critical_error("Why is the block marked?",0);
335 scan = next_block(heap,scan);
338 return (cell)address - heap->seg->start;
342 void factorvm::compact_heap(heap *heap, unordered_map<heap_block *,char *> &forwarding)
344 heap_block *scan = first_block(heap);
348 heap_block *next = next_block(heap,scan);
350 if(scan->status == B_ALLOCATED)
351 memmove(forwarding[scan],scan,scan->size);