Chunk-wise marking stack processing.

runtime/vm/gc_marker.cc

 // Copyright (c) 2011, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 
 #include "vm/gc_marker.h"
 
 #include <map>
 #include <utility>
 #include <vector>
 
 #include "vm/allocation.h"
 #include "vm/dart_api_state.h"
 #include "vm/isolate.h"
 #include "vm/log.h"
 #include "vm/pages.h"
 #include "vm/raw_object.h"
 #include "vm/stack_frame.h"
+#include "vm/store_buffer.h"
 #include "vm/thread_pool.h"
 #include "vm/visitor.h"
 #include "vm/object_id_ring.h"
 
 namespace dart {
 
-// A simple chunked marking stack.
-class MarkingStack : public ValueObject {
- public:
-  MarkingStack()
-      : head_(new MarkingStackChunk()),
-        empty_chunks_(NULL),
-        marking_stack_(NULL),
-        top_(0) {
-    marking_stack_ = head_->MarkingStackChunkMemory();
-  }
-
-  ~MarkingStack() {
-    // TODO(iposva): Consider caching a couple emtpy marking stack chunks.
-    ASSERT(IsEmpty());
-    delete head_;
-    MarkingStackChunk* next;
-    while (empty_chunks_ != NULL) {
-      next = empty_chunks_->next();
-      delete empty_chunks_;
-      empty_chunks_ = next;
-    }
-  }
-
-  bool IsEmpty() const {
-    return IsMarkingStackChunkEmpty() && (head_->next() == NULL);
-  }
-
-  void Push(RawObject* value) {
-    ASSERT(!IsMarkingStackChunkFull());
-    marking_stack_[top_] = value;
-    top_++;
-    if (IsMarkingStackChunkFull()) {
-      MarkingStackChunk* new_chunk;
-      if (empty_chunks_ == NULL) {
-        new_chunk = new MarkingStackChunk();
-      } else {
-        new_chunk = empty_chunks_;
-        empty_chunks_ = new_chunk->next();
-      }
-      new_chunk->set_next(head_);
-      head_ = new_chunk;
-      marking_stack_ = head_->MarkingStackChunkMemory();
-      top_ = 0;
-    }
-  }
-
-  RawObject* Pop() {
-    ASSERT(head_ != NULL);
-    ASSERT(!IsEmpty());
-    if (IsMarkingStackChunkEmpty()) {
-      MarkingStackChunk* empty_chunk = head_;
-      head_ = head_->next();
-      empty_chunk->set_next(empty_chunks_);
-      empty_chunks_ = empty_chunk;
-      marking_stack_ = head_->MarkingStackChunkMemory();
-      top_ = MarkingStackChunk::kMarkingStackChunkSize;
-    }
-    top_--;
-    return marking_stack_[top_];
-  }
-
- private:
-  class MarkingStackChunk {
-   public:
-    MarkingStackChunk() : next_(NULL) {}
-    ~MarkingStackChunk() {}
-
-    RawObject** MarkingStackChunkMemory() {
-      return &memory_[0];
-    }
-
-    MarkingStackChunk* next() const { return next_; }
-    void set_next(MarkingStackChunk* value) { next_ = value; }
-
-    static const uint32_t kMarkingStackChunkSize = 1024;
-
-   private:
-    RawObject* memory_[kMarkingStackChunkSize];
-    MarkingStackChunk* next_;
-
-    DISALLOW_COPY_AND_ASSIGN(MarkingStackChunk);
-  };
-
-  bool IsMarkingStackChunkFull() const {
-    return top_ == MarkingStackChunk::kMarkingStackChunkSize;
-  }
-
-  bool IsMarkingStackChunkEmpty() const {
-    return top_ == 0;
-  }
-
-  MarkingStackChunk* head_;
-  MarkingStackChunk* empty_chunks_;
-  RawObject** marking_stack_;
-  uint32_t top_;
-
-  DISALLOW_COPY_AND_ASSIGN(MarkingStack);
-};
-
+typedef StoreBufferBlock PointerBlock;  // TODO(koda): Rename to PointerBlock.
+typedef StoreBuffer MarkingStack;  // TODO(koda): Create shared base class.
 
 class DelaySet {
  private:
   typedef std::multimap<RawObject*, RawWeakProperty*> Map;
   typedef std::pair<RawObject*, RawWeakProperty*> MapEntry;
 
  public:
   DelaySet() : mutex_(new Mutex()) {}
   ~DelaySet() { delete mutex_; }
 
@@ skipping 44 matching lines @@
                  PageSpace* page_space,
                  MarkingStack* marking_stack,
                  DelaySet* delay_set,
                  bool visit_function_code)
       : ObjectPointerVisitor(isolate),
         thread_(Thread::Current()),
         heap_(heap),
         vm_heap_(Dart::vm_isolate()->heap()),
         class_table_(isolate->class_table()),
         page_space_(page_space),
-        marking_stack_(marking_stack),
+        work_list_(marking_stack),
         delay_set_(delay_set),
         visiting_old_object_(NULL),
-        visit_function_code_(visit_function_code) {
+        visit_function_code_(visit_function_code),
+        marked_bytes_(0) {
     ASSERT(heap_ != vm_heap_);
     ASSERT(thread_->isolate() == isolate);
   }
 
-  ~MarkingVisitor() {
-    // 'Finalize' should be explicitly called before destruction.
-    ASSERT(marking_stack_ == NULL);
+  uintptr_t marked_bytes() const { return marked_bytes_; }
+
+  // Returns true if some non-zero amount of work was performed.
+  bool DrainMarkingStack() {
+    RawObject* raw_obj = work_list_.Pop();
+    if (raw_obj == NULL) {
+      ASSERT(visiting_old_object_ == NULL);
+      return false;
+    }
+    do {
+      VisitingOldObject(raw_obj);
+      const intptr_t class_id = raw_obj->GetClassId();
+      // Currently, classes are considered roots (see issue 18284), so at this
+      // point, they should all be marked.
+      ASSERT(isolate()->class_table()->At(class_id)->IsMarked());
+      if (class_id != kWeakPropertyCid) {
+        marked_bytes_ += raw_obj->VisitPointers(this);
+      } else {
+        RawWeakProperty* raw_weak = reinterpret_cast<RawWeakProperty*>(raw_obj);
+        marked_bytes_ += raw_weak->Size();
+        ProcessWeakProperty(raw_weak);
+      }
+      raw_obj = work_list_.Pop();
+    } while (raw_obj != NULL);
+    VisitingOldObject(NULL);
+    return true;
   }
 
-  MarkingStack* marking_stack() const { return marking_stack_; }
-
   void VisitPointers(RawObject** first, RawObject** last) {
     for (RawObject** current = first; current <= last; current++) {
       MarkObject(*current, current);
     }
   }
 
   bool visit_function_code() const { return visit_function_code_; }
 
   virtual MallocGrowableArray<RawFunction*>* skipped_code_functions() {
     return &skipped_code_functions_;
@@ skipping 29 matching lines @@
       // Key is gray or black.  Make the weak property black.
       raw_weak->VisitPointers(this);
     }
   }
 
   // Called when all marking is complete.
   void Finalize() {
     if (!visit_function_code_) {
       DetachCode();
     }
-    // Fail fast on attempts to mark after finalizing.
-    marking_stack_ = NULL;
+    work_list_.Finalize();
   }
 
   void VisitingOldObject(RawObject* obj) {
     ASSERT((obj == NULL) || obj->IsOldObject());
     visiting_old_object_ = obj;
   }
 
  private:
+  class WorkList : public ValueObject {
+   public:
+    explicit WorkList(MarkingStack* marking_stack)
+        : marking_stack_(marking_stack) {
+      work_ = marking_stack_->PopEmptyBlock();
+    }
+
+    ~WorkList() {
+      ASSERT(work_ == NULL);
+      ASSERT(marking_stack_ == NULL);
+    }
+
+    // Returns NULL if no more work was found.
+    RawObject* Pop() {
+      ASSERT(work_ != NULL);
+      if (!work_->IsEmpty()) {
+        return work_->Pop();

[Ivan Posva, 2015/08/06 07:02:09]

How about structuring it like below, which to me reads more naturally since it
does not need to negation on the condition:

if (work_->IsEmpty()) {
  .. do all of the block flipping ..
}
return work_->Pop();

[koda, 2015/08/07 12:59:07]

Done.

+      }
+      // TODO(koda): Track over/underflow events and use in heuristics to
+      // distribute work and prevent degenerate flip-flopping.
+      PointerBlock* new_work = marking_stack_->PopNonEmptyBlock();
+      if (new_work == NULL) {
+        return NULL;
+      }
+      marking_stack_->PushBlock(work_);
+      work_ = new_work;
+      return work_->Pop();
+    }
+
+    void Push(RawObject* raw_obj) {
+      if (work_->IsFull()) {
+        // TODO(koda): Track over/underflow events and use in heuristics to
+        // distribute work and prevent degenerate flip-flopping.
+        marking_stack_->PushBlock(work_, false);
+        work_ = marking_stack_->PopEmptyBlock();
+      }
+      work_->Push(raw_obj);
+    }
+
+    void Finalize() {
+      ASSERT(work_->IsEmpty());
+      marking_stack_->PushBlock(work_, false);
+      work_ = NULL;
+      // Fail fast on attempts to mark after finalizing.
+      marking_stack_ = NULL;
+    }
+
+   private:
+    PointerBlock* work_;
+    MarkingStack* marking_stack_;
+  };
+
   void MarkAndPush(RawObject* raw_obj) {
     ASSERT(raw_obj->IsHeapObject());
     ASSERT((FLAG_verify_before_gc || FLAG_verify_before_gc) ?
            page_space_->Contains(RawObject::ToAddr(raw_obj)) :
            true);
 
     // Mark the object and push it on the marking stack.
     ASSERT(!raw_obj->IsMarked());
     const bool is_watched = raw_obj->IsWatched();
     raw_obj->SetMarkBitUnsynchronized();
     raw_obj->ClearRememberedBitUnsynchronized();
     raw_obj->ClearWatchedBitUnsynchronized();
     if (is_watched) {
       delay_set_->VisitValuesForKey(raw_obj, this);
     }
-    marking_stack_->Push(raw_obj);
+    work_list_.Push(raw_obj);
   }
 
   void MarkObject(RawObject* raw_obj, RawObject** p) {
     // Fast exit if the raw object is a Smi.
     if (!raw_obj->IsHeapObject()) {
       return;
     }
 
     // Fast exit if the raw object is marked.
     if (raw_obj->IsMarked()) {
@@ skipping 65 matching lines @@
     }
     // Clean up.
     skipped_code_functions_.Clear();
   }
 
   Thread* thread_;
   Heap* heap_;
   Heap* vm_heap_;
   ClassTable* class_table_;
   PageSpace* page_space_;
-  MarkingStack* marking_stack_;
+  WorkList work_list_;
   DelaySet* delay_set_;
   RawObject* visiting_old_object_;
   const bool visit_function_code_;
   MallocGrowableArray<RawFunction*> skipped_code_functions_;
+  uintptr_t marked_bytes_;
 
   DISALLOW_IMPLICIT_CONSTRUCTORS(MarkingVisitor);
 };
 
 
 static bool IsUnreachable(const RawObject* raw_obj) {
   if (!raw_obj->IsHeapObject()) {
     return false;
   }
   if (raw_obj == Object::null()) {
@@ skipping 99 matching lines @@
           break;
         }
       }
       // If all key objects are unreachable put the reference on a
       // delay queue.  This reference will be revisited if another
       // reference is marked.
       if (is_unreachable) {
         state->DelayWeakReferenceSet(reference_set);
       }
     }
-    if (!visitor->marking_stack()->IsEmpty()) {
-      DrainMarkingStack(isolate, visitor);
-    } else {
+    if (!visitor->DrainMarkingStack()) {
       // Break out of the loop if there has been no forward process.
       // All key objects in the weak reference sets are unreachable
       // so we reset the weak reference sets queue.
       state->set_delayed_weak_reference_sets(NULL);
       break;
     }
   }
   ASSERT(state->delayed_weak_reference_sets() == NULL);
   // All weak reference sets are zone allocated and unmarked references which
   // were on the delay queue will be freed when the zone is released in the
   // epilog callback.
 }
 
 
-void GCMarker::DrainMarkingStack(Isolate* isolate,
-                                 MarkingVisitor* visitor) {
-  while (!visitor->marking_stack()->IsEmpty()) {
-    RawObject* raw_obj = visitor->marking_stack()->Pop();
-    visitor->VisitingOldObject(raw_obj);
-    const intptr_t class_id = raw_obj->GetClassId();
-    // Currently, classes are considered roots (see issue 18284), so at this
-    // point, they should all be marked.
-    ASSERT(isolate->class_table()->At(class_id)->IsMarked());
-    if (class_id != kWeakPropertyCid) {
-      marked_bytes_ += raw_obj->VisitPointers(visitor);
-    } else {
-      RawWeakProperty* raw_weak = reinterpret_cast<RawWeakProperty*>(raw_obj);
-      marked_bytes_ += raw_weak->Size();
-      visitor->ProcessWeakProperty(raw_weak);
-    }
-  }
-  visitor->VisitingOldObject(NULL);
-}
-
-
 void GCMarker::ProcessWeakTables(PageSpace* page_space) {
   for (int sel = 0;
        sel < Heap::kNumWeakSelectors;
        sel++) {
     WeakTable* table = heap_->GetWeakTable(
         Heap::kOld, static_cast<Heap::WeakSelector>(sel));
     intptr_t size = table->size();
     for (intptr_t i = 0; i < size; i++) {
       if (table->IsValidEntryAt(i)) {
         RawObject* raw_obj = table->ObjectAt(i);
@@ skipping 42 matching lines @@
   Prologue(isolate, invoke_api_callbacks);
   // The API prologue/epilogue may create/destroy zones, so we must not
   // depend on zone allocations surviving beyond the epilogue callback.
   {
     StackZone zone(isolate);
     MarkingStack marking_stack;
     DelaySet delay_set;
     MarkingVisitor mark(isolate, heap_, page_space, &marking_stack,
                         &delay_set, visit_function_code);
     IterateRoots(isolate, &mark, !invoke_api_callbacks);
-    DrainMarkingStack(isolate, &mark);
+    mark.DrainMarkingStack();
     IterateWeakReferences(isolate, &mark);
     MarkingWeakVisitor mark_weak;
     IterateWeakRoots(isolate, &mark_weak, invoke_api_callbacks);
+    // TODO(koda): Add hand-over callback and centralize skipped code functions.
+    marked_bytes_ = mark.marked_bytes();
     mark.Finalize();
     delay_set.ClearReferences();
     ProcessWeakTables(page_space);
     ProcessObjectIdTable(isolate);
   }
   Epilogue(isolate, invoke_api_callbacks);
 }
 
 }  // namespace dart