4 const int mark_bits_granularity = sizeof(cell) * 8;
5 const int mark_bits_mask = sizeof(cell) * 8 - 1;
7 template<typename Block> struct mark_bits {
14 void clear_mark_bits()
16 memset(marked,0,bits_size * sizeof(cell));
19 void clear_forwarding()
21 memset(forwarding,0,bits_size * sizeof(cell));
24 explicit mark_bits(cell size_, cell start_) :
27 bits_size(size / data_alignment / mark_bits_granularity),
28 marked(new cell[bits_size]),
29 forwarding(new cell[bits_size])
43 cell block_line(const Block *address)
45 return (((cell)address - start) / data_alignment);
48 Block *line_block(cell line)
50 return (Block *)(line * data_alignment + start);
53 std::pair<cell,cell> bitmap_deref(const Block *address)
55 cell line_number = block_line(address);
56 cell word_index = (line_number / mark_bits_granularity);
57 cell word_shift = (line_number & mark_bits_mask);
58 return std::make_pair(word_index,word_shift);
61 bool bitmap_elt(cell *bits, const Block *address)
63 std::pair<cell,cell> position = bitmap_deref(address);
64 return (bits[position.first] & ((cell)1 << position.second)) != 0;
67 Block *next_block_after(const Block *block)
69 return (Block *)((cell)block + block->size());
72 void set_bitmap_range(cell *bits, const Block *address)
74 std::pair<cell,cell> start = bitmap_deref(address);
75 std::pair<cell,cell> end = bitmap_deref(next_block_after(address));
77 cell start_mask = ((cell)1 << start.second) - 1;
78 cell end_mask = ((cell)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] = (cell)-1;
95 assert(end.first < bits_size);
97 bits[end.first] |= end_mask;
102 bool marked_p(const Block *address)
104 return bitmap_elt(marked,address);
107 void set_marked_p(const 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 mark_bits_granularity entries; look
125 up and compute the rest */
126 Block *forward_block(const Block *original)
129 assert(marked_p(original));
131 std::pair<cell,cell> position = bitmap_deref(original);
133 cell approx_popcount = forwarding[position.first];
134 cell mask = ((cell)1 << position.second) - 1;
136 cell new_line_number = approx_popcount + popcount(marked[position.first] & mask);
137 Block *new_block = line_block(new_line_number);
139 assert(new_block <= original);
144 Block *next_unmarked_block_after(const Block *original)
146 std::pair<cell,cell> position = bitmap_deref(original);
147 cell bit_index = position.second;
149 for(cell index = position.first; index < bits_size; index++)
151 cell mask = ((fixnum)marked[index] >> bit_index);
154 /* Found an unmarked block on this page.
155 Stop, it's hammer time */
156 cell clear_bit = rightmost_clear_bit(mask);
157 return line_block(index * mark_bits_granularity + bit_index + clear_bit);
161 /* No unmarked blocks on this page.
167 /* No unmarked blocks were found */
168 return (Block *)(this->start + this->size);
171 Block *next_marked_block_after(const Block *original)
173 std::pair<cell,cell> position = bitmap_deref(original);
174 cell bit_index = position.second;
176 for(cell index = position.first; index < bits_size; index++)
178 cell mask = (marked[index] >> bit_index);
181 /* Found an marked block on this page.
182 Stop, it's hammer time */
183 cell set_bit = rightmost_set_bit(mask);
184 return line_block(index * mark_bits_granularity + bit_index + set_bit);
188 /* No marked blocks on this page.
194 /* No marked blocks were found */
195 return (Block *)(this->start + this->size);
198 cell unmarked_block_size(Block *original)
200 Block *next_marked = next_marked_block_after(original);
201 return ((char *)next_marked - (char *)original);