vm/slot_visitor.hpp

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