-namespace factor
-{
+namespace factor {
static const cell free_list_count = 32;
static const cell allocation_page_size = 1024;
-struct free_heap_block
-{
- cell header;
-
- bool free_p() const
- {
- return (header & 1) == 1;
- }
-
- cell size() const
- {
- cell size = header & ~7;
- FACTOR_ASSERT(size > 0);
- return size;
- }
-
- void make_free(cell size)
- {
- FACTOR_ASSERT(size > 0);
- header = size | 1;
- }
+struct free_heap_block {
+ cell header;
+
+ bool free_p() const { return (header & 1) == 1; }
+
+ cell size() const {
+ cell size = header & ~7;
+ FACTOR_ASSERT(size > 0);
+ return size;
+ }
+
+ void make_free(cell size) {
+ FACTOR_ASSERT(size > 0);
+ header = size | 1;
+ }
};
struct block_size_compare {
- bool operator()(free_heap_block *a, free_heap_block *b) const
- {
- return a->size() < b->size();
- }
+ bool operator()(free_heap_block* a, free_heap_block* b) const {
+ return a->size() < b->size();
+ }
};
-typedef std::multiset<free_heap_block *, block_size_compare> large_block_set;
-
-struct free_list {
- std::vector<free_heap_block *> small_blocks[free_list_count];
- large_block_set large_blocks;
- cell free_block_count;
- cell free_space;
-
- void clear_free_list();
- void initial_free_list(cell start, cell end, cell occupied);
- void add_to_free_list(free_heap_block *block);
- free_heap_block *find_free_block(cell size);
- free_heap_block *split_free_block(free_heap_block *block, cell size);
- bool can_allot_p(cell size);
- cell largest_free_block();
+struct allocator_room {
+ cell size;
+ cell occupied_space;
+ cell total_free;
+ cell contiguous_free;
+ cell free_block_count;
};
+template <typename Block> struct free_list_allocator {
+ // Region of memory managed by this free list allocator.
+ cell start;
+ cell end;
+ cell size;
+
+ // Stores the free blocks
+ std::vector<free_heap_block*> small_blocks[free_list_count];
+ std::multiset<free_heap_block*, block_size_compare> large_blocks;
+ cell free_block_count;
+ cell free_space;
+
+ mark_bits state;
+
+ // Initializing & freeing
+ free_list_allocator(cell size, cell start);
+ void initial_free_list(cell occupied);
+ void clear_free_list();
+ void add_to_free_list(free_heap_block* block);
+ void free(Block* block);
+
+ // Allocating
+ free_heap_block* find_free_block(cell size);
+ free_heap_block* split_free_block(free_heap_block* block, cell size);
+ Block* allot(cell size);
+
+ // Data
+ bool contains_p(Block* block);
+ bool can_allot_p(cell size);
+ cell occupied_space();
+ cell largest_free_block();
+ allocator_room as_allocator_room();
+
+ // Iteration
+ void sweep();
+ template <typename Iterator> void sweep(Iterator& iter);
+ template <typename Iterator, typename Fixup>
+ void compact(Iterator& iter, Fixup fixup, const Block** finger);
+ template <typename Iterator, typename Fixup>
+ void iterate(Iterator& iter, Fixup fixup);
+};
+
+template <typename Block>
+void free_list_allocator<Block>::clear_free_list() {
+ for (cell i = 0; i < free_list_count; i++)
+ small_blocks[i].clear();
+ large_blocks.clear();
+ free_block_count = 0;
+ free_space = 0;
+}
+
+template <typename Block>
+void free_list_allocator<Block>::add_to_free_list(free_heap_block* block) {
+ cell size = block->size();
+
+ free_block_count++;
+ free_space += size;
+
+ if (size < free_list_count * data_alignment)
+ small_blocks[size / data_alignment].push_back(block);
+ else
+ large_blocks.insert(block);
+}
+
+template <typename Block>
+void free_list_allocator<Block>::initial_free_list(cell occupied) {
+ clear_free_list();
+ if (occupied != end - start) {
+ free_heap_block* last_block = (free_heap_block*)(start + occupied);
+ last_block->make_free(end - (cell)last_block);
+ add_to_free_list(last_block);
+ }
+}
+
+template <typename Block>
+free_list_allocator<Block>::free_list_allocator(cell size, cell start)
+ : start(start),
+ end(start + size),
+ size(size),
+ state(mark_bits(size, start)) {
+ initial_free_list(0);
+}
+
+template <typename Block>
+bool free_list_allocator<Block>::contains_p(Block* block) {
+ return ((cell)block - start) < size;
+}
+
+template <typename Block>
+bool free_list_allocator<Block>::can_allot_p(cell size) {
+ return largest_free_block() >= std::max(size, allocation_page_size);
+}
+
+template <typename Block>
+free_heap_block* free_list_allocator<Block>::split_free_block(
+ free_heap_block* block,
+ cell size) {
+ if (block->size() != size) {
+ // split the block in two
+ free_heap_block* split = (free_heap_block*)((cell)block + size);
+ split->make_free(block->size() - size);
+ block->make_free(size);
+ add_to_free_list(split);
+ }
+
+ return block;
+}
+
+template <typename Block>
+free_heap_block* free_list_allocator<Block>::find_free_block(cell size) {
+ // Check small free lists
+ cell bucket = size / data_alignment;
+ if (bucket < free_list_count) {
+ std::vector<free_heap_block*>& blocks = small_blocks[bucket];
+ if (blocks.size() == 0) {
+ // Round up to a multiple of 'size'
+ cell large_block_size = ((allocation_page_size + size - 1) / size) * size;
+
+ // Allocate a block this big
+ free_heap_block* large_block = find_free_block(large_block_size);
+ if (!large_block)
+ return NULL;
+
+ large_block = split_free_block(large_block, large_block_size);
+
+ // Split it up into pieces and add each piece back to the free list
+ for (cell offset = 0; offset < large_block_size; offset += size) {
+ free_heap_block* small_block = large_block;
+ large_block = (free_heap_block*)((cell)large_block + size);
+ small_block->make_free(size);
+ add_to_free_list(small_block);
+ }
+ }
+
+ free_heap_block* block = blocks.back();
+ blocks.pop_back();
+
+ free_block_count--;
+ free_space -= block->size();
+
+ return block;
+ } else {
+ // Check large free list
+ free_heap_block key;
+ key.make_free(size);
+ auto iter = large_blocks.lower_bound(&key);
+ auto end = large_blocks.end();
+
+ if (iter != end) {
+ free_heap_block* block = *iter;
+ large_blocks.erase(iter);
+
+ free_block_count--;
+ free_space -= block->size();
+
+ return block;
+ }
+
+ return NULL;
+ }
+}
+
+
+template <typename Block>
+Block* free_list_allocator<Block>::allot(cell size) {
+ size = align(size, data_alignment);
+
+ free_heap_block* block = find_free_block(size);
+ if (block) {
+ block = split_free_block(block, size);
+ return (Block*)block;
+ }
+ return NULL;
+}
+
+template <typename Block>
+void free_list_allocator<Block>::free(Block* block) {
+ free_heap_block* free_block = (free_heap_block*)block;
+ free_block->make_free(block->size());
+ add_to_free_list(free_block);
+}
+
+template <typename Block>
+cell free_list_allocator<Block>::occupied_space() {
+ return size - free_space;
+}
+
+template <typename Block>
+cell free_list_allocator<Block>::largest_free_block() {
+ if (large_blocks.size()) {
+ auto last = large_blocks.rbegin();
+ return (*last)->size();
+ } else {
+ for (int i = free_list_count - 1; i >= 0; i--) {
+ if (small_blocks[i].size())
+ return small_blocks[i].back()->size();
+ }
+ return 0;
+ }
+}
+
+template <typename Block>
+template <typename Iterator>
+void free_list_allocator<Block>::sweep(Iterator& iter) {
+ clear_free_list();
+
+ cell start = this->start;
+ cell end = this->end;
+
+ while (start != end) {
+ // find next unmarked block
+ start = state.next_unmarked_block_after(start);
+
+ if (start != end) {
+ // find size
+ cell size = state.unmarked_block_size(start);
+ FACTOR_ASSERT(size > 0);
+
+ free_heap_block* free_block = (free_heap_block*)start;
+ free_block->make_free(size);
+ add_to_free_list(free_block);
+ iter((Block*)start, size);
+
+ start = start + size;
+ }
+ }
+}
+
+template <typename Block> void free_list_allocator<Block>::sweep() {
+ auto null_sweep = [](Block* free_block, cell size) { (void)free_block; (void)size; };
+ sweep(null_sweep);
+}
+
+// The forwarding map must be computed first by calling
+// state.compute_forwarding().
+template <typename Block>
+template <typename Iterator, typename Fixup>
+void free_list_allocator<Block>::compact(Iterator& iter, Fixup fixup,
+ const Block** finger) {
+ cell dest_addr = start;
+ auto compact_block_func = [&](Block* block, cell size) {
+ cell block_addr = (cell)block;
+ if (!state.marked_p(block_addr))
+ return;
+ *finger = (Block*)(block_addr + size);
+ if (dest_addr != (cell)block) {
+ memmove((Block*)dest_addr, block, size);
+ }
+ iter(block, (Block*)dest_addr, size);
+ dest_addr += size;
+ };
+ iterate(compact_block_func, fixup);
+
+ // Now update the free list; there will be a single free block at
+ // the end
+ initial_free_list(dest_addr - start);
+}
+
+// During compaction we have to be careful and measure object sizes
+// differently
+template <typename Block>
+template <typename Iterator, typename Fixup>
+void free_list_allocator<Block>::iterate(Iterator& iter, Fixup fixup) {
+ cell scan = this->start;
+ while (scan != this->end) {
+ Block* block = (Block*)scan;
+ cell size = fixup.size(block);
+ if (!block->free_p())
+ iter(block, size);
+ scan += size;
+ }
+}
+
+template <typename Block>
+allocator_room free_list_allocator<Block>::as_allocator_room() {
+ allocator_room room;
+ room.size = size;
+ room.occupied_space = occupied_space();
+ room.total_free = free_space;
+ room.contiguous_free = largest_free_block();
+ room.free_block_count = free_block_count;
+ return room;
+}
+
}
projects / factor.git / blobdiff