[not for landing, heap] Parallel compaction in main GC pause

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|.
+  // |kCompactingFinalize|: Parallel compaction is done but the chunk needs to
+  //   be finalized.
+  // |kCompactingInProgress|:  Parallel compaction is currently in progress.
+  // |kCompactingAborted|: Parallel compaction has been aborted, which should
+  //   for now only happen in OOM scenarios.
+  // |kNoEvacuationCandidate|: Page was no evacuation candidate by the time the
+  //   compactor inspected it.
+  enum ParallelCompactingState {
+    kCompactingDone,
+    kCompactingFinalize,
+    kCompactingInProgress,
+    kCompactingAborted,
+    kNoEvacuationCandidate,
+  };
+
   // 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      // AtomicFlag 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 108 matching lines @@
     // to another chunk. See the comment to Page::FromAllocationTop.
     MemoryChunk* chunk = MemoryChunk::FromAddress(mark - 1);
     intptr_t new_mark = static_cast<intptr_t>(mark - chunk->address());
     intptr_t old_mark = 0;
     do {
       old_mark = chunk->high_water_mark_.Value();
     } while ((new_mark > old_mark) &&
              !chunk->high_water_mark_.TrySetValue(old_mark, new_mark));
   }
 
+
+#define FRAGMENTATION_STATS_ACCESSORS(type, name)        \
+  type name() { return name##_.Value(); }                \
+  void set_##name(type name) { name##_.SetValue(name); } \
+  void add_##name(type name) { name##_.Increment(name); }
+
+  FRAGMENTATION_STATS_ACCESSORS(intptr_t, non_available_small_blocks)
+  FRAGMENTATION_STATS_ACCESSORS(intptr_t, available_in_small_free_list)
+  FRAGMENTATION_STATS_ACCESSORS(intptr_t, available_in_medium_free_list)
+  FRAGMENTATION_STATS_ACCESSORS(intptr_t, available_in_large_free_list)
+  FRAGMENTATION_STATS_ACCESSORS(intptr_t, available_in_huge_free_list)
+
+#undef FRAGMENTATION_STATS_ACCESSORS
+
  protected:
   size_t size_;
   intptr_t flags_;
 
   // Start and end of allocatable memory on this chunk.
   Address area_start_;
   Address area_end_;
 
   // If the chunk needs to remember its memory reservation, it is stored here.
   base::VirtualMemory reservation_;
@@ skipping 12 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 275 matching lines @@
     }
 
     Address start;
     size_t size;
   };
 
   // The global mutex guards free_list_ and allocation_list_ as GC threads may
   // access both lists concurrently to the main thread.
   base::Mutex code_range_mutex_;
 
+  // ReserveBlock can be calleed concurrently. TODO: Merge this into a single
+  // lock for CodeRange.
+  base::Mutex reserve_block_mutex_;
+
   // 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_;
 
@@ skipping 572 matching lines @@
 //     and limit when the object we need to allocate is 256-2047 words in size.
 //     These spaces are call large.
 // At least 16384 words.  This list is for objects of 2048 words or larger.
 //     Empty pages are added to this list.  These spaces are called huge.
 class FreeList {
  public:
   explicit FreeList(PagedSpace* owner);
 
   intptr_t Concatenate(FreeList* free_list);
 
+  // Evenly divide available blocks into {free_lists_to_fill}.
+  void Divide(FreeList** free_lists_to_fill, size_t num);
+
   // Clear the free list.
   void Reset();
 
   // Return the number of bytes available on the free list.
   intptr_t available() {
     return small_list_.available() + medium_list_.available() +
            large_list_.available() + huge_list_.available();
   }
 
   // Place a node on the free list.  The block of size 'size_in_bytes'
@@ skipping 40 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_; }
 
+
  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;
   static const int kMediumAllocationMax = kSmallListMax;
   static const int kLargeAllocationMax = kMediumListMax;
 
   FreeSpace* FindNodeFor(int size_in_bytes, int* node_size);
 
   PagedSpace* owner_;
   Heap* heap_;
   FreeListCategory small_list_;
   FreeListCategory medium_list_;
   FreeListCategory large_list_;
   FreeListCategory huge_list_;
 
+  friend class CompactionSpace;
+
   DISALLOW_IMPLICIT_CONSTRUCTORS(FreeList);
 };
 
 
 class AllocationResult {
  public:
   // Implicit constructor from Object*.
   AllocationResult(Object* object)  // NOLINT
       : object_(object) {
     // AllocationResults can't return Smis, which are used to represent
@@ skipping 1029 matching lines @@
     IncreaseCapacity(size_in_bytes);
     Free(start, size_in_bytes);
   }
 
  protected:
   // The space is temporary and not included in any snapshots.
   virtual bool snapshotable() { return false; }
 };
 
 
+class CompactionSpaces : public Malloced {
+ public:
+  explicit CompactionSpaces(Heap* heap)
+      : old_space_(new CompactionSpace(heap, OLD_SPACE,
+                                       Executability::NOT_EXECUTABLE)),
+        code_space_(
+            new CompactionSpace(heap, CODE_SPACE, Executability::EXECUTABLE)) {}
+
+  ~CompactionSpaces() {
+    delete old_space_;
+    delete code_space_;
+  }
+
+  CompactionSpace* Get(AllocationSpace space) {
+    switch (space) {
+      case OLD_SPACE:
+        DCHECK(old_space_ != nullptr);
+        return old_space_;
+      case CODE_SPACE:
+        DCHECK(code_space_ != nullptr);
+        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_