From ce6ffe91ddb2c8cba74d9b2d5f8e98b3b6139498 Mon Sep 17 00:00:00 2001 From: Erik Charlebois Date: Sat, 11 May 2013 22:13:01 -0400 Subject: [PATCH] VM: Refactor mark_bits.hpp to Factor style --- vm/mark_bits.hpp | 335 +++++++++++++++++++++-------------------------- 1 file changed, 148 insertions(+), 187 deletions(-) diff --git a/vm/mark_bits.hpp b/vm/mark_bits.hpp index 9a65f3a9d1..d1dd7e1808 100644 --- a/vm/mark_bits.hpp +++ b/vm/mark_bits.hpp @@ -1,206 +1,167 @@ -namespace factor -{ +namespace factor { const int mark_bits_granularity = sizeof(cell) * 8; const int mark_bits_mask = sizeof(cell) * 8 - 1; -template struct mark_bits { - cell size; - cell start; - cell bits_size; - cell *marked; - cell *forwarding; - - void clear_mark_bits() - { - memset(marked,0,bits_size * sizeof(cell)); - } - - void clear_forwarding() - { - memset(forwarding,0,bits_size * sizeof(cell)); - } - - explicit mark_bits(cell size_, cell start_) : - size(size_), - start(start_), - bits_size(size / data_alignment / mark_bits_granularity), - marked(new cell[bits_size]), - forwarding(new cell[bits_size]) - { - clear_mark_bits(); - clear_forwarding(); - } - - ~mark_bits() - { - delete[] marked; - marked = NULL; - delete[] forwarding; - forwarding = NULL; - } - - cell block_line(const Block *address) - { - return (((cell)address - start) / data_alignment); - } - - Block *line_block(cell line) - { - return (Block *)(line * data_alignment + start); - } - - std::pair bitmap_deref(const Block *address) - { - cell line_number = block_line(address); - cell word_index = (line_number / mark_bits_granularity); - cell word_shift = (line_number & mark_bits_mask); - return std::make_pair(word_index,word_shift); - } - - bool bitmap_elt(cell *bits, const Block *address) - { - std::pair position = bitmap_deref(address); - return (bits[position.first] & ((cell)1 << position.second)) != 0; - } - - Block *next_block_after(const Block *block) - { - return (Block *)((cell)block + block->size()); - } - - void set_bitmap_range(cell *bits, const Block *address) - { - std::pair start = bitmap_deref(address); - std::pair end = bitmap_deref(next_block_after(address)); - - cell start_mask = ((cell)1 << start.second) - 1; - cell end_mask = ((cell)1 << end.second) - 1; - - if(start.first == end.first) - bits[start.first] |= start_mask ^ end_mask; - else - { +template struct mark_bits { + cell size; + cell start; + cell bits_size; + cell* marked; + cell* forwarding; + + void clear_mark_bits() { memset(marked, 0, bits_size * sizeof(cell)); } + + void clear_forwarding() { memset(forwarding, 0, bits_size * sizeof(cell)); } + + explicit mark_bits(cell size_, cell start_) + : size(size_), + start(start_), + bits_size(size / data_alignment / mark_bits_granularity), + marked(new cell[bits_size]), + forwarding(new cell[bits_size]) { + clear_mark_bits(); + clear_forwarding(); + } + + ~mark_bits() { + delete[] marked; + marked = NULL; + delete[] forwarding; + forwarding = NULL; + } + + cell block_line(const Block* address) { + return (((cell) address - start) / data_alignment); + } + + Block* line_block(cell line) { + return (Block*)(line * data_alignment + start); + } + + std::pair bitmap_deref(const Block* address) { + cell line_number = block_line(address); + cell word_index = (line_number / mark_bits_granularity); + cell word_shift = (line_number & mark_bits_mask); + return std::make_pair(word_index, word_shift); + } + + bool bitmap_elt(cell* bits, const Block* address) { + std::pair position = bitmap_deref(address); + return (bits[position.first] & ((cell) 1 << position.second)) != 0; + } + + Block* next_block_after(const Block* block) { + return (Block*)((cell) block + block->size()); + } + + void set_bitmap_range(cell* bits, const Block* address) { + std::pair start = bitmap_deref(address); + std::pair end = bitmap_deref(next_block_after(address)); + + cell start_mask = ((cell) 1 << start.second) - 1; + cell end_mask = ((cell) 1 << end.second) - 1; + + if (start.first == end.first) + bits[start.first] |= start_mask ^ end_mask; + else { #ifdef FACTOR_DEBUG - FACTOR_ASSERT(start.first < bits_size); + FACTOR_ASSERT(start.first < bits_size); #endif - bits[start.first] |= ~start_mask; + bits[start.first] |= ~start_mask; - for(cell index = start.first + 1; index < end.first; index++) - bits[index] = (cell)-1; + for (cell index = start.first + 1; index < end.first; index++) + bits[index] = (cell) - 1; - if(end_mask != 0) - { + if (end_mask != 0) { #ifdef FACTOR_DEBUG - FACTOR_ASSERT(end.first < bits_size); + FACTOR_ASSERT(end.first < bits_size); #endif - bits[end.first] |= end_mask; - } - } - } - - bool marked_p(const Block *address) - { - return bitmap_elt(marked,address); - } - - void set_marked_p(const Block *address) - { - set_bitmap_range(marked,address); - } - - /* The eventual destination of a block after compaction is just the number - of marked blocks before it. Live blocks must be marked on entry. */ - void compute_forwarding() - { - cell accum = 0; - for(cell index = 0; index < bits_size; index++) - { - forwarding[index] = accum; - accum += popcount(marked[index]); - } - } - - /* We have the popcount for every mark_bits_granularity entries; look - up and compute the rest */ - Block *forward_block(const Block *original) - { + bits[end.first] |= end_mask; + } + } + } + + bool marked_p(const Block* address) { return bitmap_elt(marked, address); } + + void set_marked_p(const Block* address) { set_bitmap_range(marked, address); } + + /* The eventual destination of a block after compaction is just the number + of marked blocks before it. Live blocks must be marked on entry. */ + void compute_forwarding() { + cell accum = 0; + for (cell index = 0; index < bits_size; index++) { + forwarding[index] = accum; + accum += popcount(marked[index]); + } + } + + /* We have the popcount for every mark_bits_granularity entries; look + up and compute the rest */ + Block* forward_block(const Block* original) { #ifdef FACTOR_DEBUG - FACTOR_ASSERT(marked_p(original)); + FACTOR_ASSERT(marked_p(original)); #endif - std::pair position = bitmap_deref(original); - cell offset = (cell)original & (data_alignment - 1); + std::pair position = bitmap_deref(original); + cell offset = (cell) original & (data_alignment - 1); - cell approx_popcount = forwarding[position.first]; - cell mask = ((cell)1 << position.second) - 1; + cell approx_popcount = forwarding[position.first]; + cell mask = ((cell) 1 << position.second) - 1; - cell new_line_number = approx_popcount + popcount(marked[position.first] & mask); - Block *new_block = (Block*)((char*)line_block(new_line_number) + offset); + cell new_line_number = + approx_popcount + popcount(marked[position.first] & mask); + Block* new_block = (Block*)((char*)line_block(new_line_number) + offset); #ifdef FACTOR_DEBUG - FACTOR_ASSERT(new_block <= original); + FACTOR_ASSERT(new_block <= original); #endif - return new_block; - } - - Block *next_unmarked_block_after(const Block *original) - { - std::pair position = bitmap_deref(original); - cell bit_index = position.second; - - for(cell index = position.first; index < bits_size; index++) - { - cell mask = ((fixnum)marked[index] >> bit_index); - if(~mask) - { - /* Found an unmarked block on this page. - Stop, it's hammer time */ - cell clear_bit = rightmost_clear_bit(mask); - return line_block(index * mark_bits_granularity + bit_index + clear_bit); - } - else - { - /* No unmarked blocks on this page. - Keep looking */ - bit_index = 0; - } - } - - /* No unmarked blocks were found */ - return (Block *)(this->start + this->size); - } - - Block *next_marked_block_after(const Block *original) - { - std::pair position = bitmap_deref(original); - cell bit_index = position.second; - - for(cell index = position.first; index < bits_size; index++) - { - cell mask = (marked[index] >> bit_index); - if(mask) - { - /* Found an marked block on this page. - Stop, it's hammer time */ - cell set_bit = rightmost_set_bit(mask); - return line_block(index * mark_bits_granularity + bit_index + set_bit); - } - else - { - /* No marked blocks on this page. - Keep looking */ - bit_index = 0; - } - } - - /* No marked blocks were found */ - return (Block *)(this->start + this->size); - } - - cell unmarked_block_size(Block *original) - { - Block *next_marked = next_marked_block_after(original); - return ((char *)next_marked - (char *)original); - } + return new_block; + } + + Block* next_unmarked_block_after(const Block* original) { + std::pair position = bitmap_deref(original); + cell bit_index = position.second; + + for (cell index = position.first; index < bits_size; index++) { + cell mask = ((fixnum) marked[index] >> bit_index); + if (~mask) { + /* Found an unmarked block on this page. Stop, it's hammer time */ + cell clear_bit = rightmost_clear_bit(mask); + return line_block(index * mark_bits_granularity + bit_index + + clear_bit); + } else { + /* No unmarked blocks on this page. Keep looking */ + bit_index = 0; + } + } + + /* No unmarked blocks were found */ + return (Block*)(this->start + this->size); + } + + Block* next_marked_block_after(const Block* original) { + std::pair position = bitmap_deref(original); + cell bit_index = position.second; + + for (cell index = position.first; index < bits_size; index++) { + cell mask = (marked[index] >> bit_index); + if (mask) { + /* Found an marked block on this page. Stop, it's hammer time */ + cell set_bit = rightmost_set_bit(mask); + return line_block(index * mark_bits_granularity + bit_index + set_bit); + } else { + /* No marked blocks on this page. Keep looking */ + bit_index = 0; + } + } + + /* No marked blocks were found */ + return (Block*)(this->start + this->size); + } + + cell unmarked_block_size(Block* original) { + Block* next_marked = next_marked_block_after(original); + return ((char*)next_marked - (char*)original); + } }; } -- 2.34.1