vm/factor.o \
vm/full_collector.o \
vm/gc.o \
- vm/heap.o \
vm/image.o \
vm/inline_cache.o \
vm/io.o \
vm/jit.o \
vm/math.o \
vm/nursery_collector.o \
- vm/old_space.o \
+ vm/object_start_map.o \
vm/primitives.o \
vm/profiler.o \
vm/quotations.o \
: here-as ( tag -- pointer ) here bitor ;
+: (align-here) ( alignment -- )
+ [ here neg ] dip rem
+ [ bootstrap-cell /i [ 0 emit ] times ] unless-zero ;
+
: align-here ( -- )
- here 8 mod 4 = [ 0 emit ] when ;
+ data-alignment get (align-here) ;
: emit-fixnum ( n -- ) tag-fixnum emit ;
M: float '
[
float [
- align-here double>bits emit-64
+ 8 (align-here) double>bits emit-64
] emit-object
] cache-eql-object ;
[
byte-array [
dup length emit-fixnum
+ bootstrap-cell 4 = [ 0 emit 0 emit ] when
pad-bytes emit-bytes
] emit-object
] cache-eq-object ;
: string-offset ( -- n ) 4 string tag-number slot-offset ; inline
: string-aux-offset ( -- n ) 2 string tag-number slot-offset ; inline
: profile-count-offset ( -- n ) 8 \ word tag-number slot-offset ; inline
-: byte-array-offset ( -- n ) 2 byte-array tag-number slot-offset ; inline
+: byte-array-offset ( -- n ) 16 byte-array tag-number - ; inline
: alien-offset ( -- n ) 3 alien tag-number slot-offset ; inline
: underlying-alien-offset ( -- n ) 1 alien tag-number slot-offset ; inline
: tuple-class-offset ( -- n ) 1 tuple tag-number slot-offset ; inline
[ drop load-zone-ptr ] [ swap 0 LWZ ] 2bi ;
:: inc-allot-ptr ( nursery-ptr allot-ptr n -- )
- scratch-reg allot-ptr n 8 align ADDI
+ scratch-reg allot-ptr n data-alignment get align ADDI
scratch-reg nursery-ptr 0 STW ;
:: store-header ( dst class -- )
[ drop "nursery" %vm-field-ptr ] [ swap [] MOV ] 2bi ;
: inc-allot-ptr ( nursery-ptr n -- )
- [ [] ] dip 8 align ADD ;
+ [ [] ] dip data-alignment get align ADD ;
: store-header ( temp class -- )
[ [] ] [ type-number tag-fixnum ] bi* MOV ;
quotations assocs layouts classes.tuple.private
kernel.private ;
+16 data-alignment set
+
BIN: 111 tag-mask set
8 num-tags set
3 tag-bits set
math.order kernel.private ;
IN: layouts
+SYMBOL: data-alignment
+
SYMBOL: tag-mask
SYMBOL: num-tags
collector.trace_cards(data->tenured,
card_points_to_aging,
simple_unmarker(card_mark_mask));
- collector.cheneys_algorithm();
+ collector.tenure_reachable_objects();
}
{
/* If collection fails here, do a to_tenured collection. */
current_gc->op = collect_aging_op;
std::swap(data->aging,data->aging_semispace);
- reset_generation(data->aging);
+ data->reset_generation(data->aging);
aging_collector collector(this);
collector.trace_contexts();
collector.trace_code_heap_roots(&code->points_to_aging);
collector.cheneys_algorithm();
+
update_code_heap_for_minor_gc(&code->points_to_aging);
- nursery.here = nursery.start;
+ data->reset_generation(&nursery);
code->points_to_nursery.clear();
}
}
struct aging_policy {
factor_vm *parent;
- zone *aging, *tenured;
+ aging_space *aging;
+ tenured_space *tenured;
aging_policy(factor_vm *parent_) :
parent(parent_),
{
return !(aging->contains_p(untagged) || tenured->contains_p(untagged));
}
+
+ void promoted_object(object *obj) {}
+
+ void visited_object(object *obj) {}
};
struct aging_collector : copying_collector<aging_space,aging_policy> {
namespace factor
{
-struct aging_space : old_space {
- aging_space(cell size, cell start) : old_space(size,start) {}
+struct aging_space : bump_allocator<object> {
+ object_start_map starts;
+
+ aging_space(cell size, cell start) :
+ bump_allocator<object>(size,start), starts(size,start) {}
+
+ object *allot(cell size)
+ {
+ if(here + size > end) return NULL;
+
+ object *obj = bump_allocator<object>::allot(size);
+ starts.record_object_start_offset(obj);
+ return obj;
+ }
+
+ cell next_object_after(cell scan)
+ {
+ cell size = ((object *)scan)->size();
+ if(scan + size < here)
+ return scan + size;
+ else
+ return 0;
+ }
};
}
array *factor_vm::allot_array(cell capacity, cell fill_)
{
gc_root<object> fill(fill_,this);
- gc_root<array> new_array(allot_array_internal<array>(capacity),this);
+ gc_root<array> new_array(allot_uninitialized_array<array>(capacity),this);
if(fill.value() == tag_fixnum(0))
memset(new_array->data(),'\0',capacity * sizeof(cell));
cell factor_vm::allot_array_1(cell obj_)
{
gc_root<object> obj(obj_,this);
- gc_root<array> a(allot_array_internal<array>(1),this);
+ gc_root<array> a(allot_uninitialized_array<array>(1),this);
set_array_nth(a.untagged(),0,obj.value());
return a.value();
}
{
gc_root<object> v1(v1_,this);
gc_root<object> v2(v2_,this);
- gc_root<array> a(allot_array_internal<array>(2),this);
+ gc_root<array> a(allot_uninitialized_array<array>(2),this);
set_array_nth(a.untagged(),0,v1.value());
set_array_nth(a.untagged(),1,v2.value());
return a.value();
gc_root<object> v2(v2_,this);
gc_root<object> v3(v3_,this);
gc_root<object> v4(v4_,this);
- gc_root<array> a(allot_array_internal<array>(4),this);
+ gc_root<array> a(allot_uninitialized_array<array>(4),this);
set_array_nth(a.untagged(),0,v1.value());
set_array_nth(a.untagged(),1,v2.value());
set_array_nth(a.untagged(),2,v3.value());
#ifdef FACTOR_DEBUG
assert(slot < array_capacity(array));
assert(array->h.hi_tag() == ARRAY_TYPE);
- check_tagged_pointer(value);
#endif
cell *slot_ptr = &array->data()[slot];
*slot_ptr = value;
bignum *factor_vm::allot_bignum(bignum_length_type length, int negative_p)
{
BIGNUM_ASSERT ((length >= 0) || (length < BIGNUM_RADIX));
- bignum * result = allot_array_internal<bignum>(length + 1);
+ bignum * result = allot_uninitialized_array<bignum>(length + 1);
BIGNUM_SET_NEGATIVE_P (result, negative_p);
return (result);
}
--- /dev/null
+namespace factor
+{
+
+template<typename Block> struct bump_allocator {
+ /* offset of 'here' and 'end' is hardcoded in compiler backends */
+ cell here;
+ cell start;
+ cell end;
+ cell size;
+
+ bump_allocator(cell size_, cell start_) :
+ here(start_), start(start_), end(start_ + size_), size(size_) {}
+
+ inline bool contains_p(Block *block)
+ {
+ return ((cell)block - start) < size;
+ }
+
+ inline Block *allot(cell size)
+ {
+ cell h = here;
+ here = h + align(size,data_alignment);
+ return (Block *)h;
+ }
+};
+
+}
byte_array *factor_vm::allot_byte_array(cell size)
{
- byte_array *array = allot_array_internal<byte_array>(size);
+ byte_array *array = allot_uninitialized_array<byte_array>(size);
memset(array + 1,0,size);
return array;
}
void factor_vm::primitive_uninitialized_byte_array()
{
cell size = unbox_array_size();
- dpush(tag<byte_array>(allot_array_internal<byte_array>(size)));
+ dpush(tag<byte_array>(allot_uninitialized_array<byte_array>(size)));
}
void factor_vm::primitive_resize_byte_array()
tagged<byte_array> insns(array_nth(code_template.untagged(),0));
cell size = array_capacity(insns.untagged());
- cell bump = align8(size) + sizeof(callback);
+ cell bump = align(size,sizeof(cell)) + sizeof(callback);
if(here + bump > seg->end) fatal_error("Out of callback space",0);
callback *stub = (callback *)here;
stub->compiled = compiled;
memcpy(stub + 1,insns->data<void>(),size);
- stub->size = align8(size);
+ stub->size = align(size,sizeof(cell));
here += bump;
update(stub);
return (code_block *)frame->xt - 1;
}
-cell factor_vm::frame_type(stack_frame *frame)
+code_block_type factor_vm::frame_type(stack_frame *frame)
{
return frame_code(frame)->type();
}
{
switch(frame_type(frame))
{
- case QUOTATION_TYPE:
+ case code_block_unoptimized:
{
cell quot = frame_executing(frame);
if(to_boolean(quot))
else
return false_object;
}
- case WORD_TYPE:
+ case code_block_optimized:
return false_object;
default:
critical_error("Bad frame type",frame_type(frame));
if(parent->relocation_type_of(rel) == RT_IMMEDIATE)
{
cell offset = parent->relocation_offset_of(rel) + (cell)(compiled + 1);
- array *literals = parent->untag<array>(compiled->literals);
+ array *literals = untag<array>(compiled->literals);
fixnum absolute_value = array_nth(literals,index);
parent->store_address_in_code_block(parent->relocation_class_of(rel),offset,absolute_value);
}
are referenced after this is done. So instead of polluting
the code heap with dead PICs that will be freed on the next
GC, we add them to the free list immediately. */
- else if(compiled->type() == PIC_TYPE)
+ else if(compiled->pic_p())
code->code_heap_free(compiled);
else
{
}
};
-void factor_vm::update_code_block_for_full_gc(code_block *compiled)
+void factor_vm::update_code_block_words_and_literals(code_block *compiled)
{
if(code->needs_fixup_p(compiled))
relocate_code_block(compiled);
}
/* Might GC */
-code_block *factor_vm::allot_code_block(cell size, cell type)
+code_block *factor_vm::allot_code_block(cell size, code_block_type type)
{
- heap_block *block = code->heap_allot(size + sizeof(code_block),type);
+ heap_block *block = code->allocator->allot(size + sizeof(code_block));
/* If allocation failed, do a full GC and compact the code heap.
A full GC that occurs as a result of the data heap filling up does not
if(block == NULL)
{
primitive_compact_gc();
- block = code->heap_allot(size + sizeof(code_block),type);
+ block = code->allocator->allot(size + sizeof(code_block));
/* Insufficient room even after code GC, give up */
if(block == NULL)
{
cell used, total_free, max_free;
- code->heap_usage(&used,&total_free,&max_free);
+ code->allocator->usage(&used,&total_free,&max_free);
- print_string("Code heap stats:\n");
- print_string("Used: "); print_cell(used); nl();
- print_string("Total free space: "); print_cell(total_free); nl();
- print_string("Largest free block: "); print_cell(max_free); nl();
+ std::cout << "Code heap stats:\n";
+ std::cout << "Used: " << used << "\n";
+ std::cout << "Total free space: " << total_free << "\n";
+ std::cout << "Largest free block: " << max_free << "\n";
fatal_error("Out of memory in add-compiled-block",0);
}
}
- return (code_block *)block;
+ code_block *compiled = (code_block *)block;
+ compiled->set_type(type);
+ return compiled;
}
/* Might GC */
-code_block *factor_vm::add_code_block(cell type, cell code_, cell labels_, cell owner_, cell relocation_, cell literals_)
+code_block *factor_vm::add_code_block(code_block_type type, cell code_, cell labels_, cell owner_, cell relocation_, cell literals_)
{
gc_root<byte_array> code(code_,this);
gc_root<object> labels(labels_,this);
gc_root<byte_array> relocation(relocation_,this);
gc_root<array> literals(literals_,this);
- cell code_length = align8(array_capacity(code.untagged()));
+ cell code_length = array_capacity(code.untagged());
code_block *compiled = allot_code_block(code_length,type);
compiled->owner = owner.value();
namespace factor
{
-code_heap::code_heap(bool secure_gc, cell size) : heap(secure_gc,size,true) {}
+code_heap::code_heap(cell size)
+{
+ if(size > (1L << (sizeof(cell) * 8 - 6))) fatal_error("Heap too large",size);
+ seg = new segment(align_page(size),true);
+ if(!seg) fatal_error("Out of memory in heap allocator",size);
+ allocator = new free_list_allocator<heap_block>(size,seg->start);
+}
+
+code_heap::~code_heap()
+{
+ delete allocator;
+ allocator = NULL;
+ delete seg;
+ seg = NULL;
+}
void code_heap::write_barrier(code_block *compiled)
{
return needs_fixup.count(compiled) > 0;
}
+bool code_heap::marked_p(heap_block *compiled)
+{
+ return allocator->state.marked_p(compiled);
+}
+
+void code_heap::set_marked_p(code_block *compiled)
+{
+ allocator->state.set_marked_p(compiled);
+}
+
+void code_heap::clear_mark_bits()
+{
+ allocator->state.clear_mark_bits();
+}
+
void code_heap::code_heap_free(code_block *compiled)
{
points_to_nursery.erase(compiled);
points_to_aging.erase(compiled);
needs_fixup.erase(compiled);
- heap_free(compiled);
+ allocator->free(compiled);
}
/* Allocate a code heap during startup */
void factor_vm::init_code_heap(cell size)
{
- code = new code_heap(secure_gc,size);
+ code = new code_heap(size);
}
bool factor_vm::in_code_heap_p(cell ptr)
factor_vm *parent;
explicit word_updater(factor_vm *parent_) : parent(parent_) {}
- void operator()(code_block *compiled)
+ void operator()(code_block *compiled, cell size)
{
parent->update_word_references(compiled);
}
iterate_code_heap(updater);
}
+/* After a full GC that did not grow the heap, we have to update references
+to literals and other words. */
+struct word_and_literal_code_heap_updater {
+ factor_vm *parent;
+
+ word_and_literal_code_heap_updater(factor_vm *parent_) : parent(parent_) {}
+
+ void operator()(heap_block *block, cell size)
+ {
+ parent->update_code_block_words_and_literals((code_block *)block);
+ }
+};
+
+void factor_vm::update_code_heap_words_and_literals()
+{
+ word_and_literal_code_heap_updater updater(this);
+ code->allocator->sweep(updater);
+}
+
+/* After growing the heap, we have to perform a full relocation to update
+references to card and deck arrays. */
+struct code_heap_relocator {
+ factor_vm *parent;
+
+ code_heap_relocator(factor_vm *parent_) : parent(parent_) {}
+
+ void operator()(code_block *block, cell size)
+ {
+ parent->relocate_code_block(block);
+ }
+};
+
+void factor_vm::relocate_code_heap()
+{
+ code_heap_relocator relocator(this);
+ code_heap_iterator<code_heap_relocator> iter(relocator);
+ code->allocator->sweep(iter);
+}
+
void factor_vm::primitive_modify_code_heap()
{
gc_root<array> alist(dpop(),this);
cell code = array_nth(compiled_data,4);
code_block *compiled = add_code_block(
- WORD_TYPE,
+ code_block_optimized,
code,
labels,
owner,
void factor_vm::primitive_code_room()
{
cell used, total_free, max_free;
- code->heap_usage(&used,&total_free,&max_free);
+ code->allocator->usage(&used,&total_free,&max_free);
dpush(tag_fixnum(code->seg->size / 1024));
dpush(tag_fixnum(used / 1024));
dpush(tag_fixnum(total_free / 1024));
code_block *code_heap::forward_code_block(code_block *compiled)
{
- return (code_block *)forwarding[compiled];
+ return (code_block *)allocator->state.forward_block(compiled);
}
struct callframe_forwarder {
function returns. */
void factor_vm::compact_code_heap(bool trace_contexts_p)
{
- code->compact_heap();
+ /* Figure out where blocks are going to go */
+ code->allocator->state.compute_forwarding();
+
+ /* Update references to the code heap from the data heap */
forward_object_xts();
if(trace_contexts_p)
{
forward_context_xts();
forward_callback_xts();
}
+
+ /* Move code blocks and update references amongst them (this requires
+ that the data heap is up to date since relocation looks up object XTs) */
+ code_heap_relocator relocator(this);
+ code_heap_iterator<code_heap_relocator> iter(relocator);
+ code->allocator->compact(iter);
}
struct stack_trace_stripper {
explicit stack_trace_stripper() {}
- void operator()(code_block *compiled)
+ void operator()(code_block *compiled, cell size)
{
compiled->owner = false_object;
}
namespace factor
{
-struct code_heap : heap {
+struct code_heap {
+ /* The actual memory area */
+ segment *seg;
+
+ /* Memory allocator */
+ free_list_allocator<heap_block> *allocator;
+
/* Set of blocks which need full relocation. */
std::set<code_block *> needs_fixup;
/* Code blocks which may reference objects in aging space or the nursery */
std::set<code_block *> points_to_aging;
- explicit code_heap(bool secure_gc, cell size);
+ explicit code_heap(cell size);
+ ~code_heap();
void write_barrier(code_block *compiled);
void clear_remembered_set();
bool needs_fixup_p(code_block *compiled);
+ bool marked_p(heap_block *compiled);
+ void set_marked_p(code_block *compiled);
+ void clear_mark_bits();
void code_heap_free(code_block *compiled);
code_block *forward_code_block(code_block *compiled);
};
if(immediate_p(pointer)) return;
- object *untagged = parent->untag<object>(pointer);
+ object *untagged = untag<object>(pointer);
if(!policy.should_copy_p(untagged))
+ {
+ policy.visited_object(untagged);
return;
+ }
object *forwarding = resolve_forwarding(untagged);
else if(policy.should_copy_p(forwarding))
untagged = promote_object(forwarding);
else
+ {
untagged = forwarding;
+ policy.visited_object(untagged);
+ }
*handle = RETAG(untagged,TAG(pointer));
}
object *promote_object(object *untagged)
{
- cell size = parent->untagged_object_size(untagged);
+ cell size = untagged->size();
object *newpointer = target->allot(size);
/* XXX not exception-safe */
if(!newpointer) longjmp(current_gc->gc_unwind,1);
stats->object_count++;
stats->bytes_copied += size;
+ policy.promoted_object(newpointer);
+
return newpointer;
}
ctx = ctx->next;
}
}
+
+ inline cell first_card_in_deck(cell deck)
+ {
+ return deck << (deck_bits - card_bits);
+ }
+
+ inline cell last_card_in_deck(cell deck)
+ {
+ return first_card_in_deck(deck + 1);
+ }
+
+ inline cell card_deck_for_address(cell a)
+ {
+ return addr_to_deck(a - this->data->start);
+ }
+
+ inline cell card_start_address(cell card)
+ {
+ return (card << card_bits) + this->data->start;
+ }
+
+ inline cell card_end_address(cell card)
+ {
+ return ((card + 1) << card_bits) + this->data->start;
+ }
+
+ void trace_partial_objects(cell start, cell end, cell card_start, cell card_end)
+ {
+ if(card_start < end)
+ {
+ start += sizeof(cell);
+
+ if(start < card_start) start = card_start;
+ if(end > card_end) end = card_end;
+
+ cell *slot_ptr = (cell *)start;
+ cell *end_ptr = (cell *)end;
+
+ if(slot_ptr != end_ptr)
+ {
+ for(; slot_ptr < end_ptr; slot_ptr++)
+ this->trace_handle(slot_ptr);
+ }
+ }
+ }
+
+ template<typename SourceGeneration, typename Unmarker>
+ void trace_cards(SourceGeneration *gen, card mask, Unmarker unmarker)
+ {
+ u64 start_time = current_micros();
+
+ card_deck *decks = this->data->decks;
+ card_deck *cards = this->data->cards;
+
+ cell gen_start_card = addr_to_card(gen->start - this->data->start);
+
+ cell first_deck = card_deck_for_address(gen->start);
+ cell last_deck = card_deck_for_address(gen->end);
+
+ cell start = 0, binary_start = 0, end = 0;
+
+ for(cell deck_index = first_deck; deck_index < last_deck; deck_index++)
+ {
+ if(decks[deck_index] & mask)
+ {
+ this->parent->gc_stats.decks_scanned++;
+
+ cell first_card = first_card_in_deck(deck_index);
+ cell last_card = last_card_in_deck(deck_index);
+
+ for(cell card_index = first_card; card_index < last_card; card_index++)
+ {
+ if(cards[card_index] & mask)
+ {
+ this->parent->gc_stats.cards_scanned++;
+
+ if(end < card_start_address(card_index))
+ {
+ start = gen->starts.find_object_containing_card(card_index - gen_start_card);
+ binary_start = start + this->parent->binary_payload_start((object *)start);
+ end = start + ((object *)start)->size();
+ }
+
+#ifdef FACTOR_DEBUG
+ assert(addr_to_card(start - this->data->start) <= card_index);
+ assert(start < card_end_address(card_index));
+#endif
+
+scan_next_object: {
+ trace_partial_objects(
+ start,
+ binary_start,
+ card_start_address(card_index),
+ card_end_address(card_index));
+ if(end < card_end_address(card_index))
+ {
+ start = gen->next_object_after(start);
+ if(start)
+ {
+ binary_start = start + this->parent->binary_payload_start((object *)start);
+ end = start + ((object *)start)->size();
+ goto scan_next_object;
+ }
+ }
+ }
+
+ unmarker(&cards[card_index]);
+
+ if(!start) goto end;
+ }
+ }
+
+ unmarker(&decks[deck_index]);
+ }
+ }
+
+end: this->parent->gc_stats.card_scan_time += (current_micros() - start_time);
+ }
+
+ /* Trace all literals referenced from a code block. Only for aging and nursery collections */
+ void trace_literal_references(code_block *compiled)
+ {
+ this->trace_handle(&compiled->owner);
+ this->trace_handle(&compiled->literals);
+ this->trace_handle(&compiled->relocation);
+ this->parent->gc_stats.code_blocks_scanned++;
+ }
+
+ void trace_code_heap_roots(std::set<code_block *> *remembered_set)
+ {
+ std::set<code_block *>::const_iterator iter = remembered_set->begin();
+ std::set<code_block *>::const_iterator end = remembered_set->end();
+
+ for(; iter != end; iter++) trace_literal_references(*iter);
+ }
};
}
return false;
else
{
- array *a = allot_array_internal<array>(depth / sizeof(cell));
+ array *a = allot_uninitialized_array<array>(depth / sizeof(cell));
memcpy(a + 1,(void*)bottom,depth);
dpush(tag<array>(a));
return true;
explicit copying_collector(factor_vm *parent_, generation_statistics *stats_, TargetGeneration *target_, Policy policy_) :
collector<TargetGeneration,Policy>(parent_,stats_,target_,policy_), scan(target_->here) {}
- inline cell first_card_in_deck(cell deck)
- {
- return deck << (deck_bits - card_bits);
- }
-
- inline cell last_card_in_deck(cell deck)
- {
- return first_card_in_deck(deck + 1);
- }
-
- inline cell card_deck_for_address(cell a)
- {
- return addr_to_deck(a - this->data->start);
- }
-
- inline cell card_start_address(cell card)
- {
- return (card << card_bits) + this->data->start;
- }
-
- inline cell card_end_address(cell card)
- {
- return ((card + 1) << card_bits) + this->data->start;
- }
-
- void trace_partial_objects(cell start, cell end, cell card_start, cell card_end)
- {
- if(card_start < end)
- {
- start += sizeof(cell);
-
- if(start < card_start) start = card_start;
- if(end > card_end) end = card_end;
-
- cell *slot_ptr = (cell *)start;
- cell *end_ptr = (cell *)end;
-
- if(slot_ptr != end_ptr)
- {
- for(; slot_ptr < end_ptr; slot_ptr++)
- this->trace_handle(slot_ptr);
- }
- }
- }
-
- template<typename SourceGeneration, typename Unmarker>
- void trace_cards(SourceGeneration *gen, card mask, Unmarker unmarker)
- {
- u64 start_time = current_micros();
-
- card_deck *decks = this->data->decks;
- card_deck *cards = this->data->cards;
-
- cell gen_start_card = addr_to_card(gen->start - this->data->start);
-
- cell first_deck = card_deck_for_address(gen->start);
- cell last_deck = card_deck_for_address(gen->end);
-
- cell start = 0, binary_start = 0, end = 0;
-
- for(cell deck_index = first_deck; deck_index < last_deck; deck_index++)
- {
- if(decks[deck_index] & mask)
- {
- this->parent->gc_stats.decks_scanned++;
-
- cell first_card = first_card_in_deck(deck_index);
- cell last_card = last_card_in_deck(deck_index);
-
- for(cell card_index = first_card; card_index < last_card; card_index++)
- {
- if(cards[card_index] & mask)
- {
- this->parent->gc_stats.cards_scanned++;
-
- if(end < card_start_address(card_index))
- {
- start = gen->find_object_containing_card(card_index - gen_start_card);
- binary_start = start + this->parent->binary_payload_start((object *)start);
- end = start + this->parent->untagged_object_size((object *)start);
- }
-
-#ifdef FACTOR_DEBUG
- assert(addr_to_card(start - this->data->start) <= card_index);
- assert(start < card_end_address(card_index));
-#endif
-
-scan_next_object: {
- trace_partial_objects(
- start,
- binary_start,
- card_start_address(card_index),
- card_end_address(card_index));
- if(end < card_end_address(card_index))
- {
- start = gen->next_object_after(this->parent,start);
- if(start)
- {
- binary_start = start + this->parent->binary_payload_start((object *)start);
- end = start + this->parent->untagged_object_size((object *)start);
- goto scan_next_object;
- }
- }
- }
-
- unmarker(&cards[card_index]);
-
- if(!start) goto end;
- }
- }
-
- unmarker(&decks[deck_index]);
- }
- }
-
-end: this->parent->gc_stats.card_scan_time += (current_micros() - start_time);
- }
-
- /* Trace all literals referenced from a code block. Only for aging and nursery collections */
- void trace_literal_references(code_block *compiled)
- {
- this->trace_handle(&compiled->owner);
- this->trace_handle(&compiled->literals);
- this->trace_handle(&compiled->relocation);
- this->parent->gc_stats.code_blocks_scanned++;
- }
-
- void trace_code_heap_roots(std::set<code_block *> *remembered_set)
- {
- std::set<code_block *>::const_iterator iter = remembered_set->begin();
- std::set<code_block *>::const_iterator end = remembered_set->end();
-
- for(; iter != end; iter++) trace_literal_references(*iter);
- }
-
void cheneys_algorithm()
{
while(scan && scan < this->target->here)
{
this->trace_slots((object *)scan);
- scan = this->target->next_object_after(this->parent,scan);
+ scan = this->target->next_object_after(scan);
}
}
};
aging_size = aging_size_;
tenured_size = tenured_size_;
- cell total_size = young_size + 2 * aging_size + 2 * tenured_size;
+ cell total_size = young_size + 2 * aging_size + tenured_size;
total_size += deck_size;
cards = new card[cards_size];
cards_end = cards + cards_size;
+ memset(cards,0,cards_size);
cell decks_size = addr_to_deck(total_size);
decks = new card_deck[decks_size];
decks_end = decks + decks_size;
+ memset(decks,0,decks_size);
start = align(seg->start,deck_size);
tenured = new tenured_space(tenured_size,start);
- tenured_semispace = new tenured_space(tenured_size,tenured->end);
- aging = new aging_space(aging_size,tenured_semispace->end);
+ aging = new aging_space(aging_size,tenured->end);
aging_semispace = new aging_space(aging_size,aging->end);
- nursery = new zone(young_size,aging_semispace->end);
+ nursery = new nursery_space(young_size,aging_semispace->end);
assert(seg->end - nursery->end <= deck_size);
}
delete aging;
delete aging_semispace;
delete tenured;
- delete tenured_semispace;
delete[] cards;
delete[] decks;
}
return new data_heap(young_size,aging_size,new_tenured_size);
}
-void factor_vm::clear_cards(old_space *gen)
+template<typename Generation> void data_heap::clear_cards(Generation *gen)
{
- cell first_card = addr_to_card(gen->start - data->start);
- cell last_card = addr_to_card(gen->end - data->start);
- memset(&data->cards[first_card],0,last_card - first_card);
+ cell first_card = addr_to_card(gen->start - start);
+ cell last_card = addr_to_card(gen->end - start);
+ memset(&cards[first_card],0,last_card - first_card);
}
-void factor_vm::clear_decks(old_space *gen)
+template<typename Generation> void data_heap::clear_decks(Generation *gen)
{
- cell first_deck = addr_to_deck(gen->start - data->start);
- cell last_deck = addr_to_deck(gen->end - data->start);
- memset(&data->decks[first_deck],0,last_deck - first_deck);
+ cell first_deck = addr_to_deck(gen->start - start);
+ cell last_deck = addr_to_deck(gen->end - start);
+ memset(&decks[first_deck],0,last_deck - first_deck);
}
-/* After garbage collection, any generations which are now empty need to have
-their allocation pointers and cards reset. */
-void factor_vm::reset_generation(old_space *gen)
+void data_heap::reset_generation(nursery_space *gen)
{
gen->here = gen->start;
- if(secure_gc) memset((void*)gen->start,69,gen->size);
+}
+void data_heap::reset_generation(aging_space *gen)
+{
+ gen->here = gen->start;
+ clear_cards(gen);
+ clear_decks(gen);
+ gen->starts.clear_object_start_offsets();
+}
+
+void data_heap::reset_generation(tenured_space *gen)
+{
clear_cards(gen);
clear_decks(gen);
- gen->clear_object_start_offsets();
}
void factor_vm::set_data_heap(data_heap *data_)
{
data = data_;
nursery = *data->nursery;
- nursery.here = nursery.start;
init_card_decks();
- reset_generation(data->aging);
- reset_generation(data->tenured);
}
-void factor_vm::init_data_heap(cell young_size, cell aging_size, cell tenured_size, bool secure_gc_)
+void factor_vm::init_data_heap(cell young_size, cell aging_size, cell tenured_size)
{
set_data_heap(new data_heap(young_size,aging_size,tenured_size));
- secure_gc = secure_gc_;
}
/* Size of the object pointed to by a tagged pointer */
if(immediate_p(tagged))
return 0;
else
- return untagged_object_size(untag<object>(tagged));
+ return untag<object>(tagged)->size();
}
/* Size of the object pointed to by an untagged pointer */
-cell factor_vm::untagged_object_size(object *pointer)
+cell object::size() const
{
- return align8(unaligned_object_size(pointer));
-}
+ if(free_p()) return ((free_heap_block *)this)->size();
-/* Size of the data area of an object pointed to by an untagged pointer */
-cell factor_vm::unaligned_object_size(object *pointer)
-{
- switch(pointer->h.hi_tag())
+ switch(h.hi_tag())
{
case ARRAY_TYPE:
- return array_size((array*)pointer);
+ return align(array_size((array*)this),data_alignment);
case BIGNUM_TYPE:
- return array_size((bignum*)pointer);
+ return align(array_size((bignum*)this),data_alignment);
case BYTE_ARRAY_TYPE:
- return array_size((byte_array*)pointer);
+ return align(array_size((byte_array*)this),data_alignment);
case STRING_TYPE:
- return string_size(string_capacity((string*)pointer));
+ return align(string_size(string_capacity((string*)this)),data_alignment);
case TUPLE_TYPE:
- return tuple_size(untag<tuple_layout>(((tuple *)pointer)->layout));
+ {
+ tuple_layout *layout = (tuple_layout *)UNTAG(((tuple *)this)->layout);
+ return align(tuple_size(layout),data_alignment);
+ }
case QUOTATION_TYPE:
- return sizeof(quotation);
+ return align(sizeof(quotation),data_alignment);
case WORD_TYPE:
- return sizeof(word);
+ return align(sizeof(word),data_alignment);
case FLOAT_TYPE:
- return sizeof(boxed_float);
+ return align(sizeof(boxed_float),data_alignment);
case DLL_TYPE:
- return sizeof(dll);
+ return align(sizeof(dll),data_alignment);
case ALIEN_TYPE:
- return sizeof(alien);
+ return align(sizeof(alien),data_alignment);
case WRAPPER_TYPE:
- return sizeof(wrapper);
+ return align(sizeof(wrapper),data_alignment);
case CALLSTACK_TYPE:
- return callstack_size(untag_fixnum(((callstack *)pointer)->length));
+ return align(callstack_size(untag_fixnum(((callstack *)this)->length)),data_alignment);
default:
- critical_error("Invalid header",(cell)pointer);
+ critical_error("Invalid header",(cell)this);
return 0; /* can't happen */
}
}
a.add(tag_fixnum((data->aging->end - data->aging->here) >> 10));
a.add(tag_fixnum((data->aging->size) >> 10));
- a.add(tag_fixnum((data->tenured->end - data->tenured->here) >> 10));
- a.add(tag_fixnum((data->tenured->size) >> 10));
+ //XXX
+ cell used, total_free, max_free;
+ data->tenured->usage(&used,&total_free,&max_free);
+ a.add(tag_fixnum(total_free >> 10));
+ a.add(tag_fixnum(used >> 10));
a.trim();
dpush(a.elements.value());
/* Disables GC and activates next-object ( -- obj ) primitive */
void factor_vm::begin_scan()
{
- heap_scan_ptr = data->tenured->start;
+ heap_scan_ptr = data->tenured->first_object();
gc_off = true;
}
if(!gc_off)
general_error(ERROR_HEAP_SCAN,false_object,false_object,NULL);
- if(heap_scan_ptr >= data->tenured->here)
+ if(heap_scan_ptr)
+ {
+ cell current = heap_scan_ptr;
+ heap_scan_ptr = data->tenured->next_object_after(heap_scan_ptr);
+ return tag_dynamic((object *)current);
+ }
+ else
return false_object;
-
- object *obj = (object *)heap_scan_ptr;
- heap_scan_ptr += untagged_object_size(obj);
- return tag_dynamic(obj);
}
/* Push object at heap scan cursor and advance; pushes f when done */
segment *seg;
- zone *nursery;
+ nursery_space *nursery;
aging_space *aging;
aging_space *aging_semispace;
tenured_space *tenured;
- tenured_space *tenured_semispace;
card *cards;
card *cards_end;
explicit data_heap(cell young_size, cell aging_size, cell tenured_size);
~data_heap();
data_heap *grow(cell requested_size);
+ template<typename Generation> void clear_cards(Generation *gen);
+ template<typename Generation> void clear_decks(Generation *gen);
+ void reset_generation(nursery_space *gen);
+ void reset_generation(aging_space *gen);
+ void reset_generation(tenured_space *gen);
};
}
namespace factor
{
-void factor_vm::print_chars(string* str)
+std::ostream &operator<<(std::ostream &out, const string *str)
{
- cell i;
- for(i = 0; i < string_capacity(str); i++)
- putchar(string_nth(str,i));
+ for(cell i = 0; i < string_capacity(str); i++)
+ out << (char)str->nth(i);
+ return out;
}
void factor_vm::print_word(word* word, cell nesting)
{
if(tagged<object>(word->vocabulary).type_p(STRING_TYPE))
- {
- print_chars(untag<string>(word->vocabulary));
- print_string(":");
- }
+ std::cout << untag<string>(word->vocabulary) << ":";
if(tagged<object>(word->name).type_p(STRING_TYPE))
- print_chars(untag<string>(word->name));
+ std::cout << untag<string>(word->name);
else
{
- print_string("#<not a string: ");
+ std::cout << "#<not a string: ";
print_nested_obj(word->name,nesting);
- print_string(">");
+ std::cout << ">";
}
}
-void factor_vm::print_factor_string(string* str)
+void factor_vm::print_factor_string(string *str)
{
- putchar('"');
- print_chars(str);
- putchar('"');
+ std::cout << '"' << str << '"';
}
void factor_vm::print_array(array* array, cell nesting)
for(i = 0; i < length; i++)
{
- print_string(" ");
+ std::cout << " ";
print_nested_obj(array_nth(array,i),nesting);
}
if(trimmed)
- print_string("...");
+ std::cout << "...";
}
void factor_vm::print_tuple(tuple *tuple, cell nesting)
tuple_layout *layout = untag<tuple_layout>(tuple->layout);
cell length = to_fixnum(layout->size);
- print_string(" ");
+ std::cout << " ";
print_nested_obj(layout->klass,nesting);
- cell i;
bool trimmed;
-
if(length > 10 && !full_output)
{
trimmed = true;
else
trimmed = false;
- for(i = 0; i < length; i++)
+ for(cell i = 0; i < length; i++)
{
- print_string(" ");
+ std::cout << " ";
print_nested_obj(tuple->data()[i],nesting);
}
if(trimmed)
- print_string("...");
+ std::cout << "...";
}
void factor_vm::print_nested_obj(cell obj, fixnum nesting)
{
if(nesting <= 0 && !full_output)
{
- print_string(" ... ");
+ std::cout << " ... ";
return;
}
switch(tagged<object>(obj).type())
{
case FIXNUM_TYPE:
- print_fixnum(untag_fixnum(obj));
+ std::cout << untag_fixnum(obj);
break;
case WORD_TYPE:
print_word(untag<word>(obj),nesting - 1);
print_factor_string(untag<string>(obj));
break;
case F_TYPE:
- print_string("f");
+ std::cout << "f";
break;
case TUPLE_TYPE:
- print_string("T{");
+ std::cout << "T{";
print_tuple(untag<tuple>(obj),nesting - 1);
- print_string(" }");
+ std::cout << " }";
break;
case ARRAY_TYPE:
- print_string("{");
+ std::cout << "{";
print_array(untag<array>(obj),nesting - 1);
- print_string(" }");
+ std::cout << " }";
break;
case QUOTATION_TYPE:
- print_string("[");
+ std::cout << "[";
quot = untag<quotation>(obj);
print_array(untag<array>(quot->array),nesting - 1);
- print_string(" ]");
+ std::cout << " ]";
break;
default:
- print_string("#<type ");
- print_cell(tagged<object>(obj).type());
- print_string(" @ ");
- print_cell_hex(obj);
- print_string(">");
+ std::cout << "#<type " << tagged<object>(obj).type() << " @ ";
+ std::cout << std::hex << obj << std::dec << ">";
break;
}
}
for(; start <= end; start++)
{
print_obj(*start);
- nl();
+ std::cout << std::endl;
}
}
void factor_vm::print_datastack()
{
- print_string("==== DATA STACK:\n");
+ std::cout << "==== DATA STACK:\n";
print_objects((cell *)ds_bot,(cell *)ds);
}
void factor_vm::print_retainstack()
{
- print_string("==== RETAIN STACK:\n");
+ std::cout << "==== RETAIN STACK:\n";
print_objects((cell *)rs_bot,(cell *)rs);
}
void operator()(stack_frame *frame)
{
parent->print_obj(parent->frame_executing(frame));
- print_string("\n");
+ std::cout << std::endl;
parent->print_obj(parent->frame_scan(frame));
- print_string("\n");
- print_string("word/quot addr: ");
- print_cell_hex((cell)parent->frame_executing(frame));
- print_string("\n");
- print_string("word/quot xt: ");
- print_cell_hex((cell)frame->xt);
- print_string("\n");
- print_string("return address: ");
- print_cell_hex((cell)FRAME_RETURN_ADDRESS(frame,parent));
- print_string("\n");
+ std::cout << std::endl;
+ std::cout << "word/quot addr: ";
+ std::cout << std::hex << (cell)parent->frame_executing(frame) << std::dec;
+ std::cout << std::endl;
+ std::cout << "word/quot xt: ";
+ std::cout << std::hex << (cell)frame->xt << std::dec;
+ std::cout << std::endl;
+ std::cout << "return address: ";
+ std::cout << std::hex << (cell)FRAME_RETURN_ADDRESS(frame,parent) << std::dec;
+ std::cout << std::endl;
}
};
void factor_vm::print_callstack()
{
- print_string("==== CALL STACK:\n");
+ std::cout << "==== CALL STACK:\n";
stack_frame_printer printer(this);
iterate_callstack(ctx,printer);
}
+struct padded_address {
+ cell value;
+
+ explicit padded_address(cell value_) : value(value_) {}
+};
+
+std::ostream &operator<<(std::ostream &out, const padded_address &value)
+{
+ char prev = out.fill('0');
+ out.width(sizeof(cell) * 2);
+ out << std::hex << value.value << std::dec;
+ out.fill(prev);
+ return out;
+}
+
void factor_vm::dump_cell(cell x)
{
- print_cell_hex_pad(x); print_string(": ");
+ std::cout << padded_address(x) << ": ";
x = *(cell *)x;
- print_cell_hex_pad(x); print_string(" tag "); print_cell(TAG(x));
- nl();
+ std::cout << padded_address(x) << " tag " << TAG(x) << std::endl;
}
void factor_vm::dump_memory(cell from, cell to)
dump_cell(from);
}
-void factor_vm::dump_zone(const char *name, zone *z)
+template<typename Generation>
+void factor_vm::dump_generation(const char *name, Generation *gen)
{
- print_string(name); print_string(": ");
- print_string("Start="); print_cell(z->start);
- print_string(", size="); print_cell(z->size);
- print_string(", here="); print_cell(z->here - z->start); nl();
+ std::cout << name << ": ";
+ std::cout << "Start=" << gen->start;
+ std::cout << ", size=" << gen->size;
+ std::cout << ", end=" << gen->end;
+ std::cout << std::endl;
}
void factor_vm::dump_generations()
{
- dump_zone("Nursery",&nursery);
- dump_zone("Aging",data->aging);
- dump_zone("Tenured",data->tenured);
-
- print_string("Cards: base=");
- print_cell((cell)data->cards);
- print_string(", size=");
- print_cell((cell)(data->cards_end - data->cards));
- nl();
+ dump_generation("Nursery",&nursery);
+ dump_generation("Aging",data->aging);
+ dump_generation("Tenured",data->tenured);
+
+ std::cout << "Cards:";
+ std::cout << "base=" << (cell)data->cards << ", ";
+ std::cout << "size=" << (cell)(data->cards_end - data->cards) << std::endl;
}
void factor_vm::dump_objects(cell type)
{
if(type == TYPE_COUNT || tagged<object>(obj).type_p(type))
{
- print_cell_hex_pad(obj);
- print_string(" ");
+ std::cout << padded_address(obj) << " ";
print_nested_obj(obj,2);
- nl();
+ std::cout << std::endl;
}
}
{
if(look_for == *scan)
{
- print_cell_hex_pad(obj);
- print_string(" ");
+ std::cout << padded_address(obj) << " ";
parent->print_nested_obj(obj,2);
- nl();
+ std::cout << std::endl;
}
}
};
end_scan();
}
-/* Dump all code blocks for debugging */
-void factor_vm::dump_code_heap()
-{
- cell reloc_size = 0, literal_size = 0;
+struct code_block_printer {
+ factor_vm *parent;
+ cell reloc_size, literal_size;
- heap_block *scan = code->first_block();
+ code_block_printer(factor_vm *parent_) :
+ parent(parent_), reloc_size(0), literal_size(0) {}
- while(scan)
+ void operator()(heap_block *scan, cell size)
{
const char *status;
- if(scan->type() == FREE_BLOCK_TYPE)
+ if(scan->free_p())
status = "free";
- else if(code->state->is_marked_p(scan))
+ else if(parent->code->marked_p(scan))
{
- reloc_size += object_size(((code_block *)scan)->relocation);
- literal_size += object_size(((code_block *)scan)->literals);
+ reloc_size += parent->object_size(((code_block *)scan)->relocation);
+ literal_size += parent->object_size(((code_block *)scan)->literals);
status = "marked";
}
else
{
- reloc_size += object_size(((code_block *)scan)->relocation);
- literal_size += object_size(((code_block *)scan)->literals);
+ reloc_size += parent->object_size(((code_block *)scan)->relocation);
+ literal_size += parent->object_size(((code_block *)scan)->literals);
status = "allocated";
}
- print_cell_hex((cell)scan); print_string(" ");
- print_cell_hex(scan->size()); print_string(" ");
- print_string(status); print_string("\n");
-
- scan = code->next_block(scan);
+ std::cout << std::hex << (cell)scan << std::dec << " ";
+ std::cout << std::hex << size << std::dec << " ";
+ std::cout << status << std::endl;
}
-
- print_cell(reloc_size); print_string(" bytes of relocation data\n");
- print_cell(literal_size); print_string(" bytes of literal data\n");
+};
+
+/* Dump all code blocks for debugging */
+void factor_vm::dump_code_heap()
+{
+ code_block_printer printer(this);
+ code->allocator->iterate(printer);
+ std::cout << printer.reloc_size << " bytes of relocation data\n";
+ std::cout << printer.literal_size << " bytes of literal data\n";
}
void factor_vm::factorbug()
{
if(fep_disabled)
{
- print_string("Low level debugger disabled\n");
+ std::cout << "Low level debugger disabled\n";
exit(1);
}
/* open_console(); */
- print_string("Starting low level debugger...\n");
- print_string(" Basic commands:\n");
- print_string("q -- continue executing Factor - NOT SAFE\n");
- print_string("im -- save image to fep.image\n");
- print_string("x -- exit Factor\n");
- print_string(" Advanced commands:\n");
- print_string("d <addr> <count> -- dump memory\n");
- print_string("u <addr> -- dump object at tagged <addr>\n");
- print_string(". <addr> -- print object at tagged <addr>\n");
- print_string("t -- toggle output trimming\n");
- print_string("s r -- dump data, retain stacks\n");
- print_string(".s .r .c -- print data, retain, call stacks\n");
- print_string("e -- dump environment\n");
- print_string("g -- dump generations\n");
- print_string("data -- data heap dump\n");
- print_string("words -- words dump\n");
- print_string("tuples -- tuples dump\n");
- print_string("refs <addr> -- find data heap references to object\n");
- print_string("push <addr> -- push object on data stack - NOT SAFE\n");
- print_string("code -- code heap dump\n");
+ std::cout << "Starting low level debugger...\n";
+ std::cout << " Basic commands:\n";
+ std::cout << "q -- continue executing Factor - NOT SAFE\n";
+ std::cout << "im -- save image to fep.image\n";
+ std::cout << "x -- exit Factor\n";
+ std::cout << " Advanced commands:\n";
+ std::cout << "d <addr> <count> -- dump memory\n";
+ std::cout << "u <addr> -- dump object at tagged <addr>\n";
+ std::cout << ". <addr> -- print object at tagged <addr>\n";
+ std::cout << "t -- toggle output trimming\n";
+ std::cout << "s r -- dump data, retain stacks\n";
+ std::cout << ".s .r .c -- print data, retain, call stacks\n";
+ std::cout << "e -- dump environment\n";
+ std::cout << "g -- dump generations\n";
+ std::cout << "data -- data heap dump\n";
+ std::cout << "words -- words dump\n";
+ std::cout << "tuples -- tuples dump\n";
+ std::cout << "refs <addr> -- find data heap references to object\n";
+ std::cout << "push <addr> -- push object on data stack - NOT SAFE\n";
+ std::cout << "code -- code heap dump\n";
bool seen_command = false;
{
char cmd[1024];
- print_string("READY\n");
+ std::cout << "READY\n";
fflush(stdout);
if(scanf("%1000s",cmd) <= 0)
{
cell addr = read_cell_hex();
print_obj(addr);
- print_string("\n");
+ std::cout << std::endl;
}
else if(strcmp(cmd,"t") == 0)
full_output = !full_output;
else if(strcmp(cmd,"refs") == 0)
{
cell addr = read_cell_hex();
- print_string("Data heap references:\n");
+ std::cout << "Data heap references:\n";
find_data_references(addr);
- nl();
+ std::cout << std::endl;
}
else if(strcmp(cmd,"words") == 0)
dump_objects(WORD_TYPE);
else if(strcmp(cmd,"code") == 0)
dump_code_heap();
else
- print_string("unknown command\n");
+ std::cout << "unknown command\n";
}
}
void factor_vm::primitive_die()
{
- print_string("The die word was called by the library. Unless you called it yourself,\n");
- print_string("you have triggered a bug in Factor. Please report.\n");
+ std::cout << "The die word was called by the library. Unless you called it yourself,\n";
+ std::cout << "you have triggered a bug in Factor. Please report.\n";
factorbug();
}
void fatal_error(const char *msg, cell tagged)
{
- print_string("fatal_error: "); print_string(msg);
- print_string(": "); print_cell_hex(tagged); nl();
+ std::cout << "fatal_error: " << msg;
+ std::cout << ": " << std::hex << tagged << std::dec;
+ std::cout << std::endl;
exit(1);
}
void critical_error(const char *msg, cell tagged)
{
- print_string("You have triggered a bug in Factor. Please report.\n");
- print_string("critical_error: "); print_string(msg);
- print_string(": "); print_cell_hex(tagged); nl();
+ std::cout << "You have triggered a bug in Factor. Please report.\n";
+ std::cout << "critical_error: " << msg;
+ std::cout << ": " << std::hex << tagged << std::dec;
+ std::cout << std::endl;
tls_vm()->factorbug();
}
void out_of_memory()
{
- print_string("Out of memory\n\n");
+ std::cout << "Out of memory\n\n";
tls_vm()->dump_generations();
exit(1);
}
crash. */
else
{
- print_string("You have triggered a bug in Factor. Please report.\n");
- print_string("early_error: ");
+ std::cout << "You have triggered a bug in Factor. Please report.\n";
+ std::cout << "early_error: ";
print_obj(error);
- nl();
+ std::cout << std::endl;
factorbug();
}
}
{
factor_vm *vm;
-unordered_map<THREADHANDLE, factor_vm*> thread_vms;
+std::map<THREADHANDLE, factor_vm*> thread_vms;
void init_globals()
{
p->max_pic_size = 3;
- p->secure_gc = false;
p->fep = false;
+ p->verbosegc = false;
p->signals = true;
#ifdef WINDOWS
else if(factor_arg(arg,STRING_LITERAL("-codeheap=%d"),&p->code_size));
else if(factor_arg(arg,STRING_LITERAL("-pic=%d"),&p->max_pic_size));
else if(factor_arg(arg,STRING_LITERAL("-callbacks=%d"),&p->callback_size));
- else if(STRCMP(arg,STRING_LITERAL("-securegc")) == 0) p->secure_gc = true;
else if(STRCMP(arg,STRING_LITERAL("-fep")) == 0) p->fep = true;
else if(STRCMP(arg,STRING_LITERAL("-nosignals")) == 0) p->signals = false;
+ else if(STRCMP(arg,STRING_LITERAL("-verbosegc")) == 0) p->verbosegc = true;
else if(STRNCMP(arg,STRING_LITERAL("-i="),3) == 0) p->image_path = arg + 3;
else if(STRCMP(arg,STRING_LITERAL("-console")) == 0) p->console = true;
}
/* Do some initialization that we do once only */
void factor_vm::do_stage1_init()
{
- print_string("*** Stage 2 early init... ");
+ std::cout << "*** Stage 2 early init... ";
fflush(stdout);
compile_all_words();
userenv[STAGE2_ENV] = true_object;
- print_string("done\n");
- fflush(stdout);
+ std::cout << "done\n";
}
void factor_vm::init_factor(vm_parameters *p)
if(p->signals)
init_signals();
+ verbosegc = p->verbosegc;
+
if(p->console)
open_console();
--- /dev/null
+namespace factor
+{
+
+static const cell free_list_count = 32;
+
+struct free_list {
+ free_heap_block *small_blocks[free_list_count];
+ free_heap_block *large_blocks;
+};
+
+template<typename Block> struct free_list_allocator {
+ cell size;
+ cell start;
+ cell end;
+ free_list free_blocks;
+ mark_bits<Block> state;
+
+ explicit free_list_allocator(cell size, cell start);
+ bool contains_p(Block *block);
+ Block *first_block();
+ Block *last_block();
+ Block *next_block_after(Block *block);
+ void clear_free_list();
+ void add_to_free_list(free_heap_block *block);
+ void initial_free_list(cell size);
+ void assert_free_block(free_heap_block *block);
+ free_heap_block *find_free_block(cell size);
+ free_heap_block *split_free_block(free_heap_block *block, cell size);
+ Block *allot(cell size);
+ void free(Block *block);
+ void usage(cell *used, cell *total_free, cell *max_free);
+ cell occupied();
+ void sweep();
+ template<typename Iterator> void sweep(Iterator &iter);
+ template<typename Iterator> void compact(Iterator &iter);
+ template<typename Iterator> void iterate(Iterator &iter);
+};
+
+template<typename Block>
+free_list_allocator<Block>::free_list_allocator(cell size_, cell start_) :
+ size(size_), start(start_), end(start_ + size_), state(mark_bits<Block>(size_,start_))
+{
+ initial_free_list(0);
+}
+
+template<typename Block> void free_list_allocator<Block>::clear_free_list()
+{
+ memset(&free_blocks,0,sizeof(free_list));
+}
+
+template<typename Block> bool free_list_allocator<Block>::contains_p(Block *block)
+{
+ return ((cell)block - start) < size;
+}
+
+template<typename Block> Block *free_list_allocator<Block>::first_block()
+{
+ return (Block *)start;
+}
+
+template<typename Block> Block *free_list_allocator<Block>::last_block()
+{
+ return (Block *)end;
+}
+
+template<typename Block> Block *free_list_allocator<Block>::next_block_after(Block *block)
+{
+ return (Block *)((cell)block + block->size());
+}
+
+template<typename Block> void free_list_allocator<Block>::add_to_free_list(free_heap_block *block)
+{
+ if(block->size() < free_list_count * block_granularity)
+ {
+ int index = block->size() / block_granularity;
+ block->next_free = free_blocks.small_blocks[index];
+ free_blocks.small_blocks[index] = block;
+ }
+ else
+ {
+ block->next_free = free_blocks.large_blocks;
+ free_blocks.large_blocks = block;
+ }
+}
+
+/* Called after reading the heap from the image file, and after heap compaction.
+Makes a free list consisting of one free block, at the very end. */
+template<typename Block> void free_list_allocator<Block>::initial_free_list(cell size)
+{
+ clear_free_list();
+ if(size != this->size)
+ {
+ free_heap_block *last_block = (free_heap_block *)(start + size);
+ last_block->make_free(end - (cell)last_block);
+ add_to_free_list(last_block);
+ }
+}
+
+template<typename Block> void free_list_allocator<Block>::assert_free_block(free_heap_block *block)
+{
+#ifdef FACTOR_DEBUG
+ assert(block->free_p());
+#endif
+}
+
+template<typename Block> free_heap_block *free_list_allocator<Block>::find_free_block(cell size)
+{
+ cell attempt = size;
+
+ while(attempt < free_list_count * block_granularity)
+ {
+ int index = attempt / block_granularity;
+ free_heap_block *block = free_blocks.small_blocks[index];
+ if(block)
+ {
+ assert_free_block(block);
+ free_blocks.small_blocks[index] = block->next_free;
+ return block;
+ }
+
+ attempt *= 2;
+ }
+
+ free_heap_block *prev = NULL;
+ free_heap_block *block = free_blocks.large_blocks;
+
+ while(block)
+ {
+ assert_free_block(block);
+ if(block->size() >= size)
+ {
+ if(prev)
+ prev->next_free = block->next_free;
+ else
+ free_blocks.large_blocks = block->next_free;
+ return block;
+ }
+
+ prev = block;
+ block = block->next_free;
+ }
+
+ return NULL;
+}
+
+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);
+ split->next_free = block->next_free;
+ block->make_free(size);
+ add_to_free_list(split);
+ }
+
+ return block;
+}
+
+template<typename Block> Block *free_list_allocator<Block>::allot(cell size)
+{
+ size = align(size,block_granularity);
+
+ free_heap_block *block = find_free_block(size);
+ if(block)
+ {
+ block = split_free_block(block,size);
+ return (Block *)block;
+ }
+ else
+ 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);
+}
+
+/* Compute total sum of sizes of free blocks, and size of largest free block */
+template<typename Block> void free_list_allocator<Block>::usage(cell *used, cell *total_free, cell *max_free)
+{
+ *used = 0;
+ *total_free = 0;
+ *max_free = 0;
+
+ Block *scan = first_block();
+ Block *end = last_block();
+
+ while(scan != end)
+ {
+ cell size = scan->size();
+
+ if(scan->free_p())
+ {
+ *total_free += size;
+ if(size > *max_free)
+ *max_free = size;
+ }
+ else
+ *used += size;
+
+ scan = next_block_after(scan);
+ }
+}
+
+/* The size of the heap after compaction */
+template<typename Block> cell free_list_allocator<Block>::occupied()
+{
+ Block *scan = first_block();
+ Block *last = last_block();
+
+ while(scan != last)
+ {
+ if(scan->free_p()) break;
+ else scan = next_block_after(scan);
+ }
+
+ if(scan != last)
+ {
+ free_heap_block *free_block = (free_heap_block *)scan;
+ assert(free_block->free_p());
+ assert((cell)scan + free_block->size() == end);
+
+ return (cell)scan - (cell)first_block();
+ }
+ else
+ return size;
+}
+
+template<typename Block>
+void free_list_allocator<Block>::sweep()
+{
+ this->clear_free_list();
+
+ Block *prev = NULL;
+ Block *scan = this->first_block();
+ Block *end = this->last_block();
+
+ while(scan != end)
+ {
+ cell size = scan->size();
+
+ if(scan->free_p())
+ {
+ if(prev && prev->free_p())
+ {
+ free_heap_block *free_prev = (free_heap_block *)prev;
+ free_prev->set_size(free_prev->size() + size);
+ }
+ else
+ prev = scan;
+ }
+ else if(this->state.marked_p(scan))
+ {
+ if(prev && prev->free_p())
+ this->add_to_free_list((free_heap_block *)prev);
+ prev = scan;
+ }
+ else
+ {
+ if(prev && prev->free_p())
+ {
+ free_heap_block *free_prev = (free_heap_block *)prev;
+ free_prev->set_size(free_prev->size() + size);
+ }
+ else
+ {
+ free_heap_block *free_block = (free_heap_block *)scan;
+ free_block->make_free(size);
+ prev = scan;
+ }
+ }
+
+ scan = (Block *)((cell)scan + size);
+ }
+
+ if(prev && prev->free_p())
+ this->add_to_free_list((free_heap_block *)prev);
+}
+
+template<typename Block>
+template<typename Iterator>
+void free_list_allocator<Block>::sweep(Iterator &iter)
+{
+ this->clear_free_list();
+
+ Block *prev = NULL;
+ Block *scan = this->first_block();
+ Block *end = this->last_block();
+
+ while(scan != end)
+ {
+ cell size = scan->size();
+
+ if(scan->free_p())
+ {
+ if(prev && prev->free_p())
+ {
+ free_heap_block *free_prev = (free_heap_block *)prev;
+ free_prev->set_size(free_prev->size() + size);
+ }
+ else
+ prev = scan;
+ }
+ else if(this->state.marked_p(scan))
+ {
+ if(prev && prev->free_p())
+ this->add_to_free_list((free_heap_block *)prev);
+ prev = scan;
+ iter(scan,size);
+ }
+ else
+ {
+ if(prev && prev->free_p())
+ {
+ free_heap_block *free_prev = (free_heap_block *)prev;
+ free_prev->set_size(free_prev->size() + size);
+ }
+ else
+ {
+ free_heap_block *free_block = (free_heap_block *)scan;
+ free_block->make_free(size);
+ prev = scan;
+ }
+ }
+
+ scan = (Block *)((cell)scan + size);
+ }
+
+ if(prev && prev->free_p())
+ this->add_to_free_list((free_heap_block *)prev);
+}
+
+/* The forwarding map must be computed first by calling
+state.compute_forwarding(). */
+template<typename Block>
+template<typename Iterator>
+void free_list_allocator<Block>::compact(Iterator &iter)
+{
+ heap_compactor<Block,Iterator> compactor(&state,first_block(),iter);
+ this->iterate(compactor);
+
+ /* Now update the free list; there will be a single free block at
+ the end */
+ this->initial_free_list((cell)compactor.address - this->start);
+}
+
+template<typename Block>
+template<typename Iterator>
+void free_list_allocator<Block>::iterate(Iterator &iter)
+{
+ Block *scan = first_block();
+ Block *end = last_block();
+
+ while(scan != end)
+ {
+ cell size = scan->size();
+ Block *next = (Block *)((cell)scan + size);
+ if(!scan->free_p()) iter(scan,size);
+ scan = next;
+ }
+}
+
+}
{
full_collector::full_collector(factor_vm *parent_) :
- copying_collector<tenured_space,full_policy>(
+ collector<tenured_space,full_policy>(
parent_,
&parent_->gc_stats.full_stats,
parent_->data->tenured,
collections */
void full_collector::mark_code_block(code_block *compiled)
{
- this->code->mark_block(compiled);
- trace_literal_references(compiled);
+ if(!this->code->marked_p(compiled))
+ {
+ this->code->set_marked_p(compiled);
+ trace_literal_references(compiled);
+ }
}
-void full_collector::cheneys_algorithm()
+void full_collector::mark_reachable_objects()
{
- while(scan && scan < target->here)
+ std::vector<object *> *mark_stack = &this->target->mark_stack;
+ while(!mark_stack->empty())
{
- object *obj = (object *)scan;
+ object *obj = mark_stack->back();
+ mark_stack->pop_back();
this->trace_slots(obj);
this->mark_object_code_block(obj);
- scan = target->next_object_after(this->parent,scan);
}
}
-/* After growing the heap, we have to perform a full relocation to update
-references to card and deck arrays. */
-struct big_code_heap_updater {
- factor_vm *parent;
-
- big_code_heap_updater(factor_vm *parent_) : parent(parent_) {}
-
- void operator()(heap_block *block)
- {
- parent->relocate_code_block((code_block *)block);
- }
-};
-
-/* After a full GC that did not grow the heap, we have to update references
-to literals and other words. */
-struct small_code_heap_updater {
- factor_vm *parent;
+struct object_start_map_updater {
+ object_start_map *starts;
- small_code_heap_updater(factor_vm *parent_) : parent(parent_) {}
+ object_start_map_updater(object_start_map *starts_) : starts(starts_) {}
- void operator()(heap_block *block)
+ void operator()(object *obj, cell size)
{
- parent->update_code_block_for_full_gc((code_block *)block);
+ starts->record_object_start_offset(obj);
}
};
{
full_collector collector(this);
- code->state->clear_mark_bits();
+ code->clear_mark_bits();
+ data->tenured->clear_mark_bits();
+ data->tenured->clear_mark_stack();
collector.trace_roots();
if(trace_contexts_p)
collector.trace_callbacks();
}
- collector.cheneys_algorithm();
+ collector.mark_reachable_objects();
+
+ data->tenured->starts.clear_object_start_offsets();
+ object_start_map_updater updater(&data->tenured->starts);
+ data->tenured->sweep(updater);
- reset_generation(data->aging);
- nursery.here = nursery.start;
+ data->reset_generation(data->tenured);
+ data->reset_generation(data->aging);
+ data->reset_generation(&nursery);
+ code->clear_remembered_set();
}
void factor_vm::collect_growing_heap(cell requested_bytes,
delete old;
if(compact_code_heap_p)
- {
compact_code_heap(trace_contexts_p);
- big_code_heap_updater updater(this);
- iterate_code_heap(updater);
- }
else
- {
- big_code_heap_updater updater(this);
- code->free_unmarked(updater);
- }
-
- code->clear_remembered_set();
+ relocate_code_heap();
}
void factor_vm::collect_full(bool trace_contexts_p, bool compact_code_heap_p)
{
- /* Copy all live objects to the tenured semispace. */
- std::swap(data->tenured,data->tenured_semispace);
- reset_generation(data->tenured);
collect_full_impl(trace_contexts_p);
if(compact_code_heap_p)
- {
compact_code_heap(trace_contexts_p);
- big_code_heap_updater updater(this);
- iterate_code_heap(updater);
- }
else
- {
- small_code_heap_updater updater(this);
- code->free_unmarked(updater);
- }
-
- code->clear_remembered_set();
+ update_code_heap_words_and_literals();
}
}
struct full_policy {
factor_vm *parent;
- zone *tenured;
+ tenured_space *tenured;
full_policy(factor_vm *parent_) : parent(parent_), tenured(parent->data->tenured) {}
{
return !tenured->contains_p(untagged);
}
+
+ void promoted_object(object *obj)
+ {
+ tenured->mark_and_push(obj);
+ }
+
+ void visited_object(object *obj)
+ {
+ if(!tenured->marked_p(obj))
+ tenured->mark_and_push(obj);
+ }
};
-struct full_collector : copying_collector<tenured_space,full_policy> {
+struct full_collector : collector<tenured_space,full_policy> {
bool trace_contexts_p;
full_collector(factor_vm *parent_);
void trace_callbacks();
void trace_literal_references(code_block *compiled);
void mark_code_block(code_block *compiled);
- void cheneys_algorithm();
+ void mark_reachable_objects();
};
}
current_gc = new gc_state(op);
+ if(verbosegc)
+ std::cout << "GC requested, op=" << op << std::endl;
+
/* Keep trying to GC higher and higher generations until we don't run out
of space */
if(setjmp(current_gc->gc_unwind))
current_gc->op = collect_growing_heap_op;
break;
default:
- critical_error("Bad GC op\n",op);
+ critical_error("Bad GC op",current_gc->op);
break;
}
+
+ if(verbosegc)
+ std::cout << "GC rewind, op=" << current_gc->op << std::endl;
}
switch(current_gc->op)
record_gc_stats(&gc_stats.full_stats);
break;
default:
- critical_error("Bad GC op\n",op);
+ critical_error("Bad GC op\n",current_gc->op);
break;
}
+ if(verbosegc)
+ std::cout << "GC done, op=" << current_gc->op << std::endl;
+
delete current_gc;
current_gc = NULL;
}
else
{
/* If tenured space does not have enough room, collect */
- if(data->tenured->here + size > data->tenured->end)
+ //XXX
+ //if(data->tenured->here + size > data->tenured->end)
primitive_full_gc();
/* If it still won't fit, grow the heap */
- if(data->tenured->here + size > data->tenured->end)
+ //XXX
+ //if(data->tenured->here + size > data->tenured->end)
{
gc(collect_growing_heap_op,
size, /* requested size */
return array_size<Array>(array_capacity(array));
}
-template<typename Array> Array *factor_vm::allot_array_internal(cell capacity)
+template<typename Array> Array *factor_vm::allot_uninitialized_array(cell capacity)
{
Array *array = allot<Array>(array_size<Array>(capacity));
array->capacity = tag_fixnum(capacity);
if(capacity < to_copy)
to_copy = capacity;
- Array *new_array = allot_array_internal<Array>(capacity);
+ Array *new_array = allot_uninitialized_array<Array>(capacity);
memcpy(new_array + 1,array.untagged() + 1,to_copy * Array::element_size);
memset((char *)(new_array + 1) + to_copy * Array::element_size,
+++ /dev/null
-#include "master.hpp"
-
-/* This malloc-style heap code is reasonably generic. Maybe in the future, it
-will be used for the data heap too, if we ever get mark/sweep/compact GC. */
-
-namespace factor
-{
-
-void heap::clear_free_list()
-{
- memset(&free,0,sizeof(heap_free_list));
-}
-
-heap::heap(bool secure_gc_, cell size, bool executable_p) : secure_gc(secure_gc_)
-{
- if(size > (1L << (sizeof(cell) * 8 - 6))) fatal_error("Heap too large",size);
- seg = new segment(align_page(size),executable_p);
- if(!seg) fatal_error("Out of memory in heap allocator",size);
- state = new mark_bits<heap_block,block_size_increment>(seg->start,size);
- clear_free_list();
-}
-
-heap::~heap()
-{
- delete seg;
- seg = NULL;
- delete state;
- state = NULL;
-}
-
-void heap::add_to_free_list(free_heap_block *block)
-{
- if(block->size() < free_list_count * block_size_increment)
- {
- int index = block->size() / block_size_increment;
- block->next_free = free.small_blocks[index];
- free.small_blocks[index] = block;
- }
- else
- {
- block->next_free = free.large_blocks;
- free.large_blocks = block;
- }
-}
-
-/* Called after reading the code heap from the image file, and after code heap
-compaction. Makes a free list consisting of one free block, at the very end. */
-void heap::build_free_list(cell size)
-{
- clear_free_list();
- free_heap_block *end = (free_heap_block *)(seg->start + size);
- end->set_type(FREE_BLOCK_TYPE);
- end->set_size(seg->end - (cell)end);
- add_to_free_list(end);
-}
-
-void heap::assert_free_block(free_heap_block *block)
-{
- if(block->type() != FREE_BLOCK_TYPE)
- critical_error("Invalid block in free list",(cell)block);
-}
-
-free_heap_block *heap::find_free_block(cell size)
-{
- cell attempt = size;
-
- while(attempt < free_list_count * block_size_increment)
- {
- int index = attempt / block_size_increment;
- free_heap_block *block = free.small_blocks[index];
- if(block)
- {
- assert_free_block(block);
- free.small_blocks[index] = block->next_free;
- return block;
- }
-
- attempt *= 2;
- }
-
- free_heap_block *prev = NULL;
- free_heap_block *block = free.large_blocks;
-
- while(block)
- {
- assert_free_block(block);
- if(block->size() >= size)
- {
- if(prev)
- prev->next_free = block->next_free;
- else
- free.large_blocks = block->next_free;
- return block;
- }
-
- prev = block;
- block = block->next_free;
- }
-
- return NULL;
-}
-
-free_heap_block *heap::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->set_type(FREE_BLOCK_TYPE);
- split->set_size(block->size() - size);
- split->next_free = block->next_free;
- block->set_size(size);
- add_to_free_list(split);
- }
-
- return block;
-}
-
-/* Allocate a block of memory from the mark and sweep GC heap */
-heap_block *heap::heap_allot(cell size, cell type)
-{
- size = (size + block_size_increment - 1) & ~(block_size_increment - 1);
-
- free_heap_block *block = find_free_block(size);
- if(block)
- {
- block = split_free_block(block,size);
- block->set_type(type);
- return block;
- }
- else
- return NULL;
-}
-
-/* Deallocates a block manually */
-void heap::heap_free(heap_block *block)
-{
- block->set_type(FREE_BLOCK_TYPE);
- add_to_free_list((free_heap_block *)block);
-}
-
-void heap::mark_block(heap_block *block)
-{
- state->set_marked_p(block,true);
-}
-
-/* Compute total sum of sizes of free blocks, and size of largest free block */
-void heap::heap_usage(cell *used, cell *total_free, cell *max_free)
-{
- *used = 0;
- *total_free = 0;
- *max_free = 0;
-
- heap_block *scan = first_block();
-
- while(scan)
- {
- cell size = scan->size();
-
- if(scan->type() == FREE_BLOCK_TYPE)
- {
- *total_free += size;
- if(size > *max_free)
- *max_free = size;
- }
- else
- *used += size;
-
- scan = next_block(scan);
- }
-}
-
-/* The size of the heap after compaction */
-cell heap::heap_size()
-{
- heap_block *scan = first_block();
-
- while(scan)
- {
- if(scan->type() == FREE_BLOCK_TYPE) break;
- else scan = next_block(scan);
- }
-
- assert(scan->type() == FREE_BLOCK_TYPE);
- assert((cell)scan + scan->size() == seg->end);
-
- return (cell)scan - (cell)first_block();
-}
-
-void heap::compact_heap()
-{
- forwarding.clear();
-
- heap_block *scan = first_block();
- char *address = (char *)scan;
-
- /* Slide blocks up while building the forwarding hashtable. */
- while(scan)
- {
- heap_block *next = next_block(scan);
-
- if(state->is_marked_p(scan))
- {
- cell size = scan->size();
- memmove(address,scan,size);
- forwarding[scan] = address;
- address += size;
- }
-
- scan = next;
- }
-
- /* Now update the free list; there will be a single free block at
- the end */
- build_free_list((cell)address - seg->start);
-}
-
-heap_block *heap::free_allocated(heap_block *prev, heap_block *scan)
-{
- if(secure_gc)
- memset(scan + 1,0,scan->size() - sizeof(heap_block));
-
- if(prev && prev->type() == FREE_BLOCK_TYPE)
- {
- prev->set_size(prev->size() + scan->size());
- return prev;
- }
- else
- {
- scan->set_type(FREE_BLOCK_TYPE);
- return scan;
- }
-}
-
-}
+++ /dev/null
-namespace factor
-{
-
-static const cell free_list_count = 32;
-static const cell block_size_increment = 16;
-
-struct heap_free_list {
- free_heap_block *small_blocks[free_list_count];
- free_heap_block *large_blocks;
-};
-
-struct heap {
- bool secure_gc;
- segment *seg;
- heap_free_list free;
- mark_bits<heap_block,block_size_increment> *state;
- unordered_map<heap_block *, char *> forwarding;
-
- explicit heap(bool secure_gc_, cell size, bool executable_p);
- ~heap();
-
- inline heap_block *next_block(heap_block *block)
- {
- cell next = ((cell)block + block->size());
- if(next == seg->end)
- return NULL;
- else
- return (heap_block *)next;
- }
-
- inline heap_block *first_block()
- {
- return (heap_block *)seg->start;
- }
-
- inline heap_block *last_block()
- {
- return (heap_block *)seg->end;
- }
-
- void clear_free_list();
- void new_heap(cell size);
- void add_to_free_list(free_heap_block *block);
- void build_free_list(cell size);
- void assert_free_block(free_heap_block *block);
- free_heap_block *find_free_block(cell size);
- free_heap_block *split_free_block(free_heap_block *block, cell size);
- heap_block *heap_allot(cell size, cell type);
- void heap_free(heap_block *block);
- void mark_block(heap_block *block);
- void heap_usage(cell *used, cell *total_free, cell *max_free);
- cell heap_size();
- void compact_heap();
-
- heap_block *free_allocated(heap_block *prev, heap_block *scan);
-
- /* After code GC, all referenced code blocks have status set to B_MARKED, so any
- which are allocated and not marked can be reclaimed. */
- template<typename Iterator> void free_unmarked(Iterator &iter)
- {
- clear_free_list();
-
- heap_block *prev = NULL;
- heap_block *scan = first_block();
-
- while(scan)
- {
- if(scan->type() == FREE_BLOCK_TYPE)
- {
- if(prev && prev->type() == FREE_BLOCK_TYPE)
- prev->set_size(prev->size() + scan->size());
- else
- prev = scan;
- }
- else if(state->is_marked_p(scan))
- {
- if(prev && prev->type() == FREE_BLOCK_TYPE)
- add_to_free_list((free_heap_block *)prev);
- prev = scan;
- iter(scan);
- }
- else
- prev = free_allocated(prev,scan);
-
- scan = next_block(scan);
- }
-
- if(prev && prev->type() == FREE_BLOCK_TYPE)
- add_to_free_list((free_heap_block *)prev);
- }
-};
-
-}
init_data_heap(p->young_size,
p->aging_size,
- p->tenured_size,
- p->secure_gc);
+ p->tenured_size);
clear_gc_stats();
if((cell)bytes_read != h->data_size)
{
- print_string("truncated image: ");
- print_fixnum(bytes_read);
- print_string(" bytes read, ");
- print_cell(h->data_size);
- print_string(" bytes expected\n");
+ std::cout << "truncated image: " << bytes_read << " bytes read, ";
+ std::cout << h->data_size << " bytes expected\n";
fatal_error("load_data_heap failed",0);
}
- data->tenured->here = data->tenured->start + h->data_size;
+ data->tenured->initial_free_list(h->data_size);
}
void factor_vm::load_code_heap(FILE *file, image_header *h, vm_parameters *p)
if(h->code_size != 0)
{
- size_t bytes_read = fread(code->first_block(),1,h->code_size,file);
+ size_t bytes_read = fread(code->allocator->first_block(),1,h->code_size,file);
if(bytes_read != h->code_size)
{
- print_string("truncated image: ");
- print_fixnum(bytes_read);
- print_string(" bytes read, ");
- print_cell(h->code_size);
- print_string(" bytes expected\n");
+ std::cout << "truncated image: " << bytes_read << " bytes read, ";
+ std::cout << h->code_size << " bytes expected\n";
fatal_error("load_code_heap failed",0);
}
}
- code->build_free_list(h->code_size);
+ code->allocator->initial_free_list(h->code_size);
}
void factor_vm::data_fixup(cell *handle, cell data_relocation_base)
data_fixup(&t->layout,data_relocation_base);
cell *scan = t->data();
- cell *end = (cell *)((cell)object + untagged_object_size(object));
+ cell *end = (cell *)((cell)object + object->size());
for(; scan < end; scan++)
data_fixup(scan,data_relocation_base);
while(obj)
{
relocate_object((object *)obj,data_relocation_base,code_relocation_base);
- data->tenured->record_object_start_offset((object *)obj);
- obj = data->tenured->next_object_after(this,obj);
+ data->tenured->starts.record_object_start_offset((object *)obj);
+ obj = data->tenured->next_object_after(obj);
}
}
code_block_fixupper(factor_vm *parent_, cell data_relocation_base_) :
parent(parent_), data_relocation_base(data_relocation_base_) { }
- void operator()(code_block *compiled)
+ void operator()(code_block *compiled, cell size)
{
parent->fixup_code_block(compiled,data_relocation_base);
}
FILE *file = OPEN_READ(p->image_path);
if(file == NULL)
{
- print_string("Cannot open image file: "); print_native_string(p->image_path); nl();
- print_string(strerror(errno)); nl();
+ std::cout << "Cannot open image file: " << p->image_path << std::endl;
+ std::cout << strerror(errno) << std::endl;
exit(1);
}
file = OPEN_WRITE(filename);
if(file == NULL)
{
- print_string("Cannot open image file: "); print_native_string(filename); nl();
- print_string(strerror(errno)); nl();
+ std::cout << "Cannot open image file: " << filename << std::endl;
+ std::cout << strerror(errno) << std::endl;
return false;
}
h.magic = image_magic;
h.version = image_version;
h.data_relocation_base = data->tenured->start;
- h.data_size = data->tenured->here - data->tenured->start;
+ h.data_size = data->tenured->occupied();
h.code_relocation_base = code->seg->start;
- h.code_size = code->heap_size();
+ h.code_size = code->allocator->occupied();
h.true_object = true_object;
h.bignum_zero = bignum_zero;
if(fwrite(&h,sizeof(image_header),1,file) != 1) ok = false;
if(fwrite((void*)data->tenured->start,h.data_size,1,file) != 1) ok = false;
- if(fwrite(code->first_block(),h.code_size,1,file) != 1) ok = false;
+ if(fwrite(code->allocator->first_block(),h.code_size,1,file) != 1) ok = false;
if(fclose(file)) ok = false;
if(!ok)
- {
- print_string("save-image failed: "); print_string(strerror(errno)); nl();
- }
+ std::cout << "save-image failed: " << strerror(errno) << std::endl;
return ok;
}
cell ds_size, rs_size;
cell young_size, aging_size, tenured_size;
cell code_size;
- bool secure_gc;
bool fep;
+ bool verbosegc;
bool console;
bool signals;
cell max_pic_size;
check_code_pointer((cell)old_xt);
code_block *old_block = (code_block *)old_xt - 1;
- cell old_type = old_block->type();
-#ifdef FACTOR_DEBUG
- /* The call target was either another PIC,
- or a compiled quotation (megamorphic stub) */
- assert(old_type == PIC_TYPE || old_type == QUOTATION_TYPE);
-#endif
-
- if(old_type == PIC_TYPE)
+ /* Free the old PIC since we know its unreachable */
+ if(old_block->pic_p())
code->code_heap_free(old_block);
}
struct inline_cache_jit : public jit {
fixnum index;
- explicit inline_cache_jit(cell generic_word_,factor_vm *vm) : jit(PIC_TYPE,generic_word_,vm) {};
+ explicit inline_cache_jit(cell generic_word_,factor_vm *vm) : jit(code_block_pic,generic_word_,vm) {};
void emit_check(cell klass);
void compile_inline_cache(fixnum index,
set_call_target(return_address,xt);
#ifdef PIC_DEBUG
- printf("Updated %s call site 0x%lx with 0x%lx\n",
- tail_call_site_p(return_address) ? "tail" : "non-tail",
- return_address,
- (cell)xt);
+ std::cout << "Updated "
+ << (tail_call_site_p(return_address) ? "tail" : "non-tail")
+ << " call site 0x" << std::hex << return_address << std::dec
+ << " with " << std::hex << (cell)xt << std::dec;
#endif
return xt;
return;
}
- gc_root<byte_array> buf(allot_array_internal<byte_array>(size),this);
+ gc_root<byte_array> buf(allot_uninitialized_array<byte_array>(size),this);
for(;;)
{
- polymorphic inline caches (inline_cache.cpp) */
/* Allocates memory */
-jit::jit(cell type_, cell owner_, factor_vm *vm)
+jit::jit(code_block_type type_, cell owner_, factor_vm *vm)
: type(type_),
owner(owner_,vm),
code(vm),
{
struct jit {
- cell type;
+ code_block_type type;
gc_root<object> owner;
growable_byte_array code;
growable_byte_array relocation;
cell offset;
factor_vm *parent;
- explicit jit(cell jit_type, cell owner, factor_vm *vm);
+ explicit jit(code_block_type type, cell owner, factor_vm *parent);
void compute_position(cell offset);
void emit_relocation(cell code_template);
void emit_subprimitive(cell word_) {
gc_root<word> word(word_,parent);
gc_root<array> code_pair(word->subprimitive,parent);
- literals.append(parent->untag<array>(array_nth(code_pair.untagged(),0)));
+ literals.append(untag<array>(array_nth(code_pair.untagged(),0)));
emit(array_nth(code_pair.untagged(),1));
}
return (a + (b-1)) & ~(b-1);
}
-inline static cell align8(cell a)
-{
- return align(a,8);
-}
+static const cell data_alignment = 16;
#define WORD_SIZE (signed)(sizeof(cell)*8)
#define TYPE_COUNT 15
-/* Not real types, but code_block's type can be set to this */
-#define PIC_TYPE 16
-#define FREE_BLOCK_TYPE 17
+enum code_block_type
+{
+ code_block_unoptimized,
+ code_block_optimized,
+ code_block_profiling,
+ code_block_pic
+};
/* Constants used when floating-point trap exceptions are thrown */
enum
explicit header(cell value_) : value(value_ << TAG_BITS) {}
- void check_header() {
+ void check_header() const
+ {
#ifdef FACTOR_DEBUG
assert(TAG(value) == FIXNUM_TYPE && untag_fixnum(value) < TYPE_COUNT);
#endif
}
- cell hi_tag() {
+ cell hi_tag() const
+ {
check_header();
return value >> TAG_BITS;
}
- bool forwarding_pointer_p() {
+ bool forwarding_pointer_p() const
+ {
return TAG(value) == GC_COLLECTED;
}
- object *forwarding_pointer() {
+ object *forwarding_pointer() const
+ {
return (object *)UNTAG(value);
}
- void forward_to(object *pointer) {
+ void forward_to(object *pointer)
+ {
value = RETAG(pointer,GC_COLLECTED);
}
};
struct object {
NO_TYPE_CHECK;
header h;
- cell *slots() { return (cell *)this; }
+
+ cell size() const;
+
+ cell *slots() const { return (cell *)this; }
+
+ /* Only valid for objects in tenured space; must fast to free_heap_block
+ to do anything with it if its free */
+ bool free_p() const
+ {
+ return h.value & 1 == 1;
+ }
};
/* Assembly code makes assumptions about the layout of this struct */
/* tagged */
cell capacity;
- cell *data() { return (cell *)(this + 1); }
+ cell *data() const { return (cell *)(this + 1); }
};
/* These are really just arrays, but certain elements have special
/* tagged */
cell capacity;
- cell *data() { return (cell *)(this + 1); }
+ cell *data() const { return (cell *)(this + 1); }
};
struct byte_array : public object {
/* tagged */
cell capacity;
- template<typename Scalar> Scalar *data() { return (Scalar *)(this + 1); }
+#ifndef FACTOR_64
+ cell padding0;
+ cell padding1;
+#endif
+
+ template<typename Scalar> Scalar *data() const { return (Scalar *)(this + 1); }
};
/* Assembly code makes assumptions about the layout of this struct */
/* tagged */
cell hashcode;
- u8 *data() { return (u8 *)(this + 1); }
+ u8 *data() const { return (u8 *)(this + 1); }
+
+ cell nth(cell i) const;
};
/* The compiled code heap is structured into blocks. */
{
cell header;
- cell type() { return (header >> 1) & 0x1f; }
- void set_type(cell type)
+ bool free_p() const
+ {
+ return header & 1 == 1;
+ }
+
+ cell size() const
{
- header = ((header & ~(0x1f << 1)) | (type << 1));
+ cell bytes = header >> 3;
+#ifdef FACTOR_DEBUG
+ assert(bytes > 0);
+#endif
+ return bytes;
}
- cell size() { return (header >> 6); }
void set_size(cell size)
{
- header = (header & 0x2f) | (size << 6);
+ header = ((header & 0x7) | (size << 3));
}
};
struct free_heap_block : public heap_block
{
free_heap_block *next_free;
+
+ void make_free(cell size)
+ {
+ header = (size << 3) | 1;
+ }
};
struct code_block : public heap_block
cell literals; /* tagged pointer to array or f */
cell relocation; /* tagged pointer to byte-array or f */
- void *xt() { return (void *)(this + 1); }
+ void *xt() const
+ {
+ return (void *)(this + 1);
+ }
+
+ code_block_type type() const
+ {
+ return (code_block_type)((header >> 1) & 0x3);
+ }
+
+ void set_type(code_block_type type)
+ {
+ header = ((header & ~0x7) | (type << 1));
+ }
+
+ bool pic_p() const
+ {
+ return type() == code_block_pic;
+ }
+
+ bool optimized_p() const
+ {
+ return type() == code_block_optimized;
+ }
};
/* Assembly code makes assumptions about the layout of this struct */
/* tagged */
cell length;
- stack_frame *frame_at(cell offset)
+ stack_frame *frame_at(cell offset) const
{
return (stack_frame *)((char *)(this + 1) + offset);
}
- stack_frame *top() { return (stack_frame *)(this + 1); }
- stack_frame *bottom() { return (stack_frame *)((cell)(this + 1) + untag_fixnum(length)); }
+ stack_frame *top() const { return (stack_frame *)(this + 1); }
+ stack_frame *bottom() const { return (stack_frame *)((cell)(this + 1) + untag_fixnum(length)); }
};
struct tuple : public object {
/* tagged layout */
cell layout;
- cell *data() { return (cell *)(this + 1); }
+ cell *data() const { return (cell *)(this + 1); }
};
}
{
factor_vm *parent;
- void push() { parent->check_tagged_pointer(tagged<Type>::value()); parent->gc_locals.push_back((cell)this); }
+ void push() { parent->gc_locals.push_back((cell)this); }
explicit gc_root(cell value_,factor_vm *vm) : tagged<Type>(value_),parent(vm) { push(); }
explicit gc_root(Type *value_, factor_vm *vm) : tagged<Type>(value_),parent(vm) { push(); }
{
THREADHANDLE thread_id = pthread_from_mach_thread_np(thread);
assert(thread_id);
- unordered_map<THREADHANDLE, factor_vm*>::const_iterator vm = thread_vms.find(thread_id);
+ std::map<THREADHANDLE, factor_vm*>::const_iterator vm = thread_vms.find(thread_id);
if (vm != thread_vms.end())
vm->second->call_fault_handler(exception,code,exc_state,thread_state,float_state);
}
namespace factor
{
-const int forwarding_granularity = 128;
+const int block_granularity = 16;
+const int forwarding_granularity = 64;
-template<typename Block, int Granularity> struct mark_bits {
+template<typename Block> struct mark_bits {
cell start;
cell size;
cell bits_size;
- unsigned int *marked;
- unsigned int *freed;
- cell forwarding_size;
+ u64 *marked;
cell *forwarding;
void clear_mark_bits()
{
- memset(marked,0,bits_size * sizeof(unsigned int));
- }
-
- void clear_free_bits()
- {
- memset(freed,0,bits_size * sizeof(unsigned int));
+ memset(marked,0,bits_size * sizeof(u64));
}
void clear_forwarding()
{
- memset(forwarding,0,forwarding_size * sizeof(cell));
+ memset(forwarding,0,bits_size * sizeof(cell));
}
explicit mark_bits(cell start_, cell size_) :
start(start_),
size(size_),
- bits_size(size / Granularity / 32),
- marked(new unsigned int[bits_size]),
- freed(new unsigned int[bits_size]),
- forwarding_size(size / Granularity / forwarding_granularity),
- forwarding(new cell[forwarding_size])
+ bits_size(size / block_granularity / forwarding_granularity),
+ marked(new u64[bits_size]),
+ forwarding(new cell[bits_size])
{
clear_mark_bits();
- clear_free_bits();
clear_forwarding();
}
{
delete[] marked;
marked = NULL;
- delete[] freed;
- freed = NULL;
delete[] forwarding;
forwarding = NULL;
}
- std::pair<cell,cell> bitmap_deref(Block *address)
+ cell block_line(Block *address)
{
- cell word_number = (((cell)address - start) / Granularity);
- cell word_index = (word_number >> 5);
- cell word_shift = (word_number & 31);
+ return (((cell)address - start) / block_granularity);
+ }
-#ifdef FACTOR_DEBUG
- assert(word_index < bits_size);
-#endif
+ Block *line_block(cell line)
+ {
+ return (Block *)(line * block_granularity + start);
+ }
+ std::pair<cell,cell> bitmap_deref(Block *address)
+ {
+ cell line_number = block_line(address);
+ cell word_index = (line_number >> 6);
+ cell word_shift = (line_number & 63);
return std::make_pair(word_index,word_shift);
}
- bool bitmap_elt(unsigned int *bits, Block *address)
+ bool bitmap_elt(u64 *bits, Block *address)
{
std::pair<cell,cell> pair = bitmap_deref(address);
- return (bits[pair.first] & (1 << pair.second)) != 0;
+ return (bits[pair.first] & ((u64)1 << pair.second)) != 0;
}
- void set_bitmap_elt(unsigned int *bits, Block *address, bool flag)
+ Block *next_block_after(Block *block)
{
- std::pair<cell,cell> pair = bitmap_deref(address);
- if(flag)
- bits[pair.first] |= (1 << pair.second);
+ return (Block *)((cell)block + block->size());
+ }
+
+ void set_bitmap_range(u64 *bits, Block *address)
+ {
+ std::pair<cell,cell> start = bitmap_deref(address);
+ std::pair<cell,cell> end = bitmap_deref(next_block_after(address));
+
+ u64 start_mask = ((u64)1 << start.second) - 1;
+ u64 end_mask = ((u64)1 << end.second) - 1;
+
+ if(start.first == end.first)
+ bits[start.first] |= start_mask ^ end_mask;
else
- bits[pair.first] &= ~(1 << pair.second);
+ {
+#ifdef FACTOR_DEBUG
+ assert(start.first < bits_size);
+#endif
+ bits[start.first] |= ~start_mask;
+
+ for(cell index = start.first + 1; index < end.first; index++)
+ bits[index] = (u64)-1;
+
+ if(end_mask != 0)
+ {
+#ifdef FACTOR_DEBUG
+ assert(end.first < bits_size);
+#endif
+ bits[end.first] |= end_mask;
+ }
+ }
}
- bool is_marked_p(Block *address)
+ bool marked_p(Block *address)
{
return bitmap_elt(marked,address);
}
- void set_marked_p(Block *address, bool marked_p)
+ void set_marked_p(Block *address)
+ {
+ set_bitmap_range(marked,address);
+ }
+
+ /* From http://chessprogramming.wikispaces.com/Population+Count */
+ cell popcount(u64 x)
{
- set_bitmap_elt(marked,address,marked_p);
+ u64 k1 = 0x5555555555555555ll;
+ u64 k2 = 0x3333333333333333ll;
+ u64 k4 = 0x0f0f0f0f0f0f0f0fll;
+ u64 kf = 0x0101010101010101ll;
+ x = x - ((x >> 1) & k1); // put count of each 2 bits into those 2 bits
+ x = (x & k2) + ((x >> 2) & k2); // put count of each 4 bits into those 4 bits
+ x = (x + (x >> 4)) & k4 ; // put count of each 8 bits into those 8 bits
+ x = (x * kf) >> 56; // returns 8 most significant bits of x + (x<<8) + (x<<16) + (x<<24) + ...
+
+ return (cell)x;
}
- bool is_free_p(Block *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()
{
- return bitmap_elt(freed,address);
+ cell accum = 0;
+ for(cell index = 0; index < bits_size; index++)
+ {
+ forwarding[index] = accum;
+ accum += popcount(marked[index]);
+ }
}
- void set_free_p(Block *address, bool free_p)
+ /* We have the popcount for every 64 entries; look up and compute the rest */
+ Block *forward_block(Block *original)
+ {
+ std::pair<cell,cell> pair = bitmap_deref(original);
+
+ cell approx_popcount = forwarding[pair.first];
+ u64 mask = ((u64)1 << pair.second) - 1;
+
+ cell new_line_number = approx_popcount + popcount(marked[pair.first] & mask);
+ return line_block(new_line_number);
+ }
+};
+
+template<typename Block, typename Iterator> struct heap_compactor {
+ mark_bits<Block> *state;
+ char *address;
+ Iterator &iter;
+
+ explicit heap_compactor(mark_bits<Block> *state_, Block *address_, Iterator &iter_) :
+ state(state_), address((char *)address_), iter(iter_) {}
+
+ void operator()(Block *block, cell size)
{
- set_bitmap_elt(freed,address,free_p);
+ if(this->state->marked_p(block))
+ {
+ memmove(address,block,size);
+ iter((Block *)address,size);
+ address += size;
+ }
}
};
/* C++ headers */
#include <algorithm>
+#include <map>
#include <set>
#include <vector>
-
-#if __GNUC__ == 4
- #include <tr1/unordered_map>
-
- namespace factor
- {
- using std::tr1::unordered_map;
- }
-#elif __GNUC__ == 3
- #include <boost/unordered_map.hpp>
-
- namespace factor
- {
- using boost::unordered_map;
- }
-#else
- #error Factor requires GCC 3.x or later
-#endif
+#include <iostream>
/* Forward-declare this since it comes up in function prototypes */
namespace factor
#include "bignumint.hpp"
#include "bignum.hpp"
#include "code_block.hpp"
-#include "zone.hpp"
+#include "bump_allocator.hpp"
+#include "mark_bits.hpp"
+#include "free_list_allocator.hpp"
#include "write_barrier.hpp"
-#include "old_space.hpp"
+#include "object_start_map.hpp"
+#include "nursery_space.hpp"
#include "aging_space.hpp"
#include "tenured_space.hpp"
#include "data_heap.hpp"
#include "words.hpp"
#include "float_bits.hpp"
#include "io.hpp"
-#include "mark_bits.hpp"
-#include "heap.hpp"
#include "image.hpp"
#include "alien.hpp"
#include "code_heap.hpp"
collector.cheneys_algorithm();
update_code_heap_for_minor_gc(&code->points_to_nursery);
- nursery.here = nursery.start;
+ data->reset_generation(&nursery);
code->points_to_nursery.clear();
}
nursery_policy(factor_vm *parent_) : parent(parent_) {}
- bool should_copy_p(object *untagged)
+ bool should_copy_p(object *obj)
{
- return parent->nursery.contains_p(untagged);
+ return parent->nursery.contains_p(obj);
}
+
+ void promoted_object(object *obj) {}
+
+ void visited_object(object *obj) {}
};
struct nursery_collector : copying_collector<aging_space,nursery_policy> {
--- /dev/null
+namespace factor
+{
+
+struct nursery_space : bump_allocator<object>
+{
+ nursery_space(cell size, cell start) : bump_allocator<object>(size,start) {}
+};
+
+}
--- /dev/null
+#include "master.hpp"
+
+namespace factor
+{
+
+object_start_map::object_start_map(cell size_, cell start_) :
+ size(size_), start(start_)
+{
+ object_start_offsets = new card[addr_to_card(size_)];
+ object_start_offsets_end = object_start_offsets + addr_to_card(size_);
+}
+
+object_start_map::~object_start_map()
+{
+ delete[] object_start_offsets;
+}
+
+cell object_start_map::first_object_in_card(cell card_index)
+{
+ return object_start_offsets[card_index];
+}
+
+cell object_start_map::find_object_containing_card(cell card_index)
+{
+ if(card_index == 0)
+ return start;
+ else
+ {
+ card_index--;
+
+ while(first_object_in_card(card_index) == card_starts_inside_object)
+ {
+#ifdef FACTOR_DEBUG
+ /* First card should start with an object */
+ assert(card_index > 0);
+#endif
+ card_index--;
+ }
+
+ return start + (card_index << card_bits) + first_object_in_card(card_index);
+ }
+}
+
+/* we need to remember the first object allocated in the card */
+void object_start_map::record_object_start_offset(object *obj)
+{
+ cell idx = addr_to_card((cell)obj - start);
+ card obj_start = ((cell)obj & addr_card_mask);
+ object_start_offsets[idx] = std::min(object_start_offsets[idx],obj_start);
+}
+
+void object_start_map::clear_object_start_offsets()
+{
+ memset(object_start_offsets,card_starts_inside_object,addr_to_card(size));
+}
+
+}
--- /dev/null
+namespace factor
+{
+
+static const cell card_starts_inside_object = 0xff;
+
+struct object_start_map {
+ cell size, start;
+ card *object_start_offsets;
+ card *object_start_offsets_end;
+
+ object_start_map(cell size_, cell start_);
+ ~object_start_map();
+
+ cell first_object_in_card(cell card_index);
+ cell find_object_containing_card(cell card_index);
+ void record_object_start_offset(object *obj);
+ void clear_object_start_offsets();
+};
+
+}
+++ /dev/null
-#include "master.hpp"
-
-namespace factor
-{
-
-old_space::old_space(cell size_, cell start_) : zone(size_,start_)
-{
- object_start_offsets = new card[addr_to_card(size_)];
- object_start_offsets_end = object_start_offsets + addr_to_card(size_);
-}
-
-old_space::~old_space()
-{
- delete[] object_start_offsets;
-}
-
-cell old_space::first_object_in_card(cell card_index)
-{
- return object_start_offsets[card_index];
-}
-
-cell old_space::find_object_containing_card(cell card_index)
-{
- if(card_index == 0)
- return start;
- else
- {
- card_index--;
-
- while(first_object_in_card(card_index) == card_starts_inside_object)
- {
-#ifdef FACTOR_DEBUG
- /* First card should start with an object */
- assert(card_index > 0);
-#endif
- card_index--;
- }
-
- return start + (card_index << card_bits) + first_object_in_card(card_index);
- }
-}
-
-/* we need to remember the first object allocated in the card */
-void old_space::record_object_start_offset(object *obj)
-{
- cell idx = addr_to_card((cell)obj - start);
- if(object_start_offsets[idx] == card_starts_inside_object)
- object_start_offsets[idx] = ((cell)obj & addr_card_mask);
-}
-
-object *old_space::allot(cell size)
-{
- if(here + size > end) return NULL;
-
- object *obj = zone::allot(size);
- record_object_start_offset(obj);
- return obj;
-}
-
-void old_space::clear_object_start_offsets()
-{
- memset(object_start_offsets,card_starts_inside_object,addr_to_card(size));
-}
-
-cell old_space::next_object_after(factor_vm *parent, cell scan)
-{
- cell size = parent->untagged_object_size((object *)scan);
- if(scan + size < here)
- return scan + size;
- else
- return 0;
-}
-
-}
+++ /dev/null
-namespace factor
-{
-
-static const cell card_starts_inside_object = 0xff;
-
-struct old_space : zone {
- card *object_start_offsets;
- card *object_start_offsets_end;
-
- old_space(cell size_, cell start_);
- ~old_space();
-
- cell first_object_in_card(cell card_index);
- cell find_object_containing_card(cell card_index);
- void record_object_start_offset(object *obj);
- object *allot(cell size);
- void clear_object_start_offsets();
- cell next_object_after(factor_vm *parent, cell scan);
-};
-
-}
#define OPEN_READ(path) _wfopen(path,L"rb")
#define OPEN_WRITE(path) _wfopen(path,L"wb")
-#define print_native_string(string) wprintf(L"%s",string)
-
/* Difference between Jan 1 00:00:00 1601 and Jan 1 00:00:00 1970 */
#define EPOCH_OFFSET 0x019db1ded53e8000LL
{
gc_root<word> word(word_,this);
- jit jit(WORD_TYPE,word.value(),this);
+ jit jit(code_block_profiling,word.value(),this);
jit.emit_with(userenv[JIT_PROFILING],word.value());
return jit.to_code_block();
switch(tagged<object>(obj).type())
{
case WORD_TYPE:
- if(!parent->to_boolean(parent->untag<word>(obj)->subprimitive))
+ if(!parent->to_boolean(untag<word>(obj)->subprimitive))
return true;
break;
case QUOTATION_TYPE:
{
gc_root<quotation> quot(quot_,parent);
- array *elements = parent->untag<array>(quot->array);
+ array *elements = untag<array>(quot->array);
/* If the quotation consists of a single word, compile a direct call
to the word. */
void factor_vm::set_quot_xt(quotation *quot, code_block *code)
{
- assert(code->type() == QUOTATION_TYPE);
quot->code = code;
quot->xt = code->xt();
}
{
gc_root<word> word(array_nth(words.untagged(),i),this);
- if(!word->code || !word_optimized_p(word.untagged()))
+ if(!word->code || !word->code->optimized_p())
jit_compile_word(word.value(),word->def,false);
update_word_xt(word.value());
bool compiling, relocate;
explicit quotation_jit(cell quot, bool compiling_, bool relocate_, factor_vm *vm)
- : jit(QUOTATION_TYPE,quot,vm),
+ : jit(code_block_unoptimized,quot,vm),
elements(owner.as<quotation>().untagged()->array,vm),
compiling(compiling_),
relocate(relocate_){};
namespace factor
{
-cell factor_vm::string_nth(string* str, cell index)
+cell string::nth(cell index) const
{
/* If high bit is set, the most significant 16 bits of the char
come from the aux vector. The least significant bit of the
corresponding aux vector entry is negated, so that we can
XOR the two components together and get the original code point
back. */
- cell lo_bits = str->data()[index];
+ cell lo_bits = data()[index];
if((lo_bits & 0x80) == 0)
return lo_bits;
else
{
- byte_array *aux = untag<byte_array>(str->aux);
+ byte_array *aux = untag<byte_array>(this->aux);
cell hi_bits = aux->data<u16>()[index];
return (hi_bits << 7) ^ lo_bits;
}
if the most significant bit of a
character is set. Initially all of
the bits are clear. */
- aux = allot_array_internal<byte_array>(untag_fixnum(str->length) * sizeof(u16));
+ aux = allot_uninitialized_array<byte_array>(untag_fixnum(str->length) * sizeof(u16));
str->aux = tag<byte_array>(aux);
write_barrier(&str->aux);
{
string *str = untag<string>(dpop());
cell index = untag_fixnum(dpop());
- dpush(tag_fixnum(string_nth(str,index)));
+ dpush(tag_fixnum(str->nth(index)));
}
void factor_vm::primitive_set_string_nth_fast()
namespace factor
{
-inline static cell string_capacity(string *str)
+inline static cell string_capacity(const string *str)
{
return untag_fixnum(str->length);
}
return tag;
}
- bool type_p(cell type_) const { return type() == type_; }
+ bool type_p(cell type_) const
+ {
+ return type() == type_;
+ }
+
+ bool type_p() const
+ {
+ if(Type::type_number == TYPE_COUNT)
+ return true;
+ else
+ return type_p(Type::type_number);
+ }
Type *untag_check(factor_vm *parent) const {
- if(Type::type_number != TYPE_COUNT && !type_p(Type::type_number))
+ if(!type_p())
parent->type_error(Type::type_number,value_);
return untagged();
}
explicit tagged(cell tagged) : value_(tagged) {
#ifdef FACTOR_DEBUG
- untag_check(tls_vm());
+ assert(type_p());
#endif
}
explicit tagged(Type *untagged) : value_(factor::tag(untagged)) {
#ifdef FACTOR_DEBUG
- untag_check(tls_vm());
+ assert(type_p());
#endif
}
return tagged<Type>(value).untag_check(this);
}
-template<typename Type> Type *factor_vm::untag(cell value)
+template<typename Type> Type *untag(cell value)
{
return tagged<Type>(value).untagged();
}
namespace factor
{
-struct tenured_space : old_space {
- tenured_space(cell size, cell start) : old_space(size,start) {}
+struct tenured_space : free_list_allocator<object> {
+ object_start_map starts;
+ std::vector<object *> mark_stack;
+
+ tenured_space(cell size, cell start) :
+ free_list_allocator<object>(size,start), starts(size,start) {}
+
+ object *allot(cell size)
+ {
+ object *obj = free_list_allocator<object>::allot(size);
+ if(obj)
+ {
+ starts.record_object_start_offset(obj);
+ return obj;
+ }
+ else
+ return NULL;
+ }
+
+ object *first_allocated_block_after(object *block)
+ {
+ while(block != this->last_block() && block->free_p())
+ {
+ free_heap_block *free_block = (free_heap_block *)block;
+ block = (object *)((cell)free_block + free_block->size());
+ }
+
+ if(block == this->last_block())
+ return NULL;
+ else
+ return block;
+ }
+
+ cell first_object()
+ {
+ return (cell)first_allocated_block_after(this->first_block());
+ }
+
+ cell next_object_after(cell scan)
+ {
+ cell size = ((object *)scan)->size();
+ object *next = (object *)(scan + size);
+ return (cell)first_allocated_block_after(next);
+ }
+
+ void clear_mark_bits()
+ {
+ state.clear_mark_bits();
+ }
+
+ void clear_mark_stack()
+ {
+ mark_stack.clear();
+ }
+
+ bool marked_p(object *obj)
+ {
+ return this->state.marked_p(obj);
+ }
+
+ void mark_and_push(object *obj)
+ {
+ this->state.set_marked_p(obj);
+ this->mark_stack.push_back(obj);
+ }
};
}
{
to_tenured_collector::to_tenured_collector(factor_vm *myvm_) :
- copying_collector<tenured_space,to_tenured_policy>(
+ collector<tenured_space,to_tenured_policy>(
myvm_,
&myvm_->gc_stats.aging_stats,
myvm_->data->tenured,
to_tenured_policy(myvm_)) {}
+void to_tenured_collector::tenure_reachable_objects()
+{
+ std::vector<object *> *mark_stack = &this->target->mark_stack;
+ while(!mark_stack->empty())
+ {
+ object *obj = mark_stack->back();
+ mark_stack->pop_back();
+ this->trace_slots(obj);
+ }
+}
+
void factor_vm::collect_to_tenured()
{
/* Copy live objects from aging space to tenured space. */
to_tenured_collector collector(this);
+ data->tenured->clear_mark_stack();
+
collector.trace_roots();
collector.trace_contexts();
collector.trace_cards(data->tenured,
card_points_to_aging,
- dummy_unmarker());
+ simple_unmarker(card_mark_mask));
collector.trace_code_heap_roots(&code->points_to_aging);
- collector.cheneys_algorithm();
+ collector.tenure_reachable_objects();
update_code_heap_for_minor_gc(&code->points_to_aging);
- nursery.here = nursery.start;
- reset_generation(data->aging);
- code->points_to_nursery.clear();
- code->points_to_aging.clear();
+ data->reset_generation(&nursery);
+ data->reset_generation(data->aging);
+ code->clear_remembered_set();
}
}
struct to_tenured_policy {
factor_vm *myvm;
- zone *tenured;
+ tenured_space *tenured;
to_tenured_policy(factor_vm *myvm_) : myvm(myvm_), tenured(myvm->data->tenured) {}
{
return !tenured->contains_p(untagged);
}
+
+ void promoted_object(object *obj)
+ {
+ tenured->mark_stack.push_back(obj);
+ }
+
+ void visited_object(object *obj) {}
};
-struct to_tenured_collector : copying_collector<tenured_space,to_tenured_policy> {
+struct to_tenured_collector : collector<tenured_space,to_tenured_policy> {
to_tenured_collector(factor_vm *myvm_);
+ void tenure_reachable_objects();
};
}
return ptr;
}
-/* We don't use printf directly, because format directives are not portable.
-Instead we define the common cases here. */
-void nl()
-{
- fputs("\n",stdout);
-}
-
-void print_string(const char *str)
-{
- fputs(str,stdout);
-}
-
-void print_cell(cell x)
-{
- printf(CELL_FORMAT,x);
-}
-
-void print_cell_hex(cell x)
-{
- printf(CELL_HEX_FORMAT,x);
-}
-
-void print_cell_hex_pad(cell x)
-{
- printf(CELL_HEX_PAD_FORMAT,x);
-}
-
-void print_fixnum(fixnum x)
-{
- printf(FIXNUM_FORMAT,x);
-}
-
cell read_cell_hex()
{
cell cell;
namespace factor
{
vm_char *safe_strdup(const vm_char *str);
- void print_string(const char *str);
- void nl();
- void print_cell(cell x);
- void print_cell_hex(cell x);
void print_cell_hex_pad(cell x);
- void print_fixnum(fixnum x);
cell read_cell_hex();
}
factor_vm::factor_vm() :\r
nursery(0,0),\r
profiling_p(false),\r
- secure_gc(false),\r
gc_off(false),\r
current_gc(NULL),\r
fep_disabled(false),\r
context *ctx;
/* New objects are allocated here */
- zone nursery;
+ nursery_space nursery;
/* Add this to a shifted address to compute write barrier offsets */
cell cards_offset;
unsigned int signal_fpu_status;
stack_frame *signal_callstack_top;
- /* Zeroes out deallocated memory; set by the -securegc command line argument */
- bool secure_gc;
-
/* A heap walk allows useful things to be done, like finding all
references to an object for debugging purposes. */
cell heap_scan_ptr;
/* GC is off during heap walking */
bool gc_off;
+ /* GC logging */
+ bool verbosegc;
+
/* Data heap */
data_heap *data;
//data heap
void init_card_decks();
- void clear_cards(old_space *gen);
- void clear_decks(old_space *gen);
- void reset_generation(old_space *gen);
void set_data_heap(data_heap *data_);
- void init_data_heap(cell young_size, cell aging_size, cell tenured_size, bool secure_gc_);
- cell untagged_object_size(object *pointer);
- cell unaligned_object_size(object *pointer);
+ void init_data_heap(cell young_size, cell aging_size, cell tenured_size);
void primitive_size();
cell binary_payload_start(object *pointer);
void primitive_data_room();
#endif
}
- inline void check_tagged_pointer(cell tagged)
- {
- #ifdef FACTOR_DEBUG
- if(!immediate_p(tagged))
- {
- object *obj = untag<object>(tagged);
- check_data_pointer(obj);
- obj->h.hi_tag();
- }
- #endif
- }
-
// generic arrays
- template<typename Array> Array *allot_array_internal(cell capacity);
+ template<typename Array> Array *allot_uninitialized_array(cell capacity);
template<typename Array> bool reallot_array_in_place_p(Array *array, cell capacity);
template<typename Array> Array *reallot_array(Array *array_, cell capacity);
void print_callstack();
void dump_cell(cell x);
void dump_memory(cell from, cell to);
- void dump_zone(const char *name, zone *z);
+ template<typename Generation> void dump_generation(const char *name, Generation *gen);
void dump_generations();
void dump_objects(cell type);
void find_data_references_step(cell *scan);
inline void set_array_nth(array *array, cell slot, cell value);
//strings
- cell string_nth(string* str, cell index);
+ cell string_nth(const string *str, cell index);
void set_string_nth_fast(string *str, cell index, cell ch);
void set_string_nth_slow(string *str_, cell index, cell ch);
void set_string_nth(string *str, cell index, cell ch);
inline double untag_float_check(cell tagged);
inline fixnum float_to_fixnum(cell tagged);
inline double fixnum_to_float(cell tagged);
+
+ // tagged
template<typename Type> Type *untag_check(cell value);
- template<typename Type> Type *untag(cell value);
//io
void init_c_io();
void update_literal_references(code_block *compiled);
void relocate_code_block_step(relocation_entry rel, cell index, code_block *compiled);
void update_word_references(code_block *compiled);
- void update_code_block_for_full_gc(code_block *compiled);
+ void update_code_block_words_and_literals(code_block *compiled);
void check_code_address(cell address);
void relocate_code_block(code_block *compiled);
void fixup_labels(array *labels, code_block *compiled);
- code_block *allot_code_block(cell size, cell type);
- code_block *add_code_block(cell type, cell code_, cell labels_, cell owner_, cell relocation_, cell literals_);
+ code_block *allot_code_block(cell size, code_block_type type);
+ code_block *add_code_block(code_block_type type, cell code_, cell labels_, cell owner_, cell relocation_, cell literals_);
//code heap
inline void check_code_pointer(cell ptr)
bool in_code_heap_p(cell ptr);
void jit_compile_word(cell word_, cell def_, bool relocate);
void update_code_heap_words();
+ void update_code_heap_words_and_literals();
+ void relocate_code_heap();
void primitive_modify_code_heap();
void primitive_code_room();
void forward_object_xts();
void primitive_strip_stack_traces();
/* Apply a function to every code block */
- template<typename Iterator> void iterate_code_heap(Iterator &iter)
- {
- heap_block *scan = code->first_block();
-
- while(scan)
+ template<typename Iterator> struct code_heap_iterator {
+ Iterator &iter;
+ explicit code_heap_iterator(Iterator &iter_) : iter(iter_) {}
+ void operator()(heap_block *block, cell size)
{
- if(scan->type() != FREE_BLOCK_TYPE)
- iter((code_block *)scan);
- scan = code->next_block(scan);
+ iter((code_block *)block,size);
}
+ };
+
+ template<typename Iterator> void iterate_code_heap(Iterator &iter_)
+ {
+ code_heap_iterator<Iterator> iter(iter_);
+ code->allocator->iterate(iter);
}
//callbacks
void primitive_callstack();
void primitive_set_callstack();
code_block *frame_code(stack_frame *frame);
- cell frame_type(stack_frame *frame);
+ code_block_type frame_type(stack_frame *frame);
cell frame_executing(stack_frame *frame);
stack_frame *frame_successor(stack_frame *frame);
cell frame_scan(stack_frame *frame);
};
-extern unordered_map<THREADHANDLE, factor_vm *> thread_vms;
+extern std::map<THREADHANDLE, factor_vm *> thread_vms;
}
void factor_vm::primitive_optimized_p()
{
- drepl(tag_boolean(word_optimized_p(untag_check<word>(dpeek()))));
+ word *w = untag_check<word>(dpeek());
+ drepl(tag_boolean(w->code->optimized_p()));
}
void factor_vm::primitive_wrapper()
namespace factor
{
-inline bool word_optimized_p(word *word)
-{
- return word->code->type() == WORD_TYPE;
-}
-
}
+++ /dev/null
-namespace factor
-{
-
-struct zone {
- /* offset of 'here' and 'end' is hardcoded in compiler backends */
- cell here;
- cell start;
- cell end;
- cell size;
-
- zone(cell size_, cell start_) : here(0), start(start_), end(start_ + size_), size(size_) {}
-
- inline bool contains_p(object *pointer)
- {
- return ((cell)pointer - start) < size;
- }
-
- inline object *allot(cell size)
- {
- cell h = here;
- here = h + align8(size);
- return (object *)h;
- }
-};
-
-}