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> pair = bitmap_deref(address);
64 return (bits[pair.first] & ((u64)1 << pair.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> pair = bitmap_deref(original);
147 cell approx_popcount = forwarding[pair.first];
148 u64 mask = ((u64)1 << pair.second) - 1;
150 cell new_line_number = approx_popcount + popcount(marked[pair.first] & mask);
151 Block *new_block = line_block(new_line_number);
153 assert(new_block <= original);
158 /* Find the next allocated block without calling size() on unmarked
160 cell unmarked_space_starting_at(Block *original)
162 char *start = (char *)original;
164 char *end = (char *)(this->start + this->size);
166 while(scan != end && !marked_p((Block *)scan))
167 scan += block_granularity;