4 const int block_granularity = 16;
5 const int forwarding_granularity = 64;
7 template<typename Block> struct mark_bits {
14 void clear_mark_bits()
16 memset(marked,0,bits_size * sizeof(u64));
19 void clear_forwarding()
21 memset(forwarding,0,bits_size * sizeof(cell));
24 explicit mark_bits(cell size_, cell start_) :
27 bits_size(size / block_granularity / forwarding_granularity),
28 marked(new u64[bits_size]),
29 forwarding(new cell[bits_size])
43 cell block_line(Block *address)
45 return (((cell)address - start) / block_granularity);
48 Block *line_block(cell line)
50 return (Block *)(line * block_granularity + start);
53 std::pair<cell,cell> bitmap_deref(Block *address)
55 cell line_number = block_line(address);
56 cell word_index = (line_number >> 6);
57 cell word_shift = (line_number & 63);
58 return std::make_pair(word_index,word_shift);
61 bool bitmap_elt(u64 *bits, Block *address)
63 std::pair<cell,cell> position = bitmap_deref(address);
64 return (bits[position.first] & ((u64)1 << position.second)) != 0;
67 Block *next_block_after(Block *block)
69 return (Block *)((cell)block + block->size());
72 void set_bitmap_range(u64 *bits, Block *address)
74 std::pair<cell,cell> start = bitmap_deref(address);
75 std::pair<cell,cell> end = bitmap_deref(next_block_after(address));
77 u64 start_mask = ((u64)1 << start.second) - 1;
78 u64 end_mask = ((u64)1 << end.second) - 1;
80 if(start.first == end.first)
81 bits[start.first] |= start_mask ^ end_mask;
85 assert(start.first < bits_size);
87 bits[start.first] |= ~start_mask;
89 for(cell index = start.first + 1; index < end.first; index++)
90 bits[index] = (u64)-1;
95 assert(end.first < bits_size);
97 bits[end.first] |= end_mask;
102 bool marked_p(Block *address)
104 return bitmap_elt(marked,address);
107 void set_marked_p(Block *address)
109 set_bitmap_range(marked,address);
112 /* From http://chessprogramming.wikispaces.com/Population+Count */
115 u64 k1 = 0x5555555555555555ll;
116 u64 k2 = 0x3333333333333333ll;
117 u64 k4 = 0x0f0f0f0f0f0f0f0fll;
118 u64 kf = 0x0101010101010101ll;
119 x = x - ((x >> 1) & k1); // put count of each 2 bits into those 2 bits
120 x = (x & k2) + ((x >> 2) & k2); // put count of each 4 bits into those 4 bits
121 x = (x + (x >> 4)) & k4 ; // put count of each 8 bits into those 8 bits
122 x = (x * kf) >> 56; // returns 8 most significant bits of x + (x<<8) + (x<<16) + (x<<24) + ...
127 /* The eventual destination of a block after compaction is just the number
128 of marked blocks before it. Live blocks must be marked on entry. */
129 void compute_forwarding()
132 for(cell index = 0; index < bits_size; index++)
134 forwarding[index] = accum;
135 accum += popcount(marked[index]);
139 /* We have the popcount for every 64 entries; look up and compute the rest */
140 Block *forward_block(Block *original)
143 assert(marked_p(original));
145 std::pair<cell,cell> position = bitmap_deref(original);
147 cell approx_popcount = forwarding[position.first];
148 u64 mask = ((u64)1 << position.second) - 1;
150 cell new_line_number = approx_popcount + popcount(marked[position.first] & mask);
151 Block *new_block = line_block(new_line_number);
153 assert(new_block <= original);
158 cell rightmost_clear_bit(u64 x)
169 Block *next_unmarked_block_after_slow(Block *original)
171 char *scan = (char *)original;
172 char *end = (char *)(this->start + this->size);
174 while(scan != end && marked_p((Block *)scan))
175 scan += block_granularity;
177 return (Block *)scan;
180 Block *next_unmarked_block_after_fast(Block *original)
182 std::pair<cell,cell> position = bitmap_deref(original);
183 cell bit_index = position.second;
185 for(cell index = position.first; index < bits_size; index++)
187 u64 mask = ((s64)marked[index] >> bit_index);
190 /* Found an unmarked block on this page.
191 Stop, it's hammer time */
192 cell clear_bit = rightmost_clear_bit(mask);
193 return line_block(index * 64 + bit_index + clear_bit);
197 /* No unmarked blocks on this page.
203 /* No unmarked blocks were found */
204 return (Block *)(this->start + this->size);
207 Block *next_unmarked_block_after(Block *original)
209 Block *first_result = next_unmarked_block_after_slow(original);
210 Block *second_result = next_unmarked_block_after_fast(original);
211 assert(first_result == second_result);
212 return second_result;
215 Block *next_marked_block_after(Block *original)
217 char *scan = (char *)original;
218 char *end = (char *)(this->start + this->size);
220 while(scan != end && !marked_p((Block *)scan))
221 scan += block_granularity;
223 return (Block *)scan;
226 cell unmarked_block_size(Block *original)
228 Block *next_marked = next_marked_block_after(original);
229 return ((char *)next_marked - (char *)original);