Implement map collection for incremental marking.

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 46 matching lines @@
 
 MarkCompactCollector::MarkCompactCollector() :  // NOLINT
 #ifdef DEBUG
       state_(IDLE),
 #endif
       sweep_precisely_(false),
       reduce_memory_footprint_(false),
       abort_incremental_marking_(false),
       compacting_(false),
       was_marked_incrementally_(false),
-      collect_maps_(FLAG_collect_maps),
       flush_monomorphic_ics_(false),
       tracer_(NULL),
       migration_slots_buffer_(NULL),
       heap_(NULL),
       code_flusher_(NULL),
-      encountered_weak_maps_(NULL) { }
+      encountered_weak_maps_(NULL),
+      marker_(this, this) { }
 
 
 #ifdef DEBUG
 class VerifyMarkingVisitor: public ObjectVisitor {
  public:
   void VisitPointers(Object** start, Object** end) {
     for (Object** current = start; current < end; current++) {
       if ((*current)->IsHeapObject()) {
         HeapObject* object = HeapObject::cast(*current);
         ASSERT(HEAP->mark_compact_collector()->IsMarked(object));
@@ skipping 191 matching lines @@
 
 void MarkCompactCollector::CollectGarbage() {
   // Make sure that Prepare() has been called. The individual steps below will
   // update the state as they proceed.
   ASSERT(state_ == PREPARE_GC);
   ASSERT(encountered_weak_maps_ == Smi::FromInt(0));
 
   MarkLiveObjects();
   ASSERT(heap_->incremental_marking()->IsStopped());
 
-  if (collect_maps_) ClearNonLiveTransitions();
+  if (FLAG_collect_maps) ClearNonLiveTransitions();
 
   ClearWeakMaps();
 
 #ifdef DEBUG
   if (FLAG_verify_heap) {
     VerifyMarking(heap_);
   }
 #endif
 
   SweepSpaces();
 
-  if (!collect_maps_) ReattachInitialMaps();
+  if (!FLAG_collect_maps) ReattachInitialMaps();
 
   Finish();
 
   tracer_ = NULL;
 }
 
 
 #ifdef DEBUG
 void MarkCompactCollector::VerifyMarkbitsAreClean(PagedSpace* space) {
   PageIterator it(space);
@@ skipping 343 matching lines @@
     evacuation_candidates_.Rewind(0);
     invalidated_code_.Rewind(0);
   }
   ASSERT_EQ(0, evacuation_candidates_.length());
 }
 
 
 void MarkCompactCollector::Prepare(GCTracer* tracer) {
   was_marked_incrementally_ = heap()->incremental_marking()->IsMarking();
 
-  // Disable collection of maps if incremental marking is enabled.
-  // Map collection algorithm relies on a special map transition tree traversal
-  // order which is not implemented for incremental marking.
-  collect_maps_ = FLAG_collect_maps && !was_marked_incrementally_;
-
   // Monomorphic ICs are preserved when possible, but need to be flushed
   // when they might be keeping a Context alive, or when the heap is about
   // to be serialized.
   flush_monomorphic_ics_ =
       heap()->isolate()->context_exit_happened() || Serializer::enabled();
 
   // Rather than passing the tracer around we stash it in a static member
   // variable.
   tracer_ = tracer;
 
@@ skipping 1115 matching lines @@
 
 
 void MarkCompactCollector::ProcessNewlyMarkedObject(HeapObject* object) {
   ASSERT(IsMarked(object));
   ASSERT(HEAP->Contains(object));
   if (object->IsMap()) {
     Map* map = Map::cast(object);
     heap_->ClearCacheOnMap(map);
 
     // When map collection is enabled we have to mark through map's transitions
-    // in a special way to make transition links weak.
-    // Only maps for subclasses of JSReceiver can have transitions.
+    // in a special way to make transition links weak. Only maps for subclasses
+    // of JSReceiver can have transitions.
     STATIC_ASSERT(LAST_TYPE == LAST_JS_RECEIVER_TYPE);
-    if (collect_maps_ && map->instance_type() >= FIRST_JS_RECEIVER_TYPE) {
-      MarkMapContents(map);
+    if (FLAG_collect_maps && map->instance_type() >= FIRST_JS_RECEIVER_TYPE) {
+      marker_.MarkMapContents(map);
     } else {
       marking_deque_.PushBlack(map);
     }
   } else {
     marking_deque_.PushBlack(object);
   }
 }
 
 
-void MarkCompactCollector::MarkMapContents(Map* map) {
+// Force instantiation of template instances.
+template void Marker<IncrementalMarking>::MarkMapContents(Map* map);
+template void Marker<MarkCompactCollector>::MarkMapContents(Map* map);
+
+
+template <class T>
+void Marker<T>::MarkMapContents(Map* map) {
   // Mark prototype transitions array but don't push it into marking stack.
   // This will make references from it weak. We will clean dead prototype
-  // transitions in ClearNonLiveTransitions. But make sure that back pointers
-  // stored inside prototype transitions arrays are marked.
-  Object* raw_proto_transitions = map->unchecked_prototype_transitions();
-  if (raw_proto_transitions->IsFixedArray()) {
-    FixedArray* prototype_transitions = FixedArray::cast(raw_proto_transitions);
+  // transitions in ClearNonLiveTransitions.
+  Object** proto_trans_slot =
+      HeapObject::RawField(map, Map::kPrototypeTransitionsOrBackPointerOffset);
+  HeapObject* prototype_transitions = HeapObject::cast(*proto_trans_slot);
+  if (prototype_transitions->IsFixedArray()) {
+    mark_compact_collector()->RecordSlot(proto_trans_slot,
+                                         proto_trans_slot,
+                                         prototype_transitions);
     MarkBit mark = Marking::MarkBitFrom(prototype_transitions);
     if (!mark.Get()) {
       mark.Set();
       MemoryChunk::IncrementLiveBytesFromGC(prototype_transitions->address(),
                                             prototype_transitions->Size());
-      MarkObjectAndPush(HeapObject::cast(
-          prototype_transitions->get(Map::kProtoTransitionBackPointerOffset)));
     }
   }
 
-  Object** raw_descriptor_array_slot =
+  // Make sure that the back pointer stored either in the map itself or inside
+  // its prototype transitions array is marked. Treat pointers in the descriptor
+  // array as weak and also mark that array to prevent visiting it later.
+  base_marker()->MarkObjectAndPush(HeapObject::cast(map->GetBackPointer()));
+
+  Object** descriptor_array_slot =
       HeapObject::RawField(map, Map::kInstanceDescriptorsOrBitField3Offset);
-  Object* raw_descriptor_array = *raw_descriptor_array_slot;
-  if (!raw_descriptor_array->IsSmi()) {
-    MarkDescriptorArray(
-        reinterpret_cast<DescriptorArray*>(raw_descriptor_array));
+  Object* descriptor_array = *descriptor_array_slot;
+  if (!descriptor_array->IsSmi()) {
+    MarkDescriptorArray(reinterpret_cast<DescriptorArray*>(descriptor_array));
   }
 
-  // Mark the Object* fields of the Map.
-  // Since the descriptor array has been marked already, it is fine
-  // that one of these fields contains a pointer to it.
-  Object** start_slot = HeapObject::RawField(map,
-                                             Map::kPointerFieldsBeginOffset);
-
-  Object** end_slot = HeapObject::RawField(map, Map::kPointerFieldsEndOffset);
-
-  StaticMarkingVisitor::VisitPointers(map->GetHeap(), start_slot, end_slot);
+  // Mark the Object* fields of the Map. Since the descriptor array has been
+  // marked already, it is fine that one of these fields contains a pointer
+  // to it. But make sure to skip back pointer and prototype transitions.
+  STATIC_ASSERT(Map::kPointerFieldsEndOffset ==
+      Map::kPrototypeTransitionsOrBackPointerOffset + kPointerSize);
+  Object** start_slot = HeapObject::RawField(
+      map, Map::kPointerFieldsBeginOffset);
+  Object** end_slot = HeapObject::RawField(
+      map, Map::kPrototypeTransitionsOrBackPointerOffset);
+  for (Object** slot = start_slot; slot < end_slot; slot++) {
+    Object* obj = *slot;
+    if (!obj->NonFailureIsHeapObject()) continue;
+    mark_compact_collector()->RecordSlot(start_slot, slot, obj);
+    base_marker()->MarkObjectAndPush(reinterpret_cast<HeapObject*>(obj));
+  }
 }
 
 
-void MarkCompactCollector::MarkAccessorPairSlot(HeapObject* accessors,
-                                                int offset) {
-  Object** slot = HeapObject::RawField(accessors, offset);
-  HeapObject* accessor = HeapObject::cast(*slot);
-  if (accessor->IsMap()) return;
-  RecordSlot(slot, slot, accessor);
-  MarkObjectAndPush(accessor);
-}
+template <class T>
+void Marker<T>::MarkDescriptorArray(DescriptorArray* descriptors) {
+  // Empty descriptor array is marked as a root before any maps are marked.
+  ASSERT(descriptors != descriptors->GetHeap()->empty_descriptor_array());
 
+  // The DescriptorArray contains a pointer to its contents array, but the
+  // contents array will be marked black and hence not be visited again.
+  if (!base_marker()->MarkObjectAndPush(descriptors)) return;
+  FixedArray* contents = FixedArray::cast(
+      descriptors->get(DescriptorArray::kContentArrayIndex));
+  ASSERT(contents->length() >= 2);
+  ASSERT(Marking::IsWhite(Marking::MarkBitFrom(contents)));
+  base_marker()->MarkObjectWithoutPush(contents);
 
-void MarkCompactCollector::MarkDescriptorArray(
-    DescriptorArray* descriptors) {
-  MarkBit descriptors_mark = Marking::MarkBitFrom(descriptors);
-  if (descriptors_mark.Get()) return;
-  // Empty descriptor array is marked as a root before any maps are marked.
-  ASSERT(descriptors != heap()->empty_descriptor_array());
-  SetMark(descriptors, descriptors_mark);
-
-  FixedArray* contents = reinterpret_cast<FixedArray*>(
-      descriptors->get(DescriptorArray::kContentArrayIndex));
-  ASSERT(contents->IsHeapObject());
-  ASSERT(!IsMarked(contents));
-  ASSERT(contents->IsFixedArray());
-  ASSERT(contents->length() >= 2);
-  MarkBit contents_mark = Marking::MarkBitFrom(contents);
-  SetMark(contents, contents_mark);
-  // Contents contains (value, details) pairs.  If the details say that the type
-  // of descriptor is MAP_TRANSITION, CONSTANT_TRANSITION,
-  // EXTERNAL_ARRAY_TRANSITION or NULL_DESCRIPTOR, we don't mark the value as
-  // live.  Only for MAP_TRANSITION, EXTERNAL_ARRAY_TRANSITION and
-  // CONSTANT_TRANSITION is the value an Object* (a Map*).
+  // Contents contains (value, details) pairs.  If the descriptor contains a
+  // transition (value is a Map), we don't mark the value as live.  It might
+  // be set to the NULL_DESCRIPTOR in ClearNonLiveTransitions later.
   for (int i = 0; i < contents->length(); i += 2) {
-    // 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)));
 
     Object** slot = contents->data_start() + i;
     if (!(*slot)->IsHeapObject()) continue;
     HeapObject* value = HeapObject::cast(*slot);
 
-    RecordSlot(slot, slot, *slot);
+    mark_compact_collector()->RecordSlot(slot, slot, *slot);
 
     switch (details.type()) {
       case NORMAL:
       case FIELD:
       case CONSTANT_FUNCTION:
       case HANDLER:
       case INTERCEPTOR:
-        MarkObjectAndPush(value);
+        base_marker()->MarkObjectAndPush(value);
         break;
       case CALLBACKS:
         if (!value->IsAccessorPair()) {
-          MarkObjectAndPush(value);
-        } else if (!MarkObjectWithoutPush(value)) {
-          MarkAccessorPairSlot(value, AccessorPair::kGetterOffset);
-          MarkAccessorPairSlot(value, AccessorPair::kSetterOffset);
+          base_marker()->MarkObjectAndPush(value);
+        } else if (base_marker()->MarkObjectWithoutPush(value)) {
+          AccessorPair* accessors = AccessorPair::cast(value);
+          MarkAccessorPairSlot(accessors, AccessorPair::kGetterOffset);
+          MarkAccessorPairSlot(accessors, AccessorPair::kSetterOffset);
         }
         break;
       case ELEMENTS_TRANSITION:
         // For maps with multiple elements transitions, the transition maps are
         // stored in a FixedArray. Keep the fixed array alive but not the maps
         // that it refers to.
-        if (value->IsFixedArray()) MarkObjectWithoutPush(value);
+        if (value->IsFixedArray()) base_marker()->MarkObjectWithoutPush(value);
         break;
       case MAP_TRANSITION:
       case CONSTANT_TRANSITION:
       case NULL_DESCRIPTOR:
         break;
     }
   }
-  // The DescriptorArray descriptors contains a pointer to its contents array,
-  // but the contents array is already marked.
-  marking_deque_.PushBlack(descriptors);
 }
 
 
+template <class T>
+void Marker<T>::MarkAccessorPairSlot(AccessorPair* accessors, int offset) {
+  Object** slot = HeapObject::RawField(accessors, offset);
+  HeapObject* accessor = HeapObject::cast(*slot);
+  if (accessor->IsMap()) return;
+  mark_compact_collector()->RecordSlot(slot, slot, accessor);
+  base_marker()->MarkObjectAndPush(accessor);
+}
+
+
 // 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 DiscoverGreyObjectsWithIterator(Heap* heap,
                                             MarkingDeque* marking_deque,
                                             T* it) {
   // 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_deque->IsFull());
@@ skipping 2157 matching lines @@
   while (buffer != NULL) {
     SlotsBuffer* next_buffer = buffer->next();
     DeallocateBuffer(buffer);
     buffer = next_buffer;
   }
   *buffer_address = NULL;
 }
 
 
 } }  // namespace v8::internal