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         cell scan = gc_locals_region->start;
 270
 271         for(; scan <= gc_locals; scan += sizeof(cell))
 272                 copy_handle(*(cell **)scan);
 273 }
 274
 275 static void copy_registered_bignums()
 276 {
 277         cell scan = gc_bignums_region->start;
 278
 279         for(; scan <= gc_bignums; scan += sizeof(cell))
 280         {
 281                 bignum **handle = *(bignum ***)scan;
 282                 bignum *pointer = *handle;
 283
 284                 if(pointer)
 285                 {
 286                         check_data_pointer(pointer);
 287                         if(should_copy_p(pointer))
 288                                 *handle = copy_untagged_object(pointer);
 289 #ifdef FACTOR_DEBUG
 290                         assert((*handle)->h.hi_tag() == BIGNUM_TYPE);
 291 #endif
 292                 }
 293         }
 294 }
 295
 296 /* Copy roots over at the start of GC, namely various constants, stacks,
 297 the user environment and extra roots registered by local_roots.hpp */
 298 static void copy_roots()
 299 {
 300         copy_handle(&T);
 301         copy_handle(&bignum_zero);
 302         copy_handle(&bignum_pos_one);
 303         copy_handle(&bignum_neg_one);
 304
 305         copy_registered_locals();
 306         copy_registered_bignums();
 307
 308         if(!performing_compaction)
 309         {
 310                 save_stacks();
 311                 context *stacks = stack_chain;
 312
 313                 while(stacks)
 314                 {
 315                         copy_stack_elements(stacks->datastack_region,stacks->datastack);
 316                         copy_stack_elements(stacks->retainstack_region,stacks->retainstack);
 317
 318                         copy_handle(&stacks->catchstack_save);
 319                         copy_handle(&stacks->current_callback_save);
 320
 321                         mark_active_blocks(stacks);
 322
 323                         stacks = stacks->next;
 324                 }
 325         }
 326
 327         int i;
 328         for(i = 0; i < USER_ENV; i++)
 329                 copy_handle(&userenv[i]);
 330 }
 331
 332 static cell copy_next_from_nursery(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 nursery_start = nursery.start;
 342                 cell nursery_end = nursery.end;
 343
 344                 for(; obj < end; obj++)
 345                 {
 346                         cell pointer = *obj;
 347
 348                         if(!immediate_p(pointer))
 349                         {
 350                                 check_data_pointer((object *)pointer);
 351                                 if(pointer >= nursery_start && pointer < nursery_end)
 352                                         *obj = copy_object(pointer);
 353                         }
 354                 }
 355         }
 356
 357         return scan + untagged_object_size((object *)scan);
 358 }
 359
 360 static cell copy_next_from_aging(cell scan)
 361 {
 362         cell *obj = (cell *)scan;
 363         cell *end = (cell *)(scan + binary_payload_start((object *)scan));
 364
 365         if(obj != end)
 366         {
 367                 obj++;
 368
 369                 cell tenured_start = data->generations[data->tenured()].start;
 370                 cell tenured_end = data->generations[data->tenured()].end;
 371
 372                 cell newspace_start = newspace->start;
 373                 cell newspace_end = newspace->end;
 374
 375                 for(; obj < end; obj++)
 376                 {
 377                         cell pointer = *obj;
 378
 379                         if(!immediate_p(pointer))
 380                         {
 381                                 check_data_pointer((object *)pointer);
 382                                 if(!(pointer >= newspace_start && pointer < newspace_end)
 383                                    && !(pointer >= tenured_start && pointer < tenured_end))
 384                                         *obj = copy_object(pointer);
 385                         }
 386                 }
 387         }
 388
 389         return scan + untagged_object_size((object *)scan);
 390 }
 391
 392 static cell copy_next_from_tenured(cell scan)
 393 {
 394         cell *obj = (cell *)scan;
 395         cell *end = (cell *)(scan + binary_payload_start((object *)scan));
 396
 397         if(obj != end)
 398         {
 399                 obj++;
 400
 401                 cell newspace_start = newspace->start;
 402                 cell newspace_end = newspace->end;
 403
 404                 for(; obj < end; obj++)
 405                 {
 406                         cell pointer = *obj;
 407
 408                         if(!immediate_p(pointer))
 409                         {
 410                                 check_data_pointer((object *)pointer);
 411                                 if(!(pointer >= newspace_start && pointer < newspace_end))
 412                                         *obj = copy_object(pointer);
 413                         }
 414                 }
 415         }
 416
 417         mark_object_code_block((object *)scan);
 418
 419         return scan + untagged_object_size((object *)scan);
 420 }
 421
 422 void copy_reachable_objects(cell scan, cell *end)
 423 {
 424         if(collecting_gen == data->nursery())
 425         {
 426                 while(scan < *end)
 427                         scan = copy_next_from_nursery(scan);
 428         }
 429         else if(data->have_aging_p() && collecting_gen == data->aging())
 430         {
 431                 while(scan < *end)
 432                         scan = copy_next_from_aging(scan);
 433         }
 434         else if(collecting_gen == data->tenured())
 435         {
 436                 while(scan < *end)
 437                         scan = copy_next_from_tenured(scan);
 438         }
 439 }
 440
 441 /* Prepare to start copying reachable objects into an unused zone */
 442 static void begin_gc(cell requested_bytes)
 443 {
 444         if(growing_data_heap)
 445         {
 446                 if(collecting_gen != data->tenured())
 447                         critical_error("Invalid parameters to begin_gc",0);
 448
 449                 old_data_heap = data;
 450                 set_data_heap(grow_data_heap(old_data_heap,requested_bytes));
 451                 newspace = &data->generations[data->tenured()];
 452         }
 453         else if(collecting_accumulation_gen_p())
 454         {
 455                 /* when collecting one of these generations, rotate it
 456                 with the semispace */
 457                 zone z = data->generations[collecting_gen];
 458                 data->generations[collecting_gen] = data->semispaces[collecting_gen];
 459                 data->semispaces[collecting_gen] = z;
 460                 reset_generation(collecting_gen);
 461                 newspace = &data->generations[collecting_gen];
 462                 clear_cards(collecting_gen,collecting_gen);
 463                 clear_decks(collecting_gen,collecting_gen);
 464                 clear_allot_markers(collecting_gen,collecting_gen);
 465         }
 466         else
 467         {
 468                 /* when collecting a younger generation, we copy
 469                 reachable objects to the next oldest generation,
 470                 so we set the newspace so the next generation. */
 471                 newspace = &data->generations[collecting_gen + 1];
 472         }
 473 }
 474
 475 static void end_gc(cell gc_elapsed)
 476 {
 477         gc_stats *s = &stats[collecting_gen];
 478
 479         s->collections++;
 480         s->gc_time += gc_elapsed;
 481         if(s->max_gc_time < gc_elapsed)
 482                 s->max_gc_time = gc_elapsed;
 483
 484         if(growing_data_heap)
 485         {
 486                 dealloc_data_heap(old_data_heap);
 487                 old_data_heap = NULL;
 488                 growing_data_heap = false;
 489         }
 490
 491         if(collecting_accumulation_gen_p())
 492         {
 493                 /* all younger generations except are now empty.
 494                 if collecting_gen == data->nursery() here, we only have 1 generation;
 495                 old-school Cheney collector */
 496                 if(collecting_gen != data->nursery())
 497                         reset_generations(data->nursery(),collecting_gen - 1);
 498         }
 499         else if(collecting_gen == data->nursery())
 500         {
 501                 nursery.here = nursery.start;
 502         }
 503         else
 504         {
 505                 /* all generations up to and including the one
 506                 collected are now empty */
 507                 reset_generations(data->nursery(),collecting_gen);
 508         }
 509
 510         collecting_aging_again = false;
 511 }
 512
 513 /* Collect gen and all younger generations.
 514 If growing_data_heap_ is true, we must grow the data heap to such a size that
 515 an allocation of requested_bytes won't fail */
 516 void garbage_collection(cell gen,
 517         bool growing_data_heap_,
 518         cell requested_bytes)
 519 {
 520         if(gc_off)
 521         {
 522                 critical_error("GC disabled",gen);
 523                 return;
 524         }
 525
 526         u64 start = current_micros();
 527
 528         performing_gc = true;
 529         growing_data_heap = growing_data_heap_;
 530         collecting_gen = gen;
 531
 532         /* we come back here if a generation is full */
 533         if(setjmp(gc_jmp))
 534         {
 535                 /* We have no older generations we can try collecting, so we
 536                 resort to growing the data heap */
 537                 if(collecting_gen == data->tenured())
 538                 {
 539                         growing_data_heap = true;
 540
 541                         /* see the comment in unmark_marked() */
 542                         unmark_marked(&code);
 543                 }
 544                 /* we try collecting aging space twice before going on to
 545                 collect tenured */
 546                 else if(data->have_aging_p()
 547                         && collecting_gen == data->aging()
 548                         && !collecting_aging_again)
 549                 {
 550                         collecting_aging_again = true;
 551                 }
 552                 /* Collect the next oldest generation */
 553                 else
 554                 {
 555                         collecting_gen++;
 556                 }
 557         }
 558
 559         begin_gc(requested_bytes);
 560
 561         /* initialize chase pointer */
 562         cell scan = newspace->here;
 563
 564         /* collect objects referenced from stacks and environment */
 565         copy_roots();
 566         /* collect objects referenced from older generations */
 567         copy_cards();
 568
 569         /* do some tracing */
 570         copy_reachable_objects(scan,&newspace->here);
 571
 572         /* don't scan code heap unless it has pointers to this
 573         generation or younger */
 574         if(collecting_gen >= last_code_heap_scan)
 575         {
 576                 code_heap_scans++;
 577
 578                 if(collecting_gen == data->tenured())
 579                         free_unmarked(&code,(heap_iterator)update_literal_and_word_references);
 580                 else
 581                         copy_code_heap_roots();
 582
 583                 if(collecting_accumulation_gen_p())
 584                         last_code_heap_scan = collecting_gen;
 585                 else
 586                         last_code_heap_scan = collecting_gen + 1;
 587         }
 588
 589         cell gc_elapsed = (current_micros() - start);
 590
 591         end_gc(gc_elapsed);
 592
 593         performing_gc = false;
 594 }
 595
 596 void gc()
 597 {
 598         garbage_collection(data->tenured(),false,0);
 599 }
 600
 601 PRIMITIVE(gc)
 602 {
 603         gc();
 604 }
 605
 606 PRIMITIVE(gc_stats)
 607 {
 608         growable_array result;
 609
 610         cell i;
 611         u64 total_gc_time = 0;
 612
 613         for(i = 0; i < max_gen_count; i++)
 614         {
 615                 gc_stats *s = &stats[i];
 616                 result.add(allot_cell(s->collections));
 617                 result.add(tag<bignum>(long_long_to_bignum(s->gc_time)));
 618                 result.add(tag<bignum>(long_long_to_bignum(s->max_gc_time)));
 619                 result.add(allot_cell(s->collections == 0 ? 0 : s->gc_time / s->collections));
 620                 result.add(allot_cell(s->object_count));
 621                 result.add(tag<bignum>(long_long_to_bignum(s->bytes_copied)));
 622
 623                 total_gc_time += s->gc_time;
 624         }
 625
 626         result.add(tag<bignum>(ulong_long_to_bignum(total_gc_time)));
 627         result.add(tag<bignum>(ulong_long_to_bignum(cards_scanned)));
 628         result.add(tag<bignum>(ulong_long_to_bignum(decks_scanned)));
 629         result.add(tag<bignum>(ulong_long_to_bignum(card_scan_time)));
 630         result.add(allot_cell(code_heap_scans));
 631
 632         result.trim();
 633         dpush(result.elements.value());
 634 }
 635
 636 void clear_gc_stats()
 637 {
 638         for(cell i = 0; i < max_gen_count; i++)
 639                 memset(&stats[i],0,sizeof(gc_stats));
 640
 641         cards_scanned = 0;
 642         decks_scanned = 0;
 643         card_scan_time = 0;
 644         code_heap_scans = 0;
 645 }
 646
 647 PRIMITIVE(clear_gc_stats)
 648 {
 649         clear_gc_stats();
 650 }
 651
 652 /* classes.tuple uses this to reshape tuples; tools.deploy.shaker uses this
 653    to coalesce equal but distinct quotations and wrappers. */
 654 PRIMITIVE(become)
 655 {
 656         array *new_objects = untag_check<array>(dpop());
 657         array *old_objects = untag_check<array>(dpop());
 658
 659         cell capacity = array_capacity(new_objects);
 660         if(capacity != array_capacity(old_objects))
 661                 critical_error("bad parameters to become",0);
 662
 663         cell i;
 664
 665         for(i = 0; i < capacity; i++)
 666         {
 667                 tagged<object> old_obj(array_nth(old_objects,i));
 668                 tagged<object> new_obj(array_nth(new_objects,i));
 669
 670                 if(old_obj != new_obj)
 671                         old_obj->h.forward_to(new_obj.untagged());
 672         }
 673
 674         gc();
 675
 676         /* If a word's definition quotation was in old_objects and the
 677            quotation in new_objects is not compiled, we might leak memory
 678            by referencing the old quotation unless we recompile all
 679            unoptimized words. */
 680         compile_all_words();
 681 }
 682
 683 VM_ASM_API void inline_gc(cell *gc_roots_base, cell gc_roots_size)
 684 {
 685         for(cell i = 0; i < gc_roots_size; i++)
 686                 gc_local_push((cell)&gc_roots_base[i]);
 687
 688         garbage_collection(data->nursery(),false,0);
 689
 690         for(cell i = 0; i < gc_roots_size; i++)
 691                 gc_local_pop();
 692 }
 693
 694 }