Multi-page growing and shrinking new-space

src/spaces.cc

 // Copyright 2011 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 392 matching lines @@
                                                NOT_EXECUTABLE,
                                                semi_space);
   chunk->set_next_chunk(NULL);
   chunk->set_prev_chunk(NULL);
   chunk->initialize_scan_on_scavenge(true);
   bool in_to_space = (semi_space->id() != kFromSpace);
   chunk->SetFlag(in_to_space ? MemoryChunk::IN_TO_SPACE
                              : MemoryChunk::IN_FROM_SPACE);
   ASSERT(!chunk->IsFlagSet(in_to_space ? MemoryChunk::IN_FROM_SPACE
                                        : MemoryChunk::IN_TO_SPACE));
-  heap->incremental_marking()->SetNewSpacePageFlags(chunk);
-  return static_cast<NewSpacePage*>(chunk);
+  NewSpacePage* page = static_cast<NewSpacePage*>(chunk);
+  heap->incremental_marking()->SetNewSpacePageFlags(page);
+  return page;
 }
 
 
 void NewSpacePage::InitializeAsAnchor(SemiSpace* semi_space) {
   set_owner(semi_space);
   set_next_chunk(this);
   set_prev_chunk(this);
   // Flags marks this invalid page as not being in new-space.
   // All real new-space pages will be in new-space.
   SetFlags(0, ~0);
@@ skipping 535 matching lines @@
     if (!from_space_.Grow()) {
       // If we managed to grow to space but couldn't grow from space,
       // attempt to shrink to space.
       if (!to_space_.ShrinkTo(from_space_.Capacity())) {
         // We are in an inconsistent state because we could not
         // commit/uncommit memory from new space.
         V8::FatalProcessOutOfMemory("Failed to grow new space.");
       }
     }
   }
-  allocation_info_.limit = to_space_.page_high();
   ASSERT_SEMISPACE_ALLOCATION_INFO(allocation_info_, to_space_);
 }
 
 
 void NewSpace::Shrink() {
   int new_capacity = Max(InitialCapacity(), 2 * SizeAsInt());
   int rounded_new_capacity =
       RoundUp(new_capacity, static_cast<int>(OS::AllocateAlignment()));
   if (rounded_new_capacity < Capacity() &&
       to_space_.ShrinkTo(rounded_new_capacity))  {
     // Only shrink from space if we managed to shrink to space.
     if (!from_space_.ShrinkTo(rounded_new_capacity)) {
       // If we managed to shrink to space but couldn't shrink from
       // space, attempt to grow to space again.
       if (!to_space_.GrowTo(from_space_.Capacity())) {
         // We are in an inconsistent state because we could not
         // commit/uncommit memory from new space.
         V8::FatalProcessOutOfMemory("Failed to shrink new space.");
       }
     }
   }
   allocation_info_.limit = to_space_.page_high();
   ASSERT_SEMISPACE_ALLOCATION_INFO(allocation_info_, to_space_);
 }
 
 
 void NewSpace::UpdateAllocationInfo() {
   allocation_info_.top = to_space_.page_low();
   allocation_info_.limit = to_space_.page_high();
+
+  // Lower limit during incremental marking.
+  if (heap()->incremental_marking()->IsMarking() &&
+      inline_allocation_limit_step() != 0) {
+    Address new_limit =
+        allocation_info_.top + inline_allocation_limit_step();
+    if (new_limit < allocation_info_.limit) {

[Erik Corry, 2011/06/14 12:17:17]

This 'if' can be done more elegantly with Min(x,y)

[Lasse Reichstein, 2011/06/14 14:13:03]

Done.

+      allocation_info_.limit = new_limit;
+    }
+  }
   ASSERT_SEMISPACE_ALLOCATION_INFO(allocation_info_, to_space_);
 }
 
 
 void NewSpace::ResetAllocationInfo() {
   to_space_.Reset();
   UpdateAllocationInfo();
   // Clear all mark-bits in the to-space.
   NewSpacePageIterator it(to_space_.space_low(), to_space_.space_high());
   while (it.has_next()) {
     NewSpacePage* page = it.next();
     page->markbits()->Clear();
   }
 }
 
 
 bool NewSpace::AddFreshPage() {
   Address top = allocation_info_.top;
-  if (top == NewSpacePage::FromLimit(top)->body()) {
+  if (NewSpacePage::at_start(top)) {
     // The current page is already empty. Don't try to make another.
 
     // We should only get here if someone asks to allocate more
     // than what can be stored in a single page.
     // TODO(gc): Change the limit on new-space allocation to prevent this
     // from happening (all such allocations should go directly to LOSpace).
     return false;
   }
   if (!to_space_.AdvancePage()) {
     // Failed to get a new page in to-space.
     return false;
   }
   // Clear remainder of current page.
   int remaining_in_page =
     static_cast<int>(NewSpacePage::FromLimit(top)->body_limit() - top);
   heap()->CreateFillerObjectAt(top, remaining_in_page);
+
   UpdateAllocationInfo();
   return true;
 }
 
 
 #ifdef DEBUG
 // We do not use the SemiSpaceIterator because verification doesn't assume
 // that it works (it depends on the invariants we are checking).
 void NewSpace::Verify() {
   // The allocation pointer should be in the space or at the very end.
   ASSERT_SEMISPACE_ALLOCATION_INFO(allocation_info_, to_space_);
 
   // There should be objects packed in from the low address up to the
   // allocation pointer.
-  NewSpacePage* page = to_space_.first_page();
-  Address current = page->body();
+  Address current = to_space_.first_page()->body();
   CHECK_EQ(current, to_space_.space_low());
 
   while (current != top()) {
-    if (current == page->body_limit()) {
+    if (!NewSpacePage::at_end(current)) {
+      // The allocation pointer should not be in the middle of an object.
+      CHECK(!NewSpacePage::FromLimit(current)->ContainsLimit(top()) ||
+            current < top());
+
+      HeapObject* object = HeapObject::FromAddress(current);
+
+      // The first word should be a map, and we expect all map pointers to
+      // be in map space.
+      Map* map = object->map();
+      CHECK(map->IsMap());
+      CHECK(heap()->map_space()->Contains(map));
+
+      // The object should not be code or a map.
+      CHECK(!object->IsMap());
+      CHECK(!object->IsCode());
+
+      // The object itself should look OK.
+      object->Verify();
+
+      // All the interior pointers should be contained in the heap.
+      VerifyPointersVisitor visitor;
+      int size = object->Size();
+      object->IterateBody(map->instance_type(), size, &visitor);
+
+      current += size;
+    } else {
       // At end of page, switch to next page.
-      page = page->next_page();
+      NewSpacePage* page = NewSpacePage::FromLimit(current)->next_page();
       // Next page should be valid.
       CHECK(!page->is_anchor());
       current = page->body();

[Erik Corry, 2011/06/14 12:17:17]

I think you want a 'continue' here in case the end condition has been reached?

[Lasse Reichstein, 2011/06/14 14:13:03]

The loop ends immediately after, so that won't make any difference.

     }
-    // The allocation pointer should not be in the middle of an object.
-    CHECK(!page->ContainsLimit(top()) || current < top());
-
-    HeapObject* object = HeapObject::FromAddress(current);
-
-    // The first word should be a map, and we expect all map pointers to
-    // be in map space.
-    Map* map = object->map();
-    CHECK(map->IsMap());
-    CHECK(heap()->map_space()->Contains(map));
-
-    // The object should not be code or a map.
-    CHECK(!object->IsMap());
-    CHECK(!object->IsCode());
-
-    // The object itself should look OK.
-    object->Verify();
-
-    // All the interior pointers should be contained in the heap.
-    VerifyPointersVisitor visitor;
-    int size = object->Size();
-    object->IterateBody(map->instance_type(), size, &visitor);
-
-    current += size;
   }
 
   // Check semi-spaces.
   ASSERT_EQ(from_space_.id(), kFromSpace);
   ASSERT_EQ(to_space_.id(), kToSpace);
   from_space_.Verify();
   to_space_.Verify();
 }
 #endif
 
@@ skipping 89 matching lines @@
 }
 
 
 void SemiSpace::TearDown() {
   start_ = NULL;
   capacity_ = 0;
 }
 
 
 bool SemiSpace::Grow() {
-  return false;  // TODO(gc): Temporary hack while semispaces are only one page.
   // Double the semispace size but only up to maximum capacity.
-  int maximum_extra = maximum_capacity_ - capacity_;
-  int extra = Min(RoundUp(capacity_, static_cast<int>(OS::AllocateAlignment())),
-                  maximum_extra);
-  if (!heap()->isolate()->memory_allocator()->CommitBlock(
-      space_high(), extra, executable())) {
-    return false;
-  }
-  capacity_ += extra;
-  return true;
+  ASSERT(static_cast<size_t>(Page::kPageSize) > OS::AllocateAlignment());
+  int new_capacity = Min(maximum_capacity_,
+      RoundUp(capacity_ * 2, static_cast<int>(Page::kPageSize)));
+  return GrowTo(new_capacity);
 }
 
 
 bool SemiSpace::GrowTo(int new_capacity) {
-  return false;  // TODO(gc): Temporary hack while semispaces are only one page.
   ASSERT(new_capacity <= maximum_capacity_);
   ASSERT(new_capacity > capacity_);
+  int pages_before = capacity_ / Page::kPageSize;
   size_t delta = new_capacity - capacity_;
   ASSERT(IsAligned(delta, OS::AllocateAlignment()));
   if (!heap()->isolate()->memory_allocator()->CommitBlock(
       space_high(), delta, executable())) {
     return false;
   }
   capacity_ = new_capacity;
+  int pages_after = capacity_ / Page::kPageSize;
+  NewSpacePage* last_page = anchor()->prev_page();
+  ASSERT(last_page != anchor());
+  for (int i = pages_before; i < pages_after; i++) {
+    Address page_address = start_ + i * Page::kPageSize;
+    NewSpacePage* new_page = NewSpacePage::Initialize(heap(),
+                                                      page_address,
+                                                      this);
+    new_page->InsertAfter(last_page);
+    new_page->markbits()->Clear();
+    // Duplicate the flags that was set on the old page.
+    new_page->SetFlags(last_page->GetFlags(),
+                       NewSpacePage::kCopyOnFlipFlagsMask);
+    last_page = new_page;
+  }
   return true;
 }
 
 
 bool SemiSpace::ShrinkTo(int new_capacity) {
-  return false;  // TODO(gc): Temporary hack while semispaces are only one page.
   ASSERT(new_capacity >= initial_capacity_);
   ASSERT(new_capacity < capacity_);
   size_t delta = capacity_ - new_capacity;
   ASSERT(IsAligned(delta, OS::AllocateAlignment()));
   if (!heap()->isolate()->memory_allocator()->UncommitBlock(
       space_high() - delta, delta)) {
     return false;
   }
   capacity_ = new_capacity;
+
+  int pages_after = capacity_ / Page::kPageSize;
+  NewSpacePage* new_last_page =
+      NewSpacePage::FromAddress(start_ + (pages_after - 1) * Page::kPageSize);
+  new_last_page->set_next_page(anchor());
+  anchor()->set_next_page(new_last_page);
+  ASSERT(current_page_ == first_page());
+
   return true;
 }
 
 
 void SemiSpace::FlipPages(intptr_t flags, intptr_t mask) {
   anchor_.set_owner(this);
   // Fixup back-pointers to anchor. Address of anchor changes
   // when we swap.
   anchor_.prev_page()->set_next_page(&anchor_);
   anchor_.next_page()->set_prev_page(&anchor_);
@@ skipping 26 matching lines @@
   bool is_from_space = (id_ == kFromSpace);
   NewSpacePage* page = anchor_.next_page();
   CHECK(anchor_.semi_space() == this);
   while (page != &anchor_) {
     CHECK(page->semi_space() == this);
     CHECK(page->InNewSpace());
     CHECK(page->IsFlagSet(is_from_space ? MemoryChunk::IN_FROM_SPACE
                                         : MemoryChunk::IN_TO_SPACE));
     CHECK(!page->IsFlagSet(is_from_space ? MemoryChunk::IN_TO_SPACE
                                          : MemoryChunk::IN_FROM_SPACE));
+    CHECK(page->IsFlagSet(MemoryChunk::POINTERS_TO_HERE_ARE_INTERESTING));
+    if (!is_from_space) {
+      // The pointers-from-here-are-interesting flag isn't updated dynamically
+      // on from-space pages, so it might be out of sync with the marking state.

[Erik Corry, 2011/06/14 12:17:17]

Would it be simpler to update it dynamically on from-space pages rather than
have this 'if'?

[Lasse Reichstein, 2011/06/14 14:13:03]

Yes, but why move complexity from debug-only code to "real" code.

+      if (page->heap()->incremental_marking()->IsMarking()) {
+        CHECK(page->IsFlagSet(MemoryChunk::POINTERS_FROM_HERE_ARE_INTERESTING));
+      } else {
+        CHECK(!page->IsFlagSet(
+            MemoryChunk::POINTERS_FROM_HERE_ARE_INTERESTING));
+      }
+    }
+    CHECK(page->IsFlagSet(MemoryChunk::SCAN_ON_SCAVENGE));
     CHECK(page->prev_page()->next_page() == page);
     page = page->next_page();
   }
 }
 
 
-void SemiSpace::ValidateRange(Address start, Address end) {
+void SemiSpace::AssertValidRange(Address start, Address end) {
   // Addresses belong to same semi-space
   NewSpacePage* page = NewSpacePage::FromAddress(start);
   NewSpacePage* end_page = NewSpacePage::FromLimit(end);
   SemiSpace* space = page->semi_space();
   CHECK_EQ(space, end_page->semi_space());
   // Start address is before end address, either on same page,
   // or end address is on a later page in the linked list of
   // semi-space pages.
   if (page == end_page) {
     CHECK(start <= end);
@@ skipping 26 matching lines @@
 
 
 SemiSpaceIterator::SemiSpaceIterator(Address from, Address to) {
   Initialize(from, to, NULL);
 }
 
 
 void SemiSpaceIterator::Initialize(Address start,
                                    Address end,
                                    HeapObjectCallback size_func) {
-#ifdef DEBUG
-  SemiSpace::ValidateRange(start, end);
-#endif
-  NewSpacePage* page = NewSpacePage::FromAddress(start);
+  SemiSpace::AssertValidRange(start, end);
   current_ = start;
   limit_ = end;
-  current_page_limit_ = page->body_limit();
   size_func_ = size_func;
 }
 
 
 #ifdef DEBUG
 // heap_histograms is shared, always clear it before using it.
 static void ClearHistograms() {
   Isolate* isolate = Isolate::Current();
   // We reset the name each time, though it hasn't changed.
 #define DEF_TYPE_NAME(name) isolate->heap_histograms()[name].set_name(#name);
@@ skipping 1078 matching lines @@
   for (HeapObject* obj = obj_it.Next(); obj != NULL; obj = obj_it.Next()) {
     if (obj->IsCode()) {
       Code* code = Code::cast(obj);
       isolate->code_kind_statistics()[code->kind()] += code->Size();
     }
   }
 }
 #endif  // DEBUG
 
 } }  // namespace v8::internal