Basic implementation of incremental marking.

src/mark-compact.cc

 // Copyright 2006-2008 the V8 project authors. All rights reserved.
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 //       notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
 //       copyright notice, this list of conditions and the following
 //       disclaimer in the documentation and/or other materials provided
@@ skipping 72 matching lines @@
 
 
 void Marking::TearDown() {
   if (new_space_bitmap_ != NULL) {
     BitmapStorageDescriptor::Free(new_space_bitmap_);
     new_space_bitmap_ = NULL;
   }
 }
 
 
+#ifdef DEBUG
+class VerifyMarkingVisitor: public ObjectVisitor {
+ public:
+  void VisitPointers(Object** start, Object** end) {
+    for (Object** current = start; current < end; current++) {
+      if ((*current)->IsHeapObject()) {
+        HeapObject* object = HeapObject::cast(*current);
+        ASSERT(Marking::IsMarked(object));
+      }
+    }
+  }
+};
+

[Erik Corry, 2011/02/22 12:27:19]

2 blank lines here and several places.

[Vyacheslav Egorov (Chromium), 2011/02/23 14:31:46]

Done.

+static void VerifyMarking(Address bottom, Address top) {
+  VerifyMarkingVisitor visitor;
+  HeapObject* object;
+
+  for (Address current = bottom;
+       current < top;
+       current += object->Size()) {
+    object = HeapObject::FromAddress(current);
+    if (Marking::IsMarked(object)) object->Iterate(&visitor);
+  }
+
+}
+
+static void VerifyMarking(Page* p) {
+  VerifyMarking(p->ObjectAreaStart(), p->AllocationTop());
+}
+
+static void VerifyMarking(NewSpace* space) {
+  VerifyMarking(space->bottom(), space->top());
+}
+
+static void VerifyMarking(PagedSpace* space) {
+  PageIterator it(space, PageIterator::PAGES_IN_USE);
+
+  while (it.has_next()) {
+    VerifyMarking(it.next());
+  }
+}
+
+static void VerifyMarking() {
+  VerifyMarking(Heap::old_pointer_space());
+  VerifyMarking(Heap::old_data_space());
+  VerifyMarking(Heap::code_space());
+  VerifyMarking(Heap::cell_space());
+  VerifyMarking(Heap::map_space());
+  VerifyMarking(Heap::new_space());
+
+  VerifyMarkingVisitor visitor;
+  Heap::IterateStrongRoots(&visitor, VISIT_ONLY_STRONG);
+}
+#endif
+
 void MarkCompactCollector::CollectGarbage() {
   // Make sure that Prepare() has been called. The individual steps below will
   // update the state as they proceed.
   ASSERT(state_ == PREPARE_GC);
 
   // Prepare has selected whether to compact the old generation or not.
   // Tell the tracer.
-  if (IsCompacting()) tracer_->set_is_compacting();
+  // if (IsCompacting()) tracer_->set_is_compacting();

[Erik Corry, 2011/02/22 12:27:19]

Commented code.

[Vyacheslav Egorov (Chromium), 2011/02/23 14:31:46]

Done.

 
-  MarkLiveObjects();
+  if (IncrementalMarking::state() == IncrementalMarking::STOPPED) {
+    MarkLiveObjects();
+  } else {
+    {
+      GCTracer::Scope gc_scope(tracer_, GCTracer::Scope::MC_MARK);
+      IncrementalMarking::Finalize();
+      ASSERT(IncrementalMarking::state() == IncrementalMarking::STOPPED);
+    }
+    MarkLiveObjects();
+  }
 
-  if (FLAG_collect_maps) ClearNonLiveTransitions();
+#ifdef DEBUG
+  VerifyMarking();
+#endif
+  // if (FLAG_collect_maps) ClearNonLiveTransitions();
 
   SweepSpaces();
 
   PcToCodeCache::FlushPcToCodeCache();
 
   Finish();
 
   // Check that swept all marked objects and
   // null out the GC tracer.
   // TODO(gc) does not work with conservative sweeping.
@@ skipping 32 matching lines @@
 }
 
 static void ClearMarkbits() {
   // We are sweeping code and map spaces precisely so clearing is not required.
   ClearMarkbits(Heap::old_pointer_space());
   ClearMarkbits(Heap::old_data_space());
   ClearMarkbits(Heap::cell_space());
 }
 
 
+void Marking::TransferMark(Address old_start, Address new_start) {
+  if (IncrementalMarking::state() == IncrementalMarking::MARKING) {
+    if (IncrementalMarking::IsBlack(HeapObject::FromAddress(old_start))) {
+      IncrementalMarking::MarkBlack(HeapObject::FromAddress(new_start));
+    } else if (IncrementalMarking::IsGrey(HeapObject::FromAddress(old_start))) {
+      IncrementalMarking::WhiteToGrey(HeapObject::FromAddress(new_start));
+      // TODO(gc): if we shift huge array in the loop we might end up pushing
+      // to much to marking stack. maybe we should check one or two elements
+      // on top of it to see whether they are equal to old_start.

[Erik Corry, 2011/02/22 12:27:19]

Or perhaps we should compact the marking stack by removing pointers to filler
objects in this case.

[Vyacheslav Egorov (Chromium), 2011/02/23 14:31:46]

We will think about it.

+    }
+  } else {
+    if (Heap::InNewSpace(old_start) ||
+        Page::FromAddress(old_start)->IsFlagSet(Page::IS_CONTINUOUS) ||
+        !IsMarked(old_start)) {
+      return;
+    }
+    SetMark(new_start);
+  }
+}
+
+
 void MarkCompactCollector::Prepare(GCTracer* tracer) {
   FLAG_flush_code = false;
   FLAG_always_compact = false;
   FLAG_never_compact = true;
 
+  // Disable collection of maps if incremental marking is enabled.
+  // TODO(gc) improve maps collection algorithm to work with incremental
+  // marking.
+  if (FLAG_incremental_marking) FLAG_collect_maps = false;
+
   // Rather than passing the tracer around we stash it in a static member
   // variable.
   tracer_ = tracer;
 
 #ifdef DEBUG
   ASSERT(state_ == IDLE);
   state_ = PREPARE_GC;
 #endif
   ASSERT(!FLAG_always_compact || !FLAG_never_compact);
 
   compacting_collection_ =
       FLAG_always_compact || force_compaction_ || compact_on_next_gc_;
   compact_on_next_gc_ = false;
 
   if (FLAG_never_compact) compacting_collection_ = false;
-  if (!Heap::map_space()->MapPointersEncodable())
-      compacting_collection_ = false;
+  if (!Heap::map_space()->MapPointersEncodable()) {
+    compacting_collection_ = false;
+  }
   if (FLAG_collect_maps) CreateBackPointers();
 #ifdef ENABLE_GDB_JIT_INTERFACE
   if (FLAG_gdbjit) {
     // If GDBJIT interface is active disable compaction.
     compacting_collection_ = false;
   }
 #endif
 
   PagedSpaces spaces;
   for (PagedSpace* space = spaces.next();
        space != NULL; space = spaces.next()) {
     space->PrepareForMarkCompact(compacting_collection_);
   }
 
-  Address new_space_top = Heap::new_space()->top();
-  Address new_space_bottom = Heap::new_space()->bottom();
+  if (IncrementalMarking::state() == IncrementalMarking::STOPPED) {
+    Address new_space_top = Heap::new_space()->top();
+    Address new_space_bottom = Heap::new_space()->bottom();
 
-  Marking::ClearRange(new_space_bottom,
-                      static_cast<int>(new_space_top - new_space_bottom));
+    Marking::ClearRange(new_space_bottom,
+                        static_cast<int>(new_space_top - new_space_bottom));
 
-  ClearMarkbits();
+    ClearMarkbits();
+#ifdef DEBUG
+    VerifyMarkbitsAreClean();
+#endif
+  }
 
 #ifdef DEBUG
-  VerifyMarkbitsAreClean();
-
   live_bytes_ = 0;
   live_young_objects_size_ = 0;
   live_old_pointer_objects_size_ = 0;
   live_old_data_objects_size_ = 0;
   live_code_objects_size_ = 0;
   live_map_objects_size_ = 0;
   live_cell_objects_size_ = 0;
   live_lo_objects_size_ = 0;
 #endif
 }
@@ skipping 324 matching lines @@
       MarkCompactCollector::MarkObject(code);
     }
   }
 
   static void VisitGlobalPropertyCell(RelocInfo* rinfo) {
     ASSERT(rinfo->rmode() == RelocInfo::GLOBAL_PROPERTY_CELL);
     Object* cell = rinfo->target_cell();
     Object* old_cell = cell;
     VisitPointer(&cell);
     if (cell != old_cell) {
-      rinfo->set_target_cell(reinterpret_cast<JSGlobalPropertyCell*>(cell));
+      rinfo->set_target_cell(reinterpret_cast<JSGlobalPropertyCell*>(cell), NULL);
     }
   }
 
   static inline void VisitDebugTarget(RelocInfo* rinfo) {
     ASSERT((RelocInfo::IsJSReturn(rinfo->rmode()) &&
             rinfo->IsPatchedReturnSequence()) ||
            (RelocInfo::IsDebugBreakSlot(rinfo->rmode()) &&
             rinfo->IsPatchedDebugBreakSlotSequence()));
     HeapObject* code = Code::GetCodeFromTargetAddress(rinfo->call_address());
     MarkCompactCollector::MarkObject(code);
@@ skipping 226 matching lines @@
     Object* old_code = code;
     VisitPointer(&code);
     if (code != old_code) {
       Memory::Address_at(entry_address) =
           reinterpret_cast<Code*>(code)->entry();
     }
   }
 
 
   static void VisitJSFunctionAndFlushCode(Map* map, HeapObject* object) {
+    UNREACHABLE();

[Erik Corry, 2011/02/22 12:27:19]

TODO?

[Vyacheslav Egorov (Chromium), 2011/02/23 14:31:46]

Done.

+#if 0

[Erik Corry, 2011/02/22 12:27:19]

Commented code.

[Vyacheslav Egorov (Chromium), 2011/02/23 14:31:46]

Done.

     JSFunction* jsfunction = reinterpret_cast<JSFunction*>(object);
     // The function must have a valid context and not be a builtin.
     bool flush_code_candidate = false;
     if (IsValidNotBuiltinContext(jsfunction->unchecked_context())) {
       flush_code_candidate = FlushCodeForFunction(jsfunction);
     }
 
     if (!flush_code_candidate) {
       MarkCompactCollector::MarkObject(
           jsfunction->unchecked_shared()->unchecked_code());
@@ skipping 14 matching lines @@
           JSFunction* inlined = reinterpret_cast<JSFunction*>(literals->get(i));
           MarkCompactCollector::MarkObject(
               inlined->unchecked_shared()->unchecked_code());
         }
       }
     }
 
     VisitJSFunctionFields(map,
                           reinterpret_cast<JSFunction*>(object),
                           flush_code_candidate);
+#endif
   }
 
 
   static void VisitJSFunction(Map* map, HeapObject* object) {
     VisitJSFunctionFields(map,
                           reinterpret_cast<JSFunction*>(object),
                           false);
   }
 
 
@@ skipping 226 matching lines @@
 
 
 void MarkCompactCollector::ProcessNewlyMarkedObject(HeapObject* object) {
   ASSERT(Marking::IsMarked(object));
   ASSERT(Heap::Contains(object));
   if (object->IsMap()) {
     Map* map = Map::cast(object);
     if (FLAG_cleanup_caches_in_maps_at_gc) {
       map->ClearCodeCache();
     }
-    if (FLAG_collect_maps &&
+    /*if (FLAG_collect_maps &&

[Erik Corry, 2011/02/22 12:27:19]

Commented code.  TODO?

[Vyacheslav Egorov (Chromium), 2011/02/23 14:31:46]

Done.

         map->instance_type() >= FIRST_JS_OBJECT_TYPE &&
         map->instance_type() <= JS_FUNCTION_TYPE) {
+      UNREACHABLE();
       MarkMapContents(map);
-    } else {
+      } else {*/
       marking_stack.Push(map);
-    }
+      /*}*/
   } else {
     marking_stack.Push(object);
   }
 }
 
 
 void MarkCompactCollector::MarkMapContents(Map* map) {
   MarkDescriptorArray(reinterpret_cast<DescriptorArray*>(
       *HeapObject::RawField(map, Map::kInstanceDescriptorsOffset)));
 
@@ skipping 289 matching lines @@
   GlobalHandles::IterateWeakRoots(&root_visitor);
   while (marking_stack.overflowed()) {
     RefillMarkingStack();
     EmptyMarkingStack();
   }
 
   // Repeat the object groups to mark unmarked groups reachable from the
   // weak roots.
   ProcessObjectGroups();
 
+  AfterMarking();
+}
+
+
+void MarkCompactCollector::AfterMarking() {
   // Prune the symbol table removing all symbols only pointed to by the
   // symbol table.  Cannot use symbol_table() here because the symbol
   // table is marked.
   SymbolTable* symbol_table = Heap::raw_unchecked_symbol_table();
   SymbolTableCleaner v;
   symbol_table->IterateElements(&v);
   symbol_table->ElementsRemoved(v.PointersRemoved());
   ExternalStringTable::Iterate(&v);
   ExternalStringTable::CleanUp();
 
   // Process the weak references.
   MarkCompactWeakObjectRetainer mark_compact_object_retainer;
   Heap::ProcessWeakReferences(&mark_compact_object_retainer);
 
   // Remove object groups after marking phase.
   GlobalHandles::RemoveObjectGroups();
 
   // Flush code from collected candidates.
-  FlushCode::ProcessCandidates();
+  // FlushCode::ProcessCandidates();

[Erik Corry, 2011/02/22 12:27:19]

Commented code and missing TODO'

[Vyacheslav Egorov (Chromium), 2011/02/23 14:31:46]

Done.

 }
 
 
 #ifdef DEBUG
 void MarkCompactCollector::UpdateLiveObjectCount(HeapObject* obj) {
   live_bytes_ += obj->Size();
   if (Heap::new_space()->Contains(obj)) {
     live_young_objects_size_ += obj->Size();
   } else if (Heap::map_space()->Contains(obj)) {
     ASSERT(obj->IsMap());
@@ skipping 139 matching lines @@
   void VisitPointers(Object** start, Object** end) {
     for (Object** p = start; p < end; p++) {
       StaticPointersToNewGenUpdatingVisitor::VisitPointer(p);
     }
   }
 
   void VisitCodeTarget(RelocInfo* rinfo) {
     ASSERT(RelocInfo::IsCodeTarget(rinfo->rmode()));
     Object* target = Code::GetCodeFromTargetAddress(rinfo->target_address());
     VisitPointer(&target);
-    rinfo->set_target_address(Code::cast(target)->instruction_start());
+    rinfo->set_target_address(Code::cast(target)->instruction_start(), NULL);
   }
 
   void VisitDebugTarget(RelocInfo* rinfo) {
     ASSERT((RelocInfo::IsJSReturn(rinfo->rmode()) &&
             rinfo->IsPatchedReturnSequence()) ||
            (RelocInfo::IsDebugBreakSlot(rinfo->rmode()) &&
             rinfo->IsPatchedDebugBreakSlotSequence()));
     Object* target = Code::GetCodeFromTargetAddress(rinfo->call_address());
     VisitPointer(&target);
     rinfo->set_call_address(Code::cast(target)->instruction_start());
@@ skipping 309 matching lines @@
       Marking::ClearMark(object);
       MarkCompactCollector::tracer()->decrement_marked_count();
 
       if (!is_previous_alive) {  // Transition from free to live.
         space->DeallocateBlock(free_start,
                                static_cast<int>(current - free_start),
                                true);
         is_previous_alive = true;
       }
     } else {
+      ASSERT((current + kPointerSize) >= p->AllocationTop() ||
+             object->Size() == 4 ||

[Erik Corry, 2011/02/22 12:27:19]

kPointerSize?

[Vyacheslav Egorov (Chromium), 2011/02/23 14:31:46]

Done.

+             IncrementalMarking::IsWhite(object));
       MarkCompactCollector::ReportDeleteIfNeeded(object);
       if (is_previous_alive) {  // Transition from live to free.
         free_start = current;
         is_previous_alive = false;
       }
     }
   }
 
   if (!is_previous_alive) *last_free_start = free_start;
 }
@@ skipping 122 matching lines @@
     space->SetTop(new_allocation_top);
   }
 }
 
 
 void MarkCompactCollector::SweepSpaces() {
   GCTracer::Scope gc_scope(tracer_, GCTracer::Scope::MC_SWEEP);
 #ifdef DEBUG
   state_ = SWEEP_SPACES;
 #endif
+
+#ifndef DEBUG
+  SweeperType fast_sweeper = CONSERVATIVE;
+#else
+  SweeperType fast_sweeper = PRECISE;
+#endif
+
   ASSERT(!IsCompacting());
   // Noncompacting collections simply sweep the spaces to clear the mark
   // bits and free the nonlive blocks (for old and map spaces).  We sweep
   // the map space last because freeing non-live maps overwrites them and
   // the other spaces rely on possibly non-live maps to get the sizes for
   // non-live objects.
-  SweepSpace(Heap::old_pointer_space(), CONSERVATIVE);
-  SweepSpace(Heap::old_data_space(), CONSERVATIVE);
+  SweepSpace(Heap::old_pointer_space(), fast_sweeper);
+  SweepSpace(Heap::old_data_space(), fast_sweeper);
   SweepSpace(Heap::code_space(), PRECISE);
   // TODO(gc): implement specialized sweeper for cell space.
-  SweepSpace(Heap::cell_space(), CONSERVATIVE);
+  SweepSpace(Heap::cell_space(), fast_sweeper);
   { GCTracer::Scope gc_scope(tracer_, GCTracer::Scope::MC_SWEEP_NEWSPACE);
     SweepNewSpace(Heap::new_space());
   }
   // TODO(gc): ClearNonLiveTransitions depends on precise sweeping of
   // map space to detect whether unmarked map became dead in this
   // collection or in one of the previous ones.
   // TODO(gc): Implement specialized sweeper for map space.
   SweepSpace(Heap::map_space(), PRECISE);
 
   ASSERT(live_map_objects_size_ <= Heap::map_space()->Size());
@@ skipping 72 matching lines @@
 }
 
 
 void MarkCompactCollector::Initialize() {
   StaticPointersToNewGenUpdatingVisitor::Initialize();
   StaticMarkingVisitor::Initialize();
 }
 
 
 } }  // namespace v8::internal