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) * 3;
  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) * 2;
  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 };
 139
 140 template<typename Fixup>
 141 cell slot_visitor<Fixup>::visit_pointer(cell pointer)
 142 {
 143         if(immediate_p(pointer)) return pointer;
 144
 145         object *untagged = fixup.fixup_data(untag<object>(pointer));
 146         return RETAG(untagged,TAG(pointer));
 147 }
 148
 149 template<typename Fixup>
 150 void slot_visitor<Fixup>::visit_handle(cell *handle)
 151 {
 152         *handle = visit_pointer(*handle);
 153 }
 154
 155 template<typename Fixup>
 156 void slot_visitor<Fixup>::visit_object_array(cell *start, cell *end)
 157 {
 158         while(start < end) visit_handle(start++);
 159 }
 160
 161 template<typename Fixup>
 162 void slot_visitor<Fixup>::visit_slots(object *ptr, cell payload_start)
 163 {
 164         cell *slot = (cell *)ptr;
 165         cell *end = (cell *)((cell)ptr + payload_start);
 166
 167         if(slot != end)
 168         {
 169                 slot++;
 170                 visit_object_array(slot,end);
 171         }
 172 }
 173
 174 template<typename Fixup>
 175 void slot_visitor<Fixup>::visit_slots(object *obj)
 176 {
 177         if(obj->type() == CALLSTACK_TYPE)
 178                 visit_callstack_object((callstack *)obj);
 179         else
 180                 visit_slots(obj,obj->binary_payload_start(fixup));
 181 }
 182
 183 template<typename Fixup>
 184 void slot_visitor<Fixup>::visit_stack_elements(segment *region, cell *top)
 185 {
 186         visit_object_array((cell *)region->start,top + 1);
 187 }
 188
 189 template<typename Fixup>
 190 void slot_visitor<Fixup>::visit_data_roots()
 191 {
 192         std::vector<data_root_range>::const_iterator iter = parent->data_roots.begin();
 193         std::vector<data_root_range>::const_iterator end = parent->data_roots.end();
 194
 195         for(; iter < end; iter++)
 196                 visit_object_array(iter->start,iter->start + iter->len);
 197 }
 198
 199 template<typename Fixup>
 200 void slot_visitor<Fixup>::visit_bignum_roots()
 201 {
 202         std::vector<cell>::const_iterator iter = parent->bignum_roots.begin();
 203         std::vector<cell>::const_iterator end = parent->bignum_roots.end();
 204
 205         for(; iter < end; iter++)
 206         {
 207                 cell *handle = (cell *)(*iter);
 208
 209                 if(*handle)
 210                         *handle = (cell)fixup.fixup_data(*(object **)handle);
 211         }
 212 }
 213
 214 template<typename Fixup>
 215 struct callback_slot_visitor {
 216         callback_heap *callbacks;
 217         slot_visitor<Fixup> *visitor;
 218
 219         explicit callback_slot_visitor(callback_heap *callbacks_, slot_visitor<Fixup> *visitor_) :
 220                 callbacks(callbacks_), visitor(visitor_) {}
 221
 222         void operator()(code_block *stub)
 223         {
 224                 visitor->visit_handle(&stub->owner);
 225         }
 226 };
 227
 228 template<typename Fixup>
 229 void slot_visitor<Fixup>::visit_callback_roots()
 230 {
 231         callback_slot_visitor<Fixup> callback_visitor(parent->callbacks,this);
 232         parent->callbacks->each_callback(callback_visitor);
 233 }
 234
 235 template<typename Fixup>
 236 void slot_visitor<Fixup>::visit_literal_table_roots()
 237 {
 238         std::map<code_block *, cell> *uninitialized_blocks = &parent->code->uninitialized_blocks;
 239         std::map<code_block *, cell>::const_iterator iter = uninitialized_blocks->begin();
 240         std::map<code_block *, cell>::const_iterator end = uninitialized_blocks->end();
 241
 242         std::map<code_block *, cell> new_uninitialized_blocks;
 243         for(; iter != end; iter++)
 244         {
 245                 new_uninitialized_blocks.insert(std::make_pair(
 246                         iter->first,
 247                         visit_pointer(iter->second)));
 248         }
 249
 250         parent->code->uninitialized_blocks = new_uninitialized_blocks;
 251 }
 252
 253 template<typename Fixup>
 254 void slot_visitor<Fixup>::visit_sample_callstacks()
 255 {
 256         for (std::vector<cell>::iterator iter = parent->sample_callstacks.begin();
 257                 iter != parent->sample_callstacks.end();
 258                 ++iter)
 259         {
 260                 visit_handle(&*iter);
 261         }
 262 }
 263
 264 template<typename Fixup>
 265 void slot_visitor<Fixup>::visit_roots()
 266 {
 267         visit_handle(&parent->true_object);
 268         visit_handle(&parent->bignum_zero);
 269         visit_handle(&parent->bignum_pos_one);
 270         visit_handle(&parent->bignum_neg_one);
 271
 272         visit_data_roots();
 273         visit_bignum_roots();
 274         visit_callback_roots();
 275         visit_literal_table_roots();
 276         visit_sample_callstacks();
 277
 278         visit_object_array(parent->special_objects,parent->special_objects + special_object_count);
 279 }
 280
 281 template<typename Fixup>
 282 struct call_frame_slot_visitor {
 283         factor_vm *parent;
 284         slot_visitor<Fixup> *visitor;
 285
 286         explicit call_frame_slot_visitor(factor_vm *parent_, slot_visitor<Fixup> *visitor_) :
 287                 parent(parent_), visitor(visitor_) {}
 288
 289         /*
 290         next  -> [entry_point]
 291                  [size]
 292                  [return address] -- x86 only, backend adds 1 to each spill location
 293                  [spill area]
 294                  ...
 295         frame -> [entry_point]
 296                  [size]
 297         */
 298         void operator()(stack_frame *frame)
 299         {
 300                 cell return_address = parent->frame_offset(frame);
 301                 if(return_address == (cell)-1)
 302                         return;
 303
 304                 code_block *compiled = visitor->fixup.translate_code(parent->frame_code(frame));
 305                 gc_info *info = compiled->block_gc_info();
 306
 307                 assert(return_address < compiled->size());
 308                 cell callsite = info->return_address_index(return_address);
 309                 if(callsite == (cell)-1)
 310                         return;
 311
 312 #ifdef DEBUG_GC_MAPS
 313                 std::cout << "call frame code block " << compiled << " with offset " << return_address << std::endl;
 314 #endif
 315                 cell *stack_pointer = (cell *)(parent->frame_successor(frame) + 1);
 316                 u8 *bitmap = info->gc_info_bitmap();
 317
 318                 /* Subtract old value of base pointer from every derived pointer. */
 319                 for(cell spill_slot = 0; spill_slot < info->derived_root_count; spill_slot++)
 320                 {
 321                         u32 base_pointer = info->lookup_base_pointer(callsite, spill_slot);
 322                         if(base_pointer != (u32)-1)
 323                         {
 324 #ifdef DEBUG_GC_MAPS
 325                                 std::cout << "visiting derived root " << spill_slot
 326                                         << " with base pointer " << base_pointer
 327                                         << std::endl;
 328 #endif
 329                                 stack_pointer[spill_slot] -= stack_pointer[base_pointer];
 330                         }
 331                 }
 332
 333                 /* Update all GC roots, including base pointers. */
 334                 cell callsite_gc_roots = info->callsite_gc_roots(callsite);
 335
 336                 for(cell spill_slot = 0; spill_slot < info->gc_root_count; spill_slot++)
 337                 {
 338                         if(bitmap_p(bitmap,callsite_gc_roots + spill_slot))
 339                         {
 340 #ifdef DEBUG_GC_MAPS
 341                                 std::cout << "visiting GC root " << spill_slot << std::endl;
 342 #endif
 343                                 visitor->visit_handle(stack_pointer + spill_slot);
 344                         }
 345                 }
 346
 347                 /* Add the base pointers to obtain new derived pointer values. */
 348                 for(cell spill_slot = 0; spill_slot < info->derived_root_count; spill_slot++)
 349                 {
 350                         u32 base_pointer = info->lookup_base_pointer(callsite, spill_slot);
 351                         if(base_pointer != (u32)-1)
 352                                 stack_pointer[spill_slot] += stack_pointer[base_pointer];
 353                 }
 354         }
 355 };
 356
 357 template<typename Fixup>
 358 void slot_visitor<Fixup>::visit_callstack_object(callstack *stack)
 359 {
 360         call_frame_slot_visitor<Fixup> call_frame_visitor(parent,this);
 361         parent->iterate_callstack_object(stack,call_frame_visitor);
 362 }
 363
 364 template<typename Fixup>
 365 void slot_visitor<Fixup>::visit_callstack(context *ctx)
 366 {
 367         call_frame_slot_visitor<Fixup> call_frame_visitor(parent,this);
 368         parent->iterate_callstack(ctx,call_frame_visitor);
 369 }
 370
 371 template<typename Fixup>
 372 void slot_visitor<Fixup>::visit_contexts()
 373 {
 374         std::set<context *>::const_iterator begin = parent->active_contexts.begin();
 375         std::set<context *>::const_iterator end = parent->active_contexts.end();
 376         while(begin != end)
 377         {
 378                 context *ctx = *begin;
 379
 380                 visit_stack_elements(ctx->datastack_seg,(cell *)ctx->datastack);
 381                 visit_stack_elements(ctx->retainstack_seg,(cell *)ctx->retainstack);
 382                 visit_object_array(ctx->context_objects,ctx->context_objects + context_object_count);
 383                 visit_callstack(ctx);
 384                 begin++;
 385         }
 386 }
 387
 388 template<typename Fixup>
 389 struct literal_references_visitor {
 390         slot_visitor<Fixup> *visitor;
 391
 392         explicit literal_references_visitor(slot_visitor<Fixup> *visitor_) : visitor(visitor_) {}
 393
 394         void operator()(instruction_operand op)
 395         {
 396                 if(op.rel_type() == RT_LITERAL)
 397                         op.store_value(visitor->visit_pointer(op.load_value()));
 398         }
 399 };
 400
 401 template<typename Fixup>
 402 void slot_visitor<Fixup>::visit_code_block_objects(code_block *compiled)
 403 {
 404         visit_handle(&compiled->owner);
 405         visit_handle(&compiled->parameters);
 406         visit_handle(&compiled->relocation);
 407 }
 408
 409 template<typename Fixup>
 410 void slot_visitor<Fixup>::visit_embedded_literals(code_block *compiled)
 411 {
 412         if(!parent->code->uninitialized_p(compiled))
 413         {
 414                 literal_references_visitor<Fixup> visitor(this);
 415                 compiled->each_instruction_operand(visitor);
 416         }
 417 }
 418
 419 }