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