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