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 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(cell address) {
  35     return (address - start) / data_alignment;
  36   }
  37
  38   cell line_block(cell line) {
  39     return line * data_alignment + start;
  40   }
  41
  42   std::pair<cell, cell> bitmap_deref(const cell 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 cell address) {
  50     std::pair<cell, cell> position = bitmap_deref(address);
  51     return (bits[position.first] & ((cell)1 << position.second)) != 0;
  52   }
  53
  54   void set_bitmap_range(cell* bits, const cell address, const cell size) {
  55     std::pair<cell, cell> start = bitmap_deref(address);
  56     std::pair<cell, cell> end = bitmap_deref(address + size);
  57
  58     cell start_mask = ((cell)1 << start.second) - 1;
  59     cell end_mask = ((cell)1 << end.second) - 1;
  60
  61     if (start.first == end.first)
  62       bits[start.first] |= start_mask ^ end_mask;
  63     else {
  64       FACTOR_ASSERT(start.first < bits_size);
  65       bits[start.first] |= ~start_mask;
  66
  67       for (cell index = start.first + 1; index < end.first; index++)
  68         bits[index] = (cell)-1;
  69
  70       if (end_mask != 0) {
  71         FACTOR_ASSERT(end.first < bits_size);
  72         bits[end.first] |= end_mask;
  73       }
  74     }
  75   }
  76
  77   bool marked_p(const cell address) { return bitmap_elt(marked, address); }
  78
  79   void set_marked_p(const cell address, const cell size) {
  80     set_bitmap_range(marked, address, size);
  81   }
  82
  83   // The eventual destination of a block after compaction is just the number
  84   // of marked blocks before it. Live blocks must be marked on entry.
  85   void compute_forwarding() {
  86     cell accum = 0;
  87     for (cell index = 0; index < bits_size; index++) {
  88       forwarding[index] = accum;
  89       accum += popcount(marked[index]);
  90     }
  91   }
  92
  93   // We have the popcount for every mark_bits_granularity entries; look
  94   // up and compute the rest
  95   cell forward_block(const cell original) {
  96     FACTOR_ASSERT(marked_p(original));
  97     std::pair<cell, cell> position = bitmap_deref(original);
  98     cell offset = original & (data_alignment - 1);
  99
 100     cell approx_popcount = forwarding[position.first];
 101     cell mask = ((cell)1 << position.second) - 1;
 102
 103     cell new_line_number =
 104         approx_popcount + popcount(marked[position.first] & mask);
 105     cell new_block = line_block(new_line_number) + offset;
 106     FACTOR_ASSERT(new_block <= original);
 107     return new_block;
 108   }
 109
 110   cell next_unmarked_block_after(const cell original) {
 111     std::pair<cell, cell> position = bitmap_deref(original);
 112     cell bit_index = position.second;
 113
 114     for (cell index = position.first; index < bits_size; index++) {
 115       cell mask = ((fixnum)marked[index] >> bit_index);
 116       if (~mask) {
 117         // Found an unmarked block on this page. Stop, it's hammer time
 118         cell clear_bit = rightmost_clear_bit(mask);
 119         return line_block(index * mark_bits_granularity + bit_index +
 120                           clear_bit);
 121       }
 122       // No unmarked blocks on this page. Keep looking
 123       bit_index = 0;
 124     }
 125
 126     // No unmarked blocks were found
 127     return this->start + this->size;
 128   }
 129
 130   cell next_marked_block_after(const cell original) {
 131     std::pair<cell, cell> position = bitmap_deref(original);
 132     cell bit_index = position.second;
 133
 134     for (cell index = position.first; index < bits_size; index++) {
 135       cell mask = (marked[index] >> bit_index);
 136       if (mask) {
 137         // Found an marked block on this page. Stop, it's hammer time
 138         cell set_bit = rightmost_set_bit(mask);
 139         return line_block(index * mark_bits_granularity + bit_index + set_bit);
 140       }
 141       // No marked blocks on this page. Keep looking
 142       bit_index = 0;
 143     }
 144
 145     // No marked blocks were found
 146     return this->start + this->size;
 147   }
 148
 149   cell unmarked_block_size(cell original) {
 150     cell next_marked = next_marked_block_after(original);
 151     return next_marked - original;
 152   }
 153 };
 154
 155 }