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 /* The eventual destination of a block after compaction is just the number
113 of marked blocks before it. Live blocks must be marked on entry. */
114 void compute_forwarding()
117 for(cell index = 0; index < bits_size; index++)
119 forwarding[index] = accum;
120 accum += popcount(marked[index]);
124 /* We have the popcount for every 64 entries; look up and compute the rest */
125 Block *forward_block(Block *original)
128 assert(marked_p(original));
130 std::pair<cell,cell> position = bitmap_deref(original);
132 cell approx_popcount = forwarding[position.first];
133 u64 mask = ((u64)1 << position.second) - 1;
135 cell new_line_number = approx_popcount + popcount(marked[position.first] & mask);
136 Block *new_block = line_block(new_line_number);
138 assert(new_block <= original);
143 Block *next_unmarked_block_after(Block *original)
145 std::pair<cell,cell> position = bitmap_deref(original);
146 cell bit_index = position.second;
148 for(cell index = position.first; index < bits_size; index++)
150 u64 mask = ((s64)marked[index] >> bit_index);
153 /* Found an unmarked block on this page.
154 Stop, it's hammer time */
155 cell clear_bit = rightmost_clear_bit(mask);
156 return line_block(index * 64 + bit_index + clear_bit);
160 /* No unmarked blocks on this page.
166 /* No unmarked blocks were found */
167 return (Block *)(this->start + this->size);
170 Block *next_marked_block_after(Block *original)
172 std::pair<cell,cell> position = bitmap_deref(original);
173 cell bit_index = position.second;
175 for(cell index = position.first; index < bits_size; index++)
177 u64 mask = (marked[index] >> bit_index);
180 /* Found an marked block on this page.
181 Stop, it's hammer time */
182 cell set_bit = rightmost_set_bit(mask);
183 return line_block(index * 64 + bit_index + set_bit);
187 /* No marked blocks on this page.
193 /* No marked blocks were found */
194 return (Block *)(this->start + this->size);
197 cell unmarked_block_size(Block *original)
199 Block *next_marked = next_marked_block_after(original);
200 return ((char *)next_marked - (char *)original);