vm/collector.hpp

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