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_slots(object* ptr);
 131   void visit_stack_elements(segment* region, cell* top);
 132   void visit_all_roots();
 133   void visit_callstack_object(callstack* stack);
 134   void visit_callstack(context* ctx);
 135   void visit_context(context *ctx);
 136   void visit_code_block_objects(code_block* compiled);
 137   void visit_embedded_literals(code_block* compiled);
 138   void visit_object_code_block(object* obj);
 139   void visit_context_code_blocks();
 140   void visit_uninitialized_code_blocks();
 141   void visit_embedded_code_pointers(code_block* compiled);
 142   void visit_object(object* obj);
 143   void visit_mark_stack(std::vector<cell>* mark_stack);
 144 };
 145
 146 template <typename Fixup>
 147 cell slot_visitor<Fixup>::visit_pointer(cell pointer) {
 148   if (immediate_p(pointer))
 149     return pointer;
 150
 151   object* untagged = fixup.fixup_data(untag<object>(pointer));
 152   return RETAG(untagged, TAG(pointer));
 153 }
 154
 155 template <typename Fixup> void slot_visitor<Fixup>::visit_handle(cell* handle) {
 156   *handle = visit_pointer(*handle);
 157 }
 158
 159 template <typename Fixup>
 160 void slot_visitor<Fixup>::visit_object_array(cell* start, cell* end) {
 161   while (start < end)
 162     visit_handle(start++);
 163 }
 164
 165 template <typename Fixup> void slot_visitor<Fixup>::visit_slots(object* obj) {
 166   if (obj->type() == CALLSTACK_TYPE)
 167     visit_callstack_object((callstack*)obj);
 168   else {
 169     cell* start = (cell*)obj + 1;
 170     cell* end = start + obj->slot_count(fixup);
 171     visit_object_array(start, end);
 172   }
 173 }
 174
 175 template <typename Fixup>
 176 void slot_visitor<Fixup>::visit_stack_elements(segment* region, cell* top) {
 177   visit_object_array((cell*)region->start, top + 1);
 178 }
 179
 180 template <typename Fixup> void slot_visitor<Fixup>::visit_all_roots() {
 181   visit_handle(&parent->true_object);
 182   visit_handle(&parent->bignum_zero);
 183   visit_handle(&parent->bignum_pos_one);
 184   visit_handle(&parent->bignum_neg_one);
 185
 186   FACTOR_FOR_EACH(parent->data_roots) {
 187     visit_handle(*iter);
 188   }
 189
 190   auto callback_slot_visitor = [&](code_block* stub, cell size) {
 191     visit_handle(&stub->owner);
 192   };
 193   parent->callbacks->allocator->iterate(callback_slot_visitor);
 194
 195   FACTOR_FOR_EACH(parent->code->uninitialized_blocks) {
 196     iter->second = visit_pointer(iter->second);
 197   }
 198
 199   FACTOR_FOR_EACH(parent->sample_callstacks) {
 200     visit_handle(&*iter);
 201   }
 202
 203   FACTOR_FOR_EACH(parent->samples) {
 204     visit_handle(&iter->thread);
 205   }
 206
 207   visit_object_array(parent->special_objects,
 208                      parent->special_objects + special_object_count);
 209
 210   FACTOR_FOR_EACH(parent->active_contexts) {
 211     visit_context(*iter);
 212   }
 213 }
 214
 215 /* primitive_minor_gc() is invoked by inline GC checks, and it needs to fill in
 216    uninitialized stack locations before actually calling the GC. See the
 217    documentation in compiler.cfg.stacks.vacant for details.
 218
 219    So for each call frame:
 220
 221     - scrub some uninitialized locations
 222     - trace roots in spill slots
 223 */
 224 template <typename Fixup> struct call_frame_slot_visitor {
 225   slot_visitor<Fixup>* visitor;
 226   /* NULL in case we're a visitor for a callstack object. */
 227   context* ctx;
 228
 229   void scrub_stack(cell stack, uint8_t* bitmap, cell base, uint32_t count) {
 230     for (cell loc = 0; loc < count; loc++) {
 231       if (bitmap_p(bitmap, base + loc)) {
 232 #ifdef DEBUG_GC_MAPS
 233         FACTOR_PRINT("scrubbing stack location " << loc);
 234 #endif
 235         *((cell*)stack - loc) = 0;
 236       }
 237     }
 238   }
 239
 240   call_frame_slot_visitor(slot_visitor<Fixup>* visitor, context* ctx)
 241       : visitor(visitor), ctx(ctx) {}
 242
 243   /*
 244         frame top -> [return address]
 245                      [spill area]
 246                      ...
 247                      [entry_point]
 248                      [size]
 249         */
 250   void operator()(cell frame_top, cell size, code_block* owner, cell addr) {
 251     cell return_address = owner->offset(addr);
 252
 253     code_block* compiled =
 254         Fixup::translated_code_block_map ? owner
 255                                          : visitor->fixup.translate_code(owner);
 256     gc_info* info = compiled->block_gc_info();
 257
 258     FACTOR_ASSERT(return_address < compiled->size());
 259     cell callsite = info->return_address_index(return_address);
 260     if (callsite == (cell)-1)
 261       return;
 262
 263 #ifdef DEBUG_GC_MAPS
 264     FACTOR_PRINT("call frame code block " << compiled << " with offset "
 265                  << return_address);
 266 #endif
 267     cell* stack_pointer = (cell*)frame_top;
 268     uint8_t* bitmap = info->gc_info_bitmap();
 269
 270     if (ctx) {
 271       /* Scrub vacant stack locations. */
 272       scrub_stack(ctx->datastack,
 273                   bitmap,
 274                   info->callsite_scrub_d(callsite),
 275                   info->scrub_d_count);
 276       scrub_stack(ctx->retainstack,
 277                   bitmap,
 278                   info->callsite_scrub_r(callsite),
 279                   info->scrub_r_count);
 280     }
 281
 282     /* Subtract old value of base pointer from every derived pointer. */
 283     for (cell spill_slot = 0; spill_slot < info->derived_root_count;
 284          spill_slot++) {
 285       uint32_t base_pointer = info->lookup_base_pointer(callsite, spill_slot);
 286       if (base_pointer != (uint32_t)-1) {
 287 #ifdef DEBUG_GC_MAPS
 288         FACTOR_PRINT("visiting derived root " << spill_slot
 289                      << " with base pointer " << base_pointer);
 290 #endif
 291         stack_pointer[spill_slot] -= stack_pointer[base_pointer];
 292       }
 293     }
 294
 295     /* Update all GC roots, including base pointers. */
 296     cell callsite_gc_roots = info->callsite_gc_roots(callsite);
 297
 298     for (cell spill_slot = 0; spill_slot < info->gc_root_count; spill_slot++) {
 299       if (bitmap_p(bitmap, callsite_gc_roots + spill_slot)) {
 300 #ifdef DEBUG_GC_MAPS
 301         FACTOR_PRINT("visiting GC root " << spill_slot);
 302 #endif
 303         visitor->visit_handle(stack_pointer + spill_slot);
 304       }
 305     }
 306
 307     /* Add the base pointers to obtain new derived pointer values. */
 308     for (cell spill_slot = 0; spill_slot < info->derived_root_count;
 309          spill_slot++) {
 310       uint32_t base_pointer = info->lookup_base_pointer(callsite, spill_slot);
 311       if (base_pointer != (uint32_t)-1)
 312         stack_pointer[spill_slot] += stack_pointer[base_pointer];
 313     }
 314   }
 315 };
 316
 317 template <typename Fixup>
 318 void slot_visitor<Fixup>::visit_callstack_object(callstack* stack) {
 319   call_frame_slot_visitor<Fixup> call_frame_visitor(this, NULL);
 320   parent->iterate_callstack_object(stack, call_frame_visitor, fixup);
 321 }
 322
 323 template <typename Fixup>
 324 void slot_visitor<Fixup>::visit_callstack(context* ctx) {
 325   call_frame_slot_visitor<Fixup> call_frame_visitor(this, ctx);
 326   parent->iterate_callstack(ctx, call_frame_visitor, fixup);
 327 }
 328
 329 template <typename Fixup>
 330 void slot_visitor<Fixup>::visit_context(context* ctx) {
 331   /* Callstack is visited first because it scrubs the data and retain
 332      stacks. */
 333   visit_callstack(ctx);
 334
 335   cell ds_ptr = ctx->datastack;
 336   cell rs_ptr = ctx->retainstack;
 337   segment* ds_seg = ctx->datastack_seg;
 338   segment* rs_seg = ctx->retainstack_seg;
 339   visit_stack_elements(ds_seg, (cell*)ds_ptr);
 340   visit_stack_elements(rs_seg, (cell*)rs_ptr);
 341   visit_object_array(ctx->context_objects,
 342                      ctx->context_objects + context_object_count);
 343
 344   /* Clear out the space not visited with a known pattern. That makes
 345      it easier to see if uninitialized reads are made. */
 346   ctx->fill_stack_seg(ds_ptr, ds_seg, 0xbaadbadd);
 347   ctx->fill_stack_seg(rs_ptr, rs_seg, 0xdaabdaab);
 348 }
 349
 350 template <typename Fixup>
 351 void slot_visitor<Fixup>::visit_code_block_objects(code_block* compiled) {
 352   visit_handle(&compiled->owner);
 353   visit_handle(&compiled->parameters);
 354   visit_handle(&compiled->relocation);
 355 }
 356
 357 template <typename Fixup>
 358 void slot_visitor<Fixup>::visit_embedded_literals(code_block* compiled) {
 359   if (parent->code->uninitialized_p(compiled))
 360     return;
 361
 362   auto update_literal_refs = [&](instruction_operand op) {
 363     if (op.rel_type() == RT_LITERAL)
 364       op.store_value(visit_pointer(op.load_value()));
 365   };
 366   compiled->each_instruction_operand(update_literal_refs);
 367 }
 368
 369 template <typename Fixup> struct call_frame_code_block_visitor {
 370   Fixup fixup;
 371
 372   call_frame_code_block_visitor(Fixup fixup)
 373       : fixup(fixup) {}
 374
 375   void operator()(cell frame_top, cell size, code_block* owner, cell addr) {
 376     code_block* compiled =
 377         Fixup::translated_code_block_map ? owner : fixup.fixup_code(owner);
 378     cell fixed_addr = compiled->address_for_offset(owner->offset(addr));
 379
 380     *(cell*)frame_top = fixed_addr;
 381   }
 382 };
 383
 384 template <typename Fixup>
 385 void slot_visitor<Fixup>::visit_object_code_block(object* obj) {
 386   switch (obj->type()) {
 387     case WORD_TYPE: {
 388       word* w = (word*)obj;
 389       if (w->entry_point)
 390         w->entry_point = fixup.fixup_code(w->code())->entry_point();
 391       break;
 392     }
 393     case QUOTATION_TYPE: {
 394       quotation* q = (quotation*)obj;
 395       if (q->entry_point)
 396         q->entry_point = fixup.fixup_code(q->code())->entry_point();
 397       break;
 398     }
 399     case CALLSTACK_TYPE: {
 400       callstack* stack = (callstack*)obj;
 401       call_frame_code_block_visitor<Fixup> call_frame_visitor(fixup);
 402       parent->iterate_callstack_object(stack, call_frame_visitor, fixup);
 403       break;
 404     }
 405   }
 406 }
 407
 408 template <typename Fixup>
 409 void slot_visitor<Fixup>::visit_context_code_blocks() {
 410   call_frame_code_block_visitor<Fixup> call_frame_visitor(fixup);
 411   FACTOR_FOR_EACH(parent->active_contexts) {
 412     parent->iterate_callstack(*iter, call_frame_visitor, fixup);
 413   }
 414 }
 415
 416 template <typename Fixup>
 417 void slot_visitor<Fixup>::visit_uninitialized_code_blocks() {
 418   std::map<code_block*, cell> new_uninitialized_blocks;
 419   FACTOR_FOR_EACH(parent->code->uninitialized_blocks) {
 420     new_uninitialized_blocks.insert(
 421         std::make_pair(fixup.fixup_code(iter->first), iter->second));
 422   }
 423   parent->code->uninitialized_blocks = new_uninitialized_blocks;
 424 }
 425
 426 template <typename Fixup>
 427 void slot_visitor<Fixup>::visit_embedded_code_pointers(code_block* compiled) {
 428   if (parent->code->uninitialized_p(compiled))
 429     return;
 430   auto update_code_block_refs = [&](instruction_operand op){
 431     relocation_type type = op.rel_type();
 432     if (type == RT_ENTRY_POINT ||
 433         type == RT_ENTRY_POINT_PIC ||
 434         type == RT_ENTRY_POINT_PIC_TAIL)
 435       op.store_code_block(fixup.fixup_code(op.load_code_block()));
 436   };
 437   compiled->each_instruction_operand(update_code_block_refs);
 438 }
 439
 440 template <typename Fixup>
 441 void slot_visitor<Fixup>::visit_object(object *ptr) {
 442   visit_slots(ptr);
 443   if (ptr->type() == ALIEN_TYPE)
 444     ((alien*)ptr)->update_address();
 445 }
 446
 447 /* Pops items from the mark stack and visits them until the stack is
 448    empty. Used when doing a full collection and when collecting to
 449    tenured space. */
 450 template <typename Fixup>
 451 void slot_visitor<Fixup>::visit_mark_stack(std::vector<cell>* mark_stack) {
 452   while (!mark_stack->empty()) {
 453     cell ptr = mark_stack->back();
 454     mark_stack->pop_back();
 455
 456     if (ptr & 1) {
 457       code_block* compiled = (code_block*)(ptr - 1);
 458       visit_code_block_objects(compiled);
 459       visit_embedded_literals(compiled);
 460       visit_embedded_code_pointers(compiled);
 461     } else {
 462       object* obj = (object*)ptr;
 463       visit_object(obj);
 464       visit_object_code_block(obj);
 465     }
 466   }
 467 }
 468
 469 }