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   slot_visitor<Fixup>* visitor;
 203
 204   callback_slot_visitor(slot_visitor<Fixup>* visitor) : visitor(visitor) {}
 205
 206   void operator()(code_block* stub, cell size) {
 207     visitor->visit_handle(&stub->owner);
 208   }
 209 };
 210
 211 template <typename Fixup> void slot_visitor<Fixup>::visit_callback_roots() {
 212   callback_slot_visitor<Fixup> callback_visitor(this);
 213   parent->callbacks->allocator->iterate(callback_visitor);
 214 }
 215
 216 template <typename Fixup>
 217 void slot_visitor<Fixup>::visit_literal_table_roots() {
 218   std::map<code_block*, cell>* uninitialized_blocks =
 219       &parent->code->uninitialized_blocks;
 220   std::map<code_block*, cell>::const_iterator iter =
 221       uninitialized_blocks->begin();
 222   std::map<code_block*, cell>::const_iterator end = uninitialized_blocks->end();
 223
 224   std::map<code_block*, cell> new_uninitialized_blocks;
 225   for (; iter != end; iter++) {
 226     new_uninitialized_blocks.insert(
 227         std::make_pair(iter->first, visit_pointer(iter->second)));
 228   }
 229
 230   parent->code->uninitialized_blocks = new_uninitialized_blocks;
 231 }
 232
 233 template <typename Fixup> void slot_visitor<Fixup>::visit_sample_callstacks() {
 234   for (std::vector<cell>::iterator iter = parent->sample_callstacks.begin();
 235        iter != parent->sample_callstacks.end(); ++iter) {
 236     visit_handle(&*iter);
 237   }
 238 }
 239
 240 template <typename Fixup> void slot_visitor<Fixup>::visit_sample_threads() {
 241   for (std::vector<profiling_sample>::iterator iter = parent->samples.begin();
 242        iter != parent->samples.end(); ++iter) {
 243     visit_handle(&iter->thread);
 244   }
 245 }
 246
 247 template <typename Fixup> void slot_visitor<Fixup>::visit_roots() {
 248   visit_handle(&parent->true_object);
 249   visit_handle(&parent->bignum_zero);
 250   visit_handle(&parent->bignum_pos_one);
 251   visit_handle(&parent->bignum_neg_one);
 252
 253   visit_data_roots();
 254   visit_bignum_roots();
 255   visit_callback_roots();
 256   visit_literal_table_roots();
 257   visit_sample_callstacks();
 258   visit_sample_threads();
 259
 260   visit_object_array(parent->special_objects,
 261                      parent->special_objects + special_object_count);
 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 some overinitialized locations
 272     - trace roots in spill slots
 273 */
 274 template <typename Fixup> struct call_frame_slot_visitor {
 275   factor_vm* parent;
 276   slot_visitor<Fixup>* visitor;
 277   /* NULL in case we're a visitor for a callstack object. */
 278   context* ctx;
 279
 280   void check_stack(cell stack, uint8_t* bitmap, cell base, uint32_t count) {
 281     for (uint32_t loc = 0; loc < count; loc++) {
 282       if (bitmap_p(bitmap, base + loc)) {
 283 #ifdef DEBUG_GC_MAPS
 284         std::cout << "checking stack location " << loc << std::endl;
 285 #endif
 286         cell* value_ptr = ((cell*)stack + loc + 1);
 287         visitor->visit_handle(value_ptr);
 288       }
 289     }
 290   }
 291
 292   void scrub_stack(cell stack, uint8_t* bitmap, cell base, uint32_t count) {
 293     for (cell loc = 0; loc < count; loc++) {
 294       if (bitmap_p(bitmap, base + loc)) {
 295 #ifdef DEBUG_GC_MAPS
 296         std::cout << "scrubbing stack location " << loc << std::endl;
 297 #endif
 298         *((cell*)stack - loc) = 0;
 299       }
 300     }
 301   }
 302
 303   call_frame_slot_visitor(factor_vm* parent,
 304                           slot_visitor<Fixup>* visitor,
 305                           context* ctx)
 306       : parent(parent), visitor(visitor), ctx(ctx) {}
 307
 308   /*
 309         frame top -> [return address]
 310                      [spill area]
 311                      ...
 312                      [entry_point]
 313                      [size]
 314         */
 315   void operator()(void* frame_top, cell frame_size, code_block* owner,
 316                   void* addr) {
 317     cell return_address = owner->offset(addr);
 318
 319     code_block* compiled =
 320         Fixup::translated_code_block_map ? owner
 321                                          : visitor->fixup.translate_code(owner);
 322     gc_info* info = compiled->block_gc_info();
 323
 324     FACTOR_ASSERT(return_address < compiled->size());
 325     cell callsite = info->return_address_index(return_address);
 326     if (callsite == (cell)-1)
 327       return;
 328
 329 #ifdef DEBUG_GC_MAPS
 330     std::cout << "call frame code block " << compiled << " with offset "
 331               << return_address << std::endl;
 332 #endif
 333     cell* stack_pointer = (cell*)frame_top;
 334     uint8_t* bitmap = info->gc_info_bitmap();
 335
 336     if (ctx) {
 337       /* Scrub vacant stack locations. */
 338       scrub_stack(ctx->datastack,
 339                   bitmap,
 340                   info->callsite_scrub_d(callsite),
 341                   info->scrub_d_count);
 342       scrub_stack(ctx->retainstack,
 343                   bitmap,
 344                   info->callsite_scrub_r(callsite),
 345                   info->scrub_r_count);
 346
 347       /* Trace overinitialized stack locations. */
 348       check_stack(ctx->datastack,
 349                   bitmap,
 350                   info->callsite_check_d(callsite),
 351                   info->check_d_count);
 352       check_stack(ctx->retainstack,
 353                   bitmap,
 354                   info->callsite_check_r(callsite),
 355                   info->check_r_count);
 356     }
 357
 358     /* Subtract old value of base pointer from every derived pointer. */
 359     for (cell spill_slot = 0; spill_slot < info->derived_root_count;
 360          spill_slot++) {
 361       uint32_t base_pointer = info->lookup_base_pointer(callsite, spill_slot);
 362       if (base_pointer != (uint32_t)-1) {
 363 #ifdef DEBUG_GC_MAPS
 364         std::cout << "visiting derived root " << spill_slot
 365                   << " with base pointer " << base_pointer << std::endl;
 366 #endif
 367         stack_pointer[spill_slot] -= stack_pointer[base_pointer];
 368       }
 369     }
 370
 371     /* Update all GC roots, including base pointers. */
 372     cell callsite_gc_roots = info->callsite_gc_roots(callsite);
 373
 374     for (cell spill_slot = 0; spill_slot < info->gc_root_count; spill_slot++) {
 375       if (bitmap_p(bitmap, callsite_gc_roots + spill_slot)) {
 376 #ifdef DEBUG_GC_MAPS
 377         std::cout << "visiting GC root " << spill_slot << std::endl;
 378 #endif
 379         visitor->visit_handle(stack_pointer + spill_slot);
 380       }
 381     }
 382
 383     /* Add the base pointers to obtain new derived pointer values. */
 384     for (cell spill_slot = 0; spill_slot < info->derived_root_count;
 385          spill_slot++) {
 386       uint32_t base_pointer = info->lookup_base_pointer(callsite, spill_slot);
 387       if (base_pointer != (uint32_t)-1)
 388         stack_pointer[spill_slot] += stack_pointer[base_pointer];
 389     }
 390   }
 391 };
 392
 393 template <typename Fixup>
 394 void slot_visitor<Fixup>::visit_callstack_object(callstack* stack) {
 395   call_frame_slot_visitor<Fixup> call_frame_visitor(parent, this, NULL);
 396   parent->iterate_callstack_object(stack, call_frame_visitor, fixup);
 397 }
 398
 399 template <typename Fixup>
 400 void slot_visitor<Fixup>::visit_callstack(context* ctx) {
 401   call_frame_slot_visitor<Fixup> call_frame_visitor(parent, this, ctx);
 402   parent->iterate_callstack(ctx, call_frame_visitor, fixup);
 403 }
 404
 405 template <typename Fixup>
 406 void slot_visitor<Fixup>::visit_context(context* ctx) {
 407   /* Callstack is visited first because it scrubs the data and retain
 408      stacks. */
 409   visit_callstack(ctx);
 410
 411   visit_stack_elements(ctx->datastack_seg, (cell*)ctx->datastack);
 412   visit_stack_elements(ctx->retainstack_seg, (cell*)ctx->retainstack);
 413   visit_object_array(ctx->context_objects,
 414                      ctx->context_objects + context_object_count);
 415
 416 }
 417
 418 template <typename Fixup> void slot_visitor<Fixup>::visit_contexts() {
 419   std::set<context*>::const_iterator begin = parent->active_contexts.begin();
 420   std::set<context*>::const_iterator end = parent->active_contexts.end();
 421   while (begin != end) {
 422     visit_context(*begin);
 423     begin++;
 424   }
 425 }
 426
 427 template <typename Fixup> struct literal_references_visitor {
 428   slot_visitor<Fixup>* visitor;
 429
 430   explicit literal_references_visitor(slot_visitor<Fixup>* visitor)
 431       : visitor(visitor) {}
 432
 433   void operator()(instruction_operand op) {
 434     if (op.rel_type() == RT_LITERAL)
 435       op.store_value(visitor->visit_pointer(op.load_value()));
 436   }
 437 };
 438
 439 template <typename Fixup>
 440 void slot_visitor<Fixup>::visit_code_block_objects(code_block* compiled) {
 441   visit_handle(&compiled->owner);
 442   visit_handle(&compiled->parameters);
 443   visit_handle(&compiled->relocation);
 444 }
 445
 446 template <typename Fixup>
 447 void slot_visitor<Fixup>::visit_embedded_literals(code_block* compiled) {
 448   if (!parent->code->uninitialized_p(compiled)) {
 449     literal_references_visitor<Fixup> visitor(this);
 450     compiled->each_instruction_operand(visitor);
 451   }
 452 }
 453
 454 }