/* No need for write barrier here. Either the object is in
the nursery, or it was allocated directly in tenured space
and the write barrier is already hit for us in that case. */
- cell i;
- for(i = 0; i < capacity; i++)
+ for(cell i = 0; i < capacity; i++)
new_array->data()[i] = fill.value();
}
return new_array.untagged();
assert(array->h.hi_tag() == ARRAY_TYPE);
check_tagged_pointer(value);
#endif
- array->data()[slot] = value;
- write_barrier(array);
+ cell *slot_ptr = &array->data()[slot];
+ *slot_ptr = value;
+ write_barrier(slot_ptr);
}
struct growable_array {
explicit copying_collector(factor_vm *myvm_, TargetGeneration *target_, Policy policy_) :
collector<TargetGeneration,Policy>(myvm_,target_,policy_), scan(target_->here) {}
- template<typename SourceGeneration>
- bool trace_objects_between(SourceGeneration *gen, cell scan, cell *end)
+ inline cell first_card_in_deck(cell deck)
{
- bool copied = false;
-
- while(scan && scan < *end)
- {
- copied |= this->trace_slots((object *)scan);
- scan = gen->next_object_after(this->myvm,scan);
- }
+ return deck << (deck_bits - card_bits);
+ }
- return copied;
+ inline cell last_card_in_deck(cell deck)
+ {
+ return first_card_in_deck(deck + 1);
}
- inline cell card_index(cell deck)
+ inline cell card_to_addr(cell c)
{
- return deck << (deck_bits - card_bits);
+ return c << card_bits + this->data->start;
}
- inline cell card_deck_index(cell a)
+ inline cell card_deck_for_address(cell a)
{
- return (a - this->data->start) >> deck_bits;
+ return addr_to_deck(a - this->data->start);
}
inline cell card_start_address(cell card)
return (card << card_bits) + this->data->start;
}
- template<typename SourceGeneration, typename Unmarker>
- bool trace_card(SourceGeneration *gen, card *cards, cell card_index, Unmarker unmarker)
+ inline cell card_end_address(cell card)
{
- cell card_start = card_start_address(card_index);
- cell card_scan = card_start + gen->first_object_in_card(card_start);
- cell card_end = card_start_address(card_index + 1);
-
- bool result = this->trace_objects_between(gen,card_scan,&card_end);
- unmarker(result,&cards[card_index]);
-
- this->myvm->gc_stats.cards_scanned++;
-
- return result;
+ return ((card + 1) << card_bits) + this->data->start;
}
- template<typename SourceGeneration, typename Unmarker>
- bool trace_card_deck(SourceGeneration *gen, cell deck_index, card mask, Unmarker unmarker)
+ bool trace_partial_objects(cell start, cell end, cell card_start, cell card_end)
{
- cell first_card = card_index(deck_index);
- cell last_card = card_index(deck_index + 1);
-
bool copied = false;
- card *cards = this->data->cards;
- for(cell i = first_card; i < last_card; i++)
+ if(card_start < end)
{
- if(cards[i] & mask) copied |= trace_card(gen,cards,i,unmarker);
- }
+ start += sizeof(cell);
+
+ if(start < card_start) start = card_start;
+ if(end > card_end) end = card_end;
- this->myvm->gc_stats.decks_scanned++;
+ cell *slot_ptr = (cell *)start;
+ cell *end_ptr = (cell *)end;
+
+ if(slot_ptr != end_ptr)
+ {
+ for(; slot_ptr < end_ptr; slot_ptr++)
+ copied |= this->trace_handle(slot_ptr);
+ }
+ }
return copied;
}
template<typename SourceGeneration, typename Unmarker>
void trace_cards(SourceGeneration *gen, card mask, Unmarker unmarker)
{
- u64 start = current_micros();
-
- cell first_deck = card_deck_index(gen->start);
- cell last_deck = card_deck_index(gen->end);
-
+ u64 start_time = current_micros();
+
card_deck *decks = this->data->decks;
- for(cell i = first_deck; i < last_deck; i++)
+ 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[i] & mask)
- unmarker(trace_card_deck(gen,i,mask,unmarker),&decks[i]);
+ if(decks[deck_index] & mask)
+ {
+ cell first_card = first_card_in_deck(deck_index);
+ cell last_card = last_card_in_deck(deck_index);
+
+ bool deck_dirty = false;
+
+ for(cell card_index = first_card; card_index < last_card; card_index++)
+ {
+ if(cards[card_index] & mask)
+ {
+ if(card_start_address(card_index) >= end)
+ {
+ start = gen->find_object_containing_card(card_index - gen_start_card);
+ binary_start = start + this->myvm->binary_payload_start((object *)start);
+ end = start + this->myvm->untagged_object_size((object *)start);
+ }
+
+ bool card_dirty = false;
+
+#ifdef FACTOR_DEBUG
+ assert(addr_to_card(start - this->data->start) <= card_index);
+ assert(start < card_end_address(card_index));
+#endif
+
+scan_next_object: {
+ card_dirty |= 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->myvm,start);
+ if(!start) goto end;
+ binary_start = start + this->myvm->binary_payload_start((object *)start);
+ end = start + this->myvm->untagged_object_size((object *)start);
+ goto scan_next_object;
+ }
+ }
+
+ unmarker(card_dirty,&cards[card_index]);
+ this->myvm->gc_stats.cards_scanned++;
+
+ deck_dirty |= card_dirty;
+ }
+ }
+
+ unmarker(deck_dirty,&decks[deck_index]);
+ }
}
- this->myvm->gc_stats.card_scan_time += (current_micros() - start);
+end: this->myvm->gc_stats.card_scan_time += (current_micros() - start_time);
}
/* Trace all literals referenced from a code block. Only for aging and nursery collections */
for(; iter != end; iter++) trace_literal_references(*iter);
}
+ template<typename SourceGeneration>
+ bool trace_objects_between(SourceGeneration *gen, cell scan, cell *end)
+ {
+ bool copied = false;
+
+ while(scan && scan < *end)
+ {
+ copied |= this->trace_slots((object *)scan);
+ scan = gen->next_object_after(this->myvm,scan);
+ }
+
+ return copied;
+ }
+
void cheneys_algorithm()
{
trace_objects_between(this->target,scan,&this->target->here);
void factor_vm::init_card_decks()
{
- cell start = align(data->seg->start,deck_size);
- cards_offset = (cell)data->cards - (start >> card_bits);
- decks_offset = (cell)data->decks - (start >> deck_bits);
+ cards_offset = (cell)data->cards - addr_to_card(data->start);
+ decks_offset = (cell)data->decks - addr_to_deck(data->start);
}
-data_heap::data_heap(factor_vm *myvm, cell young_size_, cell aging_size_, cell tenured_size_)
+data_heap::data_heap(cell young_size_, cell aging_size_, cell tenured_size_)
{
young_size_ = align(young_size_,deck_size);
aging_size_ = align(aging_size_,deck_size);
seg = new segment(total_size);
- cell cards_size = total_size >> card_bits;
+ cell cards_size = addr_to_card(total_size);
cards = new card[cards_size];
cards_end = cards + cards_size;
- cell decks_size = total_size >> deck_bits;
+ cell decks_size = addr_to_deck(total_size);
decks = new card_deck[decks_size];
decks_end = decks + decks_size;
delete[] decks;
}
-data_heap *factor_vm::grow_data_heap(data_heap *data, cell requested_bytes)
+data_heap *data_heap::grow(cell requested_bytes)
{
- cell new_tenured_size = (data->tenured_size * 2) + requested_bytes;
-
- return new data_heap(this,
- data->young_size,
- data->aging_size,
- new_tenured_size);
+ cell new_tenured_size = (tenured_size * 2) + requested_bytes;
+ return new data_heap(young_size,aging_size,new_tenured_size);
}
void factor_vm::clear_cards(old_space *gen)
{
- /* NOTE: reverse order due to heap layout. */
- card *first_card = addr_to_card(gen->start);
- card *last_card = addr_to_card(gen->end);
- memset(first_card,0,last_card - first_card);
+ 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);
}
void factor_vm::clear_decks(old_space *gen)
{
- /* NOTE: reverse order due to heap layout. */
- card_deck *first_deck = addr_to_deck(gen->start);
- card_deck *last_deck = addr_to_deck(gen->end);
- memset(first_deck,0,last_deck - first_deck);
+ 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);
}
/* After garbage collection, any generations which are now empty need to have
void factor_vm::init_data_heap(cell young_size, cell aging_size, cell tenured_size, bool secure_gc_)
{
- set_data_heap(new data_heap(this,young_size,aging_size,tenured_size));
+ set_data_heap(new data_heap(young_size,aging_size,tenured_size));
secure_gc = secure_gc_;
}
card_deck *decks;
card_deck *decks_end;
- explicit data_heap(factor_vm *myvm, cell young_size, cell aging_size, cell tenured_size);
+ explicit data_heap(cell young_size, cell aging_size, cell tenured_size);
~data_heap();
+ data_heap *grow(cell requested_size);
};
static const cell nursery_gen = 0;
if(current_gc->growing_data_heap)
{
old = data;
- set_data_heap(grow_data_heap(data,requested_bytes));
+ set_data_heap(data->grow(requested_bytes));
}
else
{
/* Allows initialization code to store old->new pointers
without hitting the write barrier in the common case of
a nursery allocation */
- write_barrier(obj);
+ char *start = (char *)obj;
+ for(cell offset = 0; offset < size; offset += card_size)
+ write_barrier((cell *)(start + offset));
}
obj->h = header;
cell to_copy = array_capacity(array.untagged());
if(capacity < to_copy)
to_copy = capacity;
-
+
Array *new_array = allot_array_internal<Array>(capacity);
-
+
memcpy(new_array + 1,array.untagged() + 1,to_copy * Array::element_size);
memset((char *)(new_array + 1) + to_copy * Array::element_size,
0,(capacity - to_copy) * Array::element_size);
-
+
return new_array;
}
}
old_space::old_space(cell size_, cell start_) : zone(size_,start_)
{
- cell cards_size = size_ >> card_bits;
- object_start_offsets = new card[cards_size];
- object_start_offsets_end = object_start_offsets + cards_size;
+ 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)
{
- card *ptr = (card *)((((cell)obj - start) >> card_bits) + (cell)object_start_offsets);
- if(*ptr == card_starts_inside_object)
- *ptr = ((cell)obj & addr_card_mask);
+ 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)
void old_space::clear_object_start_offsets()
{
- memset(object_start_offsets,card_starts_inside_object,size >> card_bits);
+ memset(object_start_offsets,card_starts_inside_object,addr_to_card(size));
}
cell old_space::next_object_after(factor_vm *myvm, cell scan)
old_space(cell size_, cell start_);
~old_space();
- cell object_start_map_index(cell address)
- {
- return (address - start) >> card_bits;
- }
-
- /* Find the first object starting on or after the given address */
- cell first_object_in_card(cell address)
- {
- return object_start_offsets[object_start_map_index(address)];
- }
-
- /* Find the card which contains the header of the object which contains
- the given address */
- cell find_card_containing_header(cell address)
- {
- cell i = object_start_map_index(address);
- while(i >= 0 && object_start_offsets[i] == card_starts_inside_object) i--;
- return i;
- }
-
+ cell old_space::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();
object *obj = untag<object>(dpop());
cell value = dpop();
- obj->slots()[slot] = value;
- write_barrier(obj);
+ cell *slot_ptr = &obj->slots()[slot];
+ *slot_ptr = value;
+ write_barrier(slot_ptr);
}
void factor_vm::primitive_load_locals()
the bits are clear. */
aux = allot_array_internal<byte_array>(untag_fixnum(str->length) * sizeof(u16));
- write_barrier(str.untagged());
str->aux = tag<byte_array>(aux);
+ write_barrier(&str->aux);
}
else
aux = untag<byte_array>(str->aux);
{
byte_array *new_aux = allot_byte_array(capacity * sizeof(u16));
- write_barrier(new_str.untagged());
new_str->aux = tag<byte_array>(new_aux);
+ write_barrier(&new_str->aux);
byte_array *aux = untag<byte_array>(str->aux);
memcpy(new_aux->data<u16>(),aux->data<u16>(),to_copy * sizeof(u16));
//data heap
void init_card_decks();
- data_heap *grow_data_heap(data_heap *data, cell requested_bytes);
void clear_cards(old_space *gen);
void clear_decks(old_space *gen);
void reset_generation(old_space *gen);
cell find_all_words();
cell object_size(cell tagged);
- //write barrier
- inline card *addr_to_card(cell a)
- {
- return (card*)(((cell)(a) >> card_bits) + cards_offset);
- }
-
- inline cell card_to_addr(card *c)
- {
- return ((cell)c - cards_offset) << card_bits;
- }
-
- inline card_deck *addr_to_deck(cell a)
- {
- return (card_deck *)(((cell)a >> deck_bits) + decks_offset);
- }
-
- inline cell deck_to_addr(card_deck *c)
- {
- return ((cell)c - decks_offset) << deck_bits;
- }
-
- inline card *deck_to_card(card_deck *d)
- {
- return (card *)((((cell)d - decks_offset) << (deck_bits - card_bits)) + cards_offset);
- }
-
/* the write barrier must be called any time we are potentially storing a
pointer from an older generation to a younger one */
- inline void write_barrier(object *obj)
+ inline void write_barrier(cell *slot_ptr)
{
- *addr_to_card((cell)obj) = card_mark_mask;
- *addr_to_deck((cell)obj) = card_mark_mask;
+ data->cards[addr_to_card((cell)slot_ptr - data->start)] = card_mark_mask;
+ data->decks[addr_to_deck((cell)slot_ptr - data->start)] = card_mark_mask;
}
// gc
static const cell deck_size = (1<<deck_bits);
static const cell addr_deck_mask = (deck_size-1);
+inline cell addr_to_card(cell a)
+{
+ return a >> card_bits;
+}
+
+inline cell addr_to_deck(cell a)
+{
+ return a >> deck_bits;
+}
}