[heap] Non-contiguous young generation

src/heap/spaces.h

Index: src/heap/spaces.h
diff --git a/src/heap/spaces.h b/src/heap/spaces.h
index dd23bbc7714d4af766a6ccb9052bb96dd2d163a0..47722fbf4853af4147cf703d929f5d6a3bcdab61 100644
--- a/src/heap/spaces.h
+++ b/src/heap/spaces.h
@@ -27,6 +27,7 @@ class FreeList;
 class Isolate;
 class MemoryAllocator;
 class MemoryChunk;
+class NewSpacePage;
 class Page;
 class PagedSpace;
 class SemiSpace;
@@ -1246,6 +1247,11 @@ class SkipList {
 //
 class MemoryAllocator {
  public:
+  enum AllocationMode {
+    kRegular,
+    kPooled,
+  };
+
   explicit MemoryAllocator(Isolate* isolate);
 
   // Initializes its internal bookkeeping structures.
@@ -1254,8 +1260,13 @@ class MemoryAllocator {
 
   void TearDown();
 
-  Page* AllocatePage(intptr_t size, PagedSpace* owner,
-                     Executability executable);
+  // Allocates either Page or NewSpacePage from the allocator. AllocationMode
+  // is used to indicate whether pooled allocation, which only works for
+  // MemoryChunk::kPageSize, should be tried first.
+  template <typename PageType, MemoryAllocator::AllocationMode mode = kRegular,
+            typename SpaceType>
+  inline PageType* AllocatePage(intptr_t size, SpaceType* owner,

[Michael Lippautz, 2016/04/05 07:57:42]

In another CL I would then also merge AllocateLargePage into this one.

+                                Executability executable);
 
   LargePage* AllocateLargePage(intptr_t object_size, Space* owner,
                                Executability executable);
@@ -1271,6 +1282,9 @@ class MemoryAllocator {
   // together.
   void Free(MemoryChunk* chunk);
 
+  // Free that chunk into the pool.
+  void FreePooled(MemoryChunk* chunk);
+
   // Returns allocated spaces in bytes.
   intptr_t Size() { return size_.Value(); }
 
@@ -1322,8 +1336,6 @@ class MemoryAllocator {
 
   bool CommitMemory(Address addr, size_t size, Executability executable);
 
-  void FreeNewSpaceMemory(Address addr, base::VirtualMemory* reservation,
-                          Executability executable);
   void FreeMemory(base::VirtualMemory* reservation, Executability executable);
   void FreeMemory(Address addr, size_t size, Executability executable);
 
@@ -1376,6 +1388,10 @@ class MemoryAllocator {
                                               size_t reserved_size);
 
  private:
+  // See AllocatePage for public interface.
+  template <typename SpaceType>
+  MemoryChunk* AllocatePagePooled(SpaceType* owner, Executability executable);
+
   Isolate* isolate_;
 
   // Maximum space size in bytes.
@@ -1429,6 +1445,8 @@ class MemoryAllocator {
     } while ((high > ptr) && !highest_ever_allocated_.TrySetValue(ptr, high));
   }
 
+  List<MemoryChunk*> chunk_pool_;
+
   DISALLOW_IMPLICIT_CONSTRUCTORS(MemoryAllocator);
 };
 
@@ -2269,6 +2287,10 @@ enum SemiSpaceId { kFromSpace = 0, kToSpace = 1 };
 
 class NewSpacePage : public MemoryChunk {
  public:
+  static inline NewSpacePage* Initialize(Heap* heap, MemoryChunk* chunk,
+                                         Executability executable,
+                                         SemiSpace* owner);
+
   static bool IsAtStart(Address addr) {
     return (reinterpret_cast<intptr_t>(addr) & Page::kPageAlignmentMask) ==
            kObjectStartOffset;
@@ -2326,9 +2348,6 @@ class NewSpacePage : public MemoryChunk {
   // for the doubly-linked list of real pages.
   explicit NewSpacePage(SemiSpace* owner) { InitializeAsAnchor(owner); }
 
-  static NewSpacePage* Initialize(Heap* heap, Address start,
-                                  SemiSpace* semi_space);
-
   // Intialize a fake NewSpacePage used as sentinel at the ends
   // of a doubly-linked list of real NewSpacePages.
   // Only uses the prev/next links, and sets flags to not be in new-space.
@@ -2354,7 +2373,6 @@ class SemiSpace : public Space {
         current_capacity_(0),
         maximum_capacity_(0),
         minimum_capacity_(0),
-        start_(nullptr),
         age_mark_(nullptr),
         committed_(false),
         id_(semispace),
@@ -2365,39 +2383,38 @@ class SemiSpace : public Space {
   inline bool Contains(Object* o);
   inline bool ContainsSlow(Address a);
 
-  // Creates a space in the young generation. The constructor does not
-  // allocate memory from the OS.
-  void SetUp(Address start, int initial_capacity, int maximum_capacity);
-
-  // Tear down the space.  Heap memory was not allocated by the space, so it
-  // is not deallocated here.
+  void SetUp(int initial_capacity, int maximum_capacity);
   void TearDown();
+  bool HasBeenSetUp() { return maximum_capacity_ != 0; }
 
-  // True if the space has been set up but not torn down.
-  bool HasBeenSetUp() { return start_ != nullptr; }
+  bool Commit();
+  bool Uncommit();
+  bool is_committed() { return committed_; }
 
-  // Grow the semispace to the new capacity.  The new capacity
-  // requested must be larger than the current capacity and less than
-  // the maximum capacity.
+  // Grow the semispace to the new capacity.  The new capacity requested must
+  // be larger than the current capacity and less than the maximum capacity.
   bool GrowTo(int new_capacity);
 
-  // Shrinks the semispace to the new capacity.  The new capacity
-  // requested must be more than the amount of used memory in the
-  // semispace and less than the current capacity.
+  // Shrinks the semispace to the new capacity.  The new capacity requested
+  // must be more than the amount of used memory in the semispace and less
+  // than the current capacity.
   bool ShrinkTo(int new_capacity);
 
   // Returns the start address of the first page of the space.
   Address space_start() {
-    DCHECK_NE(anchor_.next_page(), &anchor_);
+    DCHECK_NE(anchor_.next_page(), anchor());
     return anchor_.next_page()->area_start();
   }
 
-  // Returns the start address of the current page of the space.
-  Address page_low() { return current_page_->area_start(); }
+  NewSpacePage* first_page() { return anchor_.next_page(); }
+  NewSpacePage* current_page() { return current_page_; }
 
   // Returns one past the end address of the space.
   Address space_end() { return anchor_.prev_page()->area_end(); }
 
+  // Returns the start address of the current page of the space.
+  Address page_low() { return current_page_->area_start(); }
+
   // Returns one past the end address of the current page of the space.
   Address page_high() { return current_page_->area_end(); }
 
@@ -2415,17 +2432,10 @@ class SemiSpace : public Space {
   Address age_mark() { return age_mark_; }
   void set_age_mark(Address mark);
 
-  bool is_committed() { return committed_; }
-  bool Commit();
-  bool Uncommit();
-
-  NewSpacePage* first_page() { return anchor_.next_page(); }
-  NewSpacePage* current_page() { return current_page_; }
-
-  // Returns the current total capacity of the semispace.
+  // Returns the current capacity of the semispace.
   int current_capacity() { return current_capacity_; }
 
-  // Returns the maximum total capacity of the semispace.
+  // Returns the maximum capacity of the semispace.
   int maximum_capacity() { return maximum_capacity_; }
 
   // Returns the initial capacity of the semispace.
@@ -2467,11 +2477,7 @@ class SemiSpace : public Space {
 #endif
 
  private:
-  NewSpacePage* anchor() { return &anchor_; }
-
-  void set_current_capacity(int new_capacity) {
-    current_capacity_ = new_capacity;
-  }
+  inline NewSpacePage* anchor() { return &anchor_; }
 
   // Copies the flags into the masked positions on all pages in the space.
   void FixPagesFlags(intptr_t flags, intptr_t flag_mask);
@@ -2482,11 +2488,9 @@ class SemiSpace : public Space {
   // The maximum capacity that can be used by this space.
   int maximum_capacity_;
 
-  // The mimnimum capacity for the space. A space cannot shrink below this size.
+  // The minimum capacity for the space. A space cannot shrink below this size.
   int minimum_capacity_;
 
-  // The start address of the space.
-  Address start_;
   // Used to govern object promotion during mark-compact collection.
   Address age_mark_;
 
@@ -2562,20 +2566,21 @@ class NewSpacePageIterator BASE_EMBEDDED {
 
 class NewSpace : public Space {
  public:
-  // Constructor.
   explicit NewSpace(Heap* heap)
       : Space(heap, NEW_SPACE, NOT_EXECUTABLE),
         to_space_(heap, kToSpace),
         from_space_(heap, kFromSpace),
         reservation_(),
-        top_on_previous_step_(0) {}
+        pages_used_(0),
+        top_on_previous_step_(0),
+        allocated_histogram_(nullptr),
+        promoted_histogram_(nullptr) {}
 
   inline bool Contains(HeapObject* o);
   inline bool ContainsSlow(Address a);
   inline bool Contains(Object* o);
 
-  // Sets up the new space using the given chunk.
-  bool SetUp(int reserved_semispace_size_, int max_semi_space_size);
+  bool SetUp(int initial_semispace_capacity, int max_semispace_capacity);
 
   // Tears down the space.  Heap memory was not allocated by the space, so it
   // is not deallocated here.
@@ -2638,22 +2643,39 @@ class NewSpace : public Space {
   // Return the available bytes without growing.
   intptr_t Available() override { return Capacity() - Size(); }
 
-  intptr_t PagesFromStart(Address addr) {
-    return static_cast<intptr_t>(addr - bottom()) / Page::kPageSize;
-  }
-
   size_t AllocatedSinceLastGC() {

[Michael Lippautz, 2016/04/05 07:57:43]

This is roughly 1:1 translation to non-cont. space of the previous behavior.

If this is too slow, we could try to keep a counter. The reason I did not add
the counter in first place is that maintaining it would be distributed
(AllocatedSinceLastGC, Reset, AddFreshPage) and is likely prone to be
out-of-sync.

-    intptr_t allocated = top() - to_space_.age_mark();
-    if (allocated < 0) {
-      // Runtime has lowered the top below the age mark.
+    bool seen_age_mark = false;
+    Address age_mark = to_space_.age_mark();
+    NewSpacePage* current_page = to_space_.first_page();
+    NewSpacePage* age_mark_page = NewSpacePage::FromAddress(age_mark);
+    NewSpacePage* last_page = NewSpacePage::FromAddress(top() - kPointerSize);
+    if (age_mark_page == last_page) {
+      if (top() - age_mark > 0) {

[ulan, 2016/04/05 08:46:25]

Should be (top() - age_mark >= 0) to preserve the previous behavior. 

[Michael Lippautz, 2016/04/05 09:42:34]

Done.

+        return top() - age_mark;
+      }
+      // Top was reset at some point, invalidating this metric.
       return 0;
     }
-    // Correctly account for non-allocatable regions at the beginning of
-    // each page from the age_mark() to the top().
-    intptr_t pages =
-        PagesFromStart(top()) - PagesFromStart(to_space_.age_mark());
-    allocated -= pages * (NewSpacePage::kObjectStartOffset);
-    DCHECK(0 <= allocated && allocated <= Size());
+    while (current_page != last_page) {
+      if (current_page == age_mark_page) {
+        seen_age_mark = true;
+        break;
+      }
+      current_page = current_page->next_page();
+    }
+    if (!seen_age_mark) {
+      // Top was reset at some point, invalidating this metric.
+      return 0;
+    }
+    intptr_t allocated = age_mark_page->area_end() - age_mark;
+    current_page = current_page->next_page();

[ulan, 2016/04/05 08:46:25]

Did you mean current_page = age_mark_page->next_page()?

[Michael Lippautz, 2016/04/05 09:42:34]

current_page == age_mark_page at this point. Added a DCHECK and changed the
assignment.

+    while (current_page != last_page) {
+      allocated += NewSpacePage::kAllocatableMemory;
+      current_page = current_page->next_page();
+    }
+    allocated += top() - current_page->area_start();
+    DCHECK_LE(0, allocated);
+    DCHECK_LE(allocated, Size());
     return static_cast<size_t>(allocated);
   }
 
@@ -2805,9 +2827,6 @@ class NewSpace : public Space {
 
   base::Mutex mutex_;
 
-  Address chunk_base_;
-  uintptr_t chunk_size_;
-
   // The semispaces.
   SemiSpace to_space_;
   SemiSpace from_space_;