vm/mark_bits.hpp

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