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* fixup_data(object* obj) {
  19     FACTOR_ASSERT((parent->current_gc &&
  20                    parent->current_gc->op == collect_growing_heap_op) ||
  21                   parent->data->seg->in_segment_p((cell)obj));
  22
  23     if (!policy.should_copy_p(obj)) {
  24       policy.visited_object(obj);
  25       return obj;
  26     }
  27
  28     /* is there another forwarding pointer? */
  29     while (obj->forwarding_pointer_p()) {
  30       object* dest = obj->forwarding_pointer();
  31       obj = dest;
  32     }
  33
  34     if (!policy.should_copy_p(obj)) {
  35       policy.visited_object(obj);
  36       return obj;
  37     }
  38
  39     cell size = obj->size();
  40     object* newpointer = target->allot(size);
  41     if (!newpointer)
  42       throw must_start_gc_again();
  43
  44     memcpy(newpointer, obj, size);
  45     obj->forward_to(newpointer);
  46
  47     policy.promoted_object(newpointer);
  48
  49     return newpointer;
  50   }
  51
  52   code_block* fixup_code(code_block* compiled) {
  53     if (!code->allocator->state.marked_p((cell)compiled)) {
  54       code->allocator->state.set_marked_p((cell)compiled, compiled->size());
  55       parent->mark_stack.push_back((cell)compiled + 1);
  56     }
  57
  58     return compiled;
  59   }
  60 };
  61
  62 template <typename TargetGeneration, typename Policy> struct collector {
  63   factor_vm* parent;
  64   data_heap* data;
  65   code_heap* code;
  66   TargetGeneration* target;
  67   gc_workhorse<TargetGeneration, Policy> workhorse;
  68   slot_visitor<gc_workhorse<TargetGeneration, Policy> > visitor;
  69   cell cards_scanned;
  70   cell decks_scanned;
  71   cell code_blocks_scanned;
  72   cell scan;
  73
  74   collector(factor_vm* parent, TargetGeneration* target, Policy policy)
  75       : parent(parent),
  76         data(parent->data),
  77         code(parent->code),
  78         target(target),
  79         workhorse(parent, target, policy),
  80         visitor(parent, workhorse),
  81         cards_scanned(0),
  82         decks_scanned(0),
  83         code_blocks_scanned(0) {
  84     scan = target->start + target->occupied_space();
  85   }
  86
  87   void trace_code_heap_roots(std::set<code_block*>* remembered_set) {
  88     std::set<code_block*>::const_iterator iter = remembered_set->begin();
  89     std::set<code_block*>::const_iterator end = remembered_set->end();
  90
  91     for (; iter != end; iter++) {
  92       code_block* compiled = *iter;
  93       visitor.visit_code_block_objects(compiled);
  94       visitor.visit_embedded_literals(compiled);
  95       compiled->flush_icache();
  96       code_blocks_scanned++;
  97     }
  98   }
  99
 100   void trace_partial_objects(cell start, cell card_start, cell card_end) {
 101     object* obj = (object*)start;
 102     cell end = start + obj->binary_payload_start();
 103     if (card_start < end) {
 104       start += sizeof(cell);
 105
 106       start = std::max(start, card_start);
 107       end = std::min(end, card_end);
 108
 109       cell* slot_ptr = (cell*)start;
 110       cell* end_ptr = (cell*)end;
 111
 112       for (; slot_ptr < end_ptr; slot_ptr++)
 113         visitor.visit_handle(slot_ptr);
 114     }
 115   }
 116
 117   template <typename SourceGeneration>
 118   cell trace_card(SourceGeneration* gen, cell index, cell start) {
 119
 120     cell start_addr = data->start + index * card_size;
 121     cell end_addr = start_addr + card_size;
 122
 123     if (!start || (start + ((object*)start)->size()) < start_addr) {
 124       /* Optimization because finding the objects in a memory range is
 125          expensive. It helps a lot when tracing consecutive cards. */
 126       cell gen_start_card = (gen->start - data->start) / card_size;
 127       start = gen->starts
 128           .find_object_containing_card(index - gen_start_card);
 129     }
 130
 131     while (start && start < end_addr) {
 132       trace_partial_objects(start, start_addr, end_addr);
 133       if ((start + ((object*)start)->size()) >= end_addr) {
 134         /* The object can overlap the card boundary, then the
 135            remainder of it will be handled in the next card
 136            tracing if that card is marked. */
 137         break;
 138       }
 139       start = gen->next_object_after(start);
 140     }
 141     return start;
 142   }
 143
 144   template <typename SourceGeneration>
 145   void trace_cards(SourceGeneration* gen, card mask, card unmask) {
 146     card_deck* decks = data->decks;
 147     card_deck* cards = data->cards;
 148
 149     cell first_deck = (gen->start - data->start) / deck_size;
 150     cell last_deck = (gen->end - data->start) / deck_size;
 151
 152     /* Address of last traced object. */
 153     cell start = 0;
 154
 155     for (cell deck_index = first_deck; deck_index < last_deck; deck_index++) {
 156       if (decks[deck_index] & mask) {
 157         decks[deck_index] &= ~unmask;
 158         decks_scanned++;
 159
 160         cell first_card = cards_per_deck * deck_index;
 161         cell last_card = first_card + cards_per_deck;
 162
 163         for (cell card_index = first_card; card_index < last_card;
 164              card_index++) {
 165           if (cards[card_index] & mask) {
 166             cards[card_index] &= ~unmask;
 167             cards_scanned++;
 168
 169             start = trace_card(gen, card_index, start);
 170             if (!start) {
 171               /* At end of generation, no need to scan more cards. */
 172               return;
 173             }
 174           }
 175         }
 176       }
 177     }
 178   }
 179
 180   void cheneys_algorithm() {
 181     while (scan && scan < this->target->here) {
 182       this->visitor.visit_object((object*)scan);
 183       scan = this->target->next_object_after(scan);
 184     }
 185   }
 186 };
 187
 188 }