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