3 const int mark_bits_granularity = sizeof(cell) * 8;
4 const int mark_bits_mask = sizeof(cell) * 8 - 1;
13 void clear_mark_bits() { memset(marked, 0, bits_size * sizeof(cell)); }
15 void clear_forwarding() { memset(forwarding, 0, bits_size * sizeof(cell)); }
17 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(cell address) {
35 return (address - start) / data_alignment;
38 cell line_block(cell line) {
39 return line * data_alignment + start;
42 std::pair<cell, cell> bitmap_deref(const cell 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 cell address) {
50 std::pair<cell, cell> position = bitmap_deref(address);
51 return (bits[position.first] & ((cell)1 << position.second)) != 0;
54 void set_bitmap_range(cell* bits, const cell address, const cell size) {
55 std::pair<cell, cell> start = bitmap_deref(address);
56 std::pair<cell, cell> end = bitmap_deref(address + size);
58 cell start_mask = ((cell)1 << start.second) - 1;
59 cell end_mask = ((cell)1 << end.second) - 1;
61 if (start.first == end.first)
62 bits[start.first] |= start_mask ^ end_mask;
64 FACTOR_ASSERT(start.first < bits_size);
65 bits[start.first] |= ~start_mask;
67 for (cell index = start.first + 1; index < end.first; index++)
68 bits[index] = (cell)-1;
71 FACTOR_ASSERT(end.first < bits_size);
72 bits[end.first] |= end_mask;
77 bool marked_p(const cell address) { return bitmap_elt(marked, address); }
79 void set_marked_p(const cell address, const cell size) {
80 set_bitmap_range(marked, address, size);
83 // The eventual destination of a block after compaction is just the number
84 // of marked blocks before it. Live blocks must be marked on entry.
85 void compute_forwarding() {
87 for (cell index = 0; index < bits_size; index++) {
88 forwarding[index] = accum;
89 accum += popcount(marked[index]);
93 // We have the popcount for every mark_bits_granularity entries; look
94 // up and compute the rest
95 cell forward_block(const cell original) {
96 FACTOR_ASSERT(marked_p(original));
97 std::pair<cell, cell> position = bitmap_deref(original);
98 cell offset = original & (data_alignment - 1);
100 cell approx_popcount = forwarding[position.first];
101 cell mask = ((cell)1 << position.second) - 1;
103 cell new_line_number =
104 approx_popcount + popcount(marked[position.first] & mask);
105 cell new_block = line_block(new_line_number) + offset;
106 FACTOR_ASSERT(new_block <= original);
110 cell next_unmarked_block_after(const cell original) {
111 std::pair<cell, cell> position = bitmap_deref(original);
112 cell bit_index = position.second;
114 for (cell index = position.first; index < bits_size; index++) {
115 cell mask = ((fixnum)marked[index] >> bit_index);
117 // Found an unmarked block on this page. Stop, it's hammer time
118 cell clear_bit = rightmost_clear_bit(mask);
119 return line_block(index * mark_bits_granularity + bit_index +
122 // No unmarked blocks on this page. Keep looking
127 // No unmarked blocks were found
128 return this->start + this->size;
131 cell next_marked_block_after(const cell original) {
132 std::pair<cell, cell> position = bitmap_deref(original);
133 cell bit_index = position.second;
135 for (cell index = position.first; index < bits_size; index++) {
136 cell mask = (marked[index] >> bit_index);
138 // Found an marked block on this page. Stop, it's hammer time
139 cell set_bit = rightmost_set_bit(mask);
140 return line_block(index * mark_bits_granularity + bit_index + set_bit);
142 // No marked blocks on this page. Keep looking
147 // No marked blocks were found
148 return this->start + this->size;
151 cell unmarked_block_size(cell original) {
152 cell next_marked = next_marked_block_after(original);
153 return next_marked - original;