Two-page newspace.

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 401 matching lines @@
                                        : MemoryChunk::IN_TO_SPACE));
   heap->incremental_marking()->SetNewSpacePageFlags(chunk);
   return static_cast<NewSpacePage*>(chunk);
 }
 
 
 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);
 }
 
 
 MemoryChunk* MemoryChunk::Initialize(Heap* heap,
                                      Address base,
                                      size_t size,
                                      Executability executable,
                                      Space* owner) {
   MemoryChunk* chunk = FromAddress(base);
 
@@ skipping 525 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_.high();
+  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_.high();
+  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();
   ASSERT_SEMISPACE_ALLOCATION_INFO(allocation_info_, to_space_);
 }
 
 
 void NewSpace::ResetAllocationInfo() {
   to_space_.Reset();
-  allocation_info_.top = to_space_.page_low();
-  allocation_info_.limit = to_space_.high();
-  ASSERT_SEMISPACE_ALLOCATION_INFO(allocation_info_, to_space_);
+  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()) {
+    // 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
+// 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.
-  Address current = to_space_.low();
-  while (current < top()) {
+  NewSpacePage* page = to_space_.first_page();
+  Address current = page->body();
+  CHECK_EQ(current, to_space_.space_low());
+  CHECK(end_page->ContainsLimit(top()));
+
+  while (current != top()) {
+    if (current == page->body_limit()) {
+      // At end of page, switch to next page.
+      page = page->next_page();
+      // Next page should be valid.
+      CHECK(!page->is_anchor());
+      current = page->body();
+    }
+    // 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;
   }
 
-  // The allocation pointer should not be in the middle of an object.
-  ASSERT(current == top());
-
   // Check semi-spaces.
   ASSERT_EQ(from_space_.id(), kFromSpace);
   ASSERT_EQ(to_space_.id(), kToSpace);
   from_space_.Verify();
   to_space_.Verify();
 }
 #endif
 
 
 bool SemiSpace::Commit() {
   ASSERT(!is_committed());
+  // TODO(gc): Rewrite completely when switching to n-page new-space.
+  // Create one page.
+  int pagesize = Page::kPageSize;
   if (!heap()->isolate()->memory_allocator()->CommitBlock(
-      start_, capacity_, executable())) {
+      start_, pagesize, executable())) {
     return false;
   }
-  committed_ = true;
-  // TODO(gc): When more than one page is present, initialize and
-  // chain them all.
   NewSpacePage* page = NewSpacePage::Initialize(heap(), start_, this);
   page->InsertAfter(&anchor_);
-  current_page_ = anchor_.next_page();
+
+  // Maybe create a second.
+  if (capacity_ >= 2 * pagesize) {
+    Address last_page_address =
+      start_ + ((capacity_ - pagesize) & ~Page::kPageAlignmentMask);
+    if (heap()->isolate()->memory_allocator()->CommitBlock(
+        last_page_address, pagesize, executable())) {
+      NewSpacePage* last_page = NewSpacePage::Initialize(heap(),
+                                                         last_page_address,
+                                                         this);
+      last_page->InsertAfter(page);
+    } else {
+      UNREACHABLE();  // TODO(gc): Don't rely on this. Splitting the commit
+                      // is only temporary.
+    }
+  }
+
+  committed_ = true;
+  Reset();
   return true;
 }
 
 
 bool SemiSpace::Uncommit() {
   ASSERT(is_committed());
-  if (!heap()->isolate()->memory_allocator()->UncommitBlock(
-      start_, capacity_)) {
-    return false;
+  // TODO(gc): Rewrite completely when switching to n-page new-space.
+  NewSpacePage* last_page = anchor()->prev_page();
+  while (last_page != anchor()) {
+    NewSpacePage* temp_page = last_page->prev_page();
+    last_page->Unlink();
+    if (!heap()->isolate()->memory_allocator()->UncommitBlock(
+      last_page->address(), Page::kPageSize)) {
+      return false;
+    }
+    last_page = temp_page;
   }
+
   committed_ = false;
   return true;
 }
 
 
 void SemiSpace::Reset() {
   ASSERT(anchor_.next_page() != &anchor_);
   current_page_ = anchor_.next_page();
 }
 
@@ skipping 25 matching lines @@
 bool SemiSpace::Setup(Address start,
                       int initial_capacity,
                       int maximum_capacity) {
   // Creates a space in the young generation. The constructor does not
   // allocate memory from the OS.  A SemiSpace is given a contiguous chunk of
   // memory of size 'capacity' when set up, and does not grow or shrink
   // otherwise.  In the mark-compact collector, the memory region of the from
   // space is used as the marking stack. It requires contiguous memory
   // addresses.
   ASSERT(maximum_capacity >= Page::kPageSize);
-  if (initial_capacity < Page::kPageSize) {
-    initial_capacity = Page::kPageSize;
-  } else {
-    initial_capacity &= ~Page::kPageAlignmentMask;
-  }
-  initial_capacity_ = initial_capacity;
+  initial_capacity_ = initial_capacity & ~Page::kPageAlignmentMask;
   capacity_ = initial_capacity;
   maximum_capacity_ = maximum_capacity;
   committed_ = false;
   start_ = start;
   address_mask_ = ~(maximum_capacity - 1);
   object_mask_ = address_mask_ | kHeapObjectTagMask;
   object_expected_ = reinterpret_cast<uintptr_t>(start) | kHeapObjectTag;
   age_mark_ = start_;
 
   return Commit();
 }
 
 
 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(
-      high(), extra, executable())) {
+      space_high(), extra, executable())) {
     return false;
   }
   capacity_ += extra;
   return true;
 }
 
 
 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_);
   size_t delta = new_capacity - capacity_;
   ASSERT(IsAligned(delta, OS::AllocateAlignment()));
   if (!heap()->isolate()->memory_allocator()->CommitBlock(
-      high(), delta, executable())) {
+      space_high(), delta, executable())) {
     return false;
   }
   capacity_ = new_capacity;
   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(
-      high() - delta, delta)) {
+      space_high() - delta, delta)) {
     return false;
   }
   capacity_ = new_capacity;
   return true;
 }
 
 
 void SemiSpace::FlipPages(intptr_t flags, intptr_t mask) {
   anchor_.set_owner(this);
   // Fixup back-pointers to anchor. Address of anchor changes
@@ skipping 33 matching lines @@
     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->prev_page()->next_page() == page);
     page = page->next_page();
   }
 }
+
+
+void SemiSpace::ValidateRange(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);
+  } else {
+    while (page != end_page) {
+      page = page->next_page();
+      CHECK_NE(page, space->anchor());
+    }
+  }
+}
 #endif
 
 
 // -----------------------------------------------------------------------------
 // SemiSpaceIterator implementation.
 SemiSpaceIterator::SemiSpaceIterator(NewSpace* space) {
-  Initialize(space, space->bottom(), space->top(), NULL);
+  Initialize(space->bottom(), space->top(), NULL);
 }
 
 
 SemiSpaceIterator::SemiSpaceIterator(NewSpace* space,
                                      HeapObjectCallback size_func) {
-  Initialize(space, space->bottom(), space->top(), size_func);
+  Initialize(space->bottom(), space->top(), size_func);
 }
 
 
 SemiSpaceIterator::SemiSpaceIterator(NewSpace* space, Address start) {
-  Initialize(space, start, space->top(), NULL);
+  Initialize(start, space->top(), NULL);
 }
 
 
-void SemiSpaceIterator::Initialize(NewSpace* space,
-                                   Address start,
+SemiSpaceIterator::SemiSpaceIterator(Address from, Address to) {
+  Initialize(from, to, NULL);
+}
+
+
+void SemiSpaceIterator::Initialize(Address start,
                                    Address end,
                                    HeapObjectCallback size_func) {
-  ASSERT(space->ToSpaceContains(start));
-  ASSERT(space->ToSpaceLow() <= end
-         && end <= space->ToSpaceHigh());
-  space_ = &space->to_space_;
+#ifdef DEBUG
+  SemiSpace::ValidateRange(start, end);
+#endif
+  NewSpacePage* page = NewSpacePage::FromAddress(start);
   current_ = start;
-  NewSpacePage* page = NewSpacePage::FromAddress(start);
-  current_page_limit_ = page->body() + page->body_size();
-  if (current_page_limit_ > end) current_page_limit_ = end;
   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 1077 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