vm/data_gc.c

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