Start using store buffers. Handle store buffer overflow situation....

src/heap.cc

 // Copyright 2010 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 24 matching lines @@
 #include "debug.h"
 #include "heap-profiler.h"
 #include "global-handles.h"
 #include "mark-compact.h"
 #include "natives.h"
 #include "objects-visiting.h"
 #include "runtime-profiler.h"
 #include "scanner-base.h"
 #include "scopeinfo.h"
 #include "snapshot.h"
+#include "store-buffer.h"
 #include "v8threads.h"
 #include "vm-state-inl.h"
 #if V8_TARGET_ARCH_ARM && !V8_INTERPRETED_REGEXP
 #include "regexp-macro-assembler.h"
 #include "arm/regexp-macro-assembler-arm.h"
 #endif
 
 
 namespace v8 {
 namespace internal {
@@ skipping 569 matching lines @@
 
   Object* context = global_contexts_list_;
   while (!context->IsUndefined()) {
     Context::cast(context)->normalized_map_cache()->Clear();
     context = Context::cast(context)->get(Context::NEXT_CONTEXT_LINK);
   }
 }
 
 
 #ifdef DEBUG
-
 enum PageWatermarkValidity {
   ALL_VALID,
   ALL_INVALID
 };
 
 static void VerifyPageWatermarkValidity(PagedSpace* space,
                                         PageWatermarkValidity validity) {
-  PageIterator it(space, PageIterator::PAGES_IN_USE);
+ PageIterator it(space, PageIterator::PAGES_IN_USE);

[Vyacheslav Egorov (Chromium), 2011/02/02 13:15:47]

indentation

[Erik Corry, 2011/02/03 13:21:17]

Done.

   bool expected_value = (validity == ALL_VALID);
   while (it.has_next()) {
     Page* page = it.next();
     ASSERT(page->IsWatermarkValid() == expected_value);
   }
 }
 #endif
 
+
 void Heap::UpdateSurvivalRateTrend(int start_new_space_size) {
   double survival_rate =
       (static_cast<double>(young_survivors_after_last_gc_) * 100) /
       start_new_space_size;
 
   if (survival_rate > kYoungSurvivalRateThreshold) {
     high_survival_rate_period_length_++;
   } else {
     high_survival_rate_period_length_ = 0;
   }
@@ skipping 279 matching lines @@
 #endif
 
   gc_state_ = SCAVENGE;
 
   Page::FlipMeaningOfInvalidatedWatermarkFlag();
 #ifdef DEBUG
   VerifyPageWatermarkValidity(old_pointer_space_, ALL_VALID);
   VerifyPageWatermarkValidity(map_space_, ALL_VALID);
 #endif
 
+
   // We do not update an allocation watermark of the top page during linear
   // allocation to avoid overhead. So to maintain the watermark invariant
   // we have to manually cache the watermark and mark the top page as having an
-  // invalid watermark. This guarantees that dirty regions iteration will use a
-  // correct watermark even if a linear allocation happens.
+  // invalid watermark.  This guarantees that old space pointer iteration will
+  // use a correct watermark even if a linear allocation happens.
   old_pointer_space_->FlushTopPageWatermark();
   map_space_->FlushTopPageWatermark();
 
   // Implements Cheney's copying algorithm
   LOG(ResourceEvent("scavenge", "begin"));
 
   // Clear descriptor cache.
   DescriptorLookupCache::Clear();
 
   // Used for updating survived_since_last_expansion_ at function end.
@@ skipping 27 matching lines @@
   promotion_queue.Initialize(new_space_.ToSpaceHigh());
 
 #ifdef DEBUG
   StoreBuffer::Clean();
 #endif
 
   ScavengeVisitor scavenge_visitor;
   // Copy roots.
   IterateRoots(&scavenge_visitor, VISIT_ALL_IN_SCAVENGE);
 
-  // Copy objects reachable from the old generation.  By definition,
-  // there are no intergenerational pointers in code or data spaces.
-  IterateDirtyRegions(old_pointer_space_,
-                      &IteratePointersInDirtyRegion,
-                      &ScavengePointer,
-                      WATERMARK_CAN_BE_INVALID);
-
-  IterateDirtyRegions(map_space_,
-                      &IteratePointersInDirtyMapsRegion,
-                      &ScavengePointer,
-                      WATERMARK_CAN_BE_INVALID);
-
-  lo_space_->IterateDirtyRegions(&ScavengePointer);
+  // Copy objects reachable from the old generation.
+  {
+    StoreBufferRebuildScope scope;
+    StoreBuffer::IteratePointersToNewSpace(&ScavengeObject);
+  }
 
   // Copy objects reachable from cells by scavenging cell values directly.
   HeapObjectIterator cell_iterator(cell_space_);
   for (HeapObject* cell = cell_iterator.next();
        cell != NULL; cell = cell_iterator.next()) {
     if (cell->IsJSGlobalPropertyCell()) {
       Address value_address =
           reinterpret_cast<Address>(cell) +
           (JSGlobalPropertyCell::kValueOffset - kHeapObjectTag);
       scavenge_visitor.VisitPointer(reinterpret_cast<Object**>(value_address));
@@ skipping 177 matching lines @@
 
     // 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);
       new_space_front += NewSpaceScavenger::IterateBody(object->map(), object);
     }
 
     // Promote and process all the to-be-promoted objects.
-    while (!promotion_queue.is_empty()) {
-      HeapObject* target;
-      int size;
-      promotion_queue.remove(&target, &size);
+    {
+      StoreBufferRebuildScope scope;
+      while (!promotion_queue.is_empty()) {
+        HeapObject* target;
+        int size;
+        promotion_queue.remove(&target, &size);
 
-      // Promoted object might be already partially visited
-      // during dirty regions iteration. Thus we search specificly
-      // for pointers to from semispace instead of looking for pointers
-      // to new space.
-      ASSERT(!target->IsMap());
-      IterateAndMarkPointersToFromSpace(target->address(),
-                                        target->address() + size,
-                                        &ScavengePointer);
+        // Promoted object might be already partially visited
+        // during old space pointer iteration. Thus we search specificly
+        // for pointers to from semispace instead of looking for pointers
+        // to new space.
+        ASSERT(!target->IsMap());
+        IterateAndMarkPointersToFromSpace(target->address(),
+                                          target->address() + size,
+                                          &ScavengeObject);
+      }
     }
 
     // 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());
 
   return new_space_front;
 }
 
 
@@ skipping 126 matching lines @@
           promotion_queue.insert(target, object_size);
         }
 
         Heap::tracer()->increment_promoted_objects_size(object_size);
         return;
       }
     }
     Object* result =
         Heap::new_space()->AllocateRaw(object_size)->ToObjectUnchecked();
     *slot = MigrateObject(object, HeapObject::cast(result), object_size);
+    if (!Heap::InNewSpace(reinterpret_cast<Address>(slot))) {
+      StoreBuffer::EnterDirectlyIntoStoreBuffer(
+          reinterpret_cast<Address>(slot));
+    }
     return;
   }
 
 
   static inline void EvacuateFixedArray(Map* map,
                                         HeapObject** slot,
                                         HeapObject* object) {
     int object_size = FixedArray::BodyDescriptor::SizeOf(map, object);
     EvacuateObject<POINTER_OBJECT, UNKNOWN_SIZE>(map,
                                                  slot,
@@ skipping 2511 matching lines @@
       return cell_space_->Contains(addr);
     case LO_SPACE:
       return lo_space_->SlowContains(addr);
   }
 
   return false;
 }
 
 
 #ifdef DEBUG
-static void DummyScavengePointer(HeapObject** p) {
+static void VerifyPointersUnderWatermark(

[Vyacheslav Egorov (Chromium), 2011/02/02 13:15:47]

Why we have function that does not do anything?

[Erik Corry, 2011/02/03 13:21:17]

Function restored.

+    PagedSpace* space,
+    PointerRegionCallback visit_pointer_region) {
 }
 
 
-static void VerifyPointersUnderWatermark(
-    PagedSpace* space,
-    DirtyRegionCallback visit_dirty_region) {
-  PageIterator it(space, PageIterator::PAGES_IN_USE);
-
-  while (it.has_next()) {
-    Page* page = it.next();
-    Address start = page->ObjectAreaStart();
-    Address end = page->AllocationWatermark();
-
-    Heap::IterateDirtyRegions(Page::kAllRegionsDirtyMarks,
-                              start,
-                              end,
-                              visit_dirty_region,
-                              &DummyScavengePointer);
-  }
-}
-
-
 static void VerifyPointersUnderWatermark(LargeObjectSpace* space) {
   LargeObjectIterator it(space);
   for (HeapObject* object = it.next(); object != NULL; object = it.next()) {
     if (object->IsFixedArray()) {
       Address slot_address = object->address();
       Address end = object->address() + object->Size();
 
       while (slot_address < end) {
         HeapObject** slot = reinterpret_cast<HeapObject**>(slot_address);
         // When we are not in GC the Heap::InNewSpace() predicate
@@ skipping 14 matching lines @@
 
   VerifyPointersVisitor visitor;
   IterateRoots(&visitor, VISIT_ONLY_STRONG);
 
   new_space_.Verify();
 
   old_pointer_space_->Verify(&visitor);
   map_space_->Verify(&visitor);
 
   VerifyPointersUnderWatermark(old_pointer_space_,
-                               &IteratePointersInDirtyRegion);
+                               &IteratePointersToNewSpace);
   VerifyPointersUnderWatermark(map_space_,
-                               &IteratePointersInDirtyMapsRegion);
+                               &IteratePointersFromMapsToNewSpace);
   VerifyPointersUnderWatermark(lo_space_);
 
   VerifyPageWatermarkValidity(old_pointer_space_, ALL_INVALID);
   VerifyPageWatermarkValidity(map_space_, ALL_INVALID);
 
   VerifyPointersVisitor no_dirty_regions_visitor;
   old_data_space_->Verify(&no_dirty_regions_visitor);
   code_space_->Verify(&no_dirty_regions_visitor);
   cell_space_->Verify(&no_dirty_regions_visitor);
 
@@ skipping 77 matching lines @@
   ASSERT(reinterpret_cast<Object*>(kFromSpaceZapValue)->IsHeapObject());
   for (Address a = new_space_.FromSpaceLow();
        a < new_space_.FromSpaceHigh();
        a += kPointerSize) {
     Memory::Address_at(a) = kFromSpaceZapValue;
   }
 }
 #endif  // DEBUG
 
 
-bool Heap::IteratePointersInDirtyRegion(Address start,
-                                        Address end,
-                                        ObjectSlotCallback copy_object_func) {
-  bool pointers_to_new_space_found = false;
-
+void Heap::IteratePointersToNewSpace(Address start,
+                                     Address end,
+                                     ObjectSlotCallback copy_object_func) {
   for (Address slot_address = start;
        slot_address < end;
        slot_address += kPointerSize) {
     Object** slot = reinterpret_cast<Object**>(slot_address);
     if (Heap::InNewSpace(*slot)) {
-      ASSERT((*slot)->IsHeapObject());
-      copy_object_func(reinterpret_cast<HeapObject**>(slot));
-      if (Heap::InNewSpace(*slot)) {
-        ASSERT((*slot)->IsHeapObject());
-        StoreBuffer::Mark(reinterpret_cast<Address>(slot));
-        pointers_to_new_space_found = true;
-      }
+      HeapObject* object = reinterpret_cast<HeapObject*>(*slot);
+      ASSERT(object->IsHeapObject());
+      copy_object_func(reinterpret_cast<HeapObject**>(slot), object);
     }
   }
-  return pointers_to_new_space_found;
 }
 
 
 // Compute start address of the first map following given addr.
 static inline Address MapStartAlign(Address addr) {
   Address page = Page::FromAddress(addr)->ObjectAreaStart();
   return page + (((addr - page) + (Map::kSize - 1)) / Map::kSize * Map::kSize);
 }
 
 
 // Compute end address of the first map preceding given addr.
 static inline Address MapEndAlign(Address addr) {
   Address page = Page::FromAllocationTop(addr)->ObjectAreaStart();
   return page + ((addr - page) / Map::kSize * Map::kSize);
 }
 
 
-static bool IteratePointersInDirtyMaps(Address start,
-                                       Address end,
-                                       ObjectSlotCallback copy_object_func) {
+static void IteratePointersToNewSpaceInMaps(
+    Address start,
+    Address end,
+    ObjectSlotCallback copy_object_func) {
   ASSERT(MapStartAlign(start) == start);
   ASSERT(MapEndAlign(end) == end);
 
   Address map_address = start;
-  bool pointers_to_new_space_found = false;
 
   while (map_address < end) {
     ASSERT(!Heap::InNewSpace(Memory::Object_at(map_address)));
     ASSERT(Memory::Object_at(map_address)->IsMap());
 
     Address pointer_fields_start = map_address + Map::kPointerFieldsBeginOffset;
     Address pointer_fields_end = map_address + Map::kPointerFieldsEndOffset;
 
-    if (Heap::IteratePointersInDirtyRegion(pointer_fields_start,
-                                           pointer_fields_end,
-                                           copy_object_func)) {
-      pointers_to_new_space_found = true;
-    }
-
+    Heap::IteratePointersToNewSpace(pointer_fields_start,
+                                    pointer_fields_end,
+                                    copy_object_func);
     map_address += Map::kSize;
   }
-
-  return pointers_to_new_space_found;
 }
 
 
-bool Heap::IteratePointersInDirtyMapsRegion(
+void Heap::IteratePointersFromMapsToNewSpace(
     Address start,
     Address end,
     ObjectSlotCallback copy_object_func) {
   Address map_aligned_start = MapStartAlign(start);
   Address map_aligned_end   = MapEndAlign(end);
 
-  bool contains_pointers_to_new_space = false;
-
   if (map_aligned_start != start) {
     Address prev_map = map_aligned_start - Map::kSize;
     ASSERT(Memory::Object_at(prev_map)->IsMap());
 
     Address pointer_fields_start =
         Max(start, prev_map + Map::kPointerFieldsBeginOffset);
 
     Address pointer_fields_end =
         Min(prev_map + Map::kPointerFieldsEndOffset, end);
 

[Vyacheslav Egorov (Chromium), 2011/02/02 13:15:47]

If you are not using region marks -> your start and end probably always aligned
to map size so you can get read of all this complicated misalignment handling.

[Erik Corry, 2011/02/03 13:21:17]

Done.

-    contains_pointers_to_new_space =
-      IteratePointersInDirtyRegion(pointer_fields_start,
-                                   pointer_fields_end,
-                                   copy_object_func)
-        || contains_pointers_to_new_space;
+    IteratePointersToNewSpace(pointer_fields_start,
+                              pointer_fields_end,
+                              copy_object_func);
   }
 
-  contains_pointers_to_new_space =
-    IteratePointersInDirtyMaps(map_aligned_start,
-                               map_aligned_end,
-                               copy_object_func)
-      || contains_pointers_to_new_space;
+  IteratePointersToNewSpaceInMaps(map_aligned_start,
+                                  map_aligned_end,
+                                  copy_object_func);
 
   if (map_aligned_end != end) {
     ASSERT(Memory::Object_at(map_aligned_end)->IsMap());
 
     Address pointer_fields_start =
         map_aligned_end + Map::kPointerFieldsBeginOffset;
 
     Address pointer_fields_end =
         Min(end, map_aligned_end + Map::kPointerFieldsEndOffset);
 
-    contains_pointers_to_new_space =
-      IteratePointersInDirtyRegion(pointer_fields_start,
-                                   pointer_fields_end,
-                                   copy_object_func)
-        || contains_pointers_to_new_space;
+    IteratePointersToNewSpace(pointer_fields_start,
+                                 pointer_fields_end,

[Vyacheslav Egorov (Chromium), 2011/02/02 13:15:47]

indent

[Erik Corry, 2011/02/03 13:21:17]

Done.

+                                 copy_object_func);
   }
-
-  return contains_pointers_to_new_space;
 }
 
 
 void Heap::IterateAndMarkPointersToFromSpace(Address start,
                                              Address end,
                                              ObjectSlotCallback callback) {
   Address slot_address = start;
   while (slot_address < end) {
     Object** slot = reinterpret_cast<Object**>(slot_address);
-    if (Heap::InFromSpace(*slot)) {
-      ASSERT((*slot)->IsHeapObject());
-      callback(reinterpret_cast<HeapObject**>(slot));
+    Object* object = *slot;
+    // In normal store buffer operation we use this function to process the
+    // promotion queue and we never scan an object twice so we will not see
+    // pointers that have already been updated to point to to-space.  But
+    // in the case of store buffer overflow we scan the entire old space to
+    // find pointers that point to new-space and in that case we may hit
+    // newly promoted objects and fix the pointers before the promotion
+    // queue gets to them.
+    ASSERT(StoreBuffer::store_buffer_mode() !=
+               StoreBuffer::kStoreBufferFunctional ||
+           !Heap::InToSpace(object));
+    if (Heap::InFromSpace(object)) {
+      callback(reinterpret_cast<HeapObject**>(slot), HeapObject::cast(object));
       if (Heap::InNewSpace(*slot)) {
+        ASSERT(Heap::InToSpace(*slot));
         ASSERT((*slot)->IsHeapObject());
-        StoreBuffer::Mark(reinterpret_cast<Address>(slot));
+        StoreBuffer::EnterDirectlyIntoStoreBuffer(
+            reinterpret_cast<Address>(slot));
       }
     }
     slot_address += kPointerSize;
   }
 }
 
 
-uint32_t Heap::IterateDirtyRegions(
-    uint32_t marks,
-    Address area_start,
-    Address area_end,
-    DirtyRegionCallback visit_dirty_region,
-    ObjectSlotCallback copy_object_func) {
-  ASSERT(marks == Page::kAllRegionsDirtyMarks);
-  visit_dirty_region(area_start, area_end, copy_object_func);
-  return Page::kAllRegionsDirtyMarks;
-}
-
-
 #ifdef DEBUG
 static void CheckStoreBuffer(Object** current,
                              Object** limit,
                              Object**** store_buffer_position,
                              Object*** store_buffer_top) {
   for ( ; current < limit; current++) {
     Object* o = *current;
     if (reinterpret_cast<uintptr_t>(o) == kFreeListZapValue) {
       Object*** zap_checker = *store_buffer_position;
       while (*zap_checker < current) {
@@ skipping 128 matching lines @@
                        &store_buffer_position,
                        store_buffer_top);
     }
   }
 }
 
 
 #endif
 
 
-void Heap::IterateDirtyRegions(
+void Heap::IteratePointers(
     PagedSpace* space,
-    DirtyRegionCallback visit_dirty_region,
+    PointerRegionCallback visit_pointer_region,
     ObjectSlotCallback copy_object_func,
     ExpectedPageWatermarkState expected_page_watermark_state) {
 
   PageIterator pages(space, PageIterator::PAGES_IN_USE);
 
   while (pages.has_next()) {
     Page* page = pages.next();
     Address start = page->ObjectAreaStart();
 
     // Do not try to visit pointers beyond page allocation watermark.
     // Page can contain garbage pointers there.
     Address end;
 
     if ((expected_page_watermark_state == WATERMARK_SHOULD_BE_VALID) ||
         page->IsWatermarkValid()) {
       end = page->AllocationWatermark();
     } else {
       end = page->CachedAllocationWatermark();
     }
 
     ASSERT(space == old_pointer_space_ ||
            (space == map_space_ &&
             ((page->ObjectAreaStart() - end) % Map::kSize == 0)));
 
-    IterateDirtyRegions(Page::kAllRegionsDirtyMarks,
-                        start,
-                        end,
-                        visit_dirty_region,
-                        copy_object_func);
+    visit_pointer_region(start, end, copy_object_func);
 
     // Mark page watermark as invalid to maintain watermark validity invariant.
     // See Page::FlipMeaningOfInvalidatedWatermarkFlag() for details.
     page->InvalidateWatermark(true);
   }
 }
 
 
 void Heap::IterateRoots(ObjectVisitor* v, VisitMode mode) {
   IterateStrongRoots(v, mode);
@@ skipping 1187 matching lines @@
 void ExternalStringTable::TearDown() {
   new_space_strings_.Free();
   old_space_strings_.Free();
 }
 
 
 List<Object*> ExternalStringTable::new_space_strings_;
 List<Object*> ExternalStringTable::old_space_strings_;
 
 } }  // namespace v8::internal