vm/collector.hpp

   1 namespace factor
   2 {
   3
   4 struct must_start_gc_again {};
   5
   6 template<typename TargetGeneration, typename Policy> struct data_workhorse {
   7         factor_vm *parent;
   8         TargetGeneration *target;
   9         Policy policy;
  10
  11         explicit data_workhorse(factor_vm *parent_, TargetGeneration *target_, Policy policy_) :
  12                 parent(parent_),
  13                 target(target_),
  14                 policy(policy_) {}
  15
  16         object *resolve_forwarding(object *untagged)
  17         {
  18                 parent->check_data_pointer(untagged);
  19
  20                 /* is there another forwarding pointer? */
  21                 while(untagged->forwarding_pointer_p())
  22                         untagged = untagged->forwarding_pointer();
  23
  24                 /* we've found the destination */
  25                 return untagged;
  26         }
  27
  28         object *promote_object(object *untagged)
  29         {
  30                 cell size = untagged->size();
  31                 object *newpointer = target->allot(size);
  32                 if(!newpointer) throw must_start_gc_again();
  33
  34                 memcpy(newpointer,untagged,size);
  35                 untagged->forward_to(newpointer);
  36
  37                 policy.promoted_object(newpointer);
  38
  39                 return newpointer;
  40         }
  41
  42         object *operator()(object *obj)
  43         {
  44                 if(!policy.should_copy_p(obj))
  45                 {
  46                         policy.visited_object(obj);
  47                         return obj;
  48                 }
  49
  50                 object *forwarding = resolve_forwarding(obj);
  51
  52                 if(forwarding == obj)
  53                         return promote_object(obj);
  54                 else if(policy.should_copy_p(forwarding))
  55                         return promote_object(forwarding);
  56                 else
  57                 {
  58                         policy.visited_object(forwarding);
  59                         return forwarding;
  60                 }
  61         }
  62 };
  63
  64 template<typename TargetGeneration, typename Policy>
  65 inline static slot_visitor<data_workhorse<TargetGeneration,Policy> > make_data_visitor(
  66         factor_vm *parent,
  67         TargetGeneration *target,
  68         Policy policy)
  69 {
  70         return slot_visitor<data_workhorse<TargetGeneration,Policy> >(parent,
  71                 data_workhorse<TargetGeneration,Policy>(parent,target,policy));
  72 }
  73
  74 struct dummy_unmarker {
  75         void operator()(card *ptr) {}
  76 };
  77
  78 struct simple_unmarker {
  79         card unmask;
  80         explicit simple_unmarker(card unmask_) : unmask(unmask_) {}
  81         void operator()(card *ptr) { *ptr &= ~unmask; }
  82 };
  83
  84 struct full_unmarker {
  85         explicit full_unmarker() {}
  86         void operator()(card *ptr) { *ptr = 0; }
  87 };
  88
  89 template<typename TargetGeneration, typename Policy>
  90 struct collector {
  91         factor_vm *parent;
  92         data_heap *data;
  93         code_heap *code;
  94         TargetGeneration *target;
  95         slot_visitor<data_workhorse<TargetGeneration,Policy> > data_visitor;
  96         cell cards_scanned;
  97         cell decks_scanned;
  98         cell code_blocks_scanned;
  99
 100         explicit collector(factor_vm *parent_, TargetGeneration *target_, Policy policy_) :
 101                 parent(parent_),
 102                 data(parent_->data),
 103                 code(parent_->code),
 104                 target(target_),
 105                 data_visitor(make_data_visitor(parent_,target_,policy_)),
 106                 cards_scanned(0),
 107                 decks_scanned(0),
 108                 code_blocks_scanned(0) {}
 109
 110         void trace_handle(cell *handle)
 111         {
 112                 data_visitor.visit_handle(handle);
 113         }
 114
 115         void trace_object(object *ptr)
 116         {
 117                 data_visitor.visit_slots(ptr);
 118                 if(ptr->type() == ALIEN_TYPE)
 119                         ((alien *)ptr)->update_address();
 120         }
 121
 122         void trace_roots()
 123         {
 124                 data_visitor.visit_roots();
 125         }
 126
 127         void trace_contexts()
 128         {
 129                 data_visitor.visit_contexts();
 130         }
 131
 132         void trace_code_block_objects(code_block *compiled)
 133         {
 134                 data_visitor.visit_code_block_objects(compiled);
 135         }
 136
 137         void trace_embedded_literals(code_block *compiled)
 138         {
 139                 data_visitor.visit_embedded_literals(compiled);
 140         }
 141
 142         void trace_code_heap_roots(std::set<code_block *> *remembered_set)
 143         {
 144                 std::set<code_block *>::const_iterator iter = remembered_set->begin();
 145                 std::set<code_block *>::const_iterator end = remembered_set->end();
 146
 147                 for(; iter != end; iter++)
 148                 {
 149                         code_block *compiled = *iter;
 150                         trace_code_block_objects(compiled);
 151                         trace_embedded_literals(compiled);
 152                         compiled->flush_icache();
 153                         code_blocks_scanned++;
 154                 }
 155         }
 156
 157         inline cell first_card_in_deck(cell deck)
 158         {
 159                 return deck << (deck_bits - card_bits);
 160         }
 161
 162         inline cell last_card_in_deck(cell deck)
 163         {
 164                 return first_card_in_deck(deck + 1);
 165         }
 166
 167         inline cell card_deck_for_address(cell a)
 168         {
 169                 return addr_to_deck(a - data->start);
 170         }
 171
 172         inline cell card_start_address(cell card)
 173         {
 174                 return (card << card_bits) + data->start;
 175         }
 176
 177         inline cell card_end_address(cell card)
 178         {
 179                 return ((card + 1) << card_bits) + data->start;
 180         }
 181
 182         void trace_partial_objects(cell start, cell end, cell card_start, cell card_end)
 183         {
 184                 if(card_start < end)
 185                 {
 186                         start += sizeof(cell);
 187
 188                         if(start < card_start) start = card_start;
 189                         if(end > card_end) end = card_end;
 190
 191                         cell *slot_ptr = (cell *)start;
 192                         cell *end_ptr = (cell *)end;
 193
 194                         for(; slot_ptr < end_ptr; slot_ptr++)
 195                                 data_visitor.visit_handle(slot_ptr);
 196                 }
 197         }
 198
 199         template<typename SourceGeneration, typename Unmarker>
 200         void trace_cards(SourceGeneration *gen, card mask, Unmarker unmarker)
 201         {
 202                 card_deck *decks = data->decks;
 203                 card_deck *cards = data->cards;
 204
 205                 cell gen_start_card = addr_to_card(gen->start - data->start);
 206
 207                 cell first_deck = card_deck_for_address(gen->start);
 208                 cell last_deck = card_deck_for_address(gen->end);
 209
 210                 cell start = 0, binary_start = 0, end = 0;
 211
 212                 for(cell deck_index = first_deck; deck_index < last_deck; deck_index++)
 213                 {
 214                         if(decks[deck_index] & mask)
 215                         {
 216                                 decks_scanned++;
 217
 218                                 cell first_card = first_card_in_deck(deck_index);
 219                                 cell last_card = last_card_in_deck(deck_index);
 220
 221                                 for(cell card_index = first_card; card_index < last_card; card_index++)
 222                                 {
 223                                         if(cards[card_index] & mask)
 224                                         {
 225                                                 cards_scanned++;
 226
 227                                                 if(end < card_start_address(card_index))
 228                                                 {
 229                                                         start = gen->starts.find_object_containing_card(card_index - gen_start_card);
 230                                                         binary_start = start + ((object *)start)->binary_payload_start();
 231                                                         end = start + ((object *)start)->size();
 232                                                 }
 233
 234 scan_next_object:                               if(start < card_end_address(card_index))
 235                                                 {
 236                                                         trace_partial_objects(
 237                                                                 start,
 238                                                                 binary_start,
 239                                                                 card_start_address(card_index),
 240                                                                 card_end_address(card_index));
 241                                                         if(end < card_end_address(card_index))
 242                                                         {
 243                                                                 start = gen->next_object_after(start);
 244                                                                 if(start)
 245                                                                 {
 246                                                                         binary_start = start + ((object *)start)->binary_payload_start();
 247                                                                         end = start + ((object *)start)->size();
 248                                                                         goto scan_next_object;
 249                                                                 }
 250                                                         }
 251                                                 }
 252
 253                                                 unmarker(&cards[card_index]);
 254
 255                                                 if(!start) return;
 256                                         }
 257                                 }
 258
 259                                 unmarker(&decks[deck_index]);
 260                         }
 261                 }
 262         }
 263 };
 264
 265 }