6 static void clear_free_list(heap *heap)
8 memset(&heap->free,0,sizeof(heap_free_list));
11 /* This malloc-style heap code is reasonably generic. Maybe in the future, it
12 will be used for the data heap too, if we ever get incremental
13 mark/sweep/compact GC. */
14 void new_heap(heap *heap, cell size)
16 heap->seg = alloc_segment(align_page(size));
18 fatal_error("Out of memory in new_heap",size);
20 clear_free_list(heap);
23 static void add_to_free_list(heap *heap, free_heap_block *block)
25 if(block->size < free_list_count * block_size_increment)
27 int index = block->size / block_size_increment;
28 block->next_free = heap->free.small_blocks[index];
29 heap->free.small_blocks[index] = block;
33 block->next_free = heap->free.large_blocks;
34 heap->free.large_blocks = block;
38 /* Called after reading the code heap from the image file, and after code GC.
40 In the former case, we must add a large free block from compiling.base + size to
42 void build_free_list(heap *heap, cell size)
44 heap_block *prev = NULL;
46 clear_free_list(heap);
48 size = (size + block_size_increment - 1) & ~(block_size_increment - 1);
50 heap_block *scan = first_block(heap);
51 free_heap_block *end = (free_heap_block *)(heap->seg->start + size);
53 /* Add all free blocks to the free list */
54 while(scan && scan < (heap_block *)end)
59 add_to_free_list(heap,(free_heap_block *)scan);
64 critical_error("Invalid scan->status",(cell)scan);
69 scan = next_block(heap,scan);
72 /* If there is room at the end of the heap, add a free block. This
73 branch is only taken after loading a new image, not after code GC */
74 if((cell)(end + 1) <= heap->seg->end)
77 end->size = heap->seg->end - (cell)end;
79 /* add final free block */
80 add_to_free_list(heap,end);
82 /* This branch is taken if the newly loaded image fits exactly, or
86 /* even if there's no room at the end of the heap for a new
87 free block, we might have to jigger it up by a few bytes in
88 case prev + prev->size */
89 if(prev) prev->size = heap->seg->end - (cell)prev;
94 static void assert_free_block(free_heap_block *block)
96 if(block->status != B_FREE)
97 critical_error("Invalid block in free list",(cell)block);
100 static free_heap_block *find_free_block(heap *heap, cell size)
104 while(attempt < free_list_count * block_size_increment)
106 int index = attempt / block_size_increment;
107 free_heap_block *block = heap->free.small_blocks[index];
110 assert_free_block(block);
111 heap->free.small_blocks[index] = block->next_free;
118 free_heap_block *prev = NULL;
119 free_heap_block *block = heap->free.large_blocks;
123 assert_free_block(block);
124 if(block->size >= size)
127 prev->next_free = block->next_free;
129 heap->free.large_blocks = block->next_free;
134 block = block->next_free;
140 static free_heap_block *split_free_block(heap *heap, free_heap_block *block, cell size)
142 if(block->size != size )
144 /* split the block in two */
145 free_heap_block *split = (free_heap_block *)((cell)block + size);
146 split->status = B_FREE;
147 split->size = block->size - size;
148 split->next_free = block->next_free;
150 add_to_free_list(heap,split);
156 /* Allocate a block of memory from the mark and sweep GC heap */
157 heap_block *heap_allot(heap *heap, cell size)
159 size = (size + block_size_increment - 1) & ~(block_size_increment - 1);
161 free_heap_block *block = find_free_block(heap,size);
164 block = split_free_block(heap,block,size);
166 block->status = B_ALLOCATED;
173 /* Deallocates a block manually */
174 void heap_free(heap *heap, heap_block *block)
176 block->status = B_FREE;
177 add_to_free_list(heap,(free_heap_block *)block);
180 void mark_block(heap_block *block)
182 /* If already marked, do nothing */
183 switch(block->status)
188 block->status = B_MARKED;
191 critical_error("Marking the wrong block",(cell)block);
196 /* If in the middle of code GC, we have to grow the heap, data GC restarts from
197 scratch, so we have to unmark any marked blocks. */
198 void unmark_marked(heap *heap)
200 heap_block *scan = first_block(heap);
204 if(scan->status == B_MARKED)
205 scan->status = B_ALLOCATED;
207 scan = next_block(heap,scan);
211 /* After code GC, all referenced code blocks have status set to B_MARKED, so any
212 which are allocated and not marked can be reclaimed. */
213 void free_unmarked(heap *heap, heap_iterator iter)
215 clear_free_list(heap);
217 heap_block *prev = NULL;
218 heap_block *scan = first_block(heap);
226 memset(scan + 1,0,scan->size - sizeof(heap_block));
228 if(prev && prev->status == B_FREE)
229 prev->size += scan->size;
232 scan->status = B_FREE;
237 if(prev && prev->status == B_FREE)
238 prev->size += scan->size;
243 if(prev && prev->status == B_FREE)
244 add_to_free_list(heap,(free_heap_block *)prev);
245 scan->status = B_ALLOCATED;
250 critical_error("Invalid scan->status",(cell)scan);
253 scan = next_block(heap,scan);
256 if(prev && prev->status == B_FREE)
257 add_to_free_list(heap,(free_heap_block *)prev);
260 /* Compute total sum of sizes of free blocks, and size of largest free block */
261 void heap_usage(heap *heap, cell *used, cell *total_free, cell *max_free)
267 heap_block *scan = first_block(heap);
277 *total_free += scan->size;
278 if(scan->size > *max_free)
279 *max_free = scan->size;
282 critical_error("Invalid scan->status",(cell)scan);
285 scan = next_block(heap,scan);
289 /* The size of the heap, not including the last block if it's free */
290 cell heap_size(heap *heap)
292 heap_block *scan = first_block(heap);
294 while(next_block(heap,scan) != NULL)
295 scan = next_block(heap,scan);
297 /* this is the last block in the heap, and it is free */
298 if(scan->status == B_FREE)
299 return (cell)scan - heap->seg->start;
300 /* otherwise the last block is allocated */
302 return heap->seg->size;
305 /* Compute where each block is going to go, after compaction */
306 cell compute_heap_forwarding(heap *heap, unordered_map<heap_block *,char *> &forwarding)
308 heap_block *scan = first_block(heap);
309 char *address = (char *)first_block(heap);
313 if(scan->status == B_ALLOCATED)
315 forwarding[scan] = address;
316 address += scan->size;
318 else if(scan->status == B_MARKED)
319 critical_error("Why is the block marked?",0);
321 scan = next_block(heap,scan);
324 return (cell)address - heap->seg->start;
327 void compact_heap(heap *heap, unordered_map<heap_block *,char *> &forwarding)
329 heap_block *scan = first_block(heap);
333 heap_block *next = next_block(heap,scan);
335 if(scan->status == B_ALLOCATED)
336 memmove(forwarding[scan],scan,scan->size);