vm/copying_collector.hpp

   1 namespace factor
   2 {
   3
   4 struct dummy_unmarker {
   5         void operator()(card *ptr) {}
   6 };
   7
   8 struct simple_unmarker {
   9         card unmask;
  10         simple_unmarker(card unmask_) : unmask(unmask_) {}
  11         void operator()(card *ptr) { *ptr &= ~unmask; }
  12 };
  13
  14 template<typename TargetGeneration, typename Policy>
  15 struct copying_collector : collector<TargetGeneration,Policy> {
  16         cell scan;
  17
  18         explicit copying_collector(factor_vm *myvm_, generation_statistics *stats_, TargetGeneration *target_, Policy policy_) :
  19                 collector<TargetGeneration,Policy>(myvm_,stats_,target_,policy_), scan(target_->here) {}
  20
  21         inline cell first_card_in_deck(cell deck)
  22         {
  23                 return deck << (deck_bits - card_bits);
  24         }
  25
  26         inline cell last_card_in_deck(cell deck)
  27         {
  28                 return first_card_in_deck(deck + 1);
  29         }
  30
  31         inline cell card_deck_for_address(cell a)
  32         {
  33                 return addr_to_deck(a - this->data->start);
  34         }
  35
  36         inline cell card_start_address(cell card)
  37         {
  38                 return (card << card_bits) + this->data->start;
  39         }
  40
  41         inline cell card_end_address(cell card)
  42         {
  43                 return ((card + 1) << card_bits) + this->data->start;
  44         }
  45
  46         void trace_partial_objects(cell start, cell end, cell card_start, cell card_end)
  47         {
  48                 if(card_start < end)
  49                 {
  50                         start += sizeof(cell);
  51
  52                         if(start < card_start) start = card_start;
  53                         if(end > card_end) end = card_end;
  54
  55                         cell *slot_ptr = (cell *)start;
  56                         cell *end_ptr = (cell *)end;
  57
  58                         if(slot_ptr != end_ptr)
  59                         {
  60                                 for(; slot_ptr < end_ptr; slot_ptr++)
  61                                         this->trace_handle(slot_ptr);
  62                         }
  63                 }
  64         }
  65
  66         template<typename SourceGeneration, typename Unmarker>
  67         void trace_cards(SourceGeneration *gen, card mask, Unmarker unmarker)
  68         {
  69                 u64 start_time = current_micros();
  70
  71                 card_deck *decks = this->data->decks;
  72                 card_deck *cards = this->data->cards;
  73
  74                 cell gen_start_card = addr_to_card(gen->start - this->data->start);
  75
  76                 cell first_deck = card_deck_for_address(gen->start);
  77                 cell last_deck = card_deck_for_address(gen->end);
  78
  79                 cell start = 0, binary_start = 0, end = 0;
  80
  81                 for(cell deck_index = first_deck; deck_index < last_deck; deck_index++)
  82                 {
  83                         if(decks[deck_index] & mask)
  84                         {
  85                                 this->myvm->gc_stats.decks_scanned++;
  86
  87                                 cell first_card = first_card_in_deck(deck_index);
  88                                 cell last_card = last_card_in_deck(deck_index);
  89
  90                                 for(cell card_index = first_card; card_index < last_card; card_index++)
  91                                 {
  92                                         if(cards[card_index] & mask)
  93                                         {
  94                                                 this->myvm->gc_stats.cards_scanned++;
  95
  96                                                 if(end < card_start_address(card_index))
  97                                                 {
  98                                                         start = gen->find_object_containing_card(card_index - gen_start_card);
  99                                                         binary_start = start + this->myvm->binary_payload_start((object *)start);
 100                                                         end = start + this->myvm->untagged_object_size((object *)start);
 101                                                 }
 102
 103 #ifdef FACTOR_DEBUG
 104                                                 assert(addr_to_card(start - this->data->start) <= card_index);
 105                                                 assert(start < card_end_address(card_index));
 106 #endif
 107
 108 scan_next_object:                               {
 109                                                         trace_partial_objects(
 110                                                                 start,
 111                                                                 binary_start,
 112                                                                 card_start_address(card_index),
 113                                                                 card_end_address(card_index));
 114                                                         if(end < card_end_address(card_index))
 115                                                         {
 116                                                                 start = gen->next_object_after(this->myvm,start);
 117                                                                 if(start)
 118                                                                 {
 119                                                                         binary_start = start + this->myvm->binary_payload_start((object *)start);
 120                                                                         end = start + this->myvm->untagged_object_size((object *)start);
 121                                                                         goto scan_next_object;
 122                                                                 }
 123                                                         }
 124                                                 }
 125
 126                                                 unmarker(&cards[card_index]);
 127
 128                                                 if(!start) goto end;
 129                                         }
 130                                 }
 131
 132                                 unmarker(&decks[deck_index]);
 133                         }
 134                 }
 135
 136 end:            this->myvm->gc_stats.card_scan_time += (current_micros() - start_time);
 137         }
 138
 139         /* Trace all literals referenced from a code block. Only for aging and nursery collections */
 140         void trace_literal_references(code_block *compiled)
 141         {
 142                 this->trace_handle(&compiled->owner);
 143                 this->trace_handle(&compiled->literals);
 144                 this->trace_handle(&compiled->relocation);
 145                 this->myvm->gc_stats.code_blocks_scanned++;
 146         }
 147
 148         void trace_code_heap_roots(std::set<code_block *> *remembered_set)
 149         {
 150                 std::set<code_block *>::const_iterator iter = remembered_set->begin();
 151                 std::set<code_block *>::const_iterator end = remembered_set->end();
 152
 153                 for(; iter != end; iter++) trace_literal_references(*iter);
 154         }
 155
 156         void cheneys_algorithm()
 157         {
 158                 while(scan && scan < this->target->here)
 159                 {
 160                         this->trace_slots((object *)scan);
 161                         scan = this->target->next_object_after(this->myvm,scan);
 162                 }
 163         }
 164 };
 165
 166 }