vm/mark_bits.hpp

   1 namespace factor
   2 {
   3
   4 const int forwarding_granularity = 64;
   5
   6 template<typename Block, int Granularity> struct mark_bits {
   7         cell start;
   8         cell size;
   9         cell bits_size;
  10         u64 *marked;
  11         u64 *allocated;
  12         cell *forwarding;
  13
  14         void clear_mark_bits()
  15         {
  16                 memset(marked,0,bits_size * sizeof(u64));
  17         }
  18
  19         void clear_allocated_bits()
  20         {
  21                 memset(allocated,0,bits_size * sizeof(u64));
  22         }
  23
  24         void clear_forwarding()
  25         {
  26                 memset(forwarding,0,bits_size * sizeof(cell));
  27         }
  28
  29         explicit mark_bits(cell start_, cell size_) :
  30                 start(start_),
  31                 size(size_),
  32                 bits_size(size / Granularity / forwarding_granularity),
  33                 marked(new u64[bits_size]),
  34                 allocated(new u64[bits_size]),
  35                 forwarding(new cell[bits_size])
  36         {
  37                 clear_mark_bits();
  38                 clear_allocated_bits();
  39                 clear_forwarding();
  40         }
  41
  42         ~mark_bits()
  43         {
  44                 delete[] marked;
  45                 marked = NULL;
  46                 delete[] allocated;
  47                 allocated = NULL;
  48                 delete[] forwarding;
  49                 forwarding = NULL;
  50         }
  51
  52         cell block_line(Block *address)
  53         {
  54                 return (((cell)address - start) / Granularity);
  55         }
  56
  57         Block *line_block(cell line)
  58         {
  59                 return (Block *)(line * Granularity + start);
  60         }
  61
  62         std::pair<cell,cell> bitmap_deref(Block *address)
  63         {
  64                 cell line_number = block_line(address);
  65                 cell word_index = (line_number >> 6);
  66                 cell word_shift = (line_number & 63);
  67
  68 #ifdef FACTOR_DEBUG
  69                 assert(word_index < bits_size);
  70 #endif
  71
  72                 return std::make_pair(word_index,word_shift);
  73         }
  74
  75         bool bitmap_elt(u64 *bits, Block *address)
  76         {
  77                 std::pair<cell,cell> pair = bitmap_deref(address);
  78                 return (bits[pair.first] & ((u64)1 << pair.second)) != 0;
  79         }
  80
  81         void set_bitmap_range(u64 *bits, Block *address)
  82         {
  83                 std::pair<cell,cell> start = bitmap_deref(address);
  84                 std::pair<cell,cell> end = bitmap_deref(address->next());
  85
  86                 u64 start_mask = ((u64)1 << start.second) - 1;
  87                 u64 end_mask = ((u64)1 << end.second) - 1;
  88
  89                 if(start.first == end.first)
  90                         bits[start.first] |= start_mask ^ end_mask;
  91                 else
  92                 {
  93                         bits[start.first] |= ~start_mask;
  94
  95                         if(end.first != 0)
  96                         {
  97                                 for(cell index = start.first + 1; index < end.first - 1; index++)
  98                                         bits[index] = (u64)-1;
  99                         }
 100
 101                         bits[end.first] |= end_mask;
 102                 }
 103         }
 104
 105         bool is_marked_p(Block *address)
 106         {
 107                 return bitmap_elt(marked,address);
 108         }
 109
 110         void set_marked_p(Block *address)
 111         {
 112                 set_bitmap_range(marked,address);
 113         }
 114
 115         bool is_allocated_p(Block *address)
 116         {
 117                 return bitmap_elt(allocated,address);
 118         }
 119
 120         void set_allocated_p(Block *address)
 121         {
 122                 set_bitmap_range(allocated,address);
 123         }
 124
 125         cell popcount1(u64 x)
 126         {
 127                 cell accum = 0;
 128                 while(x > 0)
 129                 {
 130                         accum += (x & 1);
 131                         x >>= 1;
 132                 }
 133                 return accum;
 134         }
 135
 136         /* From http://chessprogramming.wikispaces.com/Population+Count */
 137         cell popcount(u64 x)
 138         {
 139                 cell old = x;
 140                 u64 k1 = 0x5555555555555555ll;
 141                 u64 k2 = 0x3333333333333333ll;
 142                 u64 k4 = 0x0f0f0f0f0f0f0f0fll;
 143                 u64 kf = 0x0101010101010101ll;
 144                 x =  x       - ((x >> 1)  & k1); // put count of each 2 bits into those 2 bits
 145                 x = (x & k2) + ((x >> 2)  & k2); // put count of each 4 bits into those 4 bits
 146                 x = (x       +  (x >> 4)) & k4 ; // put count of each 8 bits into those 8 bits
 147                 x = (x * kf) >> 56; // returns 8 most significant bits of x + (x<<8) + (x<<16) + (x<<24) + ...
 148
 149                 assert(x == popcount1(old));
 150                 return (cell)x;
 151         }
 152
 153         /* The eventual destination of a block after compaction is just the number
 154         of marked blocks before it. */
 155         void compute_forwarding()
 156         {
 157                 cell accum = 0;
 158                 for(cell index = 0; index < bits_size; index++)
 159                 {
 160                         forwarding[index] = accum;
 161                         accum += popcount(marked[index]);
 162                 }
 163         }
 164
 165         /* We have the popcount for every 64 entries; look up and compute the rest */
 166         Block *forward_block(Block *original)
 167         {
 168                 std::pair<cell,cell> pair = bitmap_deref(original);
 169
 170                 cell approx_popcount = forwarding[pair.first];
 171                 u64 mask = ((u64)1 << pair.second) - 1;
 172
 173                 cell new_line_number = approx_popcount + popcount(marked[pair.first] & mask);
 174                 return line_block(new_line_number);
 175         }
 176 };
 177
 178 }