vm/slot_visitor.hpp

   1 namespace factor {
   2
   3 // Size sans alignment.
   4 template <typename Fixup>
   5 cell object::base_size(Fixup fixup) const {
   6   switch (type()) {
   7     case ARRAY_TYPE:
   8       return array_size((array*)this);
   9     case BIGNUM_TYPE:
  10       return array_size((bignum*)this);
  11     case BYTE_ARRAY_TYPE:
  12       return array_size((byte_array*)this);
  13     case STRING_TYPE:
  14       return string_size(string_capacity((string*)this));
  15     case TUPLE_TYPE: {
  16       tuple_layout* layout = (tuple_layout*)fixup.translate_data(
  17           untag<object>(((tuple*)this)->layout));
  18       return tuple_size(layout);
  19     }
  20     case QUOTATION_TYPE:
  21       return sizeof(quotation);
  22     case WORD_TYPE:
  23       return sizeof(word);
  24     case FLOAT_TYPE:
  25       return sizeof(boxed_float);
  26     case DLL_TYPE:
  27       return sizeof(dll);
  28     case ALIEN_TYPE:
  29       return sizeof(alien);
  30     case WRAPPER_TYPE:
  31       return sizeof(wrapper);
  32     case CALLSTACK_TYPE: {
  33       cell callstack_length = untag_fixnum(((callstack*)this)->length);
  34       return callstack_object_size(callstack_length);
  35     }
  36     default:
  37       critical_error("Invalid header in base_size", (cell)this);
  38       return 0;
  39   }
  40 }
  41
  42 // Size of the object pointed to by an untagged pointer
  43 template <typename Fixup>
  44 cell object::size(Fixup fixup) const {
  45   if (free_p())
  46     return ((free_heap_block*)this)->size();
  47   return align(base_size(fixup), data_alignment);
  48 }
  49
  50 inline cell object::size() const { return size(no_fixup()); }
  51
  52 // The number of slots (cells) in an object which should be scanned by
  53 // the GC. The number can vary in arrays and tuples, in all other
  54 // types the number is a constant.
  55 template <typename Fixup>
  56 inline cell object::slot_count(Fixup fixup) const {
  57   if (free_p())
  58     return 0;
  59
  60   cell t = type();
  61   if (t == ARRAY_TYPE) {
  62     // capacity + n slots
  63     return 1 + array_capacity((array*)this);
  64   } else if (t == TUPLE_TYPE) {
  65     tuple_layout* layout = (tuple_layout*)fixup.translate_data(
  66         untag<object>(((tuple*)this)->layout));
  67     // layout + n slots
  68     return 1 + tuple_capacity(layout);
  69   } else {
  70     switch (t) {
  71       // these objects do not refer to other objects at all
  72       case FLOAT_TYPE:
  73       case BYTE_ARRAY_TYPE:
  74       case BIGNUM_TYPE:
  75       case CALLSTACK_TYPE: return 0;
  76       case WORD_TYPE: return 8;
  77       case ALIEN_TYPE: return 2;
  78       case DLL_TYPE: return 1;
  79       case QUOTATION_TYPE: return 3;
  80       case STRING_TYPE: return 3;
  81       case WRAPPER_TYPE: return 1;
  82       default:
  83         critical_error("Invalid header in slot_count", (cell)this);
  84         return 0; // can't happen
  85     }
  86   }
  87 }
  88
  89 inline cell object::slot_count() const {
  90   return slot_count(no_fixup());
  91 }
  92
  93 // Slot visitors iterate over the slots of an object, applying a functor to
  94 // each one that is a non-immediate slot. The pointer is untagged first.
  95 // The functor returns a new untagged object pointer. The return value may
  96 // or may not equal the old one, however the new pointer receives the same
  97 // tag before being stored back to the original location.
  98
  99 // Slots storing immediate values are left unchanged and the visitor does
 100 // inspect them.
 101
 102 // This is used by GC's copying, sweep and compact phases, and the
 103 // implementation of the become primitive.
 104
 105 // Iteration is driven by visit_*() methods. Only one of them define GC
 106 // roots:
 107 //  - visit_all_roots()
 108
 109 // Code block visitors iterate over sets of code blocks, applying a functor
 110 // to each one. The functor returns a new code_block pointer, which may or
 111 // may not equal the old one. This is stored back to the original location.
 112
 113 // This is used by GC's sweep and compact phases, and the implementation of
 114 // the modify-code-heap primitive.
 115
 116 // Iteration is driven by visit_*() methods. Some of them define GC roots:
 117 //  - visit_context_code_blocks()
 118 //  - visit_callback_code_blocks()
 119
 120 template <typename Fixup> struct slot_visitor {
 121   factor_vm* parent;
 122   Fixup fixup;
 123   cell cards_scanned;
 124   cell decks_scanned;
 125
 126   slot_visitor<Fixup>(factor_vm* parent, Fixup fixup)
 127   : parent(parent),
 128     fixup(fixup),
 129     cards_scanned(0),
 130     decks_scanned(0) {}
 131
 132   cell visit_pointer(cell pointer);
 133   void visit_handle(cell* handle);
 134   void visit_object_array(cell* start, cell* end);
 135   void visit_partial_objects(cell start, cell card_start, cell card_end);
 136   void visit_slots(object* ptr);
 137   void visit_stack_elements(segment* region, cell* top);
 138   void visit_all_roots();
 139   void visit_callstack_object(callstack* stack);
 140   void visit_callstack(context* ctx);
 141   void visit_context(context *ctx);
 142   void visit_code_block_objects(code_block* compiled);
 143   void visit_embedded_literals(code_block* compiled);
 144   void visit_object_code_block(object* obj);
 145   void visit_context_code_blocks();
 146   void visit_uninitialized_code_blocks();
 147   void visit_embedded_code_pointers(code_block* compiled);
 148   void visit_object(object* obj);
 149   void visit_mark_stack(std::vector<cell>* mark_stack);
 150   void visit_instruction_operands(code_block* block, cell rel_base);
 151
 152   template <typename SourceGeneration>
 153   cell visit_card(SourceGeneration* gen, cell index, cell start);
 154   template <typename SourceGeneration>
 155   void visit_cards(SourceGeneration* gen, card mask, card unmask);
 156   void visit_code_heap_roots(std::set<code_block*>* remembered_set);
 157
 158   template <typename TargetGeneration>
 159   void cheneys_algorithm(TargetGeneration* gen, cell scan);
 160 };
 161
 162 template <typename Fixup>
 163 cell slot_visitor<Fixup>::visit_pointer(cell pointer) {
 164   object* untagged = fixup.fixup_data(untag<object>(pointer));
 165   return RETAG(untagged, TAG(pointer));
 166 }
 167
 168 template <typename Fixup> void slot_visitor<Fixup>::visit_handle(cell* handle) {
 169   if (!immediate_p(*handle)) {
 170     *handle = visit_pointer(*handle);
 171   }
 172 }
 173
 174 template <typename Fixup>
 175 void slot_visitor<Fixup>::visit_object_array(cell* start, cell* end) {
 176   while (start < end)
 177     visit_handle(start++);
 178 }
 179
 180 template <typename Fixup> void slot_visitor<Fixup>::visit_slots(object* obj) {
 181   if (obj->type() == CALLSTACK_TYPE)
 182     visit_callstack_object((callstack*)obj);
 183   else {
 184     cell* start = (cell*)obj + 1;
 185     cell* end = start + obj->slot_count(fixup);
 186     visit_object_array(start, end);
 187   }
 188 }
 189
 190 template <typename Fixup>
 191 void slot_visitor<Fixup>::visit_stack_elements(segment* region, cell* top) {
 192   visit_object_array((cell*)region->start, top + 1);
 193 }
 194
 195 template <typename Fixup> void slot_visitor<Fixup>::visit_all_roots() {
 196   FACTOR_FOR_EACH(parent->data_roots) {
 197     visit_handle(*iter);
 198   }
 199
 200   auto callback_slot_visitor = [&](code_block* stub, cell size) {
 201     visit_handle(&stub->owner);
 202   };
 203   parent->callbacks->allocator->iterate(callback_slot_visitor);
 204
 205   FACTOR_FOR_EACH(parent->code->uninitialized_blocks) {
 206     iter->second = visit_pointer(iter->second);
 207   }
 208
 209   FACTOR_FOR_EACH(parent->sample_callstacks) {
 210     visit_handle(&*iter);
 211   }
 212
 213   FACTOR_FOR_EACH(parent->samples) {
 214     visit_handle(&iter->thread);
 215   }
 216
 217   visit_object_array(parent->special_objects,
 218                      parent->special_objects + special_object_count);
 219
 220   FACTOR_FOR_EACH(parent->active_contexts) {
 221     visit_context(*iter);
 222   }
 223 }
 224
 225 // primitive_minor_gc() is invoked by inline GC checks, and it needs to
 226 // fill in uninitialized stack locations before actually calling the GC.
 227 // See the documentation in compiler.cfg.stacks.vacant for details.
 228
 229 // So for each call frame:
 230 //  - scrub some uninitialized locations
 231 //  - trace roots in spill slots
 232
 233 template <typename Fixup> struct call_frame_slot_visitor {
 234   slot_visitor<Fixup>* visitor;
 235   // NULL in case we're a visitor for a callstack object.
 236   context* ctx;
 237
 238   void scrub_stack(cell stack, uint8_t* bitmap, cell base, uint32_t count) {
 239     for (cell loc = 0; loc < count; loc++) {
 240       if (bitmap_p(bitmap, base + loc)) {
 241 #ifdef DEBUG_GC_MAPS
 242         FACTOR_PRINT("scrubbing stack location " << loc);
 243 #endif
 244         *((cell*)stack - loc) = 0;
 245       }
 246     }
 247   }
 248
 249   call_frame_slot_visitor(slot_visitor<Fixup>* visitor, context* ctx)
 250       : visitor(visitor), ctx(ctx) {}
 251
 252   // frame top -> [return address]
 253   //              [spill area]
 254   //              ...
 255   //              [entry_point]
 256   //              [size]
 257
 258   void operator()(cell frame_top, cell size, code_block* owner, cell addr) {
 259     cell return_address = owner->offset(addr);
 260
 261     code_block* compiled =
 262         Fixup::translated_code_block_map ? owner
 263                                          : visitor->fixup.translate_code(owner);
 264     gc_info* info = compiled->block_gc_info();
 265
 266     FACTOR_ASSERT(return_address < compiled->size());
 267     cell callsite = info->return_address_index(return_address);
 268     if (callsite == (cell)-1)
 269       return;
 270
 271 #ifdef DEBUG_GC_MAPS
 272     FACTOR_PRINT("call frame code block " << compiled << " with offset "
 273                  << return_address);
 274 #endif
 275     cell* stack_pointer = (cell*)frame_top;
 276     uint8_t* bitmap = info->gc_info_bitmap();
 277
 278     if (ctx) {
 279       // Scrub vacant stack locations.
 280       scrub_stack(ctx->datastack,
 281                   bitmap,
 282                   info->callsite_scrub_d(callsite),
 283                   info->scrub_d_count);
 284       scrub_stack(ctx->retainstack,
 285                   bitmap,
 286                   info->callsite_scrub_r(callsite),
 287                   info->scrub_r_count);
 288     }
 289
 290     // Subtract old value of base pointer from every derived pointer.
 291     for (cell spill_slot = 0; spill_slot < info->derived_root_count;
 292          spill_slot++) {
 293       uint32_t base_pointer = info->lookup_base_pointer(callsite, spill_slot);
 294       if (base_pointer != (uint32_t)-1) {
 295 #ifdef DEBUG_GC_MAPS
 296         FACTOR_PRINT("visiting derived root " << spill_slot
 297                      << " with base pointer " << base_pointer);
 298 #endif
 299         stack_pointer[spill_slot] -= stack_pointer[base_pointer];
 300       }
 301     }
 302
 303     // Update all GC roots, including base pointers.
 304     cell callsite_gc_roots = info->callsite_gc_roots(callsite);
 305
 306     for (cell spill_slot = 0; spill_slot < info->gc_root_count; spill_slot++) {
 307       if (bitmap_p(bitmap, callsite_gc_roots + spill_slot)) {
 308 #ifdef DEBUG_GC_MAPS
 309         FACTOR_PRINT("visiting GC root " << spill_slot);
 310 #endif
 311         visitor->visit_handle(stack_pointer + spill_slot);
 312       }
 313     }
 314
 315     // Add the base pointers to obtain new derived pointer values.
 316     for (cell spill_slot = 0; spill_slot < info->derived_root_count;
 317          spill_slot++) {
 318       uint32_t base_pointer = info->lookup_base_pointer(callsite, spill_slot);
 319       if (base_pointer != (uint32_t)-1)
 320         stack_pointer[spill_slot] += stack_pointer[base_pointer];
 321     }
 322   }
 323 };
 324
 325 template <typename Fixup>
 326 void slot_visitor<Fixup>::visit_callstack_object(callstack* stack) {
 327   call_frame_slot_visitor<Fixup> call_frame_visitor(this, NULL);
 328   parent->iterate_callstack_object(stack, call_frame_visitor, fixup);
 329 }
 330
 331 template <typename Fixup>
 332 void slot_visitor<Fixup>::visit_callstack(context* ctx) {
 333   call_frame_slot_visitor<Fixup> call_frame_visitor(this, ctx);
 334   parent->iterate_callstack(ctx, call_frame_visitor, fixup);
 335 }
 336
 337 template <typename Fixup>
 338 void slot_visitor<Fixup>::visit_context(context* ctx) {
 339   // Callstack is visited first because it scrubs the data and retain
 340   // stacks.
 341   visit_callstack(ctx);
 342
 343   cell ds_ptr = ctx->datastack;
 344   cell rs_ptr = ctx->retainstack;
 345   segment* ds_seg = ctx->datastack_seg;
 346   segment* rs_seg = ctx->retainstack_seg;
 347   visit_stack_elements(ds_seg, (cell*)ds_ptr);
 348   visit_stack_elements(rs_seg, (cell*)rs_ptr);
 349   visit_object_array(ctx->context_objects,
 350                      ctx->context_objects + context_object_count);
 351
 352   // Clear out the space not visited with a known pattern. That makes
 353   // it easier to see if uninitialized reads are made.
 354   ctx->fill_stack_seg(ds_ptr, ds_seg, 0xbaadbadd);
 355   ctx->fill_stack_seg(rs_ptr, rs_seg, 0xdaabdaab);
 356 }
 357
 358 template <typename Fixup>
 359 void slot_visitor<Fixup>::visit_code_block_objects(code_block* compiled) {
 360   visit_handle(&compiled->owner);
 361   visit_handle(&compiled->parameters);
 362   visit_handle(&compiled->relocation);
 363 }
 364
 365 template <typename Fixup>
 366 void slot_visitor<Fixup>::visit_embedded_literals(code_block* compiled) {
 367   if (parent->code->uninitialized_p(compiled))
 368     return;
 369
 370   auto update_literal_refs = [&](instruction_operand op) {
 371     if (op.rel.type() == RT_LITERAL) {
 372       cell value = op.load_value(op.pointer);
 373       if (!immediate_p(value)) {
 374         op.store_value(visit_pointer(value));
 375       }
 376     }
 377   };
 378   compiled->each_instruction_operand(update_literal_refs);
 379 }
 380
 381 template <typename Fixup> struct call_frame_code_block_visitor {
 382   Fixup fixup;
 383
 384   call_frame_code_block_visitor(Fixup fixup)
 385       : fixup(fixup) {}
 386
 387   void operator()(cell frame_top, cell size, code_block* owner, cell addr) {
 388     code_block* compiled =
 389         Fixup::translated_code_block_map ? owner : fixup.fixup_code(owner);
 390     cell fixed_addr = compiled->address_for_offset(owner->offset(addr));
 391
 392     *(cell*)frame_top = fixed_addr;
 393   }
 394 };
 395
 396 template <typename Fixup>
 397 void slot_visitor<Fixup>::visit_object_code_block(object* obj) {
 398   switch (obj->type()) {
 399     case WORD_TYPE: {
 400       word* w = (word*)obj;
 401       if (w->entry_point)
 402         w->entry_point = fixup.fixup_code(w->code())->entry_point();
 403       break;
 404     }
 405     case QUOTATION_TYPE: {
 406       quotation* q = (quotation*)obj;
 407       if (q->entry_point)
 408         q->entry_point = fixup.fixup_code(q->code())->entry_point();
 409       break;
 410     }
 411     case CALLSTACK_TYPE: {
 412       callstack* stack = (callstack*)obj;
 413       call_frame_code_block_visitor<Fixup> call_frame_visitor(fixup);
 414       parent->iterate_callstack_object(stack, call_frame_visitor, fixup);
 415       break;
 416     }
 417   }
 418 }
 419
 420 template <typename Fixup>
 421 void slot_visitor<Fixup>::visit_context_code_blocks() {
 422   call_frame_code_block_visitor<Fixup> call_frame_visitor(fixup);
 423   FACTOR_FOR_EACH(parent->active_contexts) {
 424     parent->iterate_callstack(*iter, call_frame_visitor, fixup);
 425   }
 426 }
 427
 428 template <typename Fixup>
 429 void slot_visitor<Fixup>::visit_uninitialized_code_blocks() {
 430   std::map<code_block*, cell> new_uninitialized_blocks;
 431   FACTOR_FOR_EACH(parent->code->uninitialized_blocks) {
 432     new_uninitialized_blocks.insert(
 433         std::make_pair(fixup.fixup_code(iter->first), iter->second));
 434   }
 435   parent->code->uninitialized_blocks = new_uninitialized_blocks;
 436 }
 437
 438 template <typename Fixup>
 439 void slot_visitor<Fixup>::visit_embedded_code_pointers(code_block* compiled) {
 440   if (parent->code->uninitialized_p(compiled))
 441     return;
 442   auto update_code_block_refs = [&](instruction_operand op){
 443     relocation_type type = op.rel.type();
 444     if (type == RT_ENTRY_POINT ||
 445         type == RT_ENTRY_POINT_PIC ||
 446         type == RT_ENTRY_POINT_PIC_TAIL) {
 447       code_block* block = fixup.fixup_code(op.load_code_block());
 448       op.store_value(block->entry_point());
 449     }
 450   };
 451   compiled->each_instruction_operand(update_code_block_refs);
 452 }
 453
 454 template <typename Fixup>
 455 void slot_visitor<Fixup>::visit_object(object *ptr) {
 456   visit_slots(ptr);
 457   if (ptr->type() == ALIEN_TYPE)
 458     ((alien*)ptr)->update_address();
 459 }
 460
 461 // Pops items from the mark stack and visits them until the stack is
 462 // empty. Used when doing a full collection and when collecting to
 463 // tenured space.
 464 template <typename Fixup>
 465 void slot_visitor<Fixup>::visit_mark_stack(std::vector<cell>* mark_stack) {
 466   while (!mark_stack->empty()) {
 467     cell ptr = mark_stack->back();
 468     mark_stack->pop_back();
 469
 470     if (ptr & 1) {
 471       code_block* compiled = (code_block*)(ptr - 1);
 472       visit_code_block_objects(compiled);
 473       visit_embedded_literals(compiled);
 474       visit_embedded_code_pointers(compiled);
 475     } else {
 476       object* obj = (object*)ptr;
 477       visit_object(obj);
 478       visit_object_code_block(obj);
 479     }
 480   }
 481 }
 482
 483 // Visits the instruction operands in a code block. If the operand is
 484 // a pointer to a code block or data object, then the fixup is applied
 485 // to it. Otherwise, if it is an external addess, that address is
 486 // recomputed. If it is an untagged number literal (RT_UNTAGGED) or an
 487 // immediate value, then nothing is done with it.
 488 template <typename Fixup>
 489 void slot_visitor<Fixup>::visit_instruction_operands(code_block* block,
 490                                                      cell rel_base) {
 491   auto visit_func = [&](instruction_operand op){
 492     cell old_offset = rel_base + op.rel.offset();
 493     cell old_value = op.load_value(old_offset);
 494     switch (op.rel.type()) {
 495       case RT_LITERAL: {
 496         if (!immediate_p(old_value)) {
 497           op.store_value(visit_pointer(old_value));
 498         }
 499         break;
 500       }
 501       case RT_ENTRY_POINT:
 502       case RT_ENTRY_POINT_PIC:
 503       case RT_ENTRY_POINT_PIC_TAIL:
 504       case RT_HERE: {
 505         cell offset = TAG(old_value);
 506         code_block* compiled = (code_block*)UNTAG(old_value);
 507         op.store_value(RETAG(fixup.fixup_code(compiled), offset));
 508         break;
 509       }
 510       case RT_UNTAGGED:
 511         break;
 512       default:
 513         op.store_value(parent->compute_external_address(op));
 514         break;
 515     }
 516   };
 517   block->each_instruction_operand(visit_func);
 518 }
 519
 520 template <typename Fixup>
 521 void slot_visitor<Fixup>::visit_partial_objects(cell start,
 522                                                 cell card_start,
 523                                                 cell card_end) {
 524   cell *scan_start = (cell*)start + 1;
 525   cell *scan_end = scan_start + ((object*)start)->slot_count();
 526
 527   scan_start = std::max(scan_start, (cell*)card_start);
 528   scan_end = std::min(scan_end, (cell*)card_end);
 529
 530   visit_object_array(scan_start, scan_end);
 531 }
 532
 533 template <typename Fixup>
 534 template <typename SourceGeneration>
 535 cell slot_visitor<Fixup>::visit_card(SourceGeneration* gen,
 536                                      cell index, cell start) {
 537   cell heap_base = parent->data->start;
 538   cell start_addr = heap_base + index * card_size;
 539   cell end_addr = start_addr + card_size;
 540
 541   // Forward to the next object whose address is in the card.
 542   if (!start || (start + ((object*)start)->size()) < start_addr) {
 543     // Optimization because finding the objects in a memory range is
 544     // expensive. It helps a lot when tracing consecutive cards.
 545     cell gen_start_card = (gen->start - heap_base) / card_size;
 546     start = gen->starts
 547         .find_object_containing_card(index - gen_start_card);
 548   }
 549
 550   while (start && start < end_addr) {
 551     visit_partial_objects(start, start_addr, end_addr);
 552     if ((start + ((object*)start)->size()) >= end_addr) {
 553       // The object can overlap the card boundary, then the
 554       // remainder of it will be handled in the next card
 555       // tracing if that card is marked.
 556       break;
 557     }
 558     start = gen->next_object_after(start);
 559   }
 560   return start;
 561 }
 562
 563 template <typename Fixup>
 564 template <typename SourceGeneration>
 565 void slot_visitor<Fixup>::visit_cards(SourceGeneration* gen,
 566                                       card mask, card unmask) {
 567   card_deck* decks = parent->data->decks;
 568   card_deck* cards = parent->data->cards;
 569   cell heap_base = parent->data->start;
 570
 571   cell first_deck = (gen->start - heap_base) / deck_size;
 572   cell last_deck = (gen->end - heap_base) / deck_size;
 573
 574   // Address of last traced object.
 575   cell start = 0;
 576   for (cell di = first_deck; di < last_deck; di++) {
 577     if (decks[di] & mask) {
 578       decks[di] &= ~unmask;
 579       decks_scanned++;
 580
 581       cell first_card = cards_per_deck * di;
 582       cell last_card = first_card + cards_per_deck;
 583
 584       for (cell ci = first_card; ci < last_card; ci++) {
 585         if (cards[ci] & mask) {
 586           cards[ci] &= ~unmask;
 587           cards_scanned++;
 588
 589           start = visit_card(gen, ci, start);
 590           if (!start) {
 591             // At end of generation, no need to scan more cards.
 592             return;
 593           }
 594         }
 595       }
 596     }
 597   }
 598 }
 599
 600 template <typename Fixup>
 601 void slot_visitor<Fixup>::visit_code_heap_roots(std::set<code_block*>* remembered_set) {
 602   FACTOR_FOR_EACH(*remembered_set) {
 603     code_block* compiled = *iter;
 604     visit_code_block_objects(compiled);
 605     visit_embedded_literals(compiled);
 606     compiled->flush_icache();
 607   }
 608 }
 609
 610 template <typename Fixup>
 611 template <typename TargetGeneration>
 612 void slot_visitor<Fixup>::cheneys_algorithm(TargetGeneration* gen, cell scan) {
 613   while (scan && scan < gen->here) {
 614     visit_object((object*)scan);
 615     scan = gen->next_object_after(scan);
 616   }
 617 }
 618
 619 }