vm/slot_visitor.hpp

   1 namespace factor
   2 {
   3
   4 /* Size of the object pointed to by an untagged pointer */
   5 template<typename Fixup>
   6 cell object::size(Fixup fixup) const
   7 {
   8         if(free_p()) return ((free_heap_block *)this)->size();
   9
  10         switch(type())
  11         {
  12         case ARRAY_TYPE:
  13                 return align(array_size((array*)this),data_alignment);
  14         case BIGNUM_TYPE:
  15                 return align(array_size((bignum*)this),data_alignment);
  16         case BYTE_ARRAY_TYPE:
  17                 return align(array_size((byte_array*)this),data_alignment);
  18         case STRING_TYPE:
  19                 return align(string_size(string_capacity((string*)this)),data_alignment);
  20         case TUPLE_TYPE:
  21                 {
  22                         tuple_layout *layout = (tuple_layout *)fixup.translate_data(untag<object>(((tuple *)this)->layout));
  23                         return align(tuple_size(layout),data_alignment);
  24                 }
  25         case QUOTATION_TYPE:
  26                 return align(sizeof(quotation),data_alignment);
  27         case WORD_TYPE:
  28                 return align(sizeof(word),data_alignment);
  29         case FLOAT_TYPE:
  30                 return align(sizeof(boxed_float),data_alignment);
  31         case DLL_TYPE:
  32                 return align(sizeof(dll),data_alignment);
  33         case ALIEN_TYPE:
  34                 return align(sizeof(alien),data_alignment);
  35         case WRAPPER_TYPE:
  36                 return align(sizeof(wrapper),data_alignment);
  37         case CALLSTACK_TYPE:
  38                 return align(callstack_object_size(untag_fixnum(((callstack *)this)->length)),data_alignment);
  39         default:
  40                 critical_error("Invalid header in size",(cell)this);
  41                 return 0; /* can't happen */
  42         }
  43 }
  44
  45 inline cell object::size() const
  46 {
  47         return size(no_fixup());
  48 }
  49
  50 /* The number of cells from the start of the object which should be scanned by
  51 the GC. Some types have a binary payload at the end (string, word, DLL) which
  52 we ignore. */
  53 template<typename Fixup>
  54 cell object::binary_payload_start(Fixup fixup) const
  55 {
  56         if(free_p()) return 0;
  57
  58         switch(type())
  59         {
  60         /* these objects do not refer to other objects at all */
  61         case FLOAT_TYPE:
  62         case BYTE_ARRAY_TYPE:
  63         case BIGNUM_TYPE:
  64         case CALLSTACK_TYPE:
  65                 return 0;
  66         /* these objects have some binary data at the end */
  67         case WORD_TYPE:
  68                 return sizeof(word) - sizeof(cell);
  69         case ALIEN_TYPE:
  70                 return sizeof(cell) * 3;
  71         case DLL_TYPE:
  72                 return sizeof(cell) * 2;
  73         case QUOTATION_TYPE:
  74                 return sizeof(quotation) - sizeof(cell);
  75         case STRING_TYPE:
  76                 return sizeof(string);
  77         /* everything else consists entirely of pointers */
  78         case ARRAY_TYPE:
  79                 return array_size<array>(array_capacity((array*)this));
  80         case TUPLE_TYPE:
  81                 {
  82                         tuple_layout *layout = (tuple_layout *)fixup.translate_data(untag<object>(((tuple *)this)->layout));
  83                         return tuple_size(layout);
  84                 }
  85         case WRAPPER_TYPE:
  86                 return sizeof(wrapper);
  87         default:
  88                 critical_error("Invalid header in binary_payload_start",(cell)this);
  89                 return 0; /* can't happen */
  90         }
  91 }
  92
  93 inline cell object::binary_payload_start() const
  94 {
  95         return binary_payload_start(no_fixup());
  96 }
  97
  98 /* Slot visitors iterate over the slots of an object, applying a functor to
  99 each one that is a non-immediate slot. The pointer is untagged first. The
 100 functor returns a new untagged object pointer. The return value may or may not equal the old one,
 101 however the new pointer receives the same tag before being stored back to the
 102 original location.
 103
 104 Slots storing immediate values are left unchanged and the visitor does inspect
 105 them.
 106
 107 This is used by GC's copying, sweep and compact phases, and the implementation
 108 of the become primitive.
 109
 110 Iteration is driven by visit_*() methods. Some of them define GC roots:
 111 - visit_roots()
 112 - visit_contexts() */
 113
 114 template<typename Fixup> struct slot_visitor {
 115         factor_vm *parent;
 116         Fixup fixup;
 117
 118         explicit slot_visitor<Fixup>(factor_vm *parent_, Fixup fixup_) :
 119                 parent(parent_), fixup(fixup_) {}
 120
 121         cell visit_pointer(cell pointer);
 122         void visit_handle(cell *handle);
 123         void visit_object_array(cell *start, cell *end);
 124         void visit_slots(object *ptr, cell payload_start);
 125         void visit_slots(object *ptr);
 126         void visit_stack_elements(segment *region, cell *top);
 127         void visit_data_roots();
 128         void visit_bignum_roots();
 129         void visit_callback_roots();
 130         void visit_literal_table_roots();
 131         void visit_roots();
 132         void visit_callstack_object(callstack *stack);
 133         void visit_callstack(context *ctx);
 134         void visit_contexts();
 135         void visit_code_block_objects(code_block *compiled);
 136         void visit_embedded_literals(code_block *compiled);
 137         void visit_sample_callstacks();
 138         void visit_sample_threads();
 139 };
 140
 141 template<typename Fixup>
 142 cell slot_visitor<Fixup>::visit_pointer(cell pointer)
 143 {
 144         if(immediate_p(pointer)) return pointer;
 145
 146         object *untagged = fixup.fixup_data(untag<object>(pointer));
 147         return RETAG(untagged,TAG(pointer));
 148 }
 149
 150 template<typename Fixup>
 151 void slot_visitor<Fixup>::visit_handle(cell *handle)
 152 {
 153         *handle = visit_pointer(*handle);
 154 }
 155
 156 template<typename Fixup>
 157 void slot_visitor<Fixup>::visit_object_array(cell *start, cell *end)
 158 {
 159         while(start < end) visit_handle(start++);
 160 }
 161
 162 template<typename Fixup>
 163 void slot_visitor<Fixup>::visit_slots(object *ptr, cell payload_start)
 164 {
 165         cell *slot = (cell *)ptr;
 166         cell *end = (cell *)((cell)ptr + payload_start);
 167
 168         if(slot != end)
 169         {
 170                 slot++;
 171                 visit_object_array(slot,end);
 172         }
 173 }
 174
 175 template<typename Fixup>
 176 void slot_visitor<Fixup>::visit_slots(object *obj)
 177 {
 178         if(obj->type() == CALLSTACK_TYPE)
 179                 visit_callstack_object((callstack *)obj);
 180         else
 181                 visit_slots(obj,obj->binary_payload_start(fixup));
 182 }
 183
 184 template<typename Fixup>
 185 void slot_visitor<Fixup>::visit_stack_elements(segment *region, cell *top)
 186 {
 187         visit_object_array((cell *)region->start,top + 1);
 188 }
 189
 190 template<typename Fixup>
 191 void slot_visitor<Fixup>::visit_data_roots()
 192 {
 193         std::vector<data_root_range>::const_iterator iter = parent->data_roots.begin();
 194         std::vector<data_root_range>::const_iterator end = parent->data_roots.end();
 195
 196         for(; iter < end; iter++)
 197                 visit_object_array(iter->start,iter->start + iter->len);
 198 }
 199
 200 template<typename Fixup>
 201 void slot_visitor<Fixup>::visit_bignum_roots()
 202 {
 203         std::vector<cell>::const_iterator iter = parent->bignum_roots.begin();
 204         std::vector<cell>::const_iterator end = parent->bignum_roots.end();
 205
 206         for(; iter < end; iter++)
 207         {
 208                 cell *handle = (cell *)(*iter);
 209
 210                 if(*handle)
 211                         *handle = (cell)fixup.fixup_data(*(object **)handle);
 212         }
 213 }
 214
 215 template<typename Fixup>
 216 struct callback_slot_visitor {
 217         callback_heap *callbacks;
 218         slot_visitor<Fixup> *visitor;
 219
 220         explicit callback_slot_visitor(callback_heap *callbacks_, slot_visitor<Fixup> *visitor_) :
 221                 callbacks(callbacks_), visitor(visitor_) {}
 222
 223         void operator()(code_block *stub)
 224         {
 225                 visitor->visit_handle(&stub->owner);
 226         }
 227 };
 228
 229 template<typename Fixup>
 230 void slot_visitor<Fixup>::visit_callback_roots()
 231 {
 232         callback_slot_visitor<Fixup> callback_visitor(parent->callbacks,this);
 233         parent->callbacks->each_callback(callback_visitor);
 234 }
 235
 236 template<typename Fixup>
 237 void slot_visitor<Fixup>::visit_literal_table_roots()
 238 {
 239         std::map<code_block *, cell> *uninitialized_blocks = &parent->code->uninitialized_blocks;
 240         std::map<code_block *, cell>::const_iterator iter = uninitialized_blocks->begin();
 241         std::map<code_block *, cell>::const_iterator end = uninitialized_blocks->end();
 242
 243         std::map<code_block *, cell> new_uninitialized_blocks;
 244         for(; iter != end; iter++)
 245         {
 246                 new_uninitialized_blocks.insert(std::make_pair(
 247                         iter->first,
 248                         visit_pointer(iter->second)));
 249         }
 250
 251         parent->code->uninitialized_blocks = new_uninitialized_blocks;
 252 }
 253
 254 template<typename Fixup>
 255 void slot_visitor<Fixup>::visit_sample_callstacks()
 256 {
 257         for (std::vector<cell>::iterator iter = parent->sample_callstacks.begin();
 258                 iter != parent->sample_callstacks.end();
 259                 ++iter)
 260         {
 261                 visit_handle(&*iter);
 262         }
 263 }
 264
 265 template<typename Fixup>
 266 void slot_visitor<Fixup>::visit_sample_threads()
 267 {
 268         for (std::vector<profiling_sample>::iterator iter = parent->samples.begin();
 269                 iter != parent->samples.end();
 270                 ++iter)
 271         {
 272                 visit_handle(&iter->thread);
 273         }
 274 }
 275
 276 template<typename Fixup>
 277 void slot_visitor<Fixup>::visit_roots()
 278 {
 279         visit_handle(&parent->true_object);
 280         visit_handle(&parent->bignum_zero);
 281         visit_handle(&parent->bignum_pos_one);
 282         visit_handle(&parent->bignum_neg_one);
 283
 284         visit_data_roots();
 285         visit_bignum_roots();
 286         visit_callback_roots();
 287         visit_literal_table_roots();
 288         visit_sample_callstacks();
 289         visit_sample_threads();
 290
 291         visit_object_array(parent->special_objects,parent->special_objects + special_object_count);
 292 }
 293
 294 template<typename Fixup>
 295 struct call_frame_slot_visitor {
 296         factor_vm *parent;
 297         slot_visitor<Fixup> *visitor;
 298
 299         explicit call_frame_slot_visitor(factor_vm *parent_, slot_visitor<Fixup> *visitor_) :
 300                 parent(parent_), visitor(visitor_) {}
 301
 302         /*
 303         next  -> [entry_point]
 304                  [size]
 305                  [return address] -- x86 only, backend adds 1 to each spill location
 306                  [spill area]
 307                  ...
 308         frame -> [entry_point]
 309                  [size]
 310         */
 311         void operator()(stack_frame *frame)
 312         {
 313                 cell return_address = parent->frame_offset(frame);
 314                 if(return_address == (cell)-1)
 315                         return;
 316
 317                 code_block *compiled = visitor->fixup.translate_code(parent->frame_code(frame));
 318                 gc_info *info = compiled->block_gc_info();
 319
 320                 assert(return_address < compiled->size());
 321                 cell callsite = info->return_address_index(return_address);
 322                 if(callsite == (cell)-1)
 323                         return;
 324
 325 #ifdef DEBUG_GC_MAPS
 326                 std::cout << "call frame code block " << compiled << " with offset " << return_address << std::endl;
 327 #endif
 328                 cell *stack_pointer = (cell *)(parent->frame_successor(frame) + 1);
 329                 u8 *bitmap = info->gc_info_bitmap();
 330
 331                 /* Subtract old value of base pointer from every derived pointer. */
 332                 for(cell spill_slot = 0; spill_slot < info->derived_root_count; spill_slot++)
 333                 {
 334                         u32 base_pointer = info->lookup_base_pointer(callsite, spill_slot);
 335                         if(base_pointer != (u32)-1)
 336                         {
 337 #ifdef DEBUG_GC_MAPS
 338                                 std::cout << "visiting derived root " << spill_slot
 339                                         << " with base pointer " << base_pointer
 340                                         << std::endl;
 341 #endif
 342                                 stack_pointer[spill_slot] -= stack_pointer[base_pointer];
 343                         }
 344                 }
 345
 346                 /* Update all GC roots, including base pointers. */
 347                 cell callsite_gc_roots = info->callsite_gc_roots(callsite);
 348
 349                 for(cell spill_slot = 0; spill_slot < info->gc_root_count; spill_slot++)
 350                 {
 351                         if(bitmap_p(bitmap,callsite_gc_roots + spill_slot))
 352                         {
 353 #ifdef DEBUG_GC_MAPS
 354                                 std::cout << "visiting GC root " << spill_slot << std::endl;
 355 #endif
 356                                 visitor->visit_handle(stack_pointer + spill_slot);
 357                         }
 358                 }
 359
 360                 /* Add the base pointers to obtain new derived pointer values. */
 361                 for(cell spill_slot = 0; spill_slot < info->derived_root_count; spill_slot++)
 362                 {
 363                         u32 base_pointer = info->lookup_base_pointer(callsite, spill_slot);
 364                         if(base_pointer != (u32)-1)
 365                                 stack_pointer[spill_slot] += stack_pointer[base_pointer];
 366                 }
 367         }
 368 };
 369
 370 template<typename Fixup>
 371 void slot_visitor<Fixup>::visit_callstack_object(callstack *stack)
 372 {
 373         call_frame_slot_visitor<Fixup> call_frame_visitor(parent,this);
 374         parent->iterate_callstack_object(stack,call_frame_visitor);
 375 }
 376
 377 template<typename Fixup>
 378 void slot_visitor<Fixup>::visit_callstack(context *ctx)
 379 {
 380         call_frame_slot_visitor<Fixup> call_frame_visitor(parent,this);
 381         parent->iterate_callstack(ctx,call_frame_visitor);
 382 }
 383
 384 template<typename Fixup>
 385 void slot_visitor<Fixup>::visit_contexts()
 386 {
 387         std::set<context *>::const_iterator begin = parent->active_contexts.begin();
 388         std::set<context *>::const_iterator end = parent->active_contexts.end();
 389         while(begin != end)
 390         {
 391                 context *ctx = *begin;
 392
 393                 visit_stack_elements(ctx->datastack_seg,(cell *)ctx->datastack);
 394                 visit_stack_elements(ctx->retainstack_seg,(cell *)ctx->retainstack);
 395                 visit_object_array(ctx->context_objects,ctx->context_objects + context_object_count);
 396                 visit_callstack(ctx);
 397                 begin++;
 398         }
 399 }
 400
 401 template<typename Fixup>
 402 struct literal_references_visitor {
 403         slot_visitor<Fixup> *visitor;
 404
 405         explicit literal_references_visitor(slot_visitor<Fixup> *visitor_) : visitor(visitor_) {}
 406
 407         void operator()(instruction_operand op)
 408         {
 409                 if(op.rel_type() == RT_LITERAL)
 410                         op.store_value(visitor->visit_pointer(op.load_value()));
 411         }
 412 };
 413
 414 template<typename Fixup>
 415 void slot_visitor<Fixup>::visit_code_block_objects(code_block *compiled)
 416 {
 417         visit_handle(&compiled->owner);
 418         visit_handle(&compiled->parameters);
 419         visit_handle(&compiled->relocation);
 420 }
 421
 422 template<typename Fixup>
 423 void slot_visitor<Fixup>::visit_embedded_literals(code_block *compiled)
 424 {
 425         if(!parent->code->uninitialized_p(compiled))
 426         {
 427                 literal_references_visitor<Fixup> visitor(this);
 428                 compiled->each_instruction_operand(visitor);
 429         }
 430 }
 431
 432 }