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