Introduce lazy sweeping.

src/incremental-marking.cc

 // Copyright 2011 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 88 matching lines @@
 
 
 class IncrementalMarkingRootMarkingVisitor : public ObjectVisitor {
  public:
   IncrementalMarkingRootMarkingVisitor(Heap* heap,
                                        IncrementalMarking* incremental_marking)
       : heap_(heap),
         incremental_marking_(incremental_marking) {
   }
 
-
   void VisitPointer(Object** p) {
     MarkObjectByPointer(p);
   }
 
   void VisitPointers(Object** start, Object** end) {
     for (Object** p = start; p < end; p++) MarkObjectByPointer(p);
   }
 
  private:
   void MarkObjectByPointer(Object** p) {
     Object* obj = *p;
     if (!obj->IsHeapObject()) return;
 
     HeapObject* heap_object = HeapObject::cast(obj);
     MarkBit mark_bit = heap_->marking()->MarkBitFrom(heap_object);
     if (mark_bit.data_only()) {
       incremental_marking_->MarkBlackOrKeepGrey(mark_bit);
     } else {
       if (IncrementalMarking::IsWhite(mark_bit)) {
         incremental_marking_->WhiteToGreyAndPush(heap_object, mark_bit);
       }
     }
   }
 
   Heap* heap_;
   IncrementalMarking* incremental_marking_;
 };
 
 
-static void ClearMarkbits(PagedSpace* space) {
+void IncrementalMarking::ClearMarkbits(PagedSpace* space) {
   PageIterator it(space);
 
   while (it.has_next()) {
     Page* p = it.next();
     p->markbits()->Clear();
   }
 }
 
 
-static void ClearMarkbits() {
+void IncrementalMarking::ClearMarkbits() {
   // TODO(gc): Clear the mark bits in the sweeper.
-  // TODO(gc) ISOLATES MERGE
-  ClearMarkbits(HEAP->old_pointer_space());
-  ClearMarkbits(HEAP->old_data_space());
-  ClearMarkbits(HEAP->cell_space());
-  ClearMarkbits(HEAP->map_space());
-  ClearMarkbits(HEAP->code_space());
+  ClearMarkbits(heap_->old_pointer_space());
+  ClearMarkbits(heap_->old_data_space());
+  ClearMarkbits(heap_->cell_space());
+  ClearMarkbits(heap_->map_space());
+  ClearMarkbits(heap_->code_space());

[Erik Corry, 2011/05/09 21:20:11]

Who clears the mark bits in the large object space?

 }
 
 
 #ifdef DEBUG
-  static void VerifyMarkbitsAreClean(PagedSpace* space) {
-    PageIterator it(space);
+void IncrementalMarking::VerifyMarkbitsAreClean(PagedSpace* space) {
+  PageIterator it(space);
 
-    while (it.has_next()) {
-      Page* p = it.next();
-      ASSERT(p->markbits()->IsClean());
-    }
+  while (it.has_next()) {
+    Page* p = it.next();
+    ASSERT(p->markbits()->IsClean());
   }
+}
 
-  static void VerifyMarkbitsAreClean() {
-    // TODO(gc) ISOLATES MERGE
-    VerifyMarkbitsAreClean(HEAP->old_pointer_space());
-    VerifyMarkbitsAreClean(HEAP->old_data_space());
-    VerifyMarkbitsAreClean(HEAP->code_space());
-    VerifyMarkbitsAreClean(HEAP->cell_space());
-    VerifyMarkbitsAreClean(HEAP->map_space());
-  }
+
+void IncrementalMarking::VerifyMarkbitsAreClean() {
+  VerifyMarkbitsAreClean(heap_->old_pointer_space());
+  VerifyMarkbitsAreClean(heap_->old_data_space());
+  VerifyMarkbitsAreClean(heap_->code_space());
+  VerifyMarkbitsAreClean(heap_->cell_space());
+  VerifyMarkbitsAreClean(heap_->map_space());
+}
 #endif
 
+
 bool IncrementalMarking::WorthActivating() {
 #ifndef DEBUG
   static const intptr_t kActivationThreshold = 8 * MB;
 #else
   // TODO(gc) consider setting this to some low level so that some
   // debug tests run with incremental marking and some without.
   static const intptr_t kActivationThreshold = 0;
 #endif
 
   // TODO(gc) ISOLATES MERGE
@@ skipping 15 matching lines @@
           CodeStub::RecordWrite) {
         Object* e = stubs->ValueAt(i);
         if (e->IsCode()) {
           RecordWriteStub::Patch(Code::cast(e), enable);
         }
       }
     }
   }
 }
 
+
 static VirtualMemory* marking_deque_memory = NULL;
 
+
 static void EnsureMarkingDequeIsCommitted() {
   if (marking_deque_memory == NULL) {
     marking_deque_memory = new VirtualMemory(4*MB);
     marking_deque_memory->Commit(
         reinterpret_cast<Address>(marking_deque_memory->address()),
         marking_deque_memory->size(),
         false);  // Not executable.
   }
 }
 
 
 void IncrementalMarking::Start() {
   if (FLAG_trace_incremental_marking) {
     PrintF("[IncrementalMarking] Start\n");
   }
   ASSERT(FLAG_incremental_marking);
   ASSERT(state_ == STOPPED);
-  state_ = MARKING;
 
   ResetStepCounters();
 
+  if (heap_->old_pointer_space()->IsSweepingComplete() &&
+      heap_->old_data_space()->IsSweepingComplete()) {
+    StartMarking();
+  } else {
+    PrintF("[IncrementalMarking] Start sweeping.\n");

[antonm, 2011/05/10 13:09:38]

if (FLAG_trace_incremental_marking)?

+    state_ = SWEEPING;
+  }
+}
+
+
+void IncrementalMarking::StartMarking() {
+  if (FLAG_trace_incremental_marking) {
+    PrintF("[IncrementalMarking] Start marking\n");
+  }
+
+  state_ = MARKING;
+
   PatchIncrementalMarkingRecordWriteStubs(true);
 
   EnsureMarkingDequeIsCommitted();
 
   // Initialize marking stack.
   Address addr = static_cast<Address>(marking_deque_memory->address());
   marking_deque_.Initialize(addr,
                             addr + marking_deque_memory->size());
 
   // Clear markbits.
@@ skipping 86 matching lines @@
     state_ = COMPLETE;
     if (FLAG_trace_incremental_marking) {
       double end = OS::TimeCurrentMillis();
       PrintF("[IncrementalMarking] Complete (hurry), spent %d ms.\n",
              static_cast<int>(end - start));
     }
   }
 }
 
 
+void IncrementalMarking::Abort() {
+  if (IsStopped()) return;
+  heap_->new_space()->LowerInlineAllocationLimit(0);
+  IncrementalMarking::set_should_hurry(false);
+  ResetStepCounters();
+  if (IsMarking()) PatchIncrementalMarkingRecordWriteStubs(false);
+  heap_->isolate()->stack_guard()->Continue(GC_REQUEST);
+  state_ = STOPPED;
+}
+
+
 void IncrementalMarking::Finalize() {
   Hurry();
   state_ = STOPPED;
   heap_->new_space()->LowerInlineAllocationLimit(0);
   IncrementalMarking::set_should_hurry(false);
   ResetStepCounters();
   PatchIncrementalMarkingRecordWriteStubs(false);
   ASSERT(marking_deque_.IsEmpty());
-  ISOLATE->stack_guard()->Continue(GC_REQUEST);
+  heap_->isolate()->stack_guard()->Continue(GC_REQUEST);
 }
 
 
 void IncrementalMarking::MarkingComplete() {
   state_ = COMPLETE;
   // We will set the stack guard to request a GC now.  This will mean the rest
   // of the GC gets performed as soon as possible (we can't do a GC here in a
   // record-write context).  If a few things get allocated between now and then
   // that shouldn't make us do a scavenge and keep being incremental, so we set
   // the should-hurry flag to indicate that there can't be much work left to do.
   set_should_hurry(true);
   if (FLAG_trace_incremental_marking) {
     PrintF("[IncrementalMarking] Complete (normal).\n");
   }
   // TODO(gc) ISOLATES
   ISOLATE->stack_guard()->RequestGC();
 }
 
 
 void IncrementalMarking::Step(intptr_t allocated_bytes) {
-  if (state_ == MARKING &&
-      heap_->gc_state() == Heap::NOT_IN_GC &&
-      FLAG_incremental_marking_steps) {
-    allocated_ += allocated_bytes;
+  if (heap_->gc_state() != Heap::NOT_IN_GC) return;
+  if (!FLAG_incremental_marking_steps) return;
 
-    if (allocated_ >= kAllocatedThreshold) {
-      double start = 0;
+  allocated_ += allocated_bytes;
 
-      if (FLAG_trace_incremental_marking || FLAG_trace_gc) {
-        start = OS::TimeCurrentMillis();
-      }
+  if (allocated_ < kAllocatedThreshold) return;
 
-      intptr_t bytes_to_process = allocated_ * allocation_marking_factor_;
-      int count = 0;
+  intptr_t bytes_to_process = allocated_ * allocation_marking_factor_;
 
-      Map* filler_map = heap_->one_pointer_filler_map();
-      IncrementalMarkingMarkingVisitor marking_visitor(heap_, this);
-      Marking* marking = heap_->marking();
-      while (!marking_deque_.IsEmpty() && bytes_to_process > 0) {
-        HeapObject* obj = marking_deque_.Pop();
+  double start = 0;
 
-        // Explicitly skip one word fillers. Incremental markbit patterns are
-        // correct only for objects that occupy at least two words.
-        Map* map = obj->map();
-        if (map != filler_map) {
-          ASSERT(IsGrey(marking->MarkBitFrom(obj)));
-          int size = obj->SizeFromMap(map);
-          bytes_to_process -= size;
-          MarkBit map_mark_bit = marking->MarkBitFromOldSpace(map);
-          if (IsWhite(map_mark_bit)) WhiteToGreyAndPush(map, map_mark_bit);
-          // TODO(gc) switch to static visitor instead of normal visitor.
-          obj->IterateBody(map->instance_type(), size, &marking_visitor);
-          MarkBit obj_mark_bit = marking->MarkBitFrom(obj);
-          MarkBlack(obj_mark_bit);
-        }
-        count++;
-      }
-      allocated_ = 0;
-      if (marking_deque_.IsEmpty()) MarkingComplete();
-      if (FLAG_trace_incremental_marking || FLAG_trace_gc) {
-        double end = OS::TimeCurrentMillis();
-        steps_took_ += (end - start);
-      }
+  if (FLAG_trace_incremental_marking || FLAG_trace_gc) {
+    start = OS::TimeCurrentMillis();
+  }
 
-      steps_count_++;
+  if (state_ == SWEEPING) {
+    if (heap_->old_pointer_space()->AdvanceSweeper(bytes_to_process) &&
+        heap_->old_data_space()->AdvanceSweeper(bytes_to_process)) {
+      StartMarking();
+    }
+  } else if (state_ == MARKING) {
+    Map* filler_map = heap_->one_pointer_filler_map();
+    IncrementalMarkingMarkingVisitor marking_visitor(heap_, this);
+    Marking* marking = heap_->marking();
+    while (!marking_deque_.IsEmpty() && bytes_to_process > 0) {
+      HeapObject* obj = marking_deque_.Pop();
 
-      if ((steps_count_ % kAllocationMarkingFactorSpeedupInterval) == 0) {
-        allocation_marking_factor_ += kAllocationMarkingFactorSpeedup;
-        allocation_marking_factor_ *= 1.3;
-        if (FLAG_trace_gc) {
-          PrintF("Marking speed increased to %d\n", allocation_marking_factor_);
-        }
+      // Explicitly skip one word fillers. Incremental markbit patterns are
+      // correct only for objects that occupy at least two words.
+      Map* map = obj->map();
+      if (map != filler_map) {
+        ASSERT(IsGrey(marking->MarkBitFrom(obj)));
+        int size = obj->SizeFromMap(map);
+        bytes_to_process -= size;
+        MarkBit map_mark_bit = marking->MarkBitFromOldSpace(map);
+        if (IsWhite(map_mark_bit)) WhiteToGreyAndPush(map, map_mark_bit);
+        // TODO(gc) switch to static visitor instead of normal visitor.
+        obj->IterateBody(map->instance_type(), size, &marking_visitor);
+        MarkBit obj_mark_bit = marking->MarkBitFrom(obj);
+        MarkBlack(obj_mark_bit);
       }
     }
+    if (marking_deque_.IsEmpty()) MarkingComplete();
+  }
+
+  allocated_ = 0;
+
+  steps_count_++;
+
+  if ((steps_count_ % kAllocationMarkingFactorSpeedupInterval) == 0) {
+    allocation_marking_factor_ += kAllocationMarkingFactorSpeedup;
+    allocation_marking_factor_ *= 1.3;
+    if (FLAG_trace_gc) {
+      PrintF("Marking speed increased to %d\n", allocation_marking_factor_);
+    }
+  }
+
+  if (FLAG_trace_incremental_marking || FLAG_trace_gc) {
+    double end = OS::TimeCurrentMillis();
+    steps_took_ += (end - start);
   }
 }
 
 
 } }  // namespace v8::internal