Allow partial scanning of large arrays in order to avoid

src/mark-compact.cc

 // Copyright 2012 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 1035 matching lines @@
    public:
     static inline void Visit(Map* map, HeapObject* obj);
   };
 
   static void Initialize();
 
   INLINE(static void VisitPointer(Heap* heap, Object** p)) {
     MarkObjectByPointer(heap->mark_compact_collector(), p, p);
   }
 
-  INLINE(static void VisitPointers(Heap* heap, Object** start, Object** end)) {
+  INLINE(static void VisitPointers(Heap* heap,
+                                   Object** anchor,
+                                   Object** start,
+                                   Object** end)) {
     // Mark all objects pointed to in [start, end).
     const int kMinRangeForMarkingRecursion = 64;
     if (end - start >= kMinRangeForMarkingRecursion) {
-      if (VisitUnmarkedObjects(heap, start, end)) return;
+      if (VisitUnmarkedObjects(heap, anchor, start, end)) return;
       // We are close to a stack overflow, so just mark the objects.
     }
     MarkCompactCollector* collector = heap->mark_compact_collector();
     for (Object** p = start; p < end; p++) {
-      MarkObjectByPointer(collector, start, p);
+      MarkObjectByPointer(collector, anchor, p);
+    }
+  }
+
+  static void VisitHugeFixedArray(Heap* heap, FixedArray* array, int length);
+
+  // The deque is contiguous and we use new space, it is therefore contained in
+  // one page minus the header.  It also has a size that is a power of two so
+  // it is half the size of a page.  We want to scan a number of array entries
+  // that is less than the number of entries in the deque, so we divide by 2
+  // once more.
+  static const int kScanningChunk = Page::kPageSize / 4 / kPointerSize;
+
+  INLINE(static void VisitFixedArray(Map* map, HeapObject* object)) {
+    FixedArray* array = FixedArray::cast(object);
+    int length = array->length();
+    Heap* heap = map->GetHeap();
+
+    if (length < kScanningChunk ||
+        MemoryChunk::FromAddress(array->address())->owner()->identity() !=
+            LO_SPACE) {
+      Object** start_slot = array->data_start();
+      VisitPointers(heap, start_slot, start_slot, start_slot + length);
+    } else {
+      VisitHugeFixedArray(heap, array, length);
     }
   }
 
   // Marks the object black and pushes it on the marking stack.
   INLINE(static void MarkObject(Heap* heap, HeapObject* object)) {
     MarkBit mark = Marking::MarkBitFrom(object);
     heap->mark_compact_collector()->MarkObject(object, mark);
   }
 
   // Marks the object black without pushing it on the marking stack.
@@ skipping 29 matching lines @@
     Map* map = obj->map();
     Heap* heap = obj->GetHeap();
     MarkBit mark = Marking::MarkBitFrom(obj);
     heap->mark_compact_collector()->SetMark(obj, mark);
     // Mark the map pointer and the body.
     MarkBit map_mark = Marking::MarkBitFrom(map);
     heap->mark_compact_collector()->MarkObject(map, map_mark);
     IterateBody(map, obj);
   }
 
-  // Visit all unmarked objects pointed to by [start, end).
+  // Visit all unmarked objects pointed to by [start_slot, end_slot).
   // Returns false if the operation fails (lack of stack space).
   static inline bool VisitUnmarkedObjects(Heap* heap,
-                                          Object** start,
-                                          Object** end) {
+                                          Object** anchor_slot,
+                                          Object** start_slot,
+                                          Object** end_slot) {
     // Return false is we are close to the stack limit.
     StackLimitCheck check(heap->isolate());
     if (check.HasOverflowed()) return false;
 
     MarkCompactCollector* collector = heap->mark_compact_collector();
     // Visit the unmarked objects.
-    for (Object** p = start; p < end; p++) {
+    for (Object** p = start_slot; p < end_slot; p++) {
       Object* o = *p;
       if (!o->IsHeapObject()) continue;
-      collector->RecordSlot(start, p, o);
+      collector->RecordSlot(anchor_slot, p, o);
       HeapObject* obj = HeapObject::cast(o);
       MarkBit mark = Marking::MarkBitFrom(obj);
       if (mark.Get()) continue;
       VisitUnmarkedObject(collector, obj);
     }
     return true;
   }
 
   static void VisitJSWeakMap(Map* map, HeapObject* object) {
     MarkCompactCollector* collector = map->GetHeap()->mark_compact_collector();
@@ skipping 300 matching lines @@
                           reinterpret_cast<JSFunction*>(object),
                           false);
   }
 
 
   static inline void VisitJSFunctionFields(Map* map,
                                            JSFunction* object,
                                            bool flush_code_candidate) {
     Heap* heap = map->GetHeap();
 
-    VisitPointers(heap,
-                  HeapObject::RawField(object, JSFunction::kPropertiesOffset),
-                  HeapObject::RawField(object, JSFunction::kCodeEntryOffset));
+    Object** start_slot =
+        HeapObject::RawField(object, JSFunction::kPropertiesOffset);
+    Object** end_slot =
+        HeapObject::RawField(object, JSFunction::kCodeEntryOffset);
+    VisitPointers(heap, start_slot, start_slot, end_slot);
 
     if (!flush_code_candidate) {
       VisitCodeEntry(heap, object->address() + JSFunction::kCodeEntryOffset);
     } else {
       // Don't visit code object.
 
       // Visit shared function info to avoid double checking of its
       // flushability.
       SharedFunctionInfo* shared_info = object->unchecked_shared();
       MarkBit shared_info_mark = Marking::MarkBitFrom(shared_info);
       if (!shared_info_mark.Get()) {
         Map* shared_info_map = shared_info->map();
         MarkBit shared_info_map_mark =
             Marking::MarkBitFrom(shared_info_map);
         heap->mark_compact_collector()->SetMark(shared_info, shared_info_mark);
         heap->mark_compact_collector()->MarkObject(shared_info_map,
                                                    shared_info_map_mark);
         VisitSharedFunctionInfoAndFlushCodeGeneric(shared_info_map,
                                                    shared_info,
                                                    true);
       }
     }
 
-    VisitPointers(
-        heap,
+    start_slot =
         HeapObject::RawField(object,
-                             JSFunction::kCodeEntryOffset + kPointerSize),
-        HeapObject::RawField(object, JSFunction::kNonWeakFieldsEndOffset));
+                             JSFunction::kCodeEntryOffset + kPointerSize);
+    end_slot =
+        HeapObject::RawField(object, JSFunction::kNonWeakFieldsEndOffset);
+    VisitPointers(heap, start_slot, start_slot, end_slot);
   }
 
 
   static void VisitSharedFunctionInfoFields(Heap* heap,
                                             HeapObject* object,
                                             bool flush_code_candidate) {
     VisitPointer(heap,
                  HeapObject::RawField(object, SharedFunctionInfo::kNameOffset));
 
     if (!flush_code_candidate) {
       VisitPointer(heap,
                    HeapObject::RawField(object,
                                         SharedFunctionInfo::kCodeOffset));
     }
 
-    VisitPointers(
-        heap,
+    Object** start_slot =
         HeapObject::RawField(object,
-                             SharedFunctionInfo::kOptimizedCodeMapOffset),
-        HeapObject::RawField(object, SharedFunctionInfo::kSize));
+                             SharedFunctionInfo::kOptimizedCodeMapOffset);
+    Object** end_slot =
+        HeapObject::RawField(object, SharedFunctionInfo::kSize);
+
+    VisitPointers(heap, start_slot, start_slot, end_slot);
   }
 
   static VisitorDispatchTable<Callback> non_count_table_;
 };
 
 
+void MarkCompactMarkingVisitor::VisitHugeFixedArray(Heap* heap,
+                                                    FixedArray* array,
+                                                    int length) {
+  MemoryChunk* chunk = MemoryChunk::FromAddress(array->address());
+
+  ASSERT(chunk->owner()->identity() == LO_SPACE);
+
+  Object** start_slot = array->data_start();
+  int from =
+      chunk->IsPartiallyScanned() ? chunk->PartiallyScannedProgress() : 0;
+  int to = Min(from + kScanningChunk, length);
+  VisitPointers(heap, start_slot, start_slot + from, start_slot + to);
+
+  if (to == length) {
+    chunk->SetCompletelyScanned();
+  } else {
+    chunk->SetPartiallyScannedProgress(to);
+  }
+}
+
+
 void MarkCompactMarkingVisitor::ObjectStatsCountFixedArray(
     FixedArrayBase* fixed_array,
     FixedArraySubInstanceType fast_type,
     FixedArraySubInstanceType dictionary_type) {
   Heap* heap = fixed_array->map()->GetHeap();
   if (fixed_array->map() != heap->fixed_cow_array_map() &&
       fixed_array->map() != heap->fixed_double_array_map() &&
       fixed_array != heap->empty_fixed_array()) {
     if (fixed_array->IsDictionary()) {
       heap->RecordObjectStats(FIXED_ARRAY_TYPE,
@@ skipping 121 matching lines @@
 
   table_.Register(kVisitSharedFunctionInfo,
                   &VisitSharedFunctionInfoAndFlushCode);
 
   table_.Register(kVisitJSFunction,
                   &VisitJSFunctionAndFlushCode);
 
   table_.Register(kVisitJSRegExp,
                   &VisitRegExpAndFlushCode);
 
+  table_.Register(kVisitFixedArray,
+                  &VisitFixedArray);
+
   if (FLAG_track_gc_object_stats) {
     // Copy the visitor table to make call-through possible.
     non_count_table_.CopyFrom(&table_);
 #define VISITOR_ID_COUNT_FUNCTION(id)                                   \
     table_.Register(kVisit##id, ObjectStatsTracker<kVisit##id>::Visit);
     VISITOR_ID_LIST(VISITOR_ID_COUNT_FUNCTION)
 #undef VISITOR_ID_COUNT_FUNCTION
   }
 }
 
 
 VisitorDispatchTable<MarkCompactMarkingVisitor::Callback>
     MarkCompactMarkingVisitor::non_count_table_;
 
 
 class MarkingVisitor : public ObjectVisitor {
  public:
   explicit MarkingVisitor(Heap* heap) : heap_(heap) { }
 
   void VisitPointer(Object** p) {
     MarkCompactMarkingVisitor::VisitPointer(heap_, p);
   }
 
-  void VisitPointers(Object** start, Object** end) {
-    MarkCompactMarkingVisitor::VisitPointers(heap_, start, end);
+  void VisitPointers(Object** start_slot, Object** end_slot) {
+    MarkCompactMarkingVisitor::VisitPointers(
+        heap_, start_slot, start_slot, end_slot);
   }
 
  private:
   Heap* heap_;
 };
 
 
 class CodeMarkingVisitor : public ThreadVisitor {
  public:
   explicit CodeMarkingVisitor(MarkCompactCollector* collector)
       : collector_(collector) {}
 
   void VisitThread(Isolate* isolate, ThreadLocalTop* top) {
     collector_->PrepareThreadForCodeFlushing(isolate, top);
   }
 
  private:
   MarkCompactCollector* collector_;
 };
 
 
 class SharedFunctionInfoMarkingVisitor : public ObjectVisitor {
  public:
   explicit SharedFunctionInfoMarkingVisitor(MarkCompactCollector* collector)
       : collector_(collector) {}
 
-  void VisitPointers(Object** start, Object** end) {
-    for (Object** p = start; p < end; p++) VisitPointer(p);
+  void VisitPointers(Object** start_slot, Object** end_slot) {
+    for (Object** p = start_slot; p < end_slot; p++) VisitPointer(p);
   }
 
   void VisitPointer(Object** slot) {
     Object* obj = *slot;
     if (obj->IsSharedFunctionInfo()) {
       SharedFunctionInfo* shared = reinterpret_cast<SharedFunctionInfo*>(obj);
       MarkBit shared_mark = Marking::MarkBitFrom(shared);
       MarkBit code_mark = Marking::MarkBitFrom(shared->code());
       collector_->MarkObject(shared->code(), code_mark);
       collector_->MarkObject(shared, shared_mark);
@@ skipping 90 matching lines @@
 // Visitor class for marking heap roots.
 class RootMarkingVisitor : public ObjectVisitor {
  public:
   explicit RootMarkingVisitor(Heap* heap)
     : collector_(heap->mark_compact_collector()) { }
 
   void VisitPointer(Object** p) {
     MarkObjectByPointer(p);
   }
 
-  void VisitPointers(Object** start, Object** end) {
-    for (Object** p = start; p < end; p++) MarkObjectByPointer(p);
+  void VisitPointers(Object** start_slot, Object** end_slot) {
+    for (Object** p = start_slot; p < end_slot; p++) MarkObjectByPointer(p);
   }
 
  private:
   void MarkObjectByPointer(Object** p) {
     if (!(*p)->IsHeapObject()) return;
 
     // Replace flat cons strings in place.
     HeapObject* object = ShortCircuitConsString(p);
     MarkBit mark_bit = Marking::MarkBitFrom(object);
     if (mark_bit.Get()) return;
@@ skipping 15 matching lines @@
   MarkCompactCollector* collector_;
 };
 
 
 // Helper class for pruning the symbol table.
 class SymbolTableCleaner : public ObjectVisitor {
  public:
   explicit SymbolTableCleaner(Heap* heap)
     : heap_(heap), pointers_removed_(0) { }
 
-  virtual void VisitPointers(Object** start, Object** end) {
-    // Visit all HeapObject pointers in [start, end).
-    for (Object** p = start; p < end; p++) {
+  virtual void VisitPointers(Object** start_slot, Object** end_slot) {
+    // Visit all HeapObject pointers in [start_slot, end_slot).
+    for (Object** p = start_slot; p < end_slot; p++) {
       Object* o = *p;
       if (o->IsHeapObject() &&
           !Marking::MarkBitFrom(HeapObject::cast(o)).Get()) {
         // Check if the symbol being pruned is an external symbol. We need to
         // delete the associated external data as this symbol is going away.
 
         // Since no objects have yet been moved we can safely access the map of
         // the object.
         if (o->IsExternalString()) {
           heap_->FinalizeExternalString(String::cast(*p));
@@ skipping 260 matching lines @@
       ASSERT(object->IsHeapObject());
       ASSERT(heap()->Contains(object));
       ASSERT(Marking::IsBlack(Marking::MarkBitFrom(object)));
 
       Map* map = object->map();
       MarkBit map_mark = Marking::MarkBitFrom(map);
       MarkObject(map, map_mark);
 
       MarkCompactMarkingVisitor::IterateBody(map, object);
     }
+    ProcessLargePostponedArrays(heap(), &marking_deque_);
 
     // Process encountered weak maps, mark objects only reachable by those
     // weak maps and repeat until fix-point is reached.
     ProcessWeakMaps();
   }
 }
 
 
+void MarkCompactCollector::ProcessLargePostponedArrays(Heap* heap,
+                                                       MarkingDeque* deque) {
+  ASSERT(deque->IsEmpty());
+  LargeObjectIterator it(heap->lo_space());
+  for (HeapObject* obj = it.Next(); obj != NULL; obj = it.Next()) {
+    if (!obj->IsFixedArray()) continue;
+    MemoryChunk* p = MemoryChunk::FromAddress(obj->address());
+    if (p->IsPartiallyScanned()) {
+      deque->PushBlack(obj);
+    }
+  }
+}
+
+
 // 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::RefillMarkingDeque() {
+  if (FLAG_trace_gc) {
+    PrintPID("Marking queue overflowed\n");
+  }
   ASSERT(marking_deque_.overflowed());
 
   SemiSpaceIterator new_it(heap()->new_space());
   DiscoverGreyObjectsWithIterator(heap(), &marking_deque_, &new_it);
   if (marking_deque_.IsFull()) return;
 
   DiscoverGreyObjectsInSpace(heap(),
                              &marking_deque_,
                              heap()->old_pointer_space());
   if (marking_deque_.IsFull()) return;
@@ skipping 470 matching lines @@
 // Visitor for updating pointers from live objects in old spaces to new space.
 // It does not expect to encounter pointers to dead objects.
 class PointersUpdatingVisitor: public ObjectVisitor {
  public:
   explicit PointersUpdatingVisitor(Heap* heap) : heap_(heap) { }
 
   void VisitPointer(Object** p) {
     UpdatePointer(p);
   }
 
-  void VisitPointers(Object** start, Object** end) {
-    for (Object** p = start; p < end; p++) UpdatePointer(p);
+  void VisitPointers(Object** start_slot, Object** end_slot) {
+    for (Object** p = start_slot; p < end_slot; p++) UpdatePointer(p);
   }
 
   void VisitEmbeddedPointer(RelocInfo* rinfo) {
     ASSERT(rinfo->rmode() == RelocInfo::EMBEDDED_OBJECT);
     Object* target = rinfo->target_object();
     VisitPointer(&target);
     rinfo->set_target_object(target);
   }
 
   void VisitCodeTarget(RelocInfo* rinfo) {
@@ skipping 1418 matching lines @@
   while (buffer != NULL) {
     SlotsBuffer* next_buffer = buffer->next();
     DeallocateBuffer(buffer);
     buffer = next_buffer;
   }
   *buffer_address = NULL;
 }
 
 
 } }  // namespace v8::internal