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<data_root_range>::const_iterator iter =
 179       parent->data_roots.begin();
 180   std::vector<data_root_range>::const_iterator end = parent->data_roots.end();
 181
 182   for (; iter < end; iter++)
 183     visit_object_array(iter->start, iter->start + iter->len);
 184 }
 185
 186 template <typename Fixup> void slot_visitor<Fixup>::visit_bignum_roots() {
 187   std::vector<cell>::const_iterator iter = parent->bignum_roots.begin();
 188   std::vector<cell>::const_iterator end = parent->bignum_roots.end();
 189
 190   for (; iter < end; iter++) {
 191     cell* handle = (cell*)(*iter);
 192
 193     if (*handle)
 194       *handle = (cell) fixup.fixup_data(*(object**)handle);
 195   }
 196 }
 197
 198 template <typename Fixup> struct callback_slot_visitor {
 199   callback_heap* callbacks;
 200   slot_visitor<Fixup>* visitor;
 201
 202   callback_slot_visitor(callback_heap* callbacks_,
 203                         slot_visitor<Fixup>* visitor_)
 204       : callbacks(callbacks_), visitor(visitor_) {}
 205
 206   void operator()(code_block* stub) { visitor->visit_handle(&stub->owner); }
 207 };
 208
 209 template <typename Fixup> void slot_visitor<Fixup>::visit_callback_roots() {
 210   callback_slot_visitor<Fixup> callback_visitor(parent->callbacks, this);
 211   parent->callbacks->each_callback(callback_visitor);
 212 }
 213
 214 template <typename Fixup>
 215 void slot_visitor<Fixup>::visit_literal_table_roots() {
 216   std::map<code_block*, cell>* uninitialized_blocks =
 217       &parent->code->uninitialized_blocks;
 218   std::map<code_block*, cell>::const_iterator iter =
 219       uninitialized_blocks->begin();
 220   std::map<code_block*, cell>::const_iterator end = uninitialized_blocks->end();
 221
 222   std::map<code_block*, cell> new_uninitialized_blocks;
 223   for (; iter != end; iter++) {
 224     new_uninitialized_blocks.insert(
 225         std::make_pair(iter->first, visit_pointer(iter->second)));
 226   }
 227
 228   parent->code->uninitialized_blocks = new_uninitialized_blocks;
 229 }
 230
 231 template <typename Fixup> void slot_visitor<Fixup>::visit_sample_callstacks() {
 232   for (std::vector<cell>::iterator iter = parent->sample_callstacks.begin();
 233        iter != parent->sample_callstacks.end(); ++iter) {
 234     visit_handle(&*iter);
 235   }
 236 }
 237
 238 template <typename Fixup> void slot_visitor<Fixup>::visit_sample_threads() {
 239   for (std::vector<profiling_sample>::iterator iter = parent->samples.begin();
 240        iter != parent->samples.end(); ++iter) {
 241     visit_handle(&iter->thread);
 242   }
 243 }
 244
 245 template <typename Fixup> void slot_visitor<Fixup>::visit_roots() {
 246   visit_handle(&parent->true_object);
 247   visit_handle(&parent->bignum_zero);
 248   visit_handle(&parent->bignum_pos_one);
 249   visit_handle(&parent->bignum_neg_one);
 250
 251   visit_data_roots();
 252   visit_bignum_roots();
 253   visit_callback_roots();
 254   visit_literal_table_roots();
 255   visit_sample_callstacks();
 256   visit_sample_threads();
 257
 258   visit_object_array(parent->special_objects,
 259                      parent->special_objects + special_object_count);
 260 }
 261
 262 template <typename Fixup> struct call_frame_slot_visitor {
 263   factor_vm* parent;
 264   slot_visitor<Fixup>* visitor;
 265
 266   call_frame_slot_visitor(factor_vm* parent_,
 267                           slot_visitor<Fixup>* visitor_)
 268       : parent(parent_), visitor(visitor_) {}
 269
 270   /*
 271         frame top -> [return address]
 272                      [spill area]
 273                      ...
 274                      [entry_point]
 275                      [size]
 276         */
 277   void operator()(void* frame_top, cell frame_size, code_block* owner,
 278                   void* addr) {
 279     cell return_address = owner->offset(addr);
 280
 281     code_block* compiled =
 282         Fixup::translated_code_block_map ? owner
 283                                          : visitor->fixup.translate_code(owner);
 284     gc_info* info = compiled->block_gc_info();
 285
 286     FACTOR_ASSERT(return_address < compiled->size());
 287     cell callsite = info->return_address_index(return_address);
 288     if (callsite == (cell) - 1)
 289       return;
 290
 291 #ifdef DEBUG_GC_MAPS
 292     std::cout << "call frame code block " << compiled << " with offset "
 293               << return_address << std::endl;
 294 #endif
 295     cell* stack_pointer = (cell*)frame_top;
 296     u8* bitmap = info->gc_info_bitmap();
 297
 298     /* Subtract old value of base pointer from every derived pointer. */
 299     for (cell spill_slot = 0; spill_slot < info->derived_root_count;
 300          spill_slot++) {
 301       u32 base_pointer = info->lookup_base_pointer(callsite, spill_slot);
 302       if (base_pointer != (u32) - 1) {
 303 #ifdef DEBUG_GC_MAPS
 304         std::cout << "visiting derived root " << spill_slot
 305                   << " with base pointer " << base_pointer << std::endl;
 306 #endif
 307         stack_pointer[spill_slot] -= stack_pointer[base_pointer];
 308       }
 309     }
 310
 311     /* Update all GC roots, including base pointers. */
 312     cell callsite_gc_roots = info->callsite_gc_roots(callsite);
 313
 314     for (cell spill_slot = 0; spill_slot < info->gc_root_count; spill_slot++) {
 315       if (bitmap_p(bitmap, callsite_gc_roots + spill_slot)) {
 316 #ifdef DEBUG_GC_MAPS
 317         std::cout << "visiting GC root " << spill_slot << std::endl;
 318 #endif
 319         visitor->visit_handle(stack_pointer + spill_slot);
 320       }
 321     }
 322
 323     /* Add the base pointers to obtain new derived pointer values. */
 324     for (cell spill_slot = 0; spill_slot < info->derived_root_count;
 325          spill_slot++) {
 326       u32 base_pointer = info->lookup_base_pointer(callsite, spill_slot);
 327       if (base_pointer != (u32) - 1)
 328         stack_pointer[spill_slot] += stack_pointer[base_pointer];
 329     }
 330   }
 331 };
 332
 333 template <typename Fixup>
 334 void slot_visitor<Fixup>::visit_callstack_object(callstack* stack) {
 335   call_frame_slot_visitor<Fixup> call_frame_visitor(parent, this);
 336   parent->iterate_callstack_object(stack, call_frame_visitor, fixup);
 337 }
 338
 339 template <typename Fixup>
 340 void slot_visitor<Fixup>::visit_callstack(context* ctx) {
 341   call_frame_slot_visitor<Fixup> call_frame_visitor(parent, this);
 342   parent->iterate_callstack(ctx, call_frame_visitor, fixup);
 343 }
 344
 345 template <typename Fixup> void slot_visitor<Fixup>::visit_contexts() {
 346   std::set<context*>::const_iterator begin = parent->active_contexts.begin();
 347   std::set<context*>::const_iterator end = parent->active_contexts.end();
 348   while (begin != end) {
 349     context* ctx = *begin;
 350
 351     visit_stack_elements(ctx->datastack_seg, (cell*)ctx->datastack);
 352     visit_stack_elements(ctx->retainstack_seg, (cell*)ctx->retainstack);
 353     visit_object_array(ctx->context_objects,
 354                        ctx->context_objects + context_object_count);
 355     visit_callstack(ctx);
 356     begin++;
 357   }
 358 }
 359
 360 template <typename Fixup> struct literal_references_visitor {
 361   slot_visitor<Fixup>* visitor;
 362
 363   explicit literal_references_visitor(slot_visitor<Fixup>* visitor_)
 364       : visitor(visitor_) {}
 365
 366   void operator()(instruction_operand op) {
 367     if (op.rel_type() == RT_LITERAL)
 368       op.store_value(visitor->visit_pointer(op.load_value()));
 369   }
 370 };
 371
 372 template <typename Fixup>
 373 void slot_visitor<Fixup>::visit_code_block_objects(code_block* compiled) {
 374   visit_handle(&compiled->owner);
 375   visit_handle(&compiled->parameters);
 376   visit_handle(&compiled->relocation);
 377 }
 378
 379 template <typename Fixup>
 380 void slot_visitor<Fixup>::visit_embedded_literals(code_block* compiled) {
 381   if (!parent->code->uninitialized_p(compiled)) {
 382     literal_references_visitor<Fixup> visitor(this);
 383     compiled->each_instruction_operand(visitor);
 384   }
 385 }
 386
 387 }