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         frame top -> [return address]
 304                      [spill area]
 305                      ...
 306                      [entry_point]
 307                      [size]
 308         */
 309         void operator()(void *frame_top, cell frame_size, code_block *owner, void *addr)
 310         {
 311                 cell return_address = owner->offset(addr);
 312
 313                 code_block *compiled = Fixup::translated_code_block_map
 314                         ? owner
 315                         : visitor->fixup.translate_code(owner);
 316                 gc_info *info = compiled->block_gc_info();
 317
 318                 FACTOR_ASSERT(return_address < compiled->size());
 319                 cell callsite = info->return_address_index(return_address);
 320                 if(callsite == (cell)-1)
 321                         return;
 322
 323 #ifdef DEBUG_GC_MAPS
 324                 std::cout << "call frame code block " << compiled << " with offset " << return_address << std::endl;
 325 #endif
 326                 cell *stack_pointer = (cell *)frame_top;
 327                 u8 *bitmap = info->gc_info_bitmap();
 328
 329                 /* Subtract old value of base pointer from every derived pointer. */
 330                 for(cell spill_slot = 0; spill_slot < info->derived_root_count; spill_slot++)
 331                 {
 332                         u32 base_pointer = info->lookup_base_pointer(callsite, spill_slot);
 333                         if(base_pointer != (u32)-1)
 334                         {
 335 #ifdef DEBUG_GC_MAPS
 336                                 std::cout << "visiting derived root " << spill_slot
 337                                         << " with base pointer " << base_pointer
 338                                         << std::endl;
 339 #endif
 340                                 stack_pointer[spill_slot] -= stack_pointer[base_pointer];
 341                         }
 342                 }
 343
 344                 /* Update all GC roots, including base pointers. */
 345                 cell callsite_gc_roots = info->callsite_gc_roots(callsite);
 346
 347                 for(cell spill_slot = 0; spill_slot < info->gc_root_count; spill_slot++)
 348                 {
 349                         if(bitmap_p(bitmap,callsite_gc_roots + spill_slot))
 350                         {
 351 #ifdef DEBUG_GC_MAPS
 352                                 std::cout << "visiting GC root " << spill_slot << std::endl;
 353 #endif
 354                                 visitor->visit_handle(stack_pointer + spill_slot);
 355                         }
 356                 }
 357
 358                 /* Add the base pointers to obtain new derived pointer values. */
 359                 for(cell spill_slot = 0; spill_slot < info->derived_root_count; spill_slot++)
 360                 {
 361                         u32 base_pointer = info->lookup_base_pointer(callsite, spill_slot);
 362                         if(base_pointer != (u32)-1)
 363                                 stack_pointer[spill_slot] += stack_pointer[base_pointer];
 364                 }
 365         }
 366 };
 367
 368 template<typename Fixup>
 369 void slot_visitor<Fixup>::visit_callstack_object(callstack *stack)
 370 {
 371         call_frame_slot_visitor<Fixup> call_frame_visitor(parent,this);
 372         parent->iterate_callstack_object_reversed(stack,call_frame_visitor,fixup);
 373 }
 374
 375 template<typename Fixup>
 376 void slot_visitor<Fixup>::visit_callstack(context *ctx)
 377 {
 378         call_frame_slot_visitor<Fixup> call_frame_visitor(parent,this);
 379         parent->iterate_callstack_reversed(ctx,call_frame_visitor,fixup);
 380 }
 381
 382 template<typename Fixup>
 383 void slot_visitor<Fixup>::visit_contexts()
 384 {
 385         std::set<context *>::const_iterator begin = parent->active_contexts.begin();
 386         std::set<context *>::const_iterator end = parent->active_contexts.end();
 387         while(begin != end)
 388         {
 389                 context *ctx = *begin;
 390
 391                 visit_stack_elements(ctx->datastack_seg,(cell *)ctx->datastack);
 392                 visit_stack_elements(ctx->retainstack_seg,(cell *)ctx->retainstack);
 393                 visit_object_array(ctx->context_objects,ctx->context_objects + context_object_count);
 394                 visit_callstack(ctx);
 395                 begin++;
 396         }
 397 }
 398
 399 template<typename Fixup>
 400 struct literal_references_visitor {
 401         slot_visitor<Fixup> *visitor;
 402
 403         explicit literal_references_visitor(slot_visitor<Fixup> *visitor_) : visitor(visitor_) {}
 404
 405         void operator()(instruction_operand op)
 406         {
 407                 if(op.rel_type() == RT_LITERAL)
 408                         op.store_value(visitor->visit_pointer(op.load_value()));
 409         }
 410 };
 411
 412 template<typename Fixup>
 413 void slot_visitor<Fixup>::visit_code_block_objects(code_block *compiled)
 414 {
 415         visit_handle(&compiled->owner);
 416         visit_handle(&compiled->parameters);
 417         visit_handle(&compiled->relocation);
 418 }
 419
 420 template<typename Fixup>
 421 void slot_visitor<Fixup>::visit_embedded_literals(code_block *compiled)
 422 {
 423         if(!parent->code->uninitialized_p(compiled))
 424         {
 425                 literal_references_visitor<Fixup> visitor(this);
 426                 compiled->each_instruction_operand(visitor);
 427         }
 428 }
 429
 430 }