Make the marking stack into a deque

src/mark-compact.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 1160 matching lines @@
   // Iterate the archived stacks in all threads to check if
   // the code is referenced.
   CodeMarkingVisitor code_marking_visitor(this);
   heap_->isolate()->thread_manager()->IterateArchivedThreads(
       &code_marking_visitor);
 
   SharedFunctionInfoMarkingVisitor visitor(this);
   heap_->isolate()->compilation_cache()->IterateFunctions(&visitor);
   heap_->isolate()->handle_scope_implementer()->Iterate(&visitor);
 
-  ProcessMarkingStack();
+  ProcessMarkingDeque();
 }
 
 
 // Visitor class for marking heap roots.
 class RootMarkingVisitor : public ObjectVisitor {
  public:
   explicit RootMarkingVisitor(Heap* heap)
     : collector_(heap->mark_compact_collector()) { }
 
   void VisitPointer(Object** p) {
@@ skipping 18 matching lines @@
     // Mark the object.
     HEAP->mark_compact_collector()->SetMark(object, mark_bit);
 
     // Mark the map pointer and body, and push them on the marking stack.
     MarkBit map_mark = Marking::MarkBitFromOldSpace(map);
     HEAP->mark_compact_collector()->MarkObject(map, map_mark);
     StaticMarkingVisitor::IterateBody(map, object);
 
     // Mark all the objects reachable from the map and body.  May leave
     // overflowed objects in the heap.
-    collector_->EmptyMarkingStack();
+    collector_->EmptyMarkingDeque();
   }
 
   MarkCompactCollector* collector_;
 };
 
 
 // Helper class for pruning the symbol table.
 class SymbolTableCleaner : public ObjectVisitor {
  public:
   SymbolTableCleaner() : pointers_removed_(0) { }
@@ skipping 49 matching lines @@
   if (object->IsMap()) {
     Map* map = Map::cast(object);
     if (FLAG_cleanup_caches_in_maps_at_gc) {
       map->ClearCodeCache(heap_);
     }
     if (FLAG_collect_maps &&
         map->instance_type() >= FIRST_JS_OBJECT_TYPE &&
         map->instance_type() <= JS_FUNCTION_TYPE) {
       MarkMapContents(map);
     } else {
-      marking_stack_.Push(map);
+      marking_deque_.Push(map);
     }
   } else {
-    marking_stack_.Push(object);
+    marking_deque_.Push(object);
   }
 }
 
 
 void MarkCompactCollector::MarkMapContents(Map* map) {
   MarkDescriptorArray(reinterpret_cast<DescriptorArray*>(
       *HeapObject::RawField(map, Map::kInstanceDescriptorsOffset)));
 
   // Mark the Object* fields of the Map.
   // Since the descriptor array has been marked already, it is fine
@@ skipping 34 matching lines @@
     // If the pair (value, details) at index i, i+1 is not
     // a transition or null descriptor, mark the value.
     PropertyDetails details(Smi::cast(contents->get(i + 1)));
     if (details.type() < FIRST_PHANTOM_PROPERTY_TYPE) {
       HeapObject* object = reinterpret_cast<HeapObject*>(contents->get(i));
       if (object->IsHeapObject()) {
         // TODO(gc) ISOLATES MERGE
         MarkBit mark = HEAP->marking()->MarkBitFrom(HeapObject::cast(object));
         if (!mark.Get()) {
           SetMark(HeapObject::cast(object), mark);
-          marking_stack_.Push(object);
+          marking_deque_.Push(object);
         }
       }
     }
   }
   // The DescriptorArray descriptors contains a pointer to its contents array,
   // but the contents array is already marked.
-  marking_stack_.Push(descriptors);
+  marking_deque_.Push(descriptors);
 }
 
 
 void MarkCompactCollector::CreateBackPointers() {
   HeapObjectIterator iterator(HEAP->map_space());
   for (HeapObject* next_object = iterator.Next();
        next_object != NULL; next_object = iterator.Next()) {
     if (next_object->IsMap()) {  // Could also be FreeSpace object on free list.
       Map* map = Map::cast(next_object);
       if (map->instance_type() >= FIRST_JS_OBJECT_TYPE &&
@@ skipping 17 matching lines @@
 
 
 // Fill the marking stack with overflowed objects returned by the given
 // iterator.  Stop when the marking stack is filled or the end of the space
 // is reached, whichever comes first.
 template<class T>
 static void ScanOverflowedObjects(T* it) {
 #if 0
   // The caller should ensure that the marking stack is initially not full,
   // so that we don't waste effort pointlessly scanning for objects.
-  ASSERT(!marking_stack.is_full());
+  ASSERT(!marking_deque.is_full());
 
   for (HeapObject* object = it->next(); object != NULL; object = it->next()) {
     if (object->IsOverflowed()) {
       object->ClearOverflow();
       ASSERT(HEAP->mark_compact_collector()->IsMarked(object));
       ASSERT(HEAP->Contains(object));
-      marking_stack.Push(object);
-      if (marking_stack.is_full()) return;
+      marking_deque.Push(object);
+      if (marking_deque.is_full()) return;
     }
   }
 #endif
   UNREACHABLE();
 }
 
 
 bool MarkCompactCollector::IsUnmarkedHeapObject(Object** p) {
   Object* o = *p;
   if (!o->IsHeapObject()) return false;
   HeapObject* heap_object = HeapObject::cast(o);
   // TODO(gc) ISOLATES MERGE
   MarkBit mark = HEAP->marking()->MarkBitFrom(heap_object);
   return !mark.Get();
 }
 
 
 void MarkCompactCollector::MarkSymbolTable() {
   SymbolTable* symbol_table = heap_->raw_unchecked_symbol_table();
   // Mark the symbol table itself.
   MarkBit symbol_table_mark = heap_->marking()->MarkBitFrom(symbol_table);
   SetMark(symbol_table, symbol_table_mark);
   // Explicitly mark the prefix.
   MarkingVisitor marker(heap_);
   symbol_table->IteratePrefix(&marker);
-  ProcessMarkingStack();
+  ProcessMarkingDeque();
 }
 
 
 void MarkCompactCollector::MarkRoots(RootMarkingVisitor* visitor) {
   // Mark the heap roots including global variables, stack variables,
   // etc., and all objects reachable from them.
   HEAP->IterateStrongRoots(visitor, VISIT_ONLY_STRONG);
 
   // Handle the symbol table specially.
   MarkSymbolTable();
 
   // There may be overflowed objects in the heap.  Visit them now.
-  while (marking_stack_.overflowed()) {
-    RefillMarkingStack();
-    EmptyMarkingStack();
+  while (marking_deque_.overflowed()) {
+    RefillMarkingDeque();
+    EmptyMarkingDeque();
   }
 }
 
 
 void MarkCompactCollector::MarkObjectGroups() {
   List<ObjectGroup*>* object_groups =
       heap_->isolate()->global_handles()->object_groups();
 
   for (int i = 0; i < object_groups->length(); i++) {
     ObjectGroup* entry = object_groups->at(i);
@@ skipping 60 matching lines @@
     delete entry;
     ref_groups->at(i) = NULL;
   }
 }
 
 
 // Mark all objects reachable from the objects on the marking stack.
 // Before: the marking stack contains zero or more heap object pointers.
 // After: the marking stack is empty, and all objects reachable from the
 // marking stack have been marked, or are overflowed in the heap.
-void MarkCompactCollector::EmptyMarkingStack() {
-  while (!marking_stack_.is_empty()) {
-    HeapObject* object = marking_stack_.Pop();
+void MarkCompactCollector::EmptyMarkingDeque() {
+  while (!marking_deque_.IsEmpty()) {
+    HeapObject* object = marking_deque_.Pop();
     ASSERT(object->IsHeapObject());
     ASSERT(heap_->Contains(object));
     ASSERT(IsMarked(object));
     ASSERT(!object->IsOverflowed());
 
     Map* map = object->map();
     MarkBit map_mark = Marking::MarkBitFromOldSpace(map);
     MarkObject(map, map_mark);
 
     StaticMarkingVisitor::IterateBody(map, object);
   }
 }
 
 
 // Sweep the heap for overflowed objects, clear their overflow bits, and
 // push them on the marking stack.  Stop early if the marking stack fills
 // before sweeping completes.  If sweeping completes, there are no remaining
 // overflowed objects in the heap so the overflow flag on the markings stack
 // is cleared.
-void MarkCompactCollector::RefillMarkingStack() {
+void MarkCompactCollector::RefillMarkingDeque() {
   UNREACHABLE();
 
 #if 0
-  ASSERT(marking_stack_.overflowed());
+  ASSERT(marking_deque_.overflowed());
 
   SemiSpaceIterator new_it(HEAP->new_space(), &OverflowObjectSize);
   OverflowedObjectsScanner::ScanOverflowedObjects(this, &new_it);
-  if (marking_stack_.is_full()) return;
+  if (marking_deque_.is_full()) return;
 
   HeapObjectIterator old_pointer_it(HEAP->old_pointer_space(),
                                     &OverflowObjectSize);
   OverflowedObjectsScanner::ScanOverflowedObjects(this, &old_pointer_it);
-  if (marking_stack_.is_full()) return;
+  if (marking_deque_.is_full()) return;
 
   HeapObjectIterator old_data_it(HEAP->old_data_space(), &OverflowObjectSize);
   OverflowedObjectsScanner::ScanOverflowedObjects(this, &old_data_it);
-  if (marking_stack_.is_full()) return;
+  if (marking_deque_.is_full()) return;
 
   HeapObjectIterator code_it(HEAP->code_space(), &OverflowObjectSize);
   OverflowedObjectsScanner::ScanOverflowedObjects(this, &code_it);
-  if (marking_stack_.is_full()) return;
+  if (marking_deque_.is_full()) return;
 
   HeapObjectIterator map_it(HEAP->map_space(), &OverflowObjectSize);
   OverflowedObjectsScanner::ScanOverflowedObjects(this, &map_it);
-  if (marking_stack_.is_full()) return;
+  if (marking_deque_.is_full()) return;
 
   HeapObjectIterator cell_it(HEAP->cell_space(), &OverflowObjectSize);
   OverflowedObjectsScanner::ScanOverflowedObjects(this, &cell_it);
-  if (marking_stack_.is_full()) return;
+  if (marking_deque_.is_full()) return;
 
   LargeObjectIterator lo_it(HEAP->lo_space(), &OverflowObjectSize);
   OverflowedObjectsScanner::ScanOverflowedObjects(this, &lo_it);
-  if (marking_stack_.is_full()) return;
+  if (marking_deque_.is_full()) return;
 
-  marking_stack_.clear_overflowed();
+  marking_deque_.clear_overflowed();
 #endif
 }
 
 
 // Mark all objects reachable (transitively) from objects on the marking
 // stack.  Before: the marking stack contains zero or more heap object
 // pointers.  After: the marking stack is empty and there are no overflowed
 // objects in the heap.
-void MarkCompactCollector::ProcessMarkingStack() {
-  EmptyMarkingStack();
-  while (marking_stack_.overflowed()) {
-    RefillMarkingStack();
-    EmptyMarkingStack();
+void MarkCompactCollector::ProcessMarkingDeque() {
+  EmptyMarkingDeque();
+  while (marking_deque_.overflowed()) {
+    RefillMarkingDeque();
+    EmptyMarkingDeque();
   }
 }
 
 
 void MarkCompactCollector::ProcessExternalMarking() {
   bool work_to_do = true;
-  ASSERT(marking_stack_.is_empty());
+  ASSERT(marking_deque_.IsEmpty());
   while (work_to_do) {
     MarkObjectGroups();
     MarkImplicitRefGroups();
-    work_to_do = !marking_stack_.is_empty();
-    ProcessMarkingStack();
+    work_to_do = !marking_deque_.IsEmpty();
+    ProcessMarkingDeque();
   }
 }
 
 
 void MarkCompactCollector::MarkLiveObjects() {
   GCTracer::Scope gc_scope(tracer_, GCTracer::Scope::MC_MARK);
   // The recursive GC marker detects when it is nearing stack overflow,
   // and switches to a different marking system.  JS interrupts interfere
   // with the C stack limit check.
   PostponeInterruptsScope postpone(heap_->isolate());
 
 #ifdef DEBUG
   ASSERT(state_ == PREPARE_GC);
   state_ = MARK_LIVE_OBJECTS;
 #endif
   // The to space contains live objects, the from space is used as a marking
   // stack.
-  marking_stack_.Initialize(heap_->new_space()->FromSpaceLow(),
+  marking_deque_.Initialize(heap_->new_space()->FromSpaceLow(),
                             heap_->new_space()->FromSpaceHigh());
 
-  ASSERT(!marking_stack_.overflowed());
+  ASSERT(!marking_deque_.overflowed());
 
   PrepareForCodeFlushing();
 
   RootMarkingVisitor root_visitor(heap_);
   MarkRoots(&root_visitor);
 
   // The objects reachable from the roots are marked, yet unreachable
   // objects are unmarked.  Mark objects reachable due to host
   // application specific logic.
   ProcessExternalMarking();
 
   // The objects reachable from the roots or object groups are marked,
   // yet unreachable objects are unmarked.  Mark objects reachable
   // only from weak global handles.
   //
   // First we identify nonlive weak handles and mark them as pending
   // destruction.
   heap_->isolate()->global_handles()->IdentifyWeakHandles(
       &IsUnmarkedHeapObject);
   // Then we mark the objects and process the transitive closure.
   heap_->isolate()->global_handles()->IterateWeakRoots(&root_visitor);
-  while (marking_stack_.overflowed()) {
-    RefillMarkingStack();
-    EmptyMarkingStack();
+  while (marking_deque_.overflowed()) {
+    RefillMarkingDeque();
+    EmptyMarkingDeque();
   }
 
   // Repeat host application specific marking to mark unmarked objects
   // reachable from the weak roots.
   ProcessExternalMarking();
 
   AfterMarking();
 }
 
 
@@ skipping 994 matching lines @@
 }
 
 
 void MarkCompactCollector::Initialize() {
   StaticPointersToNewGenUpdatingVisitor::Initialize();
   StaticMarkingVisitor::Initialize();
 }
 
 
 } }  // namespace v8::internal