From: Björn Lindqvist Date: Mon, 3 Oct 2016 03:09:02 +0000 (+0200) Subject: VM: merge of the free_list and free_list_allocator classes X-Git-Tag: unmaintained~600 X-Git-Url: https://gitweb.factorcode.org/gitweb.cgi?p=factor.git;a=commitdiff_plain;h=c2f4fdb172102c4f32c44ded2fc7067ad8dcd521 VM: merge of the free_list and free_list_allocator classes Seem simpler to have all the free list stuff in one class rather than split it over two classes. --- diff --git a/GNUmakefile b/GNUmakefile index 28259cb61b..bce0d29244 100644 --- a/GNUmakefile +++ b/GNUmakefile @@ -43,7 +43,6 @@ ifdef CONFIG vm/entry_points.o \ vm/errors.o \ vm/factor.o \ - vm/free_list.o \ vm/full_collector.o \ vm/gc.o \ vm/image.o \ diff --git a/Nmakefile b/Nmakefile index eeb13bf952..689156a57f 100644 --- a/Nmakefile +++ b/Nmakefile @@ -67,7 +67,6 @@ DLL_OBJS = $(PLAF_DLL_OBJS) \ vm\entry_points.obj \ vm\errors.obj \ vm\factor.obj \ - vm\free_list.obj \ vm\full_collector.obj \ vm\gc.obj \ vm\image.obj \ diff --git a/vm/code_blocks.cpp b/vm/code_blocks.cpp index 7348174076..04ce346aa2 100644 --- a/vm/code_blocks.cpp +++ b/vm/code_blocks.cpp @@ -301,7 +301,7 @@ code_block* factor_vm::allot_code_block(cell size, code_block_type type) { if (block == NULL) { std::cout << "Code heap used: " << code->allocator->occupied_space() << "\n"; - std::cout << "Code heap free: " << code->allocator->free_space() << "\n"; + std::cout << "Code heap free: " << code->allocator->free_space << "\n"; fatal_error("Out of memory in add-compiled-block", 0); } } diff --git a/vm/data_heap.cpp b/vm/data_heap.cpp index 2f9625d57c..27b6e6bc54 100644 --- a/vm/data_heap.cpp +++ b/vm/data_heap.cpp @@ -93,7 +93,7 @@ bool data_heap::high_fragmentation_p() { } bool data_heap::low_memory_p() { - return tenured->free_space() <= high_water_mark(); + return tenured->free_space <= high_water_mark(); } void data_heap::mark_all_cards() { @@ -123,9 +123,9 @@ data_heap_room factor_vm::data_room() { room.aging_free = data->aging->free_space(); room.tenured_size = data->tenured->size; room.tenured_occupied = data->tenured->occupied_space(); - room.tenured_total_free = data->tenured->free_space(); + room.tenured_total_free = data->tenured->free_space; room.tenured_contiguous_free = data->tenured->largest_free_block(); - room.tenured_free_block_count = data->tenured->free_block_count(); + room.tenured_free_block_count = data->tenured->free_block_count; room.cards = data->cards_end - data->cards; room.decks = data->decks_end - data->decks; room.mark_stack = mark_stack.capacity() * sizeof(cell); diff --git a/vm/free_list.cpp b/vm/free_list.cpp deleted file mode 100644 index b2534c6f99..0000000000 --- a/vm/free_list.cpp +++ /dev/null @@ -1,118 +0,0 @@ -#include "master.hpp" - -namespace factor { - -void free_list::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; -} - -void free_list::initial_free_list(cell start, cell end, 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); - } -} - -void free_list::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); -} - -free_heap_block* free_list::find_free_block(cell size) { - // Check small free lists - cell bucket = size / data_alignment; - if (bucket < free_list_count) { - std::vector& 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); - large_block_set::iterator iter = large_blocks.lower_bound(&key); - large_block_set::iterator 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; - } -} - -free_heap_block* free_list::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; -} - -bool free_list::can_allot_p(cell size) { - return largest_free_block() >= std::max(size, allocation_page_size); -} - -cell free_list::largest_free_block() { - if (large_blocks.size()) { - large_block_set::reverse_iterator 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; - } -} - -} diff --git a/vm/free_list.hpp b/vm/free_list.hpp index 4fdf449147..a93084315b 100644 --- a/vm/free_list.hpp +++ b/vm/free_list.hpp @@ -26,23 +26,6 @@ struct block_size_compare { } }; -typedef std::multiset large_block_set; - -struct free_list { - std::vector 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; @@ -52,44 +35,86 @@ struct allocator_room { }; template struct free_list_allocator { - cell size; + // Region of memory managed by this free list allocator. cell start; cell end; - free_list free_blocks; + cell size; + + // Stores the free blocks + std::vector small_blocks[free_list_count]; + std::multiset 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); - Block* allot(cell size); - void free(Block* block); cell occupied_space(); - cell free_space(); cell largest_free_block(); - cell free_block_count(); + allocator_room as_allocator_room(); + + // Iteration void sweep(); template void sweep(Iterator& iter); template void compact(Iterator& iter, Fixup fixup, const Block** finger); template void iterate(Iterator& iter, Fixup fixup); - template void iterate(Iterator& iter); - allocator_room as_allocator_room(); }; template -free_list_allocator::free_list_allocator(cell size, cell start) - : size(size), - start(start), - end(start + size), - state(mark_bits(size, start)) { - initial_free_list(0); +void free_list_allocator::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 +void free_list_allocator::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 void free_list_allocator::initial_free_list(cell occupied) { - free_blocks.initial_free_list(start, end, 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 +free_list_allocator::free_list_allocator(cell size, cell start) + : start(start), + end(start + size), + size(size), + state(mark_bits(size, start)) { + initial_free_list(0); } template @@ -99,47 +124,121 @@ bool free_list_allocator::contains_p(Block* block) { template bool free_list_allocator::can_allot_p(cell size) { - return free_blocks.can_allot_p(size); + return largest_free_block() >= std::max(size, allocation_page_size); +} + +template +free_heap_block* free_list_allocator::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 Block* free_list_allocator::allot(cell size) { +template +free_heap_block* free_list_allocator::find_free_block(cell size) { + // Check small free lists + cell bucket = size / data_alignment; + if (bucket < free_list_count) { + std::vector& 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 +Block* free_list_allocator::allot(cell size) { size = align(size, data_alignment); - free_heap_block* block = free_blocks.find_free_block(size); + free_heap_block* block = find_free_block(size); if (block) { - block = free_blocks.split_free_block(block, size); + block = split_free_block(block, size); return (Block*)block; } return NULL; } -template void free_list_allocator::free(Block* block) { +template +void free_list_allocator::free(Block* block) { free_heap_block* free_block = (free_heap_block*)block; free_block->make_free(block->size()); - free_blocks.add_to_free_list(free_block); + add_to_free_list(free_block); } -template cell free_list_allocator::free_space() { - return free_blocks.free_space; -} - -template cell free_list_allocator::occupied_space() { - return size - free_blocks.free_space; +template +cell free_list_allocator::occupied_space() { + return size - free_space; } template cell free_list_allocator::largest_free_block() { - return free_blocks.largest_free_block(); -} - -template cell free_list_allocator::free_block_count() { - return free_blocks.free_block_count; + 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 template void free_list_allocator::sweep(Iterator& iter) { - free_blocks.clear_free_list(); + clear_free_list(); cell start = this->start; cell end = this->end; @@ -155,7 +254,7 @@ void free_list_allocator::sweep(Iterator& iter) { free_heap_block* free_block = (free_heap_block*)start; free_block->make_free(size); - free_blocks.add_to_free_list(free_block); + add_to_free_list(free_block); iter((Block*)start, size); start = start + size; @@ -188,7 +287,7 @@ void free_list_allocator::compact(Iterator& iter, Fixup fixup, // Now update the free list; there will be a single free block at // the end - free_blocks.initial_free_list(start, end, dest_addr - start); + initial_free_list(dest_addr - start); } // During compaction we have to be careful and measure object sizes @@ -211,9 +310,9 @@ allocator_room free_list_allocator::as_allocator_room() { allocator_room room; room.size = size; room.occupied_space = occupied_space(); - room.total_free = free_space(); + room.total_free = free_space; room.contiguous_free = largest_free_block(); - room.free_block_count = free_block_count(); + room.free_block_count = free_block_count; return room; }