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