3 const int mark_bits_granularity = sizeof(cell) * 8;
4 const int mark_bits_mask = sizeof(cell) * 8 - 1;
6 template <typename Block> struct mark_bits {
13 void clear_mark_bits() { memset(marked, 0, bits_size * sizeof(cell)); }
15 void clear_forwarding() { memset(forwarding, 0, bits_size * sizeof(cell)); }
17 explicit mark_bits(cell size_, cell start_)
20 bits_size(size / data_alignment / mark_bits_granularity),
21 marked(new cell[bits_size]),
22 forwarding(new cell[bits_size]) {
34 cell block_line(const Block* address) {
35 return (((cell) address - start) / data_alignment);
38 Block* line_block(cell line) {
39 return (Block*)(line * data_alignment + start);
42 std::pair<cell, cell> bitmap_deref(const Block* address) {
43 cell line_number = block_line(address);
44 cell word_index = (line_number / mark_bits_granularity);
45 cell word_shift = (line_number & mark_bits_mask);
46 return std::make_pair(word_index, word_shift);
49 bool bitmap_elt(cell* bits, const Block* address) {
50 std::pair<cell, cell> position = bitmap_deref(address);
51 return (bits[position.first] & ((cell) 1 << position.second)) != 0;
54 Block* next_block_after(const Block* block) {
55 return (Block*)((cell) block + block->size());
58 void set_bitmap_range(cell* bits, const Block* address) {
59 std::pair<cell, cell> start = bitmap_deref(address);
60 std::pair<cell, cell> end = bitmap_deref(next_block_after(address));
62 cell start_mask = ((cell) 1 << start.second) - 1;
63 cell end_mask = ((cell) 1 << end.second) - 1;
65 if (start.first == end.first)
66 bits[start.first] |= start_mask ^ end_mask;
69 FACTOR_ASSERT(start.first < bits_size);
71 bits[start.first] |= ~start_mask;
73 for (cell index = start.first + 1; index < end.first; index++)
74 bits[index] = (cell) - 1;
78 FACTOR_ASSERT(end.first < bits_size);
80 bits[end.first] |= end_mask;
85 bool marked_p(const Block* address) { return bitmap_elt(marked, address); }
87 void set_marked_p(const Block* address) { set_bitmap_range(marked, address); }
89 /* The eventual destination of a block after compaction is just the number
90 of marked blocks before it. Live blocks must be marked on entry. */
91 void compute_forwarding() {
93 for (cell index = 0; index < bits_size; index++) {
94 forwarding[index] = accum;
95 accum += popcount(marked[index]);
99 /* We have the popcount for every mark_bits_granularity entries; look
100 up and compute the rest */
101 Block* forward_block(const Block* original) {
103 FACTOR_ASSERT(marked_p(original));
105 std::pair<cell, cell> position = bitmap_deref(original);
106 cell offset = (cell) original & (data_alignment - 1);
108 cell approx_popcount = forwarding[position.first];
109 cell mask = ((cell) 1 << position.second) - 1;
111 cell new_line_number =
112 approx_popcount + popcount(marked[position.first] & mask);
113 Block* new_block = (Block*)((char*)line_block(new_line_number) + offset);
115 FACTOR_ASSERT(new_block <= original);
120 Block* next_unmarked_block_after(const Block* original) {
121 std::pair<cell, cell> position = bitmap_deref(original);
122 cell bit_index = position.second;
124 for (cell index = position.first; index < bits_size; index++) {
125 cell mask = ((fixnum) marked[index] >> bit_index);
127 /* Found an unmarked block on this page. Stop, it's hammer time */
128 cell clear_bit = rightmost_clear_bit(mask);
129 return line_block(index * mark_bits_granularity + bit_index +
132 /* No unmarked blocks on this page. Keep looking */
137 /* No unmarked blocks were found */
138 return (Block*)(this->start + this->size);
141 Block* next_marked_block_after(const Block* original) {
142 std::pair<cell, cell> position = bitmap_deref(original);
143 cell bit_index = position.second;
145 for (cell index = position.first; index < bits_size; index++) {
146 cell mask = (marked[index] >> bit_index);
148 /* Found an marked block on this page. Stop, it's hammer time */
149 cell set_bit = rightmost_set_bit(mask);
150 return line_block(index * mark_bits_granularity + bit_index + set_bit);
152 /* No marked blocks on this page. Keep looking */
157 /* No marked blocks were found */
158 return (Block*)(this->start + this->size);
161 cell unmarked_block_size(Block* original) {
162 Block* next_marked = next_marked_block_after(original);
163 return ((char*)next_marked - (char*)original);