Change the scavenging collector so that promoted objects do not reside...

src/heap.cc

 // Copyright 2009 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 519 matching lines @@
  private:
   void ScavengePointer(Object** p) {
     Object* object = *p;
     if (!Heap::InNewSpace(object)) return;
     Heap::ScavengeObject(reinterpret_cast<HeapObject**>(p),
                          reinterpret_cast<HeapObject*>(object));
   }
 };
 
 
+// A queue of pointers and maps of to-be-promoted objects during a
+// scavenge collection.
+class PromotionQueue {
+ public:
+  void Initialize(Address start_address) {
+    front_ = rear_ = reinterpret_cast<HeapObject**>(start_address);
+  }
+
+  bool is_empty() { return front_ <= rear_; }
+
+  void insert(HeapObject* object, Map* map) {
+    *(--rear_) = object;
+    *(--rear_) = map;
+    // Assert no overflow into live objects.
+    ASSERT(rear_ >= Heap::new_space()->top());
+  }
+
+  void remove(HeapObject** object, Map** map) {
+    *object = *(--front_);
+    *map = Map::cast(*(--front_));
+    // Assert no underflow.
+    ASSERT(front_ >= rear_);
+  }
+
+ private:
+  // The front of the queue is higher in memory than the rear.
+  HeapObject** front_;
+  HeapObject** rear_;
+};
+
+
 // Shared state read by the scavenge collector and set by ScavengeObject.
-static Address promoted_rear = NULL;
+static PromotionQueue promotion_queue;
 
 
 #ifdef DEBUG
 // Visitor class to verify pointers in code or data space do not point into
 // new space.
 class VerifyNonPointerSpacePointersVisitor: public ObjectVisitor {
  public:
   void VisitPointers(Object** start, Object**end) {
     for (Object** current = start; current < end; current++) {
       if ((*current)->IsHeapObject()) {
@@ skipping 65 matching lines @@
   // We treat the top of the to space as a queue of addresses of
   // promoted objects.  The addresses of newly promoted and unswept
   // objects lie between a 'front' mark and a 'rear' mark that is
   // updated as a side effect of promoting an object.
   //
   // There is guaranteed to be enough room at the top of the to space
   // for the addresses of promoted objects: every object promoted
   // frees up its size in bytes from the top of the new space, and
   // objects are at least one pointer in size.
   Address new_space_front = new_space_.ToSpaceLow();
-  Address promoted_front = new_space_.ToSpaceHigh();
-  promoted_rear = new_space_.ToSpaceHigh();
+  promotion_queue.Initialize(new_space_.ToSpaceHigh());
 
   ScavengeVisitor scavenge_visitor;
   // Copy roots.
   IterateRoots(&scavenge_visitor);
 
   // Copy objects reachable from weak pointers.
   GlobalHandles::IterateWeakRoots(&scavenge_visitor);
 
   // Copy objects reachable from the old generation.  By definition,
   // there are no intergenerational pointers in code or data spaces.
   IterateRSet(old_pointer_space_, &ScavengePointer);
   IterateRSet(map_space_, &ScavengePointer);
   lo_space_->IterateRSet(&ScavengePointer);
 
   do {
     ASSERT(new_space_front <= new_space_.top());
-    ASSERT(promoted_front >= promoted_rear);
 
     // The addresses new_space_front and new_space_.top() define a
     // queue of unprocessed copied objects.  Process them until the
     // queue is empty.
     while (new_space_front < new_space_.top()) {
       HeapObject* object = HeapObject::FromAddress(new_space_front);
       object->Iterate(&scavenge_visitor);
       new_space_front += object->Size();
     }
 
-    // The addresses promoted_front and promoted_rear define a queue
-    // of unprocessed addresses of promoted objects.  Process them
-    // until the queue is empty.
-    while (promoted_front > promoted_rear) {
-      promoted_front -= kPointerSize;
-      HeapObject* object =
-          HeapObject::cast(Memory::Object_at(promoted_front));
-      object->Iterate(&scavenge_visitor);
-      UpdateRSet(object);
+    // Promote and process all the to-be-promoted objects.
+    while (!promotion_queue.is_empty()) {
+      HeapObject* source;
+      Map* map;
+      promotion_queue.remove(&source, &map);
+      // Copy the from-space object to its new location (given by the
+      // forwarding address) and fix its map.
+      HeapObject* target = source->map_word().ToForwardingAddress();
+      CopyBlock(reinterpret_cast<Object**>(target->address()),
+                reinterpret_cast<Object**>(source->address()),
+                source->SizeFromMap(map));
+      target->set_map(map);
+
+#if defined(DEBUG) || defined(ENABLE_LOGGING_AND_PROFILING)
+      // Update NewSpace stats if necessary.
+      RecordCopiedObject(target);
+#endif
+      // Visit the newly copied object for pointers to new space.
+      target->Iterate(&scavenge_visitor);
+      UpdateRSet(target);
     }
 
     // Take another spin if there are now unswept objects in new space
     // (there are currently no more unswept promoted objects).
   } while (new_space_front < new_space_.top());
 
   // Set age mark.
   new_space_.set_age_mark(new_space_.top());
 
   LOG(ResourceEvent("scavenge", "end"));
@@ skipping 136 matching lines @@
                                 HeapObject* target,
                                 int size) {
   // Copy the content of source to target.
   CopyBlock(reinterpret_cast<Object**>(target->address()),
             reinterpret_cast<Object**>(source->address()),
             size);
 
   // Set the forwarding address.
   source->set_map_word(MapWord::FromForwardingAddress(target));
 
+#if defined(DEBUG) || defined(ENABLE_LOGGING_AND_PROFILING)
   // Update NewSpace stats if necessary.
-#if defined(DEBUG) || defined(ENABLE_LOGGING_AND_PROFILING)
   RecordCopiedObject(target);
 #endif
 
   return target;
 }
 
 
-// Inlined function.
-void Heap::ScavengeObject(HeapObject** p, HeapObject* object) {
-  ASSERT(InFromSpace(object));
-
-  // We use the first word (where the map pointer usually is) of a heap
-  // object to record the forwarding pointer.  A forwarding pointer can
-  // point to an old space, the code space, or the to space of the new
-  // generation.
-  MapWord first_word = object->map_word();
-
-  // If the first word is a forwarding address, the object has already been
-  // copied.
-  if (first_word.IsForwardingAddress()) {
-    *p = first_word.ToForwardingAddress();
-    return;
-  }
-
-  // Call the slow part of scavenge object.
-  return ScavengeObjectSlow(p, object);
-}
-
-
 static inline bool IsShortcutCandidate(HeapObject* object, Map* map) {
   STATIC_ASSERT(kNotStringTag != 0 && kSymbolTag != 0);
   ASSERT(object->map() == map);
   InstanceType type = map->instance_type();
   if ((type & kShortcutTypeMask) != kShortcutTypeTag) return false;
   ASSERT(object->IsString() && !object->IsSymbol());
   return ConsString::cast(object)->unchecked_second() == Heap::empty_string();
 }
 
 
@@ skipping 10 matching lines @@
     // active semispace of the young generation and not already copied.
     if (!InNewSpace(object)) return;
     first_word = object->map_word();
     if (first_word.IsForwardingAddress()) {
       *p = first_word.ToForwardingAddress();
       return;
     }
   }
 
   int object_size = object->SizeFromMap(first_word.ToMap());
+  // We rely on live objects in new space to be at least two pointers,
+  // so we can store the from-space address and map pointer of promoted
+  // objects in the to space.
+  ASSERT(object_size >= 2 * kPointerSize);
+
   // If the object should be promoted, we try to copy it to old space.
   if (ShouldBePromoted(object->address(), object_size)) {
     OldSpace* target_space = Heap::TargetSpace(object);
     ASSERT(target_space == Heap::old_pointer_space_ ||
            target_space == Heap::old_data_space_);
     Object* result = target_space->AllocateRaw(object_size);
     if (!result->IsFailure()) {
-      *p = MigrateObject(object, HeapObject::cast(result), object_size);
+      HeapObject* target = HeapObject::cast(result);
       if (target_space == Heap::old_pointer_space_) {
-        // Record the object's address at the top of the to space, to allow
-        // it to be swept by the scavenger.
-        promoted_rear -= kPointerSize;
-        Memory::Object_at(promoted_rear) = *p;
+        // Save the from-space object pointer and its map pointer at the
+        // top of the to space to be swept and copied later.  Write the
+        // forwarding address over the map word of the from-space
+        // object.
+        promotion_queue.insert(object, first_word.ToMap());
+        object->set_map_word(MapWord::FromForwardingAddress(target));
+
+        // Give the space allocated for the result a proper map by
+        // treating it as a free list node (not linked into the free
+        // list).
+        FreeListNode* node = FreeListNode::FromAddress(target->address());
+        node->set_size(object_size);
+
+        *p = target;
       } else {
+        // Objects promoted to the data space can be copied immediately
+        // and not revisited---we will never sweep that space for
+        // pointers and the copied objects do not contain pointers to
+        // new space objects.
+        *p = MigrateObject(object, target, object_size);
 #ifdef DEBUG
-        // Objects promoted to the data space should not have pointers to
-        // new space.
         VerifyNonPointerSpacePointersVisitor v;
         (*p)->Iterate(&v);
 #endif
       }
       return;
     }
   }
 
   // The object should remain in new space or the old space allocation failed.
   Object* result = new_space_.AllocateRaw(object_size);
@@ skipping 2486 matching lines @@
 #ifdef DEBUG
 bool Heap::GarbageCollectionGreedyCheck() {
   ASSERT(FLAG_gc_greedy);
   if (Bootstrapper::IsActive()) return true;
   if (disallow_allocation_failure()) return true;
   return CollectGarbage(0, NEW_SPACE);
 }
 #endif
 
 } }  // namespace v8::internal