[heap] Non-contiguous young generation

src/heap/spaces.h

 // Copyright 2011 the V8 project authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #ifndef V8_HEAP_SPACES_H_
 #define V8_HEAP_SPACES_H_
 
 #include "src/allocation.h"
 #include "src/atomic-utils.h"
 #include "src/base/atomicops.h"
 #include "src/base/bits.h"
 #include "src/base/platform/mutex.h"
 #include "src/flags.h"
 #include "src/hashmap.h"
 #include "src/list.h"
 #include "src/objects.h"
 #include "src/utils.h"
 
 namespace v8 {
 namespace internal {
 
 class AllocationInfo;
 class AllocationObserver;
 class CompactionSpace;
 class CompactionSpaceCollection;
 class FreeList;
 class Isolate;
 class MemoryAllocator;
 class MemoryChunk;
+class NewSpacePage;
 class Page;
 class PagedSpace;
 class SemiSpace;
 class SkipList;
 class SlotsBuffer;
 class SlotSet;
 class TypedSlotSet;
 class Space;
 
 // -----------------------------------------------------------------------------
@@ skipping 1199 matching lines @@
 
 // ----------------------------------------------------------------------------
 // A space acquires chunks of memory from the operating system. The memory
 // allocator allocated and deallocates pages for the paged heap spaces and large
 // pages for large object space.
 //
 // Each space has to manage it's own pages.
 //
 class MemoryAllocator {
  public:
+  enum AllocationMode {
+    kRegular,
+    kPooled,
+  };
+
   explicit MemoryAllocator(Isolate* isolate);
 
   // Initializes its internal bookkeeping structures.
   // Max capacity of the total space and executable memory limit.
   bool SetUp(intptr_t max_capacity, intptr_t capacity_executable);
 
   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>
+  PageType* AllocatePage(intptr_t size, SpaceType* owner,
+                         Executability executable);
 
   LargePage* AllocateLargePage(intptr_t object_size, Space* owner,
                                Executability executable);
 
   // PreFree logically frees the object, i.e., it takes care of the size
   // bookkeeping and calls the allocation callback.
   void PreFreeMemory(MemoryChunk* chunk);
 
   // FreeMemory can be called concurrently when PreFree was executed before.
   void PerformFreeMemory(MemoryChunk* chunk);
 
   // Free is a wrapper method, which calls PreFree and PerformFreeMemory
   // together.
   void Free(MemoryChunk* chunk);

[Hannes Payer (out of office), 2016/04/05 12:38:49]

Maybe also templatize Free?

[Michael Lippautz, 2016/04/05 12:47:59]

Done.

 
+  // Free that chunk into the pool.
+  void FreePooled(MemoryChunk* chunk);
+
   // Returns allocated spaces in bytes.
   intptr_t Size() { return size_.Value(); }
 
   // Returns allocated executable spaces in bytes.
   intptr_t SizeExecutable() { return size_executable_.Value(); }
 
   // Returns the maximum available bytes of heaps.
   intptr_t Available() {
     intptr_t size = Size();
     return capacity_ < size ? 0 : capacity_ - size;
@@ skipping 31 matching lines @@
                              Executability executable, Space* space);
 
   Address ReserveAlignedMemory(size_t requested, size_t alignment,
                                base::VirtualMemory* controller);
   Address AllocateAlignedMemory(size_t reserve_size, size_t commit_size,
                                 size_t alignment, Executability executable,
                                 base::VirtualMemory* controller);
 
   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);
 
   // Commit a contiguous block of memory from the initial chunk.  Assumes that
   // the address is not NULL, the size is greater than zero, and that the
   // block is contained in the initial chunk.  Returns true if it succeeded
   // and false otherwise.
   bool CommitBlock(Address start, size_t size, Executability executable);
 
   // Uncommit a contiguous block of memory [start..(start+size)[.
@@ skipping 32 matching lines @@
     DCHECK_NE(LO_SPACE, space);
     return (space == CODE_SPACE) ? CodePageAreaSize()
                                  : Page::kAllocatableMemory;
   }
 
   MUST_USE_RESULT bool CommitExecutableMemory(base::VirtualMemory* vm,
                                               Address start, size_t commit_size,
                                               size_t reserved_size);
 
  private:
+  // See AllocatePage for public interface. Note that currently we only support
+  // pools for NOT_EXECUTABLE pages of size MemoryChunk::kPageSize.
+  template <typename SpaceType>
+  MemoryChunk* AllocatePagePooled(SpaceType* owner);
+
   Isolate* isolate_;
 
   // Maximum space size in bytes.
   intptr_t capacity_;
   // Maximum subset of capacity_ that can be executable
   intptr_t capacity_executable_;
 
   // Allocated space size in bytes.
   AtomicNumber<intptr_t> size_;
   // Allocated executable space size in bytes.
@@ skipping 33 matching lines @@
     // values only if they did not change in between.
     void* ptr = nullptr;
     do {
       ptr = lowest_ever_allocated_.Value();
     } while ((low < ptr) && !lowest_ever_allocated_.TrySetValue(ptr, low));
     do {
       ptr = highest_ever_allocated_.Value();
     } while ((high > ptr) && !highest_ever_allocated_.TrySetValue(ptr, high));
   }
 
+  List<MemoryChunk*> chunk_pool_;
+
   DISALLOW_IMPLICIT_CONSTRUCTORS(MemoryAllocator);
 };
 
 
 // -----------------------------------------------------------------------------
 // Interface for heap object iterator to be implemented by all object space
 // object iterators.
 //
 // NOTE: The space specific object iterators also implements the own next()
 //       method which is used to avoid using virtual functions
@@ skipping 820 matching lines @@
  private:
   const char* name_;
 };
 
 
 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;
   }
 
   static bool IsAtEnd(Address addr) {
     return (reinterpret_cast<intptr_t>(addr) & Page::kPageAlignmentMask) == 0;
   }
 
   // Finds the NewSpacePage containing the given address.
@@ skipping 37 matching lines @@
   // GC related flags copied from from-space to to-space when
   // flipping semispaces.
   static const intptr_t kCopyOnFlipFlagsMask =
       (1 << MemoryChunk::POINTERS_TO_HERE_ARE_INTERESTING) |
       (1 << MemoryChunk::POINTERS_FROM_HERE_ARE_INTERESTING);
 
   // Create a NewSpacePage object that is only used as anchor
   // 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.
   void InitializeAsAnchor(SemiSpace* owner);
 
   friend class SemiSpace;
   friend class SemiSpaceIterator;
 };
 
 
 // -----------------------------------------------------------------------------
 // SemiSpace in young generation
 //
 // A SemiSpace is a contiguous chunk of memory holding page-like memory chunks.
 // The mark-compact collector  uses the memory of the first page in the from
 // space as a marking stack when tracing live objects.
 class SemiSpace : public Space {
  public:
   static void Swap(SemiSpace* from, SemiSpace* to);
 
   SemiSpace(Heap* heap, SemiSpaceId semispace)
       : Space(heap, NEW_SPACE, NOT_EXECUTABLE),
         current_capacity_(0),
         maximum_capacity_(0),
         minimum_capacity_(0),
-        start_(nullptr),
         age_mark_(nullptr),
         committed_(false),
         id_(semispace),
         anchor_(this),
         current_page_(nullptr) {}
 
   inline bool Contains(HeapObject* o);
   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);
+  void SetUp(int initial_capacity, int maximum_capacity);
+  void TearDown();
+  bool HasBeenSetUp() { return maximum_capacity_ != 0; }
 
-  // Tear down the space.  Heap memory was not allocated by the space, so it
-  // is not deallocated here.
-  void TearDown();
+  bool Commit();
+  bool Uncommit();
+  bool is_committed() { return committed_; }
 
-  // True if the space has been set up but not torn down.
-  bool HasBeenSetUp() { return start_ != nullptr; }
-
-  // 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();
   }
 
+  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 space.
-  Address space_end() { return anchor_.prev_page()->area_end(); }
-
   // Returns one past the end address of the current page of the space.
   Address page_high() { return current_page_->area_end(); }
 
   bool AdvancePage() {
     NewSpacePage* next_page = current_page_->next_page();
     if (next_page == anchor()) return false;
     current_page_ = next_page;
     return true;
   }
 
   // Resets the space to using the first page.
   void Reset();
 
   // Age mark accessors.
   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.
   int minimum_capacity() { return minimum_capacity_; }
 
   SemiSpaceId id() { return id_; }
 
   // Approximate amount of physical memory committed for this space.
   size_t CommittedPhysicalMemory() override;
 
@@ skipping 21 matching lines @@
 #else
   // Do nothing.
   inline static void AssertValidRange(Address from, Address to) {}
 #endif
 
 #ifdef VERIFY_HEAP
   virtual void Verify();
 #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);
 
   // The currently committed space capacity.
   int current_capacity_;
 
   // 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_;
 
   bool committed_;
   SemiSpaceId id_;
 
   NewSpacePage anchor_;
   NewSpacePage* current_page_;
 
   friend class SemiSpaceIterator;
@@ skipping 55 matching lines @@
 
 
 // -----------------------------------------------------------------------------
 // The young generation space.
 //
 // The new space consists of a contiguous pair of semispaces.  It simply
 // forwards most functions to the appropriate semispace.
 
 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.
   void TearDown();
 
   // True if the space has been set up but not torn down.
   bool HasBeenSetUp() {
     return to_space_.HasBeenSetUp() && from_space_.HasBeenSetUp();
   }
 
@@ skipping 42 matching lines @@
     return from_space_.MaximumCommittedMemory() +
            to_space_.MaximumCommittedMemory();
   }
 
   // Approximate amount of physical memory committed for this space.
   size_t CommittedPhysicalMemory() override;
 
   // 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() {
-    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;

[Hannes Payer (out of office), 2016/04/05 12:38:49]

Maybe we should fix this function at some point to
a) Always return allocated bytes when allocations happened, i.e., not return 0
when top was reset
b) Don't count fragmentation as allocated for fully used pages. Fragmentation
can be high due to big objects in new space.

[Michael Lippautz, 2016/04/05 12:47:59]

Ack.

+    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) {
+        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;
+    DCHECK_EQ(current_page, age_mark_page);
+    current_page = age_mark_page->next_page();
+    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);
   }
 
   // Return the maximum capacity of a semispace.
   int MaximumCapacity() {
     DCHECK(to_space_.maximum_capacity() == from_space_.maximum_capacity());
     return to_space_.maximum_capacity();
   }
 
   bool IsAtMaximumCapacity() { return TotalCapacity() == MaximumCapacity(); }
@@ skipping 131 matching lines @@
 
   void PauseAllocationObservers() override;
   void ResumeAllocationObservers() override;
 
  private:
   // Update allocation info to match the current to-space page.
   void UpdateAllocationInfo();
 
   base::Mutex mutex_;
 
-  Address chunk_base_;
-  uintptr_t chunk_size_;
-
   // The semispaces.
   SemiSpace to_space_;
   SemiSpace from_space_;
   base::VirtualMemory reservation_;
   int pages_used_;
 
   // Allocation pointer and limit for normal allocation and allocation during
   // mark-compact collection.
   AllocationInfo allocation_info_;
 
@@ skipping 264 matching lines @@
     count = 0;
   }
   // Must be small, since an iteration is used for lookup.
   static const int kMaxComments = 64;
 };
 #endif
 }  // namespace internal
 }  // namespace v8
 
 #endif  // V8_HEAP_SPACES_H_