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. The
  95 functor returns a new untagged object pointer. The return value may or may not
  96 equal the old one,
  97 however the new pointer receives the same tag before being stored back to the
  98 original location.
  99
 100 Slots storing immediate values are left unchanged and the visitor does inspect
 101 them.
 102
 103 This is used by GC's copying, sweep and compact phases, and the implementation
 104 of the become primitive.
 105
 106 Iteration is driven by visit_*() methods. Only one of them define GC roots:
 107 - visit_all_roots()
 108
 109 Code block visitors iterate over sets of code blocks, applying a functor to
 110 each one. The functor returns a new code_block pointer, which may or may not
 111 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 the
 114 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
 124   slot_visitor<Fixup>(factor_vm* parent, Fixup fixup)
 125       : parent(parent), fixup(fixup) {}
 126
 127   cell visit_pointer(cell pointer);
 128   void visit_handle(cell* handle);
 129   void visit_object_array(cell* start, cell* end);
 130   void visit_partial_objects(cell start, cell card_start, cell card_end);
 131   void visit_slots(object* ptr);
 132   void visit_stack_elements(segment* region, cell* top);
 133   void visit_all_roots();
 134   void visit_callstack_object(callstack* stack);
 135   void visit_callstack(context* ctx);
 136   void visit_context(context *ctx);
 137   void visit_code_block_objects(code_block* compiled);
 138   void visit_embedded_literals(code_block* compiled);
 139   void visit_object_code_block(object* obj);
 140   void visit_context_code_blocks();
 141   void visit_uninitialized_code_blocks();
 142   void visit_embedded_code_pointers(code_block* compiled);
 143   void visit_object(object* obj);
 144   void visit_mark_stack(std::vector<cell>* mark_stack);
 145   void visit_instruction_operands(code_block* block, cell rel_base);
 146 };
 147
 148 template <typename Fixup>
 149 cell slot_visitor<Fixup>::visit_pointer(cell pointer) {
 150   if (immediate_p(pointer))
 151     return pointer;
 152
 153   object* untagged = fixup.fixup_data(untag<object>(pointer));
 154   return RETAG(untagged, TAG(pointer));
 155 }
 156
 157 template <typename Fixup> void slot_visitor<Fixup>::visit_handle(cell* handle) {
 158   *handle = visit_pointer(*handle);
 159 }
 160
 161 template <typename Fixup>
 162 void slot_visitor<Fixup>::visit_object_array(cell* start, cell* end) {
 163   while (start < end)
 164     visit_handle(start++);
 165 }
 166
 167 template <typename Fixup>
 168 void slot_visitor<Fixup>::visit_partial_objects(cell start,
 169                                                 cell card_start,
 170                                                 cell card_end) {
 171   cell *scan_start = (cell*)start + 1;
 172   cell *scan_end = scan_start + ((object*)start)->slot_count();
 173
 174   scan_start = std::max(scan_start, (cell*)card_start);
 175   scan_end = std::min(scan_end, (cell*)card_end);
 176
 177   visit_object_array(scan_start, scan_end);
 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   visit_handle(&parent->true_object);
 197   visit_handle(&parent->bignum_zero);
 198   visit_handle(&parent->bignum_pos_one);
 199   visit_handle(&parent->bignum_neg_one);
 200
 201   FACTOR_FOR_EACH(parent->data_roots) {
 202     visit_handle(*iter);
 203   }
 204
 205   auto callback_slot_visitor = [&](code_block* stub, cell size) {
 206     visit_handle(&stub->owner);
 207   };
 208   parent->callbacks->allocator->iterate(callback_slot_visitor);
 209
 210   FACTOR_FOR_EACH(parent->code->uninitialized_blocks) {
 211     iter->second = visit_pointer(iter->second);
 212   }
 213
 214   FACTOR_FOR_EACH(parent->sample_callstacks) {
 215     visit_handle(&*iter);
 216   }
 217
 218   FACTOR_FOR_EACH(parent->samples) {
 219     visit_handle(&iter->thread);
 220   }
 221
 222   visit_object_array(parent->special_objects,
 223                      parent->special_objects + special_object_count);
 224
 225   FACTOR_FOR_EACH(parent->active_contexts) {
 226     visit_context(*iter);
 227   }
 228 }
 229
 230 /* primitive_minor_gc() is invoked by inline GC checks, and it needs to fill in
 231    uninitialized stack locations before actually calling the GC. See the
 232    documentation in compiler.cfg.stacks.vacant for details.
 233
 234    So for each call frame:
 235
 236     - scrub some uninitialized locations
 237     - trace roots in spill slots
 238 */
 239 template <typename Fixup> struct call_frame_slot_visitor {
 240   slot_visitor<Fixup>* visitor;
 241   /* NULL in case we're a visitor for a callstack object. */
 242   context* ctx;
 243
 244   void scrub_stack(cell stack, uint8_t* bitmap, cell base, uint32_t count) {
 245     for (cell loc = 0; loc < count; loc++) {
 246       if (bitmap_p(bitmap, base + loc)) {
 247 #ifdef DEBUG_GC_MAPS
 248         FACTOR_PRINT("scrubbing stack location " << loc);
 249 #endif
 250         *((cell*)stack - loc) = 0;
 251       }
 252     }
 253   }
 254
 255   call_frame_slot_visitor(slot_visitor<Fixup>* visitor, context* ctx)
 256       : visitor(visitor), ctx(ctx) {}
 257
 258   /*
 259         frame top -> [return address]
 260                      [spill area]
 261                      ...
 262                      [entry_point]
 263                      [size]
 264         */
 265   void operator()(cell frame_top, cell size, code_block* owner, cell addr) {
 266     cell return_address = owner->offset(addr);
 267
 268     code_block* compiled =
 269         Fixup::translated_code_block_map ? owner
 270                                          : visitor->fixup.translate_code(owner);
 271     gc_info* info = compiled->block_gc_info();
 272
 273     FACTOR_ASSERT(return_address < compiled->size());
 274     cell callsite = info->return_address_index(return_address);
 275     if (callsite == (cell)-1)
 276       return;
 277
 278 #ifdef DEBUG_GC_MAPS
 279     FACTOR_PRINT("call frame code block " << compiled << " with offset "
 280                  << return_address);
 281 #endif
 282     cell* stack_pointer = (cell*)frame_top;
 283     uint8_t* bitmap = info->gc_info_bitmap();
 284
 285     if (ctx) {
 286       /* Scrub vacant stack locations. */
 287       scrub_stack(ctx->datastack,
 288                   bitmap,
 289                   info->callsite_scrub_d(callsite),
 290                   info->scrub_d_count);
 291       scrub_stack(ctx->retainstack,
 292                   bitmap,
 293                   info->callsite_scrub_r(callsite),
 294                   info->scrub_r_count);
 295     }
 296
 297     /* Subtract old value of base pointer from every derived pointer. */
 298     for (cell spill_slot = 0; spill_slot < info->derived_root_count;
 299          spill_slot++) {
 300       uint32_t base_pointer = info->lookup_base_pointer(callsite, spill_slot);
 301       if (base_pointer != (uint32_t)-1) {
 302 #ifdef DEBUG_GC_MAPS
 303         FACTOR_PRINT("visiting derived root " << spill_slot
 304                      << " with base pointer " << base_pointer);
 305 #endif
 306         stack_pointer[spill_slot] -= stack_pointer[base_pointer];
 307       }
 308     }
 309
 310     /* Update all GC roots, including base pointers. */
 311     cell callsite_gc_roots = info->callsite_gc_roots(callsite);
 312
 313     for (cell spill_slot = 0; spill_slot < info->gc_root_count; spill_slot++) {
 314       if (bitmap_p(bitmap, callsite_gc_roots + spill_slot)) {
 315 #ifdef DEBUG_GC_MAPS
 316         FACTOR_PRINT("visiting GC root " << spill_slot);
 317 #endif
 318         visitor->visit_handle(stack_pointer + spill_slot);
 319       }
 320     }
 321
 322     /* Add the base pointers to obtain new derived pointer values. */
 323     for (cell spill_slot = 0; spill_slot < info->derived_root_count;
 324          spill_slot++) {
 325       uint32_t base_pointer = info->lookup_base_pointer(callsite, spill_slot);
 326       if (base_pointer != (uint32_t)-1)
 327         stack_pointer[spill_slot] += stack_pointer[base_pointer];
 328     }
 329   }
 330 };
 331
 332 template <typename Fixup>
 333 void slot_visitor<Fixup>::visit_callstack_object(callstack* stack) {
 334   call_frame_slot_visitor<Fixup> call_frame_visitor(this, NULL);
 335   parent->iterate_callstack_object(stack, call_frame_visitor, fixup);
 336 }
 337
 338 template <typename Fixup>
 339 void slot_visitor<Fixup>::visit_callstack(context* ctx) {
 340   call_frame_slot_visitor<Fixup> call_frame_visitor(this, ctx);
 341   parent->iterate_callstack(ctx, call_frame_visitor, fixup);
 342 }
 343
 344 template <typename Fixup>
 345 void slot_visitor<Fixup>::visit_context(context* ctx) {
 346   /* Callstack is visited first because it scrubs the data and retain
 347      stacks. */
 348   visit_callstack(ctx);
 349
 350   cell ds_ptr = ctx->datastack;
 351   cell rs_ptr = ctx->retainstack;
 352   segment* ds_seg = ctx->datastack_seg;
 353   segment* rs_seg = ctx->retainstack_seg;
 354   visit_stack_elements(ds_seg, (cell*)ds_ptr);
 355   visit_stack_elements(rs_seg, (cell*)rs_ptr);
 356   visit_object_array(ctx->context_objects,
 357                      ctx->context_objects + context_object_count);
 358
 359   /* Clear out the space not visited with a known pattern. That makes
 360      it easier to see if uninitialized reads are made. */
 361   ctx->fill_stack_seg(ds_ptr, ds_seg, 0xbaadbadd);
 362   ctx->fill_stack_seg(rs_ptr, rs_seg, 0xdaabdaab);
 363 }
 364
 365 template <typename Fixup>
 366 void slot_visitor<Fixup>::visit_code_block_objects(code_block* compiled) {
 367   visit_handle(&compiled->owner);
 368   visit_handle(&compiled->parameters);
 369   visit_handle(&compiled->relocation);
 370 }
 371
 372 template <typename Fixup>
 373 void slot_visitor<Fixup>::visit_embedded_literals(code_block* compiled) {
 374   if (parent->code->uninitialized_p(compiled))
 375     return;
 376
 377   auto update_literal_refs = [&](instruction_operand op) {
 378     if (op.rel_type() == RT_LITERAL)
 379       op.store_value(visit_pointer(op.load_value()));
 380   };
 381   compiled->each_instruction_operand(update_literal_refs);
 382 }
 383
 384 template <typename Fixup> struct call_frame_code_block_visitor {
 385   Fixup fixup;
 386
 387   call_frame_code_block_visitor(Fixup fixup)
 388       : fixup(fixup) {}
 389
 390   void operator()(cell frame_top, cell size, code_block* owner, cell addr) {
 391     code_block* compiled =
 392         Fixup::translated_code_block_map ? owner : fixup.fixup_code(owner);
 393     cell fixed_addr = compiled->address_for_offset(owner->offset(addr));
 394
 395     *(cell*)frame_top = fixed_addr;
 396   }
 397 };
 398
 399 template <typename Fixup>
 400 void slot_visitor<Fixup>::visit_object_code_block(object* obj) {
 401   switch (obj->type()) {
 402     case WORD_TYPE: {
 403       word* w = (word*)obj;
 404       if (w->entry_point)
 405         w->entry_point = fixup.fixup_code(w->code())->entry_point();
 406       break;
 407     }
 408     case QUOTATION_TYPE: {
 409       quotation* q = (quotation*)obj;
 410       if (q->entry_point)
 411         q->entry_point = fixup.fixup_code(q->code())->entry_point();
 412       break;
 413     }
 414     case CALLSTACK_TYPE: {
 415       callstack* stack = (callstack*)obj;
 416       call_frame_code_block_visitor<Fixup> call_frame_visitor(fixup);
 417       parent->iterate_callstack_object(stack, call_frame_visitor, fixup);
 418       break;
 419     }
 420   }
 421 }
 422
 423 template <typename Fixup>
 424 void slot_visitor<Fixup>::visit_context_code_blocks() {
 425   call_frame_code_block_visitor<Fixup> call_frame_visitor(fixup);
 426   FACTOR_FOR_EACH(parent->active_contexts) {
 427     parent->iterate_callstack(*iter, call_frame_visitor, fixup);
 428   }
 429 }
 430
 431 template <typename Fixup>
 432 void slot_visitor<Fixup>::visit_uninitialized_code_blocks() {
 433   std::map<code_block*, cell> new_uninitialized_blocks;
 434   FACTOR_FOR_EACH(parent->code->uninitialized_blocks) {
 435     new_uninitialized_blocks.insert(
 436         std::make_pair(fixup.fixup_code(iter->first), iter->second));
 437   }
 438   parent->code->uninitialized_blocks = new_uninitialized_blocks;
 439 }
 440
 441 template <typename Fixup>
 442 void slot_visitor<Fixup>::visit_embedded_code_pointers(code_block* compiled) {
 443   if (parent->code->uninitialized_p(compiled))
 444     return;
 445   auto update_code_block_refs = [&](instruction_operand op){
 446     relocation_type type = op.rel_type();
 447     if (type == RT_ENTRY_POINT ||
 448         type == RT_ENTRY_POINT_PIC ||
 449         type == RT_ENTRY_POINT_PIC_TAIL)
 450       op.store_code_block(fixup.fixup_code(op.load_code_block()));
 451   };
 452   compiled->each_instruction_operand(update_code_block_refs);
 453 }
 454
 455 template <typename Fixup>
 456 void slot_visitor<Fixup>::visit_object(object *ptr) {
 457   visit_slots(ptr);
 458   if (ptr->type() == ALIEN_TYPE)
 459     ((alien*)ptr)->update_address();
 460 }
 461
 462 /* Pops items from the mark stack and visits them until the stack is
 463    empty. Used when doing a full collection and when collecting to
 464    tenured space. */
 465 template <typename Fixup>
 466 void slot_visitor<Fixup>::visit_mark_stack(std::vector<cell>* mark_stack) {
 467   while (!mark_stack->empty()) {
 468     cell ptr = mark_stack->back();
 469     mark_stack->pop_back();
 470
 471     if (ptr & 1) {
 472       code_block* compiled = (code_block*)(ptr - 1);
 473       visit_code_block_objects(compiled);
 474       visit_embedded_literals(compiled);
 475       visit_embedded_code_pointers(compiled);
 476     } else {
 477       object* obj = (object*)ptr;
 478       visit_object(obj);
 479       visit_object_code_block(obj);
 480     }
 481   }
 482 }
 483
 484 /* Visits the instruction operands in a code block. If the operand is
 485    a pointer to a code block or data object, then the fixup is applied
 486    to it. Otherwise, if it is an external addess, that address is
 487    recomputed. If it is an untagged number literal (RT_UNTAGGED) or an
 488    immediate value, then nothing is done with it. */
 489 template <typename Fixup>
 490 void slot_visitor<Fixup>::visit_instruction_operands(code_block* block,
 491                                                      cell rel_base) {
 492   auto visit_func = [&](instruction_operand op){
 493     cell old_offset = rel_base + op.rel_offset();
 494     cell value = op.load_value(old_offset);
 495     switch (op.rel_type()) {
 496       case RT_LITERAL: {
 497         value = visit_pointer(value);
 498         break;
 499       }
 500       case RT_ENTRY_POINT:
 501       case RT_ENTRY_POINT_PIC:
 502       case RT_ENTRY_POINT_PIC_TAIL:
 503       case RT_HERE: {
 504         cell offset = TAG(value);
 505         code_block* compiled = (code_block*)UNTAG(value);
 506         value = RETAG(fixup.fixup_code(compiled), offset);
 507         break;
 508       }
 509       case RT_UNTAGGED:
 510         break;
 511       default:
 512         value = parent->compute_external_address(op);
 513         break;
 514     }
 515     op.store_value(value);
 516   };
 517   block->each_instruction_operand(visit_func);
 518 }
 519
 520 }