vm/slot_visitor.hpp

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