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       return callstack_object_size(untag_fixnum(((callstack*)this)->length));
  34     }
  35     default:
  36       critical_error("Invalid header in base_size", (cell)this);
  37       return 0;
  38   }
  39 }
  40
  41 /* Size of the object pointed to by an untagged pointer */
  42 template <typename Fixup>
  43 cell object::size(Fixup fixup) const {
  44   if (free_p())
  45     return ((free_heap_block*)this)->size();
  46   return align(base_size(fixup), data_alignment);
  47 }
  48
  49 inline cell object::size() const { return size(no_fixup()); }
  50
  51 /* The number of slots (cells) in an object which should be scanned by
  52    the GC. The number can vary in arrays and tuples, in all other
  53    types the number is a constant. */
  54 template <typename Fixup>
  55 inline cell object::slot_count(Fixup fixup) const {
  56   if (free_p())
  57     return 0;
  58
  59   cell t = type();
  60   if (t == ARRAY_TYPE) {
  61     /* capacity + n slots */
  62     return 1 + array_capacity((array*)this);
  63   } else if (t == TUPLE_TYPE) {
  64     tuple_layout* layout = (tuple_layout*)fixup.translate_data(
  65         untag<object>(((tuple*)this)->layout));
  66     /* layout + n slots */
  67     return 1 + tuple_capacity(layout);
  68   } else {
  69     switch (t) {
  70       /* these objects do not refer to other objects at all */
  71       case FLOAT_TYPE:
  72       case BYTE_ARRAY_TYPE:
  73       case BIGNUM_TYPE:
  74       case CALLSTACK_TYPE: return 0;
  75       case WORD_TYPE: return 8;
  76       case ALIEN_TYPE: return 2;
  77       case DLL_TYPE: return 1;
  78       case QUOTATION_TYPE: return 3;
  79       case STRING_TYPE: return 3;
  80       case WRAPPER_TYPE: return 1;
  81       default:
  82         critical_error("Invalid header in slot_count", (cell)this);
  83         return 0; /* can't happen */
  84     }
  85   }
  86 }
  87
  88 inline cell object::slot_count() const {
  89   return slot_count(no_fixup());
  90 }
  91
  92 /* Slot visitors iterate over the slots of an object, applying a functor to
  93 each one that is a non-immediate slot. The pointer is untagged first. The
  94 functor returns a new untagged object pointer. The return value may or may not
  95 equal the old one,
  96 however the new pointer receives the same tag before being stored back to the
  97 original location.
  98
  99 Slots storing immediate values are left unchanged and the visitor does inspect
 100 them.
 101
 102 This is used by GC's copying, sweep and compact phases, and the implementation
 103 of the become primitive.
 104
 105 Iteration is driven by visit_*() methods. Only one of them define GC roots:
 106 - visit_all_roots()
 107
 108 Code block visitors iterate over sets of code blocks, applying a functor to
 109 each one. The functor returns a new code_block pointer, which may or may not
 110 equal the old one. This is stored back to the original location.
 111
 112 This is used by GC's sweep and compact phases, and the implementation of the
 113 modify-code-heap primitive.
 114
 115 Iteration is driven by visit_*() methods. Some of them define GC roots:
 116 - visit_context_code_blocks()
 117 - visit_callback_code_blocks() */
 118
 119 template <typename Fixup> struct slot_visitor {
 120   factor_vm* parent;
 121   Fixup fixup;
 122
 123   slot_visitor<Fixup>(factor_vm* parent, Fixup fixup)
 124       : parent(parent), fixup(fixup) {}
 125
 126   cell visit_pointer(cell pointer);
 127   void visit_handle(cell* handle);
 128   void visit_object_array(cell* start, cell* end);
 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> void slot_visitor<Fixup>::visit_slots(object* obj) {
 171   if (obj->type() == CALLSTACK_TYPE)
 172     visit_callstack_object((callstack*)obj);
 173   else {
 174     cell* start = (cell*)obj + 1;
 175     cell* end = start + obj->slot_count(fixup);
 176     visit_object_array(start, end);
 177   }
 178 }
 179
 180 template <typename Fixup>
 181 void slot_visitor<Fixup>::visit_stack_elements(segment* region, cell* top) {
 182   visit_object_array((cell*)region->start, top + 1);
 183 }
 184
 185 template <typename Fixup> void slot_visitor<Fixup>::visit_data_roots() {
 186   FACTOR_FOR_EACH(parent->data_roots) {
 187     visit_handle(*iter);
 188   }
 189 }
 190
 191 template <typename Fixup> void slot_visitor<Fixup>::visit_callback_roots() {
 192   auto callback_slot_visitor = [&](code_block* stub, cell size) {
 193     visit_handle(&stub->owner);
 194   };
 195   parent->callbacks->allocator->iterate(callback_slot_visitor);
 196 }
 197
 198 template <typename Fixup>
 199 void slot_visitor<Fixup>::visit_literal_table_roots() {
 200   FACTOR_FOR_EACH(parent->code->uninitialized_blocks) {
 201     iter->second = visit_pointer(iter->second);
 202   }
 203 }
 204
 205 template <typename Fixup> void slot_visitor<Fixup>::visit_sample_callstacks() {
 206   FACTOR_FOR_EACH(parent->sample_callstacks) {
 207     visit_handle(&*iter);
 208   }
 209 }
 210
 211 template <typename Fixup> void slot_visitor<Fixup>::visit_sample_threads() {
 212   FACTOR_FOR_EACH(parent->samples) {
 213     visit_handle(&iter->thread);
 214   }
 215 }
 216
 217 template <typename Fixup> void slot_visitor<Fixup>::visit_all_roots() {
 218   visit_handle(&parent->true_object);
 219   visit_handle(&parent->bignum_zero);
 220   visit_handle(&parent->bignum_pos_one);
 221   visit_handle(&parent->bignum_neg_one);
 222
 223   visit_data_roots();
 224   visit_callback_roots();
 225   visit_literal_table_roots();
 226   visit_sample_callstacks();
 227   visit_sample_threads();
 228
 229   visit_object_array(parent->special_objects,
 230                      parent->special_objects + special_object_count);
 231
 232   visit_contexts();
 233 }
 234
 235 /* primitive_minor_gc() is invoked by inline GC checks, and it needs to fill in
 236    uninitialized stack locations before actually calling the GC. See the
 237    documentation in compiler.cfg.stacks.vacant for details.
 238
 239    So for each call frame:
 240
 241     - scrub some uninitialized locations
 242     - trace roots in spill slots
 243 */
 244 template <typename Fixup> struct call_frame_slot_visitor {
 245   slot_visitor<Fixup>* visitor;
 246   /* NULL in case we're a visitor for a callstack object. */
 247   context* ctx;
 248
 249   void scrub_stack(cell stack, uint8_t* bitmap, cell base, uint32_t count) {
 250     for (cell loc = 0; loc < count; loc++) {
 251       if (bitmap_p(bitmap, base + loc)) {
 252 #ifdef DEBUG_GC_MAPS
 253         FACTOR_PRINT("scrubbing stack location " << loc);
 254 #endif
 255         *((cell*)stack - loc) = 0;
 256       }
 257     }
 258   }
 259
 260   call_frame_slot_visitor(slot_visitor<Fixup>* visitor, context* ctx)
 261       : visitor(visitor), ctx(ctx) {}
 262
 263   /*
 264         frame top -> [return address]
 265                      [spill area]
 266                      ...
 267                      [entry_point]
 268                      [size]
 269         */
 270   void operator()(cell frame_top, cell size, code_block* owner, cell addr) {
 271     cell return_address = owner->offset(addr);
 272
 273     code_block* compiled =
 274         Fixup::translated_code_block_map ? owner
 275                                          : visitor->fixup.translate_code(owner);
 276     gc_info* info = compiled->block_gc_info();
 277
 278     FACTOR_ASSERT(return_address < compiled->size());
 279     cell callsite = info->return_address_index(return_address);
 280     if (callsite == (cell)-1)
 281       return;
 282
 283 #ifdef DEBUG_GC_MAPS
 284     FACTOR_PRINT("call frame code block " << compiled << " with offset "
 285                  << return_address);
 286 #endif
 287     cell* stack_pointer = (cell*)frame_top;
 288     uint8_t* bitmap = info->gc_info_bitmap();
 289
 290     if (ctx) {
 291       /* Scrub vacant stack locations. */
 292       scrub_stack(ctx->datastack,
 293                   bitmap,
 294                   info->callsite_scrub_d(callsite),
 295                   info->scrub_d_count);
 296       scrub_stack(ctx->retainstack,
 297                   bitmap,
 298                   info->callsite_scrub_r(callsite),
 299                   info->scrub_r_count);
 300     }
 301
 302     /* Subtract old value of base pointer from every derived pointer. */
 303     for (cell spill_slot = 0; spill_slot < info->derived_root_count;
 304          spill_slot++) {
 305       uint32_t base_pointer = info->lookup_base_pointer(callsite, spill_slot);
 306       if (base_pointer != (uint32_t)-1) {
 307 #ifdef DEBUG_GC_MAPS
 308         FACTOR_PRINT("visiting derived root " << spill_slot
 309                      << " with base pointer " << base_pointer);
 310 #endif
 311         stack_pointer[spill_slot] -= stack_pointer[base_pointer];
 312       }
 313     }
 314
 315     /* Update all GC roots, including base pointers. */
 316     cell callsite_gc_roots = info->callsite_gc_roots(callsite);
 317
 318     for (cell spill_slot = 0; spill_slot < info->gc_root_count; spill_slot++) {
 319       if (bitmap_p(bitmap, callsite_gc_roots + spill_slot)) {
 320 #ifdef DEBUG_GC_MAPS
 321         FACTOR_PRINT("visiting GC root " << spill_slot);
 322 #endif
 323         visitor->visit_handle(stack_pointer + spill_slot);
 324       }
 325     }
 326
 327     /* Add the base pointers to obtain new derived pointer values. */
 328     for (cell spill_slot = 0; spill_slot < info->derived_root_count;
 329          spill_slot++) {
 330       uint32_t base_pointer = info->lookup_base_pointer(callsite, spill_slot);
 331       if (base_pointer != (uint32_t)-1)
 332         stack_pointer[spill_slot] += stack_pointer[base_pointer];
 333     }
 334   }
 335 };
 336
 337 template <typename Fixup>
 338 void slot_visitor<Fixup>::visit_callstack_object(callstack* stack) {
 339   call_frame_slot_visitor<Fixup> call_frame_visitor(this, NULL);
 340   parent->iterate_callstack_object(stack, call_frame_visitor, fixup);
 341 }
 342
 343 template <typename Fixup>
 344 void slot_visitor<Fixup>::visit_callstack(context* ctx) {
 345   call_frame_slot_visitor<Fixup> call_frame_visitor(this, ctx);
 346   parent->iterate_callstack(ctx, call_frame_visitor, fixup);
 347 }
 348
 349 template <typename Fixup>
 350 void slot_visitor<Fixup>::visit_context(context* ctx) {
 351   /* Callstack is visited first because it scrubs the data and retain
 352      stacks. */
 353   visit_callstack(ctx);
 354
 355   cell ds_ptr = ctx->datastack;
 356   cell rs_ptr = ctx->retainstack;
 357   segment* ds_seg = ctx->datastack_seg;
 358   segment* rs_seg = ctx->retainstack_seg;
 359   visit_stack_elements(ds_seg, (cell*)ds_ptr);
 360   visit_stack_elements(rs_seg, (cell*)rs_ptr);
 361   visit_object_array(ctx->context_objects,
 362                      ctx->context_objects + context_object_count);
 363
 364   /* Clear out the space not visited with a known pattern. That makes
 365      it easier to see if uninitialized reads are made. */
 366   ctx->fill_stack_seg(ds_ptr, ds_seg, 0xbaadbadd);
 367   ctx->fill_stack_seg(rs_ptr, rs_seg, 0xdaabdaab);
 368 }
 369
 370 template <typename Fixup> void slot_visitor<Fixup>::visit_contexts() {
 371   FACTOR_FOR_EACH(parent->active_contexts) {
 372     visit_context(*iter);
 373   }
 374 }
 375
 376 template <typename Fixup>
 377 void slot_visitor<Fixup>::visit_code_block_objects(code_block* compiled) {
 378   visit_handle(&compiled->owner);
 379   visit_handle(&compiled->parameters);
 380   visit_handle(&compiled->relocation);
 381 }
 382
 383 template <typename Fixup>
 384 void slot_visitor<Fixup>::visit_embedded_literals(code_block* compiled) {
 385   if (parent->code->uninitialized_p(compiled))
 386     return;
 387
 388   auto update_literal_refs = [&](instruction_operand op) {
 389     if (op.rel_type() == RT_LITERAL)
 390       op.store_value(visit_pointer(op.load_value()));
 391   };
 392   compiled->each_instruction_operand(update_literal_refs);
 393 }
 394
 395 template <typename Fixup> struct call_frame_code_block_visitor {
 396   Fixup fixup;
 397
 398   call_frame_code_block_visitor(Fixup fixup)
 399       : fixup(fixup) {}
 400
 401   void operator()(cell frame_top, cell size, code_block* owner, cell addr) {
 402     code_block* compiled =
 403         Fixup::translated_code_block_map ? owner : fixup.fixup_code(owner);
 404     cell fixed_addr = compiled->address_for_offset(owner->offset(addr));
 405
 406     *(cell*)frame_top = fixed_addr;
 407   }
 408 };
 409
 410 template <typename Fixup>
 411 void slot_visitor<Fixup>::visit_object_code_block(object* obj) {
 412   switch (obj->type()) {
 413     case WORD_TYPE: {
 414       word* w = (word*)obj;
 415       if (w->entry_point)
 416         w->entry_point = fixup.fixup_code(w->code())->entry_point();
 417       break;
 418     }
 419     case QUOTATION_TYPE: {
 420       quotation* q = (quotation*)obj;
 421       if (q->entry_point)
 422         q->entry_point = fixup.fixup_code(q->code())->entry_point();
 423       break;
 424     }
 425     case CALLSTACK_TYPE: {
 426       callstack* stack = (callstack*)obj;
 427       call_frame_code_block_visitor<Fixup> call_frame_visitor(fixup);
 428       parent->iterate_callstack_object(stack, call_frame_visitor, fixup);
 429       break;
 430     }
 431   }
 432 }
 433
 434 template <typename Fixup>
 435 void slot_visitor<Fixup>::visit_context_code_blocks() {
 436   call_frame_code_block_visitor<Fixup> call_frame_visitor(fixup);
 437   FACTOR_FOR_EACH(parent->active_contexts) {
 438     parent->iterate_callstack(*iter, call_frame_visitor, fixup);
 439   }
 440 }
 441
 442 template <typename Fixup>
 443 void slot_visitor<Fixup>::visit_uninitialized_code_blocks() {
 444   std::map<code_block*, cell> new_uninitialized_blocks;
 445   FACTOR_FOR_EACH(parent->code->uninitialized_blocks) {
 446     new_uninitialized_blocks.insert(
 447         std::make_pair(fixup.fixup_code(iter->first), iter->second));
 448   }
 449   parent->code->uninitialized_blocks = new_uninitialized_blocks;
 450 }
 451
 452 template <typename Fixup>
 453 void slot_visitor<Fixup>::visit_embedded_code_pointers(code_block* compiled) {
 454   if (parent->code->uninitialized_p(compiled))
 455     return;
 456   auto update_code_block_refs = [&](instruction_operand op){
 457     relocation_type type = op.rel_type();
 458     if (type == RT_ENTRY_POINT ||
 459         type == RT_ENTRY_POINT_PIC ||
 460         type == RT_ENTRY_POINT_PIC_TAIL)
 461       op.store_code_block(fixup.fixup_code(op.load_code_block()));
 462   };
 463   compiled->each_instruction_operand(update_code_block_refs);
 464 }
 465
 466 template <typename Fixup>
 467 void slot_visitor<Fixup>::visit_object(object *ptr) {
 468   visit_slots(ptr);
 469   if (ptr->type() == ALIEN_TYPE)
 470     ((alien*)ptr)->update_address();
 471 }
 472
 473 /* Pops items from the mark stack and visits them until the stack is
 474    empty. Used when doing a full collection and when collecting to
 475    tenured space. */
 476 template <typename Fixup>
 477 void slot_visitor<Fixup>::visit_mark_stack(std::vector<cell>* mark_stack) {
 478   while (!mark_stack->empty()) {
 479     cell ptr = mark_stack->back();
 480     mark_stack->pop_back();
 481
 482     if (ptr & 1) {
 483       code_block* compiled = (code_block*)(ptr - 1);
 484       visit_code_block_objects(compiled);
 485       visit_embedded_literals(compiled);
 486       visit_embedded_code_pointers(compiled);
 487     } else {
 488       object* obj = (object*)ptr;
 489       visit_object(obj);
 490       visit_object_code_block(obj);
 491     }
 492   }
 493 }
 494
 495 }