vm/code_gc.cpp

   1 #include "master.hpp"
   2
   3 namespace factor
   4 {
   5
   6 void factorvm::clear_free_list(heap *heap)
   7 {
   8         memset(&heap->free,0,sizeof(heap_free_list));
   9 }
  10
  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 factorvm::new_heap(heap *heap, cell size)
  15 {
  16         heap->seg = alloc_segment(align_page(size));
  17         if(!heap->seg)
  18                 fatal_error("Out of memory in new_heap",size);
  19
  20         clear_free_list(heap);
  21 }
  22
  23 void factorvm::add_to_free_list(heap *heap, free_heap_block *block)
  24 {
  25         if(block->size < free_list_count * block_size_increment)
  26         {
  27                 int index = block->size / block_size_increment;
  28                 block->next_free = heap->free.small_blocks[index];
  29                 heap->free.small_blocks[index] = block;
  30         }
  31         else
  32         {
  33                 block->next_free = heap->free.large_blocks;
  34                 heap->free.large_blocks = block;
  35         }
  36 }
  37
  38 /* Called after reading the code heap from the image file, and after code GC.
  39
  40 In the former case, we must add a large free block from compiling.base + size to
  41 compiling.limit. */
  42 void factorvm::build_free_list(heap *heap, cell size)
  43 {
  44         heap_block *prev = NULL;
  45
  46         clear_free_list(heap);
  47
  48         size = (size + block_size_increment - 1) & ~(block_size_increment - 1);
  49
  50         heap_block *scan = first_block(heap);
  51         free_heap_block *end = (free_heap_block *)(heap->seg->start + size);
  52
  53         /* Add all free blocks to the free list */
  54         while(scan && scan < (heap_block *)end)
  55         {
  56                 switch(scan->status)
  57                 {
  58                 case B_FREE:
  59                         add_to_free_list(heap,(free_heap_block *)scan);
  60                         break;
  61                 case B_ALLOCATED:
  62                         break;
  63                 default:
  64                         critical_error("Invalid scan->status",(cell)scan);
  65                         break;
  66                 }
  67
  68                 prev = scan;
  69                 scan = next_block(heap,scan);
  70         }
  71
  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)
  75         {
  76                 end->status = B_FREE;
  77                 end->size = heap->seg->end - (cell)end;
  78
  79                 /* add final free block */
  80                 add_to_free_list(heap,end);
  81         }
  82         /* This branch is taken if the newly loaded image fits exactly, or
  83         after code GC */
  84         else
  85         {
  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;
  90         }
  91
  92 }
  93
  94 void factorvm::assert_free_block(free_heap_block *block)
  95 {
  96         if(block->status != B_FREE)
  97                 critical_error("Invalid block in free list",(cell)block);
  98 }
  99
 100
 101 free_heap_block *factorvm::find_free_block(heap *heap, cell size)
 102 {
 103         cell attempt = size;
 104
 105         while(attempt < free_list_count * block_size_increment)
 106         {
 107                 int index = attempt / block_size_increment;
 108                 free_heap_block *block = heap->free.small_blocks[index];
 109                 if(block)
 110                 {
 111                         assert_free_block(block);
 112                         heap->free.small_blocks[index] = block->next_free;
 113                         return block;
 114                 }
 115
 116                 attempt *= 2;
 117         }
 118
 119         free_heap_block *prev = NULL;
 120         free_heap_block *block = heap->free.large_blocks;
 121
 122         while(block)
 123         {
 124                 assert_free_block(block);
 125                 if(block->size >= size)
 126                 {
 127                         if(prev)
 128                                 prev->next_free = block->next_free;
 129                         else
 130                                 heap->free.large_blocks = block->next_free;
 131                         return block;
 132                 }
 133
 134                 prev = block;
 135                 block = block->next_free;
 136         }
 137
 138         return NULL;
 139 }
 140
 141 free_heap_block *factorvm::split_free_block(heap *heap, free_heap_block *block, cell size)
 142 {
 143         if(block->size != size )
 144         {
 145                 /* split the block in two */
 146                 free_heap_block *split = (free_heap_block *)((cell)block + size);
 147                 split->status = B_FREE;
 148                 split->size = block->size - size;
 149                 split->next_free = block->next_free;
 150                 block->size = size;
 151                 add_to_free_list(heap,split);
 152         }
 153
 154         return block;
 155 }
 156
 157 /* Allocate a block of memory from the mark and sweep GC heap */
 158 heap_block *factorvm::heap_allot(heap *heap, cell size)
 159 {
 160         size = (size + block_size_increment - 1) & ~(block_size_increment - 1);
 161
 162         free_heap_block *block = find_free_block(heap,size);
 163         if(block)
 164         {
 165                 block = split_free_block(heap,block,size);
 166
 167                 block->status = B_ALLOCATED;
 168                 return block;
 169         }
 170         else
 171                 return NULL;
 172 }
 173
 174 /* Deallocates a block manually */
 175 void factorvm::heap_free(heap *heap, heap_block *block)
 176 {
 177         block->status = B_FREE;
 178         add_to_free_list(heap,(free_heap_block *)block);
 179 }
 180
 181 void factorvm::mark_block(heap_block *block)
 182 {
 183         /* If already marked, do nothing */
 184         switch(block->status)
 185         {
 186         case B_MARKED:
 187                 return;
 188         case B_ALLOCATED:
 189                 block->status = B_MARKED;
 190                 break;
 191         default:
 192                 critical_error("Marking the wrong block",(cell)block);
 193                 break;
 194         }
 195 }
 196
 197 /* If in the middle of code GC, we have to grow the heap, data GC restarts from
 198 scratch, so we have to unmark any marked blocks. */
 199 void factorvm::unmark_marked(heap *heap)
 200 {
 201         heap_block *scan = first_block(heap);
 202
 203         while(scan)
 204         {
 205                 if(scan->status == B_MARKED)
 206                         scan->status = B_ALLOCATED;
 207
 208                 scan = next_block(heap,scan);
 209         }
 210 }
 211
 212 /* After code GC, all referenced code blocks have status set to B_MARKED, so any
 213 which are allocated and not marked can be reclaimed. */
 214 void factorvm::free_unmarked(heap *heap, heap_iterator iter)
 215 {
 216         clear_free_list(heap);
 217
 218         heap_block *prev = NULL;
 219         heap_block *scan = first_block(heap);
 220
 221         while(scan)
 222         {
 223                 switch(scan->status)
 224                 {
 225                 case B_ALLOCATED:
 226                         if(secure_gc)
 227                                 memset(scan + 1,0,scan->size - sizeof(heap_block));
 228
 229                         if(prev && prev->status == B_FREE)
 230                                 prev->size += scan->size;
 231                         else
 232                         {
 233                                 scan->status = B_FREE;
 234                                 prev = scan;
 235                         }
 236                         break;
 237                 case B_FREE:
 238                         if(prev && prev->status == B_FREE)
 239                                 prev->size += scan->size;
 240                         else
 241                                 prev = scan;
 242                         break;
 243                 case B_MARKED:
 244                         if(prev && prev->status == B_FREE)
 245                                 add_to_free_list(heap,(free_heap_block *)prev);
 246                         scan->status = B_ALLOCATED;
 247                         prev = scan;
 248                         iter(scan,this);
 249                         break;
 250                 default:
 251                         critical_error("Invalid scan->status",(cell)scan);
 252                 }
 253
 254                 scan = next_block(heap,scan);
 255         }
 256
 257         if(prev && prev->status == B_FREE)
 258                 add_to_free_list(heap,(free_heap_block *)prev);
 259 }
 260
 261 /* Compute total sum of sizes of free blocks, and size of largest free block */
 262 void factorvm::heap_usage(heap *heap, cell *used, cell *total_free, cell *max_free)
 263 {
 264         *used = 0;
 265         *total_free = 0;
 266         *max_free = 0;
 267
 268         heap_block *scan = first_block(heap);
 269
 270         while(scan)
 271         {
 272                 switch(scan->status)
 273                 {
 274                 case B_ALLOCATED:
 275                         *used += scan->size;
 276                         break;
 277                 case B_FREE:
 278                         *total_free += scan->size;
 279                         if(scan->size > *max_free)
 280                                 *max_free = scan->size;
 281                         break;
 282                 default:
 283                         critical_error("Invalid scan->status",(cell)scan);
 284                 }
 285
 286                 scan = next_block(heap,scan);
 287         }
 288 }
 289
 290 /* The size of the heap, not including the last block if it's free */
 291 cell factorvm::heap_size(heap *heap)
 292 {
 293         heap_block *scan = first_block(heap);
 294
 295         while(next_block(heap,scan) != NULL)
 296                 scan = next_block(heap,scan);
 297
 298         /* this is the last block in the heap, and it is free */
 299         if(scan->status == B_FREE)
 300                 return (cell)scan - heap->seg->start;
 301         /* otherwise the last block is allocated */
 302         else
 303                 return heap->seg->size;
 304 }
 305
 306 /* Compute where each block is going to go, after compaction */
 307 cell factorvm::compute_heap_forwarding(heap *heap, unordered_map<heap_block *,char *> &forwarding)
 308 {
 309         heap_block *scan = first_block(heap);
 310         char *address = (char *)first_block(heap);
 311
 312         while(scan)
 313         {
 314                 if(scan->status == B_ALLOCATED)
 315                 {
 316                         forwarding[scan] = address;
 317                         address += scan->size;
 318                 }
 319                 else if(scan->status == B_MARKED)
 320                         critical_error("Why is the block marked?",0);
 321
 322                 scan = next_block(heap,scan);
 323         }
 324
 325         return (cell)address - heap->seg->start;
 326 }
 327
 328 void factorvm::compact_heap(heap *heap, unordered_map<heap_block *,char *> &forwarding)
 329 {
 330         heap_block *scan = first_block(heap);
 331
 332         while(scan)
 333         {
 334                 heap_block *next = next_block(heap,scan);
 335
 336                 if(scan->status == B_ALLOCATED)
 337                         memmove(forwarding[scan],scan,scan->size);
 338                 scan = next;
 339         }
 340 }
 341
 342 }