vm/mark_bits.hpp

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