vm/data_gc.cpp

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