[heap] Implement simple concurrent marking deque.

src/heap/incremental-marking.cc

 // Copyright 2012 the V8 project authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "src/heap/incremental-marking.h"
 
 #include "src/code-stubs.h"
 #include "src/compilation-cache.h"
 #include "src/conversions.h"
 #include "src/heap/concurrent-marking.h"
@@ skipping 533 matching lines @@
 
   heap_->CompletelyClearInstanceofCache();
   heap_->isolate()->compilation_cache()->MarkCompactPrologue();
 
   // Mark strong roots grey.
   IncrementalMarkingRootMarkingVisitor visitor(this);
   heap_->IterateStrongRoots(&visitor, VISIT_ONLY_STRONG);
 
   if (FLAG_concurrent_marking) {
     ConcurrentMarking* concurrent_marking = heap_->concurrent_marking();
-    heap_->mark_compact_collector()->marking_deque()->Iterate(
-        [concurrent_marking](HeapObject* obj) {
-          concurrent_marking->AddRoot(obj);
-        });
     concurrent_marking->StartTask();
   }
 
   // Ready to start incremental marking.
   if (FLAG_trace_incremental_marking) {
     heap()->isolate()->PrintWithTimestamp("[IncrementalMarking] Running\n");
   }
 }
 
 void IncrementalMarking::StartBlackAllocation() {
@@ skipping 137 matching lines @@
   }
 }
 
 void IncrementalMarking::FinalizeIncrementally() {
   TRACE_GC(heap()->tracer(), GCTracer::Scope::MC_INCREMENTAL_FINALIZE_BODY);
   DCHECK(!finalize_marking_completed_);
   DCHECK(IsMarking());
 
   double start = heap_->MonotonicallyIncreasingTimeInMs();
 
-  int old_marking_deque_top =
-      heap_->mark_compact_collector()->marking_deque()->top();
-
   // After finishing incremental marking, we try to discover all unmarked
   // objects to reduce the marking load in the final pause.
   // 1) We scan and mark the roots again to find all changes to the root set.
   // 2) Age and retain maps embedded in optimized code.
   // 3) Remove weak cell with live values from the list of weak cells, they
   // do not need processing during GC.
   MarkRoots();
 
   if (incremental_marking_finalization_rounds_ == 0) {
     // Map retaining is needed for perfromance, not correctness,
     // so we can do it only once at the beginning of the finalization.
     RetainMaps();
   }
   ProcessWeakCells();
 
   int marking_progress =
-      abs(old_marking_deque_top -
-          heap_->mark_compact_collector()->marking_deque()->top());
-
-  marking_progress += static_cast<int>(
-      heap_->local_embedder_heap_tracer()->NumberOfCachedWrappersToTrace());
+      heap_->mark_compact_collector()->marking_deque()->Size() +

[ulan, 2017/04/27 17:49:39]

This changes behavior.

+      static_cast<int>(
+          heap_->local_embedder_heap_tracer()->NumberOfCachedWrappersToTrace());
 
   double end = heap_->MonotonicallyIncreasingTimeInMs();
   double delta = end - start;
   if (FLAG_trace_incremental_marking) {
     heap()->isolate()->PrintWithTimestamp(
         "[IncrementalMarking] Finalize incrementally round %d, "
         "spent %d ms, marking progress %d.\n",
         static_cast<int>(delta), incremental_marking_finalization_rounds_,
         marking_progress);
   }
@@ skipping 13 matching lines @@
     StartBlackAllocation();
   }
 }
 
 
 void IncrementalMarking::UpdateMarkingDequeAfterScavenge() {
   if (!IsMarking()) return;
 
   MarkingDeque* marking_deque =
       heap_->mark_compact_collector()->marking_deque();
-  int current = marking_deque->bottom();

[ulan, 2017/04/27 17:49:39]

We no longer can assume contiguous structure of the marking deque.
MarkingDeque::Update method abstracts away iteration, filtering and compaction
of the marking deque. 

-  int mask = marking_deque->mask();
-  int limit = marking_deque->top();
-  HeapObject** array = marking_deque->array();
-  int new_top = current;
-
   Map* filler_map = heap_->one_pointer_filler_map();
-
-  while (current != limit) {
-    HeapObject* obj = array[current];
+  Heap* heap = heap_;
+  marking_deque->Update([heap, filler_map](HeapObject* obj) -> HeapObject* {
     DCHECK(obj->IsHeapObject());
-    current = ((current + 1) & mask);
     // Only pointers to from space have to be updated.
-    if (heap_->InFromSpace(obj)) {
+    if (heap->InFromSpace(obj)) {
       MapWord map_word = obj->map_word();
       // There may be objects on the marking deque that do not exist anymore,
       // e.g. left trimmed objects or objects from the root set (frames).
       // If these object are dead at scavenging time, their marking deque
       // entries will not point to forwarding addresses. Hence, we can discard
       // them.
-      if (map_word.IsForwardingAddress()) {
-        HeapObject* dest = map_word.ToForwardingAddress();
-        if (ObjectMarking::IsBlack(dest, MarkingState::Internal(dest)))
-          continue;
-        array[new_top] = dest;
-        new_top = ((new_top + 1) & mask);
-        DCHECK(new_top != marking_deque->bottom());
-        DCHECK(ObjectMarking::IsGrey(obj, MarkingState::Internal(obj)) ||
-               (obj->IsFiller() &&
-                ObjectMarking::IsWhite(obj, MarkingState::Internal(obj))));
+      if (!map_word.IsForwardingAddress()) return nullptr;
+      HeapObject* dest = map_word.ToForwardingAddress();
+      if (ObjectMarking::IsBlack(dest, MarkingState::Internal(dest))) {
+        // The object is already processed by the marker.
+        return nullptr;
       }
-    } else if (obj->map() != filler_map) {
+      DCHECK(ObjectMarking::IsGrey(obj, MarkingState::Internal(obj)) ||
+             (obj->IsFiller() &&
+              ObjectMarking::IsWhite(obj, MarkingState::Internal(obj))));
+      return dest;
+    } else {
       // Skip one word filler objects that appear on the
       // stack when we perform in place array shift.
-      array[new_top] = obj;
-      new_top = ((new_top + 1) & mask);
-      DCHECK(new_top != marking_deque->bottom());
       DCHECK(ObjectMarking::IsGrey(obj, MarkingState::Internal(obj)) ||
              (obj->IsFiller() &&
               ObjectMarking::IsWhite(obj, MarkingState::Internal(obj))) ||
              (MemoryChunk::FromAddress(obj->address())
                   ->IsFlagSet(MemoryChunk::HAS_PROGRESS_BAR) &&
               ObjectMarking::IsBlack(obj, MarkingState::Internal(obj))));
+      return (obj->map() == filler_map) ? nullptr : obj;
     }
-  }
-  marking_deque->set_top(new_top);
+  });
 }
 
 
 void IncrementalMarking::VisitObject(Map* map, HeapObject* obj, int size) {
   MarkGrey(heap_, map);
 
   IncrementalMarkingMarkingVisitor::IterateBody(map, obj);
 
 #if ENABLE_SLOW_DCHECKS
   MarkBit mark_bit =
@@ skipping 359 matching lines @@
   idle_marking_delay_counter_++;
 }
 
 
 void IncrementalMarking::ClearIdleMarkingDelayCounter() {
   idle_marking_delay_counter_ = 0;
 }
 
 }  // namespace internal
 }  // namespace v8