Reland "[heap] Introduce parallel compaction algorithm."

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"
@@ skipping 250 matching lines @@
 
 class SkipList;
 class SlotsBuffer;
 
 // MemoryChunk represents a memory region owned by a specific space.
 // It is divided into the header and the body. Chunk start is always
 // 1MB aligned. Start of the body is aligned so it can accommodate
 // any heap object.
 class MemoryChunk {
  public:
+  // |kCompactionDone|: Initial compaction state of a |MemoryChunk|.
+  // |kCompactingInProgress|:  Parallel compaction is currently in progress.
+  // |kCompactingFinalize|: Parallel compaction is done but the chunk needs to
+  //   be finalized.
+  // |kCompactingAborted|: Parallel compaction has been aborted, which should
+  //   for now only happen in OOM scenarios.
+  enum ParallelCompactingState {
+    kCompactingDone,
+    kCompactingInProgress,
+    kCompactingFinalize,
+    kCompactingAborted,
+  };
+
   // Only works if the pointer is in the first kPageSize of the MemoryChunk.
   static MemoryChunk* FromAddress(Address a) {
     return reinterpret_cast<MemoryChunk*>(OffsetFrom(a) & ~kAlignmentMask);
   }
   static const MemoryChunk* FromAddress(const byte* a) {
     return reinterpret_cast<const MemoryChunk*>(OffsetFrom(a) &
                                                 ~kAlignmentMask);
   }
 
   // Only works for addresses in pointer spaces, not data or code spaces.
@@ skipping 170 matching lines @@
 
   ParallelSweepingState parallel_sweeping() {
     return static_cast<ParallelSweepingState>(
         base::Acquire_Load(&parallel_sweeping_));
   }
 
   void set_parallel_sweeping(ParallelSweepingState state) {
     base::Release_Store(&parallel_sweeping_, state);
   }
 
+  AtomicValue<ParallelCompactingState>& parallel_compaction_state() {
+    return parallel_compaction_;
+  }
+
   bool TryLock() { return mutex_->TryLock(); }
 
   base::Mutex* mutex() { return mutex_; }
 
   // WaitUntilSweepingCompleted only works when concurrent sweeping is in
   // progress. In particular, when we know that right before this call a
   // sweeper thread was sweeping this page.
   void WaitUntilSweepingCompleted() {
     mutex_->Lock();
     mutex_->Unlock();
@@ skipping 88 matching lines @@
       kSlotsBufferOffset + kPointerSize  // SlotsBuffer* slots_buffer_;
       + kPointerSize;                    // SkipList* skip_list_;
 
   static const size_t kMinHeaderSize =
       kWriteBarrierCounterOffset +
       kIntptrSize         // intptr_t write_barrier_counter_
       + kIntSize          // int progress_bar_
       + kPointerSize      // AtomicValue high_water_mark_
       + kPointerSize      // base::Mutex* mutex_
       + kPointerSize      // base::AtomicWord parallel_sweeping_
+      + kPointerSize      // AtomicValue parallel_compaction_
       + 5 * kPointerSize  // AtomicNumber free-list statistics
       + kPointerSize      // base::AtomicWord next_chunk_
       + kPointerSize;     // base::AtomicWord prev_chunk_
 
   // We add some more space to the computed header size to amount for missing
   // alignment requirements in our computation.
   // Try to get kHeaderSize properly aligned on 32-bit and 64-bit machines.
   static const size_t kHeaderSize = kMinHeaderSize + kIntSize;
 
   static const int kBodyOffset =
@@ skipping 140 matching lines @@
   intptr_t write_barrier_counter_;
   // Used by the incremental marker to keep track of the scanning progress in
   // large objects that have a progress bar and are scanned in increments.
   int progress_bar_;
   // Assuming the initial allocation on a page is sequential,
   // count highest number of bytes ever allocated on the page.
   AtomicValue<intptr_t> high_water_mark_;
 
   base::Mutex* mutex_;
   base::AtomicWord parallel_sweeping_;
+  AtomicValue<ParallelCompactingState> parallel_compaction_;
 
   // PagedSpace free-list statistics.
   AtomicNumber<intptr_t> available_in_small_free_list_;
   AtomicNumber<intptr_t> available_in_medium_free_list_;
   AtomicNumber<intptr_t> available_in_large_free_list_;
   AtomicNumber<intptr_t> available_in_huge_free_list_;
   AtomicNumber<intptr_t> non_available_small_blocks_;
 
   // next_chunk_ holds a pointer of type MemoryChunk
   base::AtomicWord next_chunk_;
@@ skipping 240 matching lines @@
   // Allocates a chunk of memory from the large-object portion of
   // the code range.  On platforms with no separate code range, should
   // not be called.
   MUST_USE_RESULT Address AllocateRawMemory(const size_t requested_size,
                                             const size_t commit_size,
                                             size_t* allocated);
   bool CommitRawMemory(Address start, size_t length);
   bool UncommitRawMemory(Address start, size_t length);
   void FreeRawMemory(Address buf, size_t length);
 
-  void ReserveEmergencyBlock();
-  void ReleaseEmergencyBlock();
-
  private:
   // Frees the range of virtual memory, and frees the data structures used to
   // manage it.
   void TearDown();
 
   Isolate* isolate_;
 
   // The reserved range of virtual memory that all code objects are put in.
   base::VirtualMemory* code_range_;
   // Plain old data class, just a struct plus a constructor.
@@ skipping 22 matching lines @@
   // Freed blocks of memory are added to the free list.  When the allocation
   // list is exhausted, the free list is sorted and merged to make the new
   // allocation list.
   List<FreeBlock> free_list_;
 
   // Memory is allocated from the free blocks on the allocation list.
   // The block at current_allocation_block_index_ is the current block.
   List<FreeBlock> allocation_list_;
   int current_allocation_block_index_;
 
-  // Emergency block guarantees that we can always allocate a page for
-  // evacuation candidates when code space is compacted. Emergency block is
-  // reserved immediately after GC and is released immedietely before
-  // allocating a page for evacuation.
-  FreeBlock emergency_block_;
-
   // Finds a block on the allocation list that contains at least the
   // requested amount of memory.  If none is found, sorts and merges
   // the existing free memory blocks, and searches again.
   // If none can be found, returns false.
   bool GetNextAllocationBlock(size_t requested);
   // Compares the start addresses of two free blocks.
   static int CompareFreeBlockAddress(const FreeBlock* left,
                                      const FreeBlock* right);
   bool ReserveBlock(const size_t requested_size, FreeBlock* block);
   void ReleaseBlock(const FreeBlock* block);
@@ skipping 461 matching lines @@
   // Merge {other} into {this}.
   void Merge(const AllocationStats& other) {
     capacity_ += other.capacity_;
     size_ += other.size_;
     waste_ += other.waste_;
     if (other.max_capacity_ > max_capacity_) {
       max_capacity_ = other.max_capacity_;
     }
   }
 
+  void DecreaseCapacity(intptr_t size_in_bytes) {
+    capacity_ -= size_in_bytes;
+    DCHECK_GE(capacity_, 0);
+  }
+
+  void IncreaseCapacity(intptr_t size_in_bytes) { capacity_ += size_in_bytes; }
+
  private:
   intptr_t capacity_;
   intptr_t max_capacity_;
   intptr_t size_;
   intptr_t waste_;
 };
 
 
 // -----------------------------------------------------------------------------
 // Free lists for old object spaces
 
 // The free list category holds a pointer to the top element and a pointer to
 // the end element of the linked list of free memory blocks.
 class FreeListCategory {
  public:
-  FreeListCategory() : top_(0), end_(NULL), available_(0) {}
+  explicit FreeListCategory(FreeList* owner)
+      : top_(0), end_(NULL), available_(0), owner_(owner) {}
 
   intptr_t Concatenate(FreeListCategory* category);
 
   void Reset();
 
   void Free(FreeSpace* node, int size_in_bytes);
 
   FreeSpace* PickNodeFromList(int* node_size);
   FreeSpace* PickNodeFromList(int size_in_bytes, int* node_size);
 
@@ skipping 19 matching lines @@
 
   base::Mutex* mutex() { return &mutex_; }
 
   bool IsEmpty() { return top() == 0; }
 
 #ifdef DEBUG
   intptr_t SumFreeList();
   int FreeListLength();
 #endif
 
+  FreeList* owner() { return owner_; }
+
  private:
   // top_ points to the top FreeSpace* in the free list category.
   base::AtomicWord top_;
   FreeSpace* end_;
   base::Mutex mutex_;
 
   // Total available bytes in all blocks of this free list category.
   int available_;
+
+  FreeList* owner_;
 };
 
 
 // The free list for the old space.  The free list is organized in such a way
 // as to encourage objects allocated around the same time to be near each
 // other.  The normal way to allocate is intended to be by bumping a 'top'
 // pointer until it hits a 'limit' pointer.  When the limit is hit we need to
 // find a new space to allocate from.  This is done with the free list, which
 // is divided up into rough categories to cut down on waste.  Having finer
 // categories would scatter allocation more.
@@ skipping 72 matching lines @@
   void RepairLists(Heap* heap);
 
   intptr_t EvictFreeListItems(Page* p);
   bool ContainsPageFreeListItems(Page* p);
 
   FreeListCategory* small_list() { return &small_list_; }
   FreeListCategory* medium_list() { return &medium_list_; }
   FreeListCategory* large_list() { return &large_list_; }
   FreeListCategory* huge_list() { return &huge_list_; }
 
+  PagedSpace* owner() { return owner_; }
+
  private:
   // The size range of blocks, in bytes.
   static const int kMinBlockSize = 3 * kPointerSize;
   static const int kMaxBlockSize = Page::kMaxRegularHeapObjectSize;
 
   static const int kSmallListMin = 0x1f * kPointerSize;
   static const int kSmallListMax = 0xff * kPointerSize;
   static const int kMediumListMax = 0x7ff * kPointerSize;
   static const int kLargeListMax = 0x3fff * kPointerSize;
   static const int kSmallAllocationMax = kSmallListMin;
@@ skipping 276 matching lines @@
   void EvictEvacuationCandidatesFromFreeLists();
 
   bool CanExpand(size_t size);
 
   // Returns the number of total pages in this space.
   int CountTotalPages();
 
   // Return size of allocatable area on a page in this space.
   inline int AreaSize() { return area_size_; }
 
-  void CreateEmergencyMemory();
-  void FreeEmergencyMemory();
-  void UseEmergencyMemory();
-  intptr_t MaxEmergencyMemoryAllocated();
-
-  bool HasEmergencyMemory() { return emergency_memory_ != NULL; }
-
   // Merges {other} into the current space. Note that this modifies {other},
   // e.g., removes its bump pointer area and resets statistics.
   void MergeCompactionSpace(CompactionSpace* other);
 
+  void MoveOverFreeMemory(PagedSpace* other);
+
+  virtual bool is_local() { return false; }
+
  protected:
   // PagedSpaces that should be included in snapshots have different, i.e.,
   // smaller, initial pages.
   virtual bool snapshotable() { return true; }
 
   FreeList* free_list() { return &free_list_; }
 
   bool HasPages() { return anchor_.next_page() != &anchor_; }
 
   // Cleans up the space, frees all pages in this space except those belonging
@@ skipping 40 matching lines @@
 
   // The number of free bytes which could be reclaimed by advancing the
   // concurrent sweeper threads.
   intptr_t unswept_free_bytes_;
 
   // The sweeper threads iterate over the list of pointer and data space pages
   // and sweep these pages concurrently. They will stop sweeping after the
   // end_of_unswept_pages_ page.
   Page* end_of_unswept_pages_;
 
-  // Emergency memory is the memory of a full page for a given space, allocated
-  // conservatively before evacuating a page. If compaction fails due to out
-  // of memory error the emergency memory can be used to complete compaction.
-  // If not used, the emergency memory is released after compaction.
-  MemoryChunk* emergency_memory_;
-
   // Mutex guarding any concurrent access to the space.
   base::Mutex space_mutex_;
 
   friend class MarkCompactCollector;
   friend class PageIterator;
 };
 
 
 class NumberAndSizeInfo BASE_EMBEDDED {
  public:
@@ skipping 673 matching lines @@
  public:
   CompactionSpace(Heap* heap, AllocationSpace id, Executability executable)
       : PagedSpace(heap, id, executable) {}
 
   // Adds external memory starting at {start} of {size_in_bytes} to the space.
   void AddExternalMemory(Address start, int size_in_bytes) {
     IncreaseCapacity(size_in_bytes);
     Free(start, size_in_bytes);
   }
 
+  virtual bool is_local() { return true; }
+
  protected:
   // The space is temporary and not included in any snapshots.
   virtual bool snapshotable() { return false; }
 };
 
 
+// A collection of |CompactionSpace|s used by a single compaction task.
+class CompactionSpaceCollection : public Malloced {
+ public:
+  explicit CompactionSpaceCollection(Heap* heap)
+      : old_space_(heap, OLD_SPACE, Executability::NOT_EXECUTABLE),
+        code_space_(heap, CODE_SPACE, Executability::EXECUTABLE) {}
+
+  CompactionSpace* Get(AllocationSpace space) {
+    switch (space) {
+      case OLD_SPACE:
+        return &old_space_;
+      case CODE_SPACE:
+        return &code_space_;
+      default:
+        UNREACHABLE();
+    }
+    UNREACHABLE();
+    return nullptr;
+  }
+
+ private:
+  CompactionSpace old_space_;
+  CompactionSpace code_space_;
+};
+
+
 // -----------------------------------------------------------------------------
 // Old object space (includes the old space of objects and code space)
 
 class OldSpace : public PagedSpace {
  public:
   // Creates an old space object. The constructor does not allocate pages
   // from OS.
   OldSpace(Heap* heap, AllocationSpace id, Executability executable)
       : PagedSpace(heap, id, executable) {}
 };
@@ skipping 180 matching lines @@
     count = 0;
   }
   // Must be small, since an iteration is used for lookup.
   static const int kMaxComments = 64;
 };
 #endif
 }
 }  // namespace v8::internal
 
 #endif  // V8_HEAP_SPACES_H_