vm: simplify card marking logic, and unmark more cards during aging collections by...

diff --git a/vm/aging_collector.cpp b/vm/aging_collector.cpp
index 9b69cd297723c2e889b285d82f567cd397758517..6867ea30833550845d683bf2eea0e87504bf5716 100644 (file)
--- a/vm/aging_collector.cpp
+++ b/vm/aging_collector.cpp
@@ -16,7 +16,9 @@ void factor_vm::collect_aging()
 
        collector.trace_roots();
        collector.trace_contexts();
-       collector.trace_cards(data->tenured);
+       collector.trace_cards(data->tenured,
+               card_points_to_aging,
+               complex_unmarker(card_mark_mask,card_points_to_nursery));
        collector.trace_code_heap_roots(&code->points_to_aging);
        collector.cheneys_algorithm();
        update_dirty_code_blocks(&code->points_to_aging);

diff --git a/vm/code_heap.hpp b/vm/code_heap.hpp
index 589336fad5ad562067dd193550783662242c6edd..f9084d0b43c579458db170687f8220c2a642a994 100755 (executable)
--- a/vm/code_heap.hpp
+++ b/vm/code_heap.hpp
@@ -3,7 +3,7 @@ namespace factor
 
 struct code_heap : heap {
        /* Set of blocks which need full relocation. */
-       unordered_set<code_block *> needs_fixup;
+       std::set<code_block *> needs_fixup;
 
        /* Code blocks which may reference objects in the nursery */
        std::set<code_block *> points_to_nursery;

diff --git a/vm/collector.hpp b/vm/collector.hpp
index bfe113c7062637497d6816b8d555874195371596..2f1c34bd8c34376e2a8bd40b8dd61ed7a12cf4bf 100644 (file)
--- a/vm/collector.hpp
+++ b/vm/collector.hpp
@@ -30,15 +30,15 @@ template<typename TargetGeneration, typename Policy> struct collector {
                return untagged;
        }
 
-       void trace_handle(cell *handle)
+       bool trace_handle(cell *handle)
        {
                cell pointer = *handle;
 
-               if(immediate_p(pointer)) return;
+               if(immediate_p(pointer)) return false;
 
                object *untagged = myvm->untag<object>(pointer);
                if(!policy.should_copy_p(untagged))
-                       return;
+                       return false;
 
                object *forwarding = resolve_forwarding(untagged);
 
@@ -50,18 +50,24 @@ template<typename TargetGeneration, typename Policy> struct collector {
                        untagged = forwarding;
 
                *handle = RETAG(untagged,TAG(pointer));
+
+               return true;
        }
 
-       void trace_slots(object *ptr)
+       bool trace_slots(object *ptr)
        {
                cell *slot = (cell *)ptr;
                cell *end = (cell *)((cell)ptr + myvm->binary_payload_start(ptr));
 
+               bool copied = false;
+
                if(slot != end)
                {
                        slot++;
-                       for(; slot < end; slot++) trace_handle(slot);
+                       for(; slot < end; slot++) copied |= trace_handle(slot);
                }
+
+               return copied;
        }
 
        object *promote_object(object *untagged)

diff --git a/vm/copying_collector.hpp b/vm/copying_collector.hpp
index 9e1675366042b30a1afb6a724f72cc1e6edcf395..b8b63c4bcc31c78f0b80ac36a9cf2983208431bd 100644 (file)
--- a/vm/copying_collector.hpp
+++ b/vm/copying_collector.hpp
@@ -1,6 +1,26 @@
 namespace factor
 {
 
+struct dummy_unmarker {
+       void operator()(bool result, card *ptr) {}
+};
+
+struct simple_unmarker {
+       card unmask;
+       simple_unmarker(card unmask_) : unmask(unmask_) {}
+       void operator()(bool result, card *ptr) { *ptr &= ~unmask; }
+};
+
+struct complex_unmarker {
+       card unmask_none, unmask_some;
+       complex_unmarker(card unmask_none_, card unmask_some_) :
+               unmask_none(unmask_none_), unmask_some(unmask_some_) {}
+
+       void operator()(bool result, card *ptr) {
+               *ptr &= (result ? ~unmask_some : ~unmask_none);
+       }
+};
+
 template<typename TargetGeneration, typename Policy>
 struct copying_collector : collector<TargetGeneration,Policy> {
        cell scan;
@@ -8,29 +28,37 @@ struct copying_collector : collector<TargetGeneration,Policy> {
        explicit copying_collector(factor_vm *myvm_, TargetGeneration *target_, Policy policy_) :
                collector<TargetGeneration,Policy>(myvm_,target_,policy_), scan(target_->here) {}
 
-       template<typename SourceGeneration> void trace_objects_between(SourceGeneration *gen, cell scan, cell *end)
+       template<typename SourceGeneration>
+       bool trace_objects_between(SourceGeneration *gen, cell scan, cell *end)
        {
+               bool copied = false;
+
                while(scan && scan < *end)
                {
-                       this->trace_slots((object *)scan);
+                       copied |= this->trace_slots((object *)scan);
                        scan = gen->next_object_after(this->myvm,scan);
                }
+
+               return copied;
        }
 
-       template<typename SourceGeneration> void trace_card(SourceGeneration *gen, card *ptr, card unmask)
+       template<typename SourceGeneration, typename Unmarker>
+       bool trace_card(SourceGeneration *gen, card *ptr, Unmarker unmarker)
        {
                cell card_start = this->myvm->card_to_addr(ptr);
                cell card_scan = card_start + gen->card_offset(card_start);
                cell card_end = this->myvm->card_to_addr(ptr + 1);
 
-               trace_objects_between(gen,card_scan,&card_end);
-
-               *ptr &= ~unmask;
+               bool result = this->trace_objects_between(gen,card_scan,&card_end);
+               unmarker(result,ptr);
 
                this->myvm->gc_stats.cards_scanned++;
+
+               return result;
        }
 
-       template<typename SourceGeneration> void trace_card_deck(SourceGeneration *gen, card_deck *deck, card mask, card unmask)
+       template<typename SourceGeneration, typename Unmarker>
+       bool trace_card_deck(SourceGeneration *gen, card_deck *deck, card mask, Unmarker unmarker)
        {
                card *first_card = this->myvm->deck_to_card(deck);
                card *last_card = this->myvm->deck_to_card(deck + 1);
@@ -38,84 +66,38 @@ struct copying_collector : collector<TargetGeneration,Policy> {
                u32 *quad_ptr;
                u32 quad_mask = mask | (mask << 8) | (mask << 16) | (mask << 24);
 
+               bool copied = false;
+
                for(quad_ptr = (u32 *)first_card; quad_ptr < (u32 *)last_card; quad_ptr++)
                {
                        if(*quad_ptr & quad_mask)
                        {
                                card *ptr = (card *)quad_ptr;
 
-                               if(ptr[0] & mask) trace_card(gen,&ptr[0],unmask);
-                               if(ptr[1] & mask) trace_card(gen,&ptr[1],unmask);
-                               if(ptr[2] & mask) trace_card(gen,&ptr[2],unmask);
-                               if(ptr[3] & mask) trace_card(gen,&ptr[3],unmask);
+                               if(ptr[0] & mask) copied |= trace_card(gen,&ptr[0],unmarker);
+                               if(ptr[1] & mask) copied |= trace_card(gen,&ptr[1],unmarker);
+                               if(ptr[2] & mask) copied |= trace_card(gen,&ptr[2],unmarker);
+                               if(ptr[3] & mask) copied |= trace_card(gen,&ptr[3],unmarker);
                        }
                }
 
                this->myvm->gc_stats.decks_scanned++;
+
+               return copied;
        }
 
-       template<typename SourceGeneration> void trace_cards(SourceGeneration *gen)
+       template<typename SourceGeneration, typename Unmarker>
+       void trace_cards(SourceGeneration *gen, cell mask, Unmarker unmarker)
        {
                u64 start = current_micros();
 
                card_deck *first_deck = this->myvm->addr_to_deck(gen->start);
                card_deck *last_deck = this->myvm->addr_to_deck(gen->end);
 
-               card mask, unmask;
-
-               /* if we are collecting the nursery, we care about old->nursery pointers
-               but not old->aging pointers */
-               if(this->current_gc->collecting_nursery_p())
-               {
-                       mask = card_points_to_nursery;
-
-                       /* after the collection, no old->nursery pointers remain
-                       anywhere, but old->aging pointers might remain in tenured
-                       space */
-                       if(gen->is_tenured_p())
-                               unmask = card_points_to_nursery;
-                       /* after the collection, all cards in aging space can be
-                       cleared */
-                       else if(gen->is_aging_p())
-                               unmask = card_mark_mask;
-                       else
-                       {
-                               critical_error("bug in trace_gen_cards",0);
-                               return;
-                       }
-               }
-               /* if we are collecting aging space into tenured space, we care about
-               all old->nursery and old->aging pointers. no old->aging pointers can
-               remain */
-               else if(this->current_gc->collecting_aging_p())
-               {
-                       if(this->current_gc->collecting_aging_again)
-                       {
-                               mask = card_points_to_aging;
-                               unmask = card_mark_mask;
-                       }
-                       /* after we collect aging space into the aging semispace, no
-                       old->nursery pointers remain but tenured space might still have
-                       pointers to aging space. */
-                       else
-                       {
-                               mask = card_points_to_aging;
-                               unmask = card_points_to_nursery;
-                       }
-               }
-               else
-               {
-                       critical_error("bug in trace_gen_cards",0);
-                       return;
-               }
-
                for(card_deck *ptr = first_deck; ptr < last_deck; ptr++)
                {
                        if(*ptr & mask)
-                       {
-                               trace_card_deck(gen,ptr,mask,unmask);
-                               *ptr &= ~unmask;
-                       }
+                               unmarker(trace_card_deck(gen,ptr,mask,unmarker),ptr);
                }
 
                this->myvm->gc_stats.card_scan_time += (current_micros() - start);

diff --git a/vm/master.hpp b/vm/master.hpp
index fbafaf2d7bc09e9036d73d05dd3638649c7822b3..2058af8c43ab2e915e16033f39b5029c1e949da3 100755 (executable)
--- a/vm/master.hpp
+++ b/vm/master.hpp
@@ -30,21 +30,17 @@
 
 #if __GNUC__ == 4
         #include <tr1/unordered_map>
-        #include <tr1/unordered_set>
 
        namespace factor
        {
                using std::tr1::unordered_map;
-               using std::tr1::unordered_set;
        }
 #elif __GNUC__ == 3
         #include <boost/unordered_map.hpp>
-        #include <boost/unordered_set.hpp>
 
        namespace factor
        {
                using boost::unordered_map;
-               using boost::unordered_set;
        }
 #else
         #error Factor requires GCC 3.x or later

diff --git a/vm/nursery_collector.cpp b/vm/nursery_collector.cpp
index cff753e68774d87ed0876b15a914238932a20b5a..de5eab45933b013b2ff22566d593c9c58f1aaa50 100644 (file)
--- a/vm/nursery_collector.cpp
+++ b/vm/nursery_collector.cpp
@@ -13,8 +13,12 @@ void factor_vm::collect_nursery()
 
        collector.trace_roots();
        collector.trace_contexts();
-       collector.trace_cards(data->tenured);
-       collector.trace_cards(data->aging);
+       collector.trace_cards(data->tenured,
+               card_points_to_nursery,
+               simple_unmarker(card_points_to_nursery));
+       collector.trace_cards(data->aging,
+               card_points_to_nursery,
+               simple_unmarker(card_mark_mask));
        collector.trace_code_heap_roots(&code->points_to_nursery);
        collector.cheneys_algorithm();
        update_dirty_code_blocks(&code->points_to_nursery);

diff --git a/vm/to_tenured_collector.cpp b/vm/to_tenured_collector.cpp
index 1242acd897f3e0b8267caeebad33f8c5d95a147f..881b45fbc4624c37b27fd3b61dc8c8a26cdcbb89 100644 (file)
--- a/vm/to_tenured_collector.cpp
+++ b/vm/to_tenured_collector.cpp
@@ -13,7 +13,9 @@ void factor_vm::collect_to_tenured()
 
        collector.trace_roots();
        collector.trace_contexts();
-       collector.trace_cards(data->tenured);
+       collector.trace_cards(data->tenured,
+               card_points_to_aging,
+               dummy_unmarker());
        collector.trace_code_heap_roots(&code->points_to_aging);
        collector.cheneys_algorithm();
        update_dirty_code_blocks(&code->points_to_aging);