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_contexts();
 129   void visit_code_block_objects(code_block* compiled);
 130   void visit_embedded_literals(code_block* compiled);
 131   void visit_sample_callstacks();
 132   void visit_sample_threads();
 133 };
 134
 135 template <typename Fixup>
 136 cell slot_visitor<Fixup>::visit_pointer(cell pointer) {
 137   if (immediate_p(pointer))
 138     return pointer;
 139
 140   object* untagged = fixup.fixup_data(untag<object>(pointer));
 141   return RETAG(untagged, TAG(pointer));
 142 }
 143
 144 template <typename Fixup> void slot_visitor<Fixup>::visit_handle(cell* handle) {
 145   *handle = visit_pointer(*handle);
 146 }
 147
 148 template <typename Fixup>
 149 void slot_visitor<Fixup>::visit_object_array(cell* start, cell* end) {
 150   while (start < end)
 151     visit_handle(start++);
 152 }
 153
 154 template <typename Fixup>
 155 void slot_visitor<Fixup>::visit_slots(object* ptr, cell payload_start) {
 156   cell* slot = (cell*)ptr;
 157   cell* end = (cell*)((cell)ptr + payload_start);
 158
 159   if (slot != end) {
 160     slot++;
 161     visit_object_array(slot, end);
 162   }
 163 }
 164
 165 template <typename Fixup> void slot_visitor<Fixup>::visit_slots(object* obj) {
 166   if (obj->type() == CALLSTACK_TYPE)
 167     visit_callstack_object((callstack*)obj);
 168   else
 169     visit_slots(obj, obj->binary_payload_start(fixup));
 170 }
 171
 172 template <typename Fixup>
 173 void slot_visitor<Fixup>::visit_stack_elements(segment* region, cell* top) {
 174   visit_object_array((cell*)region->start, top + 1);
 175 }
 176
 177 template <typename Fixup> void slot_visitor<Fixup>::visit_data_roots() {
 178   std::vector<cell*>::const_iterator iter =
 179       parent->data_roots.begin();
 180   std::vector<cell*>::const_iterator end =
 181       parent->data_roots.end();
 182
 183   for (; iter < end; iter++) {
 184     visit_handle(*iter);
 185   }
 186 }
 187
 188 template <typename Fixup> void slot_visitor<Fixup>::visit_bignum_roots() {
 189   std::vector<bignum**>::const_iterator iter =
 190       parent->bignum_roots.begin();
 191   std::vector<bignum**>::const_iterator end =
 192       parent->bignum_roots.end();
 193
 194   for (; iter < end; iter++) {
 195     bignum** ref = *iter;
 196     *ref = (bignum*)fixup.fixup_data(*ref);
 197   }
 198 }
 199
 200 template <typename Fixup> struct callback_slot_visitor {
 201   callback_heap* callbacks;
 202   slot_visitor<Fixup>* visitor;
 203
 204   callback_slot_visitor(callback_heap* callbacks,
 205                         slot_visitor<Fixup>* visitor)
 206       : callbacks(callbacks), visitor(visitor) {}
 207
 208   void operator()(code_block* stub) { visitor->visit_handle(&stub->owner); }
 209 };
 210
 211 template <typename Fixup> void slot_visitor<Fixup>::visit_callback_roots() {
 212   callback_slot_visitor<Fixup> callback_visitor(parent->callbacks, this);
 213   parent->callbacks->each_callback(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 template <typename Fixup> struct call_frame_slot_visitor {
 265   factor_vm* parent;
 266   slot_visitor<Fixup>* visitor;
 267   context* ctx;
 268
 269   call_frame_slot_visitor(factor_vm* parent,
 270                           slot_visitor<Fixup>* visitor,
 271                           context* ctx)
 272       : parent(parent), visitor(visitor), ctx(ctx) {}
 273
 274   /*
 275         frame top -> [return address]
 276                      [spill area]
 277                      ...
 278                      [entry_point]
 279                      [size]
 280         */
 281   void operator()(void* frame_top, cell frame_size, code_block* owner,
 282                   void* addr) {
 283     cell return_address = owner->offset(addr);
 284
 285     code_block* compiled =
 286         Fixup::translated_code_block_map ? owner
 287                                          : visitor->fixup.translate_code(owner);
 288     gc_info* info = compiled->block_gc_info();
 289
 290     FACTOR_ASSERT(return_address < compiled->size());
 291     cell callsite = info->return_address_index(return_address);
 292     if (callsite == (cell)-1)
 293       return;
 294
 295 #ifdef DEBUG_GC_MAPS
 296     std::cout << "call frame code block " << compiled << " with offset "
 297               << return_address << std::endl;
 298 #endif
 299     cell* stack_pointer = (cell*)frame_top;
 300     uint8_t* bitmap = info->gc_info_bitmap();
 301
 302     /* Subtract old value of base pointer from every derived pointer. */
 303     for (cell spill_slot = 0; spill_slot < info->derived_root_count;
 304          spill_slot++) {
 305       uint32_t base_pointer = info->lookup_base_pointer(callsite, spill_slot);
 306       if (base_pointer != (uint32_t)-1) {
 307 #ifdef DEBUG_GC_MAPS
 308         std::cout << "visiting derived root " << spill_slot
 309                   << " with base pointer " << base_pointer << std::endl;
 310 #endif
 311         stack_pointer[spill_slot] -= stack_pointer[base_pointer];
 312       }
 313     }
 314
 315     /* Trace all overinitialized stack locations. */
 316     cell callsite_check_d = info->callsite_check_d(callsite);
 317     for (uint32_t loc = 0; loc < info->check_d_count; loc++) {
 318       if (bitmap_p(bitmap, callsite_check_d + loc)) {
 319 #ifdef DEBUG_GC_MAPS
 320         std::cout << "checking datastack location " << loc << std::endl;
 321 #endif
 322         cell* value_ptr = ((cell*)ctx->datastack + loc + 1);
 323         visitor->visit_handle(value_ptr);
 324       }
 325     }
 326
 327     cell callsite_check_r = info->callsite_check_r(callsite);
 328     for (uint32_t loc = 0; loc < info->check_r_count; loc++) {
 329       if (bitmap_p(bitmap, callsite_check_r + loc)) {
 330 #ifdef DEBUG_GC_MAPS
 331         std::cout << "checking retainstack location " << loc << std::endl;
 332 #endif
 333         cell* value_ptr = ((cell*)ctx->retainstack + loc + 1);
 334         visitor->visit_handle(value_ptr);
 335       }
 336     }
 337
 338     /* Update all GC roots, including base pointers. */
 339     cell callsite_gc_roots = info->callsite_gc_roots(callsite);
 340
 341     for (cell spill_slot = 0; spill_slot < info->gc_root_count; spill_slot++) {
 342       if (bitmap_p(bitmap, callsite_gc_roots + spill_slot)) {
 343 #ifdef DEBUG_GC_MAPS
 344         std::cout << "visiting GC root " << spill_slot << std::endl;
 345 #endif
 346         visitor->visit_handle(stack_pointer + spill_slot);
 347       }
 348     }
 349
 350     /* Add the base pointers to obtain new derived pointer values. */
 351     for (cell spill_slot = 0; spill_slot < info->derived_root_count;
 352          spill_slot++) {
 353       uint32_t base_pointer = info->lookup_base_pointer(callsite, spill_slot);
 354       if (base_pointer != (uint32_t)-1)
 355         stack_pointer[spill_slot] += stack_pointer[base_pointer];
 356     }
 357   }
 358 };
 359
 360 template <typename Fixup>
 361 void slot_visitor<Fixup>::visit_callstack_object(callstack* stack) {
 362   /* TODO: is parent->ctx right? */
 363   call_frame_slot_visitor<Fixup> call_frame_visitor(parent, this, parent->ctx);
 364   parent->iterate_callstack_object(stack, call_frame_visitor, fixup);
 365 }
 366
 367 template <typename Fixup>
 368 void slot_visitor<Fixup>::visit_callstack(context* ctx) {
 369   call_frame_slot_visitor<Fixup> call_frame_visitor(parent, this, ctx);
 370   parent->iterate_callstack(ctx, call_frame_visitor, fixup);
 371 }
 372
 373 template <typename Fixup> void slot_visitor<Fixup>::visit_contexts() {
 374   std::set<context*>::const_iterator begin = parent->active_contexts.begin();
 375   std::set<context*>::const_iterator end = parent->active_contexts.end();
 376   while (begin != end) {
 377     context* ctx = *begin;
 378
 379     visit_stack_elements(ctx->datastack_seg, (cell*)ctx->datastack);
 380     visit_stack_elements(ctx->retainstack_seg, (cell*)ctx->retainstack);
 381     visit_object_array(ctx->context_objects,
 382                        ctx->context_objects + context_object_count);
 383     visit_callstack(ctx);
 384     begin++;
 385   }
 386 }
 387
 388 template <typename Fixup> struct literal_references_visitor {
 389   slot_visitor<Fixup>* visitor;
 390
 391   explicit literal_references_visitor(slot_visitor<Fixup>* visitor)
 392       : visitor(visitor) {}
 393
 394   void operator()(instruction_operand op) {
 395     if (op.rel_type() == RT_LITERAL)
 396       op.store_value(visitor->visit_pointer(op.load_value()));
 397   }
 398 };
 399
 400 template <typename Fixup>
 401 void slot_visitor<Fixup>::visit_code_block_objects(code_block* compiled) {
 402   visit_handle(&compiled->owner);
 403   visit_handle(&compiled->parameters);
 404   visit_handle(&compiled->relocation);
 405 }
 406
 407 template <typename Fixup>
 408 void slot_visitor<Fixup>::visit_embedded_literals(code_block* compiled) {
 409   if (!parent->code->uninitialized_p(compiled)) {
 410     literal_references_visitor<Fixup> visitor(this);
 411     compiled->each_instruction_operand(visitor);
 412   }
 413 }
 414
 415 }