* Complete new store buffer on ia32. The store buffer now covers...

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 953 matching lines @@
   LOG(ResourceEvent("scavenge", "begin"));
 
   // Clear descriptor cache.
   DescriptorLookupCache::Clear();
 
   // Used for updating survived_since_last_expansion_ at function end.
   intptr_t survived_watermark = PromotedSpaceSize();
 
   CheckNewSpaceExpansionCriteria();
 
+  StoreBuffer::Verify();

[Vyacheslav Egorov (Chromium), 2011/01/21 18:18:18]

we should move verification of storebuffer into Heap::Verify().

add TODO(gc)?

[Erik Corry, 2011/01/24 13:56:00]

Done.

+
   // Flip the semispaces.  After flipping, to space is empty, from space has
   // live objects.
   new_space_.Flip();
   new_space_.ResetAllocationInfo();
 
   // We need to sweep newly copied objects which can be either in the
   // to space or promoted to the old generation.  For to-space
   // objects, we treat the bottom of the to space as a queue.  Newly
   // copied and unswept objects lie between a 'front' mark and the
   // allocation pointer.
   //
   // Promoted objects can go into various old-generation spaces, and
   // can be allocated internally in the spaces (from the free list).
   // 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();
   promotion_queue.Initialize(new_space_.ToSpaceHigh());
 
   ScavengeVisitor scavenge_visitor;
   // Copy roots.
   IterateRoots(&scavenge_visitor, VISIT_ALL_IN_SCAVENGE);
 
+#ifdef DEBUG
+  StoreBuffer::Clean();

[Vyacheslav Egorov (Chromium), 2011/01/21 18:18:18]

Why we do this only in debug? 

Comment?

[Erik Corry, 2011/01/24 13:56:00]

When we actually use the store buffer info it will get cleaned and rebuilt as a
side effect of using it.

+#endif
+
   // 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,
@@ skipping 3038 matching lines @@
        a += kPointerSize) {
     Memory::Address_at(a) = kFromSpaceZapValue;
   }
 }
 #endif  // DEBUG
 
 
 bool Heap::IteratePointersInDirtyRegion(Address start,
                                         Address end,
                                         ObjectSlotCallback copy_object_func) {
-  Address slot_address = start;
   bool pointers_to_new_space_found = false;
 
-  while (slot_address < end) {
+  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;
       }
     }
-    slot_address += kPointerSize;
   }
   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);
 }
@@ skipping 84 matching lines @@
   }
 
   return contains_pointers_to_new_space;
 }
 
 
 void Heap::IterateAndMarkPointersToFromSpace(Address start,
                                              Address end,
                                              ObjectSlotCallback callback) {
   Address slot_address = start;
-  Page* page = Page::FromAddress(start);
-
-  uint32_t marks = page->GetRegionMarks();
-
   while (slot_address < end) {
     Object** slot = reinterpret_cast<Object**>(slot_address);
     if (Heap::InFromSpace(*slot)) {
       ASSERT((*slot)->IsHeapObject());
       callback(reinterpret_cast<HeapObject**>(slot));
       if (Heap::InNewSpace(*slot)) {
         ASSERT((*slot)->IsHeapObject());
-        marks |= page->GetRegionMaskForAddress(slot_address);
+        StoreBuffer::Mark(reinterpret_cast<Address>(slot));
       }
     }
     slot_address += kPointerSize;
   }
-
-  page->SetRegionMarks(marks);
 }
 
 
 uint32_t Heap::IterateDirtyRegions(

[Vyacheslav Egorov (Chromium), 2011/01/21 18:18:18]

If you decided to kill cardmarking wb maybe you will do it completely without
leaving any trace (search for all ENABLE_CARDMARKING_ ifdefs and kill them?)

[Erik Corry, 2011/01/24 13:56:00]

That is certainly the plan.

     uint32_t marks,
     Address area_start,
     Address area_end,
     DirtyRegionCallback visit_dirty_region,
     ObjectSlotCallback copy_object_func) {
-#ifndef ENABLE_CARDMARKING_WRITE_BARRIER
   ASSERT(marks == Page::kAllRegionsDirtyMarks);
   visit_dirty_region(area_start, area_end, copy_object_func);
   return Page::kAllRegionsDirtyMarks;
-#else
-  uint32_t newmarks = 0;
-  uint32_t mask = 1;
+}
 
-  if (area_start >= area_end) {
-    return newmarks;
-  }
 
-  Address region_start = area_start;
+#ifdef DEBUG
+// Check that the store buffer contains all intergenerational pointers by
+// scanning a page and ensuring that all pointers to young space are in the
+// store buffer.
+void Heap::OldPointerSpaceCheckStoreBuffer(
+    ExpectedPageWatermarkState watermark_state) {
+  OldSpace* space = old_pointer_space();
+  PageIterator pages(space, PageIterator::PAGES_IN_USE);
 
-  // area_start does not necessarily coincide with start of the first region.
-  // Thus to calculate the beginning of the next region we have to align
-  // area_start by Page::kRegionSize.
-  Address second_region =
-      reinterpret_cast<Address>(
-          reinterpret_cast<intptr_t>(area_start + Page::kRegionSize) &
-          ~Page::kRegionAlignmentMask);
+  space->free_list()->Zap();

[Vyacheslav Egorov (Chromium), 2011/01/21 18:18:18]

Why do we need to Zap free_list?

Can we zap it with a special value to detect cases when we have slots of dead
objects in store buffer?

[Erik Corry, 2011/01/24 13:56:00]

We zap the free list so that we can walk the whole old space (ignoring object
boundaries) and verify that there are no new space pointers that are missing in
the store buffer.

The issue you raise is the opposite one, the issue of entries in the store
buffer that are inside dead objects.  I think a magic zap value can take care of
both issues.
Yes.

 
-  // Next region might be beyond area_end.
-  Address region_end = Min(second_region, area_end);
+  StoreBuffer::SortUniq();

[Vyacheslav Egorov (Chromium), 2011/01/21 18:18:18]

Verifying StoreBuffer has an unfortunate side-effect of uniqifying it.

Are we going to uniqify it on each collection? If not --- storebuffer with
verification and without will behave differently.

[Erik Corry, 2011/01/24 13:56:00]

I think we will be sorting and uniqifying on each collection.

 
-  if (marks & mask) {
-    if (visit_dirty_region(region_start, region_end, copy_object_func)) {
-      newmarks |= mask;
-    }
-  }
-  mask <<= 1;
+  while (pages.has_next()) {
+    Page* page = pages.next();
+    Object** current = reinterpret_cast<Object**>(page->ObjectAreaStart());
 
-  // Iterate subsequent regions which fully lay inside [area_start, area_end[.
-  region_start = region_end;
-  region_end = region_start + Page::kRegionSize;
+    // Do not try to visit pointers beyond page allocation watermark.
+    // Page can contain garbage pointers there.
+    Address end;
 
-  while (region_end <= area_end) {
-    if (marks & mask) {
-      if (visit_dirty_region(region_start, region_end, copy_object_func)) {
-        newmarks |= mask;
-      }
+    if (watermark_state == WATERMARK_SHOULD_BE_VALID ||
+        page->IsWatermarkValid()) {
+      end = page->AllocationWatermark();
+    } else {
+      end = page->CachedAllocationWatermark();
     }
 
-    region_start = region_end;
-    region_end = region_start + Page::kRegionSize;
+    Object*** store_buffer_position = StoreBuffer::Start();
+    Object*** store_buffer_top = StoreBuffer::Top();
 
-    mask <<= 1;
-  }
-
-  if (region_start != area_end) {
-    // A small piece of area left uniterated because area_end does not coincide
-    // with region end. Check whether region covering last part of area is
-    // dirty.
-    if (marks & mask) {
-      if (visit_dirty_region(region_start, area_end, copy_object_func)) {
-        newmarks |= mask;
+    Object** limit = reinterpret_cast<Object**>(end);
+    for ( ; current < limit; current++) {
+      Object* o = *current;
+      if (o->IsSmi()) continue;

[Vyacheslav Egorov (Chromium), 2011/01/21 18:18:18]

InNewSpace(Object* o) can't return true for a smi.

[Erik Corry, 2011/01/24 13:56:00]

Done.

+      // We have to check that the pointer does not point into new space
+      // without trying to cast it to a heap object since the hash field of
+      // a string can contain values like 1 and 3 which are tagged null
+      // pointers.
+      if (!InNewSpace(o)) continue;
+      while (*store_buffer_position < current) {
+        store_buffer_position++;
+        ASSERT(store_buffer_position < store_buffer_top);
+      }
+      if (*store_buffer_position != current) {
+        Object** obj_start = current;
+        while (!(*obj_start)->IsMap()) obj_start--;
+        UNREACHABLE();
       }
     }
   }
-
-  return newmarks;
-#endif
 }
 
 
+void Heap::MapSpaceCheckStoreBuffer(
+    ExpectedPageWatermarkState watermark_state) {
+  MapSpace* space = map_space();
+  PageIterator pages(space, PageIterator::PAGES_IN_USE);
+
+  space->free_list()->Zap();

[Vyacheslav Egorov (Chromium), 2011/01/21 18:18:18]

Can we zap it with a special value to detect cases when we have slots of dead
objects in store buffer?

[Erik Corry, 2011/01/24 13:56:00]

Done.

+
+  StoreBuffer::SortUniq();
+
+  while (pages.has_next()) {
+    Page* page = pages.next();
+
+    // Do not try to visit pointers beyond page allocation watermark.
+    // Page can contain garbage pointers there.
+    Address end;
+
+    if (watermark_state == WATERMARK_SHOULD_BE_VALID ||
+        page->IsWatermarkValid()) {
+      end = page->AllocationWatermark();
+    } else {
+      end = page->CachedAllocationWatermark();
+    }
+
+    Address map_aligned_current = MapStartAlign(page->ObjectAreaStart());

[Vyacheslav Egorov (Chromium), 2011/01/21 18:18:18]

both ObjectAreaStart and watermark should be aligned by MapSize.

this is no-ops. consider removing them

[Erik Corry, 2011/01/24 13:56:00]

Done.

+    Address map_aligned_end   = MapEndAlign(end);
+
+    Object*** store_buffer_position = StoreBuffer::Start();
+    Object*** store_buffer_top = StoreBuffer::Top();
+
+    for ( ;
+         map_aligned_current < map_aligned_end;
+         map_aligned_current += Map::kSize) {
+      ASSERT(!Heap::InNewSpace(Memory::Object_at(map_aligned_current)));
+      ASSERT(Memory::Object_at(map_aligned_current)->IsMap());
+
+      Object** current = reinterpret_cast<Object**>(
+          map_aligned_current + Map::kPointerFieldsBeginOffset);
+      Object** limit = reinterpret_cast<Object**>(
+          map_aligned_current + Map::kPointerFieldsEndOffset);
+
+      for ( ; current < limit; current++) {

[Vyacheslav Egorov (Chromium), 2011/01/21 18:18:18]

This loop looks familiar.

I saw similar one above.

[Erik Corry, 2011/01/24 13:56:00]

Done.

+        Object* o = *current;
+        if (o->IsSmi()) continue;

[Vyacheslav Egorov (Chromium), 2011/01/21 18:18:18]

InNewSpace(Object* o) can't return true for a smi.

[Erik Corry, 2011/01/24 13:56:00]

Done.

+        HeapObject* heap_object = HeapObject::cast(o);
+        if (!InNewSpace(heap_object)) continue;
+        while (*store_buffer_position < current) {
+          store_buffer_position++;
+          ASSERT(store_buffer_position < store_buffer_top);
+        }
+        ASSERT(*store_buffer_position == current);
+      }
+    }
+  }
+}
+
+
+void Heap::LargeObjectSpaceCheckStoreBuffer() {
+  LargeObjectIterator it(lo_space());
+  for (HeapObject* object = it.next(); object != NULL; object = it.next()) {
+    // We only have code, sequential strings, or fixed arrays in large
+    // object space, and only fixed arrays can possibly contain pointers to
+    // the young generation.
+    if (object->IsFixedArray()) {
+      Object*** store_buffer_position = StoreBuffer::Start();
+      Object*** store_buffer_top = StoreBuffer::Top();
+      Object** current = reinterpret_cast<Object**>(object->address());
+      Object** limit =
+          reinterpret_cast<Object**>(object->address() + object->Size());
+      for ( ; current < limit; current++) {

[Vyacheslav Egorov (Chromium), 2011/01/21 18:18:18]

This loop looks familiar.

Consider moving it to separate function.

[Erik Corry, 2011/01/24 13:56:00]

Done.

+        Object* o = *current;
+        if (o->IsSmi()) continue;
+        HeapObject* heap_object = HeapObject::cast(o);
+        if (!InNewSpace(heap_object)) continue;
+        while (*store_buffer_position < current) {
+          store_buffer_position++;
+          ASSERT(store_buffer_position < store_buffer_top);
+        }
+        ASSERT(*store_buffer_position == current);
+      }
+    }
+  }
+}
+
+
+#endif
+
 
 void Heap::IterateDirtyRegions(
     PagedSpace* space,
     DirtyRegionCallback visit_dirty_region,
     ObjectSlotCallback copy_object_func,
     ExpectedPageWatermarkState expected_page_watermark_state) {
 
-  PageIterator it(space, PageIterator::PAGES_IN_USE);
+  PageIterator pages(space, PageIterator::PAGES_IN_USE);
 
-  while (it.has_next()) {
-    Page* page = it.next();
-    uint32_t marks = page->GetRegionMarks();
+  while (pages.has_next()) {
+    Page* page = pages.next();
+    Address start = page->ObjectAreaStart();
 
-    if (marks != Page::kAllRegionsCleanMarks) {
-      Address start = page->ObjectAreaStart();
+    // Do not try to visit pointers beyond page allocation watermark.
+    // Page can contain garbage pointers there.
+    Address end;
 
-      // 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();
+    }
 
-      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)));
 
-      ASSERT(space == old_pointer_space_ ||
-             (space == map_space_ &&
-              ((page->ObjectAreaStart() - end) % Map::kSize == 0)));
-
-      page->SetRegionMarks(IterateDirtyRegions(marks,
-                                               start,
-                                               end,
-                                               visit_dirty_region,
-                                               copy_object_func));
-    }
+    IterateDirtyRegions(Page::kAllRegionsDirtyMarks,
+                        start,
+                        end,
+                        visit_dirty_region,
+                        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 1182 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