3 static const cell free_list_count = 32;
4 static const cell allocation_page_size = 1024;
6 struct free_heap_block {
9 bool free_p() const { return (header & 1) == 1; }
12 cell size = header & ~7;
13 FACTOR_ASSERT(size > 0);
17 void make_free(cell size) {
18 FACTOR_ASSERT(size > 0);
23 struct block_size_compare {
24 bool operator()(free_heap_block* a, free_heap_block* b) const {
25 return a->size() < b->size();
29 struct allocator_room {
34 cell free_block_count;
37 template <typename Block> struct free_list_allocator {
38 // Region of memory managed by this free list allocator.
43 // Stores the free blocks
44 std::vector<free_heap_block*> small_blocks[free_list_count];
45 std::multiset<free_heap_block*, block_size_compare> large_blocks;
46 cell free_block_count;
51 // Initializing & freeing
52 free_list_allocator(cell size, cell start);
53 void initial_free_list(cell occupied);
54 void clear_free_list();
55 void add_to_free_list(free_heap_block* block);
56 void free(Block* block);
59 free_heap_block* find_free_block(cell size);
60 free_heap_block* split_free_block(free_heap_block* block, cell size);
61 Block* allot(cell size);
64 bool contains_p(Block* block);
65 bool can_allot_p(cell size);
66 cell occupied_space();
67 cell largest_free_block();
68 allocator_room as_allocator_room();
72 template <typename Iterator> void sweep(Iterator& iter);
73 template <typename Iterator, typename Fixup>
74 void compact(Iterator& iter, Fixup fixup, const Block** finger);
75 template <typename Iterator, typename Fixup>
76 void iterate(Iterator& iter, Fixup fixup);
79 template <typename Block>
80 void free_list_allocator<Block>::clear_free_list() {
81 for (cell i = 0; i < free_list_count; i++)
82 small_blocks[i].clear();
88 template <typename Block>
89 void free_list_allocator<Block>::add_to_free_list(free_heap_block* block) {
90 cell size = block->size();
95 if (size < free_list_count * data_alignment)
96 small_blocks[size / data_alignment].push_back(block);
98 large_blocks.insert(block);
101 template <typename Block>
102 void free_list_allocator<Block>::initial_free_list(cell occupied) {
104 if (occupied != end - start) {
105 free_heap_block* last_block = (free_heap_block*)(start + occupied);
106 last_block->make_free(end - (cell)last_block);
107 add_to_free_list(last_block);
111 template <typename Block>
112 free_list_allocator<Block>::free_list_allocator(cell size, cell start)
116 state(mark_bits(size, start)) {
117 initial_free_list(0);
120 template <typename Block>
121 bool free_list_allocator<Block>::contains_p(Block* block) {
122 return ((cell)block - start) < size;
125 template <typename Block>
126 bool free_list_allocator<Block>::can_allot_p(cell size) {
127 return largest_free_block() >= std::max(size, allocation_page_size);
130 template <typename Block>
131 free_heap_block* free_list_allocator<Block>::split_free_block(
132 free_heap_block* block,
134 if (block->size() != size) {
135 // split the block in two
136 free_heap_block* split = (free_heap_block*)((cell)block + size);
137 split->make_free(block->size() - size);
138 block->make_free(size);
139 add_to_free_list(split);
145 template <typename Block>
146 free_heap_block* free_list_allocator<Block>::find_free_block(cell size) {
147 // Check small free lists
148 cell bucket = size / data_alignment;
149 if (bucket < free_list_count) {
150 std::vector<free_heap_block*>& blocks = small_blocks[bucket];
151 if (blocks.size() == 0) {
152 // Round up to a multiple of 'size'
153 cell large_block_size = ((allocation_page_size + size - 1) / size) * size;
155 // Allocate a block this big
156 free_heap_block* large_block = find_free_block(large_block_size);
160 large_block = split_free_block(large_block, large_block_size);
162 // Split it up into pieces and add each piece back to the free list
163 for (cell offset = 0; offset < large_block_size; offset += size) {
164 free_heap_block* small_block = large_block;
165 large_block = (free_heap_block*)((cell)large_block + size);
166 small_block->make_free(size);
167 add_to_free_list(small_block);
171 free_heap_block* block = blocks.back();
175 free_space -= block->size();
179 // Check large free list
182 auto iter = large_blocks.lower_bound(&key);
183 auto end = large_blocks.end();
186 free_heap_block* block = *iter;
187 large_blocks.erase(iter);
190 free_space -= block->size();
200 template <typename Block>
201 Block* free_list_allocator<Block>::allot(cell size) {
202 size = align(size, data_alignment);
204 free_heap_block* block = find_free_block(size);
206 block = split_free_block(block, size);
207 return (Block*)block;
212 template <typename Block>
213 void free_list_allocator<Block>::free(Block* block) {
214 free_heap_block* free_block = (free_heap_block*)block;
215 free_block->make_free(block->size());
216 add_to_free_list(free_block);
219 template <typename Block>
220 cell free_list_allocator<Block>::occupied_space() {
221 return size - free_space;
224 template <typename Block>
225 cell free_list_allocator<Block>::largest_free_block() {
226 if (large_blocks.size()) {
227 auto last = large_blocks.rbegin();
228 return (*last)->size();
230 for (int i = free_list_count - 1; i >= 0; i--) {
231 if (small_blocks[i].size())
232 return small_blocks[i].back()->size();
238 template <typename Block>
239 template <typename Iterator>
240 void free_list_allocator<Block>::sweep(Iterator& iter) {
243 cell start = this->start;
244 cell end = this->end;
246 while (start != end) {
247 // find next unmarked block
248 start = state.next_unmarked_block_after(start);
252 cell size = state.unmarked_block_size(start);
253 FACTOR_ASSERT(size > 0);
255 free_heap_block* free_block = (free_heap_block*)start;
256 free_block->make_free(size);
257 add_to_free_list(free_block);
258 iter((Block*)start, size);
260 start = start + size;
265 template <typename Block> void free_list_allocator<Block>::sweep() {
266 auto null_sweep = [](Block* free_block, cell size) { };
270 // The forwarding map must be computed first by calling
271 // state.compute_forwarding().
272 template <typename Block>
273 template <typename Iterator, typename Fixup>
274 void free_list_allocator<Block>::compact(Iterator& iter, Fixup fixup,
275 const Block** finger) {
276 cell dest_addr = start;
277 auto compact_block_func = [&](Block* block, cell size) {
278 cell block_addr = (cell)block;
279 if (!state.marked_p(block_addr))
281 *finger = (Block*)(block_addr + size);
282 if (dest_addr != (cell)block) {
283 memmove((Block*)dest_addr, block, size);
285 iter(block, (Block*)dest_addr, size);
288 iterate(compact_block_func, fixup);
290 // Now update the free list; there will be a single free block at
292 initial_free_list(dest_addr - start);
295 // During compaction we have to be careful and measure object sizes
297 template <typename Block>
298 template <typename Iterator, typename Fixup>
299 void free_list_allocator<Block>::iterate(Iterator& iter, Fixup fixup) {
300 cell scan = this->start;
301 while (scan != this->end) {
302 Block* block = (Block*)scan;
303 cell size = fixup.size(block);
304 if (!block->free_p())
310 template <typename Block>
311 allocator_room free_list_allocator<Block>::as_allocator_room() {
314 room.occupied_space = occupied_space();
315 room.total_free = free_space;
316 room.contiguous_free = largest_free_block();
317 room.free_block_count = free_block_count;