vm/data_gc.cpp

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