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