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<cell>::const_iterator iter = parent->bignum_roots.begin();
 190   std::vector<cell>::const_iterator end = parent->bignum_roots.end();
 191
 192   for (; iter < end; iter++) {
 193     cell* handle = (cell*)(*iter);
 194
 195     if (*handle)
 196       *handle = (cell)fixup.fixup_data(*(object**)handle);
 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
 268   call_frame_slot_visitor(factor_vm* parent,
 269                           slot_visitor<Fixup>* visitor)
 270       : parent(parent), visitor(visitor) {}
 271
 272   /*
 273         frame top -> [return address]
 274                      [spill area]
 275                      ...
 276                      [entry_point]
 277                      [size]
 278         */
 279   void operator()(void* frame_top, cell frame_size, code_block* owner,
 280                   void* addr) {
 281     cell return_address = owner->offset(addr);
 282
 283     code_block* compiled =
 284         Fixup::translated_code_block_map ? owner
 285                                          : visitor->fixup.translate_code(owner);
 286     gc_info* info = compiled->block_gc_info();
 287
 288     FACTOR_ASSERT(return_address < compiled->size());
 289     cell callsite = info->return_address_index(return_address);
 290     if (callsite == (cell)-1)
 291       return;
 292
 293 #ifdef DEBUG_GC_MAPS
 294     std::cout << "call frame code block " << compiled << " with offset "
 295               << return_address << std::endl;
 296 #endif
 297     cell* stack_pointer = (cell*)frame_top;
 298     uint8_t* bitmap = info->gc_info_bitmap();
 299
 300     /* Subtract old value of base pointer from every derived pointer. */
 301     for (cell spill_slot = 0; spill_slot < info->derived_root_count;
 302          spill_slot++) {
 303       uint32_t base_pointer = info->lookup_base_pointer(callsite, spill_slot);
 304       if (base_pointer != (uint32_t)-1) {
 305 #ifdef DEBUG_GC_MAPS
 306         std::cout << "visiting derived root " << spill_slot
 307                   << " with base pointer " << base_pointer << std::endl;
 308 #endif
 309         stack_pointer[spill_slot] -= stack_pointer[base_pointer];
 310       }
 311     }
 312
 313     /* Update all GC roots, including base pointers. */
 314     cell callsite_gc_roots = info->callsite_gc_roots(callsite);
 315
 316     for (cell spill_slot = 0; spill_slot < info->gc_root_count; spill_slot++) {
 317       if (bitmap_p(bitmap, callsite_gc_roots + spill_slot)) {
 318 #ifdef DEBUG_GC_MAPS
 319         std::cout << "visiting GC root " << spill_slot << std::endl;
 320 #endif
 321         visitor->visit_handle(stack_pointer + spill_slot);
 322       }
 323     }
 324
 325     /* Add the base pointers to obtain new derived pointer values. */
 326     for (cell spill_slot = 0; spill_slot < info->derived_root_count;
 327          spill_slot++) {
 328       uint32_t base_pointer = info->lookup_base_pointer(callsite, spill_slot);
 329       if (base_pointer != (uint32_t)-1)
 330         stack_pointer[spill_slot] += stack_pointer[base_pointer];
 331     }
 332   }
 333 };
 334
 335 template <typename Fixup>
 336 void slot_visitor<Fixup>::visit_callstack_object(callstack* stack) {
 337   call_frame_slot_visitor<Fixup> call_frame_visitor(parent, this);
 338   parent->iterate_callstack_object(stack, call_frame_visitor, fixup);
 339 }
 340
 341 template <typename Fixup>
 342 void slot_visitor<Fixup>::visit_callstack(context* ctx) {
 343   call_frame_slot_visitor<Fixup> call_frame_visitor(parent, this);
 344   parent->iterate_callstack(ctx, call_frame_visitor, fixup);
 345 }
 346
 347 template <typename Fixup> void slot_visitor<Fixup>::visit_contexts() {
 348   std::set<context*>::const_iterator begin = parent->active_contexts.begin();
 349   std::set<context*>::const_iterator end = parent->active_contexts.end();
 350   while (begin != end) {
 351     context* ctx = *begin;
 352
 353     visit_stack_elements(ctx->datastack_seg, (cell*)ctx->datastack);
 354     visit_stack_elements(ctx->retainstack_seg, (cell*)ctx->retainstack);
 355     visit_object_array(ctx->context_objects,
 356                        ctx->context_objects + context_object_count);
 357     visit_callstack(ctx);
 358     begin++;
 359   }
 360 }
 361
 362 template <typename Fixup> struct literal_references_visitor {
 363   slot_visitor<Fixup>* visitor;
 364
 365   explicit literal_references_visitor(slot_visitor<Fixup>* visitor)
 366       : visitor(visitor) {}
 367
 368   void operator()(instruction_operand op) {
 369     if (op.rel_type() == RT_LITERAL)
 370       op.store_value(visitor->visit_pointer(op.load_value()));
 371   }
 372 };
 373
 374 template <typename Fixup>
 375 void slot_visitor<Fixup>::visit_code_block_objects(code_block* compiled) {
 376   visit_handle(&compiled->owner);
 377   visit_handle(&compiled->parameters);
 378   visit_handle(&compiled->relocation);
 379 }
 380
 381 template <typename Fixup>
 382 void slot_visitor<Fixup>::visit_embedded_literals(code_block* compiled) {
 383   if (!parent->code->uninitialized_p(compiled)) {
 384     literal_references_visitor<Fixup> visitor(this);
 385     compiled->each_instruction_operand(visitor);
 386   }
 387 }
 388
 389 }