vm/collector.hpp

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