vm/mark_bits.hpp

   1 namespace factor {
   2
   3 const int mark_bits_granularity = sizeof(cell) * 8;
   4 const int mark_bits_mask = sizeof(cell) * 8 - 1;
   5
   6 template <typename Block> struct mark_bits {
   7   cell size;
   8   cell start;
   9   cell bits_size;
  10   cell* marked;
  11   cell* forwarding;
  12
  13   void clear_mark_bits() { memset(marked, 0, bits_size * sizeof(cell)); }
  14
  15   void clear_forwarding() { memset(forwarding, 0, bits_size * sizeof(cell)); }
  16
  17   mark_bits(cell size_, cell start_)
  18       : size(size_),
  19         start(start_),
  20         bits_size(size / data_alignment / mark_bits_granularity),
  21         marked(new cell[bits_size]),
  22         forwarding(new cell[bits_size]) {
  23     clear_mark_bits();
  24     clear_forwarding();
  25   }
  26
  27   ~mark_bits() {
  28     delete[] marked;
  29     marked = NULL;
  30     delete[] forwarding;
  31     forwarding = NULL;
  32   }
  33
  34   cell block_line(const Block* address) {
  35     return (((cell) address - start) / data_alignment);
  36   }
  37
  38   Block* line_block(cell line) {
  39     return (Block*)(line * data_alignment + start);
  40   }
  41
  42   std::pair<cell, cell> bitmap_deref(const Block* address) {
  43     cell line_number = block_line(address);
  44     cell word_index = (line_number / mark_bits_granularity);
  45     cell word_shift = (line_number & mark_bits_mask);
  46     return std::make_pair(word_index, word_shift);
  47   }
  48
  49   bool bitmap_elt(cell* bits, const Block* address) {
  50     std::pair<cell, cell> position = bitmap_deref(address);
  51     return (bits[position.first] & ((cell) 1 << position.second)) != 0;
  52   }
  53
  54   Block* next_block_after(const Block* block) {
  55     return (Block*)((cell) block + block->size());
  56   }
  57
  58   void set_bitmap_range(cell* bits, const Block* address) {
  59     std::pair<cell, cell> start = bitmap_deref(address);
  60     std::pair<cell, cell> end = bitmap_deref(next_block_after(address));
  61
  62     cell start_mask = ((cell) 1 << start.second) - 1;
  63     cell end_mask = ((cell) 1 << end.second) - 1;
  64
  65     if (start.first == end.first)
  66       bits[start.first] |= start_mask ^ end_mask;
  67     else {
  68 #ifdef FACTOR_DEBUG
  69       FACTOR_ASSERT(start.first < bits_size);
  70 #endif
  71       bits[start.first] |= ~start_mask;
  72
  73       for (cell index = start.first + 1; index < end.first; index++)
  74         bits[index] = (cell) - 1;
  75
  76       if (end_mask != 0) {
  77 #ifdef FACTOR_DEBUG
  78         FACTOR_ASSERT(end.first < bits_size);
  79 #endif
  80         bits[end.first] |= end_mask;
  81       }
  82     }
  83   }
  84
  85   bool marked_p(const Block* address) { return bitmap_elt(marked, address); }
  86
  87   void set_marked_p(const Block* address) { set_bitmap_range(marked, address); }
  88
  89   /* The eventual destination of a block after compaction is just the number
  90      of marked blocks before it. Live blocks must be marked on entry. */
  91   void compute_forwarding() {
  92     cell accum = 0;
  93     for (cell index = 0; index < bits_size; index++) {
  94       forwarding[index] = accum;
  95       accum += popcount(marked[index]);
  96     }
  97   }
  98
  99   /* We have the popcount for every mark_bits_granularity entries; look
 100      up and compute the rest */
 101   Block* forward_block(const Block* original) {
 102 #ifdef FACTOR_DEBUG
 103     FACTOR_ASSERT(marked_p(original));
 104 #endif
 105     std::pair<cell, cell> position = bitmap_deref(original);
 106     cell offset = (cell) original & (data_alignment - 1);
 107
 108     cell approx_popcount = forwarding[position.first];
 109     cell mask = ((cell) 1 << position.second) - 1;
 110
 111     cell new_line_number =
 112         approx_popcount + popcount(marked[position.first] & mask);
 113     Block* new_block = (Block*)((char*)line_block(new_line_number) + offset);
 114 #ifdef FACTOR_DEBUG
 115     FACTOR_ASSERT(new_block <= original);
 116 #endif
 117     return new_block;
 118   }
 119
 120   Block* next_unmarked_block_after(const Block* original) {
 121     std::pair<cell, cell> position = bitmap_deref(original);
 122     cell bit_index = position.second;
 123
 124     for (cell index = position.first; index < bits_size; index++) {
 125       cell mask = ((fixnum) marked[index] >> bit_index);
 126       if (~mask) {
 127         /* Found an unmarked block on this page. Stop, it's hammer time */
 128         cell clear_bit = rightmost_clear_bit(mask);
 129         return line_block(index * mark_bits_granularity + bit_index +
 130                           clear_bit);
 131       } else {
 132         /* No unmarked blocks on this page. Keep looking */
 133         bit_index = 0;
 134       }
 135     }
 136
 137     /* No unmarked blocks were found */
 138     return (Block*)(this->start + this->size);
 139   }
 140
 141   Block* next_marked_block_after(const Block* original) {
 142     std::pair<cell, cell> position = bitmap_deref(original);
 143     cell bit_index = position.second;
 144
 145     for (cell index = position.first; index < bits_size; index++) {
 146       cell mask = (marked[index] >> bit_index);
 147       if (mask) {
 148         /* Found an marked block on this page. Stop, it's hammer time */
 149         cell set_bit = rightmost_set_bit(mask);
 150         return line_block(index * mark_bits_granularity + bit_index + set_bit);
 151       } else {
 152         /* No marked blocks on this page. Keep looking */
 153         bit_index = 0;
 154       }
 155     }
 156
 157     /* No marked blocks were found */
 158     return (Block*)(this->start + this->size);
 159   }
 160
 161   cell unmarked_block_size(Block* original) {
 162     Block* next_marked = next_marked_block_after(original);
 163     return ((char*)next_marked - (char*)original);
 164   }
 165 };
 166
 167 }