vm/data_gc.cpp

   1 #include "master.hpp"
   2
   3 namespace factor
   4 {
   5
   6 /* used during garbage collection only */
   7 zone *newspace;
   8 bool performing_gc;
   9 bool performing_compaction;
  10 cell collecting_gen;
  11
  12 /* if true, we are collecting aging space for the second time, so if it is still
  13 full, we go on to collect tenured */
  14 bool collecting_aging_again;
  15
  16 /* in case a generation fills up in the middle of a gc, we jump back
  17 up to try collecting the next generation. */
  18 jmp_buf gc_jmp;
  19
  20 gc_stats stats[max_gen_count];
  21 u64 cards_scanned;
  22 u64 decks_scanned;
  23 u64 card_scan_time;
  24 cell code_heap_scans;
  25
  26 /* What generation was being collected when copy_code_heap_roots() was last
  27 called? Until the next call to add_code_block(), future
  28 collections of younger generations don't have to touch the code
  29 heap. */
  30 cell last_code_heap_scan;
  31
  32 /* sometimes we grow the heap */
  33 bool growing_data_heap;
  34 data_heap *old_data_heap;
  35
  36 void init_data_gc()
  37 {
  38         performing_gc = false;
  39         last_code_heap_scan = data->nursery();
  40         collecting_aging_again = false;
  41 }
  42
  43 /* Given a pointer to oldspace, copy it to newspace */
  44 static object *copy_untagged_object_impl(object *pointer, cell size)
  45 {
  46         if(newspace->here + size >= newspace->end)
  47                 longjmp(gc_jmp,1);
  48         object *newpointer = allot_zone(newspace,size);
  49
  50         gc_stats *s = &stats[collecting_gen];
  51         s->object_count++;
  52         s->bytes_copied += size;
  53
  54         memcpy(newpointer,pointer,size);
  55         return newpointer;
  56 }
  57
  58 static object *copy_object_impl(object *untagged)
  59 {
  60         object *newpointer = copy_untagged_object_impl(untagged,untagged_object_size(untagged));
  61         untagged->h.forward_to(newpointer);
  62         return newpointer;
  63 }
  64
  65 static bool should_copy_p(object *untagged)
  66 {
  67         if(in_zone(newspace,untagged))
  68                 return false;
  69         if(collecting_gen == data->tenured())
  70                 return true;
  71         else if(data->have_aging_p() && collecting_gen == data->aging())
  72                 return !in_zone(&data->generations[data->tenured()],untagged);
  73         else if(collecting_gen == data->nursery())
  74                 return in_zone(&nursery,untagged);
  75         else
  76         {
  77                 critical_error("Bug in should_copy_p",(cell)untagged);
  78                 return false;
  79         }
  80 }
  81
  82 /* Follow a chain of forwarding pointers */
  83 static object *resolve_forwarding(object *untagged)
  84 {
  85         check_data_pointer(untagged);
  86
  87         /* is there another forwarding pointer? */
  88         if(untagged->h.forwarding_pointer_p())
  89                 return resolve_forwarding(untagged->h.forwarding_pointer());
  90         /* we've found the destination */
  91         else
  92         {
  93                 untagged->h.check_header();
  94                 if(should_copy_p(untagged))
  95                         return copy_object_impl(untagged);
  96                 else
  97                         return untagged;
  98         }
  99 }
 100
 101 template <typename T> static T *copy_untagged_object(T *untagged)
 102 {
 103         check_data_pointer(untagged);
 104
 105         if(untagged->h.forwarding_pointer_p())
 106                 untagged = (T *)resolve_forwarding(untagged->h.forwarding_pointer());
 107         else
 108         {
 109                 untagged->h.check_header();
 110                 untagged = (T *)copy_object_impl(untagged);
 111         }
 112
 113         return untagged;
 114 }
 115
 116 static cell copy_object(cell pointer)
 117 {
 118         return RETAG(copy_untagged_object(untag<object>(pointer)),TAG(pointer));
 119 }
 120
 121 void copy_handle(cell *handle)
 122 {
 123         cell pointer = *handle;
 124
 125         if(!immediate_p(pointer))
 126         {
 127                 object *obj = untag<object>(pointer);
 128                 check_data_pointer(obj);
 129                 if(should_copy_p(obj))
 130                         *handle = copy_object(pointer);
 131         }
 132 }
 133
 134 /* Scan all the objects in the card */
 135 static void copy_card(card *ptr, cell gen, cell here)
 136 {
 137         cell card_scan = card_to_addr(ptr) + card_offset(ptr);
 138         cell card_end = card_to_addr(ptr + 1);
 139
 140         if(here < card_end)
 141                 card_end = here;
 142
 143         copy_reachable_objects(card_scan,&card_end);
 144
 145         cards_scanned++;
 146 }
 147
 148 static void copy_card_deck(card_deck *deck, cell gen, card mask, card unmask)
 149 {
 150         card *first_card = deck_to_card(deck);
 151         card *last_card = deck_to_card(deck + 1);
 152
 153         cell here = data->generations[gen].here;
 154
 155         u32 *quad_ptr;
 156         u32 quad_mask = mask | (mask << 8) | (mask << 16) | (mask << 24);
 157
 158         for(quad_ptr = (u32 *)first_card; quad_ptr < (u32 *)last_card; quad_ptr++)
 159         {
 160                 if(*quad_ptr & quad_mask)
 161                 {
 162                         card *ptr = (card *)quad_ptr;
 163
 164                         int card;
 165                         for(card = 0; card < 4; card++)
 166                         {
 167                                 if(ptr[card] & mask)
 168                                 {
 169                                         copy_card(&ptr[card],gen,here);
 170                                         ptr[card] &= ~unmask;
 171                                 }
 172                         }
 173                 }
 174         }
 175
 176         decks_scanned++;
 177 }
 178
 179 /* Copy all newspace objects referenced from marked cards to the destination */
 180 static void copy_gen_cards(cell gen)
 181 {
 182         card_deck *first_deck = addr_to_deck(data->generations[gen].start);
 183         card_deck *last_deck = addr_to_deck(data->generations[gen].end);
 184
 185         card mask, unmask;
 186
 187         /* if we are collecting the nursery, we care about old->nursery pointers
 188         but not old->aging pointers */
 189         if(collecting_gen == data->nursery())
 190         {
 191                 mask = card_points_to_nursery;
 192
 193                 /* after the collection, no old->nursery pointers remain
 194                 anywhere, but old->aging pointers might remain in tenured
 195                 space */
 196                 if(gen == data->tenured())
 197                         unmask = card_points_to_nursery;
 198                 /* after the collection, all cards in aging space can be
 199                 cleared */
 200                 else if(data->have_aging_p() && gen == data->aging())
 201                         unmask = card_mark_mask;
 202                 else
 203                 {
 204                         critical_error("bug in copy_gen_cards",gen);
 205                         return;
 206                 }
 207         }
 208         /* if we are collecting aging space into tenured space, we care about
 209         all old->nursery and old->aging pointers. no old->aging pointers can
 210         remain */
 211         else if(data->have_aging_p() && collecting_gen == data->aging())
 212         {
 213                 if(collecting_aging_again)
 214                 {
 215                         mask = card_points_to_aging;
 216                         unmask = card_mark_mask;
 217                 }
 218                 /* after we collect aging space into the aging semispace, no
 219                 old->nursery pointers remain but tenured space might still have
 220                 pointers to aging space. */
 221                 else
 222                 {
 223                         mask = card_points_to_aging;
 224                         unmask = card_points_to_nursery;
 225                 }
 226         }
 227         else
 228         {
 229                 critical_error("bug in copy_gen_cards",gen);
 230                 return;
 231         }
 232
 233         card_deck *ptr;
 234
 235         for(ptr = first_deck; ptr < last_deck; ptr++)
 236         {
 237                 if(*ptr & mask)
 238                 {
 239                         copy_card_deck(ptr,gen,mask,unmask);
 240                         *ptr &= ~unmask;
 241                 }
 242         }
 243 }
 244
 245 /* Scan cards in all generations older than the one being collected, copying
 246 old->new references */
 247 static void copy_cards()
 248 {
 249         u64 start = current_micros();
 250
 251         cell i;
 252         for(i = collecting_gen + 1; i < data->gen_count; i++)
 253                 copy_gen_cards(i);
 254
 255         card_scan_time += (current_micros() - start);
 256 }
 257
 258 /* Copy all tagged pointers in a range of memory */
 259 static void copy_stack_elements(segment *region, cell top)
 260 {
 261         cell ptr = region->start;
 262
 263         for(; ptr <= top; ptr += sizeof(cell))
 264                 copy_handle((cell*)ptr);
 265 }
 266
 267 static void copy_registered_locals()
 268 {
 269         std::vector<cell>::const_iterator iter = gc_locals.begin();
 270         std::vector<cell>::const_iterator end = gc_locals.end();
 271
 272         for(; iter < end; iter++)
 273                 copy_handle((cell *)(*iter));
 274 }
 275
 276 static void copy_registered_bignums()
 277 {
 278         std::vector<cell>::const_iterator iter = gc_bignums.begin();
 279         std::vector<cell>::const_iterator end = gc_bignums.end();
 280
 281         for(; iter < end; iter++)
 282         {
 283                 bignum **handle = (bignum **)(*iter);
 284                 bignum *pointer = *handle;
 285
 286                 if(pointer)
 287                 {
 288                         check_data_pointer(pointer);
 289                         if(should_copy_p(pointer))
 290                                 *handle = copy_untagged_object(pointer);
 291 #ifdef FACTOR_DEBUG
 292                         assert((*handle)->h.hi_tag() == BIGNUM_TYPE);
 293 #endif
 294                 }
 295         }
 296 }
 297
 298 /* Copy roots over at the start of GC, namely various constants, stacks,
 299 the user environment and extra roots registered by local_roots.hpp */
 300 static void copy_roots()
 301 {
 302         copy_handle(&T);
 303         copy_handle(&bignum_zero);
 304         copy_handle(&bignum_pos_one);
 305         copy_handle(&bignum_neg_one);
 306
 307         copy_registered_locals();
 308         copy_registered_bignums();
 309
 310         if(!performing_compaction)
 311         {
 312                 save_stacks();
 313                 context *stacks = stack_chain;
 314
 315                 while(stacks)
 316                 {
 317                         copy_stack_elements(stacks->datastack_region,stacks->datastack);
 318                         copy_stack_elements(stacks->retainstack_region,stacks->retainstack);
 319
 320                         copy_handle(&stacks->catchstack_save);
 321                         copy_handle(&stacks->current_callback_save);
 322
 323                         mark_active_blocks(stacks);
 324
 325                         stacks = stacks->next;
 326                 }
 327         }
 328
 329         int i;
 330         for(i = 0; i < USER_ENV; i++)
 331                 copy_handle(&userenv[i]);
 332 }
 333
 334 static cell copy_next_from_nursery(cell scan)
 335 {
 336         cell *obj = (cell *)scan;
 337         cell *end = (cell *)(scan + binary_payload_start((object *)scan));
 338
 339         if(obj != end)
 340         {
 341                 obj++;
 342
 343                 cell nursery_start = nursery.start;
 344                 cell nursery_end = nursery.end;
 345
 346                 for(; obj < end; obj++)
 347                 {
 348                         cell pointer = *obj;
 349
 350                         if(!immediate_p(pointer))
 351                         {
 352                                 check_data_pointer((object *)pointer);
 353                                 if(pointer >= nursery_start && pointer < nursery_end)
 354                                         *obj = copy_object(pointer);
 355                         }
 356                 }
 357         }
 358
 359         return scan + untagged_object_size((object *)scan);
 360 }
 361
 362 static cell copy_next_from_aging(cell scan)
 363 {
 364         cell *obj = (cell *)scan;
 365         cell *end = (cell *)(scan + binary_payload_start((object *)scan));
 366
 367         if(obj != end)
 368         {
 369                 obj++;
 370
 371                 cell tenured_start = data->generations[data->tenured()].start;
 372                 cell tenured_end = data->generations[data->tenured()].end;
 373
 374                 cell newspace_start = newspace->start;
 375                 cell newspace_end = newspace->end;
 376
 377                 for(; obj < end; obj++)
 378                 {
 379                         cell pointer = *obj;
 380
 381                         if(!immediate_p(pointer))
 382                         {
 383                                 check_data_pointer((object *)pointer);
 384                                 if(!(pointer >= newspace_start && pointer < newspace_end)
 385                                    && !(pointer >= tenured_start && pointer < tenured_end))
 386                                         *obj = copy_object(pointer);
 387                         }
 388                 }
 389         }
 390
 391         return scan + untagged_object_size((object *)scan);
 392 }
 393
 394 static cell copy_next_from_tenured(cell scan)
 395 {
 396         cell *obj = (cell *)scan;
 397         cell *end = (cell *)(scan + binary_payload_start((object *)scan));
 398
 399         if(obj != end)
 400         {
 401                 obj++;
 402
 403                 cell newspace_start = newspace->start;
 404                 cell newspace_end = newspace->end;
 405
 406                 for(; obj < end; obj++)
 407                 {
 408                         cell pointer = *obj;
 409
 410                         if(!immediate_p(pointer))
 411                         {
 412                                 check_data_pointer((object *)pointer);
 413                                 if(!(pointer >= newspace_start && pointer < newspace_end))
 414                                         *obj = copy_object(pointer);
 415                         }
 416                 }
 417         }
 418
 419         mark_object_code_block((object *)scan);
 420
 421         return scan + untagged_object_size((object *)scan);
 422 }
 423
 424 void copy_reachable_objects(cell scan, cell *end)
 425 {
 426         if(collecting_gen == data->nursery())
 427         {
 428                 while(scan < *end)
 429                         scan = copy_next_from_nursery(scan);
 430         }
 431         else if(data->have_aging_p() && collecting_gen == data->aging())
 432         {
 433                 while(scan < *end)
 434                         scan = copy_next_from_aging(scan);
 435         }
 436         else if(collecting_gen == data->tenured())
 437         {
 438                 while(scan < *end)
 439                         scan = copy_next_from_tenured(scan);
 440         }
 441 }
 442
 443 /* Prepare to start copying reachable objects into an unused zone */
 444 static void begin_gc(cell requested_bytes)
 445 {
 446         if(growing_data_heap)
 447         {
 448                 if(collecting_gen != data->tenured())
 449                         critical_error("Invalid parameters to begin_gc",0);
 450
 451                 old_data_heap = data;
 452                 set_data_heap(grow_data_heap(old_data_heap,requested_bytes));
 453                 newspace = &data->generations[data->tenured()];
 454         }
 455         else if(collecting_accumulation_gen_p())
 456         {
 457                 /* when collecting one of these generations, rotate it
 458                 with the semispace */
 459                 zone z = data->generations[collecting_gen];
 460                 data->generations[collecting_gen] = data->semispaces[collecting_gen];
 461                 data->semispaces[collecting_gen] = z;
 462                 reset_generation(collecting_gen);
 463                 newspace = &data->generations[collecting_gen];
 464                 clear_cards(collecting_gen,collecting_gen);
 465                 clear_decks(collecting_gen,collecting_gen);
 466                 clear_allot_markers(collecting_gen,collecting_gen);
 467         }
 468         else
 469         {
 470                 /* when collecting a younger generation, we copy
 471                 reachable objects to the next oldest generation,
 472                 so we set the newspace so the next generation. */
 473                 newspace = &data->generations[collecting_gen + 1];
 474         }
 475 }
 476
 477 static void end_gc(cell gc_elapsed)
 478 {
 479         gc_stats *s = &stats[collecting_gen];
 480
 481         s->collections++;
 482         s->gc_time += gc_elapsed;
 483         if(s->max_gc_time < gc_elapsed)
 484                 s->max_gc_time = gc_elapsed;
 485
 486         if(growing_data_heap)
 487         {
 488                 dealloc_data_heap(old_data_heap);
 489                 old_data_heap = NULL;
 490                 growing_data_heap = false;
 491         }
 492
 493         if(collecting_accumulation_gen_p())
 494         {
 495                 /* all younger generations except are now empty.
 496                 if collecting_gen == data->nursery() here, we only have 1 generation;
 497                 old-school Cheney collector */
 498                 if(collecting_gen != data->nursery())
 499                         reset_generations(data->nursery(),collecting_gen - 1);
 500         }
 501         else if(collecting_gen == data->nursery())
 502         {
 503                 nursery.here = nursery.start;
 504         }
 505         else
 506         {
 507                 /* all generations up to and including the one
 508                 collected are now empty */
 509                 reset_generations(data->nursery(),collecting_gen);
 510         }
 511
 512         collecting_aging_again = false;
 513 }
 514
 515 /* Collect gen and all younger generations.
 516 If growing_data_heap_ is true, we must grow the data heap to such a size that
 517 an allocation of requested_bytes won't fail */
 518 void garbage_collection(cell gen,
 519         bool growing_data_heap_,
 520         cell requested_bytes)
 521 {
 522         if(gc_off)
 523         {
 524                 critical_error("GC disabled",gen);
 525                 return;
 526         }
 527
 528         u64 start = current_micros();
 529
 530         performing_gc = true;
 531         growing_data_heap = growing_data_heap_;
 532         collecting_gen = gen;
 533
 534         /* we come back here if a generation is full */
 535         if(setjmp(gc_jmp))
 536         {
 537                 /* We have no older generations we can try collecting, so we
 538                 resort to growing the data heap */
 539                 if(collecting_gen == data->tenured())
 540                 {
 541                         growing_data_heap = true;
 542
 543                         /* see the comment in unmark_marked() */
 544                         unmark_marked(&code);
 545                 }
 546                 /* we try collecting aging space twice before going on to
 547                 collect tenured */
 548                 else if(data->have_aging_p()
 549                         && collecting_gen == data->aging()
 550                         && !collecting_aging_again)
 551                 {
 552                         collecting_aging_again = true;
 553                 }
 554                 /* Collect the next oldest generation */
 555                 else
 556                 {
 557                         collecting_gen++;
 558                 }
 559         }
 560
 561         begin_gc(requested_bytes);
 562
 563         /* initialize chase pointer */
 564         cell scan = newspace->here;
 565
 566         /* collect objects referenced from stacks and environment */
 567         copy_roots();
 568         /* collect objects referenced from older generations */
 569         copy_cards();
 570
 571         /* do some tracing */
 572         copy_reachable_objects(scan,&newspace->here);
 573
 574         /* don't scan code heap unless it has pointers to this
 575         generation or younger */
 576         if(collecting_gen >= last_code_heap_scan)
 577         {
 578                 code_heap_scans++;
 579
 580                 if(collecting_gen == data->tenured())
 581                         free_unmarked(&code,(heap_iterator)update_literal_and_word_references);
 582                 else
 583                         copy_code_heap_roots();
 584
 585                 if(collecting_accumulation_gen_p())
 586                         last_code_heap_scan = collecting_gen;
 587                 else
 588                         last_code_heap_scan = collecting_gen + 1;
 589         }
 590
 591         cell gc_elapsed = (current_micros() - start);
 592
 593         end_gc(gc_elapsed);
 594
 595         performing_gc = false;
 596 }
 597
 598 void gc()
 599 {
 600         garbage_collection(data->tenured(),false,0);
 601 }
 602
 603 PRIMITIVE(gc)
 604 {
 605         gc();
 606 }
 607
 608 PRIMITIVE(gc_stats)
 609 {
 610         growable_array result;
 611
 612         cell i;
 613         u64 total_gc_time = 0;
 614
 615         for(i = 0; i < max_gen_count; i++)
 616         {
 617                 gc_stats *s = &stats[i];
 618                 result.add(allot_cell(s->collections));
 619                 result.add(tag<bignum>(long_long_to_bignum(s->gc_time)));
 620                 result.add(tag<bignum>(long_long_to_bignum(s->max_gc_time)));
 621                 result.add(allot_cell(s->collections == 0 ? 0 : s->gc_time / s->collections));
 622                 result.add(allot_cell(s->object_count));
 623                 result.add(tag<bignum>(long_long_to_bignum(s->bytes_copied)));
 624
 625                 total_gc_time += s->gc_time;
 626         }
 627
 628         result.add(tag<bignum>(ulong_long_to_bignum(total_gc_time)));
 629         result.add(tag<bignum>(ulong_long_to_bignum(cards_scanned)));
 630         result.add(tag<bignum>(ulong_long_to_bignum(decks_scanned)));
 631         result.add(tag<bignum>(ulong_long_to_bignum(card_scan_time)));
 632         result.add(allot_cell(code_heap_scans));
 633
 634         result.trim();
 635         dpush(result.elements.value());
 636 }
 637
 638 void clear_gc_stats()
 639 {
 640         for(cell i = 0; i < max_gen_count; i++)
 641                 memset(&stats[i],0,sizeof(gc_stats));
 642
 643         cards_scanned = 0;
 644         decks_scanned = 0;
 645         card_scan_time = 0;
 646         code_heap_scans = 0;
 647 }
 648
 649 PRIMITIVE(clear_gc_stats)
 650 {
 651         clear_gc_stats();
 652 }
 653
 654 /* classes.tuple uses this to reshape tuples; tools.deploy.shaker uses this
 655    to coalesce equal but distinct quotations and wrappers. */
 656 PRIMITIVE(become)
 657 {
 658         array *new_objects = untag_check<array>(dpop());
 659         array *old_objects = untag_check<array>(dpop());
 660
 661         cell capacity = array_capacity(new_objects);
 662         if(capacity != array_capacity(old_objects))
 663                 critical_error("bad parameters to become",0);
 664
 665         cell i;
 666
 667         for(i = 0; i < capacity; i++)
 668         {
 669                 tagged<object> old_obj(array_nth(old_objects,i));
 670                 tagged<object> new_obj(array_nth(new_objects,i));
 671
 672                 if(old_obj != new_obj)
 673                         old_obj->h.forward_to(new_obj.untagged());
 674         }
 675
 676         gc();
 677
 678         /* If a word's definition quotation was in old_objects and the
 679            quotation in new_objects is not compiled, we might leak memory
 680            by referencing the old quotation unless we recompile all
 681            unoptimized words. */
 682         compile_all_words();
 683 }
 684
 685 VM_ASM_API void inline_gc(cell *gc_roots_base, cell gc_roots_size)
 686 {
 687         for(cell i = 0; i < gc_roots_size; i++)
 688                 gc_locals.push_back((cell)&gc_roots_base[i]);
 689
 690         garbage_collection(data->nursery(),false,0);
 691
 692         for(cell i = 0; i < gc_roots_size; i++)
 693                 gc_locals.pop_back();
 694 }
 695
 696 }