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. Some of them define GC roots:
 105 - visit_roots()
 106 - visit_contexts() */
 107
 108 template <typename Fixup> struct slot_visitor {
 109   factor_vm* parent;
 110   Fixup fixup;
 111
 112   slot_visitor<Fixup>(factor_vm* parent, Fixup fixup)
 113       : parent(parent), fixup(fixup) {}
 114
 115   cell visit_pointer(cell pointer);
 116   void visit_handle(cell* handle);
 117   void visit_object_array(cell* start, cell* end);
 118   void visit_slots(object* ptr, cell payload_start);
 119   void visit_slots(object* ptr);
 120   void visit_stack_elements(segment* region, cell* top);
 121   void visit_data_roots();
 122   void visit_bignum_roots();
 123   void visit_callback_roots();
 124   void visit_literal_table_roots();
 125   void visit_roots();
 126   void visit_callstack_object(callstack* stack);
 127   void visit_callstack(context* ctx);
 128   void visit_context(context *ctx);
 129   void visit_contexts();
 130   void visit_code_block_objects(code_block* compiled);
 131   void visit_embedded_literals(code_block* compiled);
 132   void visit_sample_callstacks();
 133   void visit_sample_threads();
 134 };
 135
 136 template <typename Fixup>
 137 cell slot_visitor<Fixup>::visit_pointer(cell pointer) {
 138   if (immediate_p(pointer))
 139     return pointer;
 140
 141   object* untagged = fixup.fixup_data(untag<object>(pointer));
 142   return RETAG(untagged, TAG(pointer));
 143 }
 144
 145 template <typename Fixup> void slot_visitor<Fixup>::visit_handle(cell* handle) {
 146   *handle = visit_pointer(*handle);
 147 }
 148
 149 template <typename Fixup>
 150 void slot_visitor<Fixup>::visit_object_array(cell* start, cell* end) {
 151   while (start < end)
 152     visit_handle(start++);
 153 }
 154
 155 template <typename Fixup>
 156 void slot_visitor<Fixup>::visit_slots(object* ptr, cell payload_start) {
 157   cell* slot = (cell*)ptr;
 158   cell* end = (cell*)((cell)ptr + payload_start);
 159
 160   if (slot != end) {
 161     slot++;
 162     visit_object_array(slot, end);
 163   }
 164 }
 165
 166 template <typename Fixup> void slot_visitor<Fixup>::visit_slots(object* obj) {
 167   if (obj->type() == CALLSTACK_TYPE)
 168     visit_callstack_object((callstack*)obj);
 169   else
 170     visit_slots(obj, obj->binary_payload_start(fixup));
 171 }
 172
 173 template <typename Fixup>
 174 void slot_visitor<Fixup>::visit_stack_elements(segment* region, cell* top) {
 175   visit_object_array((cell*)region->start, top + 1);
 176 }
 177
 178 template <typename Fixup> void slot_visitor<Fixup>::visit_data_roots() {
 179   std::vector<cell*>::const_iterator iter =
 180       parent->data_roots.begin();
 181   std::vector<cell*>::const_iterator end =
 182       parent->data_roots.end();
 183
 184   for (; iter < end; iter++) {
 185     visit_handle(*iter);
 186   }
 187 }
 188
 189 template <typename Fixup> void slot_visitor<Fixup>::visit_bignum_roots() {
 190   std::vector<bignum**>::const_iterator iter =
 191       parent->bignum_roots.begin();
 192   std::vector<bignum**>::const_iterator end =
 193       parent->bignum_roots.end();
 194
 195   for (; iter < end; iter++) {
 196     bignum** ref = *iter;
 197     *ref = (bignum*)fixup.fixup_data(*ref);
 198   }
 199 }
 200
 201 template <typename Fixup> struct callback_slot_visitor {
 202   callback_heap* callbacks;
 203   slot_visitor<Fixup>* visitor;
 204
 205   callback_slot_visitor(callback_heap* callbacks,
 206                         slot_visitor<Fixup>* visitor)
 207       : callbacks(callbacks), visitor(visitor) {}
 208
 209   void operator()(object* stub) {
 210     code_block *block = (code_block*)stub;
 211     visitor->visit_handle(&block->owner);
 212   }
 213 };
 214
 215 template <typename Fixup> void slot_visitor<Fixup>::visit_callback_roots() {
 216   callback_slot_visitor<Fixup> callback_visitor(parent->callbacks, this);
 217   parent->each_object(parent->callbacks->allocator, callback_visitor);
 218 }
 219
 220 template <typename Fixup>
 221 void slot_visitor<Fixup>::visit_literal_table_roots() {
 222   std::map<code_block*, cell>* uninitialized_blocks =
 223       &parent->code->uninitialized_blocks;
 224   std::map<code_block*, cell>::const_iterator iter =
 225       uninitialized_blocks->begin();
 226   std::map<code_block*, cell>::const_iterator end = uninitialized_blocks->end();
 227
 228   std::map<code_block*, cell> new_uninitialized_blocks;
 229   for (; iter != end; iter++) {
 230     new_uninitialized_blocks.insert(
 231         std::make_pair(iter->first, visit_pointer(iter->second)));
 232   }
 233
 234   parent->code->uninitialized_blocks = new_uninitialized_blocks;
 235 }
 236
 237 template <typename Fixup> void slot_visitor<Fixup>::visit_sample_callstacks() {
 238   for (std::vector<cell>::iterator iter = parent->sample_callstacks.begin();
 239        iter != parent->sample_callstacks.end(); ++iter) {
 240     visit_handle(&*iter);
 241   }
 242 }
 243
 244 template <typename Fixup> void slot_visitor<Fixup>::visit_sample_threads() {
 245   for (std::vector<profiling_sample>::iterator iter = parent->samples.begin();
 246        iter != parent->samples.end(); ++iter) {
 247     visit_handle(&iter->thread);
 248   }
 249 }
 250
 251 template <typename Fixup> void slot_visitor<Fixup>::visit_roots() {
 252   visit_handle(&parent->true_object);
 253   visit_handle(&parent->bignum_zero);
 254   visit_handle(&parent->bignum_pos_one);
 255   visit_handle(&parent->bignum_neg_one);
 256
 257   visit_data_roots();
 258   visit_bignum_roots();
 259   visit_callback_roots();
 260   visit_literal_table_roots();
 261   visit_sample_callstacks();
 262   visit_sample_threads();
 263
 264   visit_object_array(parent->special_objects,
 265                      parent->special_objects + special_object_count);
 266 }
 267
 268 /* primitive_minor_gc() is invoked by inline GC checks, and it needs to fill in
 269    uninitialized stack locations before actually calling the GC. See the
 270    documentation in compiler.cfg.stacks.vacant for details.
 271
 272    So for each call frame:
 273
 274     - scrub some uninitialized locations
 275     - trace some overinitialized locations
 276     - trace roots in spill slots
 277 */
 278 template <typename Fixup> struct call_frame_slot_visitor {
 279   factor_vm* parent;
 280   slot_visitor<Fixup>* visitor;
 281   /* NULL in case we're a visitor for a callstack object. */
 282   context* ctx;
 283
 284   void check_stack(cell stack, uint8_t* bitmap, cell base, uint32_t count) {
 285     for (uint32_t loc = 0; loc < count; loc++) {
 286       if (bitmap_p(bitmap, base + loc)) {
 287 #ifdef DEBUG_GC_MAPS
 288         std::cout << "checking stack location " << loc << std::endl;
 289 #endif
 290         cell* value_ptr = ((cell*)stack + loc + 1);
 291         visitor->visit_handle(value_ptr);
 292       }
 293     }
 294   }
 295
 296   void scrub_stack(cell stack, uint8_t* bitmap, cell base, uint32_t count) {
 297     for (cell loc = 0; loc < count; loc++) {
 298       if (bitmap_p(bitmap, base + loc)) {
 299 #ifdef DEBUG_GC_MAPS
 300         std::cout << "scrubbing stack location " << loc << std::endl;
 301 #endif
 302         *((cell*)stack - loc) = 0;
 303       }
 304     }
 305   }
 306
 307   call_frame_slot_visitor(factor_vm* parent,
 308                           slot_visitor<Fixup>* visitor,
 309                           context* ctx)
 310       : parent(parent), visitor(visitor), ctx(ctx) {}
 311
 312   /*
 313         frame top -> [return address]
 314                      [spill area]
 315                      ...
 316                      [entry_point]
 317                      [size]
 318         */
 319   void operator()(void* frame_top, cell frame_size, code_block* owner,
 320                   void* addr) {
 321     cell return_address = owner->offset(addr);
 322
 323     code_block* compiled =
 324         Fixup::translated_code_block_map ? owner
 325                                          : visitor->fixup.translate_code(owner);
 326     gc_info* info = compiled->block_gc_info();
 327
 328     FACTOR_ASSERT(return_address < compiled->size());
 329     cell callsite = info->return_address_index(return_address);
 330     if (callsite == (cell)-1)
 331       return;
 332
 333 #ifdef DEBUG_GC_MAPS
 334     std::cout << "call frame code block " << compiled << " with offset "
 335               << return_address << std::endl;
 336 #endif
 337     cell* stack_pointer = (cell*)frame_top;
 338     uint8_t* bitmap = info->gc_info_bitmap();
 339
 340     if (ctx) {
 341       /* Scrub vacant stack locations. */
 342       scrub_stack(ctx->datastack,
 343                   bitmap,
 344                   info->callsite_scrub_d(callsite),
 345                   info->scrub_d_count);
 346       scrub_stack(ctx->retainstack,
 347                   bitmap,
 348                   info->callsite_scrub_r(callsite),
 349                   info->scrub_r_count);
 350
 351       /* Trace overinitialized stack locations. */
 352       check_stack(ctx->datastack,
 353                   bitmap,
 354                   info->callsite_check_d(callsite),
 355                   info->check_d_count);
 356       check_stack(ctx->retainstack,
 357                   bitmap,
 358                   info->callsite_check_r(callsite),
 359                   info->check_r_count);
 360     }
 361
 362     /* Subtract old value of base pointer from every derived pointer. */
 363     for (cell spill_slot = 0; spill_slot < info->derived_root_count;
 364          spill_slot++) {
 365       uint32_t base_pointer = info->lookup_base_pointer(callsite, spill_slot);
 366       if (base_pointer != (uint32_t)-1) {
 367 #ifdef DEBUG_GC_MAPS
 368         std::cout << "visiting derived root " << spill_slot
 369                   << " with base pointer " << base_pointer << std::endl;
 370 #endif
 371         stack_pointer[spill_slot] -= stack_pointer[base_pointer];
 372       }
 373     }
 374
 375     /* Update all GC roots, including base pointers. */
 376     cell callsite_gc_roots = info->callsite_gc_roots(callsite);
 377
 378     for (cell spill_slot = 0; spill_slot < info->gc_root_count; spill_slot++) {
 379       if (bitmap_p(bitmap, callsite_gc_roots + spill_slot)) {
 380 #ifdef DEBUG_GC_MAPS
 381         std::cout << "visiting GC root " << spill_slot << std::endl;
 382 #endif
 383         visitor->visit_handle(stack_pointer + spill_slot);
 384       }
 385     }
 386
 387     /* Add the base pointers to obtain new derived pointer values. */
 388     for (cell spill_slot = 0; spill_slot < info->derived_root_count;
 389          spill_slot++) {
 390       uint32_t base_pointer = info->lookup_base_pointer(callsite, spill_slot);
 391       if (base_pointer != (uint32_t)-1)
 392         stack_pointer[spill_slot] += stack_pointer[base_pointer];
 393     }
 394   }
 395 };
 396
 397 template <typename Fixup>
 398 void slot_visitor<Fixup>::visit_callstack_object(callstack* stack) {
 399   call_frame_slot_visitor<Fixup> call_frame_visitor(parent, this, NULL);
 400   parent->iterate_callstack_object(stack, call_frame_visitor, fixup);
 401 }
 402
 403 template <typename Fixup>
 404 void slot_visitor<Fixup>::visit_callstack(context* ctx) {
 405   call_frame_slot_visitor<Fixup> call_frame_visitor(parent, this, ctx);
 406   parent->iterate_callstack(ctx, call_frame_visitor, fixup);
 407 }
 408
 409 template <typename Fixup>
 410 void slot_visitor<Fixup>::visit_context(context* ctx) {
 411   /* Callstack is visited first because it scrubs the data and retain
 412      stacks. */
 413   visit_callstack(ctx);
 414
 415   visit_stack_elements(ctx->datastack_seg, (cell*)ctx->datastack);
 416   visit_stack_elements(ctx->retainstack_seg, (cell*)ctx->retainstack);
 417   visit_object_array(ctx->context_objects,
 418                      ctx->context_objects + context_object_count);
 419
 420 }
 421
 422 template <typename Fixup> void slot_visitor<Fixup>::visit_contexts() {
 423   std::set<context*>::const_iterator begin = parent->active_contexts.begin();
 424   std::set<context*>::const_iterator end = parent->active_contexts.end();
 425   while (begin != end) {
 426     visit_context(*begin);
 427     begin++;
 428   }
 429 }
 430
 431 template <typename Fixup> struct literal_references_visitor {
 432   slot_visitor<Fixup>* visitor;
 433
 434   explicit literal_references_visitor(slot_visitor<Fixup>* visitor)
 435       : visitor(visitor) {}
 436
 437   void operator()(instruction_operand op) {
 438     if (op.rel_type() == RT_LITERAL)
 439       op.store_value(visitor->visit_pointer(op.load_value()));
 440   }
 441 };
 442
 443 template <typename Fixup>
 444 void slot_visitor<Fixup>::visit_code_block_objects(code_block* compiled) {
 445   visit_handle(&compiled->owner);
 446   visit_handle(&compiled->parameters);
 447   visit_handle(&compiled->relocation);
 448 }
 449
 450 template <typename Fixup>
 451 void slot_visitor<Fixup>::visit_embedded_literals(code_block* compiled) {
 452   if (!parent->code->uninitialized_p(compiled)) {
 453     literal_references_visitor<Fixup> visitor(this);
 454     compiled->each_instruction_operand(visitor);
 455   }
 456 }
 457
 458 }