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   FACTOR_FOR_EACH(parent->data_roots) {
 195     visit_handle(*iter);
 196   }
 197 }
 198
 199 template <typename Fixup> struct callback_slot_visitor {
 200   slot_visitor<Fixup>* visitor;
 201
 202   callback_slot_visitor(slot_visitor<Fixup>* visitor) : visitor(visitor) {}
 203
 204   void operator()(code_block* stub, cell size) {
 205     visitor->visit_handle(&stub->owner);
 206   }
 207 };
 208
 209 template <typename Fixup> void slot_visitor<Fixup>::visit_callback_roots() {
 210   callback_slot_visitor<Fixup> callback_visitor(this);
 211   parent->callbacks->allocator->iterate(callback_visitor);
 212 }
 213
 214 template <typename Fixup>
 215 void slot_visitor<Fixup>::visit_literal_table_roots() {
 216   FACTOR_FOR_EACH(parent->code->uninitialized_blocks) {
 217     iter->second = visit_pointer(iter->second);
 218   }
 219 }
 220
 221 template <typename Fixup> void slot_visitor<Fixup>::visit_sample_callstacks() {
 222   FACTOR_FOR_EACH(parent->sample_callstacks) {
 223     visit_handle(&*iter);
 224   }
 225 }
 226
 227 template <typename Fixup> void slot_visitor<Fixup>::visit_sample_threads() {
 228   FACTOR_FOR_EACH(parent->samples) {
 229     visit_handle(&iter->thread);
 230   }
 231 }
 232
 233 template <typename Fixup> void slot_visitor<Fixup>::visit_all_roots() {
 234   visit_handle(&parent->true_object);
 235   visit_handle(&parent->bignum_zero);
 236   visit_handle(&parent->bignum_pos_one);
 237   visit_handle(&parent->bignum_neg_one);
 238
 239   visit_data_roots();
 240   visit_callback_roots();
 241   visit_literal_table_roots();
 242   visit_sample_callstacks();
 243   visit_sample_threads();
 244
 245   visit_object_array(parent->special_objects,
 246                      parent->special_objects + special_object_count);
 247
 248   visit_contexts();
 249 }
 250
 251 /* primitive_minor_gc() is invoked by inline GC checks, and it needs to fill in
 252    uninitialized stack locations before actually calling the GC. See the
 253    documentation in compiler.cfg.stacks.vacant for details.
 254
 255    So for each call frame:
 256
 257     - scrub some uninitialized locations
 258     - trace roots in spill slots
 259 */
 260 template <typename Fixup> struct call_frame_slot_visitor {
 261   slot_visitor<Fixup>* visitor;
 262   /* NULL in case we're a visitor for a callstack object. */
 263   context* ctx;
 264
 265   void scrub_stack(cell stack, uint8_t* bitmap, cell base, uint32_t count) {
 266     for (cell loc = 0; loc < count; loc++) {
 267       if (bitmap_p(bitmap, base + loc)) {
 268 #ifdef DEBUG_GC_MAPS
 269         FACTOR_PRINT("scrubbing stack location " << loc);
 270 #endif
 271         *((cell*)stack - loc) = 0;
 272       }
 273     }
 274   }
 275
 276   call_frame_slot_visitor(slot_visitor<Fixup>* visitor, context* ctx)
 277       : visitor(visitor), ctx(ctx) {}
 278
 279   /*
 280         frame top -> [return address]
 281                      [spill area]
 282                      ...
 283                      [entry_point]
 284                      [size]
 285         */
 286   void operator()(cell frame_top, cell size, code_block* owner, cell addr) {
 287     cell return_address = owner->offset(addr);
 288
 289     code_block* compiled =
 290         Fixup::translated_code_block_map ? owner
 291                                          : visitor->fixup.translate_code(owner);
 292     gc_info* info = compiled->block_gc_info();
 293
 294     FACTOR_ASSERT(return_address < compiled->size());
 295     cell callsite = info->return_address_index(return_address);
 296     if (callsite == (cell)-1)
 297       return;
 298
 299 #ifdef DEBUG_GC_MAPS
 300     FACTOR_PRINT("call frame code block " << compiled << " with offset "
 301                  << return_address);
 302 #endif
 303     cell* stack_pointer = (cell*)frame_top;
 304     uint8_t* bitmap = info->gc_info_bitmap();
 305
 306     if (ctx) {
 307       /* Scrub vacant stack locations. */
 308       scrub_stack(ctx->datastack,
 309                   bitmap,
 310                   info->callsite_scrub_d(callsite),
 311                   info->scrub_d_count);
 312       scrub_stack(ctx->retainstack,
 313                   bitmap,
 314                   info->callsite_scrub_r(callsite),
 315                   info->scrub_r_count);
 316     }
 317
 318     /* Subtract old value of base pointer from every derived pointer. */
 319     for (cell spill_slot = 0; spill_slot < info->derived_root_count;
 320          spill_slot++) {
 321       uint32_t base_pointer = info->lookup_base_pointer(callsite, spill_slot);
 322       if (base_pointer != (uint32_t)-1) {
 323 #ifdef DEBUG_GC_MAPS
 324         FACTOR_PRINT("visiting derived root " << spill_slot
 325                      << " with base pointer " << base_pointer);
 326 #endif
 327         stack_pointer[spill_slot] -= stack_pointer[base_pointer];
 328       }
 329     }
 330
 331     /* Update all GC roots, including base pointers. */
 332     cell callsite_gc_roots = info->callsite_gc_roots(callsite);
 333
 334     for (cell spill_slot = 0; spill_slot < info->gc_root_count; spill_slot++) {
 335       if (bitmap_p(bitmap, callsite_gc_roots + spill_slot)) {
 336 #ifdef DEBUG_GC_MAPS
 337         FACTOR_PRINT("visiting GC root " << spill_slot);
 338 #endif
 339         visitor->visit_handle(stack_pointer + spill_slot);
 340       }
 341     }
 342
 343     /* Add the base pointers to obtain new derived pointer values. */
 344     for (cell spill_slot = 0; spill_slot < info->derived_root_count;
 345          spill_slot++) {
 346       uint32_t base_pointer = info->lookup_base_pointer(callsite, spill_slot);
 347       if (base_pointer != (uint32_t)-1)
 348         stack_pointer[spill_slot] += stack_pointer[base_pointer];
 349     }
 350   }
 351 };
 352
 353 template <typename Fixup>
 354 void slot_visitor<Fixup>::visit_callstack_object(callstack* stack) {
 355   call_frame_slot_visitor<Fixup> call_frame_visitor(this, NULL);
 356   parent->iterate_callstack_object(stack, call_frame_visitor, fixup);
 357 }
 358
 359 template <typename Fixup>
 360 void slot_visitor<Fixup>::visit_callstack(context* ctx) {
 361   call_frame_slot_visitor<Fixup> call_frame_visitor(this, ctx);
 362   parent->iterate_callstack(ctx, call_frame_visitor, fixup);
 363 }
 364
 365 template <typename Fixup>
 366 void slot_visitor<Fixup>::visit_context(context* ctx) {
 367   /* Callstack is visited first because it scrubs the data and retain
 368      stacks. */
 369   visit_callstack(ctx);
 370
 371   cell ds_ptr = ctx->datastack;
 372   cell rs_ptr = ctx->retainstack;
 373   segment* ds_seg = ctx->datastack_seg;
 374   segment* rs_seg = ctx->retainstack_seg;
 375   visit_stack_elements(ds_seg, (cell*)ds_ptr);
 376   visit_stack_elements(rs_seg, (cell*)rs_ptr);
 377   visit_object_array(ctx->context_objects,
 378                      ctx->context_objects + context_object_count);
 379
 380   /* Clear out the space not visited with a known pattern. That makes
 381      it easier to see if uninitialized reads are made. */
 382   ctx->fill_stack_seg(ds_ptr, ds_seg, 0xbaadbadd);
 383   ctx->fill_stack_seg(rs_ptr, rs_seg, 0xdaabdaab);
 384 }
 385
 386 template <typename Fixup> void slot_visitor<Fixup>::visit_contexts() {
 387   FACTOR_FOR_EACH(parent->active_contexts) {
 388     visit_context(*iter);
 389   }
 390 }
 391
 392 template <typename Fixup> struct literal_references_visitor {
 393   slot_visitor<Fixup>* visitor;
 394
 395   explicit literal_references_visitor(slot_visitor<Fixup>* visitor)
 396       : visitor(visitor) {}
 397
 398   void operator()(instruction_operand op) {
 399     if (op.rel_type() == RT_LITERAL)
 400       op.store_value(visitor->visit_pointer(op.load_value()));
 401   }
 402 };
 403
 404 template <typename Fixup>
 405 void slot_visitor<Fixup>::visit_code_block_objects(code_block* compiled) {
 406   visit_handle(&compiled->owner);
 407   visit_handle(&compiled->parameters);
 408   visit_handle(&compiled->relocation);
 409 }
 410
 411 template <typename Fixup>
 412 void slot_visitor<Fixup>::visit_embedded_literals(code_block* compiled) {
 413   if (!parent->code->uninitialized_p(compiled)) {
 414     literal_references_visitor<Fixup> visitor(this);
 415     compiled->each_instruction_operand(visitor);
 416   }
 417 }
 418
 419 template <typename Fixup> struct call_frame_code_block_visitor {
 420   Fixup fixup;
 421
 422   call_frame_code_block_visitor(Fixup fixup)
 423       : fixup(fixup) {}
 424
 425   void operator()(cell frame_top, cell size, code_block* owner, cell addr) {
 426     code_block* compiled =
 427         Fixup::translated_code_block_map ? owner : fixup.fixup_code(owner);
 428     cell fixed_addr = compiled->address_for_offset(owner->offset(addr));
 429
 430     *(cell*)frame_top = fixed_addr;
 431   }
 432 };
 433
 434 template <typename Fixup>
 435 void slot_visitor<Fixup>::visit_object_code_block(object* obj) {
 436   switch (obj->type()) {
 437     case WORD_TYPE: {
 438       word* w = (word*)obj;
 439       if (w->entry_point)
 440         w->entry_point = fixup.fixup_code(w->code())->entry_point();
 441       break;
 442     }
 443     case QUOTATION_TYPE: {
 444       quotation* q = (quotation*)obj;
 445       if (q->entry_point)
 446         q->entry_point = fixup.fixup_code(q->code())->entry_point();
 447       break;
 448     }
 449     case CALLSTACK_TYPE: {
 450       callstack* stack = (callstack*)obj;
 451       call_frame_code_block_visitor<Fixup> call_frame_visitor(fixup);
 452       parent->iterate_callstack_object(stack, call_frame_visitor, fixup);
 453       break;
 454     }
 455   }
 456 }
 457
 458 template <typename Fixup>
 459 void slot_visitor<Fixup>::visit_context_code_blocks() {
 460   call_frame_code_block_visitor<Fixup> call_frame_visitor(fixup);
 461   FACTOR_FOR_EACH(parent->active_contexts) {
 462     parent->iterate_callstack(*iter, call_frame_visitor, fixup);
 463   }
 464 }
 465
 466 template <typename Fixup>
 467 void slot_visitor<Fixup>::visit_uninitialized_code_blocks() {
 468   std::map<code_block*, cell> new_uninitialized_blocks;
 469   FACTOR_FOR_EACH(parent->code->uninitialized_blocks) {
 470     new_uninitialized_blocks.insert(
 471         std::make_pair(fixup.fixup_code(iter->first), iter->second));
 472   }
 473   parent->code->uninitialized_blocks = new_uninitialized_blocks;
 474 }
 475
 476 template <typename Fixup> struct embedded_code_pointers_visitor {
 477   Fixup fixup;
 478
 479   explicit embedded_code_pointers_visitor(Fixup fixup) : fixup(fixup) {}
 480
 481   void operator()(instruction_operand op) {
 482     relocation_type type = op.rel_type();
 483     if (type == RT_ENTRY_POINT || type == RT_ENTRY_POINT_PIC ||
 484         type == RT_ENTRY_POINT_PIC_TAIL)
 485       op.store_code_block(fixup.fixup_code(op.load_code_block()));
 486   }
 487 };
 488
 489 template <typename Fixup>
 490 void slot_visitor<Fixup>::visit_embedded_code_pointers(code_block* compiled) {
 491   if (!parent->code->uninitialized_p(compiled)) {
 492     embedded_code_pointers_visitor<Fixup> operand_visitor(fixup);
 493     compiled->each_instruction_operand(operand_visitor);
 494   }
 495 }
 496
 497 template <typename Fixup>
 498 void slot_visitor<Fixup>::visit_object(object *ptr) {
 499   visit_slots(ptr);
 500   if (ptr->type() == ALIEN_TYPE)
 501     ((alien*)ptr)->update_address();
 502 }
 503
 504 /* Pops items from the mark stack and visits them until the stack is
 505    empty. Used when doing a full collection and when collecting to
 506    tenured space. */
 507 template <typename Fixup>
 508 void slot_visitor<Fixup>::visit_mark_stack(std::vector<cell>* mark_stack) {
 509   while (!mark_stack->empty()) {
 510     cell ptr = mark_stack->back();
 511     // TJaba
 512     mark_stack->pop_back();
 513
 514     if (ptr & 1) {
 515       code_block* compiled = (code_block*)(ptr - 1);
 516       visit_code_block_objects(compiled);
 517       visit_embedded_literals(compiled);
 518       visit_embedded_code_pointers(compiled);
 519     } else {
 520       object* obj = (object*)ptr;
 521       visit_object(obj);
 522       visit_object_code_block(obj);
 523     }
 524   }
 525 }
 526
 527 }