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