vm/mark_bits.hpp

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